diff options
Diffstat (limited to 'source/blender/blenlib')
70 files changed, 2764 insertions, 1769 deletions
diff --git a/source/blender/blenlib/BLI_alloca.h b/source/blender/blenlib/BLI_alloca.h index b44e6c66d2a..4fa69a24966 100644 --- a/source/blender/blenlib/BLI_alloca.h +++ b/source/blender/blenlib/BLI_alloca.h @@ -29,10 +29,6 @@ /* BLI_array_alloca / alloca */ -#if defined(__MINGW32__) -# include <malloc.h> /* mingw needs for alloca() */ -#endif - #if defined(__GNUC__) || defined(__clang__) #if defined(__cplusplus) && (__cplusplus > 199711L) #define BLI_array_alloca(arr, realsize) \ diff --git a/source/blender/blenlib/BLI_array.h b/source/blender/blenlib/BLI_array.h index c645ff06c00..3ffca818c0d 100644 --- a/source/blender/blenlib/BLI_array.h +++ b/source/blender/blenlib/BLI_array.h @@ -135,11 +135,12 @@ void _bli_array_grow_func(void **arr_p, const void *arr_static, #define BLI_array_append_ret(arr) \ (BLI_array_reserve(arr, 1), &arr[(_##arr##_count++)]) -#define BLI_array_free(arr) \ +#define BLI_array_free(arr) { \ if (arr && (char *)arr != _##arr##_static) { \ - BLI_array_fake_user(arr); \ - MEM_freeN(arr); \ - } (void)0 + BLI_array_fake_user(arr); \ + MEM_freeN(arr); \ + } \ +} ((void)0) #define BLI_array_pop(arr) ( \ (arr && _##arr##_count) ? \ diff --git a/source/blender/blenlib/BLI_compiler_attrs.h b/source/blender/blenlib/BLI_compiler_attrs.h index f0d32670229..4c548654e33 100644 --- a/source/blender/blenlib/BLI_compiler_attrs.h +++ b/source/blender/blenlib/BLI_compiler_attrs.h @@ -92,4 +92,12 @@ # define ATTR_PRINTF_FORMAT(format_param, dots_param) #endif +/* Use to suppress '-Wimplicit-fallthrough' (in place of 'break'). */ +#if defined(__GNUC__) && (__GNUC__ >= 7) /* gcc7.0+ only */ +#define ATTR_FALLTHROUGH __attribute__((fallthrough)) +#else +#define ATTR_FALLTHROUGH ((void)0) +#endif + + #endif /* __BLI_COMPILER_ATTRS_H__ */ diff --git a/source/blender/blenlib/BLI_compiler_compat.h b/source/blender/blenlib/BLI_compiler_compat.h index 8edbc25bcbc..0726e3bb343 100644 --- a/source/blender/blenlib/BLI_compiler_compat.h +++ b/source/blender/blenlib/BLI_compiler_compat.h @@ -32,11 +32,6 @@ # define alloca _alloca #endif -/* alloca is defined here for MinGW32 */ -#ifdef __MINGW32__ -# include <malloc.h> -#endif - #if defined(__cplusplus) && ((__cplusplus >= 201103L) || defined(_MSC_VER)) # define HAS_CPP11_FEATURES #endif @@ -53,12 +48,7 @@ extern "C++" { #if defined(_MSC_VER) # define BLI_INLINE static __forceinline #else -# if (defined(__APPLE__) && defined(__ppc__)) -/* static inline __attribute__ here breaks osx ppc gcc42 build */ -# define BLI_INLINE static __attribute__((always_inline)) __attribute__((__unused__)) -# else -# define BLI_INLINE static inline __attribute__((always_inline)) __attribute__((__unused__)) -# endif +# define BLI_INLINE static inline __attribute__((always_inline)) __attribute__((__unused__)) #endif #endif /* __BLI_COMPILER_COMPAT_H__ */ diff --git a/source/blender/blenlib/BLI_dial.h b/source/blender/blenlib/BLI_dial.h index ad7680fe03e..71ab57bb61a 100644 --- a/source/blender/blenlib/BLI_dial.h +++ b/source/blender/blenlib/BLI_dial.h @@ -52,8 +52,8 @@ typedef struct Dial Dial; -Dial *BLI_dial_initialize(float start_position[2], float threshold); +Dial *BLI_dial_initialize(const float start_position[2], float threshold); -float BLI_dial_angle(Dial *dial, float current_position[2]); +float BLI_dial_angle(Dial *dial, const float current_position[2]); #endif /* __BLI_DIAL_H__ */ diff --git a/source/blender/blenlib/BLI_dynlib.h b/source/blender/blenlib/BLI_dynlib.h index 7d5eb888021..310db9ea051 100644 --- a/source/blender/blenlib/BLI_dynlib.h +++ b/source/blender/blenlib/BLI_dynlib.h @@ -34,7 +34,7 @@ typedef struct DynamicLibrary DynamicLibrary; -DynamicLibrary *BLI_dynlib_open(char *name); +DynamicLibrary *BLI_dynlib_open(const char *name); void *BLI_dynlib_find_symbol(DynamicLibrary *lib, const char *symname); char *BLI_dynlib_get_error_as_string(DynamicLibrary *lib); void BLI_dynlib_close(DynamicLibrary *lib); diff --git a/source/blender/blenlib/BLI_dynstr.h b/source/blender/blenlib/BLI_dynstr.h index 7aa1c30e449..b26accc7f78 100644 --- a/source/blender/blenlib/BLI_dynstr.h +++ b/source/blender/blenlib/BLI_dynstr.h @@ -43,11 +43,14 @@ #include "BLI_compiler_attrs.h" struct DynStr; +struct MemArena; /** The abstract DynStr type */ typedef struct DynStr DynStr; DynStr *BLI_dynstr_new(void) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; +DynStr *BLI_dynstr_new_memarena(void) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; + void BLI_dynstr_append(DynStr *__restrict ds, const char *cstr) ATTR_NONNULL(); void BLI_dynstr_nappend(DynStr *__restrict ds, const char *cstr, int len) ATTR_NONNULL(); @@ -56,8 +59,9 @@ void BLI_dynstr_vappendf(DynStr *__restrict ds, const char *__restrict format int BLI_dynstr_get_len(DynStr *ds) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); char *BLI_dynstr_get_cstring(DynStr *ds) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); - void BLI_dynstr_get_cstring_ex(DynStr *__restrict ds, char *__restrict str) ATTR_NONNULL(); + +void BLI_dynstr_clear(DynStr *ds) ATTR_NONNULL(); void BLI_dynstr_free(DynStr *ds) ATTR_NONNULL(); #endif /* __BLI_DYNSTR_H__ */ diff --git a/source/blender/blenlib/BLI_fileops.h b/source/blender/blenlib/BLI_fileops.h index 91d139c7085..5c1fa57886a 100644 --- a/source/blender/blenlib/BLI_fileops.h +++ b/source/blender/blenlib/BLI_fileops.h @@ -65,10 +65,8 @@ int BLI_create_symlink(const char *path, const char *to) ATTR_NONNULL(); /* keep in sync with the definition of struct direntry in BLI_fileops_types.h */ #ifdef WIN32 -# if defined(_MSC_VER) || defined(__MINGW64__) +# if defined(_MSC_VER) typedef struct _stat64 BLI_stat_t; -# elif defined(__MINGW32__) -typedef struct _stati64 BLI_stat_t; # else typedef struct _stat BLI_stat_t; # endif diff --git a/source/blender/blenlib/BLI_fileops_types.h b/source/blender/blenlib/BLI_fileops_types.h index 0cf8c8ddb4a..0ffa3276f1f 100644 --- a/source/blender/blenlib/BLI_fileops_types.h +++ b/source/blender/blenlib/BLI_fileops_types.h @@ -35,7 +35,7 @@ #include <sys/stat.h> -#if defined(WIN32) && !defined(FREE_WINDOWS) +#if defined(WIN32) typedef unsigned int mode_t; #endif @@ -50,10 +50,8 @@ struct direntry { const char *relname; const char *path; #ifdef WIN32 /* keep in sync with the definition of BLI_stat_t in BLI_fileops.h */ -# if defined(_MSC_VER) || defined(__MINGW64__) +# if defined(_MSC_VER) struct _stat64 s; -# elif defined(__MINGW32__) - struct _stati64 s; # else struct _stat s; # endif diff --git a/source/blender/blenlib/BLI_fnmatch.h b/source/blender/blenlib/BLI_fnmatch.h index f69f5b39869..06fa5048622 100644 --- a/source/blender/blenlib/BLI_fnmatch.h +++ b/source/blender/blenlib/BLI_fnmatch.h @@ -28,7 +28,7 @@ extern "C" { #endif -#if defined WIN32 && !defined _LIBC || defined __sun +#if defined WIN32 && !defined _LIBC #if defined(__cplusplus) || (defined(__STDC__) && __STDC__) #undef __P @@ -53,7 +53,7 @@ extern "C" { #define FNM_NOESCAPE (1 << 1) /* Backslashes don't quote special chars. */ #define FNM_PERIOD (1 << 2) /* Leading `.' is matched only explicitly. */ -#if !defined(_POSIX_C_SOURCE) || _POSIX_C_SOURCE < 2 || defined(_GNU_SOURCE) || defined(__SUNPRO_C) +#if !defined(_POSIX_C_SOURCE) || _POSIX_C_SOURCE < 2 || defined(_GNU_SOURCE) #define FNM_FILE_NAME FNM_PATHNAME /* Preferred GNU name. */ #define FNM_LEADING_DIR (1 << 3) /* Ignore `/...' after a match. */ #define FNM_CASEFOLD (1 << 4) /* Compare without regard to case. */ @@ -72,7 +72,7 @@ extern int fnmatch __P((const char *__pattern, const char *__string, # define _GNU_SOURCE # endif # include <fnmatch.h> -#endif /* defined WIN32 && !defined _LIBC || defined __sun */ +#endif /* defined WIN32 && !defined _LIBC */ #ifdef __cplusplus } diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h index 7e3a009ede8..b42a36a3567 100644 --- a/source/blender/blenlib/BLI_ghash.h +++ b/source/blender/blenlib/BLI_ghash.h @@ -43,7 +43,7 @@ extern "C" { #ifndef GHASH_INTERNAL_API # ifdef __GNUC__ # undef _GHASH_INTERNAL_ATTR -# define _GHASH_INTERNAL_ATTR __attribute__ ((deprecated)) +# define _GHASH_INTERNAL_ATTR __attribute__ ((deprecated)) /* not deprecated, just private. */ # endif #endif @@ -90,6 +90,7 @@ void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfre void BLI_ghash_reserve(GHash *gh, const unsigned int nentries_reserve); void BLI_ghash_insert(GHash *gh, void *key, void *val); bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); +void *BLI_ghash_replace_key(GHash *gh, void *key); void *BLI_ghash_lookup(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT; void *BLI_ghash_lookup_default(GHash *gh, const void *key, void *val_default) ATTR_WARN_UNUSED_RESULT; void **BLI_ghash_lookup_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT; @@ -167,6 +168,8 @@ unsigned int BLI_ghashutil_inthash_p_murmur(const void *ptr); unsigned int BLI_ghashutil_inthash_p_simple(const void *ptr); bool BLI_ghashutil_intcmp(const void *a, const void *b); +size_t BLI_ghashutil_combine_hash(size_t hash_a, size_t hash_b); + unsigned int BLI_ghashutil_uinthash_v4(const unsigned int key[4]); #define BLI_ghashutil_inthash_v4(key) ( \ @@ -246,6 +249,7 @@ void BLI_gset_insert(GSet *gh, void *key); bool BLI_gset_add(GSet *gs, void *key); bool BLI_gset_ensure_p_ex(GSet *gs, const void *key, void ***r_key); bool BLI_gset_reinsert(GSet *gh, void *key, GSetKeyFreeFP keyfreefp); +void *BLI_gset_replace_key(GSet *gs, void *key); bool BLI_gset_haskey(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT; bool BLI_gset_pop(GSet *gs, GSetIterState *state, void **r_key) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp); @@ -294,6 +298,25 @@ double BLI_ghash_calc_quality(GHash *gh); double BLI_gset_calc_quality(GSet *gs); #endif /* GHASH_INTERNAL_API */ +#define GHASH_FOREACH_BEGIN(type, var, what) \ + do { \ + GHashIterator gh_iter##var; \ + GHASH_ITER(gh_iter##var, what) { \ + type var = (type)(BLI_ghashIterator_getValue(&gh_iter##var)); \ + +#define GHASH_FOREACH_END() \ + } \ + } while(0) + +#define GSET_FOREACH_BEGIN(type, var, what) \ + do { \ + GSetIterator gh_iter##var; \ + GSET_ITER(gh_iter##var, what) { \ + type var = (type)(BLI_gsetIterator_getKey(&gh_iter##var)); + +#define GSET_FOREACH_END() \ + } \ + } while(0) #ifdef __cplusplus } diff --git a/source/blender/blenlib/BLI_hash.h b/source/blender/blenlib/BLI_hash.h new file mode 100644 index 00000000000..e849e5f8f61 --- /dev/null +++ b/source/blender/blenlib/BLI_hash.h @@ -0,0 +1,66 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_HASH_H__ +#define __BLI_HASH_H__ + +/** \file BLI_hash.h + * \ingroup bli + */ + +BLI_INLINE unsigned int BLI_hash_int_2d(unsigned int kx, unsigned int ky) +{ +#define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) + + unsigned int a, b, c; + + a = b = c = 0xdeadbeef + (2 << 2) + 13; + a += kx; + b += ky; + + c ^= b; c -= rot(b, 14); + a ^= c; a -= rot(c, 11); + b ^= a; b -= rot(a, 25); + c ^= b; c -= rot(b, 16); + a ^= c; a -= rot(c, 4); + b ^= a; b -= rot(a, 14); + c ^= b; c -= rot(b, 24); + + return c; + +#undef rot +} + +BLI_INLINE unsigned int BLI_hash_string(const char *str) +{ + unsigned int i = 0, c; + + while ((c = *str++)) { + i = i * 37 + c; + } + return i; +} + +BLI_INLINE unsigned int BLI_hash_int(unsigned int k) +{ + return BLI_hash_int_2d(k, 0); +} + +#endif // __BLI_HASH_H__ diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h index 91d39801645..564659ad21e 100644 --- a/source/blender/blenlib/BLI_kdopbvh.h +++ b/source/blender/blenlib/BLI_kdopbvh.h @@ -36,7 +36,7 @@ */ #ifdef __cplusplus -extern "C" { +extern "C" { #endif struct BVHTree; @@ -62,7 +62,7 @@ typedef struct BVHTreeNearest { int index; /* the index of the nearest found (untouched if none is found within a dist radius from the given coordinates) */ float co[3]; /* nearest coordinates (untouched it none is found within a dist radius from the given coordinates) */ float no[3]; /* normal at nearest coordinates (untouched it none is found within a dist radius from the given coordinates) */ - float dist_sq; /* squared distance to search arround */ + float dist_sq; /* squared distance to search around */ int flags; } BVHTreeNearest; @@ -95,10 +95,6 @@ typedef void (*BVHTree_NearestPointCallback)(void *userdata, int index, const fl /* callback must update hit in case it finds a nearest successful hit */ typedef void (*BVHTree_RayCastCallback)(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit); -/* callback must update nearest in case it finds a nearest result */ -typedef void (*BVHTree_NearestToRayCallback)(void *userdata, const float ray_co[3], const float ray_dir[3], - const float scale[3], int index, BVHTreeNearest *nearest); - /* callback to check if 2 nodes overlap (use thread if intersection results need to be stored) */ typedef bool (*BVHTree_OverlapCallback)(void *userdata, int index_a, int index_b, int thread); @@ -143,18 +139,6 @@ int BLI_bvhtree_find_nearest( BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata); -int BLI_bvhtree_find_nearest_to_ray_angle( - BVHTree *tree, const float co[3], const float dir[3], - const bool ray_is_normalized, const float scale[3], - BVHTreeNearest *nearest, - BVHTree_NearestToRayCallback callback, void *userdata); - -int BLI_bvhtree_find_nearest_to_ray( - BVHTree *tree, const float co[3], const float dir[3], - const bool ray_is_normalized, const float scale[3], - BVHTreeNearest *nearest, - BVHTree_NearestToRayCallback callback, void *userdata); - int BLI_bvhtree_ray_cast_ex( BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata, diff --git a/source/blender/blenlib/BLI_kdtree.h b/source/blender/blenlib/BLI_kdtree.h index aa54e1c823c..18908f8c551 100644 --- a/source/blender/blenlib/BLI_kdtree.h +++ b/source/blender/blenlib/BLI_kdtree.h @@ -66,6 +66,10 @@ void BLI_kdtree_range_search_cb( const KDTree *tree, const float co[3], float range, bool (*search_cb)(void *user_data, int index, const float co[3], float dist_sq), void *user_data); +int BLI_kdtree_calc_duplicates_fast( + const KDTree *tree, const float range, bool use_index_order, + int *doubles); + /* Normal use is deprecated */ /* remove __normal functions when last users drop */ int BLI_kdtree_find_nearest_n__normal( diff --git a/source/blender/blenlib/BLI_listbase.h b/source/blender/blenlib/BLI_listbase.h index 96349a7b066..b06944e4985 100644 --- a/source/blender/blenlib/BLI_listbase.h +++ b/source/blender/blenlib/BLI_listbase.h @@ -67,6 +67,7 @@ void *BLI_poptail(ListBase *listbase) ATTR_NONNULL(1); void BLI_addhead(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1); void BLI_insertlinkbefore(struct ListBase *listbase, void *vnextlink, void *vnewlink) ATTR_NONNULL(1); void BLI_insertlinkafter(struct ListBase *listbase, void *vprevlink, void *vnewlink) ATTR_NONNULL(1); +void BLI_insertlinkreplace(ListBase *listbase, void *v_l_src, void *v_l_dst) ATTR_NONNULL(1, 2, 3); void BLI_listbase_sort(struct ListBase *listbase, int (*cmp)(const void *, const void *)) ATTR_NONNULL(1, 2); void BLI_listbase_sort_r(ListBase *listbase, int (*cmp)(void *, const void *, const void *), void *thunk) ATTR_NONNULL(1, 2); bool BLI_listbase_link_move(ListBase *listbase, void *vlink, int step) ATTR_NONNULL(); @@ -124,6 +125,11 @@ if ((lb)->last && (lb_init || (lb_init = (lb)->last))) { \ (lb_iter != lb_init)); \ } +#define LINKLIST_FOREACH(type, var, list) \ + for (type var = (type)((list)->first); \ + var != NULL; \ + var = (type)(((Link*)(var))->next)) + #ifdef __cplusplus } #endif diff --git a/source/blender/blenlib/BLI_math_base.h b/source/blender/blenlib/BLI_math_base.h index e97a250cd24..e6a72298ae7 100644 --- a/source/blender/blenlib/BLI_math_base.h +++ b/source/blender/blenlib/BLI_math_base.h @@ -85,63 +85,6 @@ static const int NAN_INT = 0x7FC00000; # define NAN_FLT (*((float *)(&NAN_INT))) #endif -/* do not redefine functions from C99, POSIX.1-2001 or MSVC12 (partial C99) */ -#if !(defined(_ISOC99_SOURCE) || (defined(_POSIX_C_SOURCE) && _POSIX_C_SOURCE >= 200112L) || defined(_MSC_VER)) - -#ifndef sqrtf -#define sqrtf(a) ((float)sqrt(a)) -#endif -#ifndef powf -#define powf(a, b) ((float)pow(a, b)) -#endif -#ifndef cosf -#define cosf(a) ((float)cos(a)) -#endif -#ifndef sinf -#define sinf(a) ((float)sin(a)) -#endif -#ifndef acosf -#define acosf(a) ((float)acos(a)) -#endif -#ifndef asinf -#define asinf(a) ((float)asin(a)) -#endif -#ifndef atan2f -#define atan2f(a, b) ((float)atan2(a, b)) -#endif -#ifndef tanf -#define tanf(a) ((float)tan(a)) -#endif -#ifndef atanf -#define atanf(a) ((float)atan(a)) -#endif -#ifndef floorf -#define floorf(a) ((float)floor(a)) -#endif -#ifndef ceilf -#define ceilf(a) ((float)ceil(a)) -#endif -#ifndef fabsf -#define fabsf(a) ((float)fabs(a)) -#endif -#ifndef logf -#define logf(a) ((float)log(a)) -#endif -#ifndef expf -#define expf(a) ((float)exp(a)) -#endif -#ifndef fmodf -#define fmodf(a, b) ((float)fmod(a, b)) -#endif -#ifndef hypotf -#define hypotf(a, b) ((float)hypot(a, b)) -#endif -#ifndef copysignf -#define copysignf(a, b) ((float)copysign(a, b)) -#endif - -#endif /* C99, POSIX.1-2001 or MSVC12 (partial C99) */ - #if BLI_MATH_DO_INLINE #include "intern/math_base_inline.c" #endif @@ -195,6 +138,9 @@ MINLINE int signum_i(float a); MINLINE float power_of_2(float f); +MINLINE int integer_digits_f(const float f); +MINLINE int integer_digits_d(const double d); + /* these don't really fit anywhere but were being copied about a lot */ MINLINE int is_power_of_2_i(int n); MINLINE int power_of_2_max_i(int n); @@ -203,10 +149,37 @@ MINLINE int power_of_2_min_i(int n); MINLINE unsigned int power_of_2_max_u(unsigned int x); MINLINE unsigned int power_of_2_min_u(unsigned int x); -MINLINE int iroundf(float a); MINLINE int divide_round_i(int a, int b); MINLINE int mod_i(int i, int n); +MINLINE signed char round_fl_to_char(float a); +MINLINE unsigned char round_fl_to_uchar(float a); +MINLINE short round_fl_to_short(float a); +MINLINE unsigned short round_fl_to_ushort(float a); +MINLINE int round_fl_to_int(float a); +MINLINE unsigned int round_fl_to_uint(float a); + +MINLINE signed char round_db_to_char(double a); +MINLINE unsigned char round_db_to_uchar(double a); +MINLINE short round_db_to_short(double a); +MINLINE unsigned short round_db_to_ushort(double a); +MINLINE int round_db_to_int(double a); +MINLINE unsigned int round_db_to_uint(double a); + +MINLINE signed char round_fl_to_char_clamp(float a); +MINLINE unsigned char round_fl_to_uchar_clamp(float a); +MINLINE short round_fl_to_short_clamp(float a); +MINLINE unsigned short round_fl_to_ushort_clamp(float a); +MINLINE int round_fl_to_int_clamp(float a); +MINLINE unsigned int round_fl_to_uint_clamp(float a); + +MINLINE signed char round_db_to_char_clamp(double a); +MINLINE unsigned char round_db_to_uchar_clamp(double a); +MINLINE short round_db_to_short_clamp(double a); +MINLINE unsigned short round_db_to_ushort_clamp(double a); +MINLINE int round_db_to_int_clamp(double a); +MINLINE unsigned int round_db_to_uint_clamp(double a); + int pow_i(int base, int exp); double double_round(double x, int ndigits); diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index 514b0300274..933e31ba84b 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -44,9 +44,6 @@ extern "C" { /********************************** Polygons *********************************/ -void cent_tri_v3(float r[3], const float a[3], const float b[3], const float c[3]); -void cent_quad_v3(float r[3], const float a[3], const float b[3], const float c[3], const float d[3]); - float normal_tri_v3(float r[3], const float a[3], const float b[3], const float c[3]); float normal_quad_v3(float r[3], const float a[3], const float b[3], const float c[3], const float d[3]); float normal_poly_v3(float r[3], const float verts[][3], unsigned int nr); @@ -122,6 +119,26 @@ float dist_squared_ray_to_seg_v3( const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], float r_point[3], float *r_depth); + +struct DistRayAABB_Precalc { + float ray_origin[3]; + float ray_direction[3]; + float ray_inv_dir[3]; + bool sign[3]; +}; +void dist_squared_ray_to_aabb_v3_precalc( + struct DistRayAABB_Precalc *neasrest_precalc, + const float ray_origin[3], const float ray_direction[3]); +float dist_squared_ray_to_aabb_v3( + const struct DistRayAABB_Precalc *data, + const float bb_min[3], const float bb_max[3], + float r_point[3], float *r_depth); +/* when there is no advantage to precalc. */ +float dist_squared_ray_to_aabb_v3_simple( + const float ray_origin[3], const float ray_direction[3], + const float bb_min[3], const float bb_max[3], + float r_point[3], float *r_depth); + float closest_to_line_v2(float r_close[2], const float p[2], const float l1[2], const float l2[2]); float closest_to_line_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3]); void closest_to_line_segment_v2(float r_close[2], const float p[2], const float l1[2], const float l2[2]); @@ -169,8 +186,14 @@ void limit_dist_v3(float v1[3], float v2[3], const float dist); int isect_seg_seg_v2(const float a1[2], const float a2[2], const float b1[2], const float b2[2]); int isect_seg_seg_v2_int(const int a1[2], const int a2[2], const int b1[2], const int b2[2]); -int isect_seg_seg_v2_point(const float v0[2], const float v1[2], const float v2[2], const float v3[2], float vi[2]); -bool isect_seg_seg_v2_simple(const float v1[2], const float v2[2], const float v3[2], const float v4[2]); +int isect_seg_seg_v2_point_ex( + const float v0[2], const float v1[2], const float v2[2], const float v3[2], const float endpoint_bias, + float vi[2]); +int isect_seg_seg_v2_point( + const float v0[2], const float v1[2], const float v2[2], const float v3[2], + float vi[2]); +bool isect_seg_seg_v2_simple( + const float v1[2], const float v2[2], const float v3[2], const float v4[2]); int isect_line_sphere_v3(const float l1[3], const float l2[3], const float sp[3], const float r, float r_p1[3], float r_p2[3]); int isect_line_sphere_v2(const float l1[2], const float l2[2], const float sp[2], const float r, float r_p1[2], float r_p2[2]); @@ -296,23 +319,10 @@ void isect_ray_aabb_v3_precalc( bool isect_ray_aabb_v3( const struct IsectRayAABB_Precalc *data, const float bb_min[3], const float bb_max[3], float *tmin); - -struct NearestRayToAABB_Precalc { - float ray_origin[3]; - float ray_direction[3]; - float ray_inv_dir[3]; - float cdot_axis[3]; - float idiag_sq[3]; - bool sign[3]; -}; - -void dist_squared_ray_to_aabb_v3_precalc( - struct NearestRayToAABB_Precalc *data, - const float ray_origin[3], const float ray_direction[3]); -float dist_squared_ray_to_aabb_v3( - const struct NearestRayToAABB_Precalc *data, +bool isect_ray_aabb_v3_simple( + const float orig[3], const float dir[3], const float bb_min[3], const float bb_max[3], - bool r_axis_closest[3]); + float *tmin, float *tmax); /* other */ bool isect_sweeping_sphere_tri_v3(const float p1[3], const float p2[3], const float radius, @@ -326,10 +336,8 @@ bool clip_segment_v3_plane_n( float r_p1[3], float r_p2[3]); /****************************** Interpolation ********************************/ - -/* tri or quad, d can be NULL */ -void interp_weights_face_v3(float w[4], - const float a[3], const float b[3], const float c[3], const float d[3], const float p[3]); +void interp_weights_tri_v3(float w[3], const float a[3], const float b[3], const float c[3], const float p[3]); +void interp_weights_quad_v3(float w[4], const float a[3], const float b[3], const float c[3], const float d[3], const float p[3]); void interp_weights_poly_v3(float w[], float v[][3], const int n, const float co[3]); void interp_weights_poly_v2(float w[], float v[][2], const int n, const float co[2]); @@ -394,26 +402,28 @@ void box_minmax_bounds_m4(float min[3], float max[3], void map_to_tube(float *r_u, float *r_v, const float x, const float y, const float z); void map_to_sphere(float *r_u, float *r_v, const float x, const float y, const float z); +void map_to_plane_v2_v3v3(float r_co[2], const float co[3], const float no[3]); +void map_to_plane_axis_angle_v2_v3v3fl(float r_co[2], const float co[3], const float axis[3], const float angle); /********************************** Normals **********************************/ -void accumulate_vertex_normals_tri( +void accumulate_vertex_normals_tri_v3( float n1[3], float n2[3], float n3[3], const float f_no[3], const float co1[3], const float co2[3], const float co3[3]); -void accumulate_vertex_normals( +void accumulate_vertex_normals_v3( float n1[3], float n2[3], float n3[3], float n4[3], const float f_no[3], const float co1[3], const float co2[3], const float co3[3], const float co4[3]); -void accumulate_vertex_normals_poly( +void accumulate_vertex_normals_poly_v3( float **vertnos, const float polyno[3], const float **vertcos, float vdiffs[][3], const int nverts); /********************************* Tangents **********************************/ -void tangent_from_uv( +void tangent_from_uv_v3( const float uv1[2], const float uv2[2], const float uv3[2], const float co1[3], const float co2[3], const float co3[3], const float n[3], @@ -421,9 +431,9 @@ void tangent_from_uv( /******************************** Vector Clouds ******************************/ -void vcloud_estimate_transform(int list_size, float (*pos)[3], float *weight, - float (*rpos)[3], float *rweight, - float lloc[3], float rloc[3], float lrot[3][3], float lscale[3][3]); +void vcloud_estimate_transform_v3( + const int list_size, const float (*pos)[3], const float *weight, const float (*rpos)[3], const float *rweight, + float lloc[3], float rloc[3], float lrot[3][3], float lscale[3][3]); /****************************** Spherical Harmonics *************************/ @@ -454,7 +464,7 @@ float form_factor_hemi_poly(float p[3], float n[3], float v1[3], float v2[3], float v3[3], float v4[3]); void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3]); -void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3]); +void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3]); MINLINE void axis_dominant_v3(int *r_axis_a, int *r_axis_b, const float axis[3]); MINLINE float axis_dominant_v3_max(int *r_axis_a, int *r_axis_b, const float axis[3]) ATTR_WARN_UNUSED_RESULT; diff --git a/source/blender/blenlib/BLI_math_inline.h b/source/blender/blenlib/BLI_math_inline.h index 840cf24f8cf..383abda5b2f 100644 --- a/source/blender/blenlib/BLI_math_inline.h +++ b/source/blender/blenlib/BLI_math_inline.h @@ -44,12 +44,7 @@ extern "C" { # define MALWAYS_INLINE MINLINE # else # define MINLINE static inline -# if (defined(__APPLE__) && defined(__ppc__)) - /* static inline __attribute__ here breaks osx ppc gcc42 build */ -# define MALWAYS_INLINE static __attribute__((always_inline)) __attribute__((unused)) -# else -# define MALWAYS_INLINE static inline __attribute__((always_inline)) __attribute__((unused)) -# endif +# define MALWAYS_INLINE static inline __attribute__((always_inline)) __attribute__((unused)) # endif #else # define MINLINE diff --git a/source/blender/blenlib/BLI_math_matrix.h b/source/blender/blenlib/BLI_math_matrix.h index 8124e07dd47..d0dfad2a02f 100644 --- a/source/blender/blenlib/BLI_math_matrix.h +++ b/source/blender/blenlib/BLI_math_matrix.h @@ -219,7 +219,6 @@ void mat4_to_size(float r[3], float M[4][4]); void translate_m4(float mat[4][4], float tx, float ty, float tz); void rotate_m4(float mat[4][4], const char axis, const float angle); -void rotate_m2(float mat[2][2], const float angle); void transform_pivot_set_m4(float mat[4][4], const float pivot[3]); void mat3_to_rot_size(float rot[3][3], float size[3], float mat3[3][3]); diff --git a/source/blender/blenlib/BLI_math_rotation.h b/source/blender/blenlib/BLI_math_rotation.h index 24c20ee7b50..e059327a490 100644 --- a/source/blender/blenlib/BLI_math_rotation.h +++ b/source/blender/blenlib/BLI_math_rotation.h @@ -122,8 +122,9 @@ void mat3_to_axis_angle(float axis[3], float *angle, float M[3][3]); void mat4_to_axis_angle(float axis[3], float *angle, float M[4][4]); void quat_to_axis_angle(float axis[3], float *angle, const float q[4]); -void axis_angle_to_mat3_single(float R[3][3], const char axis, const float angle); void angle_to_mat2(float R[2][2], const float angle); +void axis_angle_to_mat3_single(float R[3][3], const char axis, const float angle); +void axis_angle_to_mat4_single(float R[4][4], const char axis, const float angle); void axis_angle_to_quat_single(float q[4], const char axis, const float angle); @@ -217,8 +218,12 @@ float angle_wrap_deg(float angle); float angle_compat_rad(float angle, float angle_compat); -int mat3_from_axis_conversion(int from_forward, int from_up, int to_forward, int to_up, - float r_mat[3][3]); +bool mat3_from_axis_conversion( + int src_forward, int src_up, int dst_forward, int dst_up, + float r_mat[3][3]); +bool mat3_from_axis_conversion_single( + int src_axis, int dst_axis, + float r_mat[3][3]); #ifdef __cplusplus } diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h index d15fe1a95dc..4fdb33926a2 100644 --- a/source/blender/blenlib/BLI_math_vector.h +++ b/source/blender/blenlib/BLI_math_vector.h @@ -234,6 +234,7 @@ void mid_v3_v3v3(float r[3], const float a[3], const float b[3]); void mid_v2_v2v2(float r[2], const float a[2], const float b[2]); void mid_v3_v3v3v3(float v[3], const float v1[3], const float v2[3], const float v3[3]); void mid_v3_v3v3v3v3(float v[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3]); +void mid_v3_v3_array(float r[3], const float (*vec_arr)[3], const unsigned int nbr); void mid_v3_v3v3_angle_weighted(float r[3], const float a[3], const float b[3]); void mid_v3_angle_weighted(float r[3]); @@ -285,6 +286,8 @@ float angle_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT; float angle_v3v3v3(const float a[3], const float b[3], const float c[3]) ATTR_WARN_UNUSED_RESULT; float cos_v3v3v3(const float p1[3], const float p2[3], const float p3[3]) ATTR_WARN_UNUSED_RESULT; float cos_v2v2v2(const float p1[2], const float p2[2], const float p3[2]) ATTR_WARN_UNUSED_RESULT; +float angle_on_axis_v3v3_v3(const float v1[3], const float v2[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT; +float angle_signed_on_axis_v3v3_v3(const float v1[3], const float v2[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT; float angle_normalized_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT; float angle_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT; float angle_signed_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT; @@ -296,8 +299,12 @@ void angle_poly_v3(float *angles, const float *verts[3], int len); void project_v2_v2v2(float out[2], const float p[2], const float v_proj[2]); void project_v3_v3v3(float out[3], const float p[3], const float v_proj[3]); +void project_v2_v2v2_normalized(float out[2], const float p[2], const float v_proj[2]); +void project_v3_v3v3_normalized(float out[3], const float p[3], const float v_proj[3]); void project_plane_v3_v3v3(float out[3], const float p[3], const float v_plane[3]); void project_plane_v2_v2v2(float out[2], const float p[2], const float v_plane[2]); +void project_plane_normalized_v3_v3v3(float out[3], const float p[3], const float v_plane[3]); +void project_plane_normalized_v2_v2v2(float out[2], const float p[2], const float v_plane[2]); void project_v3_plane(float out[3], const float plane_no[3], const float plane_co[3]); void reflect_v3_v3v3(float out[3], const float vec[3], const float normal[3]); void ortho_basis_v3v3_v3(float r_n1[3], float r_n2[3], const float n[3]); diff --git a/source/blender/blenlib/BLI_path_util.h b/source/blender/blenlib/BLI_path_util.h index 1a626ff44bd..b59e7f99d59 100644 --- a/source/blender/blenlib/BLI_path_util.h +++ b/source/blender/blenlib/BLI_path_util.h @@ -39,20 +39,12 @@ extern "C" { struct ListBase; -#ifdef WIN32 -#define SEP '\\' -#define ALTSEP '/' -#else -#define SEP '/' -#define ALTSEP '\\' -#endif - void BLI_setenv(const char *env, const char *val) ATTR_NONNULL(1); void BLI_setenv_if_new(const char *env, const char *val) ATTR_NONNULL(1); void BLI_make_file_string(const char *relabase, char *string, const char *dir, const char *file); void BLI_make_exist(char *dir); -void BLI_make_existing_file(const char *name); +bool BLI_make_existing_file(const char *name); void BLI_split_dirfile(const char *string, char *dir, char *file, const size_t dirlen, const size_t filelen); void BLI_split_dir_part(const char *string, char *dir, const size_t dirlen); void BLI_split_file_part(const char *string, char *file, const size_t filelen); @@ -60,7 +52,13 @@ void BLI_path_append(char *__restrict dst, const size_t maxlen, const char *__restrict file) ATTR_NONNULL(); void BLI_join_dirfile(char *__restrict string, const size_t maxlen, const char *__restrict dir, const char *__restrict file) ATTR_NONNULL(); +size_t BLI_path_join( + char *__restrict dst, const size_t dst_len, + const char *path_first, ...) ATTR_NONNULL(1, 3) ATTR_SENTINEL(0); const char *BLI_path_basename(const char *path) ATTR_NONNULL() ATTR_WARN_UNUSED_RESULT; +bool BLI_path_name_at_index( + const char *__restrict path, const int index, + int *__restrict r_offset, int *__restrict r_len) ATTR_NONNULL() ATTR_WARN_UNUSED_RESULT; #if 0 typedef enum bli_rebase_state { @@ -83,7 +81,6 @@ bool BLI_path_program_extensions_add_win32(char *name, const size_t maxlen); #endif bool BLI_path_program_search(char *fullname, const size_t maxlen, const char *name); -void BLI_getlastdir(const char *dir, char *last, const size_t maxlen); bool BLI_testextensie(const char *str, const char *ext) ATTR_NONNULL() ATTR_WARN_UNUSED_RESULT; bool BLI_testextensie_n(const char *str, ...) ATTR_NONNULL(1) ATTR_SENTINEL(0); bool BLI_testextensie_array(const char *str, const char **ext_array) ATTR_NONNULL() ATTR_WARN_UNUSED_RESULT; @@ -91,13 +88,8 @@ bool BLI_testextensie_glob(const char *str, const char *ext_fnmatch) ATTR_NONNUL bool BLI_replace_extension(char *path, size_t maxlen, const char *ext) ATTR_NONNULL(); bool BLI_ensure_extension(char *path, size_t maxlen, const char *ext) ATTR_NONNULL(); bool BLI_ensure_filename(char *filepath, size_t maxlen, const char *filename) ATTR_NONNULL(); -bool BLI_uniquename(struct ListBase *list, void *vlink, const char *defname, char delim, int name_offs, int len); -bool BLI_uniquename_cb(bool (*unique_check)(void *arg, const char *name), - void *arg, const char *defname, char delim, char *name, int name_len); -void BLI_newname(char *name, int add); int BLI_stringdec(const char *string, char *head, char *start, unsigned short *numlen); void BLI_stringenc(char *string, const char *head, const char *tail, unsigned short numlen, int pic); -int BLI_split_name_num(char *left, int *nr, const char *name, const char delim); /* removes trailing slash */ void BLI_cleanup_file(const char *relabase, char *path) ATTR_NONNULL(2); @@ -148,6 +140,18 @@ bool BLI_path_suffix(char *string, size_t maxlen, const char *suffix, const char # define FILE_MAX 1024 #endif +#ifdef WIN32 +# define SEP '\\' +# define ALTSEP '/' +# define SEP_STR "\\" +# define ALTSEP_STR "/" +#else +# define SEP '/' +# define ALTSEP '\\' +# define SEP_STR "/" +# define ALTSEP_STR "\\" +#endif + /* Parent and current dir helpers. */ #define FILENAME_PARENT ".." #define FILENAME_CURRENT "." diff --git a/source/blender/blenlib/BLI_polyfill2d_beautify.h b/source/blender/blenlib/BLI_polyfill2d_beautify.h index 20e53b080fe..29a900200bb 100644 --- a/source/blender/blenlib/BLI_polyfill2d_beautify.h +++ b/source/blender/blenlib/BLI_polyfill2d_beautify.h @@ -33,8 +33,12 @@ void BLI_polyfill_beautify( /* structs for reuse */ struct MemArena *arena, struct Heap *eheap, struct EdgeHash *eh); -float BLI_polyfill_beautify_quad_rotate_calc( - const float v1[2], const float v2[2], const float v3[2], const float v4[2]); +float BLI_polyfill_beautify_quad_rotate_calc_ex( + const float v1[2], const float v2[2], const float v3[2], const float v4[2], + const bool lock_degenerate); +#define BLI_polyfill_beautify_quad_rotate_calc(v1, v2, v3, v4) \ + BLI_polyfill_beautify_quad_rotate_calc_ex(v1, v2, v3, v4, false) + /* avoid realloc's when creating new structures for polyfill ngons */ #define BLI_POLYFILL_ALLOC_NGON_RESERVE 64 diff --git a/source/blender/blenlib/BLI_rect.h b/source/blender/blenlib/BLI_rect.h index 59bf3644912..471d875c9af 100644 --- a/source/blender/blenlib/BLI_rect.h +++ b/source/blender/blenlib/BLI_rect.h @@ -47,12 +47,16 @@ bool BLI_rcti_is_empty(const struct rcti *rect); bool BLI_rctf_is_empty(const struct rctf *rect); void BLI_rctf_init(struct rctf *rect, float xmin, float xmax, float ymin, float ymax); void BLI_rcti_init(struct rcti *rect, int xmin, int xmax, int ymin, int ymax); +void BLI_rctf_init_pt_radius(struct rctf *rect, const float xy[2], float size); +void BLI_rcti_init_pt_radius(struct rcti *rect, const int xy[2], int size); void BLI_rcti_init_minmax(struct rcti *rect); void BLI_rctf_init_minmax(struct rctf *rect); void BLI_rcti_do_minmax_v(struct rcti *rect, const int xy[2]); void BLI_rctf_do_minmax_v(struct rctf *rect, const float xy[2]); void BLI_rctf_transform_pt_v(const rctf *dst, const rctf *src, float xy_dst[2], const float xy_src[2]); +void BLI_rctf_transform_calc_m4_pivot_min_ex(const rctf *dst, const rctf *src, float matrix[4][4], uint x, uint y); +void BLI_rctf_transform_calc_m4_pivot_min(const rctf *dst, const rctf *src, float matrix[4][4]); void BLI_rctf_translate(struct rctf *rect, float x, float y); void BLI_rcti_translate(struct rcti *rect, int x, int y); @@ -95,6 +99,7 @@ void BLI_rctf_union(struct rctf *rctf1, const struct rctf *rctf2); void BLI_rcti_rctf_copy(struct rcti *dst, const struct rctf *src); void BLI_rctf_rcti_copy(struct rctf *dst, const struct rcti *src); void BLI_rcti_rctf_copy_floor(struct rcti *dst, const struct rctf *src); +void BLI_rcti_rctf_copy_round(struct rcti *dst, const struct rctf *src); void BLI_rctf_rotate_expand(rctf *dst, const rctf *src, const float angle); diff --git a/source/blender/blenlib/BLI_stack.h b/source/blender/blenlib/BLI_stack.h index 222005ee92e..d54f2a7bab2 100644 --- a/source/blender/blenlib/BLI_stack.h +++ b/source/blender/blenlib/BLI_stack.h @@ -30,6 +30,10 @@ #include "BLI_compiler_attrs.h" +#ifdef __cplusplus +extern "C" { +#endif + typedef struct BLI_Stack BLI_Stack; BLI_Stack *BLI_stack_new_ex( @@ -55,4 +59,8 @@ size_t BLI_stack_count(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONN bool BLI_stack_is_empty(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +#ifdef __cplusplus +} +#endif + #endif /* __BLI_STACK_H__ */ diff --git a/source/blender/blenlib/BLI_strict_flags.h b/source/blender/blenlib/BLI_strict_flags.h index 964ee06469d..86b7285655e 100644 --- a/source/blender/blenlib/BLI_strict_flags.h +++ b/source/blender/blenlib/BLI_strict_flags.h @@ -30,6 +30,8 @@ #ifdef __GNUC__ # if (__GNUC__ * 100 + __GNUC_MINOR__) >= 406 /* gcc4.6+ only */ # pragma GCC diagnostic error "-Wsign-compare" +# endif +# if __GNUC__ >= 6 /* gcc6+ only */ # pragma GCC diagnostic error "-Wconversion" # endif # if (__GNUC__ * 100 + __GNUC_MINOR__) >= 408 diff --git a/source/blender/blenlib/BLI_string_utf8.h b/source/blender/blenlib/BLI_string_utf8.h index 0740b574c1a..32504a88b48 100644 --- a/source/blender/blenlib/BLI_string_utf8.h +++ b/source/blender/blenlib/BLI_string_utf8.h @@ -36,8 +36,8 @@ extern "C" { char *BLI_strncpy_utf8(char *__restrict dst, const char *__restrict src, size_t maxncpy) ATTR_NONNULL(); size_t BLI_strncpy_utf8_rlen(char *__restrict dst, const char *__restrict src, size_t maxncpy) ATTR_NONNULL(); char *BLI_strncat_utf8(char *__restrict dst, const char *__restrict src, size_t maxncpy) ATTR_NONNULL(); -int BLI_utf8_invalid_byte(const char *str, int length) ATTR_NONNULL(); -int BLI_utf8_invalid_strip(char *str, int length) ATTR_NONNULL(); +ptrdiff_t BLI_utf8_invalid_byte(const char *str, size_t length) ATTR_NONNULL(); +int BLI_utf8_invalid_strip(char *str, size_t length) ATTR_NONNULL(); int BLI_str_utf8_size(const char *p) ATTR_NONNULL(); /* warning, can return -1 on bad chars */ int BLI_str_utf8_size_safe(const char *p) ATTR_NONNULL(); diff --git a/source/blender/blenlib/BLI_string_utils.h b/source/blender/blenlib/BLI_string_utils.h new file mode 100644 index 00000000000..5701bce51ea --- /dev/null +++ b/source/blender/blenlib/BLI_string_utils.h @@ -0,0 +1,82 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2017 by the Blender Foundation. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): none yet. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_STRING_UTILS_H__ +#define __BLI_STRING_UTILS_H__ + +/** \file BLI_string_utils.h + * \ingroup bli + */ + +#include <stdarg.h> + +#ifdef __cplusplus +extern "C" { +#endif + +#include "BLI_compiler_attrs.h" +#include "BLI_utildefines_variadic.h" + +struct ListBase; + +typedef bool (*UniquenameCheckCallback)(void *arg, const char *name); + +size_t BLI_split_name_num(char *left, int *nr, const char *name, const char delim); + +void BLI_string_split_suffix(const char *string, char *r_body, char *r_suf, const size_t str_len); +void BLI_string_split_prefix(const char *string, char *r_pre, char *r_body, const size_t str_len); + +/* Join strings, return newly allocated string. */ +char *BLI_string_join_arrayN( + const char *strings[], uint strings_len) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +char *BLI_string_join_array_by_sep_charN( + char sep, const char *strings[], uint strings_len) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +char *BLI_string_join_array_by_sep_char_with_tableN( + char sep, char *table[], const char *strings[], uint strings_len) ATTR_NONNULL(); +/* Take multiple arguments, pass as (array, length). */ +#define BLI_string_joinN(...) \ + BLI_string_join_arrayN( \ + ((const char *[]){__VA_ARGS__}), VA_NARGS_COUNT(__VA_ARGS__)) +#define BLI_string_join_by_sep_charN(sep, ...) \ + BLI_string_join_array_by_sep_charN( \ + sep, ((const char *[]){__VA_ARGS__}), VA_NARGS_COUNT(__VA_ARGS__)) +#define BLI_string_join_by_sep_char_with_tableN(sep, table, ...) \ + BLI_string_join_array_by_sep_char_with_tableN( \ + sep, table, ((const char *[]){__VA_ARGS__}), VA_NARGS_COUNT(__VA_ARGS__)) + +void BLI_string_flip_side_name(char *r_name, const char *from_name, const bool strip_number, const size_t name_len); + +bool BLI_uniquename_cb( + UniquenameCheckCallback unique_check, void *arg, const char *defname, char delim, char *name, size_t name_len); +bool BLI_uniquename( + struct ListBase *list, void *vlink, const char *defname, char delim, int name_offs, size_t len); + +#ifdef __cplusplus +} +#endif + +#endif /* __BLI_STRING_UTILS_H__ */ diff --git a/source/blender/blenlib/BLI_sys_types.h b/source/blender/blenlib/BLI_sys_types.h index 7929e1d6551..9477f61713c 100644 --- a/source/blender/blenlib/BLI_sys_types.h +++ b/source/blender/blenlib/BLI_sys_types.h @@ -65,8 +65,8 @@ typedef uint64_t u_int64_t; #include <inttypes.h> -/* MinGW and MSVC >= 2010 */ -#elif defined(FREE_WINDOWS) || defined(_MSC_VER) +/* MSVC >= 2010 */ +#elif defined(_MSC_VER) #include <stdint.h> #else @@ -80,6 +80,11 @@ typedef uint64_t u_int64_t; #include <stddef.h> /* size_t define */ #include <stdbool.h> +typedef unsigned int uint; +typedef unsigned short ushort; +typedef unsigned long ulong; +typedef unsigned char uchar; + #ifdef __cplusplus } #endif diff --git a/source/blender/blenlib/BLI_task.h b/source/blender/blenlib/BLI_task.h index 967e0be6d0a..721327d26a8 100644 --- a/source/blender/blenlib/BLI_task.h +++ b/source/blender/blenlib/BLI_task.h @@ -81,6 +81,7 @@ typedef void (*TaskFreeFunction)(TaskPool *__restrict pool, void *taskdata, int TaskPool *BLI_task_pool_create(TaskScheduler *scheduler, void *userdata); TaskPool *BLI_task_pool_create_background(TaskScheduler *scheduler, void *userdata); +TaskPool *BLI_task_pool_create_suspended(TaskScheduler *scheduler, void *userdata); void BLI_task_pool_free(TaskPool *pool); void BLI_task_pool_push_ex( @@ -95,14 +96,6 @@ void BLI_task_pool_push_from_thread(TaskPool *pool, TaskRunFunction run, void BLI_task_pool_work_and_wait(TaskPool *pool); /* cancel all tasks, keep worker threads running */ void BLI_task_pool_cancel(TaskPool *pool); -/* stop all worker threads */ -void BLI_task_pool_stop(TaskPool *pool); - -/* get number of threads allowed to be used by this pool */ -int BLI_pool_get_num_threads(TaskPool *pool); - -/* set number of threads allowed to be used by this pool */ -void BLI_pool_set_num_threads(TaskPool *pool, int num_threads); /* for worker threads, test if canceled */ bool BLI_task_pool_canceled(TaskPool *pool); @@ -113,8 +106,12 @@ void *BLI_task_pool_userdata(TaskPool *pool); /* optional mutex to use from run function */ ThreadMutex *BLI_task_pool_user_mutex(TaskPool *pool); -/* number of tasks done, for stats, don't use this to make decisions */ -size_t BLI_task_pool_tasks_done(TaskPool *pool); +/* Delayed push, use that to reduce thread overhead by accumulating + * all new tasks into local queue first and pushing it to scheduler + * from within a single mutex lock. + */ +void BLI_task_pool_delayed_push_begin(TaskPool *pool, int thread_id); +void BLI_task_pool_delayed_push_end(TaskPool *pool, int thread_id); /* Parallel for routines */ typedef void (*TaskParallelRangeFunc)(void *userdata, const int iter); diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h index 746eb922c65..66c7f247f61 100644 --- a/source/blender/blenlib/BLI_utildefines.h +++ b/source/blender/blenlib/BLI_utildefines.h @@ -39,35 +39,12 @@ extern "C" { /* avoid many includes for now */ #include "BLI_sys_types.h" #include "BLI_compiler_compat.h" +#include "BLI_utildefines_variadic.h" #ifndef NDEBUG /* for BLI_assert */ #include <stdio.h> #endif - -/* varargs macros (keep first so others can use) */ -/* --- internal helpers --- */ -#define _VA_NARGS_GLUE(x, y) x y -#define _VA_NARGS_RETURN_COUNT(\ - _1_, _2_, _3_, _4_, _5_, _6_, _7_, _8_, _9_, _10_, _11_, _12_, _13_, _14_, _15_, _16_, \ - _17_, _18_, _19_, _20_, _21_, _22_, _23_, _24_, _25_, _26_, _27_, _28_, _29_, _30_, _31_, _32_, \ - _33_, _34_, _35_, _36_, _37_, _38_, _39_, _40_, _41_, _42_, _43_, _44_, _45_, _46_, _47_, _48_, \ - _49_, _50_, _51_, _52_, _53_, _54_, _55_, _56_, _57_, _58_, _59_, _60_, _61_, _62_, _63_, _64_, \ - count, ...) count -#define _VA_NARGS_EXPAND(args) _VA_NARGS_RETURN_COUNT args -/* 64 args max */ -#define _VA_NARGS_COUNT(...) _VA_NARGS_EXPAND((__VA_ARGS__, \ - 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, \ - 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, \ - 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, \ - 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)) -#define _VA_NARGS_OVERLOAD_MACRO2(name, count) name##count -#define _VA_NARGS_OVERLOAD_MACRO1(name, count) _VA_NARGS_OVERLOAD_MACRO2(name, count) -#define _VA_NARGS_OVERLOAD_MACRO(name, count) _VA_NARGS_OVERLOAD_MACRO1(name, count) -/* --- expose for re-use --- */ -#define VA_NARGS_CALL_OVERLOAD(name, ...) \ - _VA_NARGS_GLUE(_VA_NARGS_OVERLOAD_MACRO(name, _VA_NARGS_COUNT(__VA_ARGS__)), (__VA_ARGS__)) - /* useful for finding bad use of min/max */ #if 0 /* gcc only */ diff --git a/source/blender/blenlib/BLI_utildefines_iter.h b/source/blender/blenlib/BLI_utildefines_iter.h new file mode 100644 index 00000000000..094c1a4b3dc --- /dev/null +++ b/source/blender/blenlib/BLI_utildefines_iter.h @@ -0,0 +1,52 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_UTILDEFINES_ITER_H__ +#define __BLI_UTILDEFINES_ITER_H__ + +/** \file BLI_utildefines_iter.h + * \ingroup bli + * + * General looping helpers, use `BLI_FOREACH` prefix. + */ + +/** + * Even value distribution. + * + * \a src must be larger than \a dst, + * \a dst defines the number of iterations, their values are evenly spaced. + * + * The following pairs represent (src, dst) arguments and the values they loop over. + * <pre> + * (19, 4) -> [2, 7, 11. 16] + * (100, 5) -> [9, 29, 49, 69, 89] + * (100, 3) -> [16, 49, 83] + * (100, 100) -> [0..99] + * </pre> + * \note this is mainly useful for numbers that might not divide evenly into eachother. + */ +#define BLI_FOREACH_SPARSE_RANGE(src, dst, i) \ +for (int _src = (src), _src2 = _src * 2, _dst2 = (dst) * 2, _error = _dst2 - _src, i = 0, _delta; \ + ((void)(_delta = divide_floor_i(_error, _dst2)), \ + (void)(i -= _delta), \ + (i < _src)); \ + _error -= (_delta * _dst2) + _src2) + +#endif /* __BLI_UTILDEFINES_ITER_H__ */ diff --git a/source/blender/blenlib/BLI_stackdefines.h b/source/blender/blenlib/BLI_utildefines_stack.h index 42b11eb9a2b..15b0029e727 100644 --- a/source/blender/blenlib/BLI_stackdefines.h +++ b/source/blender/blenlib/BLI_utildefines_stack.h @@ -18,10 +18,10 @@ * ***** END GPL LICENSE BLOCK ***** */ -#ifndef __BLI_STACKDEFINES_H__ -#define __BLI_STACKDEFINES_H__ +#ifndef __BLI_UTILDEFINES_STACK_H__ +#define __BLI_UTILDEFINES_STACK_H__ -/** \file BLI_stackdefines.h +/** \file BLI_utildefines_stack.h * \ingroup bli * * Macro's for a simple array based stack @@ -86,4 +86,4 @@ } ((void)0) #endif -#endif /* __BLI_STACKDEFINES_H__ */ +#endif /* __BLI_UTILDEFINES_STACK_H__ */ diff --git a/source/blender/blenlib/BLI_utildefines_variadic.h b/source/blender/blenlib/BLI_utildefines_variadic.h new file mode 100644 index 00000000000..7c15754fd83 --- /dev/null +++ b/source/blender/blenlib/BLI_utildefines_variadic.h @@ -0,0 +1,50 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_UTILDEFINES_VARIADIC_H__ +#define __BLI_UTILDEFINES_VARIADIC_H__ + +/** \file BLI_utildefines_variadic.h + * \ingroup bli + */ + +/* --- internal helpers --- */ +#define _VA_NARGS_GLUE(x, y) x y +#define _VA_NARGS_RETURN_COUNT(\ + _1_, _2_, _3_, _4_, _5_, _6_, _7_, _8_, _9_, _10_, _11_, _12_, _13_, _14_, _15_, _16_, \ + _17_, _18_, _19_, _20_, _21_, _22_, _23_, _24_, _25_, _26_, _27_, _28_, _29_, _30_, _31_, _32_, \ + _33_, _34_, _35_, _36_, _37_, _38_, _39_, _40_, _41_, _42_, _43_, _44_, _45_, _46_, _47_, _48_, \ + _49_, _50_, _51_, _52_, _53_, _54_, _55_, _56_, _57_, _58_, _59_, _60_, _61_, _62_, _63_, _64_, \ + count, ...) count +#define _VA_NARGS_EXPAND(args) _VA_NARGS_RETURN_COUNT args +#define _VA_NARGS_OVERLOAD_MACRO2(name, count) name##count +#define _VA_NARGS_OVERLOAD_MACRO1(name, count) _VA_NARGS_OVERLOAD_MACRO2(name, count) +#define _VA_NARGS_OVERLOAD_MACRO(name, count) _VA_NARGS_OVERLOAD_MACRO1(name, count) +/* --- expose for re-use --- */ +/* 64 args max */ +#define VA_NARGS_COUNT(...) _VA_NARGS_EXPAND((__VA_ARGS__, \ + 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, \ + 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, \ + 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, \ + 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)) +#define VA_NARGS_CALL_OVERLOAD(name, ...) \ + _VA_NARGS_GLUE(_VA_NARGS_OVERLOAD_MACRO(name, VA_NARGS_COUNT(__VA_ARGS__)), (__VA_ARGS__)) + +#endif /* __BLI_UTILDEFINES_VARIADIC_H__ */ diff --git a/source/blender/blenlib/BLI_vfontdata.h b/source/blender/blenlib/BLI_vfontdata.h index 8a7079b6c5f..0cd50319a33 100644 --- a/source/blender/blenlib/BLI_vfontdata.h +++ b/source/blender/blenlib/BLI_vfontdata.h @@ -52,8 +52,10 @@ typedef struct VChar { } VChar; VFontData *BLI_vfontdata_from_freetypefont(struct PackedFile *pf); +VFontData *BLI_vfontdata_copy(const VFontData *vfont_src, const int flag); VChar *BLI_vfontchar_from_freetypefont(struct VFont *vfont, unsigned long character); +VChar *BLI_vfontchar_copy(const VChar *vchar_src, const int flag); #endif diff --git a/source/blender/blenlib/BLI_winstuff.h b/source/blender/blenlib/BLI_winstuff.h index b421b7dbb90..6fbbed01400 100644 --- a/source/blender/blenlib/BLI_winstuff.h +++ b/source/blender/blenlib/BLI_winstuff.h @@ -37,15 +37,6 @@ # error "This include is for Windows only!" #endif -#ifdef FREE_WINDOWS -# ifdef WINVER -# undef WINVER -# endif - -/* Some stuff requires WINVER 0x500, but mingw's default is 0x400 */ -# define WINVER 0x0501 -#endif - #define WIN32_LEAN_AND_MEAN #ifndef WIN32_SKIP_HKEY_PROTECTION @@ -94,7 +85,7 @@ extern "C" { # define snprintf _snprintf #endif -#if defined(_MSC_VER) || (defined(FREE_WINDOWS) && !defined(FREE_WINDOWS64)) +#if defined(_MSC_VER) # define R_OK 4 # define W_OK 2 // not accepted by access() on windows @@ -102,28 +93,22 @@ extern "C" { # define F_OK 0 #endif -#ifndef FREE_WINDOWS typedef unsigned int mode_t; -#endif /* use functions that take a 64 bit offset for files larger than 4GB */ -#ifndef FREE_WINDOWS -# include <stdio.h> -# define fseek(stream, offset, origin) _fseeki64(stream, offset, origin) -# define ftell(stream) _ftelli64(stream) -# define lseek(fd, offset, origin) _lseeki64(fd, offset, origin) -# define tell(fd) _telli64(fd) -#endif +#include <stdio.h> +#define fseek(stream, offset, origin) _fseeki64(stream, offset, origin) +#define ftell(stream) _ftelli64(stream) +#define lseek(fd, offset, origin) _lseeki64(fd, offset, origin) +#define tell(fd) _telli64(fd) + -/* mingw using _SSIZE_T_ to declare ssize_t type */ #ifndef _SSIZE_T_ # define _SSIZE_T_ /* python uses HAVE_SSIZE_T */ # ifndef HAVE_SSIZE_T # define HAVE_SSIZE_T 1 -# ifndef FREE_WINDOWS64 typedef long ssize_t; -# endif # endif #endif diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 6e717a3ae7e..61a1241cd8f 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -109,6 +109,7 @@ set(SRC intern/string.c intern/string_cursor_utf8.c intern/string_utf8.c + intern/string_utils.c intern/system.c intern/task.c intern/threads.c @@ -151,6 +152,7 @@ set(SRC BLI_ghash.h BLI_graph.h BLI_gsqueue.h + BLI_hash.h BLI_hash_md5.h BLI_hash_mm2a.h BLI_heap.h @@ -190,17 +192,20 @@ set(SRC BLI_sort.h BLI_sort_utils.h BLI_stack.h - BLI_stackdefines.h BLI_strict_flags.h BLI_string.h BLI_string_cursor_utf8.h BLI_string_utf8.h + BLI_string_utils.h BLI_sys_types.h BLI_system.h BLI_task.h BLI_threads.h BLI_timecode.h BLI_utildefines.h + BLI_utildefines_iter.h + BLI_utildefines_stack.h + BLI_utildefines_variadic.h BLI_uvproject.h BLI_vfontdata.h BLI_voronoi.h diff --git a/source/blender/blenlib/PIL_time_utildefines.h b/source/blender/blenlib/PIL_time_utildefines.h index 9157e04a7bf..412cfb3a090 100644 --- a/source/blender/blenlib/PIL_time_utildefines.h +++ b/source/blender/blenlib/PIL_time_utildefines.h @@ -80,9 +80,10 @@ } \ const float _delta_##var = TIMEIT_VALUE(var); \ _sum_##var += _delta_##var; \ + _num_##var++; \ printf("time end (" #var "): %.6f" " " AT "\n", _delta_##var); \ - printf("time averaged (" #var "): %.6f" " " AT "\n", \ - (_sum_##var / ++_num_##var)); \ + printf("time averaged (" #var "): %.6f (total: %.6f, in %d runs)\n", \ + (_sum_##var / _num_##var), _sum_##var, (int)_num_##var); \ fflush(stdout); \ } (void)0 diff --git a/source/blender/blenlib/intern/BLI_dial.c b/source/blender/blenlib/intern/BLI_dial.c index cfbb52847fd..89f18fa10b4 100644 --- a/source/blender/blenlib/intern/BLI_dial.c +++ b/source/blender/blenlib/intern/BLI_dial.c @@ -46,7 +46,7 @@ struct Dial { }; -Dial *BLI_dial_initialize(float start_position[2], float threshold) +Dial *BLI_dial_initialize(const float start_position[2], float threshold) { Dial *dial = MEM_callocN(sizeof(Dial), "dial"); @@ -56,7 +56,7 @@ Dial *BLI_dial_initialize(float start_position[2], float threshold) return dial; } -float BLI_dial_angle(Dial *dial, float current_position[2]) +float BLI_dial_angle(Dial *dial, const float current_position[2]) { float current_direction[2]; diff --git a/source/blender/blenlib/intern/BLI_dynstr.c b/source/blender/blenlib/intern/BLI_dynstr.c index ecd4a6e6b09..bce6614beb5 100644 --- a/source/blender/blenlib/intern/BLI_dynstr.c +++ b/source/blender/blenlib/intern/BLI_dynstr.c @@ -35,6 +35,7 @@ #include "MEM_guardedalloc.h" #include "BLI_utildefines.h" +#include "BLI_memarena.h" #include "BLI_string.h" #include "BLI_dynstr.h" @@ -64,6 +65,7 @@ struct DynStrElem { struct DynStr { DynStrElem *elems, *last; int curlen; + MemArena *memarena; }; /***/ @@ -78,11 +80,32 @@ DynStr *BLI_dynstr_new(void) DynStr *ds = MEM_mallocN(sizeof(*ds), "DynStr"); ds->elems = ds->last = NULL; ds->curlen = 0; + ds->memarena = NULL; return ds; } /** + * Create a new DynStr. + * + * \return Pointer to a new DynStr. + */ +DynStr *BLI_dynstr_new_memarena(void) +{ + DynStr *ds = MEM_mallocN(sizeof(*ds), "DynStr"); + ds->elems = ds->last = NULL; + ds->curlen = 0; + ds->memarena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); + + return ds; +} + +BLI_INLINE void *dynstr_alloc(DynStr *__restrict ds, size_t size) +{ + return ds->memarena ? BLI_memarena_alloc(ds->memarena, size) : malloc(size); +} + +/** * Append a c-string to a DynStr. * * \param ds The DynStr to append to. @@ -90,10 +113,10 @@ DynStr *BLI_dynstr_new(void) */ void BLI_dynstr_append(DynStr *__restrict ds, const char *cstr) { - DynStrElem *dse = malloc(sizeof(*dse)); + DynStrElem *dse = dynstr_alloc(ds, sizeof(*dse)); int cstrlen = strlen(cstr); - dse->str = malloc(cstrlen + 1); + dse->str = dynstr_alloc(ds, cstrlen + 1); memcpy(dse->str, cstr, cstrlen + 1); dse->next = NULL; @@ -114,10 +137,10 @@ void BLI_dynstr_append(DynStr *__restrict ds, const char *cstr) */ void BLI_dynstr_nappend(DynStr *__restrict ds, const char *cstr, int len) { - DynStrElem *dse = malloc(sizeof(*dse)); + DynStrElem *dse = dynstr_alloc(ds, sizeof(*dse)); int cstrlen = BLI_strnlen(cstr, len); - dse->str = malloc(cstrlen + 1); + dse->str = dynstr_alloc(ds, cstrlen + 1); memcpy(dse->str, cstr, cstrlen); dse->str[cstrlen] = '\0'; dse->next = NULL; @@ -296,22 +319,41 @@ char *BLI_dynstr_get_cstring(DynStr *ds) } /** + * Clear the DynStr + * + * \param ds The DynStr to clear. + */ +void BLI_dynstr_clear(DynStr *ds) +{ + if (ds->memarena) { + BLI_memarena_clear(ds->memarena); + } + else { + for (DynStrElem *dse_next, *dse = ds->elems; dse; dse = dse_next) { + dse_next = dse->next; + + free(dse->str); + free(dse); + } + } + + ds->elems = ds->last = NULL; + ds->curlen = 0; +} + +/** * Free the DynStr * * \param ds The DynStr to free. */ void BLI_dynstr_free(DynStr *ds) { - DynStrElem *dse; - - for (dse = ds->elems; dse; ) { - DynStrElem *n = dse->next; - - free(dse->str); - free(dse); - - dse = n; + if (ds->memarena) { + BLI_memarena_free(ds->memarena); } - + else { + BLI_dynstr_clear(ds); + } + MEM_freeN(ds); } diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 944ee18e6b2..1b2a27e33d8 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -116,6 +116,12 @@ struct GHash { }; +/* -------------------------------------------------------------------- */ +/* GHash API */ + +/** \name Internal Utility API + * \{ */ + BLI_INLINE void ghash_entry_copy( GHash *gh_dst, Entry *dst, GHash *gh_src, Entry *src, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp) @@ -132,12 +138,6 @@ BLI_INLINE void ghash_entry_copy( } } -/* -------------------------------------------------------------------- */ -/* GHash API */ - -/** \name Internal Utility API - * \{ */ - /** * Get the full hash for a key. */ @@ -763,6 +763,28 @@ bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreef } /** + * Replaces the key of an item in the \a gh. + * + * Use when a key is re-allocated or it's memory location is changed. + * + * \returns The previous key or NULL if not found, the caller may free if it's needed. + */ +void *BLI_ghash_replace_key(GHash *gh, void *key) +{ + const unsigned int hash = ghash_keyhash(gh, key); + const unsigned int bucket_index = ghash_bucket_index(gh, hash); + GHashEntry *e = (GHashEntry *)ghash_lookup_entry_ex(gh, key, bucket_index); + if (e != NULL) { + void *key_prev = e->e.key; + e->e.key = key; + return key_prev; + } + else { + return NULL; + } +} + +/** * Lookup the value of \a key in \a gh. * * \param key The key to lookup. @@ -1225,6 +1247,11 @@ bool BLI_ghashutil_intcmp(const void *a, const void *b) return (a != b); } +size_t BLI_ghashutil_combine_hash(size_t hash_a, size_t hash_b) +{ + return hash_a ^ (hash_b + 0x9e3779b9 + (hash_a << 6) + (hash_a >> 2)); +} + /** * This function implements the widely used "djb" hash apparently posted * by Daniel Bernstein to comp.lang.c some time ago. The 32 bit @@ -1429,6 +1456,18 @@ bool BLI_gset_reinsert(GSet *gs, void *key, GSetKeyFreeFP keyfreefp) return ghash_insert_safe_keyonly((GHash *)gs, key, true, keyfreefp); } +/** + * Replaces the key to the set if it's found. + * Matching #BLI_ghash_replace_key + * + * \returns The old key or NULL if not found. + */ +void *BLI_gset_replace_key(GSet *gs, void *key) +{ + return BLI_ghash_replace_key((GHash *)gs, key); +} + + bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp) { return BLI_ghash_remove((GHash *)gs, key, keyfreefp, NULL); diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index b14007a88cb..e5ca53a0193 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -55,12 +55,20 @@ #include "BLI_stack.h" #include "BLI_kdopbvh.h" #include "BLI_math.h" -#include "BLI_strict_flags.h" #include "BLI_task.h" +#include "BLI_strict_flags.h" + /* used for iterative_raycast */ // #define USE_SKIP_LINKS +/* Use to print balanced output. */ +// #define USE_PRINT_TREE + +/* Check tree is valid. */ +// #define USE_VERIFY_TREE + + #define MAX_TREETYPE 32 /* Setting zero so we can catch bugs in BLI_task/KDOPBVH. @@ -129,7 +137,7 @@ typedef struct BVHOverlapData_Thread { } BVHOverlapData_Thread; typedef struct BVHNearestData { - BVHTree *tree; + const BVHTree *tree; const float *co; BVHTree_NearestPointCallback callback; void *userdata; @@ -139,7 +147,7 @@ typedef struct BVHNearestData { } BVHNearestData; typedef struct BVHRayCastData { - BVHTree *tree; + const BVHTree *tree; BVHTree_RayCastCallback callback; void *userdata; @@ -159,29 +167,6 @@ typedef struct BVHRayCastData { BVHTreeRayHit hit; } BVHRayCastData; -typedef struct BVHNearestRayData { - BVHTree *tree; - BVHTree_NearestToRayCallback callback; - void *userdata; - - struct { - bool sign[3]; - float origin[3]; - float direction[3]; - - float direction_scaled_square[3]; - float inv_dir[3]; - - float cdot_axis[3]; - } ray; - - bool pick_smallest[3]; - - BVHTreeNearest nearest; - - float scale[3]; -} BVHNearestRayData; - /** \} */ @@ -194,9 +179,9 @@ typedef struct BVHNearestRayData { */ const float bvhtree_kdop_axes[13][3] = { - {1.0, 0, 0}, {0, 1.0, 0}, {0, 0, 1.0}, {1.0, 1.0, 1.0}, {1.0, -1.0, 1.0}, {1.0, 1.0, -1.0}, - {1.0, -1.0, -1.0}, {1.0, 1.0, 0}, {1.0, 0, 1.0}, {0, 1.0, 1.0}, {1.0, -1.0, 0}, {1.0, 0, -1.0}, - {0, 1.0, -1.0} + {1.0, 0, 0}, {0, 1.0, 0}, {0, 0, 1.0}, + {1.0, 1.0, 1.0}, {1.0, -1.0, 1.0}, {1.0, 1.0, -1.0}, {1.0, -1.0, -1.0}, + {1.0, 1.0, 0}, {1.0, 0, 1.0}, {0, 1.0, 1.0}, {1.0, -1.0, 0}, {1.0, 0, -1.0}, {0, 1.0, -1.0} }; @@ -344,11 +329,16 @@ static int bvh_partition(BVHNode **a, int lo, int hi, BVHNode *x, int axis) { int i = lo, j = hi; while (1) { - while ((a[i])->bv[axis] < x->bv[axis]) i++; + while (a[i]->bv[axis] < x->bv[axis]) { + i++; + } j--; - while (x->bv[axis] < (a[j])->bv[axis]) j--; - if (!(i < j)) + while (x->bv[axis] < a[j]->bv[axis]) { + j--; + } + if (!(i < j)) { return i; + } SWAP(BVHNode *, a[i], a[j]); i++; } @@ -450,19 +440,18 @@ static void sort_along_axis(BVHTree *tree, int start, int end, int axis) * \note after a call to this function you can expect one of: * - every node to left of a[n] are smaller or equal to it * - every node to the right of a[n] are greater or equal to it */ -static int partition_nth_element(BVHNode **a, int _begin, int _end, int n, int axis) +static void partition_nth_element(BVHNode **a, int begin, int end, const int n, const int axis) { - int begin = _begin, end = _end, cut; while (end - begin > 3) { - cut = bvh_partition(a, begin, end, bvh_medianof3(a, begin, (begin + end) / 2, end - 1, axis), axis); - if (cut <= n) + const int cut = bvh_partition(a, begin, end, bvh_medianof3(a, begin, (begin + end) / 2, end - 1, axis), axis); + if (cut <= n) { begin = cut; - else + } + else { end = cut; + } } bvh_insertionsort(a, begin, end, axis); - - return n; } #ifdef USE_SKIP_LINKS @@ -487,7 +476,7 @@ static void build_skip_links(BVHTree *tree, BVHNode *node, BVHNode *left, BVHNod /* * BVHTree bounding volumes functions */ -static void create_kdop_hull(BVHTree *tree, BVHNode *node, const float *co, int numpoints, int moving) +static void create_kdop_hull(const BVHTree *tree, BVHNode *node, const float *co, int numpoints, int moving) { float newminmax; float *bv = node->bv; @@ -514,7 +503,7 @@ static void create_kdop_hull(BVHTree *tree, BVHNode *node, const float *co, int /** * \note depends on the fact that the BVH's for each face is already build */ -static void refit_kdop_hull(BVHTree *tree, BVHNode *node, int start, int end) +static void refit_kdop_hull(const BVHTree *tree, BVHNode *node, int start, int end) { float newmin, newmax; float *bv = node->bv; @@ -589,10 +578,12 @@ static void node_join(BVHTree *tree, BVHNode *node) } } -/* +#ifdef USE_PRINT_TREE + +/** * Debug and information functions */ -#if 0 + static void bvhtree_print_tree(BVHTree *tree, BVHNode *node, int depth) { int i; @@ -615,26 +606,29 @@ static void bvhtree_print_tree(BVHTree *tree, BVHNode *node, int depth) static void bvhtree_info(BVHTree *tree) { - printf("BVHTree info\n"); - printf("tree_type = %d, axis = %d, epsilon = %f\n", tree->tree_type, tree->axis, tree->epsilon); - printf("nodes = %d, branches = %d, leafs = %d\n", tree->totbranch + tree->totleaf, tree->totbranch, tree->totleaf); - printf("Memory per node = %ldbytes\n", sizeof(BVHNode) + sizeof(BVHNode *) * tree->tree_type + sizeof(float) * tree->axis); - printf("BV memory = %dbytes\n", (int)MEM_allocN_len(tree->nodebv)); - - printf("Total memory = %ldbytes\n", sizeof(BVHTree) + - MEM_allocN_len(tree->nodes) + - MEM_allocN_len(tree->nodearray) + - MEM_allocN_len(tree->nodechild) + - MEM_allocN_len(tree->nodebv)); - -// bvhtree_print_tree(tree, tree->nodes[tree->totleaf], 0); -} -#endif + printf("BVHTree Info: tree_type = %d, axis = %d, epsilon = %f\n", + tree->tree_type, tree->axis, tree->epsilon); + printf("nodes = %d, branches = %d, leafs = %d\n", + tree->totbranch + tree->totleaf, tree->totbranch, tree->totleaf); + printf("Memory per node = %ubytes\n", + (uint)(sizeof(BVHNode) + sizeof(BVHNode *) * tree->tree_type + sizeof(float) * tree->axis)); + printf("BV memory = %ubytes\n", + (uint)MEM_allocN_len(tree->nodebv)); -#if 0 + printf("Total memory = %ubytes\n", + (uint)(sizeof(BVHTree) + + MEM_allocN_len(tree->nodes) + + MEM_allocN_len(tree->nodearray) + + MEM_allocN_len(tree->nodechild) + + MEM_allocN_len(tree->nodebv))); + bvhtree_print_tree(tree, tree->nodes[tree->totleaf], 0); +} +#endif /* USE_PRINT_TREE */ + +#ifdef USE_VERIFY_TREE -static void verify_tree(BVHTree *tree) +static void bvhtree_verify(BVHTree *tree) { int i, j, check = 0; @@ -672,12 +666,14 @@ static void verify_tree(BVHTree *tree) } } - printf("branches: %d, leafs: %d, total: %d\n", tree->totbranch, tree->totleaf, tree->totbranch + tree->totleaf); + printf("branches: %d, leafs: %d, total: %d\n", + tree->totbranch, tree->totleaf, tree->totbranch + tree->totleaf); } -#endif +#endif /* USE_VERIFY_TREE */ /* Helper data and structures to build a min-leaf generalized implicit tree - * This code can be easily reduced (basicly this is only method to calculate pow(k, n) in O(1).. and stuff like that) */ + * This code can be easily reduced + * (basicly this is only method to calculate pow(k, n) in O(1).. and stuff like that) */ typedef struct BVHBuildHelper { int tree_type; /* */ int totleafs; /* */ @@ -689,7 +685,7 @@ typedef struct BVHBuildHelper { } BVHBuildHelper; -static void build_implicit_tree_helper(BVHTree *tree, BVHBuildHelper *data) +static void build_implicit_tree_helper(const BVHTree *tree, BVHBuildHelper *data) { int depth = 0; int remain; @@ -719,7 +715,7 @@ static void build_implicit_tree_helper(BVHTree *tree, BVHBuildHelper *data) } // return the min index of all the leafs archivable with the given branch -static int implicit_leafs_index(BVHBuildHelper *data, int depth, int child_index) +static int implicit_leafs_index(const BVHBuildHelper *data, const int depth, const int child_index) { int min_leaf_index = child_index * data->leafs_per_child[depth - 1]; if (min_leaf_index <= data->remain_leafs) @@ -734,8 +730,8 @@ static int implicit_leafs_index(BVHBuildHelper *data, int depth, int child_index * Generalized implicit tree build * * An implicit tree is a tree where its structure is implied, thus there is no need to store child pointers or indexs. - * Its possible to find the position of the child or the parent with simple maths (multiplication and adittion). This type - * of tree is for example used on heaps.. where node N has its childs at indexs N*2 and N*2+1. + * Its possible to find the position of the child or the parent with simple maths (multiplication and adittion). + * This type of tree is for example used on heaps.. where node N has its childs at indexs N*2 and N*2+1. * * Although in this case the tree type is general.. and not know until runtime. * tree_type stands for the maximum number of childs that a tree node can have. @@ -776,7 +772,7 @@ static int implicit_needed_branches(int tree_type, int leafs) * * TODO: This can be optimized a bit by doing a specialized nth_element instead of K nth_elements */ -static void split_leafs(BVHNode **leafs_array, int *nth, int partitions, int split_axis) +static void split_leafs(BVHNode **leafs_array, const int nth[], const int partitions, const int split_axis) { int i; for (i = 0; i < partitions - 1; i++) { @@ -788,14 +784,14 @@ static void split_leafs(BVHNode **leafs_array, int *nth, int partitions, int spl } typedef struct BVHDivNodesData { - BVHTree *tree; + const BVHTree *tree; BVHNode *branches_array; BVHNode **leafs_array; int tree_type; int tree_offset; - BVHBuildHelper *data; + const BVHBuildHelper *data; int depth; int i; @@ -808,7 +804,7 @@ static void non_recursive_bvh_div_nodes_task_cb(void *userdata, const int j) int k; const int parent_level_index = j - data->i; - BVHNode *parent = data->branches_array + j; + BVHNode *parent = &data->branches_array[j]; int nth_positions[MAX_TREETYPE + 1]; char split_axis; @@ -847,7 +843,7 @@ static void non_recursive_bvh_div_nodes_task_cb(void *userdata, const int j) const int child_leafs_end = implicit_leafs_index(data->data, data->depth + 1, child_level_index + 1); if (child_leafs_end - child_leafs_begin > 1) { - parent->children[k] = data->branches_array + child_index; + parent->children[k] = &data->branches_array[child_index]; parent->children[k]->parent = parent; } else if (child_leafs_end - child_leafs_begin == 1) { @@ -878,7 +874,8 @@ static void non_recursive_bvh_div_nodes_task_cb(void *userdata, const int j) * To archive this is necessary to find how much leafs are accessible from a certain branch, BVHBuildHelper * implicit_needed_branches and implicit_leafs_index are auxiliary functions to solve that "optimal-split". */ -static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array, BVHNode **leafs_array, int num_leafs) +static void non_recursive_bvh_div_nodes( + const BVHTree *tree, BVHNode *branches_array, BVHNode **leafs_array, int num_leafs) { int i; @@ -890,13 +887,13 @@ static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array, int depth; /* set parent from root node to NULL */ - BVHNode *tmp = branches_array + 0; + BVHNode *tmp = &branches_array[0]; tmp->parent = NULL; /* Most of bvhtree code relies on 1-leaf trees having at least one branch * We handle that special case here */ if (num_leafs == 1) { - BVHNode *root = branches_array + 0; + BVHNode *root = &branches_array[0]; refit_kdop_hull(tree, root, 0, num_leafs); root->main_axis = get_largest_axis(root->bv) / 2; root->totnode = 1; @@ -918,16 +915,24 @@ static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array, /* Loop tree levels (log N) loops */ for (i = 1, depth = 1; i <= num_branches; i = i * tree_type + tree_offset, depth++) { const int first_of_next_level = i * tree_type + tree_offset; - const int end_j = min_ii(first_of_next_level, num_branches + 1); /* index of last branch on this level */ + const int i_stop = min_ii(first_of_next_level, num_branches + 1); /* index of last branch on this level */ /* Loop all branches on this level */ cb_data.first_of_next_level = first_of_next_level; cb_data.i = i; cb_data.depth = depth; - BLI_task_parallel_range( - i, end_j, &cb_data, non_recursive_bvh_div_nodes_task_cb, - num_leafs > KDOPBVH_THREAD_LEAF_THRESHOLD); + if (true) { + BLI_task_parallel_range( + i, i_stop, &cb_data, non_recursive_bvh_div_nodes_task_cb, + num_leafs > KDOPBVH_THREAD_LEAF_THRESHOLD); + } + else { + /* Less hassle for debugging. */ + for (int i_task = i; i_task < i_stop; i_task++) { + non_recursive_bvh_div_nodes_task_cb(&cb_data, i_task); + } + } } } @@ -1044,7 +1049,8 @@ void BLI_bvhtree_balance(BVHTree *tree) BVHNode *branches_array = tree->nodearray + tree->totleaf; BVHNode **leafs_array = tree->nodes; - /* This function should only be called once (some big bug goes here if its being called more than once per tree) */ + /* This function should only be called once + * (some big bug goes here if its being called more than once per tree) */ BLI_assert(tree->totbranch == 0); /* Build the implicit tree */ @@ -1060,7 +1066,13 @@ void BLI_bvhtree_balance(BVHTree *tree) build_skip_links(tree, tree->nodes[tree->totleaf], NULL, NULL); #endif - /* bvhtree_info(tree); */ +#ifdef USE_VERIFY_TREE + bvhtree_verify(tree); +#endif + +#ifdef USE_PRINT_TREE + bvhtree_info(tree); +#endif } void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints) @@ -1493,7 +1505,8 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) else { /* adjust heap size */ if ((heap_size >= max_heap_size) && - ADJUST_MEMORY(default_heap, (void **)&heap, heap_size + 1, &max_heap_size, sizeof(heap[0])) == false) + ADJUST_MEMORY(default_heap, (void **)&heap, + heap_size + 1, &max_heap_size, sizeof(heap[0])) == false) { printf("WARNING: bvh_find_nearest got out of memory\n"); @@ -1900,453 +1913,6 @@ void BLI_bvhtree_ray_cast_all( /* -------------------------------------------------------------------- */ -/** \name BLI_bvhtree_find_nearest_to_ray functions - * - * \{ */ - -static void dist_squared_ray_to_aabb_scaled_v3_precalc( - BVHNearestRayData *data, - const float ray_origin[3], const float ray_direction[3], - const bool ray_is_normalized, const float scale[3]) -{ - if (scale) { - copy_v3_v3(data->scale, scale); - } - else { - copy_v3_fl(data->scale, 1.0f); - } - /* un-normalize ray */ - if (ray_is_normalized && scale && - (data->scale[0] != 1.0f || data->scale[1] != 1.0f || data->scale[2] != 1.0f)) - { - data->ray.direction[0] = ray_direction[0] * data->scale[0]; - data->ray.direction[1] = ray_direction[1] * data->scale[1]; - data->ray.direction[2] = ray_direction[2] * data->scale[2]; - - mul_v3_v3fl(data->ray.direction, ray_direction, 1 / len_v3(data->ray.direction)); - } - else { - copy_v3_v3(data->ray.direction, ray_direction); - } - - float dir_sq[3]; - - for (int i = 0; i < 3; i++) { - data->ray.origin[i] = ray_origin[i]; - data->ray.inv_dir[i] = (data->ray.direction[i] != 0.0f) ? - (1.0f / data->ray.direction[i]) : FLT_MAX; - /* It has to be in function of `ray.inv_dir`, - * since the division of 1 by 0.0f, can be -inf or +inf */ - data->ray.sign[i] = (data->ray.inv_dir[i] < 0.0f); - - data->ray.direction_scaled_square[i] = data->ray.direction[i] * data->scale[i]; - - dir_sq[i] = SQUARE(data->ray.direction_scaled_square[i]); - - data->ray.direction_scaled_square[i] *= data->scale[i]; - } - - /* `diag_sq` Length square of each face diagonal */ - float diag_sq[3] = { - dir_sq[1] + dir_sq[2], - dir_sq[0] + dir_sq[2], - dir_sq[0] + dir_sq[1], - }; - - data->ray.cdot_axis[0] = (diag_sq[0] != 0.0f) ? data->ray.direction[0] / diag_sq[0] : FLT_MAX; - data->ray.cdot_axis[1] = (diag_sq[1] != 0.0f) ? data->ray.direction[1] / diag_sq[1] : FLT_MAX; - data->ray.cdot_axis[2] = (diag_sq[2] != 0.0f) ? data->ray.direction[2] / diag_sq[2] : FLT_MAX; -} - -/** - * Returns the squared distance from a ray to a bound-box `AABB`. - * It is based on `fast_ray_nearest_hit` solution to obtain - * the coordinates of the nearest edge of Bound Box to the ray - */ -MINLINE float dist_squared_ray_to_aabb_scaled_v3__impl( - const BVHNearestRayData *data, - const float bv[6], float *r_depth_sq, bool r_axis_closest[3]) -{ - - /* `tmin` is a vector that has the smaller distances to each of the - * infinite planes of the `AABB` faces (hit in nearest face X plane, - * nearest face Y plane and nearest face Z plane) */ - float local_bvmin[3], local_bvmax[3]; - - if (data->ray.sign[0]) { - local_bvmin[0] = bv[1]; - local_bvmax[0] = bv[0]; - } - else { - local_bvmin[0] = bv[0]; - local_bvmax[0] = bv[1]; - } - - if (data->ray.sign[1]) { - local_bvmin[1] = bv[3]; - local_bvmax[1] = bv[2]; - } - else { - local_bvmin[1] = bv[2]; - local_bvmax[1] = bv[3]; - } - - if (data->ray.sign[2]) { - local_bvmin[2] = bv[5]; - local_bvmax[2] = bv[4]; - } - else { - local_bvmin[2] = bv[4]; - local_bvmax[2] = bv[5]; - } - - sub_v3_v3(local_bvmin, data->ray.origin); - sub_v3_v3(local_bvmax, data->ray.origin); - - const float tmin[3] = { - local_bvmin[0] * data->ray.inv_dir[0], - local_bvmin[1] * data->ray.inv_dir[1], - local_bvmin[2] * data->ray.inv_dir[2], - }; - - /* `tmax` is a vector that has the longer distances to each of the - * infinite planes of the `AABB` faces (hit in farthest face X plane, - * farthest face Y plane and farthest face Z plane) */ - const float tmax[3] = { - local_bvmax[0] * data->ray.inv_dir[0], - local_bvmax[1] * data->ray.inv_dir[1], - local_bvmax[2] * data->ray.inv_dir[2], - }; - /* `v1` and `v3` is be the coordinates of the nearest `AABB` edge to the ray*/ - float v1[3], v2[3]; - /* `rtmin` is the highest value of the smaller distances. == max_axis_v3(tmin) - * `rtmax` is the lowest value of longer distances. == min_axis_v3(tmax)*/ - float rtmin, rtmax, mul; - /* `main_axis` is the axis equivalent to edge close to the ray */ - int main_axis; - - r_axis_closest[0] = false; - r_axis_closest[1] = false; - r_axis_closest[2] = false; - - /* *** min_axis_v3(tmax) *** */ - if ((tmax[0] <= tmax[1]) && (tmax[0] <= tmax[2])) { - // printf("# Hit in X %s\n", data->sign[0] ? "min", "max"); - rtmax = tmax[0]; - v1[0] = v2[0] = local_bvmax[0]; - mul = local_bvmax[0] * data->ray.direction_scaled_square[0]; - main_axis = 3; - r_axis_closest[0] = data->ray.sign[0]; - } - else if ((tmax[1] <= tmax[0]) && (tmax[1] <= tmax[2])) { - // printf("# Hit in Y %s\n", data->sign[1] ? "min", "max"); - rtmax = tmax[1]; - v1[1] = v2[1] = local_bvmax[1]; - mul = local_bvmax[1] * data->ray.direction_scaled_square[1]; - main_axis = 2; - r_axis_closest[1] = data->ray.sign[1]; - } - else { - // printf("# Hit in Z %s\n", data->sign[2] ? "min", "max"); - rtmax = tmax[2]; - v1[2] = v2[2] = local_bvmax[2]; - mul = local_bvmax[2] * data->ray.direction_scaled_square[2]; - main_axis = 1; - r_axis_closest[2] = data->ray.sign[2]; - } - - /* *** max_axis_v3(tmin) *** */ - if ((tmin[0] >= tmin[1]) && (tmin[0] >= tmin[2])) { - // printf("# To X %s\n", data->sign[0] ? "max", "min"); - rtmin = tmin[0]; - v1[0] = v2[0] = local_bvmin[0]; - mul += local_bvmin[0] * data->ray.direction_scaled_square[0]; - main_axis -= 3; - r_axis_closest[0] = !data->ray.sign[0]; - } - else if ((tmin[1] >= tmin[0]) && (tmin[1] >= tmin[2])) { - // printf("# To Y %s\n", data->sign[1] ? "max", "min"); - rtmin = tmin[1]; - v1[1] = v2[1] = local_bvmin[1]; - mul += local_bvmin[1] * data->ray.direction_scaled_square[1]; - main_axis -= 1; - r_axis_closest[1] = !data->ray.sign[1]; - } - else { - // printf("# To Z %s\n", data->sign[2] ? "max", "min"); - rtmin = tmin[2]; - v1[2] = v2[2] = local_bvmin[2]; - mul += local_bvmin[2] * data->ray.direction_scaled_square[2]; - main_axis -= 2; - r_axis_closest[2] = !data->ray.sign[2]; - } - /* *** end min/max axis *** */ - - if (main_axis < 0) - main_axis += 3; - - /* if rtmin < rtmax, ray intersect `AABB` */ - if (rtmin <= rtmax) { -#ifdef IGNORE_BEHIND_RAY - /* `if rtmax < depth_min`, the whole `AABB` is behind us */ - if (rtmax < min_depth) { - return fallback; - } -#endif - const float proj = rtmin * data->ray.direction[main_axis]; - - if (data->ray.sign[main_axis]) - r_axis_closest[main_axis] = (proj - local_bvmax[main_axis]) < (local_bvmin[main_axis] - proj); - else - r_axis_closest[main_axis] = (proj - local_bvmin[main_axis]) < (local_bvmax[main_axis] - proj); - - //if (r_depth_sq) - // *r_depth_sq = SQUARE(rtmin); - - return 0.0f; - } -#ifdef IGNORE_BEHIND_RAY - /* `if rtmin < depth_min`, the whole `AABB` is behing us */ - else if (rtmin < min_depth) { - return fallback; - } -#endif - - if (data->ray.sign[main_axis]) { - v1[main_axis] = local_bvmax[main_axis]; - v2[main_axis] = local_bvmin[main_axis]; - } - else { - v1[main_axis] = local_bvmin[main_axis]; - v2[main_axis] = local_bvmax[main_axis]; - } - { - /* `proj` equals to nearest point on the ray closest to the edge `v1 v2` of the `AABB`. */ - const float proj = mul * data->ray.cdot_axis[main_axis]; - float depth_sq, r_point[3]; - if (v1[main_axis] > proj) { /* the nearest point to the ray is the point v1 */ - r_axis_closest[main_axis] = true; - /* `depth` is equivalent the distance of the the projection of v1 on the ray */ - depth_sq = mul + data->ray.direction_scaled_square[main_axis] * v1[main_axis]; - - copy_v3_v3(r_point, v1); - } - else if (v2[main_axis] < proj) { /* the nearest point of the ray is the point v2 */ - r_axis_closest[main_axis] = false; - - depth_sq = mul + data->ray.direction_scaled_square[main_axis] * v2[main_axis]; - - copy_v3_v3(r_point, v2); - } - else { /* the nearest point of the ray is on the edge of the `AABB`. */ - r_axis_closest[main_axis] = (proj - v1[main_axis]) < (v2[main_axis] - proj); - - depth_sq = mul + data->ray.direction_scaled_square[main_axis] * proj; -#if 0 - r_point[0] = main_axis == 0 ? proj : v2[0]; - r_point[1] = main_axis == 1 ? proj : v2[1]; - r_point[2] = main_axis == 2 ? proj : v2[2]; -#else - v2[main_axis] = proj; - copy_v3_v3(r_point, v2); -#endif - } - depth_sq *= depth_sq; - - if (r_depth_sq) - *r_depth_sq = depth_sq; - - /* TODO: scale can be optional */ - r_point[0] *= data->scale[0]; - r_point[1] *= data->scale[1]; - r_point[2] *= data->scale[2]; - - return len_squared_v3(r_point) - depth_sq; - } -} - -/** - * <pre> - * + r_point - * | - * | dist - * | - * +----depth----+orig <-- dir - * - * tangent = dist/depth - * </pre> - */ -static float calc_tangent_sq(BVHNearestRayData *data, BVHNode *node) -{ - float depth_sq; - const float dist_sq = dist_squared_ray_to_aabb_scaled_v3__impl( - data, node->bv, &depth_sq, data->pick_smallest); - - return (dist_sq != 0.0f) ? (dist_sq / depth_sq) : 0.0f; -} - -static float calc_dist_sq_to_ray(BVHNearestRayData *data, BVHNode *node) -{ - return dist_squared_ray_to_aabb_scaled_v3__impl( - data, node->bv, NULL, - data->pick_smallest); -} - -static void dfs_find_lowest_tangent_dfs(BVHNearestRayData *data, BVHNode *node) -{ - if (node->totnode == 0) { - if (data->callback) { - data->callback(data->userdata, data->ray.origin, data->ray.direction, - data->scale, node->index, &data->nearest); - } - else { - data->nearest.index = node->index; - data->nearest.dist_sq = calc_tangent_sq(data, node); - /* TODO: return a value to the data->nearest.co - * not urgent however since users currently define own callbacks */ - } - } - else { - int i; - /* First pick the closest node to dive on */ - if (data->pick_smallest[node->main_axis]) { - for (i = 0; i != node->totnode; i++) { - if (calc_tangent_sq(data, node->children[i]) < data->nearest.dist_sq) { - dfs_find_lowest_tangent_dfs(data, node->children[i]); - } - } - } - else { - for (i = node->totnode - 1; i >= 0; i--) { - if (calc_tangent_sq(data, node->children[i]) < data->nearest.dist_sq) { - dfs_find_lowest_tangent_dfs(data, node->children[i]); - } - } - } - } -} - -static void dfs_find_nearest_to_ray_dfs(BVHNearestRayData *data, BVHNode *node) -{ - if (node->totnode == 0) { - if (data->callback) { - data->callback(data->userdata, data->ray.origin, data->ray.direction, - data->scale, node->index, &data->nearest); - } - else { - data->nearest.index = node->index; - data->nearest.dist_sq = calc_dist_sq_to_ray(data, node); - /* TODO: return a value to the data->nearest.co - * not urgent however since users currently define own callbacks */ - } - } - else { - int i; - /* First pick the closest node to dive on */ - if (data->pick_smallest[node->main_axis]) { - for (i = 0; i != node->totnode; i++) { - if (calc_dist_sq_to_ray(data, node->children[i]) < data->nearest.dist_sq) { - dfs_find_nearest_to_ray_dfs(data, node->children[i]); - } - } - } - else { - for (i = node->totnode - 1; i >= 0; i--) { - if (calc_dist_sq_to_ray(data, node->children[i]) < data->nearest.dist_sq) { - dfs_find_nearest_to_ray_dfs(data, node->children[i]); - } - } - } - } -} - -/** - * Returns the point whose tangent defined by the angle between the point and ray is the lowest - * nearest.dist_sq returns the angle's tangent - */ -int BLI_bvhtree_find_nearest_to_ray_angle( - BVHTree *tree, const float co[3], const float dir[3], - const bool ray_is_normalized, const float scale[3], - BVHTreeNearest *nearest, - BVHTree_NearestToRayCallback callback, void *userdata) -{ - BVHNearestRayData data; - BVHNode *root = tree->nodes[tree->totleaf]; - - data.tree = tree; - - data.callback = callback; - data.userdata = userdata; - - dist_squared_ray_to_aabb_scaled_v3_precalc(&data, co, dir, ray_is_normalized, scale); - - if (nearest) { - memcpy(&data.nearest, nearest, sizeof(*nearest)); - } - else { - data.nearest.index = -1; - data.nearest.dist_sq = FLT_MAX; - } - - /* dfs search */ - if (root) { - if (calc_tangent_sq(&data, root) < data.nearest.dist_sq) - dfs_find_lowest_tangent_dfs(&data, root); - } - - /* copy back results */ - if (nearest) { - memcpy(nearest, &data.nearest, sizeof(*nearest)); - } - - return data.nearest.index; -} - -/* return the nearest point to ray */ -int BLI_bvhtree_find_nearest_to_ray( - BVHTree *tree, const float co[3], const float dir[3], - const bool ray_is_normalized, const float scale[3], - BVHTreeNearest *nearest, - BVHTree_NearestToRayCallback callback, void *userdata) -{ - BVHNearestRayData data; - BVHNode *root = tree->nodes[tree->totleaf]; - - data.tree = tree; - - data.callback = callback; - data.userdata = userdata; - - dist_squared_ray_to_aabb_scaled_v3_precalc(&data, co, dir, ray_is_normalized, scale); - - if (nearest) { - memcpy(&data.nearest, nearest, sizeof(*nearest)); - } - else { - data.nearest.index = -1; - data.nearest.dist_sq = FLT_MAX; - } - - /* dfs search */ - if (root) { - if (calc_dist_sq_to_ray(&data, root) < data.nearest.dist_sq) { - dfs_find_nearest_to_ray_dfs(&data, root); - } - } - - /* copy back results */ - if (nearest) { - memcpy(nearest, &data.nearest, sizeof(*nearest)); - } - - return data.nearest.index; -} - -/** \} */ - - -/* -------------------------------------------------------------------- */ - /** \name BLI_bvhtree_range_query * * Allocs and fills an array with the indexs of node that are on the given spherical range (center, radius). diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c index a81f9b28b83..84ac339cc4d 100644 --- a/source/blender/blenlib/intern/BLI_kdtree.c +++ b/source/blender/blenlib/intern/BLI_kdtree.c @@ -674,3 +674,123 @@ finally: if (stack != defaultstack) MEM_freeN(stack); } + +/** + * Use when we want to loop over nodes ordered by index. + * Requires indices to be aligned with nodes. + */ +static uint *kdtree_order(const KDTree *tree) +{ + const KDTreeNode *nodes = tree->nodes; + uint *order = MEM_mallocN(sizeof(uint) * tree->totnode, __func__); + for (uint i = 0; i < tree->totnode; i++) { + order[nodes[i].index] = i; + } + return order; +} + +/* -------------------------------------------------------------------- */ +/** \name BLI_kdtree_calc_duplicates_fast + * \{ */ + +struct DeDuplicateParams { + /* Static */ + const KDTreeNode *nodes; + float range; + float range_sq; + int *duplicates; + int *duplicates_found; + + /* Per Search */ + float search_co[3]; + int search; +}; + +static void deduplicate_recursive(const struct DeDuplicateParams *p, uint i) +{ + const KDTreeNode *node = &p->nodes[i]; + if (p->search_co[node->d] + p->range <= node->co[node->d]) { + if (node->left != KD_NODE_UNSET) { + deduplicate_recursive(p, node->left); + } + } + else if (p->search_co[node->d] - p->range >= node->co[node->d]) { + if (node->right != KD_NODE_UNSET) { + deduplicate_recursive(p, node->right); + } + } + else { + if ((p->search != node->index) && (p->duplicates[node->index] == -1)) { + if (compare_len_squared_v3v3(node->co, p->search_co, p->range_sq)) { + p->duplicates[node->index] = (int)p->search; + *p->duplicates_found += 1; + } + } + if (node->left != KD_NODE_UNSET) { + deduplicate_recursive(p, node->left); + } + if (node->right != KD_NODE_UNSET) { + deduplicate_recursive(p, node->right); + } + } +} + +/** + * Find duplicate points in \a range. + * Favors speed over quality since it doesn't find the best target vertex for merging. + * Nodes are looped over, duplicates are added when found. + * Nevertheless results are predictable. + * + * \param range: Coordinates in this range are candidates to be merged. + * \param use_index_order: Loop over the coordinates ordered by #KDTreeNode.index + * At the expense of some performance, this ensures the layout of the tree doesn't influence + * the iteration order. + * \param duplicates: An array of int's the length of #KDTree.totnode + * Values initialized to -1 are candidates to me merged. + * Setting the index to it's own position in the array prevents it from being touched, + * although it can still be used as a target. + * \returns The numebr of merges found (includes any merges already in the \a duplicates array). + * + * \note Merging is always a single step (target indices wont be marked for merging). + */ +int BLI_kdtree_calc_duplicates_fast( + const KDTree *tree, const float range, bool use_index_order, + int *duplicates) +{ + int found = 0; + struct DeDuplicateParams p = { + .nodes = tree->nodes, + .range = range, + .range_sq = range * range, + .duplicates = duplicates, + .duplicates_found = &found, + }; + + if (use_index_order) { + uint *order = kdtree_order(tree); + for (uint i = 0; i < tree->totnode; i++) { + const uint node_index = order[i]; + const int index = (int)i; + if (ELEM(duplicates[index], -1, index)) { + p.search = index; + copy_v3_v3(p.search_co, tree->nodes[node_index].co); + deduplicate_recursive(&p, tree->root); + } + } + MEM_freeN(order); + } + else { + for (uint i = 0; i < tree->totnode; i++) { + const uint node_index = i; + const int index = p.nodes[node_index].index; + if (ELEM(duplicates[index], -1, index)) { + p.search = index; + copy_v3_v3(p.search_co, tree->nodes[node_index].co); + deduplicate_recursive(&p, tree->root); + } + } + } + return found; +} + +/** \} */ diff --git a/source/blender/blenlib/intern/array_store.c b/source/blender/blenlib/intern/array_store.c index 21ddddad32e..d3a63aceb89 100644 --- a/source/blender/blenlib/intern/array_store.c +++ b/source/blender/blenlib/intern/array_store.c @@ -217,15 +217,12 @@ /** \name Internal Structs * \{ */ -typedef unsigned int uint; -typedef unsigned char ubyte; - typedef uint64_t hash_key; typedef struct BArrayInfo { size_t chunk_stride; - uint chunk_count; + // uint chunk_count; /* UNUSED (other values are derived from this) */ /* pre-calculated */ size_t chunk_byte_size; @@ -291,7 +288,7 @@ typedef struct BChunkList { /* a chunk of an array */ typedef struct BChunk { - const ubyte *data; + const uchar *data; size_t data_len; /** number of #BChunkList using this. */ int users; @@ -332,7 +329,7 @@ static size_t bchunk_list_size(const BChunkList *chunk_list); * \{ */ static BChunk *bchunk_new( - BArrayMemory *bs_mem, const ubyte *data, const size_t data_len) + BArrayMemory *bs_mem, const uchar *data, const size_t data_len) { BChunk *chunk = BLI_mempool_alloc(bs_mem->chunk); chunk->data = data; @@ -345,9 +342,9 @@ static BChunk *bchunk_new( } static BChunk *bchunk_new_copydata( - BArrayMemory *bs_mem, const ubyte *data, const size_t data_len) + BArrayMemory *bs_mem, const uchar *data, const size_t data_len) { - ubyte *data_copy = MEM_mallocN(data_len, __func__); + uchar *data_copy = MEM_mallocN(data_len, __func__); memcpy(data_copy, data, data_len); return bchunk_new(bs_mem, data_copy, data_len); } @@ -367,7 +364,7 @@ static void bchunk_decref( static bool bchunk_data_compare( const BChunk *chunk, - const ubyte *data_base, const size_t data_base_len, + const uchar *data_base, const size_t data_base_len, const size_t offset) { if (offset + (size_t)chunk->data_len <= data_base_len) { @@ -426,14 +423,14 @@ static void bchunk_list_decref( #ifdef USE_VALIDATE_LIST_DATA_PARTIAL static size_t bchunk_list_data_check( - const BChunkList *chunk_list, const ubyte *data) + const BChunkList *chunk_list, const uchar *data) { - size_t total_size = 0; + size_t offset = 0; for (BChunkRef *cref = chunk_list->chunk_refs.first; cref; cref = cref->next) { - if (memcmp(&data[total_size], cref->link->data, cref->link->data_len) != 0) { + if (memcmp(&data[offset], cref->link->data, cref->link->data_len) != 0) { return false; } - total_size += cref->link->data_len; + offset += cref->link->data_len; } return true; } @@ -466,7 +463,7 @@ static void bchunk_list_ensure_min_size_last( chunk_list->chunk_refs.last = cref->prev; chunk_list->chunk_refs_len -= 1; - ubyte *data_merge = MEM_mallocN(data_merge_len, __func__); + uchar *data_merge = MEM_mallocN(data_merge_len, __func__); memcpy(data_merge, chunk_prev->data, chunk_prev->data_len); memcpy(&data_merge[chunk_prev->data_len], chunk_curr->data, chunk_curr->data_len); @@ -487,8 +484,8 @@ static void bchunk_list_ensure_min_size_last( /* merge and split */ const size_t data_prev_len = split; const size_t data_curr_len = data_merge_len - split; - ubyte *data_prev = MEM_mallocN(data_prev_len, __func__); - ubyte *data_curr = MEM_mallocN(data_curr_len, __func__); + uchar *data_prev = MEM_mallocN(data_prev_len, __func__); + uchar *data_curr = MEM_mallocN(data_curr_len, __func__); if (data_prev_len <= chunk_prev->data_len) { const size_t data_curr_shrink_len = chunk_prev->data_len - data_prev_len; @@ -597,11 +594,10 @@ static void bchunk_list_append_only( static void bchunk_list_append_data( const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, - const ubyte *data, const size_t data_len) + const uchar *data, const size_t data_len) { BLI_assert(data_len != 0); - // printf("data_len: %d\n", data_len); #ifdef USE_MERGE_CHUNKS BLI_assert(data_len <= info->chunk_byte_size_max); @@ -613,13 +609,13 @@ static void bchunk_list_append_data( const size_t data_merge_len = chunk_prev->data_len + data_len; /* realloc for single user */ if (cref->link->users == 1) { - ubyte *data_merge = MEM_reallocN((void *)cref->link->data, data_merge_len); + uchar *data_merge = MEM_reallocN((void *)cref->link->data, data_merge_len); memcpy(&data_merge[chunk_prev->data_len], data, data_len); cref->link->data = data_merge; cref->link->data_len = data_merge_len; } else { - ubyte *data_merge = MEM_mallocN(data_merge_len, __func__); + uchar *data_merge = MEM_mallocN(data_merge_len, __func__); memcpy(data_merge, chunk_prev->data, chunk_prev->data_len); memcpy(&data_merge[chunk_prev->data_len], data, data_len); cref->link = bchunk_new(bs_mem, data_merge, data_merge_len); @@ -639,7 +635,7 @@ static void bchunk_list_append_data( /* don't run this, instead preemptively avoid creating a chunk only to merge it (above). */ #if 0 #ifdef USE_MERGE_CHUNKS - bchunk_list_ensure_min_size_last(info, bs_mem, chunk_list, chunk_size_min); + bchunk_list_ensure_min_size_last(info, bs_mem, chunk_list); #endif #endif } @@ -654,7 +650,7 @@ static void bchunk_list_append_data( static void bchunk_list_append_data_n( const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, - const ubyte *data, size_t data_len) + const uchar *data, size_t data_len) { size_t data_trim_len, data_last_chunk_len; bchunk_list_calc_trim_len(info, data_len, &data_trim_len, &data_last_chunk_len); @@ -714,7 +710,7 @@ static void bchunk_list_append( static void bchunk_list_fill_from_array( const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, - const ubyte *data, + const uchar *data, const size_t data_len) { BLI_assert(BLI_listbase_is_empty(&chunk_list->chunk_refs)); @@ -765,13 +761,13 @@ static void bchunk_list_fill_from_array( #define HASH_INIT (5381) -BLI_INLINE uint hash_data_single(const ubyte p) +BLI_INLINE uint hash_data_single(const uchar p) { return (HASH_INIT << 5) + HASH_INIT + (unsigned int)p; } /* hash bytes, from BLI_ghashutil_strhash_n */ -static uint hash_data(const ubyte *key, size_t n) +static uint hash_data(const uchar *key, size_t n) { const signed char *p; unsigned int h = HASH_INIT; @@ -788,7 +784,7 @@ static uint hash_data(const ubyte *key, size_t n) #ifdef USE_HASH_TABLE_ACCUMULATE static void hash_array_from_data( - const BArrayInfo *info, const ubyte *data_slice, const size_t data_slice_len, + const BArrayInfo *info, const uchar *data_slice, const size_t data_slice_len, hash_key *hash_array) { if (info->chunk_stride != 1) { @@ -877,12 +873,12 @@ static void hash_accum_single(hash_key *hash_array, const size_t hash_array_len, static hash_key key_from_chunk_ref( const BArrayInfo *info, const BChunkRef *cref, - /* avoid reallicating each time */ + /* avoid reallocating each time */ hash_key *hash_store, const size_t hash_store_len) { /* in C, will fill in a reusable array */ BChunk *chunk = cref->link; - BLI_assert(info->accum_read_ahead_bytes * info->chunk_stride); + BLI_assert((info->accum_read_ahead_bytes * info->chunk_stride) != 0); if (info->accum_read_ahead_bytes <= chunk->data_len) { hash_key key; @@ -899,7 +895,7 @@ static hash_key key_from_chunk_ref( key = hash_store[0]; /* cache the key */ - if (key == HASH_TABLE_KEY_UNSET) { + if (UNLIKELY(key == HASH_TABLE_KEY_UNSET)) { key = HASH_TABLE_KEY_FALLBACK; } chunk->key = key; @@ -929,12 +925,12 @@ static hash_key key_from_chunk_ref( static const BChunkRef *table_lookup( const BArrayInfo *info, BTableRef **table, const size_t table_len, const size_t i_table_start, - const ubyte *data, const size_t data_len, const size_t offset, const hash_key *table_hash_array) + const uchar *data, const size_t data_len, const size_t offset, const hash_key *table_hash_array) { size_t size_left = data_len - offset; hash_key key = table_hash_array[((offset - i_table_start) / info->chunk_stride)]; size_t key_index = (size_t)(key % (hash_key)table_len); - for (BTableRef *tref = table[key_index]; tref; tref = tref->next) { + for (const BTableRef *tref = table[key_index]; tref; tref = tref->next) { const BChunkRef *cref = tref->cref; #ifdef USE_HASH_TABLE_KEY_CACHE if (cref->link->key == key) @@ -985,7 +981,7 @@ static hash_key key_from_chunk_ref(const BArrayInfo *info, const BChunkRef *cref static const BChunkRef *table_lookup( const BArrayInfo *info, BTableRef **table, const size_t table_len, const uint UNUSED(i_table_start), - const ubyte *data, const size_t data_len, const size_t offset, const hash_key *UNUSED(table_hash_array)) + const uchar *data, const size_t data_len, const size_t offset, const hash_key *UNUSED(table_hash_array)) { const size_t data_hash_len = BCHUNK_HASH_LEN * info->chunk_stride; /* TODO, cache */ @@ -1025,7 +1021,7 @@ static const BChunkRef *table_lookup( */ static BChunkList *bchunk_list_from_data_merge( const BArrayInfo *info, BArrayMemory *bs_mem, - const ubyte *data, const size_t data_len_original, + const uchar *data, const size_t data_len_original, const BChunkList *chunk_list_reference) { ASSERT_CHUNKLIST_SIZE(chunk_list_reference, chunk_list_reference->total_size); @@ -1042,10 +1038,8 @@ static BChunkList *bchunk_list_from_data_merge( size_t i_prev = 0; #ifdef USE_FASTPATH_CHUNKS_FIRST - bool full_match = false; - { - full_match = true; + bool full_match = true; const BChunkRef *cref = chunk_list_reference->chunk_refs.first; while (i_prev < data_len_original) { @@ -1433,7 +1427,7 @@ BArrayStore *BLI_array_store_create( BArrayStore *bs = MEM_callocN(sizeof(BArrayStore), __func__); bs->info.chunk_stride = stride; - bs->info.chunk_count = chunk_count; + // bs->info.chunk_count = chunk_count; bs->info.chunk_byte_size = chunk_count * stride; #ifdef USE_MERGE_CHUNKS @@ -1566,7 +1560,7 @@ BArrayState *BLI_array_store_state_add( const void *data, const size_t data_len, const BArrayState *state_reference) { - /* ensure we're aligned to the stride */ + /* ensure we're aligned to the stride */ BLI_assert((data_len % bs->info.chunk_stride) == 0); #ifdef USE_PARANOID_CHECKS @@ -1579,7 +1573,7 @@ BArrayState *BLI_array_store_state_add( if (state_reference) { chunk_list = bchunk_list_from_data_merge( &bs->info, &bs->memory, - (const ubyte *)data, data_len, + (const uchar *)data, data_len, /* re-use reference chunks */ state_reference->chunk_list); } @@ -1588,7 +1582,7 @@ BArrayState *BLI_array_store_state_add( bchunk_list_fill_from_array( &bs->info, &bs->memory, chunk_list, - (const ubyte *)data, data_len); + (const uchar *)data, data_len); } chunk_list->users += 1; @@ -1655,7 +1649,7 @@ void BLI_array_store_state_data_get( BLI_assert(data_test_len == state->chunk_list->total_size); #endif - ubyte *data_step = (ubyte *)data; + uchar *data_step = (uchar *)data; for (BChunkRef *cref = state->chunk_list->chunk_refs.first; cref; cref = cref->next) { BLI_assert(cref->link->users > 0); memcpy(data_step, cref->link->data, cref->link->data_len); diff --git a/source/blender/blenlib/intern/bitmap_draw_2d.c b/source/blender/blenlib/intern/bitmap_draw_2d.c index afc54511d13..e77e8cf40d0 100644 --- a/source/blender/blenlib/intern/bitmap_draw_2d.c +++ b/source/blender/blenlib/intern/bitmap_draw_2d.c @@ -46,6 +46,8 @@ /** * Plot a line from \a p1 to \a p2 (inclusive). + * + * \note For clipped line drawing, see: http://stackoverflow.com/a/40902741/432509 */ void BLI_bitmap_draw_2d_line_v2v2i( const int p1[2], const int p2[2], @@ -57,33 +59,36 @@ void BLI_bitmap_draw_2d_line_v2v2i( int x2 = p2[0]; int y2 = p2[1]; - int ix; - int iy; - - /* if x1 == x2 or y1 == y2, then it does not matter what we set here */ - int delta_x = (x2 > x1 ? ((void)(ix = 1), x2 - x1) : ((void)(ix = -1), x1 - x2)) << 1; - int delta_y = (y2 > y1 ? ((void)(iy = 1), y2 - y1) : ((void)(iy = -1), y1 - y2)) << 1; - if (callback(x1, y1, userData) == 0) { return; } + /* if x1 == x2 or y1 == y2, then it does not matter what we set here */ + const int sign_x = (x2 > x1) ? 1 : -1; + const int sign_y = (y2 > y1) ? 1 : -1; + + const int delta_x = (sign_x == 1) ? (x2 - x1) : (x1 - x2); + const int delta_y = (sign_y == 1) ? (y2 - y1) : (y1 - y2); + + const int delta_x_step = delta_x * 2; + const int delta_y_step = delta_y * 2; + if (delta_x >= delta_y) { /* error may go below zero */ - int error = delta_y - (delta_x >> 1); + int error = delta_y_step - delta_x; while (x1 != x2) { if (error >= 0) { - if (error || (ix > 0)) { - y1 += iy; - error -= delta_x; + if (error || (sign_x == 1)) { + y1 += sign_y; + error -= delta_x_step; } /* else do nothing */ } /* else do nothing */ - x1 += ix; - error += delta_y; + x1 += sign_x; + error += delta_y_step; if (callback(x1, y1, userData) == 0) { return; @@ -92,20 +97,20 @@ void BLI_bitmap_draw_2d_line_v2v2i( } else { /* error may go below zero */ - int error = delta_x - (delta_y >> 1); + int error = delta_x_step - delta_y; while (y1 != y2) { if (error >= 0) { - if (error || (iy > 0)) { - x1 += ix; - error -= delta_y; + if (error || (sign_y == 1)) { + x1 += sign_x; + error -= delta_y_step; } /* else do nothing */ } /* else do nothing */ - y1 += iy; - error += delta_x; + y1 += sign_y; + error += delta_x_step; if (callback(x1, y1, userData) == 0) { return; diff --git a/source/blender/blenlib/intern/dynlib.c b/source/blender/blenlib/intern/dynlib.c index b47c2ee60a6..51b91fb360f 100644 --- a/source/blender/blenlib/intern/dynlib.c +++ b/source/blender/blenlib/intern/dynlib.c @@ -50,7 +50,7 @@ struct DynamicLibrary { #include "utf_winfunc.h" #include "utfconv.h" -DynamicLibrary *BLI_dynlib_open(char *name) +DynamicLibrary *BLI_dynlib_open(const char *name) { DynamicLibrary *lib; void *handle; @@ -106,7 +106,7 @@ void BLI_dynlib_close(DynamicLibrary *lib) #include <dlfcn.h> -DynamicLibrary *BLI_dynlib_open(char *name) +DynamicLibrary *BLI_dynlib_open(const char *name) { DynamicLibrary *lib; void *handle = dlopen(name, RTLD_LAZY); diff --git a/source/blender/blenlib/intern/fileops.c b/source/blender/blenlib/intern/fileops.c index db4b3bcf20c..1df7f6f81e4 100644 --- a/source/blender/blenlib/intern/fileops.c +++ b/source/blender/blenlib/intern/fileops.c @@ -42,9 +42,6 @@ #include "zlib.h" #ifdef WIN32 -# ifdef __MINGW32__ -# include <ctype.h> -# endif # include <io.h> # include "BLI_winstuff.h" # include "BLI_callbacks.h" @@ -265,7 +262,7 @@ void *BLI_gzopen(const char *filename, const char *mode) /* temporary #if until we update all libraries to 1.2.7 * for correct wide char path handling */ -#if ZLIB_VERNUM >= 0x1270 && !defined(FREE_WINDOWS) +#if ZLIB_VERNUM >= 0x1270 UTF16_ENCODE(filename); gzfile = gzopen_w(filename_16, mode); diff --git a/source/blender/blenlib/intern/freetypefont.c b/source/blender/blenlib/intern/freetypefont.c index 8719c92a2a6..e990f0b663c 100644 --- a/source/blender/blenlib/intern/freetypefont.c +++ b/source/blender/blenlib/intern/freetypefont.c @@ -481,6 +481,22 @@ VFontData *BLI_vfontdata_from_freetypefont(PackedFile *pf) return vfd; } +static void *vfontdata_copy_characters_value_cb(const void *src) +{ + return BLI_vfontchar_copy(src, 0); +} + +VFontData *BLI_vfontdata_copy(const VFontData *vfont_src, const int UNUSED(flag)) +{ + VFontData *vfont_dst = MEM_dupallocN(vfont_src); + + if (vfont_src->characters != NULL) { + vfont_dst->characters = BLI_ghash_copy(vfont_src->characters, NULL, vfontdata_copy_characters_value_cb); + } + + return vfont_dst; +} + VChar *BLI_vfontchar_from_freetypefont(VFont *vfont, unsigned long character) { VChar *che = NULL; @@ -503,6 +519,20 @@ VChar *BLI_vfontchar_from_freetypefont(VFont *vfont, unsigned long character) return che; } +/* Yeah, this is very bad... But why is this in BLI in the first place, since it uses Nurb data? + * Anyway, do not feel like duplicating whole Nurb copy code here, so unless someone has a better idea... */ +#include "../../blenkernel/BKE_curve.h" + +VChar *BLI_vfontchar_copy(const VChar *vchar_src, const int UNUSED(flag)) +{ + VChar *vchar_dst = MEM_dupallocN(vchar_src); + + BLI_listbase_clear(&vchar_dst->nurbsbase); + BKE_nurbList_duplicate(&vchar_dst->nurbsbase, &vchar_src->nurbsbase); + + return vchar_dst; +} + #if 0 /* Freetype2 Outline struct */ diff --git a/source/blender/blenlib/intern/hash_mm2a.c b/source/blender/blenlib/intern/hash_mm2a.c index af6ef4f355f..e8ca9244f25 100644 --- a/source/blender/blenlib/intern/hash_mm2a.c +++ b/source/blender/blenlib/intern/hash_mm2a.c @@ -36,6 +36,8 @@ * for temporary data. */ +#include "BLI_compiler_attrs.h" + #include "BLI_hash_mm2a.h" /* own include */ /* Helpers. */ @@ -128,10 +130,10 @@ uint32_t BLI_hash_mm2(const unsigned char *data, size_t len, uint32_t seed) switch (len) { case 3: h ^= data[2] << 16; - /* fall through */ + ATTR_FALLTHROUGH; case 2: h ^= data[1] << 8; - /* fall through */ + ATTR_FALLTHROUGH; case 1: h ^= data[0]; h *= MM2A_M; diff --git a/source/blender/blenlib/intern/listbase.c b/source/blender/blenlib/intern/listbase.c index c9bf4976ae8..46dcee48eda 100644 --- a/source/blender/blenlib/intern/listbase.c +++ b/source/blender/blenlib/intern/listbase.c @@ -342,6 +342,40 @@ void BLI_insertlinkbefore(ListBase *listbase, void *vnextlink, void *vnewlink) } } + +/** + * Insert a link in place of another, without changing it's position in the list. + * + * Puts `vnewlink` in the position of `vreplacelink`, removing `vreplacelink`. + * - `vreplacelink` *must* be in the list. + * - `vnewlink` *must not* be in the list. + */ +void BLI_insertlinkreplace(ListBase *listbase, void *vreplacelink, void *vnewlink) +{ + Link *l_old = vreplacelink; + Link *l_new = vnewlink; + + /* update adjacent links */ + if (l_old->next != NULL) { + l_old->next->prev = l_new; + } + if (l_old->prev != NULL) { + l_old->prev->next = l_new; + } + + /* set direct links */ + l_new->next = l_old->next; + l_new->prev = l_old->prev; + + /* update list */ + if (listbase->first == l_old) { + listbase->first = l_new; + } + if (listbase->last == l_old) { + listbase->last = l_new; + } +} + /** * Reinsert \a vlink relative to its current position but offset by \a step. Doesn't move * item if new position would exceed list (could optionally move to head/tail). @@ -630,7 +664,7 @@ void *BLI_rfindptr(const ListBase *listbase, const void *ptr, const int offset) } /** - * Returns the 1-based index of the first element of listbase which contains the specified + * Returns the 0-based index of the first element of listbase which contains the specified * null-terminated string at the specified offset, or -1 if not found. */ int BLI_findstringindex(const ListBase *listbase, const char *id, const int offset) diff --git a/source/blender/blenlib/intern/math_base_inline.c b/source/blender/blenlib/intern/math_base_inline.c index 8d2d80c2a35..749c18fc0ce 100644 --- a/source/blender/blenlib/intern/math_base_inline.c +++ b/source/blender/blenlib/intern/math_base_inline.c @@ -33,6 +33,7 @@ #include <float.h> #include <stdio.h> #include <stdlib.h> +#include <limits.h> #ifdef __SSE2__ # include <emmintrin.h> @@ -181,11 +182,59 @@ MINLINE unsigned power_of_2_min_u(unsigned x) return x - (x >> 1); } -MINLINE int iroundf(float a) -{ - return (int)floorf(a + 0.5f); +/* rounding and clamping */ + +#define _round_clamp_fl_impl(arg, ty, min, max) { \ + float r = floorf(arg + 0.5f); \ + if (UNLIKELY(r <= (float)min)) return (ty)min; \ + else if (UNLIKELY(r >= (float)max)) return (ty)max; \ + else return (ty)r; \ +} + +#define _round_clamp_db_impl(arg, ty, min, max) { \ + double r = floor(arg + 0.5); \ + if (UNLIKELY(r <= (double)min)) return (ty)min; \ + else if (UNLIKELY(r >= (double)max)) return (ty)max; \ + else return (ty)r; \ } +#define _round_fl_impl(arg, ty) { return (ty)floorf(arg + 0.5f); } +#define _round_db_impl(arg, ty) { return (ty)floor(arg + 0.5); } + +MINLINE signed char round_fl_to_char(float a) { _round_fl_impl(a, signed char) } +MINLINE unsigned char round_fl_to_uchar(float a) { _round_fl_impl(a, unsigned char) } +MINLINE short round_fl_to_short(float a) { _round_fl_impl(a, short) } +MINLINE unsigned short round_fl_to_ushort(float a) { _round_fl_impl(a, unsigned short) } +MINLINE int round_fl_to_int(float a) { _round_fl_impl(a, int) } +MINLINE unsigned int round_fl_to_uint(float a) { _round_fl_impl(a, unsigned int) } + +MINLINE signed char round_db_to_char(double a) { _round_db_impl(a, signed char) } +MINLINE unsigned char round_db_to_uchar(double a) { _round_db_impl(a, unsigned char) } +MINLINE short round_db_to_short(double a) { _round_db_impl(a, short) } +MINLINE unsigned short round_db_to_ushort(double a) { _round_db_impl(a, unsigned short) } +MINLINE int round_db_to_int(double a) { _round_db_impl(a, int) } +MINLINE unsigned int round_db_to_uint(double a) { _round_db_impl(a, unsigned int) } + +#undef _round_fl_impl +#undef _round_db_impl + +MINLINE signed char round_fl_to_char_clamp(float a) { _round_clamp_fl_impl(a, signed char, SCHAR_MIN, SCHAR_MAX) } +MINLINE unsigned char round_fl_to_uchar_clamp(float a) { _round_clamp_fl_impl(a, unsigned char, 0, UCHAR_MAX) } +MINLINE short round_fl_to_short_clamp(float a) { _round_clamp_fl_impl(a, short, SHRT_MIN, SHRT_MAX) } +MINLINE unsigned short round_fl_to_ushort_clamp(float a) { _round_clamp_fl_impl(a, unsigned short, 0, USHRT_MAX) } +MINLINE int round_fl_to_int_clamp(float a) { _round_clamp_fl_impl(a, int, INT_MIN, INT_MAX) } +MINLINE unsigned int round_fl_to_uint_clamp(float a) { _round_clamp_fl_impl(a, unsigned int, 0, UINT_MAX) } + +MINLINE signed char round_db_to_char_clamp(double a) { _round_clamp_db_impl(a, signed char, SCHAR_MIN, SCHAR_MAX) } +MINLINE unsigned char round_db_to_uchar_clamp(double a) { _round_clamp_db_impl(a, unsigned char, 0, UCHAR_MAX) } +MINLINE short round_db_to_short_clamp(double a) { _round_clamp_db_impl(a, short, SHRT_MIN, SHRT_MAX) } +MINLINE unsigned short round_db_to_ushort_clamp(double a) { _round_clamp_db_impl(a, unsigned short, 0, USHRT_MAX) } +MINLINE int round_db_to_int_clamp(double a) { _round_clamp_db_impl(a, int, INT_MIN, INT_MAX) } +MINLINE unsigned int round_db_to_uint_clamp(double a) { _round_clamp_db_impl(a, unsigned int, 0, UINT_MAX) } + +#undef _round_clamp_fl_impl +#undef _round_clamp_db_impl + /* integer division that rounds 0.5 up, particularly useful for color blending * with integers, to avoid gradual darkening when rounding down */ MINLINE int divide_round_i(int a, int b) @@ -194,6 +243,17 @@ MINLINE int divide_round_i(int a, int b) } /** + * Integer division that floors negative result. + * \note This works like Python's int division. + */ +MINLINE int divide_floor_i(int a, int b) +{ + int d = a / b; + int r = a % b; /* Optimizes into a single division. */ + return r ? d - ((a < 0) ^ (b < 0)) : d; +} + +/** * modulo that handles negative numbers, works the same as Python's. */ MINLINE int mod_i(int i, int n) @@ -314,6 +374,21 @@ MINLINE int signum_i(float a) else return 0; } +/** Returns number of (base ten) *significant* digits of integer part of given float + * (negative in case of decimal-only floats, 0.01 returns -1 e.g.). */ +MINLINE int integer_digits_f(const float f) +{ + return (f == 0.0f) ? 0 : (int)floor(log10(fabs(f))) + 1; +} + +/** Returns number of (base ten) *significant* digits of integer part of given double + * (negative in case of decimal-only floats, 0.01 returns -1 e.g.). */ +MINLINE int integer_digits_d(const double d) +{ + return (d == 0.0) ? 0 : (int)floor(log10(fabs(d))) + 1; +} + + /* Internal helpers for SSE2 implementation. * * NOTE: Are to be called ONLY from inside `#ifdef __SSE2__` !!! diff --git a/source/blender/blenlib/intern/math_color_blend_inline.c b/source/blender/blenlib/intern/math_color_blend_inline.c index 048ab71c6dc..dc3874f83a2 100644 --- a/source/blender/blenlib/intern/math_color_blend_inline.c +++ b/source/blender/blenlib/intern/math_color_blend_inline.c @@ -444,7 +444,7 @@ MINLINE void blend_color_vividlight_byte(unsigned char dst[4], unsigned const ch else if (src2[i] == 0) { temp = 0; } - else if (src2[i] > 127) { + else if (src2[i] > 127) { temp = min_ii(((src1[i]) * 255) / (2 * (255 - src2[i])), 255); } else { diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index f31d0935b77..d3080e5530f 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -37,20 +37,6 @@ /********************************** Polygons *********************************/ -void cent_tri_v3(float cent[3], const float v1[3], const float v2[3], const float v3[3]) -{ - cent[0] = (v1[0] + v2[0] + v3[0]) / 3.0f; - cent[1] = (v1[1] + v2[1] + v3[1]) / 3.0f; - cent[2] = (v1[2] + v2[2] + v3[2]) / 3.0f; -} - -void cent_quad_v3(float cent[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3]) -{ - cent[0] = 0.25f * (v1[0] + v2[0] + v3[0] + v4[0]); - cent[1] = 0.25f * (v1[1] + v2[1] + v3[1] + v4[1]); - cent[2] = 0.25f * (v1[2] + v2[2] + v3[2] + v4[2]); -} - void cross_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3]) { float n1[3], n2[3]; @@ -586,8 +572,8 @@ float dist_squared_to_ray_v3( } /** * Find the closest point in a seg to a ray and return the distance squared. - * \param r_point : Is the point on segment closest to ray (or to ray_origin if the ray and the segment are parallel). - * \param depth: the distance of r_point projection on ray to the ray_origin. + * \param r_point: Is the point on segment closest to ray (or to ray_origin if the ray and the segment are parallel). + * \param r_depth: the distance of r_point projection on ray to the ray_origin. */ float dist_squared_ray_to_seg_v3( const float ray_origin[3], const float ray_direction[3], @@ -633,6 +619,152 @@ float dist_squared_ray_to_seg_v3( return len_squared_v3(t) - SQUARE(*r_depth); } +/* -------------------------------------------------------------------- */ +/** \name dist_squared_to_ray_to_aabb and helpers + * \{ */ + +void dist_squared_ray_to_aabb_v3_precalc( + struct DistRayAABB_Precalc *neasrest_precalc, + const float ray_origin[3], const float ray_direction[3]) +{ + copy_v3_v3(neasrest_precalc->ray_origin, ray_origin); + copy_v3_v3(neasrest_precalc->ray_direction, ray_direction); + + for (int i = 0; i < 3; i++) { + neasrest_precalc->ray_inv_dir[i] = + (neasrest_precalc->ray_direction[i] != 0.0f) ? + (1.0f / neasrest_precalc->ray_direction[i]) : FLT_MAX; + neasrest_precalc->sign[i] = (neasrest_precalc->ray_inv_dir[i] < 0.0f); + } +} + +/** + * Returns the distance from a ray to a bound-box (projected on ray) + */ +float dist_squared_ray_to_aabb_v3( + const struct DistRayAABB_Precalc *data, + const float bb_min[3], const float bb_max[3], + float r_point[3], float *r_depth) +{ + // bool r_axis_closest[3]; + float local_bvmin[3], local_bvmax[3]; + if (data->sign[0]) { + local_bvmin[0] = bb_max[0]; + local_bvmax[0] = bb_min[0]; + } + else { + local_bvmin[0] = bb_min[0]; + local_bvmax[0] = bb_max[0]; + } + if (data->sign[1]) { + local_bvmin[1] = bb_max[1]; + local_bvmax[1] = bb_min[1]; + } + else { + local_bvmin[1] = bb_min[1]; + local_bvmax[1] = bb_max[1]; + } + if (data->sign[2]) { + local_bvmin[2] = bb_max[2]; + local_bvmax[2] = bb_min[2]; + } + else { + local_bvmin[2] = bb_min[2]; + local_bvmax[2] = bb_max[2]; + } + + const float tmin[3] = { + (local_bvmin[0] - data->ray_origin[0]) * data->ray_inv_dir[0], + (local_bvmin[1] - data->ray_origin[1]) * data->ray_inv_dir[1], + (local_bvmin[2] - data->ray_origin[2]) * data->ray_inv_dir[2], + }; + const float tmax[3] = { + (local_bvmax[0] - data->ray_origin[0]) * data->ray_inv_dir[0], + (local_bvmax[1] - data->ray_origin[1]) * data->ray_inv_dir[1], + (local_bvmax[2] - data->ray_origin[2]) * data->ray_inv_dir[2], + }; + /* `va` and `vb` are the coordinates of the AABB edge closest to the ray */ + float va[3], vb[3]; + /* `rtmin` and `rtmax` are the minimum and maximum distances of the ray hits on the AABB */ + float rtmin, rtmax; + int main_axis; + + if ((tmax[0] <= tmax[1]) && (tmax[0] <= tmax[2])) { + rtmax = tmax[0]; + va[0] = vb[0] = local_bvmax[0]; + main_axis = 3; + // r_axis_closest[0] = data->sign[0]; + } + else if ((tmax[1] <= tmax[0]) && (tmax[1] <= tmax[2])) { + rtmax = tmax[1]; + va[1] = vb[1] = local_bvmax[1]; + main_axis = 2; + // r_axis_closest[1] = data->sign[1]; + } + else { + rtmax = tmax[2]; + va[2] = vb[2] = local_bvmax[2]; + main_axis = 1; + // r_axis_closest[2] = data->sign[2]; + } + + if ((tmin[0] >= tmin[1]) && (tmin[0] >= tmin[2])) { + rtmin = tmin[0]; + va[0] = vb[0] = local_bvmin[0]; + main_axis -= 3; + // r_axis_closest[0] = !data->sign[0]; + } + else if ((tmin[1] >= tmin[0]) && (tmin[1] >= tmin[2])) { + rtmin = tmin[1]; + va[1] = vb[1] = local_bvmin[1]; + main_axis -= 1; + // r_axis_closest[1] = !data->sign[1]; + } + else { + rtmin = tmin[2]; + va[2] = vb[2] = local_bvmin[2]; + main_axis -= 2; + // r_axis_closest[2] = !data->sign[2]; + } + if (main_axis < 0) { + main_axis += 3; + } + + /* if rtmin <= rtmax, ray intersect `AABB` */ + if (rtmin <= rtmax) { + float dvec[3]; + copy_v3_v3(r_point, local_bvmax); + sub_v3_v3v3(dvec, local_bvmax, data->ray_origin); + *r_depth = dot_v3v3(dvec, data->ray_direction); + return 0.0f; + } + + if (data->sign[main_axis]) { + va[main_axis] = local_bvmax[main_axis]; + vb[main_axis] = local_bvmin[main_axis]; + } + else { + va[main_axis] = local_bvmin[main_axis]; + vb[main_axis] = local_bvmax[main_axis]; + } + + return dist_squared_ray_to_seg_v3( + data->ray_origin, data->ray_direction, va, vb, + r_point, r_depth); +} + +float dist_squared_ray_to_aabb_v3_simple( + const float ray_origin[3], const float ray_direction[3], + const float bbmin[3], const float bbmax[3], + float r_point[3], float *r_depth) +{ + struct DistRayAABB_Precalc data; + dist_squared_ray_to_aabb_v3_precalc(&data, ray_origin, ray_direction); + return dist_squared_ray_to_aabb_v3(&data, bbmin, bbmax, r_point, r_depth); +} +/** \} */ + + /* Adapted from "Real-Time Collision Detection" by Christer Ericson, * published by Morgan Kaufmann Publishers, copyright 2005 Elsevier Inc. * @@ -779,18 +911,29 @@ int isect_seg_seg_v2(const float v1[2], const float v2[2], const float v3[2], co return ISECT_LINE_LINE_NONE; } -/* get intersection point of two 2D segments and return intersection type: - * -1: collinear - * 1: intersection +/** + * Get intersection point of two 2D segments. + * + * \param endpoint_bias: Bias to use when testing for end-point overlap. + * A positive value considers intersections that extend past the endpoints, + * negative values contract the endpoints. + * Note the bias is applied to a 0-1 factor, not scaled to the length of segments. + * + * \returns intersection type: + * - -1: collinear. + * - 1: intersection. + * - 0: no intersection. */ -int isect_seg_seg_v2_point( +int isect_seg_seg_v2_point_ex( const float v0[2], const float v1[2], const float v2[2], const float v3[2], + const float endpoint_bias, float r_vi[2]) { float s10[2], s32[2], s30[2], d; const float eps = 1e-6f; - const float eps_sq = eps * eps; + const float endpoint_min = -endpoint_bias; + const float endpoint_max = endpoint_bias + 1.0f; sub_v2_v2v2(s10, v1, v0); sub_v2_v2v2(s32, v3, v2); @@ -804,8 +947,8 @@ int isect_seg_seg_v2_point( u = cross_v2v2(s30, s32) / d; v = cross_v2v2(s10, s30) / d; - if ((u >= -eps && u <= 1.0f + eps) && - (v >= -eps && v <= 1.0f + eps)) + if ((u >= endpoint_min && u <= endpoint_max) && + (v >= endpoint_min && v <= endpoint_max)) { /* intersection */ float vi_test[2]; @@ -824,7 +967,7 @@ int isect_seg_seg_v2_point( sub_v2_v2v2(s_vi_v2, vi_test, v2); v = (dot_v2v2(s32, s_vi_v2) / dot_v2v2(s32, s32)); #endif - if (v >= -eps && v <= 1.0f + eps) { + if (v >= endpoint_min && v <= endpoint_max) { copy_v2_v2(r_vi, vi_test); return 1; } @@ -842,7 +985,7 @@ int isect_seg_seg_v2_point( float u_a, u_b; if (equals_v2v2(v0, v1)) { - if (len_squared_v2v2(v2, v3) > eps_sq) { + if (len_squared_v2v2(v2, v3) > SQUARE(eps)) { /* use non-point segment as basis */ SWAP(const float *, v0, v2); SWAP(const float *, v1, v3); @@ -869,7 +1012,7 @@ int isect_seg_seg_v2_point( if (u_a > u_b) SWAP(float, u_a, u_b); - if (u_a > 1.0f + eps || u_b < -eps) { + if (u_a > endpoint_max || u_b < endpoint_min) { /* non-overlapping segments */ return -1; } @@ -885,6 +1028,15 @@ int isect_seg_seg_v2_point( } } +int isect_seg_seg_v2_point( + const float v0[2], const float v1[2], + const float v2[2], const float v3[2], + float r_vi[2]) +{ + const float endpoint_bias = 1e-6f; + return isect_seg_seg_v2_point_ex(v0, v1, v2, v3, endpoint_bias, r_vi); +} + bool isect_seg_seg_v2_simple(const float v1[2], const float v2[2], const float v3[2], const float v4[2]) { #define CCW(A, B, C) \ @@ -1842,7 +1994,7 @@ bool isect_tri_tri_epsilon_v3( (range[0].max < range[1].min)) == 0) { if (r_i1 && r_i2) { - project_plane_v3_v3v3(plane_co, plane_co, plane_no); + project_plane_normalized_v3_v3v3(plane_co, plane_co, plane_no); madd_v3_v3v3fl(r_i1, plane_co, plane_no, max_ff(range[0].min, range[1].min)); madd_v3_v3v3fl(r_i2, plane_co, plane_no, min_ff(range[0].max, range[1].max)); } @@ -2323,222 +2475,32 @@ bool isect_ray_aabb_v3( return true; } -void dist_squared_ray_to_aabb_v3_precalc( - struct NearestRayToAABB_Precalc *data, - const float ray_origin[3], const float ray_direction[3]) -{ - float dir_sq[3]; - - for (int i = 0; i < 3; i++) { - data->ray_origin[i] = ray_origin[i]; - data->ray_direction[i] = ray_direction[i]; - data->ray_inv_dir[i] = (data->ray_direction[i] != 0.0f) ? (1.0f / data->ray_direction[i]) : FLT_MAX; - /* It has to be a function of `ray_inv_dir`, - * since the division of 1 by 0.0f, can be -inf or +inf */ - data->sign[i] = (data->ray_inv_dir[i] < 0.0f); - - dir_sq[i] = SQUARE(data->ray_direction[i]); - } - - /* `diag_sq` Length square of each face diagonal */ - float diag_sq[3] = { - dir_sq[1] + dir_sq[2], - dir_sq[0] + dir_sq[2], - dir_sq[0] + dir_sq[1], - }; - data->idiag_sq[0] = (diag_sq[0] > FLT_EPSILON) ? (1.0f / diag_sq[0]) : FLT_MAX; - data->idiag_sq[1] = (diag_sq[1] > FLT_EPSILON) ? (1.0f / diag_sq[1]) : FLT_MAX; - data->idiag_sq[2] = (diag_sq[2] > FLT_EPSILON) ? (1.0f / diag_sq[2]) : FLT_MAX; - - data->cdot_axis[0] = data->ray_direction[0] * data->idiag_sq[0]; - data->cdot_axis[1] = data->ray_direction[1] * data->idiag_sq[1]; - data->cdot_axis[2] = data->ray_direction[2] * data->idiag_sq[2]; -} - -/** - * Returns the squared distance from a ray to a bound-box `AABB`. - * It is based on `fast_ray_nearest_hit` solution to obtain - * the coordinates of the nearest edge of Bound Box to the ray +/* + * Test a bounding box (AABB) for ray intersection + * assumes the ray is already local to the boundbox space */ -float dist_squared_ray_to_aabb_v3( - const struct NearestRayToAABB_Precalc *data, +bool isect_ray_aabb_v3_simple( + const float orig[3], const float dir[3], const float bb_min[3], const float bb_max[3], - bool r_axis_closest[3]) -{ - /* `tmin` is a vector that has the smaller distances to each of the - * infinite planes of the `AABB` faces (hit in nearest face X plane, - * nearest face Y plane and nearest face Z plane) */ - float local_bvmin[3], local_bvmax[3]; - - if (data->sign[0] == 0) { - local_bvmin[0] = bb_min[0] - data->ray_origin[0]; - local_bvmax[0] = bb_max[0] - data->ray_origin[0]; - } - else { - local_bvmin[0] = bb_max[0] - data->ray_origin[0]; - local_bvmax[0] = bb_min[0] - data->ray_origin[0]; - } - - if (data->sign[1] == 0) { - local_bvmin[1] = bb_min[1] - data->ray_origin[1]; - local_bvmax[1] = bb_max[1] - data->ray_origin[1]; - } - else { - local_bvmin[1] = bb_max[1] - data->ray_origin[1]; - local_bvmax[1] = bb_min[1] - data->ray_origin[1]; - } - - if (data->sign[2] == 0) { - local_bvmin[2] = bb_min[2] - data->ray_origin[2]; - local_bvmax[2] = bb_max[2] - data->ray_origin[2]; - } - else { - local_bvmin[2] = bb_max[2] - data->ray_origin[2]; - local_bvmax[2] = bb_min[2] - data->ray_origin[2]; - } - - const float tmin[3] = { - local_bvmin[0] * data->ray_inv_dir[0], - local_bvmin[1] * data->ray_inv_dir[1], - local_bvmin[2] * data->ray_inv_dir[2], - }; - - /* `tmax` is a vector that has the longer distances to each of the - * infinite planes of the `AABB` faces (hit in farthest face X plane, - * farthest face Y plane and farthest face Z plane) */ - const float tmax[3] = { - local_bvmax[0] * data->ray_inv_dir[0], - local_bvmax[1] * data->ray_inv_dir[1], - local_bvmax[2] * data->ray_inv_dir[2], - }; - /* `v1` and `v3` is be the coordinates of the nearest `AABB` edge to the ray*/ - float v1[3], v2[3]; - /* `rtmin` is the highest value of the smaller distances. == max_axis_v3(tmin) - * `rtmax` is the lowest value of longer distances. == min_axis_v3(tmax)*/ - float rtmin, rtmax, mul, rdist; - /* `main_axis` is the axis equivalent to edge close to the ray */ - int main_axis; - - r_axis_closest[0] = false; - r_axis_closest[1] = false; - r_axis_closest[2] = false; - - /* *** min_axis_v3(tmax) *** */ - if ((tmax[0] <= tmax[1]) && (tmax[0] <= tmax[2])) { - // printf("# Hit in X %s\n", data->sign[0] ? "min", "max"); - rtmax = tmax[0]; - v1[0] = v2[0] = local_bvmax[0]; - mul = local_bvmax[0] * data->ray_direction[0]; - main_axis = 3; - r_axis_closest[0] = data->sign[0]; - } - else if ((tmax[1] <= tmax[0]) && (tmax[1] <= tmax[2])) { - // printf("# Hit in Y %s\n", data->sign[1] ? "min", "max"); - rtmax = tmax[1]; - v1[1] = v2[1] = local_bvmax[1]; - mul = local_bvmax[1] * data->ray_direction[1]; - main_axis = 2; - r_axis_closest[1] = data->sign[1]; - } - else { - // printf("# Hit in Z %s\n", data->sign[2] ? "min", "max"); - rtmax = tmax[2]; - v1[2] = v2[2] = local_bvmax[2]; - mul = local_bvmax[2] * data->ray_direction[2]; - main_axis = 1; - r_axis_closest[2] = data->sign[2]; - } - - /* *** max_axis_v3(tmin) *** */ - if ((tmin[0] >= tmin[1]) && (tmin[0] >= tmin[2])) { - // printf("# To X %s\n", data->sign[0] ? "max", "min"); - rtmin = tmin[0]; - v1[0] = v2[0] = local_bvmin[0]; - mul += local_bvmin[0] * data->ray_direction[0]; - main_axis -= 3; - r_axis_closest[0] = !data->sign[0]; - } - else if ((tmin[1] >= tmin[0]) && (tmin[1] >= tmin[2])) { - // printf("# To Y %s\n", data->sign[1] ? "max", "min"); - rtmin = tmin[1]; - v1[1] = v2[1] = local_bvmin[1]; - mul += local_bvmin[1] * data->ray_direction[1]; - main_axis -= 1; - r_axis_closest[1] = !data->sign[1]; - } - else { - // printf("# To Z %s\n", data->sign[2] ? "max", "min"); - rtmin = tmin[2]; - v1[2] = v2[2] = local_bvmin[2]; - mul += local_bvmin[2] * data->ray_direction[2]; - main_axis -= 2; - r_axis_closest[2] = !data->sign[2]; - } - /* *** end min/max axis *** */ - - - /* `if rtmax < 0`, the whole `AABB` is behing us */ - if ((rtmax < 0.0f) && (rtmin < 0.0f)) { - return FLT_MAX; - } - - if (main_axis < 0) { - main_axis += 3; - } - - if (data->sign[main_axis] == 0) { - v1[main_axis] = local_bvmin[main_axis]; - v2[main_axis] = local_bvmax[main_axis]; - } - else { - v1[main_axis] = local_bvmax[main_axis]; - v2[main_axis] = local_bvmin[main_axis]; - } - - /* if rtmin < rtmax, ray intersect `AABB` */ - if (rtmin <= rtmax) { - const float proj = rtmin * data->ray_direction[main_axis]; - rdist = 0.0f; - r_axis_closest[main_axis] = (proj - v1[main_axis]) < (v2[main_axis] - proj); - } + float *tmin, float *tmax) +{ + double t[7]; + float hit_dist[2]; + t[1] = (double)(bb_min[0] - orig[0]) / dir[0]; + t[2] = (double)(bb_max[0] - orig[0]) / dir[0]; + t[3] = (double)(bb_min[1] - orig[1]) / dir[1]; + t[4] = (double)(bb_max[1] - orig[1]) / dir[1]; + t[5] = (double)(bb_min[2] - orig[2]) / dir[2]; + t[6] = (double)(bb_max[2] - orig[2]) / dir[2]; + hit_dist[0] = (float)fmax(fmax(fmin(t[1], t[2]), fmin(t[3], t[4])), fmin(t[5], t[6])); + hit_dist[1] = (float)fmin(fmin(fmax(t[1], t[2]), fmax(t[3], t[4])), fmax(t[5], t[6])); + if ((hit_dist[1] < 0 || hit_dist[0] > hit_dist[1])) + return false; else { - /* `proj` equals to nearest point on the ray closest to the edge `v1 v2` of the `AABB`. */ - const float proj = mul * data->cdot_axis[main_axis]; - float depth; - if (v1[main_axis] > proj) { /* the nearest point to the ray is the point v1 */ - /* `depth` is equivalent the distance from the origin to the point v1, - * Here's a faster way to calculate the dot product of v1 and ray - * (depth = dot_v3v3(v1, data->ray.direction))*/ - depth = mul + data->ray_direction[main_axis] * v1[main_axis]; - rdist = len_squared_v3(v1) - SQUARE(depth); - r_axis_closest[main_axis] = true; - } - else if (v2[main_axis] < proj) { /* the nearest point of the ray is the point v2 */ - depth = mul + data->ray_direction[main_axis] * v2[main_axis]; - rdist = len_squared_v3(v2) - SQUARE(depth); - r_axis_closest[main_axis] = false; - } - else { /* the nearest point of the ray is on the edge of the `AABB`. */ - float v[2]; - mul *= data->idiag_sq[main_axis]; - if (main_axis == 0) { - v[0] = (mul * data->ray_direction[1]) - v1[1]; - v[1] = (mul * data->ray_direction[2]) - v1[2]; - } - else if (main_axis == 1) { - v[0] = (mul * data->ray_direction[0]) - v1[0]; - v[1] = (mul * data->ray_direction[2]) - v1[2]; - } - else { - v[0] = (mul * data->ray_direction[0]) - v1[0]; - v[1] = (mul * data->ray_direction[1]) - v1[1]; - } - rdist = len_squared_v2(v); - r_axis_closest[main_axis] = (proj - v1[main_axis]) < (v2[main_axis] - proj); - } + if (tmin) *tmin = hit_dist[0]; + if (tmax) *tmax = hit_dist[1]; + return true; } - - return rdist; } /* find closest point to p on line through (l1, l2) and return lambda, @@ -2964,7 +2926,15 @@ static bool barycentric_weights(const float v1[3], const float v2[3], const floa } } -void interp_weights_face_v3(float w[4], const float v1[3], const float v2[3], const float v3[3], const float v4[3], const float co[3]) +void interp_weights_tri_v3(float w[3], const float v1[3], const float v2[3], const float v3[3], const float co[3]) +{ + float n[3]; + + normal_tri_v3(n, v1, v2, v3); + barycentric_weights(v1, v2, v3, co, n, w); +} + +void interp_weights_quad_v3(float w[4], const float v1[3], const float v2[3], const float v3[3], const float v4[3], const float co[3]) { float w2[3]; @@ -2977,7 +2947,7 @@ void interp_weights_face_v3(float w[4], const float v1[3], const float v2[3], co w[1] = 1.0f; else if (equals_v3v3(co, v3)) w[2] = 1.0f; - else if (v4 && equals_v3v3(co, v4)) + else if (equals_v3v3(co, v4)) w[3] = 1.0f; else { /* otherwise compute barycentric interpolation weights */ @@ -2985,35 +2955,24 @@ void interp_weights_face_v3(float w[4], const float v1[3], const float v2[3], co bool degenerate; sub_v3_v3v3(n1, v1, v3); - if (v4) { - sub_v3_v3v3(n2, v2, v4); - } - else { - sub_v3_v3v3(n2, v2, v3); - } + sub_v3_v3v3(n2, v2, v4); cross_v3_v3v3(n, n1, n2); - /* OpenGL seems to split this way, so we do too */ - if (v4) { - degenerate = barycentric_weights(v1, v2, v4, co, n, w); - SWAP(float, w[2], w[3]); - - if (degenerate || (w[0] < 0.0f)) { - /* if w[1] is negative, co is on the other side of the v1-v3 edge, - * so we interpolate using the other triangle */ - degenerate = barycentric_weights(v2, v3, v4, co, n, w2); - - if (!degenerate) { - w[0] = 0.0f; - w[1] = w2[0]; - w[2] = w2[1]; - w[3] = w2[2]; - } + degenerate = barycentric_weights(v1, v2, v4, co, n, w); + SWAP(float, w[2], w[3]); + + if (degenerate || (w[0] < 0.0f)) { + /* if w[1] is negative, co is on the other side of the v1-v3 edge, + * so we interpolate using the other triangle */ + degenerate = barycentric_weights(v2, v3, v4, co, n, w2); + + if (!degenerate) { + w[0] = 0.0f; + w[1] = w2[0]; + w[2] = w2[1]; + w[3] = w2[2]; } } - else { - barycentric_weights(v1, v2, v3, co, n, w); - } } } @@ -3058,6 +3017,9 @@ bool barycentric_coords_v2(const float v1[2], const float v2[2], const float v3[ /** * \note: using #cross_tri_v2 means locations outside the triangle are correctly weighted + * + * \note This is *exactly* the same calculation as #resolve_tri_uv_v2, + * although it has double precision and is used for texture baking, so keep both. */ void barycentric_weights_v2(const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3]) { @@ -3097,9 +3059,11 @@ void barycentric_weights_v2_persp(const float v1[4], const float v2[4], const fl } } -/* same as #barycentric_weights_v2 but works with a quad, +/** + * same as #barycentric_weights_v2 but works with a quad, * note: untested for values outside the quad's bounds - * this is #interp_weights_poly_v2 expanded for quads only */ + * this is #interp_weights_poly_v2 expanded for quads only + */ void barycentric_weights_v2_quad(const float v1[2], const float v2[2], const float v3[2], const float v4[2], const float co[2], float w[4]) { @@ -3552,6 +3516,8 @@ void interp_cubic_v3(float x[3], float v[3], const float x1[3], const float v1[3 * Barycentric reverse * * Compute coordinates (u, v) for point \a st with respect to triangle (\a st0, \a st1, \a st2) + * + * \note same basic result as #barycentric_weights_v2, see it's comment for details. */ void resolve_tri_uv_v2(float r_uv[2], const float st[2], const float st0[2], const float st1[2], const float st2[2]) @@ -3763,6 +3729,9 @@ void interp_barycentric_tri_v3(float data[3][3], float u, float v, float res[3]) /***************************** View & Projection *****************************/ +/** + * Matches `glOrtho` result. + */ void orthographic_m4(float matrix[4][4], const float left, const float right, const float bottom, const float top, const float nearClip, const float farClip) { @@ -3783,6 +3752,9 @@ void orthographic_m4(float matrix[4][4], const float left, const float right, co matrix[3][2] = -(farClip + nearClip) / Zdelta; } +/** + * Matches `glFrustum` result. + */ void perspective_m4(float mat[4][4], const float left, const float right, const float bottom, const float top, const float nearClip, const float farClip) { @@ -3917,10 +3889,9 @@ void lookat_m4(float mat[4][4], float vx, float vy, float vz, float px, float py float sine, cosine, hyp, hyp1, dx, dy, dz; float mat1[4][4]; - unit_m4(mat); unit_m4(mat1); - rotate_m4(mat, 'Z', -twist); + axis_angle_to_mat4_single(mat, 'Z', -twist); dx = px - vx; dy = py - vy; @@ -4060,9 +4031,29 @@ void map_to_sphere(float *r_u, float *r_v, const float x, const float y, const f } } +void map_to_plane_v2_v3v3(float r_co[2], const float co[3], const float no[3]) +{ + float target[3] = {0.0f, 0.0f, 1.0f}; + float axis[3]; + + cross_v3_v3v3(axis, no, target); + normalize_v3(axis); + + map_to_plane_axis_angle_v2_v3v3fl(r_co, co, axis, angle_normalized_v3v3(no, target)); +} + +void map_to_plane_axis_angle_v2_v3v3fl(float r_co[2], const float co[3], const float axis[3], const float angle) +{ + float tmp[3]; + + rotate_normalized_v3_v3v3fl(tmp, co, axis, angle); + + copy_v2_v2(r_co, tmp); +} + /********************************* Normals **********************************/ -void accumulate_vertex_normals_tri( +void accumulate_vertex_normals_tri_v3( float n1[3], float n2[3], float n3[3], const float f_no[3], const float co1[3], const float co2[3], const float co3[3]) @@ -4096,7 +4087,7 @@ void accumulate_vertex_normals_tri( } } -void accumulate_vertex_normals( +void accumulate_vertex_normals_v3( float n1[3], float n2[3], float n3[3], float n4[3], const float f_no[3], const float co1[3], const float co2[3], const float co3[3], const float co4[3]) @@ -4140,7 +4131,7 @@ void accumulate_vertex_normals( /* Add weighted face normal component into normals of the face vertices. * Caller must pass pre-allocated vdiffs of nverts length. */ -void accumulate_vertex_normals_poly(float **vertnos, const float polyno[3], +void accumulate_vertex_normals_poly_v3(float **vertnos, const float polyno[3], const float **vertcos, float vdiffs[][3], const int nverts) { int i; @@ -4171,7 +4162,7 @@ void accumulate_vertex_normals_poly(float **vertnos, const float polyno[3], /********************************* Tangents **********************************/ -void tangent_from_uv( +void tangent_from_uv_v3( const float uv1[2], const float uv2[2], const float uv3[3], const float co1[3], const float co2[3], const float co3[3], const float n[3], @@ -4213,30 +4204,28 @@ void tangent_from_uv( /****************************** Vector Clouds ********************************/ /* vector clouds */ -/* void vcloud_estimate_transform(int list_size, float (*pos)[3], float *weight, float (*rpos)[3], float *rweight, - * float lloc[3], float rloc[3], float lrot[3][3], float lscale[3][3]) - * +/** * input - * ( - * int list_size - * 4 lists as pointer to array[list_size] - * 1. current pos array of 'new' positions - * 2. current weight array of 'new'weights (may be NULL pointer if you have no weights ) - * 3. reference rpos array of 'old' positions - * 4. reference rweight array of 'old'weights (may be NULL pointer if you have no weights ) - * ) + * + * \param list_size: 4 lists as pointer to array[list_size] + * \param pos: current pos array of 'new' positions + * \param weight: current weight array of 'new'weights (may be NULL pointer if you have no weights) + * \param rpos: Reference rpos array of 'old' positions + * \param rweight: Reference rweight array of 'old'weights (may be NULL pointer if you have no weights). + * * output - * ( - * float lloc[3] center of mass pos - * float rloc[3] center of mass rpos - * float lrot[3][3] rotation matrix - * float lscale[3][3] scale matrix + * + * \param lloc: Center of mass pos. + * \param rloc: Center of mass rpos. + * \param lrot: Rotation matrix. + * \param lscale: Scale matrix. + * * pointers may be NULL if not needed - * ) */ -void vcloud_estimate_transform(int list_size, float (*pos)[3], float *weight, float (*rpos)[3], float *rweight, - float lloc[3], float rloc[3], float lrot[3][3], float lscale[3][3]) +void vcloud_estimate_transform_v3( + const int list_size, const float (*pos)[3], const float *weight, const float (*rpos)[3], const float *rweight, + float lloc[3], float rloc[3], float lrot[3][3], float lscale[3][3]) { float accu_com[3] = {0.0f, 0.0f, 0.0f}, accu_rcom[3] = {0.0f, 0.0f, 0.0f}; float accu_weight = 0.0f, accu_rweight = 0.0f; diff --git a/source/blender/blenlib/intern/math_matrix.c b/source/blender/blenlib/intern/math_matrix.c index c9c61d5c878..d1a219c196a 100644 --- a/source/blender/blenlib/intern/math_matrix.c +++ b/source/blender/blenlib/intern/math_matrix.c @@ -1625,53 +1625,50 @@ void translate_m4(float mat[4][4], float Tx, float Ty, float Tz) mat[3][2] += (Tx * mat[0][2] + Ty * mat[1][2] + Tz * mat[2][2]); } +/** + * Rotate a matrix in-place. + * + * \note To create a new rotation matrix see: + * #axis_angle_to_mat4_single, #axis_angle_to_mat3_single, #angle_to_mat2 + * (axis & angle args are compatible). + */ void rotate_m4(float mat[4][4], const char axis, const float angle) { - int col; - float temp[4] = {0.0f, 0.0f, 0.0f, 0.0f}; - float cosine, sine; + const float angle_cos = cosf(angle); + const float angle_sin = sinf(angle); assert(axis >= 'X' && axis <= 'Z'); - cosine = cosf(angle); - sine = sinf(angle); switch (axis) { case 'X': - for (col = 0; col < 4; col++) - temp[col] = cosine * mat[1][col] + sine * mat[2][col]; - for (col = 0; col < 4; col++) { - mat[2][col] = -sine * mat[1][col] + cosine * mat[2][col]; - mat[1][col] = temp[col]; + for (int col = 0; col < 4; col++) { + float temp = angle_cos * mat[1][col] + angle_sin * mat[2][col]; + mat[2][col] = -angle_sin * mat[1][col] + angle_cos * mat[2][col]; + mat[1][col] = temp; } break; case 'Y': - for (col = 0; col < 4; col++) - temp[col] = cosine * mat[0][col] - sine * mat[2][col]; - for (col = 0; col < 4; col++) { - mat[2][col] = sine * mat[0][col] + cosine * mat[2][col]; - mat[0][col] = temp[col]; + for (int col = 0; col < 4; col++) { + float temp = angle_cos * mat[0][col] - angle_sin * mat[2][col]; + mat[2][col] = angle_sin * mat[0][col] + angle_cos * mat[2][col]; + mat[0][col] = temp; } break; case 'Z': - for (col = 0; col < 4; col++) - temp[col] = cosine * mat[0][col] + sine * mat[1][col]; - for (col = 0; col < 4; col++) { - mat[1][col] = -sine * mat[0][col] + cosine * mat[1][col]; - mat[0][col] = temp[col]; + for (int col = 0; col < 4; col++) { + float temp = angle_cos * mat[0][col] + angle_sin * mat[1][col]; + mat[1][col] = -angle_sin * mat[0][col] + angle_cos * mat[1][col]; + mat[0][col] = temp; } break; + default: + BLI_assert(0); + break; } } -void rotate_m2(float mat[2][2], const float angle) -{ - mat[0][0] = mat[1][1] = cosf(angle); - mat[0][1] = sinf(angle); - mat[1][0] = -mat[0][1]; -} - /** * Scale or rotate around a pivot point, * a convenience function to avoid having to do inline. @@ -1744,16 +1741,16 @@ void blend_m4_m4m4(float out[4][4], float dst[4][4], float src[4][4], const floa /** * A polar-decomposition-based interpolation between matrix A and matrix B. * - * \note This code is about five times slower as the 'naive' interpolation done by \a blend_m3_m3m3 - * (it typically remains below 2 usec on an average i74700, while \a blend_m3_m3m3 remains below 0.4 usec). + * \note This code is about five times slower as the 'naive' interpolation done by #blend_m3_m3m3 + * (it typically remains below 2 usec on an average i74700, while #blend_m3_m3m3 remains below 0.4 usec). * However, it gives expected results even with non-uniformaly scaled matrices, see T46418 for an example. * * Based on "Matrix Animation and Polar Decomposition", by Ken Shoemake & Tom Duff * - * @return R the interpolated matrix. - * @param A the intput matrix which is totally effective with \a t = 0.0. - * @param B the intput matrix which is totally effective with \a t = 1.0. - * @param t the interpolation factor. + * \param R: Resulting interpolated matrix. + * \param A: Input matrix which is totally effective with `t = 0.0`. + * \param B: Input matrix which is totally effective with `t = 1.0`. + * \param t: Interpolation factor. */ void interp_m3_m3m3(float R[3][3], float A[3][3], float B[3][3], const float t) { @@ -1783,12 +1780,12 @@ void interp_m3_m3m3(float R[3][3], float A[3][3], float B[3][3], const float t) } /** - * Complete transform matrix interpolation, based on polar-decomposition-based interpolation from interp_m3_m3m3. + * Complete transform matrix interpolation, based on polar-decomposition-based interpolation from #interp_m3_m3m3. * - * @return R the interpolated matrix. - * @param A the intput matrix which is totally effective with \a t = 0.0. - * @param B the intput matrix which is totally effective with \a t = 1.0. - * @param t the interpolation factor. + * \param R: Resulting interpolated matrix. + * \param A: Input matrix which is totally effective with `t = 0.0`. + * \param B: Input matrix which is totally effective with `t = 1.0`. + * \param t: Interpolation factor. */ void interp_m4_m4m4(float R[4][4], float A[4][4], float B[4][4], const float t) { diff --git a/source/blender/blenlib/intern/math_rotation.c b/source/blender/blenlib/intern/math_rotation.c index b285a74b8ac..23bd5e60e22 100644 --- a/source/blender/blenlib/intern/math_rotation.c +++ b/source/blender/blenlib/intern/math_rotation.c @@ -84,8 +84,6 @@ void mul_qt_qtqt(float q[4], const float q1[4], const float q2[4]) * \note: * Assumes a unit quaternion? * - * \note: multiplying by 3x3 matrix is ~25% faster. - * * in fact not, but you may want to use a unit quat, read on... * * Shortcut for 'q v q*' when \a v is actually a quaternion. @@ -98,6 +96,8 @@ void mul_qt_qtqt(float q[4], const float q1[4], const float q2[4]) * * For people used to python mathutils, its like: * def mul_qt_v3(q, v): (q * Quaternion((0.0, v[0], v[1], v[2])) * q.conjugated())[1:] + * + * \note: multiplying by 3x3 matrix is ~25% faster. */ void mul_qt_v3(const float q[4], float v[3]) { @@ -1009,6 +1009,13 @@ void mat4_to_axis_angle(float axis[3], float *angle, float mat[4][4]) quat_to_axis_angle(axis, angle, q); } +void axis_angle_to_mat4_single(float mat[4][4], const char axis, const float angle) +{ + float mat3[3][3]; + axis_angle_to_mat3_single(mat3, axis, angle); + copy_m4_m3(mat, mat3); +} + /* rotation matrix from a single axis */ void axis_angle_to_mat3_single(float mat[3][3], const char axis, const float angle) { @@ -2140,38 +2147,37 @@ BLI_INLINE int _axis_signed(const int axis) return (axis < 3) ? axis : axis - 3; } -/* +/** * Each argument us an axis in ['X', 'Y', 'Z', '-X', '-Y', '-Z'] * where the first 2 are a source and the second 2 are the target. */ -int mat3_from_axis_conversion(int from_forward, int from_up, int to_forward, int to_up, - float r_mat[3][3]) +bool mat3_from_axis_conversion( + int src_forward, int src_up, int dst_forward, int dst_up, + float r_mat[3][3]) { // from functools import reduce int value; - unsigned int i; - if (from_forward == to_forward && from_up == to_up) { + if (src_forward == dst_forward && src_up == dst_up) { unit_m3(r_mat); return false; } - if ((_axis_signed(from_forward) == _axis_signed(from_up)) || - (_axis_signed(to_forward) == _axis_signed(to_up))) + if ((_axis_signed(src_forward) == _axis_signed(src_up)) || + (_axis_signed(dst_forward) == _axis_signed(dst_up))) { /* we could assert here! */ unit_m3(r_mat); return false; } - value = ((from_forward << (0 * 3)) | - (from_up << (1 * 3)) | - (to_forward << (2 * 3)) | - (to_up << (3 * 3))); + value = ((src_forward << (0 * 3)) | + (src_up << (1 * 3)) | + (dst_forward << (2 * 3)) | + (dst_up << (3 * 3))); - for (i = 0; i < (sizeof(_axis_convert_matrix) / sizeof(*_axis_convert_matrix)); i++) { - unsigned int j; - for (j = 0; j < (sizeof(*_axis_convert_lut) / sizeof(*_axis_convert_lut[0])); j++) { + for (uint i = 0; i < (sizeof(_axis_convert_matrix) / sizeof(*_axis_convert_matrix)); i++) { + for (uint j = 0; j < (sizeof(*_axis_convert_lut) / sizeof(*_axis_convert_lut[0])); j++) { if (_axis_convert_lut[i][j] == value) { copy_m3_m3(r_mat, _axis_convert_matrix[i]); return true; @@ -2182,3 +2188,27 @@ int mat3_from_axis_conversion(int from_forward, int from_up, int to_forward, int // BLI_assert(0); return false; } + +/** + * Use when the second axis can be guessed. + */ +bool mat3_from_axis_conversion_single( + int src_axis, int dst_axis, + float r_mat[3][3]) +{ + if (src_axis == dst_axis) { + unit_m3(r_mat); + return false; + } + + /* Pick predictable next axis. */ + int src_axis_next = (src_axis + 1) % 3; + int dst_axis_next = (dst_axis + 1) % 3; + + if ((src_axis < 3) != (dst_axis < 3)) { + /* Flip both axis so matrix sign remains positive. */ + dst_axis_next += 3; + } + + return mat3_from_axis_conversion(src_axis, src_axis_next, dst_axis, dst_axis_next, r_mat); +} diff --git a/source/blender/blenlib/intern/math_vector.c b/source/blender/blenlib/intern/math_vector.c index 95d5c9fde87..5f44c93e169 100644 --- a/source/blender/blenlib/intern/math_vector.c +++ b/source/blender/blenlib/intern/math_vector.c @@ -280,6 +280,16 @@ void mid_v3_v3v3v3v3(float v[3], const float v1[3], const float v2[3], const flo v[2] = (v1[2] + v2[2] + v3[2] + v4[2]) / 4.0f; } +void mid_v3_v3_array(float r[3], const float (*vec_arr)[3], const unsigned int nbr) +{ + const float factor = 1.0f / (float)nbr; + zero_v3(r); + + for (unsigned int i = 0; i < nbr; i++) { + madd_v3_v3fl(r, vec_arr[i], factor); + } +} + /** * Specialized function for calculating normals. * fastpath for: @@ -508,38 +518,27 @@ float angle_normalized_v2v2(const float v1[2], const float v2[2]) } /** - * angle between 2 vectors defined by 3 coords, about an axis. */ -float angle_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]) + * Angle between 2 vectors, about an axis (axis can be considered a plane). + */ +float angle_on_axis_v3v3_v3(const float v1[3], const float v2[3], const float axis[3]) { - float v1_proj[3], v2_proj[3], tproj[3]; - - sub_v3_v3v3(v1_proj, v1, v2); - sub_v3_v3v3(v2_proj, v3, v2); + float v1_proj[3], v2_proj[3]; /* project the vectors onto the axis */ - project_v3_v3v3(tproj, v1_proj, axis); - sub_v3_v3(v1_proj, tproj); - - project_v3_v3v3(tproj, v2_proj, axis); - sub_v3_v3(v2_proj, tproj); + project_plane_normalized_v3_v3v3(v1_proj, v1, axis); + project_plane_normalized_v3_v3v3(v2_proj, v2, axis); return angle_v3v3(v1_proj, v2_proj); } -float angle_signed_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]) +float angle_signed_on_axis_v3v3_v3(const float v1[3], const float v2[3], const float axis[3]) { float v1_proj[3], v2_proj[3], tproj[3]; float angle; - sub_v3_v3v3(v1_proj, v1, v2); - sub_v3_v3v3(v2_proj, v3, v2); - /* project the vectors onto the axis */ - project_v3_v3v3(tproj, v1_proj, axis); - sub_v3_v3(v1_proj, tproj); - - project_v3_v3v3(tproj, v2_proj, axis); - sub_v3_v3(v2_proj, tproj); + project_plane_normalized_v3_v3v3(v1_proj, v1, axis); + project_plane_normalized_v3_v3v3(v2_proj, v2, axis); angle = angle_v3v3(v1_proj, v2_proj); @@ -552,6 +551,29 @@ float angle_signed_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const return angle; } +/** + * Angle between 2 vectors defined by 3 coords, about an axis (axis can be considered a plane). + */ +float angle_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]) +{ + float vec1[3], vec2[3]; + + sub_v3_v3v3(vec1, v1, v2); + sub_v3_v3v3(vec2, v3, v2); + + return angle_on_axis_v3v3_v3(vec1, vec2, axis); +} + +float angle_signed_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]) +{ + float vec1[3], vec2[3]; + + sub_v3_v3v3(vec1, v1, v2); + sub_v3_v3v3(vec2, v3, v2); + + return angle_signed_on_axis_v3v3_v3(vec1, vec2, axis); +} + void angle_tri_v3(float angles[3], const float v1[3], const float v2[3], const float v3[3]) { float ed1[3], ed2[3], ed3[3]; @@ -630,6 +652,31 @@ void project_v3_v3v3(float out[3], const float p[3], const float v_proj[3]) } /** + * Project \a p onto a unit length \a v_proj + */ +void project_v2_v2v2_normalized(float out[2], const float p[2], const float v_proj[2]) +{ + BLI_ASSERT_UNIT_V2(v_proj); + const float mul = dot_v2v2(p, v_proj); + + out[0] = mul * v_proj[0]; + out[1] = mul * v_proj[1]; +} + +/** + * Project \a p onto a unit length \a v_proj + */ +void project_v3_v3v3_normalized(float out[3], const float p[3], const float v_proj[3]) +{ + BLI_ASSERT_UNIT_V3(v_proj); + const float mul = dot_v3v3(p, v_proj); + + out[0] = mul * v_proj[0]; + out[1] = mul * v_proj[1]; + out[2] = mul * v_proj[2]; +} + +/** * In this case plane is a 3D vector only (no 4th component). * * Projecting will make \a c a copy of \a v orthogonal to \a v_plane. @@ -659,6 +706,25 @@ void project_plane_v2_v2v2(float out[2], const float p[2], const float v_plane[2 out[1] = p[1] - (mul * v_plane[1]); } +void project_plane_normalized_v3_v3v3(float out[3], const float p[3], const float v_plane[3]) +{ + BLI_ASSERT_UNIT_V3(v_plane); + const float mul = dot_v3v3(p, v_plane); + + out[0] = p[0] - (mul * v_plane[0]); + out[1] = p[1] - (mul * v_plane[1]); + out[2] = p[2] - (mul * v_plane[2]); +} + +void project_plane_normalized_v2_v2v2(float out[2], const float p[2], const float v_plane[2]) +{ + BLI_ASSERT_UNIT_V2(v_plane); + const float mul = dot_v2v2(p, v_plane); + + out[0] = p[0] - (mul * v_plane[0]); + out[1] = p[1] - (mul * v_plane[1]); +} + /* project a vector on a plane defined by normal and a plane point p */ void project_v3_plane(float out[3], const float plane_no[3], const float plane_co[3]) { @@ -687,7 +753,19 @@ void bisect_v3_v3v3v3(float out[3], const float v1[3], const float v2[3], const /** * Returns a reflection vector from a vector and a normal vector - * reflect = vec - ((2 * DotVecs(vec, mirror)) * mirror) + * reflect = vec - ((2 * dot(vec, mirror)) * mirror). + * + * <pre> + * v + * + ^ + * \ | + * \| + * + normal: axis of reflection + * / + * / + * + + * out: result (negate for a 'bounce'). + * </pre> */ void reflect_v3_v3v3(float out[3], const float v[3], const float normal[3]) { diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c index e9fb77f6302..ee5e8651bd3 100644 --- a/source/blender/blenlib/intern/math_vector_inline.c +++ b/source/blender/blenlib/intern/math_vector_inline.c @@ -479,7 +479,18 @@ MINLINE void mul_v2_v2_ccw(float r[2], const float mat[2], const float vec[2]) r[1] = mat[1] * vec[0] + (+mat[0]) * vec[1]; } -/* note: could add a matrix inline */ +/** + * Convenience function to get the projected depth of a position. + * This avoids creating a temporary 4D vector and multiplying it - only for the 4th component. + * + * Matches logic for: + * + * \code{.c} + * float co_4d[4] = {co[0], co[1], co[2], 1.0}; + * mul_m4_v4(mat, co_4d); + * return co_4d[3]; + * \endcode + */ MINLINE float mul_project_m4_v3_zfac(float mat[4][4], const float co[3]) { return (mat[0][3] * co[0]) + diff --git a/source/blender/blenlib/intern/noise.c b/source/blender/blenlib/intern/noise.c index f834c5b4c74..83012694ac0 100644 --- a/source/blender/blenlib/intern/noise.c +++ b/source/blender/blenlib/intern/noise.c @@ -1394,6 +1394,11 @@ static float voronoi_CrS(float x, float y, float z) /* returns unsigned cellnoise */ static float cellNoiseU(float x, float y, float z) { + /* avoid precision issues on unit coordinates */ + x = (x + 0.000001f) * 1.00001f; + y = (y + 0.000001f) * 1.00001f; + z = (z + 0.000001f) * 1.00001f; + int xi = (int)(floor(x)); int yi = (int)(floor(y)); int zi = (int)(floor(z)); @@ -1411,6 +1416,11 @@ float cellNoise(float x, float y, float z) /* returns a vector/point/color in ca, using point hasharray directly */ void cellNoiseV(float x, float y, float z, float ca[3]) { + /* avoid precision issues on unit coordinates */ + x = (x + 0.000001f) * 1.00001f; + y = (y + 0.000001f) * 1.00001f; + z = (z + 0.000001f) * 1.00001f; + int xi = (int)(floor(x)); int yi = (int)(floor(y)); int zi = (int)(floor(z)); diff --git a/source/blender/blenlib/intern/path_util.c b/source/blender/blenlib/intern/path_util.c index f0d0bd00dea..4b3a74d02ae 100644 --- a/source/blender/blenlib/intern/path_util.c +++ b/source/blender/blenlib/intern/path_util.c @@ -63,9 +63,6 @@ #include "MEM_guardedalloc.h" -/* local */ -#define UNIQUE_NAME_MAX 128 - /* Declarations */ #ifdef WIN32 @@ -147,162 +144,6 @@ void BLI_stringenc(char *string, const char *head, const char *tail, unsigned sh sprintf(string, "%s%.*d%s", head, numlen, MAX2(0, pic), tail); } -/** - * Looks for a numeric suffix preceded by delim character on the end of - * name, puts preceding part into *left and value of suffix into *nr. - * Returns the length of *left. - * - * Foo.001 -> "Foo", 1 - * Returning the length of "Foo" - * - * \param left Where to return copy of part preceding delim - * \param nr Where to return value of numeric suffix - * \param name String to split - * \param delim Delimiter character - * \return Length of \a left - */ -int BLI_split_name_num(char *left, int *nr, const char *name, const char delim) -{ - const int name_len = strlen(name); - - *nr = 0; - memcpy(left, name, (name_len + 1) * sizeof(char)); - - /* name doesn't end with a delimiter "foo." */ - if ((name_len > 1 && name[name_len - 1] == delim) == 0) { - int a = name_len; - while (a--) { - if (name[a] == delim) { - left[a] = '\0'; /* truncate left part here */ - *nr = atol(name + a + 1); - /* casting down to an int, can overflow for large numbers */ - if (*nr < 0) - *nr = 0; - return a; - } - else if (isdigit(name[a]) == 0) { - /* non-numeric suffix - give up */ - break; - } - } - } - - return name_len; -} - -/** - * Ensures name is unique (according to criteria specified by caller in unique_check callback), - * incrementing its numeric suffix as necessary. Returns true if name had to be adjusted. - * - * \param unique_check Return true if name is not unique - * \param arg Additional arg to unique_check--meaning is up to caller - * \param defname To initialize name if latter is empty - * \param delim Delimits numeric suffix in name - * \param name Name to be ensured unique - * \param name_len Maximum length of name area - * \return true if there if the name was changed - */ -bool BLI_uniquename_cb(bool (*unique_check)(void *arg, const char *name), - void *arg, const char *defname, char delim, char *name, int name_len) -{ - if (name[0] == '\0') { - BLI_strncpy(name, defname, name_len); - } - - if (unique_check(arg, name)) { - char numstr[16]; - char tempname[UNIQUE_NAME_MAX]; - char left[UNIQUE_NAME_MAX]; - int number; - int len = BLI_split_name_num(left, &number, name, delim); - do { - /* add 1 to account for \0 */ - const int numlen = BLI_snprintf(numstr, sizeof(numstr), "%c%03d", delim, ++number) + 1; - - /* highly unlikely the string only has enough room for the number - * but support anyway */ - if ((len == 0) || (numlen >= name_len)) { - /* number is know not to be utf-8 */ - BLI_strncpy(tempname, numstr, name_len); - } - else { - char *tempname_buf; - tempname_buf = tempname + BLI_strncpy_utf8_rlen(tempname, left, name_len - numlen); - memcpy(tempname_buf, numstr, numlen); - } - } while (unique_check(arg, tempname)); - - BLI_strncpy(name, tempname, name_len); - - return true; - } - - return false; -} - -/* little helper macro for BLI_uniquename */ -#ifndef GIVE_STRADDR -# define GIVE_STRADDR(data, offset) ( ((char *)data) + offset) -#endif - -/* Generic function to set a unique name. It is only designed to be used in situations - * where the name is part of the struct, and also that the name is at most UNIQUE_NAME_MAX chars long. - * - * For places where this is used, see constraint.c for example... - * - * name_offs: should be calculated using offsetof(structname, membername) macro from stddef.h - * len: maximum length of string (to prevent overflows, etc.) - * defname: the name that should be used by default if none is specified already - * delim: the character which acts as a delimiter between parts of the name - */ -static bool uniquename_find_dupe(ListBase *list, void *vlink, const char *name, int name_offs) -{ - Link *link; - - for (link = list->first; link; link = link->next) { - if (link != vlink) { - if (STREQ(GIVE_STRADDR(link, name_offs), name)) { - return true; - } - } - } - - return false; -} - -static bool uniquename_unique_check(void *arg, const char *name) -{ - struct {ListBase *lb; void *vlink; int name_offs; } *data = arg; - return uniquename_find_dupe(data->lb, data->vlink, name, data->name_offs); -} - -/** - * Ensures that the specified block has a unique name within the containing list, - * incrementing its numeric suffix as necessary. Returns true if name had to be adjusted. - * - * \param list List containing the block - * \param vlink The block to check the name for - * \param defname To initialize block name if latter is empty - * \param delim Delimits numeric suffix in name - * \param name_offs Offset of name within block structure - * \param name_len Maximum length of name area - */ -bool BLI_uniquename(ListBase *list, void *vlink, const char *defname, char delim, int name_offs, int name_len) -{ - struct {ListBase *lb; void *vlink; int name_offs; } data; - data.lb = list; - data.vlink = vlink; - data.name_offs = name_offs; - - assert((name_len > 1) && (name_len <= UNIQUE_NAME_MAX)); - - /* See if we are given an empty string */ - if (ELEM(NULL, vlink, defname)) - return false; - - return BLI_uniquename_cb(uniquename_unique_check, &data, defname, delim, GIVE_STRADDR(vlink, name_offs), name_len); -} - static int BLI_path_unc_prefix_len(const char *path); /* defined below in same file */ /* ******************** string encoding ***************** */ @@ -1326,52 +1167,16 @@ bool BLI_path_program_search( } /** - * Copies into *last the part of *dir following the second-last slash. - */ -void BLI_getlastdir(const char *dir, char *last, const size_t maxlen) -{ - const char *s = dir; - const char *lslash = NULL; - const char *prevslash = NULL; - while (*s) { - if ((*s == '\\') || (*s == '/')) { - prevslash = lslash; - lslash = s; - } - s++; - } - if (prevslash) { - BLI_strncpy(last, prevslash + 1, maxlen); - } - else { - BLI_strncpy(last, dir, maxlen); - } -} - - -/** * Sets the specified environment variable to the specified value, * and clears it if val == NULL. */ void BLI_setenv(const char *env, const char *val) { /* free windows */ -#if (defined(WIN32) || defined(WIN64)) && defined(FREE_WINDOWS) - char *envstr; - if (val) - envstr = BLI_sprintfN("%s=%s", env, val); - else - envstr = BLI_sprintfN("%s=", env); - - putenv(envstr); - MEM_freeN(envstr); - - /* non-free windows */ -#elif (defined(WIN32) || defined(WIN64)) /* not free windows */ +#if (defined(WIN32) || defined(WIN64)) uputenv(env, val); - #else /* linux/osx/bsd */ if (val) @@ -1417,14 +1222,16 @@ void BLI_make_exist(char *dir) /** * Ensures that the parent directory of *name exists. + * + * \return true on success (i.e. given path now exists on FS), false otherwise. */ -void BLI_make_existing_file(const char *name) +bool BLI_make_existing_file(const char *name) { char di[FILE_MAX]; BLI_split_dir_part(name, di, sizeof(di)); /* make if the dir doesn't exist */ - BLI_dir_create_recursive(di); + return BLI_dir_create_recursive(di); } /** @@ -1774,6 +1581,90 @@ void BLI_join_dirfile(char *__restrict dst, const size_t maxlen, const char *__r } /** + * Join multiple strings into a path, ensuring only a single path separator between each, + * and trailing slash is kept. + * + * \note If you want a trailing slash, add ``SEP_STR`` as the last path argument, + * duplicate slashes will be cleaned up. + */ +size_t BLI_path_join(char *__restrict dst, const size_t dst_len, const char *path, ...) +{ + if (UNLIKELY(dst_len == 0)) { + return 0; + } + const size_t dst_last = dst_len - 1; + size_t ofs = BLI_strncpy_rlen(dst, path, dst_len); + + if (ofs == dst_last) { + return ofs; + } + + /* remove trailing slashes, unless there are _only_ trailing slashes + * (allow "//" as the first argument). */ + bool has_trailing_slash = false; + if (ofs != 0) { + size_t len = ofs; + while ((len != 0) && ELEM(path[len - 1], SEP, ALTSEP)) { + len -= 1; + } + if (len != 0) { + ofs = len; + } + has_trailing_slash = (path[len] != '\0'); + } + + va_list args; + va_start(args, path); + while ((path = (const char *) va_arg(args, const char *))) { + has_trailing_slash = false; + const char *path_init = path; + while (ELEM(path[0], SEP, ALTSEP)) { + path++; + } + size_t len = strlen(path); + if (len != 0) { + while ((len != 0) && ELEM(path[len - 1], SEP, ALTSEP)) { + len -= 1; + } + + if (len != 0) { + /* the very first path may have a slash at the end */ + if (ofs && !ELEM(dst[ofs - 1], SEP, ALTSEP)) { + dst[ofs++] = SEP; + if (ofs == dst_last) { + break; + } + } + has_trailing_slash = (path[len] != '\0'); + if (ofs + len >= dst_last) { + len = dst_last - ofs; + } + memcpy(&dst[ofs], path, len); + ofs += len; + if (ofs == dst_last) { + break; + } + } + } + else { + has_trailing_slash = (path_init != path); + } + } + va_end(args); + + if (has_trailing_slash) { + if ((ofs != dst_last) && (ofs != 0) && (ELEM(dst[ofs - 1], SEP, ALTSEP) == 0)) { + dst[ofs++] = SEP; + } + } + + BLI_assert(ofs <= dst_last); + dst[ofs] = '\0'; + + return ofs; +} + +/** * like pythons os.path.basename() * * \return The pointer into \a path string immediately after last slash, @@ -1785,6 +1676,71 @@ const char *BLI_path_basename(const char *path) return filename ? filename + 1 : path; } +/** + * Get an element of the path at an index, eg: + * "/some/path/file.txt" where an index of... + * - 0 or -3: "some" + * - 1 or -2: "path" + * - 2 or -1: "file.txt" + * + * Ignores multiple slashes at any point in the path (including start/end). + */ +bool BLI_path_name_at_index(const char *path, const int index, int *r_offset, int *r_len) +{ + if (index >= 0) { + int index_step = 0; + int prev = -1; + int i = 0; + while (true) { + const char c = path[i]; + if (ELEM(c, SEP, ALTSEP, '\0')) { + if (prev + 1 != i) { + prev += 1; + if (index_step == index) { + *r_offset = prev; + *r_len = i - prev; + /* printf("!!! %d %d\n", start, end); */ + return true; + } + index_step += 1; + } + if (c == '\0') { + break; + } + prev = i; + } + i += 1; + } + return false; + } + else { + /* negative number, reverse where -1 is the last element */ + int index_step = -1; + int prev = strlen(path); + int i = prev - 1; + while (true) { + const char c = i >= 0 ? path[i] : '\0'; + if (ELEM(c, SEP, ALTSEP, '\0')) { + if (prev - 1 != i) { + i += 1; + if (index_step == index) { + *r_offset = i; + *r_len = prev - i; + return true; + } + index_step -= 1; + } + if (c == '\0') { + break; + } + prev = i; + } + i -= 1; + } + return false; + } +} + /* UNUSED */ #if 0 /** diff --git a/source/blender/blenlib/intern/polyfill2d.c b/source/blender/blenlib/intern/polyfill2d.c index 8d9881e4539..018e2f9be5a 100644 --- a/source/blender/blenlib/intern/polyfill2d.c +++ b/source/blender/blenlib/intern/polyfill2d.c @@ -21,8 +21,15 @@ /** \file blender/blenlib/intern/polyfill2d.c * \ingroup bli * - * A simple implementation of the ear cutting algorithm - * to triangulate simple polygons without holes. + * An ear clipping algorithm to triangulate single boundary polygons. + * + * Details: + * + * - The algorithm guarantees all triangles are assigned (number of coords - 2) + * and that triangles will have non-overlapping indices (even for degenerate geometry). + * - Self-intersections are considered degenerate (resulting triangles will overlap). + * - While multiple polygons aren't supported, holes can still be defined using *key-holes* + * (where the polygon doubles back on its self with *exactly* matching coordinates). * * \note * @@ -74,6 +81,12 @@ typedef signed char eSign; #ifdef USE_KDTREE /** + * Spatial optimization for point-in-triangle intersection checks. + * The simple version of this algorithm is ``O(n^2)`` complexity + * (every point needing to check the triangle defined by every other point), + * Using a binary-tree reduces the complexity to ``O(n log n)`` + * plus some overhead of creating the tree. + * * This is a single purpose KDTree based on BLI_kdtree with some modifications * to better suit polyfill2d. * @@ -92,24 +105,24 @@ typedef bool axis_t; /* use for sorting */ typedef struct KDTreeNode2D_head { - unsigned int neg, pos; - unsigned int index; + uint neg, pos; + uint index; } KDTreeNode2D_head; typedef struct KDTreeNode2D { - unsigned int neg, pos; - unsigned int index; + uint neg, pos; + uint index; axis_t axis; /* range is only (0-1) */ - unsigned short flag; - unsigned int parent; + ushort flag; + uint parent; } KDTreeNode2D; struct KDTree2D { KDTreeNode2D *nodes; const float (*coords)[2]; - unsigned int root; - unsigned int totnode; - unsigned int *nodes_map; /* index -> node lookup */ + uint root; + uint totnode; + uint *nodes_map; /* index -> node lookup */ }; struct KDRange2D { @@ -127,14 +140,14 @@ typedef struct PolyFill { struct PolyIndex *indices; /* vertex aligned */ const float (*coords)[2]; - unsigned int coords_tot; + uint coords_tot; #ifdef USE_CONVEX_SKIP - unsigned int coords_tot_concave; + uint coords_tot_concave; #endif /* A polygon with n vertices has a triangulation of n-2 triangles. */ - unsigned int (*tris)[3]; - unsigned int tris_tot; + uint (*tris)[3]; + uint tris_tot; #ifdef USE_KDTREE struct KDTree2D kdtree; @@ -145,7 +158,7 @@ typedef struct PolyFill { /* circular linklist */ typedef struct PolyIndex { struct PolyIndex *next, *prev; - unsigned int index; + uint index; eSign sign; } PolyIndex; @@ -199,7 +212,7 @@ static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float #ifdef USE_KDTREE -#define KDNODE_UNSET ((unsigned int)-1) +#define KDNODE_UNSET ((uint)-1) enum { KDNODE_FLAG_REMOVED = (1 << 0), @@ -207,7 +220,7 @@ enum { static void kdtree2d_new( struct KDTree2D *tree, - unsigned int tot, + uint tot, const float (*coords)[2]) { /* set by caller */ @@ -222,11 +235,11 @@ static void kdtree2d_new( */ static void kdtree2d_init( struct KDTree2D *tree, - const unsigned int coords_tot, + const uint coords_tot, const PolyIndex *indices) { KDTreeNode2D *node; - unsigned int i; + uint i; for (i = 0, node = tree->nodes; i < coords_tot; i++) { if (indices[i].sign != CONVEX) { @@ -238,15 +251,15 @@ static void kdtree2d_init( } } - BLI_assert(tree->totnode == (unsigned int)(node - tree->nodes)); + BLI_assert(tree->totnode == (uint)(node - tree->nodes)); } -static unsigned int kdtree2d_balance_recursive( - KDTreeNode2D *nodes, unsigned int totnode, axis_t axis, - const float (*coords)[2], const unsigned int ofs) +static uint kdtree2d_balance_recursive( + KDTreeNode2D *nodes, uint totnode, axis_t axis, + const float (*coords)[2], const uint ofs) { KDTreeNode2D *node; - unsigned int neg, pos, median, i, j; + uint neg, pos, median, i, j; if (totnode <= 0) { return KDNODE_UNSET; @@ -304,7 +317,7 @@ static void kdtree2d_balance( static void kdtree2d_init_mapping( struct KDTree2D *tree) { - unsigned int i; + uint i; KDTreeNode2D *node; for (i = 0, node = tree->nodes; i < tree->totnode; i++, node++) { @@ -325,9 +338,9 @@ static void kdtree2d_init_mapping( static void kdtree2d_node_remove( struct KDTree2D *tree, - unsigned int index) + uint index) { - unsigned int node_index = tree->nodes_map[index]; + uint node_index = tree->nodes_map[index]; KDTreeNode2D *node; if (node_index == KDNODE_UNSET) { @@ -349,7 +362,7 @@ static void kdtree2d_node_remove( { KDTreeNode2D *node_parent = &tree->nodes[node->parent]; - BLI_assert((unsigned int)(node - tree->nodes) == node_index); + BLI_assert((uint)(node - tree->nodes) == node_index); if (node_parent->neg == node_index) { node_parent->neg = KDNODE_UNSET; } @@ -370,7 +383,7 @@ static void kdtree2d_node_remove( static bool kdtree2d_isect_tri_recursive( const struct KDTree2D *tree, - const unsigned int tri_index[3], + const uint tri_index[3], const float *tri_coords[3], const float tri_center[2], const struct KDRange2D bounds[2], @@ -398,11 +411,11 @@ static bool kdtree2d_isect_tri_recursive( } #define KDTREE2D_ISECT_TRI_RECURSE_NEG \ - (((node->neg != KDNODE_UNSET) && (co[node->axis] > bounds[node->axis].min)) && \ + (((node->neg != KDNODE_UNSET) && (co[node->axis] >= bounds[node->axis].min)) && \ (kdtree2d_isect_tri_recursive(tree, tri_index, tri_coords, tri_center, bounds, \ &tree->nodes[node->neg]))) #define KDTREE2D_ISECT_TRI_RECURSE_POS \ - (((node->pos != KDNODE_UNSET) && (co[node->axis] < bounds[node->axis].max)) && \ + (((node->pos != KDNODE_UNSET) && (co[node->axis] <= bounds[node->axis].max)) && \ (kdtree2d_isect_tri_recursive(tree, tri_index, tri_coords, tri_center, bounds, \ &tree->nodes[node->pos]))) @@ -433,10 +446,10 @@ static bool kdtree2d_isect_tri_recursive( static bool kdtree2d_isect_tri( struct KDTree2D *tree, - const unsigned int ind[3]) + const uint ind[3]) { const float *vs[3]; - unsigned int i; + uint i; struct KDRange2D bounds[2] = { {FLT_MAX, -FLT_MAX}, {FLT_MAX, -FLT_MAX}, @@ -462,7 +475,7 @@ static bool kdtree2d_isect_tri( #endif /* USE_KDTREE */ -static unsigned int *pf_tri_add(PolyFill *pf) +static uint *pf_tri_add(PolyFill *pf) { return pf->tris[pf->tris_tot++]; } @@ -483,7 +496,7 @@ static void pf_coord_remove(PolyFill *pf, PolyIndex *pi) pf->indices = pi->next; } #ifdef DEBUG - pi->index = (unsigned int)-1; + pi->index = (uint)-1; pi->next = pi->prev = NULL; #endif @@ -581,7 +594,7 @@ static void pf_triangulate(PolyFill *pf) } if (pf->coords_tot == 3) { - unsigned int *tri = pf_tri_add(pf); + uint *tri = pf_tri_add(pf); pi_ear = pf->indices; tri[0] = pi_ear->index; pi_ear = pi_ear->next; tri[1] = pi_ear->index; pi_ear = pi_ear->next; @@ -614,10 +627,10 @@ static PolyIndex *pf_ear_tip_find( ) { /* localize */ - const unsigned int coords_tot = pf->coords_tot; + const uint coords_tot = pf->coords_tot; PolyIndex *pi_ear; - unsigned int i; + uint i; #ifdef USE_CLIP_EVEN pi_ear = pi_ear_init; @@ -675,7 +688,7 @@ static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip) #endif #if defined(USE_CONVEX_SKIP) && !defined(USE_KDTREE) - unsigned int coords_tot_concave_checked = 0; + uint coords_tot_concave_checked = 0; #endif @@ -684,13 +697,13 @@ static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip) #ifdef USE_CONVEX_SKIP_TEST /* check if counting is wrong */ { - unsigned int coords_tot_concave_test = 0; - unsigned int i = pf->coords_tot; - while (i--) { - if (coords_sign[indices[i]] != CONVEX) { + uint coords_tot_concave_test = 0; + PolyIndex *pi_iter = pi_ear_tip; + do { + if (pi_iter->sign != CONVEX) { coords_tot_concave_test += 1; } - } + } while ((pi_iter = pi_iter->next) != pi_ear_tip); BLI_assert(coords_tot_concave_test == pf->coords_tot_concave); } #endif @@ -707,7 +720,7 @@ static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip) #ifdef USE_KDTREE { - const unsigned int ind[3] = { + const uint ind[3] = { pi_ear_tip->index, pi_ear_tip->next->index, pi_ear_tip->prev->index}; @@ -758,7 +771,7 @@ static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip) static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip) { - unsigned int *tri = pf_tri_add(pf); + uint *tri = pf_tri_add(pf); tri[0] = pi_ear_tip->prev->index; tri[1] = pi_ear_tip->index; @@ -773,15 +786,15 @@ static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip) static void polyfill_prepare( PolyFill *pf, const float (*coords)[2], - const unsigned int coords_tot, + const uint coords_tot, int coords_sign, - unsigned int (*r_tris)[3], + uint (*r_tris)[3], PolyIndex *r_indices) { /* localize */ PolyIndex *indices = r_indices; - unsigned int i; + uint i; /* assign all polyfill members here */ pf->indices = r_indices; @@ -819,7 +832,7 @@ static void polyfill_prepare( } else { /* reversed */ - unsigned int n = coords_tot - 1; + uint n = coords_tot - 1; for (i = 0; i < coords_tot; i++) { indices[i].next = &indices[i + 1]; indices[i].prev = &indices[i - 1]; @@ -863,9 +876,9 @@ static void polyfill_calc( */ void BLI_polyfill_calc_arena( const float (*coords)[2], - const unsigned int coords_tot, + const uint coords_tot, const int coords_sign, - unsigned int (*r_tris)[3], + uint (*r_tris)[3], struct MemArena *arena) { @@ -919,9 +932,9 @@ void BLI_polyfill_calc_arena( */ void BLI_polyfill_calc( const float (*coords)[2], - const unsigned int coords_tot, + const uint coords_tot, const int coords_sign, - unsigned int (*r_tris)[3]) + uint (*r_tris)[3]) { PolyFill pf; PolyIndex *indices = BLI_array_alloca(indices, coords_tot); diff --git a/source/blender/blenlib/intern/polyfill2d_beautify.c b/source/blender/blenlib/intern/polyfill2d_beautify.c index 896177f436c..5f6fb8e6cd4 100644 --- a/source/blender/blenlib/intern/polyfill2d_beautify.c +++ b/source/blender/blenlib/intern/polyfill2d_beautify.c @@ -121,45 +121,53 @@ BLI_INLINE bool is_boundary_edge(unsigned int i_a, unsigned int i_b, const unsig * Assuming we have 2 triangles sharing an edge (2 - 4), * check if the edge running from (1 - 3) gives better results. * + * \param lock_degenerate: Use to avoid rotating out of a degenerate state. + * - When true, an existing zero area face on either side of the (2 - 4) split will return a positive value. + * - When false, the check must be non-biased towards either split direction. + * * \return (negative number means the edge can be rotated, lager == better). */ -float BLI_polyfill_beautify_quad_rotate_calc( - const float v1[2], const float v2[2], const float v3[2], const float v4[2]) +float BLI_polyfill_beautify_quad_rotate_calc_ex( + const float v1[2], const float v2[2], const float v3[2], const float v4[2], + const bool lock_degenerate) { /* not a loop (only to be able to break out) */ do { - bool is_zero_a, is_zero_b; - + /* Allow very small faces to be considered non-zero. */ + const float eps_zero_area = 1e-12f; const float area_2x_234 = cross_tri_v2(v2, v3, v4); const float area_2x_241 = cross_tri_v2(v2, v4, v1); const float area_2x_123 = cross_tri_v2(v1, v2, v3); const float area_2x_134 = cross_tri_v2(v1, v3, v4); - { - BLI_assert((ELEM(v1, v2, v3, v4) == false) && - (ELEM(v2, v1, v3, v4) == false) && - (ELEM(v3, v1, v2, v4) == false) && - (ELEM(v4, v1, v2, v3) == false)); - - is_zero_a = (fabsf(area_2x_234) <= FLT_EPSILON); - is_zero_b = (fabsf(area_2x_241) <= FLT_EPSILON); - - if (is_zero_a && is_zero_b) { - break; - } + BLI_assert((ELEM(v1, v2, v3, v4) == false) && + (ELEM(v2, v1, v3, v4) == false) && + (ELEM(v3, v1, v2, v4) == false) && + (ELEM(v4, v1, v2, v3) == false)); + /* + * Test for unusable (1-3) state. + * - Area sign flipping to check faces aren't going to point in opposite directions. + * - Area epsilon check that the one of the faces won't be zero area. + */ + if ((area_2x_123 >= 0.0f) != (area_2x_134 >= 0.0f)) { + break; } - - /* one of the tri's was degenerate, check we're not rotating - * into a different degenerate shape or flipping the face */ - if ((fabsf(area_2x_123) <= FLT_EPSILON) || (fabsf(area_2x_134) <= FLT_EPSILON)) { - /* one of the new rotations is degenerate */ + else if ((fabsf(area_2x_123) <= eps_zero_area) || (fabsf(area_2x_134) <= eps_zero_area)) { break; } - if ((area_2x_123 >= 0.0f) != (area_2x_134 >= 0.0f)) { - /* rotation would cause flipping */ - break; + /* Test for unusable (2-4) state (same as above). */ + if ((area_2x_234 >= 0.0f) != (area_2x_241 >= 0.0f)) { + if (lock_degenerate) { + break; + } + else { + return -FLT_MAX; /* always rotate */ + } + } + else if ((fabsf(area_2x_234) <= eps_zero_area) || (fabsf(area_2x_241) <= eps_zero_area)) { + return -FLT_MAX; /* always rotate */ } { diff --git a/source/blender/blenlib/intern/rct.c b/source/blender/blenlib/intern/rct.c index 9d5a4630f68..3adc6b30f6e 100644 --- a/source/blender/blenlib/intern/rct.c +++ b/source/blender/blenlib/intern/rct.c @@ -32,6 +32,7 @@ * A minimalist lib for functions doing stuff with rectangle structs. */ +#include <stdlib.h> #include <stdio.h> #include <math.h> @@ -41,6 +42,9 @@ #include "DNA_vec_types.h" #include "BLI_rect.h" +/* avoid including BLI_math */ +static void unit_m4(float m[4][4]); + /** * Determine if a rect is empty. An empty * rect is one with a zero (or negative) @@ -351,6 +355,22 @@ void BLI_rcti_init(rcti *rect, int xmin, int xmax, int ymin, int ymax) } } +void BLI_rctf_init_pt_radius(rctf *rect, const float xy[2], float size) +{ + rect->xmin = xy[0] - size; + rect->xmax = xy[0] + size; + rect->ymin = xy[1] - size; + rect->ymax = xy[1] + size; +} + +void BLI_rcti_init_pt_radius(rcti *rect, const int xy[2], int size) +{ + rect->xmin = xy[0] - size; + rect->xmax = xy[0] + size; + rect->ymin = xy[1] - size; + rect->ymax = xy[1] + size; +} + void BLI_rcti_init_minmax(rcti *rect) { rect->xmin = rect->ymin = INT_MAX; @@ -389,6 +409,31 @@ void BLI_rctf_transform_pt_v(const rctf *dst, const rctf *src, float xy_dst[2], xy_dst[1] = dst->ymin + ((dst->ymax - dst->ymin) * xy_dst[1]); } +/** + * Calculate a 4x4 matrix representing the transformation between two rectangles. + * + * \note Multiplying a vector by this matrix does *not* give the same value as #BLI_rctf_transform_pt_v. + */ +void BLI_rctf_transform_calc_m4_pivot_min_ex( + const rctf *dst, const rctf *src, float matrix[4][4], + uint x, uint y) +{ + BLI_assert(x < 3 && y < 3); + + unit_m4(matrix); + + matrix[x][x] = BLI_rctf_size_x(src) / BLI_rctf_size_x(dst); + matrix[y][y] = BLI_rctf_size_y(src) / BLI_rctf_size_y(dst); + matrix[3][x] = (src->xmin - dst->xmin) * matrix[x][x]; + matrix[3][y] = (src->ymin - dst->ymin) * matrix[y][y]; +} + +void BLI_rctf_transform_calc_m4_pivot_min( + const rctf *dst, const rctf *src, float matrix[4][4]) +{ + BLI_rctf_transform_calc_m4_pivot_min_ex(dst, src, matrix, 0, 1); +} + void BLI_rcti_translate(rcti *rect, int x, int y) { rect->xmin += x; @@ -420,20 +465,16 @@ void BLI_rctf_recenter(rctf *rect, float x, float y) /* change width & height around the central location */ void BLI_rcti_resize(rcti *rect, int x, int y) { - rect->xmin = rect->xmax = BLI_rcti_cent_x(rect); - rect->ymin = rect->ymax = BLI_rcti_cent_y(rect); - rect->xmin -= x / 2; - rect->ymin -= y / 2; + rect->xmin = BLI_rcti_cent_x(rect) - (x / 2); + rect->ymin = BLI_rcti_cent_y(rect) - (y / 2); rect->xmax = rect->xmin + x; rect->ymax = rect->ymin + y; } void BLI_rctf_resize(rctf *rect, float x, float y) { - rect->xmin = rect->xmax = BLI_rctf_cent_x(rect); - rect->ymin = rect->ymax = BLI_rctf_cent_y(rect); - rect->xmin -= x * 0.5f; - rect->ymin -= y * 0.5f; + rect->xmin = BLI_rctf_cent_x(rect) - (x * 0.5f); + rect->ymin = BLI_rctf_cent_y(rect) - (y * 0.5f); rect->xmax = rect->xmin + x; rect->ymax = rect->ymin + y; } @@ -681,6 +722,14 @@ void BLI_rcti_rctf_copy_floor(rcti *dst, const rctf *src) dst->ymax = floorf(src->ymax); } +void BLI_rcti_rctf_copy_round(rcti *dst, const rctf *src) +{ + dst->xmin = floorf(src->xmin + 0.5f); + dst->xmax = floorf(src->xmax + 0.5f); + dst->ymin = floorf(src->ymin + 0.5f); + dst->ymax = floorf(src->ymax + 0.5f); +} + void BLI_rctf_rcti_copy(rctf *dst, const rcti *src) { dst->xmin = src->xmin; @@ -743,3 +792,12 @@ void BLI_rctf_rotate_expand(rctf *dst, const rctf *src, const float angle) #undef ROTATE_SINCOS /** \} */ + +static void unit_m4(float m[4][4]) +{ + m[0][0] = m[1][1] = m[2][2] = m[3][3] = 1.0f; + m[0][1] = m[0][2] = m[0][3] = 0.0f; + m[1][0] = m[1][2] = m[1][3] = 0.0f; + m[2][0] = m[2][1] = m[2][3] = 0.0f; + m[3][0] = m[3][1] = m[3][2] = 0.0f; +} diff --git a/source/blender/blenlib/intern/storage.c b/source/blender/blenlib/intern/storage.c index 3edc00a8c1a..a48c8b074dd 100644 --- a/source/blender/blenlib/intern/storage.c +++ b/source/blender/blenlib/intern/storage.c @@ -37,14 +37,10 @@ #include <sys/stat.h> -#if defined(__NetBSD__) || defined(__DragonFly__) || defined(__sun__) || defined(__sun) +#if defined(__NetBSD__) || defined(__DragonFly__) /* Other modern unix os's should probably use this also */ # include <sys/statvfs.h> # define USE_STATFS_STATVFS -#elif (defined(__sparc) || defined(__sparc__)) && !defined(__FreeBSD__) && !defined(__linux__) -# include <sys/statfs.h> - /* 4 argument version (not common) */ -# define USE_STATFS_4ARGS #endif #if defined(__APPLE__) || defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__NetBSD__) || defined(__DragonFly__) @@ -113,7 +109,7 @@ double BLI_dir_free_space(const char *dir) #ifdef WIN32 DWORD sectorspc, bytesps, freec, clusters; char tmp[4]; - + tmp[0] = '\\'; tmp[1] = 0; /* Just a failsafe */ if (dir[0] == '/' || dir[0] == '\\') { tmp[0] = '\\'; @@ -139,10 +135,10 @@ double BLI_dir_free_space(const char *dir) char name[FILE_MAXDIR], *slash; int len = strlen(dir); - + if (len >= FILE_MAXDIR) /* path too long */ return -1; - + strcpy(name, dir); if (len) { @@ -194,7 +190,7 @@ size_t BLI_file_size(const char *path) */ int BLI_exists(const char *name) { -#if defined(WIN32) +#if defined(WIN32) BLI_stat_t st; wchar_t *tmp_16 = alloc_utf16_from_8(name, 1); int len, res; @@ -253,10 +249,8 @@ int BLI_stat(const char *path, BLI_stat_t *buffer) int BLI_wstat(const wchar_t *path, BLI_stat_t *buffer) { -#if defined(_MSC_VER) || defined(__MINGW64__) +#if defined(_MSC_VER) return _wstat64(path, buffer); -#elif defined(__MINGW32__) - return _wstati64(path, buffer); #else return _wstat(path, buffer); #endif @@ -372,7 +366,7 @@ LinkNode *BLI_file_read_as_lines(const char *name) size_t size; if (!fp) return NULL; - + fseek(fp, 0, SEEK_END); size = (size_t)ftell(fp); fseek(fp, 0, SEEK_SET); @@ -385,7 +379,7 @@ LinkNode *BLI_file_read_as_lines(const char *name) buf = MEM_mallocN(size, "file_as_lines"); if (buf) { size_t i, last = 0; - + /* * size = because on win32 reading * all the bytes in the file will return @@ -403,10 +397,10 @@ LinkNode *BLI_file_read_as_lines(const char *name) last = i + 1; } } - + MEM_freeN(buf); } - + fclose(fp); return lines.list; @@ -424,23 +418,13 @@ void BLI_file_free_lines(LinkNode *lines) bool BLI_file_older(const char *file1, const char *file2) { #ifdef WIN32 -#ifndef __MINGW32__ struct _stat st1, st2; -#else - struct _stati64 st1, st2; -#endif UTF16_ENCODE(file1); UTF16_ENCODE(file2); - -#ifndef __MINGW32__ + if (_wstat(file1_16, &st1)) return false; if (_wstat(file2_16, &st2)) return false; -#else - if (_wstati64(file1_16, &st1)) return false; - if (_wstati64(file2_16, &st2)) return false; -#endif - UTF16_UN_ENCODE(file2); UTF16_UN_ENCODE(file1); diff --git a/source/blender/blenlib/intern/string.c b/source/blender/blenlib/intern/string.c index f62ffe9e985..6022732025b 100644 --- a/source/blender/blenlib/intern/string.c +++ b/source/blender/blenlib/intern/string.c @@ -332,7 +332,7 @@ size_t BLI_strescape(char *__restrict dst, const char *__restrict src, const siz goto escape_finish; case '\\': case '"': - /* fall-through */ + ATTR_FALLTHROUGH; /* less common but should also be support */ case '\t': @@ -346,7 +346,7 @@ size_t BLI_strescape(char *__restrict dst, const char *__restrict src, const siz /* not enough space to escape */ break; } - /* fall-through */ + ATTR_FALLTHROUGH; default: *dst = *src; break; diff --git a/source/blender/blenlib/intern/string_utf8.c b/source/blender/blenlib/intern/string_utf8.c index 96033615cf5..229a97a2fa7 100644 --- a/source/blender/blenlib/intern/string_utf8.c +++ b/source/blender/blenlib/intern/string_utf8.c @@ -47,6 +47,19 @@ // #define DEBUG_STRSIZE +/* array copied from glib's gutf8.c, */ +/* Note: last two values (0xfe and 0xff) are forbidden in utf-8, so they are considered 1 byte length too. */ +static const size_t utf8_skip_data[256] = { + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 1, 1 +}; + /* from libswish3, originally called u8_isvalid(), * modified to return the index of the bad character (byte index not utf). * http://svn.swish-e.org/libswish3/trunk/src/libswish3/utf8.c r3044 - campbell */ @@ -56,73 +69,91 @@ * length is in bytes, since without knowing whether the string is valid * it's hard to know how many characters there are! */ -static const char trailingBytesForUTF8[256] = { - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5 -}; - -int BLI_utf8_invalid_byte(const char *str, int length) +/** + * Find first utf-8 invalid byte in given \a str, of \a length bytes. + * + * \return the offset of the first invalid byte. + */ +ptrdiff_t BLI_utf8_invalid_byte(const char *str, size_t length) { - const unsigned char *p, *pend = (const unsigned char *)str + length; + const unsigned char *p, *perr, *pend = (const unsigned char *)str + length; unsigned char c; int ab; - for (p = (const unsigned char *)str; p < pend; p++) { + for (p = (const unsigned char *)str; p < pend; p++, length--) { c = *p; + perr = p; /* Erroneous char is always the first of an invalid utf8 sequence... */ + if (ELEM(c, 0xfe, 0xff, 0x00)) /* Those three values are not allowed in utf8 string. */ + goto utf8_error; if (c < 128) continue; if ((c & 0xc0) != 0xc0) goto utf8_error; - ab = trailingBytesForUTF8[c]; - if (length < ab) + + /* Note that since we always increase p (and decrease length) by one byte in main loop, we only add/subtract + * extra utf8 bytes in code below + * (ab number, aka number of bytes remaining in the utf8 sequence after the initial one). */ + ab = (int)utf8_skip_data[c] - 1; + if (length <= ab) { goto utf8_error; - length -= ab; + } - p++; /* Check top bits in the second byte */ + p++; + length--; if ((*p & 0xc0) != 0x80) goto utf8_error; /* Check for overlong sequences for each different length */ switch (ab) { - /* Check for xx00 000x */ - case 1: - if ((c & 0x3e) == 0) goto utf8_error; - continue; /* We know there aren't any more bytes to check */ - - /* Check for 1110 0000, xx0x xxxx */ - case 2: - if (c == 0xe0 && (*p & 0x20) == 0) goto utf8_error; - break; - - /* Check for 1111 0000, xx00 xxxx */ - case 3: - if (c == 0xf0 && (*p & 0x30) == 0) goto utf8_error; - break; - - /* Check for 1111 1000, xx00 0xxx */ - case 4: - if (c == 0xf8 && (*p & 0x38) == 0) goto utf8_error; - break; - - /* Check for leading 0xfe or 0xff, - * and then for 1111 1100, xx00 00xx */ - case 5: - if (c == 0xfe || c == 0xff || - (c == 0xfc && (*p & 0x3c) == 0)) goto utf8_error; - break; + case 1: + /* Check for xx00 000x */ + if ((c & 0x3e) == 0) goto utf8_error; + continue; /* We know there aren't any more bytes to check */ + + case 2: + /* Check for 1110 0000, xx0x xxxx */ + if (c == 0xe0 && (*p & 0x20) == 0) goto utf8_error; + /* Some special cases, see section 5 of utf-8 decoder stress-test by Markus Kuhn + * (https://www.cl.cam.ac.uk/~mgk25/ucs/examples/UTF-8-test.txt). */ + /* From section 5.1 (and 5.2) */ + if (c == 0xed) { + if (*p == 0xa0 && *(p + 1) == 0x80) goto utf8_error; + if (*p == 0xad && *(p + 1) == 0xbf) goto utf8_error; + if (*p == 0xae && *(p + 1) == 0x80) goto utf8_error; + if (*p == 0xaf && *(p + 1) == 0xbf) goto utf8_error; + if (*p == 0xb0 && *(p + 1) == 0x80) goto utf8_error; + if (*p == 0xbe && *(p + 1) == 0x80) goto utf8_error; + if (*p == 0xbf && *(p + 1) == 0xbf) goto utf8_error; + } + /* From section 5.3 */ + if (c == 0xef) { + if (*p == 0xbf && *(p + 1) == 0xbe) goto utf8_error; + if (*p == 0xbf && *(p + 1) == 0xbf) goto utf8_error; + } + break; + + case 3: + /* Check for 1111 0000, xx00 xxxx */ + if (c == 0xf0 && (*p & 0x30) == 0) goto utf8_error; + break; + + case 4: + /* Check for 1111 1000, xx00 0xxx */ + if (c == 0xf8 && (*p & 0x38) == 0) goto utf8_error; + break; + + case 5: + /* Check for 1111 1100, xx00 00xx */ + if (c == 0xfc && (*p & 0x3c) == 0) goto utf8_error; + break; } /* Check for valid bytes after the 2nd, if any; all must start 10 */ while (--ab > 0) { - if ((*(p + 1) & 0xc0) != 0x80) goto utf8_error; - p++; /* do this after so we get usable offset - campbell */ + p++; + length--; + if ((*p & 0xc0) != 0x80) goto utf8_error; } } @@ -130,18 +161,24 @@ int BLI_utf8_invalid_byte(const char *str, int length) utf8_error: - return (int)((const char *)p - (const char *)str) - 1; + return ((const char *)perr - (const char *)str); } -int BLI_utf8_invalid_strip(char *str, int length) +/** + * Remove any invalid utf-8 byte (taking into account multi-bytes sequence of course). + * + * \return number of stripped bytes. + */ +int BLI_utf8_invalid_strip(char *str, size_t length) { - int bad_char, tot = 0; + ptrdiff_t bad_char; + int tot = 0; BLI_assert(str[length] == '\0'); while ((bad_char = BLI_utf8_invalid_byte(str, length)) != -1) { str += bad_char; - length -= bad_char; + length -= (size_t)(bad_char + 1); if (length == 0) { /* last character bad, strip it */ @@ -151,7 +188,7 @@ int BLI_utf8_invalid_strip(char *str, int length) } else { /* strip, keep looking */ - memmove(str, str + 1, (size_t)length); + memmove(str, str + 1, length + 1); /* +1 for NULL char! */ tot++; } } @@ -162,31 +199,17 @@ int BLI_utf8_invalid_strip(char *str, int length) /* compatible with BLI_strncpy, but esnure no partial utf8 chars */ -/* array copied from glib's gutf8.c, - * note: this looks to be at odd's with 'trailingBytesForUTF8', - * need to find out what gives here! - campbell */ -static const size_t utf8_skip_data[256] = { - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, - 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 1, 1 -}; - #define BLI_STR_UTF8_CPY(dst, src, maxncpy) \ { \ size_t utf8_size; \ while (*src != '\0' && (utf8_size = utf8_skip_data[*src]) < maxncpy) {\ maxncpy -= utf8_size; \ switch (utf8_size) { \ - case 6: *dst ++ = *src ++; \ - case 5: *dst ++ = *src ++; \ - case 4: *dst ++ = *src ++; \ - case 3: *dst ++ = *src ++; \ - case 2: *dst ++ = *src ++; \ + case 6: *dst ++ = *src ++; ATTR_FALLTHROUGH; \ + case 5: *dst ++ = *src ++; ATTR_FALLTHROUGH; \ + case 4: *dst ++ = *src ++; ATTR_FALLTHROUGH; \ + case 3: *dst ++ = *src ++; ATTR_FALLTHROUGH; \ + case 2: *dst ++ = *src ++; ATTR_FALLTHROUGH; \ case 1: *dst ++ = *src ++; \ } \ } \ diff --git a/source/blender/blenlib/intern/string_utils.c b/source/blender/blenlib/intern/string_utils.c new file mode 100644 index 00000000000..a693463a302 --- /dev/null +++ b/source/blender/blenlib/intern/string_utils.c @@ -0,0 +1,473 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2017 by the Blender FOundation. + * All rights reserved. + * + * Contributor(s): none yet. + * + * ***** END GPL LICENSE BLOCK ***** + * + */ + +/** \file blender/blenlib/intern/string_utils.c + * \ingroup bli + */ + +#include <ctype.h> +#include <string.h> +#include <stdlib.h> + +#include "MEM_guardedalloc.h" + +#include "BLI_listbase.h" +#include "BLI_string.h" +#include "BLI_string_utf8.h" +#include "BLI_string_utils.h" +#include "BLI_utildefines.h" + +#include "DNA_listBase.h" + + +#ifdef __GNUC__ +# pragma GCC diagnostic error "-Wsign-conversion" +#endif + +/** + * Looks for a numeric suffix preceded by delim character on the end of + * name, puts preceding part into *left and value of suffix into *nr. + * Returns the length of *left. + * + * Foo.001 -> "Foo", 1 + * Returning the length of "Foo" + * + * \param left Where to return copy of part preceding delim + * \param nr Where to return value of numeric suffix + * \param name String to split + * \param delim Delimiter character + * \return Length of \a left + */ +size_t BLI_split_name_num(char *left, int *nr, const char *name, const char delim) +{ + const size_t name_len = strlen(name); + + *nr = 0; + memcpy(left, name, (name_len + 1) * sizeof(char)); + + /* name doesn't end with a delimiter "foo." */ + if ((name_len > 1 && name[name_len - 1] == delim) == 0) { + size_t a = name_len; + while (a--) { + if (name[a] == delim) { + left[a] = '\0'; /* truncate left part here */ + *nr = atol(name + a + 1); + /* casting down to an int, can overflow for large numbers */ + if (*nr < 0) + *nr = 0; + return a; + } + else if (isdigit(name[a]) == 0) { + /* non-numeric suffix - give up */ + break; + } + } + } + + return name_len; +} + +static bool is_char_sep(const char c) +{ + return ELEM(c, '.', ' ', '-', '_'); +} + +/** + * based on `BLI_split_dirfile()` / `os.path.splitext()`, + * `"a.b.c"` -> (`"a.b"`, `".c"`). + */ +void BLI_string_split_suffix(const char *string, char *r_body, char *r_suf, const size_t str_len) +{ + size_t len = BLI_strnlen(string, str_len); + size_t i; + + r_body[0] = r_suf[0] = '\0'; + + for (i = len; i > 0; i--) { + if (is_char_sep(string[i])) { + BLI_strncpy(r_body, string, i + 1); + BLI_strncpy(r_suf, string + i, (len + 1) - i); + return; + } + } + + memcpy(r_body, string, len + 1); +} + +/** + * `"a.b.c"` -> (`"a."`, `"b.c"`) + */ +void BLI_string_split_prefix(const char *string, char *r_pre, char *r_body, const size_t str_len) +{ + size_t len = BLI_strnlen(string, str_len); + size_t i; + + r_body[0] = r_pre[0] = '\0'; + + for (i = 1; i < len; i++) { + if (is_char_sep(string[i])) { + i++; + BLI_strncpy(r_pre, string, i + 1); + BLI_strncpy(r_body, string + i, (len + 1) - i); + return; + } + } + + BLI_strncpy(r_body, string, len); +} + +/** + * Finds the best possible flipped (left/right) name. For renaming; check for unique names afterwards. + * + * \param r_name flipped name, assumed to be a pointer to a string of at least \a name_len size. + * \param from_name original name, assumed to be a pointer to a string of at least \a name_len size. + * \param strip_number If set, remove number extensions. + */ +void BLI_string_flip_side_name(char *r_name, const char *from_name, const bool strip_number, const size_t name_len) +{ + size_t len; + char *prefix = alloca(name_len); /* The part before the facing */ + char *suffix = alloca(name_len); /* The part after the facing */ + char *replace = alloca(name_len); /* The replacement string */ + char *number = alloca(name_len); /* The number extension string */ + char *index = NULL; + bool is_set = false; + + *prefix = *suffix = *replace = *number = '\0'; + + /* always copy the name, since this can be called with an uninitialized string */ + BLI_strncpy(r_name, from_name, name_len); + + len = BLI_strnlen(from_name, name_len); + if (len < 3) { + /* we don't do names like .R or .L */ + return; + } + + /* We first check the case with a .### extension, let's find the last period */ + if (isdigit(r_name[len - 1])) { + index = strrchr(r_name, '.'); // last occurrence + if (index && isdigit(index[1])) { // doesnt handle case bone.1abc2 correct..., whatever! + if (strip_number == false) { + BLI_strncpy(number, index, name_len); + } + *index = 0; + len = BLI_strnlen(r_name, name_len); + } + } + + BLI_strncpy(prefix, r_name, name_len); + + /* first case; separator . - _ with extensions r R l L */ + if ((len > 1) && is_char_sep(r_name[len - 2])) { + is_set = true; + switch (r_name[len - 1]) { + case 'l': + prefix[len - 1] = 0; + strcpy(replace, "r"); + break; + case 'r': + prefix[len - 1] = 0; + strcpy(replace, "l"); + break; + case 'L': + prefix[len - 1] = 0; + strcpy(replace, "R"); + break; + case 'R': + prefix[len - 1] = 0; + strcpy(replace, "L"); + break; + default: + is_set = false; + } + } + + /* case; beginning with r R l L, with separator after it */ + if (!is_set && is_char_sep(r_name[1])) { + is_set = true; + switch (r_name[0]) { + case 'l': + strcpy(replace, "r"); + BLI_strncpy(suffix, r_name + 1, name_len); + prefix[0] = 0; + break; + case 'r': + strcpy(replace, "l"); + BLI_strncpy(suffix, r_name + 1, name_len); + prefix[0] = 0; + break; + case 'L': + strcpy(replace, "R"); + BLI_strncpy(suffix, r_name + 1, name_len); + prefix[0] = 0; + break; + case 'R': + strcpy(replace, "L"); + BLI_strncpy(suffix, r_name + 1, name_len); + prefix[0] = 0; + break; + default: + is_set = false; + } + } + + if (!is_set && len > 5) { + /* hrms, why test for a separator? lets do the rule 'ultimate left or right' */ + if (((index = BLI_strcasestr(prefix, "right")) == prefix) || + (index == prefix + len - 5)) + { + is_set = true; + if (index[0] == 'r') { + strcpy(replace, "left"); + } + else { + strcpy(replace, (index[1] == 'I') ? "LEFT" : "Left"); + } + *index = 0; + BLI_strncpy(suffix, index + 5, name_len); + } + else if (((index = BLI_strcasestr(prefix, "left")) == prefix) || + (index == prefix + len - 4)) + { + is_set = true; + if (index[0] == 'l') { + strcpy(replace, "right"); + } + else { + strcpy(replace, (index[1] == 'E') ? "RIGHT" : "Right"); + } + *index = 0; + BLI_strncpy(suffix, index + 4, name_len); + } + } + + BLI_snprintf(r_name, name_len, "%s%s%s%s", prefix, replace, suffix, number); +} + + +/* Unique name utils. */ + +/** + * Ensures name is unique (according to criteria specified by caller in unique_check callback), + * incrementing its numeric suffix as necessary. Returns true if name had to be adjusted. + * + * \param unique_check Return true if name is not unique + * \param arg Additional arg to unique_check--meaning is up to caller + * \param defname To initialize name if latter is empty + * \param delim Delimits numeric suffix in name + * \param name Name to be ensured unique + * \param name_len Maximum length of name area + * \return true if there if the name was changed + */ +bool BLI_uniquename_cb( + UniquenameCheckCallback unique_check, void *arg, const char *defname, char delim, char *name, size_t name_len) +{ + if (name[0] == '\0') { + BLI_strncpy(name, defname, name_len); + } + + if (unique_check(arg, name)) { + char numstr[16]; + char *tempname = alloca(name_len); + char *left = alloca(name_len); + int number; + size_t len = BLI_split_name_num(left, &number, name, delim); + do { + /* add 1 to account for \0 */ + const size_t numlen = BLI_snprintf(numstr, sizeof(numstr), "%c%03d", delim, ++number) + 1; + + /* highly unlikely the string only has enough room for the number + * but support anyway */ + if ((len == 0) || (numlen >= name_len)) { + /* number is know not to be utf-8 */ + BLI_strncpy(tempname, numstr, name_len); + } + else { + char *tempname_buf; + tempname_buf = tempname + BLI_strncpy_utf8_rlen(tempname, left, name_len - numlen); + memcpy(tempname_buf, numstr, numlen); + } + } while (unique_check(arg, tempname)); + + BLI_strncpy(name, tempname, name_len); + + return true; + } + + return false; +} + +/* little helper macro for BLI_uniquename */ +#ifndef GIVE_STRADDR +# define GIVE_STRADDR(data, offset) ( ((char *)data) + offset) +#endif + +/* Generic function to set a unique name. It is only designed to be used in situations + * where the name is part of the struct. + * + * For places where this is used, see constraint.c for example... + * + * name_offs: should be calculated using offsetof(structname, membername) macro from stddef.h + * len: maximum length of string (to prevent overflows, etc.) + * defname: the name that should be used by default if none is specified already + * delim: the character which acts as a delimiter between parts of the name + */ +static bool uniquename_find_dupe(ListBase *list, void *vlink, const char *name, int name_offs) +{ + Link *link; + + for (link = list->first; link; link = link->next) { + if (link != vlink) { + if (STREQ(GIVE_STRADDR(link, name_offs), name)) { + return true; + } + } + } + + return false; +} + +static bool uniquename_unique_check(void *arg, const char *name) +{ + struct {ListBase *lb; void *vlink; int name_offs; } *data = arg; + return uniquename_find_dupe(data->lb, data->vlink, name, data->name_offs); +} + +/** + * Ensures that the specified block has a unique name within the containing list, + * incrementing its numeric suffix as necessary. Returns true if name had to be adjusted. + * + * \param list List containing the block + * \param vlink The block to check the name for + * \param defname To initialize block name if latter is empty + * \param delim Delimits numeric suffix in name + * \param name_offs Offset of name within block structure + * \param name_len Maximum length of name area + */ +bool BLI_uniquename(ListBase *list, void *vlink, const char *defname, char delim, int name_offs, size_t name_len) +{ + struct {ListBase *lb; void *vlink; int name_offs; } data; + data.lb = list; + data.vlink = vlink; + data.name_offs = name_offs; + + BLI_assert(name_len > 1); + + /* See if we are given an empty string */ + if (ELEM(NULL, vlink, defname)) + return false; + + return BLI_uniquename_cb(uniquename_unique_check, &data, defname, delim, GIVE_STRADDR(vlink, name_offs), name_len); +} + +/* ------------------------------------------------------------------------- */ +/** \name Join Strings + * + * For non array versions of these functions, use the macros: + * - #BLI_string_joinN + * - #BLI_string_join_by_sep_charN + * - #BLI_string_join_by_sep_char_with_tableN + * + * \{ */ + +/** + * Join an array of strings into a newly allocated, null terminated string. + */ +char *BLI_string_join_arrayN( + const char *strings[], uint strings_len) +{ + uint total_len = 1; + for (uint i = 0; i < strings_len; i++) { + total_len += strlen(strings[i]); + } + char *result = MEM_mallocN(sizeof(char) * total_len, __func__); + char *c = result; + for (uint i = 0; i < strings_len; i++) { + c += BLI_strcpy_rlen(c, strings[i]); + } + return result; +} + +/** + * A version of #BLI_string_joinN that takes a separator which can be any character including '\0'. + */ +char *BLI_string_join_array_by_sep_charN( + char sep, const char *strings[], uint strings_len) +{ + uint total_len = 0; + for (uint i = 0; i < strings_len; i++) { + total_len += strlen(strings[i]) + 1; + } + if (total_len == 0) { + total_len = 1; + } + + char *result = MEM_mallocN(sizeof(char) * total_len, __func__); + char *c = result; + if (strings_len != 0) { + for (uint i = 0; i < strings_len; i++) { + c += BLI_strcpy_rlen(c, strings[i]); + *c = sep; + c++; + } + c--; + } + *c = '\0'; + return result; +} + +/** + * A version of #BLI_string_join_array_by_sep_charN that takes a table array. + * The new location of each string is written into this array. + */ +char *BLI_string_join_array_by_sep_char_with_tableN( + char sep, char *table[], const char *strings[], uint strings_len) +{ + uint total_len = 0; + for (uint i = 0; i < strings_len; i++) { + total_len += strlen(strings[i]) + 1; + } + if (total_len == 0) { + total_len = 1; + } + + char *result = MEM_mallocN(sizeof(char) * total_len, __func__); + char *c = result; + if (strings_len != 0) { + for (uint i = 0; i < strings_len; i++) { + table[i] = c; /* <-- only difference to BLI_string_join_array_by_sep_charN. */ + c += BLI_strcpy_rlen(c, strings[i]); + *c = sep; + c++; + } + c--; + } + *c = '\0'; + return result; +} + +/** \} */ diff --git a/source/blender/blenlib/intern/task.c b/source/blender/blenlib/intern/task.c index fc2d9674c2f..e050f3148b8 100644 --- a/source/blender/blenlib/intern/task.c +++ b/source/blender/blenlib/intern/task.c @@ -48,6 +48,39 @@ */ #define MEMPOOL_SIZE 256 +/* Number of tasks which are pushed directly to local thread queue. + * + * This allows thread to fetch next task without locking the whole queue. + */ +#define LOCAL_QUEUE_SIZE 1 + +/* Number of tasks which are allowed to be scheduled in a delayed manner. + * + * This allows to use less locks per graph node children schedule. More details + * could be found at TaskThreadLocalStorage::do_delayed_push. + */ +#define DELAYED_QUEUE_SIZE 4096 + +#ifndef NDEBUG +# define ASSERT_THREAD_ID(scheduler, thread_id) \ + do { \ + if (!BLI_thread_is_main()) { \ + TaskThread *thread = pthread_getspecific(scheduler->tls_id_key); \ + if (thread == NULL) { \ + BLI_assert(thread_id == 0); \ + } \ + else { \ + BLI_assert(thread_id == thread->id); \ + } \ + } \ + else { \ + BLI_assert(thread_id == 0); \ + } \ + } while (false) +#else +# define ASSERT_THREAD_ID(scheduler, thread_id) +#endif + typedef struct Task { struct Task *next, *prev; @@ -102,13 +135,35 @@ typedef struct TaskMemPoolStats { } TaskMemPoolStats; #endif +typedef struct TaskThreadLocalStorage { + /* Memory pool for faster task allocation. + * The idea is to re-use memory of finished/discarded tasks by this thread. + */ + TaskMemPool task_mempool; + + /* Local queue keeps thread alive by keeping small amount of tasks ready + * to be picked up without causing global thread locks for synchronization. + */ + int num_local_queue; + Task *local_queue[LOCAL_QUEUE_SIZE]; + + /* Thread can be marked for delayed tasks push. This is helpful when it's + * know that lots of subsequent task pushed will happen from the same thread + * without "interrupting" for task execution. + * + * We try to accumulate as much tasks as possible in a local queue without + * any locks first, and then we push all of them into a scheduler's queue + * from within a single mutex lock. + */ + bool do_delayed_push; + int num_delayed_queue; + Task *delayed_queue[DELAYED_QUEUE_SIZE]; +} TaskThreadLocalStorage; + struct TaskPool { TaskScheduler *scheduler; volatile size_t num; - volatile size_t done; - size_t num_threads; - size_t currently_running_tasks; ThreadMutex num_mutex; ThreadCondition num_cond; @@ -116,6 +171,11 @@ struct TaskPool { ThreadMutex user_mutex; volatile bool do_cancel; + volatile bool do_work; + + volatile bool is_suspended; + ListBase suspended_queue; + size_t num_suspended; /* If set, this pool may never be work_and_wait'ed, which means TaskScheduler * has to use its special background fallback thread in case we are in @@ -123,16 +183,20 @@ struct TaskPool { */ bool run_in_background; - /* This pool is used for caching task pointers for thread id 0. - * This could either point to a global scheduler's task_mempool[0] if the - * pool is handled form the main thread or point to task_mempool_local - * otherwise. - * - * This way we solve possible threading conflicts accessing same global - * memory pool from multiple threads from which wait_work() is called. + /* This is a task scheduler's ID of a thread at which pool was constructed. + * It will be used to access task TLS. + */ + int thread_id; + + /* For the pools which are created from non-main thread which is not a + * scheduler worker thread we can't re-use any of scheduler's threads TLS + * and have to use our own one. */ - TaskMemPool *task_mempool; - TaskMemPool task_mempool_local; + bool use_local_tls; + TaskThreadLocalStorage local_tls; +#ifndef NDEBUG + pthread_t creator_thread_id; +#endif #ifdef DEBUG_STATS TaskMemPoolStats *mempool_stats; @@ -142,7 +206,6 @@ struct TaskPool { struct TaskScheduler { pthread_t *threads; struct TaskThread *task_threads; - TaskMemPool *task_mempool; int num_threads; bool background_thread_only; @@ -151,15 +214,19 @@ struct TaskScheduler { ThreadCondition queue_cond; volatile bool do_exit; + + /* NOTE: In pthread's TLS we store the whole TaskThread structure. */ + pthread_key_t tls_id_key; }; typedef struct TaskThread { TaskScheduler *scheduler; int id; + TaskThreadLocalStorage tls; } TaskThread; /* Helper */ -static void task_data_free(Task *task, const int thread_id) +BLI_INLINE void task_data_free(Task *task, const int thread_id) { if (task->free_taskdata) { if (task->freedata) { @@ -171,28 +238,54 @@ static void task_data_free(Task *task, const int thread_id) } } -BLI_INLINE TaskMemPool *get_task_mempool(TaskPool *pool, const int thread_id) +BLI_INLINE void initialize_task_tls(TaskThreadLocalStorage *tls) +{ + memset(tls, 0, sizeof(TaskThreadLocalStorage)); +} + +BLI_INLINE TaskThreadLocalStorage *get_task_tls(TaskPool *pool, + const int thread_id) { + TaskScheduler *scheduler = pool->scheduler; + BLI_assert(thread_id >= 0); + BLI_assert(thread_id <= scheduler->num_threads); + if (pool->use_local_tls && thread_id == 0) { + BLI_assert(pool->thread_id == 0); + BLI_assert(!BLI_thread_is_main()); + BLI_assert(pthread_equal(pthread_self(), pool->creator_thread_id)); + return &pool->local_tls; + } if (thread_id == 0) { - return pool->task_mempool; + BLI_assert(BLI_thread_is_main()); + return &scheduler->task_threads[pool->thread_id].tls; + } + return &scheduler->task_threads[thread_id].tls; +} + +BLI_INLINE void free_task_tls(TaskThreadLocalStorage *tls) +{ + TaskMemPool *task_mempool = &tls->task_mempool; + for (int i = 0; i < task_mempool->num_tasks; ++i) { + MEM_freeN(task_mempool->tasks[i]); } - return &pool->scheduler->task_mempool[thread_id]; } static Task *task_alloc(TaskPool *pool, const int thread_id) { - assert(thread_id <= pool->scheduler->num_threads); + BLI_assert(thread_id <= pool->scheduler->num_threads); if (thread_id != -1) { - assert(thread_id >= 0); - TaskMemPool *mem_pool = get_task_mempool(pool, thread_id); + BLI_assert(thread_id >= 0); + BLI_assert(thread_id <= pool->scheduler->num_threads); + TaskThreadLocalStorage *tls = get_task_tls(pool, thread_id); + TaskMemPool *task_mempool = &tls->task_mempool; /* Try to re-use task memory from a thread local storage. */ - if (mem_pool->num_tasks > 0) { - --mem_pool->num_tasks; + if (task_mempool->num_tasks > 0) { + --task_mempool->num_tasks; /* Success! We've just avoided task allocation. */ #ifdef DEBUG_STATS pool->mempool_stats[thread_id].num_reuse++; #endif - return mem_pool->tasks[mem_pool->num_tasks]; + return task_mempool->tasks[task_mempool->num_tasks]; } /* We are doomed to allocate new task data. */ #ifdef DEBUG_STATS @@ -205,13 +298,17 @@ static Task *task_alloc(TaskPool *pool, const int thread_id) static void task_free(TaskPool *pool, Task *task, const int thread_id) { task_data_free(task, thread_id); - assert(thread_id >= 0); - assert(thread_id <= pool->scheduler->num_threads); - TaskMemPool *mem_pool = get_task_mempool(pool, thread_id); - if (mem_pool->num_tasks < MEMPOOL_SIZE - 1) { + BLI_assert(thread_id >= 0); + BLI_assert(thread_id <= pool->scheduler->num_threads); + if (thread_id == 0) { + BLI_assert(pool->use_local_tls || BLI_thread_is_main()); + } + TaskThreadLocalStorage *tls = get_task_tls(pool, thread_id); + TaskMemPool *task_mempool = &tls->task_mempool; + if (task_mempool->num_tasks < MEMPOOL_SIZE - 1) { /* Successfully allowed the task to be re-used later. */ - mem_pool->tasks[mem_pool->num_tasks] = task; - ++mem_pool->num_tasks; + task_mempool->tasks[task_mempool->num_tasks] = task; + ++task_mempool->num_tasks; } else { /* Local storage saturated, no other way than just discard @@ -237,8 +334,6 @@ static void task_pool_num_decrease(TaskPool *pool, size_t done) BLI_assert(pool->num >= done); pool->num -= done; - atomic_sub_and_fetch_z(&pool->currently_running_tasks, done); - pool->done += done; if (pool->num == 0) BLI_condition_notify_all(&pool->num_cond); @@ -246,11 +341,11 @@ static void task_pool_num_decrease(TaskPool *pool, size_t done) BLI_mutex_unlock(&pool->num_mutex); } -static void task_pool_num_increase(TaskPool *pool) +static void task_pool_num_increase(TaskPool *pool, size_t new) { BLI_mutex_lock(&pool->num_mutex); - pool->num++; + pool->num += new; BLI_condition_notify_all(&pool->num_cond); BLI_mutex_unlock(&pool->num_mutex); @@ -292,17 +387,10 @@ static bool task_scheduler_thread_wait_pop(TaskScheduler *scheduler, Task **task continue; } - if (atomic_add_and_fetch_z(&pool->currently_running_tasks, 1) <= pool->num_threads || - pool->num_threads == 0) - { - *task = current_task; - found_task = true; - BLI_remlink(&scheduler->queue, *task); - break; - } - else { - atomic_sub_and_fetch_z(&pool->currently_running_tasks, 1); - } + *task = current_task; + found_task = true; + BLI_remlink(&scheduler->queue, *task); + break; } if (!found_task) BLI_condition_wait(&scheduler->queue_cond, &scheduler->queue_mutex); @@ -313,23 +401,51 @@ static bool task_scheduler_thread_wait_pop(TaskScheduler *scheduler, Task **task return true; } +BLI_INLINE void handle_local_queue(TaskThreadLocalStorage *tls, + const int thread_id) +{ + BLI_assert(!tls->do_delayed_push); + while (tls->num_local_queue > 0) { + /* We pop task from queue before handling it so handler of the task can + * push next job to the local queue. + */ + tls->num_local_queue--; + Task *local_task = tls->local_queue[tls->num_local_queue]; + /* TODO(sergey): Double-check work_and_wait() doesn't handle other's + * pool tasks. + */ + TaskPool *local_pool = local_task->pool; + local_task->run(local_pool, local_task->taskdata, thread_id); + task_free(local_pool, local_task, thread_id); + } + BLI_assert(!tls->do_delayed_push); +} + static void *task_scheduler_thread_run(void *thread_p) { TaskThread *thread = (TaskThread *) thread_p; + TaskThreadLocalStorage *tls = &thread->tls; TaskScheduler *scheduler = thread->scheduler; int thread_id = thread->id; Task *task; + pthread_setspecific(scheduler->tls_id_key, thread); + /* keep popping off tasks */ while (task_scheduler_thread_wait_pop(scheduler, &task)) { TaskPool *pool = task->pool; /* run task */ + BLI_assert(!tls->do_delayed_push); task->run(pool, task->taskdata, thread_id); + BLI_assert(!tls->do_delayed_push); /* delete task */ task_free(pool, task, thread_id); + /* Handle all tasks from local queue. */ + handle_local_queue(tls, thread_id); + /* notify pool task was done */ task_pool_num_decrease(pool, 1); } @@ -359,30 +475,35 @@ TaskScheduler *BLI_task_scheduler_create(int num_threads) /* Add background-only thread if needed. */ if (num_threads == 0) { - scheduler->background_thread_only = true; - num_threads = 1; + scheduler->background_thread_only = true; + num_threads = 1; } + scheduler->task_threads = MEM_mallocN(sizeof(TaskThread) * (num_threads + 1), + "TaskScheduler task threads"); + + /* Initialize TLS for main thread. */ + initialize_task_tls(&scheduler->task_threads[0].tls); + + pthread_key_create(&scheduler->tls_id_key, NULL); + /* launch threads that will be waiting for work */ if (num_threads > 0) { int i; scheduler->num_threads = num_threads; scheduler->threads = MEM_callocN(sizeof(pthread_t) * num_threads, "TaskScheduler threads"); - scheduler->task_threads = MEM_callocN(sizeof(TaskThread) * num_threads, "TaskScheduler task threads"); for (i = 0; i < num_threads; i++) { - TaskThread *thread = &scheduler->task_threads[i]; + TaskThread *thread = &scheduler->task_threads[i + 1]; thread->scheduler = scheduler; thread->id = i + 1; + initialize_task_tls(&thread->tls); if (pthread_create(&scheduler->threads[i], NULL, task_scheduler_thread_run, thread) != 0) { fprintf(stderr, "TaskScheduler failed to launch thread %d/%d\n", i, num_threads); } } - - scheduler->task_mempool = MEM_callocN(sizeof(*scheduler->task_mempool) * (num_threads + 1), - "TaskScheduler task_mempool"); } return scheduler; @@ -398,6 +519,8 @@ void BLI_task_scheduler_free(TaskScheduler *scheduler) BLI_condition_notify_all(&scheduler->queue_cond); BLI_mutex_unlock(&scheduler->queue_mutex); + pthread_key_delete(scheduler->tls_id_key); + /* delete threads */ if (scheduler->threads) { int i; @@ -412,17 +535,12 @@ void BLI_task_scheduler_free(TaskScheduler *scheduler) /* Delete task thread data */ if (scheduler->task_threads) { - MEM_freeN(scheduler->task_threads); - } - - /* Delete task memory pool */ - if (scheduler->task_mempool) { - for (int i = 0; i <= scheduler->num_threads; ++i) { - for (int j = 0; j < scheduler->task_mempool[i].num_tasks; ++j) { - MEM_freeN(scheduler->task_mempool[i].tasks[j]); - } + for (int i = 0; i < scheduler->num_threads + 1; ++i) { + TaskThreadLocalStorage *tls = &scheduler->task_threads[i].tls; + free_task_tls(tls); } - MEM_freeN(scheduler->task_mempool); + + MEM_freeN(scheduler->task_threads); } /* delete leftover tasks */ @@ -445,7 +563,7 @@ int BLI_task_scheduler_num_threads(TaskScheduler *scheduler) static void task_scheduler_push(TaskScheduler *scheduler, Task *task, TaskPriority priority) { - task_pool_num_increase(task->pool); + task_pool_num_increase(task->pool, 1); /* add task to queue */ BLI_mutex_lock(&scheduler->queue_mutex); @@ -459,6 +577,27 @@ static void task_scheduler_push(TaskScheduler *scheduler, Task *task, TaskPriori BLI_mutex_unlock(&scheduler->queue_mutex); } +static void task_scheduler_push_all(TaskScheduler *scheduler, + TaskPool *pool, + Task **tasks, + int num_tasks) +{ + if (num_tasks == 0) { + return; + } + + task_pool_num_increase(pool, num_tasks); + + BLI_mutex_lock(&scheduler->queue_mutex); + + for (int i = 0; i < num_tasks; i++) { + BLI_addhead(&scheduler->queue, tasks[i]); + } + + BLI_condition_notify_all(&scheduler->queue_cond); + BLI_mutex_unlock(&scheduler->queue_mutex); +} + static void task_scheduler_clear(TaskScheduler *scheduler, TaskPool *pool) { Task *task, *nexttask; @@ -471,7 +610,7 @@ static void task_scheduler_clear(TaskScheduler *scheduler, TaskPool *pool) nexttask = task->next; if (task->pool == pool) { - task_data_free(task, 0); + task_data_free(task, pool->thread_id); BLI_freelinkN(&scheduler->queue, task); done++; @@ -486,7 +625,10 @@ static void task_scheduler_clear(TaskScheduler *scheduler, TaskPool *pool) /* Task Pool */ -static TaskPool *task_pool_create_ex(TaskScheduler *scheduler, void *userdata, const bool is_background) +static TaskPool *task_pool_create_ex(TaskScheduler *scheduler, + void *userdata, + const bool is_background, + const bool is_suspended) { TaskPool *pool = MEM_mallocN(sizeof(TaskPool), "TaskPool"); @@ -504,11 +646,13 @@ static TaskPool *task_pool_create_ex(TaskScheduler *scheduler, void *userdata, c pool->scheduler = scheduler; pool->num = 0; - pool->done = 0; - pool->num_threads = 0; - pool->currently_running_tasks = 0; pool->do_cancel = false; + pool->do_work = false; + pool->is_suspended = is_suspended; + pool->num_suspended = 0; + pool->suspended_queue.first = pool->suspended_queue.last = NULL; pool->run_in_background = is_background; + pool->use_local_tls = false; BLI_mutex_init(&pool->num_mutex); BLI_condition_init(&pool->num_cond); @@ -517,11 +661,26 @@ static TaskPool *task_pool_create_ex(TaskScheduler *scheduler, void *userdata, c BLI_mutex_init(&pool->user_mutex); if (BLI_thread_is_main()) { - pool->task_mempool = scheduler->task_mempool; + pool->thread_id = 0; } else { - pool->task_mempool = &pool->task_mempool_local; - pool->task_mempool_local.num_tasks = 0; + TaskThread *thread = pthread_getspecific(scheduler->tls_id_key); + if (thread == NULL) { + /* NOTE: Task pool is created from non-main thread which is not + * managed by the task scheduler. We identify ourselves as thread ID + * 0 but we do not use scheduler's TLS storage and use our own + * instead to avoid any possible threading conflicts. + */ + pool->thread_id = 0; + pool->use_local_tls = true; +#ifndef NDEBUG + pool->creator_thread_id = pthread_self(); +#endif + initialize_task_tls(&pool->local_tls); + } + else { + pool->thread_id = thread->id; + } } #ifdef DEBUG_STATS @@ -548,7 +707,7 @@ static TaskPool *task_pool_create_ex(TaskScheduler *scheduler, void *userdata, c */ TaskPool *BLI_task_pool_create(TaskScheduler *scheduler, void *userdata) { - return task_pool_create_ex(scheduler, userdata, false); + return task_pool_create_ex(scheduler, userdata, false, false); } /** @@ -563,25 +722,28 @@ TaskPool *BLI_task_pool_create(TaskScheduler *scheduler, void *userdata) */ TaskPool *BLI_task_pool_create_background(TaskScheduler *scheduler, void *userdata) { - return task_pool_create_ex(scheduler, userdata, true); + return task_pool_create_ex(scheduler, userdata, true, false); +} + +/** + * Similar to BLI_task_pool_create() but does not schedule any tasks for execution + * for until BLI_task_pool_work_and_wait() is called. This helps reducing therading + * overhead when pushing huge amount of small initial tasks from the main thread. + */ +TaskPool *BLI_task_pool_create_suspended(TaskScheduler *scheduler, void *userdata) +{ + return task_pool_create_ex(scheduler, userdata, false, true); } void BLI_task_pool_free(TaskPool *pool) { - BLI_task_pool_stop(pool); + BLI_task_pool_cancel(pool); BLI_mutex_end(&pool->num_mutex); BLI_condition_end(&pool->num_cond); BLI_mutex_end(&pool->user_mutex); - /* Free local memory pool, those pointers are lost forever. */ - if (pool->task_mempool == &pool->task_mempool_local) { - for (int i = 0; i < pool->task_mempool_local.num_tasks; i++) { - MEM_freeN(pool->task_mempool_local.tasks[i]); - } - } - #ifdef DEBUG_STATS printf("Thread ID Allocated Reused Discarded\n"); for (int i = 0; i < pool->scheduler->num_threads + 1; ++i) { @@ -594,24 +756,68 @@ void BLI_task_pool_free(TaskPool *pool) MEM_freeN(pool->mempool_stats); #endif + if (pool->use_local_tls) { + free_task_tls(&pool->local_tls); + } + MEM_freeN(pool); BLI_end_threaded_malloc(); } +BLI_INLINE bool task_can_use_local_queues(TaskPool *pool, int thread_id) +{ + return (thread_id != -1 && (thread_id != pool->thread_id || pool->do_work)); +} + static void task_pool_push( TaskPool *pool, TaskRunFunction run, void *taskdata, bool free_taskdata, TaskFreeFunction freedata, TaskPriority priority, int thread_id) { + /* Allocate task and fill it's properties. */ Task *task = task_alloc(pool, thread_id); - task->run = run; task->taskdata = taskdata; task->free_taskdata = free_taskdata; task->freedata = freedata; task->pool = pool; - + /* For suspended pools we put everything yo a global queue first + * and exit as soon as possible. + * + * This tasks will be moved to actual execution when pool is + * activated by work_and_wait(). + */ + if (pool->is_suspended) { + BLI_addhead(&pool->suspended_queue, task); + atomic_fetch_and_add_z(&pool->num_suspended, 1); + return; + } + /* Populate to any local queue first, this is cheapest push ever. */ + if (task_can_use_local_queues(pool, thread_id)) { + ASSERT_THREAD_ID(pool->scheduler, thread_id); + TaskThreadLocalStorage *tls = get_task_tls(pool, thread_id); + /* Try to push to a local execution queue. + * These tasks will be picked up next. + */ + if (tls->num_local_queue < LOCAL_QUEUE_SIZE) { + tls->local_queue[tls->num_local_queue] = task; + tls->num_local_queue++; + return; + } + /* If we are in the delayed tasks push mode, we push tasks to a + * temporary local queue first without any locks, and then move them + * to global execution queue with a single lock. + */ + if (tls->do_delayed_push && tls->num_delayed_queue < DELAYED_QUEUE_SIZE) { + tls->delayed_queue[tls->num_delayed_queue] = task; + tls->num_delayed_queue++; + return; + } + } + /* Do push to a global execution ppol, slowest possible method, + * causes quite reasonable amount of threading overhead. + */ task_scheduler_push(pool->scheduler, task, priority); } @@ -636,8 +842,25 @@ void BLI_task_pool_push_from_thread(TaskPool *pool, TaskRunFunction run, void BLI_task_pool_work_and_wait(TaskPool *pool) { + TaskThreadLocalStorage *tls = get_task_tls(pool, pool->thread_id); TaskScheduler *scheduler = pool->scheduler; + if (atomic_fetch_and_and_uint8((uint8_t *)&pool->is_suspended, 0)) { + if (pool->num_suspended) { + task_pool_num_increase(pool, pool->num_suspended); + BLI_mutex_lock(&scheduler->queue_mutex); + + BLI_movelisttolist(&scheduler->queue, &pool->suspended_queue); + + BLI_condition_notify_all(&scheduler->queue_cond); + BLI_mutex_unlock(&scheduler->queue_mutex); + } + } + + pool->do_work = true; + + ASSERT_THREAD_ID(pool->scheduler, pool->thread_id); + BLI_mutex_lock(&pool->num_mutex); while (pool->num != 0) { @@ -651,16 +874,12 @@ void BLI_task_pool_work_and_wait(TaskPool *pool) /* find task from this pool. if we get a task from another pool, * we can get into deadlock */ - if (pool->num_threads == 0 || - pool->currently_running_tasks < pool->num_threads) - { - for (task = scheduler->queue.first; task; task = task->next) { - if (task->pool == pool) { - work_task = task; - found_task = true; - BLI_remlink(&scheduler->queue, task); - break; - } + for (task = scheduler->queue.first; task; task = task->next) { + if (task->pool == pool) { + work_task = task; + found_task = true; + BLI_remlink(&scheduler->queue, task); + break; } } @@ -669,11 +888,15 @@ void BLI_task_pool_work_and_wait(TaskPool *pool) /* if found task, do it, otherwise wait until other tasks are done */ if (found_task) { /* run task */ - atomic_add_and_fetch_z(&pool->currently_running_tasks, 1); - work_task->run(pool, work_task->taskdata, 0); + BLI_assert(!tls->do_delayed_push); + work_task->run(pool, work_task->taskdata, pool->thread_id); + BLI_assert(!tls->do_delayed_push); /* delete task */ - task_free(pool, task, 0); + task_free(pool, task, pool->thread_id); + + /* Handle all tasks from local queue. */ + handle_local_queue(tls, pool->thread_id); /* notify pool task was done */ task_pool_num_decrease(pool, 1); @@ -688,22 +911,8 @@ void BLI_task_pool_work_and_wait(TaskPool *pool) } BLI_mutex_unlock(&pool->num_mutex); -} - -int BLI_pool_get_num_threads(TaskPool *pool) -{ - if (pool->num_threads != 0) { - return pool->num_threads; - } - else { - return BLI_task_scheduler_num_threads(pool->scheduler); - } -} -void BLI_pool_set_num_threads(TaskPool *pool, int num_threads) -{ - /* NOTE: Don't try to modify threads while tasks are running! */ - pool->num_threads = num_threads; + handle_local_queue(tls, pool->thread_id); } void BLI_task_pool_cancel(TaskPool *pool) @@ -721,13 +930,6 @@ void BLI_task_pool_cancel(TaskPool *pool) pool->do_cancel = false; } -void BLI_task_pool_stop(TaskPool *pool) -{ - task_scheduler_clear(pool->scheduler, pool); - - BLI_assert(pool->num == 0); -} - bool BLI_task_pool_canceled(TaskPool *pool) { return pool->do_cancel; @@ -743,9 +945,28 @@ ThreadMutex *BLI_task_pool_user_mutex(TaskPool *pool) return &pool->user_mutex; } -size_t BLI_task_pool_tasks_done(TaskPool *pool) +void BLI_task_pool_delayed_push_begin(TaskPool *pool, int thread_id) +{ + if (task_can_use_local_queues(pool, thread_id)) { + ASSERT_THREAD_ID(pool->scheduler, thread_id); + TaskThreadLocalStorage *tls = get_task_tls(pool, thread_id); + tls->do_delayed_push = true; + } +} + +void BLI_task_pool_delayed_push_end(TaskPool *pool, int thread_id) { - return pool->done; + if (task_can_use_local_queues(pool, thread_id)) { + ASSERT_THREAD_ID(pool->scheduler, thread_id); + TaskThreadLocalStorage *tls = get_task_tls(pool, thread_id); + BLI_assert(tls->do_delayed_push); + task_scheduler_push_all(pool->scheduler, + pool, + tls->delayed_queue, + tls->num_delayed_queue); + tls->do_delayed_push = false; + tls->num_delayed_queue = 0; + } } /* Parallel range routines */ @@ -783,7 +1004,7 @@ BLI_INLINE bool parallel_range_next_iter_get( int * __restrict iter, int * __restrict count) { uint32_t uval = atomic_fetch_and_add_uint32((uint32_t *)(&state->iter), state->chunk_size); - int previter = *(int32_t*)&uval; + int previter = *(int32_t *)&uval; *iter = previter; *count = max_ii(0, min_ii(state->chunk_size, state->stop - previter)); @@ -906,7 +1127,7 @@ static void task_parallel_range_ex( atomic_fetch_and_add_uint32((uint32_t *)(&state.iter), 0); if (use_userdata_chunk) { - userdata_chunk_array = MALLOCA(userdata_chunk_size * num_tasks); + userdata_chunk_array = MALLOCA(userdata_chunk_size * num_tasks); } for (i = 0; i < num_tasks; i++) { @@ -918,7 +1139,8 @@ static void task_parallel_range_ex( BLI_task_pool_push_from_thread(task_pool, parallel_range_func, userdata_chunk_local, false, - TASK_PRIORITY_HIGH, 0); + TASK_PRIORITY_HIGH, + task_pool->thread_id); } BLI_task_pool_work_and_wait(task_pool); @@ -1124,7 +1346,8 @@ void BLI_task_parallel_listbase( BLI_task_pool_push_from_thread(task_pool, parallel_listbase_func, NULL, false, - TASK_PRIORITY_HIGH, 0); + TASK_PRIORITY_HIGH, + task_pool->thread_id); } BLI_task_pool_work_and_wait(task_pool); diff --git a/source/blender/blenlib/intern/threads.c b/source/blender/blenlib/intern/threads.c index b60981802aa..abf611d1245 100644 --- a/source/blender/blenlib/intern/threads.c +++ b/source/blender/blenlib/intern/threads.c @@ -54,6 +54,8 @@ # include <sys/time.h> #endif +#include "atomic_ops.h" + #if defined(__APPLE__) && defined(_OPENMP) && (__GNUC__ == 4) && (__GNUC_MINOR__ == 2) && !defined(__clang__) # define USE_APPLE_OMP_FIX #endif @@ -124,7 +126,7 @@ static pthread_mutex_t _colormanage_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_mutex_t _fftw_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_mutex_t _view3d_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_t mainid; -static int thread_levels = 0; /* threads can be invoked inside threads */ +static unsigned int thread_levels = 0; /* threads can be invoked inside threads */ static int num_threads_override = 0; /* just a max for security reasons */ @@ -198,9 +200,9 @@ void BLI_init_threads(ListBase *threadbase, void *(*do_thread)(void *), int tot) tslot->avail = 1; } } - - BLI_spin_lock(&_malloc_lock); - if (thread_levels == 0) { + + unsigned int level = atomic_fetch_and_add_u(&thread_levels, 1); + if (level == 0) { MEM_set_lock_callback(BLI_lock_malloc_thread, BLI_unlock_malloc_thread); #ifdef USE_APPLE_OMP_FIX @@ -210,9 +212,6 @@ void BLI_init_threads(ListBase *threadbase, void *(*do_thread)(void *), int tot) thread_tls_data = pthread_getspecific(gomp_tls_key); #endif } - - thread_levels++; - BLI_spin_unlock(&_malloc_lock); } /* amount of available threads */ @@ -331,11 +330,10 @@ void BLI_end_threads(ListBase *threadbase) BLI_freelistN(threadbase); } - BLI_spin_lock(&_malloc_lock); - thread_levels--; - if (thread_levels == 0) + unsigned int level = atomic_sub_and_fetch_u(&thread_levels, 1); + if (level == 0) { MEM_set_lock_callback(NULL, NULL); - BLI_spin_unlock(&_malloc_lock); + } } /* System Information */ @@ -812,26 +810,22 @@ void BLI_thread_queue_wait_finish(ThreadQueue *queue) void BLI_begin_threaded_malloc(void) { - /* Used for debug only */ - /* BLI_assert(thread_levels >= 0); */ - - BLI_spin_lock(&_malloc_lock); - if (thread_levels == 0) { + unsigned int level = atomic_fetch_and_add_u(&thread_levels, 1); + if (level == 0) { MEM_set_lock_callback(BLI_lock_malloc_thread, BLI_unlock_malloc_thread); + /* There is a little chance that two threads will meed to acces to a + * scheduler which was not yet created from main thread. which could + * cause scheduler created multiple times. + */ + BLI_task_scheduler_get(); } - thread_levels++; - BLI_spin_unlock(&_malloc_lock); } void BLI_end_threaded_malloc(void) { - /* Used for debug only */ - /* BLI_assert(thread_levels >= 0); */ - - BLI_spin_lock(&_malloc_lock); - thread_levels--; - if (thread_levels == 0) + unsigned int level = atomic_sub_and_fetch_u(&thread_levels, 1); + if (level == 0) { MEM_set_lock_callback(NULL, NULL); - BLI_spin_unlock(&_malloc_lock); + } } diff --git a/source/blender/blenlib/intern/timecode.c b/source/blender/blenlib/intern/timecode.c index e755a7ae52c..7856bad4d99 100644 --- a/source/blender/blenlib/intern/timecode.c +++ b/source/blender/blenlib/intern/timecode.c @@ -94,11 +94,11 @@ size_t BLI_timecode_string_from_time( * to cope with 'half' frames, etc., which should be fine in most cases */ seconds = (int)time; - frames = iroundf((float)(((double)time - (double)seconds) * fps)); + frames = round_fl_to_int((float)(((double)time - (double)seconds) * fps)); } else { /* seconds (with pixel offset rounding) */ - seconds = iroundf(time); + seconds = round_fl_to_int(time); } switch (timecode_style) { @@ -169,7 +169,7 @@ size_t BLI_timecode_string_from_time( /* precision of decimal part */ const int ms_dp = (power <= 0) ? (1 - power) : 1; - const int ms = iroundf((time - (float)seconds) * 1000.0f); + const int ms = round_fl_to_int((time - (float)seconds) * 1000.0f); rlen = BLI_snprintf_rlen( str, maxncpy, "%s%02d:%02d:%02d,%0*d", neg, hours, minutes, seconds, ms_dp, ms); @@ -183,7 +183,7 @@ size_t BLI_timecode_string_from_time( rlen = BLI_snprintf_rlen(str, maxncpy, "%.*f", 1 - power, time_seconds); } else { - rlen = BLI_snprintf_rlen(str, maxncpy, "%d", iroundf(time_seconds)); + rlen = BLI_snprintf_rlen(str, maxncpy, "%d", round_fl_to_int(time_seconds)); } break; } @@ -250,7 +250,7 @@ size_t BLI_timecode_string_from_time_seconds( rlen = BLI_snprintf_rlen(str, maxncpy, "%.*f", 1 - power, time_seconds); } else { - rlen = BLI_snprintf_rlen(str, maxncpy, "%d", iroundf(time_seconds)); + rlen = BLI_snprintf_rlen(str, maxncpy, "%d", round_fl_to_int(time_seconds)); } return rlen; diff --git a/source/blender/blenlib/intern/winstuff.c b/source/blender/blenlib/intern/winstuff.c index 3b06b7df09a..d6834428376 100644 --- a/source/blender/blenlib/intern/winstuff.c +++ b/source/blender/blenlib/intern/winstuff.c @@ -160,8 +160,6 @@ void RegisterBlendExtension(void) GetSystemDirectory(SysDir, FILE_MAXDIR); #ifdef _WIN64 ThumbHandlerDLL = "BlendThumb64.dll"; -#elif defined(__MINGW32__) - ThumbHandlerDLL = "BlendThumb.dll"; #else IsWow64Process(GetCurrentProcess(), &IsWOW64); if (IsWOW64 == true) |