diff options
Diffstat (limited to 'source/blender/blenlib')
50 files changed, 1670 insertions, 813 deletions
diff --git a/source/blender/blenlib/BLI_alloca.h b/source/blender/blenlib/BLI_alloca.h index fd814940624..b44e6c66d2a 100644 --- a/source/blender/blenlib/BLI_alloca.h +++ b/source/blender/blenlib/BLI_alloca.h @@ -34,8 +34,13 @@ #endif #if defined(__GNUC__) || defined(__clang__) +#if defined(__cplusplus) && (__cplusplus > 199711L) +#define BLI_array_alloca(arr, realsize) \ + (decltype(arr))alloca(sizeof(*arr) * (realsize)) +#else #define BLI_array_alloca(arr, realsize) \ (typeof(arr))alloca(sizeof(*arr) * (realsize)) +#endif #else #define BLI_array_alloca(arr, realsize) \ alloca(sizeof(*arr) * (realsize)) diff --git a/source/blender/blenlib/BLI_buffer.h b/source/blender/blenlib/BLI_buffer.h index 4e5b61da532..6ea9e765c1d 100644 --- a/source/blender/blenlib/BLI_buffer.h +++ b/source/blender/blenlib/BLI_buffer.h @@ -23,27 +23,12 @@ /** \file BLI_buffer.h * \ingroup bli - * - * \note this more or less fills same purpose as BLI_array, but makes - * it much easier to resize the array outside of the function it was - * declared in since. - * - * Usage examples: - * \code{.c} - * BLI_buffer_declare_static(int, my_int_array, BLI_BUFFER_NOP, 32); - * - * BLI_buffer_append(my_int_array, int, 42); - * assert(my_int_array.count == 1); - * assert(BLI_buffer_at(my_int_array, int, 0) == 42); - * - * BLI_buffer_free(&my_int_array); - * \endcode */ typedef struct { void *data; - const int elem_size; - int count, alloc_count; + const size_t elem_size; + size_t count, alloc_count; int flag; } BLI_Buffer; @@ -79,7 +64,7 @@ enum { #define BLI_buffer_at(buffer_, type_, index_) ( \ (((type_ *)(buffer_)->data)[ \ (BLI_assert(sizeof(type_) == (buffer_)->elem_size)), \ - (BLI_assert(index_ >= 0 && index_ < (buffer_)->count)), \ + (BLI_assert((int)(index_) >= 0 && (size_t)(index_) < (buffer_)->count)), \ index_])) #define BLI_buffer_array(buffer_, type_) ( \ @@ -88,6 +73,9 @@ enum { #define BLI_buffer_resize_data(buffer_, type_, new_count_) ( \ (BLI_buffer_resize(buffer_, new_count_), new_count_ ? BLI_buffer_array(buffer_, type_) : NULL)) +#define BLI_buffer_reinit_data(buffer_, type_, new_count_) ( \ + (BLI_buffer_reinit(buffer_, new_count_), new_count_ ? BLI_buffer_array(buffer_, type_) : NULL)) + #define BLI_buffer_append(buffer_, type_, val_) ( \ BLI_buffer_resize(buffer_, (buffer_)->count + 1), \ (BLI_buffer_at(buffer_, type_, (buffer_)->count - 1) = val_) \ @@ -98,7 +86,10 @@ enum { } (void)0 /* Never decreases the amount of memory allocated */ -void BLI_buffer_resize(BLI_Buffer *buffer, int new_count); +void BLI_buffer_resize(BLI_Buffer *buffer, const size_t new_count); + +/* Ensure size, throwing away old data, respecting BLI_BUFFER_USE_CALLOC */ +void BLI_buffer_reinit(BLI_Buffer *buffer, const size_t new_count); /* Does not free the buffer structure itself */ void _bli_buffer_free(BLI_Buffer *buffer); diff --git a/source/blender/blenlib/BLI_fileops.h b/source/blender/blenlib/BLI_fileops.h index 93842731ab7..53ebc81fe22 100644 --- a/source/blender/blenlib/BLI_fileops.h +++ b/source/blender/blenlib/BLI_fileops.h @@ -58,8 +58,10 @@ int BLI_exists(const char *path) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); int BLI_copy(const char *path, const char *to) ATTR_NONNULL(); int BLI_rename(const char *from, const char *to) ATTR_NONNULL(); int BLI_delete(const char *path, bool dir, bool recursive) ATTR_NONNULL(); +#if 0 /* Unused */ int BLI_move(const char *path, const char *to) ATTR_NONNULL(); int BLI_create_symlink(const char *path, const char *to) ATTR_NONNULL(); +#endif /* keep in sync with the definition of struct direntry in BLI_fileops_types.h */ #ifdef WIN32 @@ -87,15 +89,23 @@ bool BLI_is_dir(const char *path) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BLI_is_file(const char *path) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BLI_dir_create_recursive(const char *dir) ATTR_NONNULL(); double BLI_dir_free_space(const char *dir) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); -char *BLI_current_working_dir(char *dir, const size_t maxlen) ATTR_NONNULL(); +char *BLI_current_working_dir(char *dir, const size_t maxlen) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); /* Filelist */ -unsigned int BLI_filelist_dir_contents(const char *dir, struct direntry **filelist); +unsigned int BLI_filelist_dir_contents(const char *dir, struct direntry **r_filelist); +void BLI_filelist_entry_duplicate(struct direntry *dst, const struct direntry *src); void BLI_filelist_duplicate( - struct direntry **dest_filelist, struct direntry *src_filelist, unsigned int nrentries, - void *(*dup_poin)(void *)); -void BLI_filelist_free(struct direntry *filelist, unsigned int nrentries, void (*free_poin)(void *)); + struct direntry **dest_filelist, struct direntry * const src_filelist, const unsigned int nrentries); +void BLI_filelist_entry_free(struct direntry *entry); +void BLI_filelist_free(struct direntry *filelist, const unsigned int nrentries); + +void BLI_filelist_entry_size_to_string(const struct stat *st, const uint64_t sz, const bool compact, char r_size[]); +void BLI_filelist_entry_mode_to_string( + const struct stat *st, const bool compact, char r_mode1[], char r_mode2[], char r_mode3[]); +void BLI_filelist_entry_owner_to_string(const struct stat *st, const bool compact, char r_owner[]); +void BLI_filelist_entry_datetime_to_string( + const struct stat *st, const int64_t ts, const bool compact, char r_time[], char r_date[]); /* Files */ diff --git a/source/blender/blenlib/BLI_fileops_types.h b/source/blender/blenlib/BLI_fileops_types.h index 5a1126b05d2..0cf8c8ddb4a 100644 --- a/source/blender/blenlib/BLI_fileops_types.h +++ b/source/blender/blenlib/BLI_fileops_types.h @@ -39,7 +39,11 @@ typedef unsigned int mode_t; #endif -struct ImBuf; +#define FILELIST_DIRENTRY_SIZE_LEN 16 +#define FILELIST_DIRENTRY_MODE_LEN 4 +#define FILELIST_DIRENTRY_OWNER_LEN 16 +#define FILELIST_DIRENTRY_TIME_LEN 8 +#define FILELIST_DIRENTRY_DATE_LEN 16 struct direntry { mode_t type; @@ -56,19 +60,6 @@ struct direntry { #else struct stat s; #endif - unsigned int flags; - char size[16]; - char mode1[4]; - char mode2[4]; - char mode3[4]; - char owner[16]; - char time[8]; - char date[16]; - char extra[16]; - void *poin; - int nr; - struct ImBuf *image; - unsigned int selflag; /* selection flag */ }; struct dirlink { diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h index 4981b163cdf..0c359c7f090 100644 --- a/source/blender/blenlib/BLI_kdopbvh.h +++ b/source/blender/blenlib/BLI_kdopbvh.h @@ -41,15 +41,13 @@ extern "C" { struct BVHTree; typedef struct BVHTree BVHTree; +#define USE_KDOPBVH_WATERTIGHT typedef struct BVHTreeOverlap { int indexA; int indexB; } BVHTreeOverlap; -/* flags */ -#define BVH_ONQUAD (1 << 0) - 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) */ @@ -62,6 +60,9 @@ typedef struct BVHTreeRay { float origin[3]; /* ray origin */ float direction[3]; /* ray direction */ float radius; /* radius around ray */ +#ifdef USE_KDOPBVH_WATERTIGHT + struct IsectRayPrecalc *isect_precalc; +#endif } BVHTreeRay; typedef struct BVHTreeRayHit { @@ -69,15 +70,23 @@ typedef struct BVHTreeRayHit { float co[3]; /* coordinates of the hit point */ float no[3]; /* normal on hit point */ float dist; /* distance to the hit point */ - int flags; } BVHTreeRayHit; +enum { + /* calculate IsectRayPrecalc data */ + BVH_RAYCAST_WATERTIGHT = (1 << 0), +}; +#define BVH_RAYCAST_DEFAULT (BVH_RAYCAST_WATERTIGHT) + /* callback must update nearest in case it finds a nearest result */ typedef void (*BVHTree_NearestPointCallback)(void *userdata, int index, const float co[3], BVHTreeNearest *nearest); /* 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 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); + /* callback to range search query */ typedef void (*BVHTree_RangeQuery)(void *userdata, int index, float dist_sq); @@ -92,8 +101,12 @@ void BLI_bvhtree_balance(BVHTree *tree); bool BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints); void BLI_bvhtree_update_tree(BVHTree *tree); +int BLI_bvhtree_overlap_thread_num(const BVHTree *tree); + /* collision/overlap: check two trees if they overlap, alloc's *overlap with length of the int return value */ -BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int *r_overlap_tot); +BVHTreeOverlap *BLI_bvhtree_overlap( + const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_tot, + BVHTree_OverlapCallback callback, void *userdata); float BLI_bvhtree_getepsilon(const BVHTree *tree); @@ -102,12 +115,21 @@ float BLI_bvhtree_getepsilon(const BVHTree *tree); int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata); -int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, - BVHTree_RayCastCallback callback, void *userdata); - -/* Calls the callback for every ray intersection */ -int BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3], float radius, - BVHTree_RayCastCallback 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, + int flag); +int BLI_bvhtree_ray_cast( + BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, + BVHTree_RayCastCallback callback, void *userdata); + +int BLI_bvhtree_ray_cast_all_ex( + BVHTree *tree, const float co[3], const float dir[3], float radius, + BVHTree_RayCastCallback callback, void *userdata, + int flag); +int BLI_bvhtree_ray_cast_all( + BVHTree *tree, const float co[3], const float dir[3], float radius, + BVHTree_RayCastCallback callback, void *userdata); float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], const float light_end[3], float pos[3]); diff --git a/source/blender/blenlib/BLI_math_bits.h b/source/blender/blenlib/BLI_math_bits.h index 876c0d92e31..1ac98a682d1 100644 --- a/source/blender/blenlib/BLI_math_bits.h +++ b/source/blender/blenlib/BLI_math_bits.h @@ -40,6 +40,12 @@ MINLINE unsigned short highest_order_bit_s(unsigned short n); MINLINE int count_bits_i(unsigned int n); #endif +MINLINE int float_as_int(float f); +MINLINE unsigned int float_as_uint(float f); +MINLINE float int_as_float(int i); +MINLINE float uint_as_float(unsigned int i); +MINLINE float xor_fl(float x, int y); + #if BLI_MATH_DO_INLINE #include "intern/math_bits_inline.c" #endif diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index 5124da4cd35..dfc51895c77 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -119,14 +119,25 @@ float dist_signed_squared_to_corner_v3v3v3( float closest_to_line_v3(float r[3], const float p[3], const float l1[3], const float l2[3]); float closest_to_line_v2(float r[2], const float p[2], const float l1[2], const float l2[2]); void closest_to_line_segment_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3]); +void closest_to_plane_normalized_v3(float r_close[3], const float plane[4], const float pt[3]); void closest_to_plane_v3(float r_close[3], const float plane[4], const float pt[3]); +void closest_to_plane3_normalized_v3(float r_close[3], const float plane[3], const float pt[3]); +void closest_to_plane3_v3(float r_close[3], const float plane[3], const float pt[3]); /* Set 'r' to the point in triangle (t1, t2, t3) closest to point 'p' */ void closest_on_tri_to_point_v3(float r[3], const float p[3], const float t1[3], const float t2[3], const float t3[3]); +float line_point_factor_v3_ex( + const float p[3], const float l1[3], const float l2[3], + const float epsilon, const float fallback); +float line_point_factor_v3( + const float p[3], const float l1[3], const float l2[3]); -float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3]); -float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2]); +float line_point_factor_v2_ex( + const float p[2], const float l1[2], const float l2[2], + const float epsilon, const float fallback); +float line_point_factor_v2( + const float p[2], const float l1[2], const float l2[2]); float line_plane_factor_v3(const float plane_co[3], const float plane_no[3], const float l1[3], const float l2[3]); @@ -163,36 +174,70 @@ bool isect_line_line_strict_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3], float vi[3], float *r_lambda); -bool isect_ray_plane_v3(const float p1[3], const float d[3], - const float v0[3], const float v1[3], const float v2[3], - float *r_lambda, const int clip); +bool isect_ray_plane_v3( + const float p1[3], const float d[3], + const float plane[4], + float *r_lambda, const bool clip); bool isect_point_planes_v3(float (*planes)[4], int totplane, const float p[3]); bool isect_line_plane_v3(float out[3], const float l1[3], const float l2[3], const float plane_co[3], const float plane_no[3]) ATTR_WARN_UNUSED_RESULT; -bool isect_plane_plane_v3(float r_isect_co[3], float r_isect_no[3], - const float plane_a_co[3], const float plane_a_no[3], - const float plane_b_co[3], const float plane_b_no[3]) ATTR_WARN_UNUSED_RESULT; +bool isect_plane_plane_plane_v3( + const float plane_a[4], const float plane_b[4], const float plane_c[4], + float r_isect_co[3]) ATTR_WARN_UNUSED_RESULT; +bool isect_plane_plane_v3( + const float plane_a[4], const float plane_b[4], + float r_isect_co[3], float r_isect_no[3]) ATTR_WARN_UNUSED_RESULT; /* line/ray triangle */ -bool isect_line_tri_v3(const float p1[3], const float p2[3], - const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2]); -bool isect_line_tri_epsilon_v3(const float p1[3], const float p2[3], - const float v0[3], const float v1[3], const float v2[3], - float *r_lambda, float r_uv[2], const float epsilon); -bool isect_ray_tri_v3(const float p1[3], const float d[3], - const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2]); -bool isect_ray_tri_threshold_v3(const float p1[3], const float d[3], - const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], const float threshold); -bool isect_ray_tri_epsilon_v3(const float p1[3], const float d[3], - const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], const float epsilon); +bool isect_line_tri_v3( + const float p1[3], const float p2[3], + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float r_uv[2]); +bool isect_line_tri_epsilon_v3( + const float p1[3], const float p2[3], + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float r_uv[2], const float epsilon); +bool isect_ray_tri_v3( + const float p1[3], const float d[3], + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float r_uv[2]); +bool isect_ray_tri_threshold_v3( + const float p1[3], const float d[3], + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float r_uv[2], const float threshold); +bool isect_ray_tri_epsilon_v3( + const float p1[3], const float d[3], + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float r_uv[2], const float epsilon); bool isect_tri_tri_epsilon_v3( const float t_a0[3], const float t_a1[3], const float t_a2[3], const float t_b0[3], const float t_b1[3], const float t_b2[3], float r_i1[3], float r_i2[3], const float epsilon); +/* water-tight raycast (requires pre-calculation) */ +struct IsectRayPrecalc { + /* Maximal dimension kz, and orthogonal dimensions. */ + int kx, ky, kz; + + /* Shear constants. */ + float sx, sy, sz; +}; + +void isect_ray_tri_watertight_v3_precalc( + struct IsectRayPrecalc *isect_precalc, const float dir[3]); +bool isect_ray_tri_watertight_v3( + const float P[3], const struct IsectRayPrecalc *isect_precalc, + const float v0[3], const float v1[3], const float v2[3], + float *r_dist, float r_uv[2]); +/* slower version which calculates IsectRayPrecalc each time */ +bool isect_ray_tri_watertight_v3_simple( + const float P[3], const float dir[3], + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float r_uv[2]); + /* point in polygon */ bool isect_point_poly_v2(const float pt[2], const float verts[][2], const unsigned int nr, const bool use_holes); bool isect_point_poly_v2_int(const int pt[2], const int verts[][2], const unsigned int nr, const bool use_holes); diff --git a/source/blender/blenlib/BLI_math_inline.h b/source/blender/blenlib/BLI_math_inline.h index 2bf3b9532dd..840cf24f8cf 100644 --- a/source/blender/blenlib/BLI_math_inline.h +++ b/source/blender/blenlib/BLI_math_inline.h @@ -46,9 +46,9 @@ extern "C" { # 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)) +# define MALWAYS_INLINE static __attribute__((always_inline)) __attribute__((unused)) # else -# define MALWAYS_INLINE static inline __attribute__((always_inline)) +# define MALWAYS_INLINE static inline __attribute__((always_inline)) __attribute__((unused)) # endif # endif #else diff --git a/source/blender/blenlib/BLI_math_matrix.h b/source/blender/blenlib/BLI_math_matrix.h index d7a309e0835..5900e391d3e 100644 --- a/source/blender/blenlib/BLI_math_matrix.h +++ b/source/blender/blenlib/BLI_math_matrix.h @@ -153,10 +153,14 @@ void transpose_m4_m4(float R[4][4], float A[4][4]); int compare_m4m4(float mat1[4][4], float mat2[4][4], float limit); -void normalize_m3(float R[3][3]); -void normalize_m3_m3(float R[3][3], float A[3][3]); -void normalize_m4(float R[4][4]); -void normalize_m4_m4(float R[4][4], float A[4][4]); +void normalize_m3_ex(float R[3][3], float r_scale[3]) ATTR_NONNULL(); +void normalize_m3(float R[3][3]) ATTR_NONNULL(); +void normalize_m3_m3_ex(float R[3][3], float A[3][3], float r_scale[3]) ATTR_NONNULL(); +void normalize_m3_m3(float R[3][3], float A[3][3]) ATTR_NONNULL(); +void normalize_m4_ex(float R[4][4], float r_scale[3]) ATTR_NONNULL(); +void normalize_m4(float R[4][4]) ATTR_NONNULL(); +void normalize_m4_m4_ex(float R[4][4], float A[4][4], float r_scale[3]) ATTR_NONNULL(); +void normalize_m4_m4(float R[4][4], float A[4][4]) ATTR_NONNULL(); void orthogonalize_m3(float R[3][3], int axis); void orthogonalize_m4(float R[4][4], int axis); @@ -215,6 +219,8 @@ void mat4_to_loc_rot_size(float loc[3], float rot[3][3], float size[3], float wm void mat4_to_loc_quat(float loc[3], float quat[4], float wmat[4][4]); void mat4_decompose(float loc[3], float quat[4], float size[3], float wmat[4][4]); +void mat3_polar_decompose(float mat3[3][3], float r_U[3][3], float r_P[3][3]); + void loc_eul_size_to_mat4(float R[4][4], const float loc[3], const float eul[3], const float size[3]); void loc_eulO_size_to_mat4(float R[4][4], @@ -227,6 +233,9 @@ void loc_axisangle_size_to_mat4(float R[4][4], void blend_m3_m3m3(float R[3][3], float A[3][3], float B[3][3], const float t); void blend_m4_m4m4(float R[4][4], float A[4][4], float B[4][4], const float t); +void interp_m3_m3m3(float R[3][3], float A[3][3], float B[3][3], const float t); +void interp_m4_m4m4(float R[4][4], float A[4][4], float B[4][4], const float t); + bool is_negative_m3(float mat[3][3]); bool is_negative_m4(float mat[4][4]); diff --git a/source/blender/blenlib/BLI_math_solvers.h b/source/blender/blenlib/BLI_math_solvers.h index ec9ba5538e2..810c84cc830 100644 --- a/source/blender/blenlib/BLI_math_solvers.h +++ b/source/blender/blenlib/BLI_math_solvers.h @@ -46,6 +46,7 @@ extern "C" { bool BLI_eigen_solve_selfadjoint_m3(const float m3[3][3], float r_eigen_values[3], float r_eigen_vectors[3][3]); +void BLI_svd_m3(const float m3[3][3], float r_U[3][3], float r_S[], float r_V[3][3]); /**************************** Inline Definitions ******************************/ #if 0 /* None so far. */ diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h index 493c285d251..01c00ddb48e 100644 --- a/source/blender/blenlib/BLI_math_vector.h +++ b/source/blender/blenlib/BLI_math_vector.h @@ -61,11 +61,14 @@ MINLINE void swap_v2_v2(float a[2], float b[2]); MINLINE void swap_v3_v3(float a[3], float b[3]); MINLINE void swap_v4_v4(float a[4], float b[4]); +/* unsigned char */ +MINLINE void copy_v2_v2_uchar(unsigned char r[2], const unsigned char a[2]); +MINLINE void copy_v3_v3_uchar(unsigned char r[3], const unsigned char a[3]); +MINLINE void copy_v4_v4_uchar(unsigned char r[4], const unsigned char a[4]); /* char */ MINLINE void copy_v2_v2_char(char r[2], const char a[2]); MINLINE void copy_v3_v3_char(char r[3], const char a[3]); MINLINE void copy_v4_v4_char(char r[4], const char a[4]); - /* short */ MINLINE void copy_v2_v2_short(short r[2], const short a[2]); MINLINE void copy_v3_v3_short(short r[3], const short a[3]); @@ -307,7 +310,7 @@ MINLINE void normal_float_to_short_v3(short r[3], const float n[3]); void minmax_v3v3_v3(float min[3], float max[3], const float vec[3]); void minmax_v2v2_v2(float min[2], float max[2], const float vec[2]); -void minmax_v3v3_v3_array(float r_min[3], float r_max[3], float (*vec_arr)[3], int nbr); +void minmax_v3v3_v3_array(float r_min[3], float r_max[3], const float (*vec_arr)[3], int nbr); void dist_ensure_v3_v3fl(float v1[3], const float v2[3], const float dist); void dist_ensure_v2_v2fl(float v1[2], const float v2[2], const float dist); diff --git a/source/blender/blenlib/BLI_memarena.h b/source/blender/blenlib/BLI_memarena.h index 8d5a7654425..6b1d32b48f2 100644 --- a/source/blender/blenlib/BLI_memarena.h +++ b/source/blender/blenlib/BLI_memarena.h @@ -27,11 +27,6 @@ /** \file BLI_memarena.h * \ingroup bli - * \brief Memory arena ADT. - * \section aboutmemarena Memory Arena - * Memory arena's are commonly used when the program - * needs to quickly allocate lots of little bits of - * data, which are all freed at the same moment. */ #ifndef __BLI_MEMARENA_H__ diff --git a/source/blender/blenlib/BLI_memory_utils.h b/source/blender/blenlib/BLI_memory_utils.h new file mode 100644 index 00000000000..32bbdf8a7b5 --- /dev/null +++ b/source/blender/blenlib/BLI_memory_utils.h @@ -0,0 +1,34 @@ +/* + * ***** 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_MEMORY_UTILS_H__ +#define __BLI_MEMORY_UTILS_H__ + +/** \file BLI_memory_utils.h + * \ingroup bli + * \brief Generic memory manipulation API. + */ + +/* it may be defined already */ +#ifndef __BLI_UTILDEFINES_H__ +bool BLI_memory_is_zero(const void *arr, const size_t size); +#endif + +#endif /* __BLI_MEMORY_UTILS_H__ */ diff --git a/source/blender/blenlib/BLI_mempool.h b/source/blender/blenlib/BLI_mempool.h index 64e673f6db2..0c754f551e0 100644 --- a/source/blender/blenlib/BLI_mempool.h +++ b/source/blender/blenlib/BLI_mempool.h @@ -30,8 +30,6 @@ /** \file BLI_mempool.h * \ingroup bli - * \author Geoffrey Bantle - * \brief Simple fast memory allocator for fixed size chunks. */ #ifdef __cplusplus @@ -46,10 +44,6 @@ struct BLI_mempool_chunk; typedef struct BLI_mempool BLI_mempool; -/* allow_iter allows iteration on this mempool. note: this requires that the - * first four bytes of the elements never contain the character string - * 'free'. use with care.*/ - BLI_mempool *BLI_mempool_create(unsigned int esize, unsigned int totelem, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; void *BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); @@ -82,6 +76,11 @@ typedef struct BLI_mempool_iter { /* flag */ enum { BLI_MEMPOOL_NOP = 0, + /** allow iterating on this mempool. + * + * \note this requires that the first four bytes of the elements never begin with 'free' (FREEWORD). + * \note order of iteration is only assured to be the order of allocation when no chunks have been freed. + */ BLI_MEMPOOL_ALLOW_ITER = (1 << 0), }; diff --git a/source/blender/blenlib/BLI_path_util.h b/source/blender/blenlib/BLI_path_util.h index a344c9d2bc1..1a626ff44bd 100644 --- a/source/blender/blenlib/BLI_path_util.h +++ b/source/blender/blenlib/BLI_path_util.h @@ -99,12 +99,6 @@ int BLI_stringdec(const char *string, char *head, char *start, unsigned short *n 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); -/** - * dir can be any input, like from buttons, and this function - * converts it to a regular full path. - * Also removes garbage from directory paths, like /../ or double slashes etc - */ - /* removes trailing slash */ void BLI_cleanup_file(const char *relabase, char *path) ATTR_NONNULL(2); /* same as above but adds a trailing slash */ @@ -118,25 +112,13 @@ bool BLI_path_make_safe(char *path) ATTR_NONNULL(1); /* go back one directory */ bool BLI_parent_dir(char *path) ATTR_NONNULL(); -/** - * Blender's path code replacement function. - * Bases \a path strings leading with "//" by the - * directory \a basepath, and replaces instances of - * '#' with the \a framenum. Results are written - * back into \a path. - * - * \a path The path to convert - * \a basepath The directory to base relative paths with. - * \a framenum The framenumber to replace the frame code with. - * \retval Returns true if the path was relative (started with "//"). - */ bool BLI_path_abs(char *path, const char *basepath) ATTR_NONNULL(); bool BLI_path_frame(char *path, int frame, int digits) ATTR_NONNULL(); bool BLI_path_frame_range(char *path, int sta, int end, int digits) ATTR_NONNULL(); bool BLI_path_frame_get(char *path, int *r_frame, int *numdigits) ATTR_NONNULL(); -void BLI_path_frame_strip(char *path, bool setsharp, char *ext) ATTR_NONNULL(); +void BLI_path_frame_strip(char *path, bool set_frame_char, char *ext) ATTR_NONNULL(); bool BLI_path_frame_check_chars(const char *path) ATTR_NONNULL(); -bool BLI_path_cwd(char *path) ATTR_NONNULL(); +bool BLI_path_cwd(char *path, const size_t maxlen) ATTR_NONNULL(); void BLI_path_rel(char *file, const char *relfile) ATTR_NONNULL(); bool BLI_path_is_rel(const char *path) ATTR_NONNULL() ATTR_WARN_UNUSED_RESULT; @@ -158,10 +140,6 @@ bool BLI_path_suffix(char *string, size_t maxlen, const char *suffix, const char # define BLI_path_ncmp strncmp #endif -#ifdef WITH_ICONV -void BLI_string_to_utf8(char *original, char *utf_8, const char *code); -#endif - /* these values need to be hardcoded in structs, dna does not recognize defines */ /* also defined in DNA_space_types.h */ #ifndef FILE_MAXDIR @@ -183,5 +161,4 @@ void BLI_string_to_utf8(char *original, char *utf_8, const char *code); } #endif -#endif - +#endif /* __BLI_PATH_UTIL_H__ */ diff --git a/source/blender/blenlib/BLI_rect.h b/source/blender/blenlib/BLI_rect.h index 242ba9f860a..59bf3644912 100644 --- a/source/blender/blenlib/BLI_rect.h +++ b/source/blender/blenlib/BLI_rect.h @@ -66,6 +66,8 @@ void BLI_rctf_interp(struct rctf *rect, const struct rctf *rect_a, const struct //void BLI_rcti_interp(struct rctf *rect, struct rctf *rect_a, struct rctf *rect_b, float fac); bool BLI_rctf_clamp_pt_v(const struct rctf *rect, float xy[2]); bool BLI_rcti_clamp_pt_v(const struct rcti *rect, int xy[2]); +bool BLI_rctf_clamp(struct rctf *rect, const struct rctf *rect_bounds, float r_xy[2]); +bool BLI_rcti_clamp(struct rcti *rect, const struct rcti *rect_bounds, int r_xy[2]); bool BLI_rctf_compare(const struct rctf *rect_a, const struct rctf *rect_b, const float limit); bool BLI_rcti_compare(const struct rcti *rect_a, const struct rcti *rect_b); bool BLI_rctf_isect(const struct rctf *src1, const struct rctf *src2, struct rctf *dest); @@ -92,6 +94,7 @@ void BLI_rcti_union(struct rcti *rcti1, const struct rcti *rcti2); 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_rctf_rotate_expand(rctf *dst, const rctf *src, const float angle); diff --git a/source/blender/blenlib/BLI_threads.h b/source/blender/blenlib/BLI_threads.h index b2ead15af22..6ae833d5ed7 100644 --- a/source/blender/blenlib/BLI_threads.h +++ b/source/blender/blenlib/BLI_threads.h @@ -158,6 +158,7 @@ typedef pthread_cond_t ThreadCondition; void BLI_condition_init(ThreadCondition *cond); void BLI_condition_wait(ThreadCondition *cond, ThreadMutex *mutex); +void BLI_condition_wait_global_mutex(ThreadCondition *cond, const int type); void BLI_condition_notify_one(ThreadCondition *cond); void BLI_condition_notify_all(ThreadCondition *cond); void BLI_condition_end(ThreadCondition *cond); diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h index 65e8dcdba4a..31852fa0f43 100644 --- a/source/blender/blenlib/BLI_utildefines.h +++ b/source/blender/blenlib/BLI_utildefines.h @@ -513,6 +513,17 @@ extern "C" { sizeof(*(struct_var)) - OFFSETOF_STRUCT(struct_var, member)); \ } (void)0 +/* defined + * in memory_utils.c for now. I do not know where we should put it actually... */ +#ifndef __BLI_MEMORY_UTILS_H__ +extern bool BLI_memory_is_zero(const void *arr, const size_t arr_size); +#endif + +#define MEMCMP_STRUCT_OFS_IS_ZERO(struct_var, member) \ + (BLI_memory_is_zero( \ + (char *)(struct_var) + OFFSETOF_STRUCT(struct_var, member), \ + sizeof(*(struct_var)) - OFFSETOF_STRUCT(struct_var, member))) + /* Warning-free macros for storing ints in pointers. Use these _only_ * for storing an int in a pointer, not a pointer in an int (64bit)! */ #define SET_INT_IN_POINTER(i) ((void *)(intptr_t)(i)) @@ -623,9 +634,9 @@ extern "C" { #else # if (defined(__APPLE__) && defined(__ppc__)) /* static inline __attribute__ here breaks osx ppc gcc42 build */ -# define BLI_INLINE static __attribute__((always_inline)) +# define BLI_INLINE static __attribute__((always_inline)) __attribute__((__unused__)) # else -# define BLI_INLINE static inline __attribute__((always_inline)) +# define BLI_INLINE static inline __attribute__((always_inline)) __attribute__((__unused__)) # endif #endif diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index dcf7c3b5d39..0de614a5ca7 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -88,6 +88,7 @@ set(SRC intern/math_statistics.c intern/math_vector.c intern/math_vector_inline.c + intern/memory_utils.c intern/noise.c intern/path_util.c intern/polyfill2d.c @@ -169,6 +170,7 @@ set(SRC BLI_math_statistics.h BLI_math_vector.h BLI_memarena.h + BLI_memory_utils.h BLI_mempool.h BLI_noise.h BLI_path_util.h diff --git a/source/blender/blenlib/intern/BLI_array.c b/source/blender/blenlib/intern/BLI_array.c index 01550ad1008..f681d222e69 100644 --- a/source/blender/blenlib/intern/BLI_array.c +++ b/source/blender/blenlib/intern/BLI_array.c @@ -30,18 +30,12 @@ * \ingroup bli * \brief A (mainly) macro array library. * - * This library needs to be changed to not use macros quite so heavily, - * and to be more of a complete array API. The way arrays are - * exposed to client code as normal C arrays is very useful though, imho. - * it does require some use of macros, however. + * This is an array library, used to manage array (re)allocation. * - * anyway, it's used a bit too heavily to simply rewrite as a - * more "correct" solution without macros entirely. I originally wrote this - * to be very easy to use, without the normal pain of most array libraries. - * This was especially helpful when it came to the massive refactors necessary - * for bmesh, and really helped to speed the process up. - joeedh + * \note This is primarily accessed via macros, + * functions are used to implement some of the internals. * - * little array macro library. example of usage: + * Example usage: * * \code{.c} * int *arr = NULL; @@ -55,9 +49,10 @@ * BLI_array_free(arr); * \endcode * - * arrays are buffered, using double-buffering (so on each reallocation, - * the array size is doubled). supposedly this should give good Big Oh - * behavior, though it may not be the best in practice. + * Arrays are over allocated, so each reallocation the array size is doubled. + * In situations where contiguous array access isn't needed, + * other solutions for allocation are available. + * Consider using on of: BLI_memarena.c, BLI_mempool.c, BLi_stack.c */ #include <string.h> diff --git a/source/blender/blenlib/intern/BLI_dynstr.c b/source/blender/blenlib/intern/BLI_dynstr.c index 80cbce7e256..ecd4a6e6b09 100644 --- a/source/blender/blenlib/intern/BLI_dynstr.c +++ b/source/blender/blenlib/intern/BLI_dynstr.c @@ -258,7 +258,7 @@ int BLI_dynstr_get_len(DynStr *ds) /** * Get a DynStr's contents as a c-string. - * he \a rets argument must be allocated to be at + * The \a rets argument must be allocated to be at * least the size of ``BLI_dynstr_get_len(ds) + 1``. * * \param ds: The DynStr of interest. diff --git a/source/blender/blenlib/intern/BLI_filelist.c b/source/blender/blenlib/intern/BLI_filelist.c index 38a6781c159..527d9934797 100644 --- a/source/blender/blenlib/intern/BLI_filelist.c +++ b/source/blender/blenlib/intern/BLI_filelist.c @@ -182,7 +182,6 @@ static void bli_builddir(struct BuildDirCtx *dir_ctx, const char *dirname) /* Hack around for UNC paths on windows - does not support stat on '\\SERVER\foo\..', sigh... */ file->type |= S_IFDIR; } - file->flags = 0; dir_ctx->nrfiles++; file++; dlink = dlink->next; @@ -210,130 +209,161 @@ static void bli_builddir(struct BuildDirCtx *dir_ctx, const char *dirname) } /** - * Fills in the "mode[123]", "size" and "string" fields in the elements of the files - * array with descriptive details about each item. "string" will have a format similar to "ls -l". + * Scans the contents of the directory named *dirname, and allocates and fills in an + * array of entries describing them in *filelist. + * + * \return The length of filelist array. */ -static void bli_adddirstrings(struct BuildDirCtx *dir_ctx) +unsigned int BLI_filelist_dir_contents(const char *dirname, struct direntry **r_filelist) { - const char *types[8] = {"---", "--x", "-w-", "-wx", "r--", "r-x", "rw-", "rwx"}; - /* symbolic display, indexed by mode field value */ - int num; - double size; - struct direntry *file; - struct tm *tm; - time_t zero = 0; - -#ifndef WIN32 - int mode; -#endif - - for (num = 0, file = dir_ctx->files; num < dir_ctx->nrfiles; num++, file++) { + struct BuildDirCtx dir_ctx; - /* Mode */ -#ifdef WIN32 - BLI_strncpy(file->mode1, types[0], sizeof(file->mode1)); - BLI_strncpy(file->mode2, types[0], sizeof(file->mode2)); - BLI_strncpy(file->mode3, types[0], sizeof(file->mode3)); -#else - mode = file->s.st_mode; + dir_ctx.nrfiles = 0; + dir_ctx.files = NULL; - BLI_strncpy(file->mode1, types[(mode & 0700) >> 6], sizeof(file->mode1)); - BLI_strncpy(file->mode2, types[(mode & 0070) >> 3], sizeof(file->mode2)); - BLI_strncpy(file->mode3, types[(mode & 0007)], sizeof(file->mode3)); + bli_builddir(&dir_ctx, dirname); - if (((mode & S_ISGID) == S_ISGID) && (file->mode2[2] == '-')) file->mode2[2] = 'l'; + if (dir_ctx.files) { + *r_filelist = dir_ctx.files; + } + else { + // keep blender happy. Blender stores this in a variable + // where 0 has special meaning..... + *r_filelist = MEM_mallocN(sizeof(**r_filelist), __func__); + } - if (mode & (S_ISUID | S_ISGID)) { - if (file->mode1[2] == 'x') file->mode1[2] = 's'; - else file->mode1[2] = 'S'; + return dir_ctx.nrfiles; +} - if (file->mode2[2] == 'x') file->mode2[2] = 's'; - } +/** + * Convert given entry's size into human-readable strings. + * + */ +void BLI_filelist_entry_size_to_string( + const struct stat *st, const uint64_t sz, const bool compact, char r_size[FILELIST_DIRENTRY_SIZE_LEN]) +{ + double size; + const char *fmt; + const char *units[] = {"KiB", "MiB", "GiB", "TiB", NULL}; + const char *units_compact[] = {"K", "M", "G", "T", NULL}; + const char *unit = "B"; + + /* + * Seems st_size is signed 32-bit value in *nix and Windows. This + * will buy us some time until files get bigger than 4GB or until + * everyone starts using __USE_FILE_OFFSET64 or equivalent. + */ + size = (double)(st ? st->st_size : sz); + + if (size > 1024.0) { + const char **u; + for (u = compact ? units_compact : units, size /= 1024.0; size > 1024.0 && *(u + 1); u++, size /= 1024.0); + fmt = size > 100.0 ? "%.0f %s" : (size > 10.0 ? "%.1f %s" : "%.2f %s"); + unit = *u; + } + else { + fmt = "%.0f %s"; + } - if (mode & S_ISVTX) { - if (file->mode3[2] == 'x') file->mode3[2] = 't'; - else file->mode3[2] = 'T'; - } -#endif + BLI_snprintf(r_size, sizeof(*r_size) * FILELIST_DIRENTRY_SIZE_LEN, fmt, size, unit); +} +/** + * Convert given entry's modes into human-readable strings. + * + */ +void BLI_filelist_entry_mode_to_string( + const struct stat *st, const bool UNUSED(compact), char r_mode1[FILELIST_DIRENTRY_MODE_LEN], + char r_mode2[FILELIST_DIRENTRY_MODE_LEN], char r_mode3[FILELIST_DIRENTRY_MODE_LEN]) +{ + const char *types[8] = {"---", "--x", "-w-", "-wx", "r--", "r-x", "rw-", "rwx"}; - /* User */ #ifdef WIN32 - strcpy(file->owner, "user"); + BLI_strncpy(r_mode1, types[0], sizeof(*r_mode1) * FILELIST_DIRENTRY_MODE_LEN); + BLI_strncpy(r_mode2, types[0], sizeof(*r_mode2) * FILELIST_DIRENTRY_MODE_LEN); + BLI_strncpy(r_mode3, types[0], sizeof(*r_mode3) * FILELIST_DIRENTRY_MODE_LEN); #else - { - struct passwd *pwuser; - pwuser = getpwuid(file->s.st_uid); - if (pwuser) { - BLI_strncpy(file->owner, pwuser->pw_name, sizeof(file->owner)); - } - else { - BLI_snprintf(file->owner, sizeof(file->owner), "%u", file->s.st_uid); - } - } -#endif + const int mode = st->st_mode; + BLI_strncpy(r_mode1, types[(mode & 0700) >> 6], sizeof(*r_mode1) * FILELIST_DIRENTRY_MODE_LEN); + BLI_strncpy(r_mode2, types[(mode & 0070) >> 3], sizeof(*r_mode2) * FILELIST_DIRENTRY_MODE_LEN); + BLI_strncpy(r_mode3, types[(mode & 0007)], sizeof(*r_mode3) * FILELIST_DIRENTRY_MODE_LEN); - /* Time */ - tm = localtime(&file->s.st_mtime); - // prevent impossible dates in windows - if (tm == NULL) tm = localtime(&zero); - strftime(file->time, sizeof(file->time), "%H:%M", tm); - strftime(file->date, sizeof(file->date), "%d-%b-%y", tm); + if (((mode & S_ISGID) == S_ISGID) && (r_mode2[2] == '-')) r_mode2[2] = 'l'; + if (mode & (S_ISUID | S_ISGID)) { + if (r_mode1[2] == 'x') r_mode1[2] = 's'; + else r_mode1[2] = 'S'; - /* Size */ - /* - * Seems st_size is signed 32-bit value in *nix and Windows. This - * will buy us some time until files get bigger than 4GB or until - * everyone starts using __USE_FILE_OFFSET64 or equivalent. - */ - size = (double)file->s.st_size; + if (r_mode2[2] == 'x') r_mode2[2] = 's'; + } - if (size > 1024.0 * 1024.0 * 1024.0 * 1024.0) { - BLI_snprintf(file->size, sizeof(file->size), "%.1f TiB", size / (1024.0 * 1024.0 * 1024.0 * 1024.0)); - } - else if (size > 1024.0 * 1024.0 * 1024.0) { - BLI_snprintf(file->size, sizeof(file->size), "%.1f GiB", size / (1024.0 * 1024.0 * 1024.0)); - } - else if (size > 1024.0 * 1024.0) { - BLI_snprintf(file->size, sizeof(file->size), "%.1f MiB", size / (1024.0 * 1024.0)); - } - else if (size > 1024.0) { - BLI_snprintf(file->size, sizeof(file->size), "%.1f KiB", size / 1024.0); - } - else { - BLI_snprintf(file->size, sizeof(file->size), "%d B", (int)size); - } + if (mode & S_ISVTX) { + if (r_mode3[2] == 'x') r_mode3[2] = 't'; + else r_mode3[2] = 'T'; } +#endif } /** - * Scans the contents of the directory named *dirname, and allocates and fills in an - * array of entries describing them in *filelist. + * Convert given entry's owner into human-readable strings. * - * \return The length of filelist array. */ -unsigned int BLI_filelist_dir_contents(const char *dirname, struct direntry **filelist) +void BLI_filelist_entry_owner_to_string( + const struct stat *st, const bool UNUSED(compact), char r_owner[FILELIST_DIRENTRY_OWNER_LEN]) { - struct BuildDirCtx dir_ctx; +#ifdef WIN32 + strcpy(r_owner, "unknown"); +#else + struct passwd *pwuser = getpwuid(st->st_uid); - dir_ctx.nrfiles = 0; - dir_ctx.files = NULL; + if (pwuser) { + BLI_strncpy(r_owner, pwuser->pw_name, sizeof(*r_owner) * FILELIST_DIRENTRY_OWNER_LEN); + } + else { + BLI_snprintf(r_owner, sizeof(*r_owner) * FILELIST_DIRENTRY_OWNER_LEN, "%u", st->st_uid); + } +#endif +} - bli_builddir(&dir_ctx, dirname); - bli_adddirstrings(&dir_ctx); +/** + * Convert given entry's time into human-readable strings. + */ +void BLI_filelist_entry_datetime_to_string( + const struct stat *st, const int64_t ts, const bool compact, + char r_time[FILELIST_DIRENTRY_TIME_LEN], char r_date[FILELIST_DIRENTRY_DATE_LEN]) +{ + time_t ts_mtime = ts; + const struct tm *tm = localtime(st ? &st->st_mtime : &ts_mtime); + const time_t zero = 0; - if (dir_ctx.files) { - *filelist = dir_ctx.files; + /* Prevent impossible dates in windows. */ + if (tm == NULL) { + tm = localtime(&zero); } - else { - // keep blender happy. Blender stores this in a variable - // where 0 has special meaning..... - *filelist = MEM_mallocN(sizeof(**filelist), __func__); + + if (r_time) { + strftime(r_time, sizeof(*r_time) * FILELIST_DIRENTRY_TIME_LEN, "%H:%M", tm); + } + if (r_date) { + strftime(r_date, sizeof(*r_date) * FILELIST_DIRENTRY_DATE_LEN, compact ? "%d/%m/%y" : "%d-%b-%y", tm); } +} - return dir_ctx.nrfiles; +/** + * Deep-duplicate of a single direntry. + * + * \param dup_poin If given, called for each non-NULL direntry->poin. Otherwise, pointer is always simply copied over. + */ +void BLI_filelist_entry_duplicate(struct direntry *dst, const struct direntry *src) +{ + *dst = *src; + if (dst->relname) { + dst->relname = MEM_dupallocN(src->relname); + } + if (dst->path) { + dst->path = MEM_dupallocN(src->path); + } } /** @@ -342,48 +372,39 @@ unsigned int BLI_filelist_dir_contents(const char *dirname, struct direntry **f * \param dup_poin If given, called for each non-NULL direntry->poin. Otherwise, pointer is always simply copied over. */ void BLI_filelist_duplicate( - struct direntry **dest_filelist, struct direntry *src_filelist, unsigned int nrentries, - void *(*dup_poin)(void *)) + struct direntry **dest_filelist, struct direntry * const src_filelist, const unsigned int nrentries) { unsigned int i; *dest_filelist = MEM_mallocN(sizeof(**dest_filelist) * (size_t)(nrentries), __func__); for (i = 0; i < nrentries; ++i) { struct direntry * const src = &src_filelist[i]; - struct direntry *dest = &(*dest_filelist)[i]; - *dest = *src; - if (dest->image) { - dest->image = IMB_dupImBuf(src->image); - } - if (dest->relname) { - dest->relname = MEM_dupallocN(src->relname); - } - if (dest->path) { - dest->path = MEM_dupallocN(src->path); - } - if (dest->poin && dup_poin) { - dest->poin = dup_poin(src->poin); - } + struct direntry *dst = &(*dest_filelist)[i]; + BLI_filelist_entry_duplicate(dst, src); + } +} + +/** + * frees storage for a single direntry, not the direntry itself. + */ +void BLI_filelist_entry_free(struct direntry *entry) +{ + if (entry->relname) { + MEM_freeN((void *)entry->relname); + } + if (entry->path) { + MEM_freeN((void *)entry->path); } } /** * frees storage for an array of direntries, including the array itself. */ -void BLI_filelist_free(struct direntry *filelist, unsigned int nrentries, void (*free_poin)(void *)) +void BLI_filelist_free(struct direntry *filelist, const unsigned int nrentries) { unsigned int i; for (i = 0; i < nrentries; ++i) { - struct direntry *entry = filelist + i; - if (entry->image) { - IMB_freeImBuf(entry->image); - } - if (entry->relname) - MEM_freeN((void *)entry->relname); - if (entry->path) - MEM_freeN((void *)entry->path); - if (entry->poin && free_poin) - free_poin(entry->poin); + BLI_filelist_entry_free(&filelist[i]); } if (filelist != NULL) { diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 91ac0ce1c43..7e6dabdffef 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -653,7 +653,7 @@ GHash *BLI_ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcop } /** - * Reverve given ammount of entries (resize \a gh accordingly if needed). + * Reserve given amount of entries (resize \a gh accordingly if needed). */ void BLI_ghash_reserve(GHash *gh, const unsigned int nentries_reserve) { diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c index c0f338a1918..4bd404e5d73 100644 --- a/source/blender/blenlib/intern/BLI_heap.c +++ b/source/blender/blenlib/intern/BLI_heap.c @@ -54,13 +54,13 @@ struct Heap { /* internal functions */ -#define HEAP_PARENT(i) ((i - 1) >> 1) -#define HEAP_LEFT(i) ((i << 1) + 1) -#define HEAP_RIGHT(i) ((i << 1) + 2) -#define HEAP_COMPARE(a, b) (a->value < b->value) +#define HEAP_PARENT(i) (((i) - 1) >> 1) +#define HEAP_LEFT(i) (((i) << 1) + 1) +#define HEAP_RIGHT(i) (((i) << 1) + 2) +#define HEAP_COMPARE(a, b) ((a)->value < (b)->value) #if 0 /* UNUSED */ -#define HEAP_EQUALS(a, b) (a->value == b->value) +#define HEAP_EQUALS(a, b) ((a)->value == (b)->value) #endif BLI_INLINE void heap_swap(Heap *heap, const unsigned int i, const unsigned int j) diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index e4504bcaab1..ddb61e415ac 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -27,6 +27,16 @@ /** \file blender/blenlib/intern/BLI_kdopbvh.c * \ingroup bli + * \brief BVH-tree implementation. + * + * KD-Overlap-BVH, implements a bvh-tree structure with support for: + * + * - Ray-cast: + * #BLI_bvhtree_ray_cast, #BVHRayCastData + * - Nearest point on surface: + * #BLI_bvhtree_find_nearest, #BVHNearestData + * - Overlapping 2 trees: + * #BLI_bvhtree_overlap, #BVHOverlapData_Shared, #BVHOverlapData_Thread */ #include <assert.h> @@ -34,6 +44,7 @@ #include "MEM_guardedalloc.h" #include "BLI_utildefines.h" +#include "BLI_alloca.h" #include "BLI_stack.h" #include "BLI_kdopbvh.h" #include "BLI_math.h" @@ -92,11 +103,22 @@ BLI_STATIC_ASSERT((sizeof(void *) == 8 && sizeof(BVHTree) <= 48) || (sizeof(void *) == 4 && sizeof(BVHTree) <= 32), "over sized") -typedef struct BVHOverlapData { - BVHTree *tree1, *tree2; - struct BLI_Stack *overlap; /* store BVHTreeOverlap */ +/* avoid duplicating vars in BVHOverlapData_Thread */ +typedef struct BVHOverlapData_Shared { + const BVHTree *tree1, *tree2; axis_t start_axis, stop_axis; -} BVHOverlapData; + + /* use for callbacks */ + BVHTree_OverlapCallback callback; + void *userdata; +} BVHOverlapData_Shared; + +typedef struct BVHOverlapData_Thread { + BVHOverlapData_Shared *shared; + struct BLI_Stack *overlap; /* store BVHTreeOverlap */ + /* use for callbacks */ + int thread; +} BVHOverlapData_Thread; typedef struct BVHNearestData { BVHTree *tree; @@ -116,6 +138,12 @@ typedef struct BVHRayCastData { BVHTreeRay ray; + +#ifdef USE_KDOPBVH_WATERTIGHT + struct IsectRayPrecalc isect_precalc; +#endif + + /* initialized by bvhtree_ray_cast_data_precalc */ float ray_dot_axis[13]; float idot_axis[13]; int index[6]; @@ -1030,30 +1058,30 @@ float BLI_bvhtree_getepsilon(const BVHTree *tree) /** * overlap - is it possible for 2 bv's to collide ? */ -static int tree_overlap(BVHNode *node1, BVHNode *node2, axis_t start_axis, axis_t stop_axis) +static bool tree_overlap_test(const BVHNode *node1, const BVHNode *node2, axis_t start_axis, axis_t stop_axis) { - const float *bv1 = node1->bv; - const float *bv2 = node2->bv; - - const float *bv1_end = bv1 + (stop_axis << 1); - - bv1 += start_axis << 1; - bv2 += start_axis << 1; + const float *bv1 = node1->bv + (start_axis << 1); + const float *bv2 = node2->bv + (start_axis << 1); + const float *bv1_end = node1->bv + (stop_axis << 1); /* test all axis if min + max overlap */ for (; bv1 != bv1_end; bv1 += 2, bv2 += 2) { - if ((*(bv1) > *(bv2 + 1)) || (*(bv2) > *(bv1 + 1))) + if ((bv1[0] > bv2[1]) || (bv2[0] > bv1[1])) { return 0; + } } return 1; } -static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2) +static void tree_overlap_traverse( + BVHOverlapData_Thread *data_thread, + const BVHNode *node1, const BVHNode *node2) { + BVHOverlapData_Shared *data = data_thread->shared; int j; - if (tree_overlap(node1, node2, data->start_axis, data->stop_axis)) { + if (tree_overlap_test(node1, node2, data->start_axis, data->stop_axis)) { /* check if node1 is a leaf */ if (!node1->totnode) { /* check if node2 is a leaf */ @@ -1065,33 +1093,97 @@ static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2) } /* both leafs, insert overlap! */ - overlap = BLI_stack_push_r(data->overlap); + overlap = BLI_stack_push_r(data_thread->overlap); overlap->indexA = node1->index; overlap->indexB = node2->index; } else { for (j = 0; j < data->tree2->tree_type; j++) { - if (node2->children[j]) - traverse(data, node1, node2->children[j]); + if (node2->children[j]) { + tree_overlap_traverse(data_thread, node1, node2->children[j]); + } } } } else { for (j = 0; j < data->tree2->tree_type; j++) { - if (node1->children[j]) - traverse(data, node1->children[j], node2); + if (node1->children[j]) { + tree_overlap_traverse(data_thread, node1->children[j], node2); + } } } } - return; } -BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int *r_overlap_tot) +/** + * a version of #tree_overlap_traverse that runs a callback to check if the nodes really intersect. + */ +static void tree_overlap_traverse_cb( + BVHOverlapData_Thread *data_thread, + const BVHNode *node1, const BVHNode *node2) { + BVHOverlapData_Shared *data = data_thread->shared; + int j; + + if (tree_overlap_test(node1, node2, data->start_axis, data->stop_axis)) { + /* check if node1 is a leaf */ + if (!node1->totnode) { + /* check if node2 is a leaf */ + if (!node2->totnode) { + BVHTreeOverlap *overlap; + + if (UNLIKELY(node1 == node2)) { + return; + } + + /* only difference to tree_overlap_traverse! */ + if (data->callback(data->userdata, node1->index, node2->index, data_thread->thread)) { + /* both leafs, insert overlap! */ + overlap = BLI_stack_push_r(data_thread->overlap); + overlap->indexA = node1->index; + overlap->indexB = node2->index; + } + } + else { + for (j = 0; j < data->tree2->tree_type; j++) { + if (node2->children[j]) { + tree_overlap_traverse_cb(data_thread, node1, node2->children[j]); + } + } + } + } + else { + for (j = 0; j < data->tree2->tree_type; j++) { + if (node1->children[j]) { + tree_overlap_traverse_cb(data_thread, node1->children[j], node2); + } + } + } + } +} + +/** + * Use to check the total number of threads #BLI_bvhtree_overlap will use. + * + * \warning Must be the first tree passed to #BLI_bvhtree_overlap! + */ +int BLI_bvhtree_overlap_thread_num(const BVHTree *tree) +{ + return (int)MIN2(tree->tree_type, tree->nodes[tree->totleaf]->totnode); +} + +BVHTreeOverlap *BLI_bvhtree_overlap( + const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_tot, + /* optional callback to test the overlap before adding (must be thread-safe!) */ + BVHTree_OverlapCallback callback, void *userdata) +{ + const int thread_num = BLI_bvhtree_overlap_thread_num(tree1); int j; size_t total = 0; BVHTreeOverlap *overlap = NULL, *to = NULL; - BVHOverlapData **data; + BVHOverlapData_Shared data_shared; + BVHOverlapData_Thread *data = BLI_array_alloca(data, (size_t)thread_num); + axis_t start_axis, stop_axis; /* check for compatibility of both trees (can't compare 14-DOP with 18-DOP) */ if (UNLIKELY((tree1->axis != tree2->axis) && @@ -1101,50 +1193,55 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int BLI_assert(0); return NULL; } + + start_axis = min_axis(tree1->start_axis, tree2->start_axis); + stop_axis = min_axis(tree1->stop_axis, tree2->stop_axis); /* fast check root nodes for collision before doing big splitting + traversal */ - if (!tree_overlap(tree1->nodes[tree1->totleaf], tree2->nodes[tree2->totleaf], - min_axis(tree1->start_axis, tree2->start_axis), - min_axis(tree1->stop_axis, tree2->stop_axis))) - { + if (!tree_overlap_test(tree1->nodes[tree1->totleaf], tree2->nodes[tree2->totleaf], start_axis, stop_axis)) { return NULL; } - data = MEM_mallocN(sizeof(BVHOverlapData *) * tree1->tree_type, "BVHOverlapData_star"); - - for (j = 0; j < tree1->tree_type; j++) { - data[j] = MEM_mallocN(sizeof(BVHOverlapData), "BVHOverlapData"); - - /* init BVHOverlapData */ - data[j]->overlap = BLI_stack_new(sizeof(BVHTreeOverlap), __func__); - data[j]->tree1 = tree1; - data[j]->tree2 = tree2; - data[j]->start_axis = min_axis(tree1->start_axis, tree2->start_axis); - data[j]->stop_axis = min_axis(tree1->stop_axis, tree2->stop_axis); + data_shared.tree1 = tree1; + data_shared.tree2 = tree2; + data_shared.start_axis = start_axis; + data_shared.stop_axis = stop_axis; + + /* can be NULL */ + data_shared.callback = callback; + data_shared.userdata = userdata; + + for (j = 0; j < thread_num; j++) { + /* init BVHOverlapData_Thread */ + data[j].shared = &data_shared; + data[j].overlap = BLI_stack_new(sizeof(BVHTreeOverlap), __func__); + + /* for callback */ + data[j].thread = j; } #pragma omp parallel for private(j) schedule(static) if (tree1->totleaf > KDOPBVH_OMP_LIMIT) - for (j = 0; j < MIN2(tree1->tree_type, tree1->nodes[tree1->totleaf]->totnode); j++) { - traverse(data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]); + for (j = 0; j < thread_num; j++) { + if (callback) { + tree_overlap_traverse_cb(&data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]); + } + else { + tree_overlap_traverse(&data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]); + } } - for (j = 0; j < tree1->tree_type; j++) - total += BLI_stack_count(data[j]->overlap); + for (j = 0; j < thread_num; j++) + total += BLI_stack_count(data[j].overlap); to = overlap = MEM_mallocN(sizeof(BVHTreeOverlap) * total, "BVHTreeOverlap"); - for (j = 0; j < tree1->tree_type; j++) { - unsigned int count = (unsigned int)BLI_stack_count(data[j]->overlap); - BLI_stack_pop_n(data[j]->overlap, to, count); - BLI_stack_free(data[j]->overlap); + for (j = 0; j < thread_num; j++) { + unsigned int count = (unsigned int)BLI_stack_count(data[j].overlap); + BLI_stack_pop_n(data[j].overlap, to, count); + BLI_stack_free(data[j].overlap); to += count; } - - for (j = 0; j < tree1->tree_type; j++) { - MEM_freeN(data[j]); - } - MEM_freeN(data); - + *r_overlap_tot = (unsigned int)total; return overlap; } @@ -1533,13 +1630,46 @@ static void iterative_raycast(BVHRayCastData *data, BVHNode *node) } #endif -int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, - BVHTree_RayCastCallback callback, void *userdata) +static void bvhtree_ray_cast_data_precalc(BVHRayCastData *data, int flag) { int i; + + for (i = 0; i < 3; i++) { + data->ray_dot_axis[i] = dot_v3v3(data->ray.direction, KDOP_AXES[i]); + data->idot_axis[i] = 1.0f / data->ray_dot_axis[i]; + + if (fabsf(data->ray_dot_axis[i]) < FLT_EPSILON) { + data->ray_dot_axis[i] = 0.0; + } + data->index[2 * i] = data->idot_axis[i] < 0.0f ? 1 : 0; + data->index[2 * i + 1] = 1 - data->index[2 * i]; + data->index[2 * i] += 2 * i; + data->index[2 * i + 1] += 2 * i; + } + +#ifdef USE_KDOPBVH_WATERTIGHT + if (flag & BVH_RAYCAST_WATERTIGHT) { + isect_ray_tri_watertight_v3_precalc(&data->isect_precalc, data->ray.direction); + data->ray.isect_precalc = &data->isect_precalc; + } + else { + data->ray.isect_precalc = NULL; + } +#else + UNUSED_VARS(flag); +#endif +} + +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, + int flag) +{ BVHRayCastData data; BVHNode *root = tree->nodes[tree->totleaf]; + BLI_ASSERT_UNIT_V3(dir); + data.tree = tree; data.callback = callback; @@ -1549,24 +1679,11 @@ int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], f copy_v3_v3(data.ray.direction, dir); data.ray.radius = radius; - normalize_v3(data.ray.direction); - - for (i = 0; i < 3; i++) { - data.ray_dot_axis[i] = dot_v3v3(data.ray.direction, KDOP_AXES[i]); - data.idot_axis[i] = 1.0f / data.ray_dot_axis[i]; - - if (fabsf(data.ray_dot_axis[i]) < FLT_EPSILON) { - data.ray_dot_axis[i] = 0.0; - } - data.index[2 * i] = data.idot_axis[i] < 0.0f ? 1 : 0; - data.index[2 * i + 1] = 1 - data.index[2 * i]; - data.index[2 * i] += 2 * i; - data.index[2 * i + 1] += 2 * i; - } - + bvhtree_ray_cast_data_precalc(&data, flag); - if (hit) + if (hit) { memcpy(&data.hit, hit, sizeof(*hit)); + } else { data.hit.index = -1; data.hit.dist = FLT_MAX; @@ -1584,6 +1701,13 @@ int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], f return data.hit.index; } +int BLI_bvhtree_ray_cast( + BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, + BVHTree_RayCastCallback callback, void *userdata) +{ + return BLI_bvhtree_ray_cast_ex(tree, co, dir, radius, hit, callback, userdata, BVH_RAYCAST_DEFAULT); +} + float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], const float light_end[3], float pos[3]) { BVHRayCastData data; @@ -1609,13 +1733,19 @@ float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], cons } -int BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3], float radius, - BVHTree_RayCastCallback callback, void *userdata) +/** + * Calls the callback for every ray intersection + */ +int BLI_bvhtree_ray_cast_all_ex( + BVHTree *tree, const float co[3], const float dir[3], float radius, + BVHTree_RayCastCallback callback, void *userdata, + int flag) { - int i; BVHRayCastData data; BVHNode *root = tree->nodes[tree->totleaf]; + BLI_ASSERT_UNIT_V3(dir); + data.tree = tree; data.callback = callback; @@ -1625,21 +1755,7 @@ int BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3 copy_v3_v3(data.ray.direction, dir); data.ray.radius = radius; - normalize_v3(data.ray.direction); - - for (i = 0; i < 3; i++) { - data.ray_dot_axis[i] = dot_v3v3(data.ray.direction, KDOP_AXES[i]); - data.idot_axis[i] = 1.0f / data.ray_dot_axis[i]; - - if (fabsf(data.ray_dot_axis[i]) < FLT_EPSILON) { - data.ray_dot_axis[i] = 0.0; - } - data.index[2 * i] = data.idot_axis[i] < 0.0f ? 1 : 0; - data.index[2 * i + 1] = 1 - data.index[2 * i]; - data.index[2 * i] += 2 * i; - data.index[2 * i + 1] += 2 * i; - } - + bvhtree_ray_cast_data_precalc(&data, flag); data.hit.index = -1; data.hit.dist = FLT_MAX; @@ -1651,6 +1767,13 @@ int BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3 return data.hit.index; } +int BLI_bvhtree_ray_cast_all( + BVHTree *tree, const float co[3], const float dir[3], float radius, + BVHTree_RayCastCallback callback, void *userdata) +{ + return BLI_bvhtree_ray_cast_all_ex(tree, co, dir, radius, callback, userdata, BVH_RAYCAST_DEFAULT); +} + /** * Range Query - as request by broken :P * diff --git a/source/blender/blenlib/intern/BLI_memarena.c b/source/blender/blenlib/intern/BLI_memarena.c index dd0997c8e1c..2604dbafdc0 100644 --- a/source/blender/blenlib/intern/BLI_memarena.c +++ b/source/blender/blenlib/intern/BLI_memarena.c @@ -28,6 +28,14 @@ /** \file blender/blenlib/intern/BLI_memarena.c * \ingroup bli + * \brief Memory arena ADT. + * \section aboutmemarena Memory Arena + * + * Memory arena's are commonly used when the program + * needs to quickly allocate lots of little bits of data, + * which are all freed at the same moment. + * + * \note Memory can't be freed during the arenas lifetime. */ #include <stdlib.h> diff --git a/source/blender/blenlib/intern/BLI_mempool.c b/source/blender/blenlib/intern/BLI_mempool.c index 8fc5f97221d..7338804c685 100644 --- a/source/blender/blenlib/intern/BLI_mempool.c +++ b/source/blender/blenlib/intern/BLI_mempool.c @@ -27,8 +27,15 @@ /** \file blender/blenlib/intern/BLI_mempool.c * \ingroup bli + * \author Geoffrey Bantle * * Simple, fast memory allocator for allocating many elements of the same size. + * + * Supports: + * + * - Freeing chunks. + * - Iterating over allocated chunks + * (optionally when using the #BLI_MEMPOOL_ALLOW_ITER flag). */ #include <string.h> diff --git a/source/blender/blenlib/intern/array_utils.c b/source/blender/blenlib/intern/array_utils.c index 6c5dc5a7f1e..cef912e42a3 100644 --- a/source/blender/blenlib/intern/array_utils.c +++ b/source/blender/blenlib/intern/array_utils.c @@ -21,6 +21,10 @@ /** \file blender/blenlib/intern/array_utils.c * \ingroup bli * \brief Generic array manipulation API. + * + * \warning Some array operations here are inherently inefficient, + * and only included for the cases where the performance is acceptable. + * Use with care. */ #include <string.h> #include <stdlib.h> @@ -35,7 +39,11 @@ #include "BLI_strict_flags.h" - +/** + *In-place array reverse. + * + * Access via #BLI_array_reverse + */ void _bli_array_reverse(void *arr_v, unsigned int arr_len, size_t arr_stride) { const unsigned int arr_stride_uint = (unsigned int)arr_stride; @@ -54,6 +62,12 @@ void _bli_array_reverse(void *arr_v, unsigned int arr_len, size_t arr_stride) } } +/** + * In-place array wrap. + * (rotate the array one step forward or backwards). + * + * Access via #BLI_array_wrap + */ void _bli_array_wrap(void *arr_v, unsigned int arr_len, size_t arr_stride, int dir) { char *arr = arr_v; @@ -74,6 +88,12 @@ void _bli_array_wrap(void *arr_v, unsigned int arr_len, size_t arr_stride, int d } } +/** + *In-place array permute. + * (re-arrange elements based on an array of indices). + * + * Access via #BLI_array_wrap + */ void _bli_array_permute( void *arr_v, const unsigned int arr_len, const size_t arr_stride, const unsigned int *order, void *arr_temp) @@ -105,6 +125,10 @@ void _bli_array_permute( } /** + * Find the first index of an item in an array. + * + * Access via #BLI_array_findindex + * * \note Not efficient, use for error checks/asserts. */ int _bli_array_findindex(const void *arr, unsigned int arr_len, size_t arr_stride, const void *p) diff --git a/source/blender/blenlib/intern/buffer.c b/source/blender/blenlib/intern/buffer.c index 9e96205a5e8..24b2228c884 100644 --- a/source/blender/blenlib/intern/buffer.c +++ b/source/blender/blenlib/intern/buffer.c @@ -20,30 +20,55 @@ /** \file blender/blenlib/intern/buffer.c * \ingroup bli + * + * Primitive generic buffer library. + * + * - Automatically grow as needed. + * (currently never shrinks). + * - Can be passed between functions. + * - Supports using stack memory by default, + * falling back to heap as needed. + * + * Usage examples: + * \code{.c} + * BLI_buffer_declare_static(int, my_int_array, BLI_BUFFER_NOP, 32); + * + * BLI_buffer_append(my_int_array, int, 42); + * assert(my_int_array.count == 1); + * assert(BLI_buffer_at(my_int_array, int, 0) == 42); + * + * BLI_buffer_free(&my_int_array); + * \endcode + * + * \note this more or less fills same purpose as #BLI_array, + * but supports resizing the array outside of the function + * it was declared in. */ +#include <string.h> + #include "MEM_guardedalloc.h" #include "BLI_buffer.h" #include "BLI_utildefines.h" -#include <string.h> +#include "BLI_strict_flags.h" -static void *buffer_alloc(BLI_Buffer *buffer, int len) +static void *buffer_alloc(BLI_Buffer *buffer, const size_t len) { return ((buffer->flag & BLI_BUFFER_USE_CALLOC) ? MEM_callocN : MEM_mallocN) (buffer->elem_size * len, "BLI_Buffer.data"); } -static void *buffer_realloc(BLI_Buffer *buffer, int len) +static void *buffer_realloc(BLI_Buffer *buffer, const size_t len) { return ((buffer->flag & BLI_BUFFER_USE_CALLOC) ? MEM_recallocN_id : MEM_reallocN_id) (buffer->data, buffer->elem_size * len, "BLI_Buffer.data"); } -void BLI_buffer_resize(BLI_Buffer *buffer, int new_count) +void BLI_buffer_resize(BLI_Buffer *buffer, const size_t new_count) { if (UNLIKELY(new_count > buffer->alloc_count)) { if (buffer->flag & BLI_BUFFER_USE_STATIC) { @@ -65,6 +90,47 @@ void BLI_buffer_resize(BLI_Buffer *buffer, int new_count) buffer->data = buffer_realloc(buffer, buffer->alloc_count); } } + else { + if (buffer->flag & BLI_BUFFER_USE_CALLOC) { + if (new_count > buffer->count) { + memset(POINTER_OFFSET(buffer->data, buffer->elem_size * buffer->count), 0, + buffer->elem_size * (new_count - buffer->count)); + } + } + } + + buffer->count = new_count; +} + +/** + * Similar to #BLI_buffer_resize, but use when the existing data can be: + * - Ignored (malloc'd) + * - Cleared (when BLI_BUFFER_USE_CALLOC is set) + */ +void BLI_buffer_reinit(BLI_Buffer *buffer, size_t new_count) +{ + if (UNLIKELY(new_count > buffer->alloc_count)) { + if ((buffer->flag & BLI_BUFFER_USE_STATIC) == 0) { + if (buffer->data) { + MEM_freeN(buffer->data); + } + } + + if (buffer->alloc_count && (new_count < buffer->alloc_count * 2)) { + buffer->alloc_count *= 2; + } + else { + buffer->alloc_count = new_count; + } + + buffer->data = buffer_alloc(buffer, new_count); + } + else { + if (buffer->flag & BLI_BUFFER_USE_CALLOC) { + memset(buffer->data, 0, + buffer->elem_size * new_count); + } + } buffer->count = new_count; } diff --git a/source/blender/blenlib/intern/fileops.c b/source/blender/blenlib/intern/fileops.c index bf9daea7f7c..ef9a7c0603f 100644 --- a/source/blender/blenlib/intern/fileops.c +++ b/source/blender/blenlib/intern/fileops.c @@ -193,15 +193,25 @@ bool BLI_file_is_writable(const char *filename) /** * Creates the file with nothing in it, or updates its last-modified date if it already exists. - * Returns true if successful. (like the unix touch command) + * Returns true if successful (like the unix touch command). */ bool BLI_file_touch(const char *file) { FILE *f = BLI_fopen(file, "r+b"); + if (f != NULL) { int c = getc(f); - rewind(f); - putc(c, f); + + if (c == EOF) { + /* Empty file, reopen in truncate write mode... */ + fclose(f); + f = BLI_fopen(file, "w+b"); + } + else { + /* Otherwise, rewrite first byte. */ + rewind(f); + putc(c, f); + } } else { f = BLI_fopen(file, "wb"); @@ -220,10 +230,10 @@ static void callLocalErrorCallBack(const char *err) printf("%s\n", err); } -static char str[MAXPATHLEN + 12]; - FILE *BLI_fopen(const char *filename, const char *mode) { + BLI_assert(!BLI_path_is_rel(filename)); + return ufopen(filename, mode); } @@ -247,41 +257,42 @@ void *BLI_gzopen(const char *filename, const char *mode) { gzFile gzfile; - if (!filename || !mode) { - return 0; - } - else { - /* xxx Creates file before transcribing the path */ - if (mode[0] == 'w') - fclose(ufopen(filename, "a")); + BLI_assert(!BLI_path_is_rel(filename)); - /* temporary #if until we update all libraries to 1.2.7 - * for correct wide char path handling */ + /* xxx Creates file before transcribing the path */ + if (mode[0] == 'w') + fclose(ufopen(filename, "a")); + + /* temporary #if until we update all libraries to 1.2.7 + * for correct wide char path handling */ #if ZLIB_VERNUM >= 0x1270 && !defined(FREE_WINDOWS) - UTF16_ENCODE(filename); + UTF16_ENCODE(filename); - gzfile = gzopen_w(filename_16, mode); + gzfile = gzopen_w(filename_16, mode); - UTF16_UN_ENCODE(filename); + UTF16_UN_ENCODE(filename); #else - { - char short_name[256]; - BLI_get_short_name(short_name, filename); - gzfile = gzopen(short_name, mode); - } -#endif + { + char short_name[256]; + BLI_get_short_name(short_name, filename); + gzfile = gzopen(short_name, mode); } +#endif return gzfile; } int BLI_open(const char *filename, int oflag, int pmode) { + BLI_assert(!BLI_path_is_rel(filename)); + return uopen(filename, oflag, pmode); } int BLI_access(const char *filename, int mode) { + BLI_assert(!BLI_path_is_rel(filename)); + return uaccess(filename, mode); } @@ -342,7 +353,7 @@ static bool delete_recursive(const char *dir) err = true; } - BLI_filelist_free(filelist, nbr, NULL); + BLI_filelist_free(filelist, nbr); return err; } @@ -351,6 +362,8 @@ int BLI_delete(const char *file, bool dir, bool recursive) { int err; + BLI_assert(!BLI_path_is_rel(file)); + if (recursive) { err = delete_recursive(file); } @@ -365,6 +378,7 @@ int BLI_delete(const char *file, bool dir, bool recursive) #if 0 int BLI_move(const char *file, const char *to) { + char str[MAXPATHLEN + 12]; int err; /* windows doesn't support moving to a directory @@ -396,6 +410,7 @@ int BLI_move(const char *file, const char *to) int BLI_copy(const char *file, const char *to) { + char str[MAXPATHLEN + 12]; int err; /* windows doesn't support copying to a directory @@ -424,13 +439,16 @@ int BLI_copy(const char *file, const char *to) return err; } +#if 0 int BLI_create_symlink(const char *file, const char *to) { + /* See patch from T30870, should this ever become needed. */ callLocalErrorCallBack("Linking files is unsupported on Windows"); (void)file; (void)to; return 1; } +#endif /** \return true on success (i.e. given path now exists on FS), false otherwise. */ bool BLI_dir_create_recursive(const char *dirname) @@ -552,7 +570,7 @@ static int recursive_operation(const char *startfrom, const char *startto, char *from_path = NULL, *to_path = NULL; struct dirent **dirlist = NULL; size_t from_alloc_len = -1, to_alloc_len = -1; - int i, n, ret = 0; + int i, n = 0, ret = 0; do { /* once */ /* ensure there's no trailing slash in file path */ @@ -968,10 +986,12 @@ int BLI_copy(const char *file, const char *to) return ret; } +#if 0 int BLI_create_symlink(const char *file, const char *to) { return symlink(to, file); } +#endif /** \return true on success (i.e. given path now exists on FS), false otherwise. */ bool BLI_dir_create_recursive(const char *dirname) diff --git a/source/blender/blenlib/intern/math_bits_inline.c b/source/blender/blenlib/intern/math_bits_inline.c index 11ee6e7fa5b..82d7e2114c2 100644 --- a/source/blender/blenlib/intern/math_bits_inline.c +++ b/source/blender/blenlib/intern/math_bits_inline.c @@ -56,4 +56,37 @@ MINLINE int count_bits_i(unsigned int i) } #endif +MINLINE int float_as_int(float f) +{ + union { int i; float f; } u; + u.f = f; + return u.i; +} + +MINLINE unsigned int float_as_uint(float f) +{ + union { unsigned int i; float f; } u; + u.f = f; + return u.i; +} + +MINLINE float int_as_float(int i) +{ + union { int i; float f; } u; + u.i = i; + return u.f; +} + +MINLINE float uint_as_float(unsigned int i) +{ + union { unsigned int i; float f; } u; + u.i = i; + return u.f; +} + +MINLINE float xor_fl(float x, int y) +{ + return int_as_float(float_as_int(x) ^ y); +} + #endif /* __MATH_BITS_INLINE_C__ */ diff --git a/source/blender/blenlib/intern/math_color_blend_inline.c b/source/blender/blenlib/intern/math_color_blend_inline.c index 73a7259ddcd..048ab71c6dc 100644 --- a/source/blender/blenlib/intern/math_color_blend_inline.c +++ b/source/blender/blenlib/intern/math_color_blend_inline.c @@ -36,7 +36,7 @@ #ifndef __MATH_COLOR_BLEND_INLINE_C__ #define __MATH_COLOR_BLEND_INLINE_C__ -/* don't add any saturation to a completly black and white image */ +/* don't add any saturation to a completely black and white image */ #define EPS_SATURATION 0.0005f #define EPS_ALPHA 0.0005f @@ -72,7 +72,7 @@ MINLINE void blend_color_mix_byte(unsigned char dst[4], const unsigned char src1 } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -94,7 +94,7 @@ MINLINE void blend_color_add_byte(unsigned char dst[4], const unsigned char src1 } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -116,7 +116,7 @@ MINLINE void blend_color_sub_byte(unsigned char dst[4], const unsigned char src1 } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -139,7 +139,7 @@ MINLINE void blend_color_mul_byte(unsigned char dst[4], const unsigned char src1 } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -162,7 +162,7 @@ MINLINE void blend_color_lighten_byte(unsigned char dst[4], const unsigned char } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -185,7 +185,7 @@ MINLINE void blend_color_darken_byte(unsigned char dst[4], const unsigned char s } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -202,7 +202,7 @@ MINLINE void blend_color_erase_alpha_byte(unsigned char dst[4], const unsigned c } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -219,7 +219,7 @@ MINLINE void blend_color_add_alpha_byte(unsigned char dst[4], const unsigned cha } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -244,7 +244,7 @@ MINLINE void blend_color_overlay_byte(unsigned char dst[4], unsigned const char } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -270,7 +270,7 @@ MINLINE void blend_color_hardlight_byte(unsigned char dst[4], unsigned const cha } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -289,7 +289,7 @@ MINLINE void blend_color_burn_byte(unsigned char dst[4], unsigned const char src } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -308,7 +308,7 @@ MINLINE void blend_color_linearburn_byte(unsigned char dst[4], unsigned const ch } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -327,7 +327,7 @@ MINLINE void blend_color_dodge_byte(unsigned char dst[4], unsigned const char sr } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -345,7 +345,7 @@ MINLINE void blend_color_screen_byte(unsigned char dst[4], unsigned const char s } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -371,7 +371,7 @@ MINLINE void blend_color_softlight_byte(unsigned char dst[4], unsigned const cha } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -397,7 +397,7 @@ MINLINE void blend_color_pinlight_byte(unsigned char dst[4], unsigned const char } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -423,7 +423,7 @@ MINLINE void blend_color_linearlight_byte(unsigned char dst[4], unsigned const c } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -455,7 +455,7 @@ MINLINE void blend_color_vividlight_byte(unsigned char dst[4], unsigned const ch } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -475,7 +475,7 @@ MINLINE void blend_color_difference_byte(unsigned char dst[4], unsigned const ch } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -494,7 +494,7 @@ MINLINE void blend_color_exclusion_byte(unsigned char dst[4], unsigned const cha } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -521,7 +521,7 @@ MINLINE void blend_color_color_byte(unsigned char dst[4], unsigned const char sr } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -547,7 +547,7 @@ MINLINE void blend_color_hue_byte(unsigned char dst[4], unsigned const char src1 } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -575,7 +575,7 @@ MINLINE void blend_color_saturation_byte(unsigned char dst[4], unsigned const ch } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -601,7 +601,7 @@ MINLINE void blend_color_luminosity_byte(unsigned char dst[4], unsigned const ch } else { /* no op */ - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } @@ -621,7 +621,7 @@ MINLINE void blend_color_interpolate_byte(unsigned char dst[4], const unsigned c dst[3] = (unsigned char)divide_round_i(tmp, 255); } else { - copy_v4_v4_char((char *)dst, (char *)src1); + copy_v4_v4_uchar(dst, src1); } } diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index e05cd7c300b..e5fb5533728 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -30,6 +30,7 @@ #include "MEM_guardedalloc.h" #include "BLI_math.h" +#include "BLI_math_bits.h" #include "BLI_utildefines.h" #include "BLI_strict_flags.h" @@ -307,72 +308,25 @@ float volume_tetrahedron_signed_v3(const float v1[3], const float v2[3], const f * using Hesse formula, NO LINE PIECE! */ float dist_squared_to_line_v2(const float p[2], const float l1[2], const float l2[2]) { - float a[2], deler; + float closest[2]; - a[0] = l1[1] - l2[1]; - a[1] = l2[0] - l1[0]; + closest_to_line_v2(closest, p, l1, l2); - deler = len_squared_v2(a); - - if (deler != 0.0f) { - float f = ((p[0] - l1[0]) * a[0] + - (p[1] - l1[1]) * a[1]); - return (f * f) / deler; - } - else { - return 0.0f; - } + return len_squared_v2v2(closest, p); } float dist_to_line_v2(const float p[2], const float l1[2], const float l2[2]) { - float a[2], deler; - - a[0] = l1[1] - l2[1]; - a[1] = l2[0] - l1[0]; - - deler = len_squared_v2(a); - - if (deler != 0.0f) { - float f = ((p[0] - l1[0]) * a[0] + - (p[1] - l1[1]) * a[1]); - return fabsf(f) / sqrtf(deler); - } - else { - return 0.0f; - } + return sqrtf(dist_squared_to_line_v2(p, l1, l2)); } /* distance p to line-piece v1-v2 */ float dist_squared_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2]) { - float lambda, rc[2], pt[2], len; + float closest[2]; - rc[0] = l2[0] - l1[0]; - rc[1] = l2[1] - l1[1]; - len = rc[0] * rc[0] + rc[1] * rc[1]; - if (len == 0.0f) { - rc[0] = p[0] - l1[0]; - rc[1] = p[1] - l1[1]; - return (rc[0] * rc[0] + rc[1] * rc[1]); - } + closest_to_line_segment_v2(closest, p, l1, l2); - lambda = (rc[0] * (p[0] - l1[0]) + rc[1] * (p[1] - l1[1])) / len; - if (lambda <= 0.0f) { - pt[0] = l1[0]; - pt[1] = l1[1]; - } - else if (lambda >= 1.0f) { - pt[0] = l2[0]; - pt[1] = l2[1]; - } - else { - pt[0] = lambda * rc[0] + l1[0]; - pt[1] = lambda * rc[1] + l1[1]; - } - - rc[0] = pt[0] - p[0]; - rc[1] = pt[1] - p[1]; - return (rc[0] * rc[0] + rc[1] * rc[1]); + return len_squared_v2v2(closest, p); } float dist_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2]) @@ -426,6 +380,27 @@ void closest_to_plane_v3(float r_close[3], const float plane[4], const float pt[ madd_v3_v3v3fl(r_close, pt, plane, -side / len_sq); } +void closest_to_plane_normalized_v3(float r_close[3], const float plane[4], const float pt[3]) +{ + const float side = plane_point_side_v3(plane, pt); + BLI_ASSERT_UNIT_V3(plane); + madd_v3_v3v3fl(r_close, pt, plane, -side); +} + +void closest_to_plane3_v3(float r_close[3], const float plane[3], const float pt[3]) +{ + const float len_sq = len_squared_v3(plane); + const float side = dot_v3v3(plane, pt); + madd_v3_v3v3fl(r_close, pt, plane, -side / len_sq); +} + +void closest_to_plane3_normalized_v3(float r_close[3], const float plane[3], const float pt[3]) +{ + const float side = dot_v3v3(plane, pt); + BLI_ASSERT_UNIT_V3(plane); + madd_v3_v3v3fl(r_close, pt, plane, -side); +} + float dist_signed_squared_to_plane_v3(const float pt[3], const float plane[4]) { const float len_sq = len_squared_v3(plane); @@ -500,17 +475,17 @@ float dist_to_line_segment_v3(const float p[3], const float l1[3], const float l return sqrtf(dist_squared_to_line_segment_v3(p, l1, l2)); } -float dist_squared_to_line_v3(const float v1[3], const float l1[3], const float l2[3]) +float dist_squared_to_line_v3(const float p[3], const float l1[3], const float l2[3]) { float closest[3]; - closest_to_line_v3(closest, v1, l1, l2); + closest_to_line_v3(closest, p, l1, l2); - return len_squared_v3v3(closest, v1); + return len_squared_v3v3(closest, p); } -float dist_to_line_v3(const float v1[3], const float l1[3], const float l2[3]) +float dist_to_line_v3(const float p[3], const float l1[3], const float l2[3]) { - return sqrtf(dist_squared_to_line_v3(v1, l1, l2)); + return sqrtf(dist_squared_to_line_v3(p, l1, l2)); } /** @@ -522,7 +497,7 @@ float dist_to_line_v3(const float v1[3], const float l1[3], const float l2[3]) * \note the distance from \a v1 & \a v3 to \a v2 doesnt matter * (it just defines the planes). * - * \return the lowest squared distance to eithe of the planes. + * \return the lowest squared distance to either of the planes. * where ``(return < 0.0)`` is outside. * * <pre> @@ -572,7 +547,7 @@ float dist_signed_squared_to_corner_v3v3v3( dist_a = dist_signed_squared_to_plane_v3(p, plane_a); dist_b = dist_signed_squared_to_plane_v3(p, plane_b); #else - /* calculate without he planes 4th component to avoid float precision issues */ + /* calculate without the planes 4th component to avoid float precision issues */ sub_v3_v3v3(s_p_v2, p, v2); dist_a = dist_signed_squared_to_plane3_v3(s_p_v2, plane_a); @@ -1155,9 +1130,10 @@ int isect_point_quad_v2(const float pt[2], const float v1[2], const float v2[2], * test if the line starting at p1 ending at p2 intersects the triangle v0..v2 * return non zero if it does */ -bool isect_line_tri_v3(const float p1[3], const float p2[3], - const float v0[3], const float v1[3], const float v2[3], - float *r_lambda, float r_uv[2]) +bool isect_line_tri_v3( + const float p1[3], const float p2[3], + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float r_uv[2]) { float p[3], s[3], d[3], e1[3], e2[3], q[3]; @@ -1194,9 +1170,10 @@ bool isect_line_tri_v3(const float p1[3], const float p2[3], } /* like isect_line_tri_v3, but allows epsilon tolerance around triangle */ -bool isect_line_tri_epsilon_v3(const float p1[3], const float p2[3], - const float v0[3], const float v1[3], const float v2[3], - float *r_lambda, float r_uv[2], const float epsilon) +bool isect_line_tri_epsilon_v3( + const float p1[3], const float p2[3], + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float r_uv[2], const float epsilon) { float p[3], s[3], d[3], e1[3], e2[3], q[3]; @@ -1236,10 +1213,14 @@ bool isect_line_tri_epsilon_v3(const float p1[3], const float p2[3], * test if the ray starting at p1 going in d direction intersects the triangle v0..v2 * return non zero if it does */ -bool isect_ray_tri_v3(const float p1[3], const float d[3], - const float v0[3], const float v1[3], const float v2[3], - float *r_lambda, float r_uv[2]) +bool isect_ray_tri_v3( + const float p1[3], const float d[3], + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float r_uv[2]) { + /* note: these values were 0.000001 in 2.4x but for projection snapping on + * a human head (1BU == 1m), subsurf level 2, this gave many errors - campbell */ + const float epsilon = 0.00000001f; float p[3], s[3], e1[3], e2[3], q[3]; float a, f, u, v; @@ -1248,9 +1229,7 @@ bool isect_ray_tri_v3(const float p1[3], const float d[3], cross_v3_v3v3(p, d, e2); a = dot_v3v3(e1, p); - /* note: these values were 0.000001 in 2.4x but for projection snapping on - * a human head (1BU == 1m), subsurf level 2, this gave many errors - campbell */ - if ((a > -0.00000001f) && (a < 0.00000001f)) return false; + if ((a > -epsilon) && (a < epsilon)) return false; f = 1.0f / a; sub_v3_v3v3(s, p1, v0); @@ -1277,42 +1256,34 @@ bool isect_ray_tri_v3(const float p1[3], const float d[3], /** * if clip is nonzero, will only return true if lambda is >= 0.0 * (i.e. intersection point is along positive d) + * + * \note #line_plane_factor_v3() shares logic. */ -bool isect_ray_plane_v3(const float p1[3], const float d[3], - const float v0[3], const float v1[3], const float v2[3], - float *r_lambda, const int clip) +bool isect_ray_plane_v3( + const float p1[3], const float d[3], + const float plane[4], + float *r_lambda, const bool clip) { - float p[3], s[3], e1[3], e2[3], q[3]; - float a, f; - /* float u, v; */ /*UNUSED*/ - - sub_v3_v3v3(e1, v1, v0); - sub_v3_v3v3(e2, v2, v0); - - cross_v3_v3v3(p, d, e2); - a = dot_v3v3(e1, p); - /* note: these values were 0.000001 in 2.4x but for projection snapping on - * a human head (1BU == 1m), subsurf level 2, this gave many errors - campbell */ - if ((a > -0.00000001f) && (a < 0.00000001f)) return false; - f = 1.0f / a; - - sub_v3_v3v3(s, p1, v0); - - /* u = f * dot_v3v3(s, p); */ /*UNUSED*/ - - cross_v3_v3v3(q, s, e1); - - /* v = f * dot_v3v3(d, q); */ /*UNUSED*/ - - *r_lambda = f * dot_v3v3(e2, q); - if (clip && (*r_lambda < 0.0f)) return false; + float h[3], plane_co[3]; + float dot; + dot = dot_v3v3(plane, d); + if (dot == 0.0f) { + return false; + } + mul_v3_v3fl(plane_co, plane, (-plane[3] / len_squared_v3(plane))); + sub_v3_v3v3(h, p1, plane_co); + *r_lambda = -dot_v3v3(plane, h) / dot; + if (clip && (*r_lambda < 0.0f)) { + return false; + } return true; } -bool isect_ray_tri_epsilon_v3(const float p1[3], const float d[3], - const float v0[3], const float v1[3], const float v2[3], - float *r_lambda, float uv[2], const float epsilon) +bool isect_ray_tri_epsilon_v3( + const float p1[3], const float d[3], + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float uv[2], const float epsilon) { float p[3], s[3], e1[3], e2[3], q[3]; float a, f, u, v; @@ -1322,7 +1293,7 @@ bool isect_ray_tri_epsilon_v3(const float p1[3], const float d[3], cross_v3_v3v3(p, d, e2); a = dot_v3v3(e1, p); - if (a == 0.0f) return 0; + if (a == 0.0f) return false; f = 1.0f / a; sub_v3_v3v3(s, p1, v0); @@ -1346,10 +1317,132 @@ bool isect_ray_tri_epsilon_v3(const float p1[3], const float d[3], return true; } -bool isect_ray_tri_threshold_v3(const float p1[3], const float d[3], - const float v0[3], const float v1[3], const float v2[3], - float *r_lambda, float r_uv[2], const float threshold) +void isect_ray_tri_watertight_v3_precalc(struct IsectRayPrecalc *isect_precalc, const float dir[3]) { + float inv_dir_z; + + /* Calculate dimension where the ray direction is maximal. */ + int kz = axis_dominant_v3_single(dir); + int kx = (kz != 2) ? (kz + 1) : 0; + int ky = (kx != 2) ? (kx + 1) : 0; + + /* Swap kx and ky dimensions to preserve winding direction of triangles. */ + if (dir[kz] < 0.0f) { + SWAP(int, kx, ky); + } + + /* Calculate the shear constants. */ + inv_dir_z = 1.0f / dir[kz]; + isect_precalc->sx = dir[kx] * inv_dir_z; + isect_precalc->sy = dir[ky] * inv_dir_z; + isect_precalc->sz = inv_dir_z; + + /* Store the dimensions. */ + isect_precalc->kx = kx; + isect_precalc->ky = ky; + isect_precalc->kz = kz; +} + +bool isect_ray_tri_watertight_v3( + const float p[3], const struct IsectRayPrecalc *isect_precalc, + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float r_uv[2]) +{ + const int kx = isect_precalc->kx; + const int ky = isect_precalc->ky; + const int kz = isect_precalc->kz; + const float sx = isect_precalc->sx; + const float sy = isect_precalc->sy; + const float sz = isect_precalc->sz; + + /* Calculate vertices relative to ray origin. */ + const float a[3] = {v0[0] - p[0], v0[1] - p[1], v0[2] - p[2]}; + const float b[3] = {v1[0] - p[0], v1[1] - p[1], v1[2] - p[2]}; + const float c[3] = {v2[0] - p[0], v2[1] - p[1], v2[2] - p[2]}; + + const float a_kx = a[kx], a_ky = a[ky], a_kz = a[kz]; + const float b_kx = b[kx], b_ky = b[ky], b_kz = b[kz]; + const float c_kx = c[kx], c_ky = c[ky], c_kz = c[kz]; + + /* Perform shear and scale of vertices. */ + const float ax = a_kx - sx * a_kz; + const float ay = a_ky - sy * a_kz; + const float bx = b_kx - sx * b_kz; + const float by = b_ky - sy * b_kz; + const float cx = c_kx - sx * c_kz; + const float cy = c_ky - sy * c_kz; + + /* Calculate scaled barycentric coordinates. */ + float u = cx * by - cy * bx; + int sign_mask = (float_as_int(u) & (int)0x80000000); + float v = ax * cy - ay * cx; + float w, det; + + if (sign_mask != (float_as_int(v) & (int)0x80000000)) { + return false; + } + w = bx * ay - by * ax; + if (sign_mask != (float_as_int(w) & (int)0x80000000)) { + return false; + } + + /* Calculate determinant. */ + det = u + v + w; + if (UNLIKELY(det == 0.0f)) { + return false; + } + else { + /* Calculate scaled z-coordinates of vertices and use them to calculate + * the hit distance. + */ + const float t = (u * a_kz + v * b_kz + w * c_kz) * sz; + const float sign_t = xor_fl(t, sign_mask); + if ((sign_t < 0.0f) + /* differ from Cycles, don't read r_lambda's original value + * otherwise we won't match any of the other intersect functions here... + * which would be confusing */ +#if 0 + || + (sign_T > *r_lambda * xor_signmask(det, sign_mask)) +#endif + ) + { + return false; + } + else { + /* Normalize u, v and t. */ + const float inv_det = 1.0f / det; + if (r_uv) { + r_uv[0] = u * inv_det; + r_uv[1] = v * inv_det; + } + *r_lambda = t * inv_det; + return true; + } + } +} + +bool isect_ray_tri_watertight_v3_simple( + const float P[3], const float dir[3], + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float r_uv[2]) +{ + struct IsectRayPrecalc isect_precalc; + isect_ray_tri_watertight_v3_precalc(&isect_precalc, dir); + return isect_ray_tri_watertight_v3(P, &isect_precalc, v0, v1, v2, r_lambda, r_uv); +} + +#if 0 /* UNUSED */ +/** + * A version of #isect_ray_tri_v3 which takes a threshold argument + * so rays slightly outside the triangle to be considered as intersecting. + */ +bool isect_ray_tri_threshold_v3( + const float p1[3], const float d[3], + const float v0[3], const float v1[3], const float v2[3], + float *r_lambda, float r_uv[2], const float threshold) +{ + const float epsilon = 0.00000001f; float p[3], s[3], e1[3], e2[3], q[3]; float a, f, u, v; float du, dv; @@ -1359,7 +1452,7 @@ bool isect_ray_tri_threshold_v3(const float p1[3], const float d[3], cross_v3_v3v3(p, d, e2); a = dot_v3v3(e1, p); - if ((a > -0.000001f) && (a < 0.000001f)) return false; + if ((a > -epsilon) && (a < epsilon)) return false; f = 1.0f / a; sub_v3_v3v3(s, p1, v0); @@ -1400,6 +1493,7 @@ bool isect_ray_tri_threshold_v3(const float p1[3], const float d[3], return true; } +#endif /** * Check if a point is behind all planes. @@ -1451,28 +1545,90 @@ bool isect_line_plane_v3(float out[3], } /** + * Intersect three planes, return the point where all 3 meet. + * See Graphics Gems 1 pg 305 + * + * \param plane_a, plane_b, plane_c: Planes. + * \param r_isect_co: The resulting intersection point. + */ +bool isect_plane_plane_plane_v3( + const float plane_a[4], const float plane_b[4], const float plane_c[4], + float r_isect_co[3]) +{ + float det; + + det = determinant_m3(UNPACK3(plane_a), UNPACK3(plane_b), UNPACK3(plane_c)); + + if (det != 0.0f) { + float tmp[3]; + + /* (plane_b.xyz.cross(plane_c.xyz) * -plane_a[3] + + * plane_c.xyz.cross(plane_a.xyz) * -plane_b[3] + + * plane_a.xyz.cross(plane_b.xyz) * -plane_c[3]) / det; */ + + cross_v3_v3v3(tmp, plane_c, plane_b); + mul_v3_v3fl(r_isect_co, tmp, plane_a[3]); + + cross_v3_v3v3(tmp, plane_a, plane_c); + madd_v3_v3fl(r_isect_co, tmp, plane_b[3]); + + cross_v3_v3v3(tmp, plane_b, plane_a); + madd_v3_v3fl(r_isect_co, tmp, plane_c[3]); + + mul_v3_fl(r_isect_co, 1.0f / det); + + return true; + } + else { + return false; + } +} + +/** * Intersect two planes, return a point on the intersection and a vector * that runs on the direction of the intersection. - * Return error code is the same as 'isect_line_line_v3'. * - * \param r_isect_co The resulting intersection point. - * \param r_isect_no The resulting vector of the intersection. - * \param plane_a_co The point on the first plane. - * \param plane_a_no The normal of the first plane. - * \param plane_b_co The point on the second plane. - * \param plane_b_no The normal of the second plane. * - * \note return normal isn't unit length + * \note this is a slightly reduced version of #isect_plane_plane_plane_v3 + * + * \param plane_a, plane_b: Planes. + * \param r_isect_co: The resulting intersection point. + * \param r_isect_no: The resulting vector of the intersection. + * + * \note \a r_isect_no isn't unit length. */ -bool isect_plane_plane_v3(float r_isect_co[3], float r_isect_no[3], - const float plane_a_co[3], const float plane_a_no[3], - const float plane_b_co[3], const float plane_b_no[3]) +bool isect_plane_plane_v3( + const float plane_a[4], const float plane_b[4], + float r_isect_co[3], float r_isect_no[3]) { - float plane_a_co_other[3]; - cross_v3_v3v3(r_isect_no, plane_a_no, plane_b_no); /* direction is simply the cross product */ - cross_v3_v3v3(plane_a_co_other, plane_a_no, r_isect_no); - add_v3_v3(plane_a_co_other, plane_a_co); - return isect_line_plane_v3(r_isect_co, plane_a_co, plane_a_co_other, plane_b_co, plane_b_no); + float det, plane_c[3]; + + /* direction is simply the cross product */ + cross_v3_v3v3(plane_c, plane_a, plane_b); + + /* in this case we don't need to use 'determinant_m3' */ + det = len_squared_v3(plane_c); + + if (det != 0.0f) { + float tmp[3]; + + /* (plane_b.xyz.cross(plane_c.xyz) * -plane_a[3] + + * plane_c.xyz.cross(plane_a.xyz) * -plane_b[3]) / det; */ + cross_v3_v3v3(tmp, plane_c, plane_b); + mul_v3_v3fl(r_isect_co, tmp, plane_a[3]); + + cross_v3_v3v3(tmp, plane_a, plane_c); + madd_v3_v3fl(r_isect_co, tmp, plane_b[3]); + + mul_v3_fl(r_isect_co, 1.0f / det); + + copy_v3_v3(r_isect_no, plane_c); + + return true; + } + else { + return false; + } } /** @@ -1490,46 +1646,67 @@ bool isect_tri_tri_epsilon_v3( const float epsilon) { const float *tri_pair[2][3] = {{t_a0, t_a1, t_a2}, {t_b0, t_b1, t_b2}}; - float no_a[3], no_b[3]; - float isect_co[3], isect_no[3]; + float plane_a[4], plane_b[4]; + float plane_co[3], plane_no[3]; BLI_assert((r_i1 != NULL) == (r_i2 != NULL)); - normal_tri_v3(no_a, UNPACK3(tri_pair[0])); - normal_tri_v3(no_b, UNPACK3(tri_pair[1])); + /* normalizing is needed for small triangles T46007 */ + normal_tri_v3(plane_a, UNPACK3(tri_pair[0])); + normal_tri_v3(plane_b, UNPACK3(tri_pair[1])); - if (isect_plane_plane_v3(isect_co, isect_no, t_a0, no_a, t_b0, no_b)) { - float isect_co_other[3]; + plane_a[3] = -dot_v3v3(plane_a, t_a0); + plane_b[3] = -dot_v3v3(plane_b, t_b0); + + if (isect_plane_plane_v3(plane_a, plane_b, plane_co, plane_no) && + (normalize_v3(plane_no) > epsilon)) + { + /** + * Implementation note: its simpler to project the triangles onto the intersection plane + * before intersecting their edges with the ray, defined by 'isect_plane_plane_v3'. + * This way we can use 'line_point_factor_v3_ex' to see if an edge crosses 'co_proj', + * then use the factor to calculate the world-space point. + */ struct { float min, max; } range[2] = {{FLT_MAX, -FLT_MAX}, {FLT_MAX, -FLT_MAX}}; int t; + float co_proj[3]; - add_v3_v3v3(isect_co_other, isect_co, isect_no); + closest_to_plane3_normalized_v3(co_proj, plane_no, plane_co); - /* For both triangles, find the overlap with the line defined by (isect_co, isect_co_other). + /* For both triangles, find the overlap with the line defined by the ray [co_proj, plane_no]. * When the ranges overlap we know the triangles do too. */ for (t = 0; t < 2; t++) { int j, j_prev; + float tri_proj[3][3]; + + closest_to_plane3_normalized_v3(tri_proj[0], plane_no, tri_pair[t][0]); + closest_to_plane3_normalized_v3(tri_proj[1], plane_no, tri_pair[t][1]); + closest_to_plane3_normalized_v3(tri_proj[2], plane_no, tri_pair[t][2]); for (j = 0, j_prev = 2; j < 3; j_prev = j++) { - /* intersection point on the line intersecting both planes */ - float ix_span[3]; - /* intersection point on the triangles edge */ - float ix_tri[3]; - - if (isect_line_line_epsilon_v3( - isect_co, isect_co_other, - tri_pair[t][j], tri_pair[t][j_prev], - ix_span, ix_tri, - epsilon) == 2) - { - const float edge_fac = line_point_factor_v3(ix_tri, tri_pair[t][j], tri_pair[t][j_prev]); - if (edge_fac >= -epsilon && edge_fac <= 1.0f + epsilon) { - const float span_fac = dist_signed_squared_to_plane3_v3(ix_tri, isect_no); - range[t].min = min_ff(range[t].min, span_fac); - range[t].max = max_ff(range[t].max, span_fac); - } + /* note that its important to have a very small nonzero epsilon here + * otherwise this fails for very small faces. + * However if its too small, large adjacent faces will count as intersecting */ + const float edge_fac = line_point_factor_v3_ex(co_proj, tri_proj[j_prev], tri_proj[j], 1e-10f, -1.0f); + /* ignore collinear lines, they are either an edge shared between 2 tri's + * (which runs along [co_proj, plane_no], but can be safely ignored). + * + * or a collinear edge placed away from the ray - which we don't intersect with & can ignore. */ + if (UNLIKELY(edge_fac == -1.0f)) { + /* pass */ + } + else if (edge_fac > 0.0f && edge_fac < 1.0f) { + float ix_tri[3]; + float span_fac; + + interp_v3_v3v3(ix_tri, tri_pair[t][j_prev], tri_pair[t][j], edge_fac); + /* the actual distance, since 'plane_no' is normalized */ + span_fac = dot_v3v3(plane_no, ix_tri); + + range[t].min = min_ff(range[t].min, span_fac); + range[t].max = max_ff(range[t].max, span_fac); } } @@ -1542,9 +1719,9 @@ bool isect_tri_tri_epsilon_v3( (range[0].max < range[1].min)) == 0) { if (r_i1 && r_i2) { - project_plane_v3_v3v3(isect_co, isect_co, isect_no); - madd_v3_v3v3fl(r_i1, isect_co, isect_no, sqrtf_signed(max_ff(range[0].min, range[1].min))); - madd_v3_v3v3fl(r_i2, isect_co, isect_no, sqrtf_signed(min_ff(range[0].max, range[1].max))); + project_plane_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)); } return true; @@ -1782,6 +1959,7 @@ bool isect_sweeping_sphere_tri_v3(const float p1[3], const float p2[3], const fl bool isect_axial_line_tri_v3(const int axis, const float p1[3], const float p2[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda) { + const float epsilon = 0.000001f; float p[3], e1[3], e2[3]; float u, v, f; int a0 = axis, a1 = (axis + 1) % 3, a2 = (axis + 2) % 3; @@ -1803,15 +1981,15 @@ bool isect_axial_line_tri_v3(const int axis, const float p1[3], const float p2[3 sub_v3_v3v3(p, v0, p1); f = (e2[a1] * e1[a2] - e2[a2] * e1[a1]); - if ((f > -0.000001f) && (f < 0.000001f)) return false; + if ((f > -epsilon) && (f < epsilon)) return false; v = (p[a2] * e1[a1] - p[a1] * e1[a2]) / f; if ((v < 0.0f) || (v > 1.0f)) return false; f = e1[a1]; - if ((f > -0.000001f) && (f < 0.000001f)) { + if ((f > -epsilon) && (f < epsilon)) { f = e1[a2]; - if ((f > -0.000001f) && (f < 0.000001f)) return false; + if ((f > -epsilon) && (f < epsilon)) return false; u = (-p[a2] - v * e2[a2]) / f; } else @@ -1828,7 +2006,7 @@ bool isect_axial_line_tri_v3(const int axis, const float p1[3], const float p2[3 /** * \return The number of point of interests - * 0 - lines are colinear + * 0 - lines are collinear * 1 - lines are coplanar, i1 is set to intersection * 2 - i1 and i2 are the nearest points on line 1 (v1, v2) and line 2 (v3, v4) respectively */ @@ -1837,25 +2015,18 @@ int isect_line_line_epsilon_v3( const float v3[3], const float v4[3], float i1[3], float i2[3], const float epsilon) { - float a[3], b[3], c[3], ab[3], cb[3], dir1[3], dir2[3]; + float a[3], b[3], c[3], ab[3], cb[3]; float d, div; sub_v3_v3v3(c, v3, v1); sub_v3_v3v3(a, v2, v1); sub_v3_v3v3(b, v4, v3); - normalize_v3_v3(dir1, a); - normalize_v3_v3(dir2, b); - d = dot_v3v3(dir1, dir2); - if (d == 1.0f || d == -1.0f) { - /* colinear */ - return 0; - } - cross_v3_v3v3(ab, a, b); d = dot_v3v3(c, ab); div = dot_v3v3(ab, ab); + /* important not to use an epsilon here, see: T45919 */ /* test zero length line */ if (UNLIKELY(div == 0.0f)) { return 0; @@ -1916,31 +2087,28 @@ bool isect_line_line_strict_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3], float vi[3], float *r_lambda) { - float a[3], b[3], c[3], ab[3], cb[3], ca[3], dir1[3], dir2[3]; + const float epsilon = 0.000001f; + float a[3], b[3], c[3], ab[3], cb[3], ca[3]; float d, div; sub_v3_v3v3(c, v3, v1); sub_v3_v3v3(a, v2, v1); sub_v3_v3v3(b, v4, v3); - normalize_v3_v3(dir1, a); - normalize_v3_v3(dir2, b); - d = dot_v3v3(dir1, dir2); - if (d == 1.0f || d == -1.0f || d == 0) { - /* colinear or one vector is zero-length*/ - return false; - } - cross_v3_v3v3(ab, a, b); d = dot_v3v3(c, ab); div = dot_v3v3(ab, ab); + /* important not to use an epsilon here, see: T45919 */ /* test zero length line */ if (UNLIKELY(div == 0.0f)) { return false; } /* test if the two lines are coplanar */ - else if (d > -0.000001f && d < 0.000001f) { + else if (UNLIKELY(fabsf(d) < epsilon)) { + return false; + } + else { float f1, f2; cross_v3_v3v3(cb, c, b); cross_v3_v3v3(ca, c, a); @@ -1962,9 +2130,6 @@ bool isect_line_line_strict_v3(const float v1[3], const float v2[3], return false; } } - else { - return false; - } } bool isect_aabb_aabb_v3(const float min1[3], const float max1[3], const float min2[3], const float max2[3]) @@ -2059,8 +2224,13 @@ float closest_to_line_v2(float cp[2], const float p[2], const float l1[2], const /** * A simplified version of #closest_to_line_v3 * we only need to return the ``lambda`` + * + * \param epsilon: avoid approaching divide-by-zero. + * Passing a zero will just check for nonzero division. */ -float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3]) +float line_point_factor_v3_ex( + const float p[3], const float l1[3], const float l2[3], + const float epsilon, const float fallback) { float h[3], u[3]; float dot; @@ -2071,11 +2241,18 @@ float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3 #else /* better check for zero */ dot = dot_v3v3(u, u); - return (dot != 0.0f) ? (dot_v3v3(u, h) / dot) : 0.0f; + return (fabsf(dot) > epsilon) ? (dot_v3v3(u, h) / dot) : fallback; #endif } +float line_point_factor_v3( + const float p[3], const float l1[3], const float l2[3]) +{ + return line_point_factor_v3_ex(p, l1, l2, 0.0f, 0.0f); +} -float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2]) +float line_point_factor_v2_ex( + const float p[2], const float l1[2], const float l2[2], + const float epsilon, const float fallback) { float h[2], u[2]; float dot; @@ -2086,10 +2263,15 @@ float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2 #else /* better check for zero */ dot = dot_v2v2(u, u); - return (dot != 0.0f) ? (dot_v2v2(u, h) / dot) : 0.0f; + return (fabsf(dot) > epsilon) ? (dot_v2v2(u, h) / dot) : fallback; #endif } +float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2]) +{ + return line_point_factor_v2_ex(p, l1, l2, 0.0f, 0.0f); +} + /** * \note #isect_line_plane_v3() shares logic */ @@ -2916,7 +3098,7 @@ static float mean_value_half_tan_v3(const struct Float3_Len *d_curr, const struc float cross[3], area; cross_v3_v3v3(cross, d_curr->dir, d_next->dir); area = len_v3(cross); - if (LIKELY(area != 0.0f)) { + if (LIKELY(fabsf(area) > FLT_EPSILON)) { const float dot = dot_v3v3(d_curr->dir, d_next->dir); const float len = d_curr->len * d_next->len; return (len - dot) / area; @@ -2931,7 +3113,7 @@ static float mean_value_half_tan_v2(const struct Float2_Len *d_curr, const struc float area; /* different from the 3d version but still correct */ area = cross_v2v2(d_curr->dir, d_next->dir); - if (LIKELY(area != 0.0f)) { + if (LIKELY(fabsf(area) > FLT_EPSILON)) { const float dot = dot_v2v2(d_curr->dir, d_next->dir); const float len = d_curr->len * d_next->len; return (len - dot) / area; @@ -2948,18 +3130,22 @@ void interp_weights_poly_v3(float *w, float v[][3], const int n, const float co[ const float *v_curr, *v_next; float ht_prev, ht; /* half tangents */ float totweight = 0.0f; - int i = 0; + int i_curr, i_next; char ix_flag = 0; struct Float3_Len d_curr, d_next; - v_curr = v[0]; - v_next = v[1]; + /* loop over 'i_next' */ + i_curr = n - 1; + i_next = 0; + + v_curr = v[i_curr]; + v_next = v[i_next]; - DIR_V3_SET(&d_curr, v[n - 1], co); - DIR_V3_SET(&d_next, v_curr, co); + DIR_V3_SET(&d_curr, v_curr - 3 /* v[n - 2] */, co); + DIR_V3_SET(&d_next, v_curr /* v[n - 1] */, co); ht_prev = mean_value_half_tan_v3(&d_curr, &d_next); - while (i < n) { + while (i_next < n) { /* Mark Mayer et al algorithm that is used here does not operate well if vertex is close * to borders of face. In that case, do simple linear interpolation between the two edge vertices */ @@ -2976,22 +3162,19 @@ void interp_weights_poly_v3(float *w, float v[][3], const int n, const float co[ d_curr = d_next; DIR_V3_SET(&d_next, v_next, co); ht = mean_value_half_tan_v3(&d_curr, &d_next); - w[i] = (ht_prev + ht) / d_curr.len; - totweight += w[i]; + w[i_curr] = (ht_prev + ht) / d_curr.len; + totweight += w[i_curr]; /* step */ - i++; + i_curr = i_next++; v_curr = v_next; - v_next = v[(i + 1) % n]; + v_next = v[i_next]; ht_prev = ht; } if (ix_flag) { - const int i_curr = i; - for (i = 0; i < n; i++) { - w[i] = 0.0f; - } + memset(w, 0, sizeof(*w) * (size_t)n); if (ix_flag & IS_POINT_IX) { w[i_curr] = 1.0f; @@ -3000,13 +3183,13 @@ void interp_weights_poly_v3(float *w, float v[][3], const int n, const float co[ float fac = line_point_factor_v3(co, v_curr, v_next); CLAMP(fac, 0.0f, 1.0f); w[i_curr] = 1.0f - fac; - w[(i_curr + 1) % n] = fac; + w[i_next] = fac; } } else { if (totweight != 0.0f) { - for (i = 0; i < n; i++) { - w[i] /= totweight; + for (i_curr = 0; i_curr < n; i_curr++) { + w[i_curr] /= totweight; } } } @@ -3020,18 +3203,22 @@ void interp_weights_poly_v2(float *w, float v[][2], const int n, const float co[ const float *v_curr, *v_next; float ht_prev, ht; /* half tangents */ float totweight = 0.0f; - int i = 0; + int i_curr, i_next; char ix_flag = 0; struct Float2_Len d_curr, d_next; - v_curr = v[0]; - v_next = v[1]; + /* loop over 'i_next' */ + i_curr = n - 1; + i_next = 0; - DIR_V2_SET(&d_curr, v[n - 1], co); - DIR_V2_SET(&d_next, v_curr, co); + v_curr = v[i_curr]; + v_next = v[i_next]; + + DIR_V2_SET(&d_curr, v_curr - 2 /* v[n - 2] */, co); + DIR_V2_SET(&d_next, v_curr /* v[n - 1] */, co); ht_prev = mean_value_half_tan_v2(&d_curr, &d_next); - while (i < n) { + while (i_next < n) { /* Mark Mayer et al algorithm that is used here does not operate well if vertex is close * to borders of face. In that case, do simple linear interpolation between the two edge vertices */ @@ -3048,22 +3235,19 @@ void interp_weights_poly_v2(float *w, float v[][2], const int n, const float co[ d_curr = d_next; DIR_V2_SET(&d_next, v_next, co); ht = mean_value_half_tan_v2(&d_curr, &d_next); - w[i] = (ht_prev + ht) / d_curr.len; - totweight += w[i]; + w[i_curr] = (ht_prev + ht) / d_curr.len; + totweight += w[i_curr]; /* step */ - i++; + i_curr = i_next++; v_curr = v_next; - v_next = v[(i + 1) % n]; + v_next = v[i_next]; ht_prev = ht; } if (ix_flag) { - const int i_curr = i; - for (i = 0; i < n; i++) { - w[i] = 0.0f; - } + memset(w, 0, sizeof(*w) * (size_t)n); if (ix_flag & IS_POINT_IX) { w[i_curr] = 1.0f; @@ -3072,13 +3256,13 @@ void interp_weights_poly_v2(float *w, float v[][2], const int n, const float co[ float fac = line_point_factor_v2(co, v_curr, v_next); CLAMP(fac, 0.0f, 1.0f); w[i_curr] = 1.0f - fac; - w[(i_curr + 1) % n] = fac; + w[i_next] = fac; } } else { if (totweight != 0.0f) { - for (i = 0; i < n; i++) { - w[i] /= totweight; + for (i_curr = 0; i_curr < n; i_curr++) { + w[i_curr] /= totweight; } } } @@ -3375,8 +3559,8 @@ void perspective_m4(float mat[4][4], const float left, const float right, const mat[2][3] = -1.0f; mat[3][2] = (-2.0f * nearClip * farClip) / Zdelta; mat[0][1] = mat[0][2] = mat[0][3] = - mat[1][0] = mat[1][2] = mat[1][3] = - mat[3][0] = mat[3][1] = mat[3][3] = 0.0f; + mat[1][0] = mat[1][2] = mat[1][3] = + mat[3][0] = mat[3][1] = mat[3][3] = 0.0f; } diff --git a/source/blender/blenlib/intern/math_matrix.c b/source/blender/blenlib/intern/math_matrix.c index 33d0fb87aca..4bf6d162970 100644 --- a/source/blender/blenlib/intern/math_matrix.c +++ b/source/blender/blenlib/intern/math_matrix.c @@ -516,7 +516,8 @@ void mul_v3_mat3_m4v3(float r[3], float mat[4][4], const float vec[3]) void mul_project_m4_v3(float mat[4][4], float vec[3]) { - const float w = mul_project_m4_v3_zfac(mat, vec); + /* absolute value to not flip the frustum upside down behind the camera */ + const float w = fabsf(mul_project_m4_v3_zfac(mat, vec)); mul_m4_v3(mat, vec); vec[0] /= w; @@ -526,7 +527,7 @@ void mul_project_m4_v3(float mat[4][4], float vec[3]) void mul_v3_project_m4_v3(float r[3], float mat[4][4], const float vec[3]) { - const float w = mul_project_m4_v3_zfac(mat, vec); + const float w = fabsf(mul_project_m4_v3_zfac(mat, vec)); mul_v3_m4v3(r, mat, vec); r[0] /= w; @@ -536,7 +537,7 @@ void mul_v3_project_m4_v3(float r[3], float mat[4][4], const float vec[3]) void mul_v2_project_m4_v3(float r[2], float mat[4][4], const float vec[3]) { - const float w = mul_project_m4_v3_zfac(mat, vec); + const float w = fabsf(mul_project_m4_v3_zfac(mat, vec)); mul_v2_m4v3(r, mat, vec); r[0] /= w; @@ -1247,36 +1248,74 @@ bool is_uniform_scaled_m4(float m[4][4]) return is_uniform_scaled_m3(t); } +void normalize_m3_ex(float mat[3][3], float r_scale[3]) +{ + int i; + for (i = 0; i < 3; i++) { + r_scale[i] = normalize_v3(mat[i]); + } +} void normalize_m3(float mat[3][3]) { - normalize_v3(mat[0]); - normalize_v3(mat[1]); - normalize_v3(mat[2]); + int i; + for (i = 0; i < 3; i++) { + normalize_v3(mat[i]); + } } +void normalize_m3_m3_ex(float rmat[3][3], float mat[3][3], float r_scale[3]) +{ + int i; + for (i = 0; i < 3; i++) { + r_scale[i] = normalize_v3_v3(rmat[i], mat[i]); + } +} void normalize_m3_m3(float rmat[3][3], float mat[3][3]) { - normalize_v3_v3(rmat[0], mat[0]); - normalize_v3_v3(rmat[1], mat[1]); - normalize_v3_v3(rmat[2], mat[2]); + int i; + for (i = 0; i < 3; i++) { + normalize_v3_v3(rmat[i], mat[i]); + } } +void normalize_m4_ex(float mat[4][4], float r_scale[3]) +{ + int i; + for (i = 0; i < 3; i++) { + r_scale[i] = normalize_v3(mat[i]); + if (r_scale[i] != 0.0f) { + mat[i][3] /= r_scale[i]; + } + } +} void normalize_m4(float mat[4][4]) { - float len; - - len = normalize_v3(mat[0]); - if (len != 0.0f) mat[0][3] /= len; - len = normalize_v3(mat[1]); - if (len != 0.0f) mat[1][3] /= len; - len = normalize_v3(mat[2]); - if (len != 0.0f) mat[2][3] /= len; + int i; + for (i = 0; i < 3; i++) { + float len = normalize_v3(mat[i]); + if (len != 0.0f) { + mat[i][3] /= len; + } + } } +void normalize_m4_m4_ex(float rmat[4][4], float mat[4][4], float r_scale[3]) +{ + int i; + for (i = 0; i < 3; i++) { + r_scale[i] = normalize_v3_v3(rmat[i], mat[i]); + rmat[i][3] = (r_scale[i] != 0.0f) ? (mat[i][3] / r_scale[i]) : mat[i][3]; + } + copy_v4_v4(rmat[3], mat[3]); +} void normalize_m4_m4(float rmat[4][4], float mat[4][4]) { - copy_m4_m4(rmat, mat); - normalize_m4(rmat); + int i; + for (i = 0; i < 3; i++) { + float len = normalize_v3_v3(rmat[i], mat[i]); + rmat[i][3] = (len != 0.0f) ? (mat[i][3] / len) : mat[i][3]; + } + copy_v4_v4(rmat[3], mat[3]); } void adjoint_m2_m2(float m1[2][2], float m[2][2]) @@ -1521,6 +1560,34 @@ void mat4_decompose(float loc[3], float quat[4], float size[3], float wmat[4][4] mat3_to_quat(quat, rot); } +/** + * Right polar decomposition: + * M = UP + * + * U is the 'rotation'-like component, the closest orthogonal matrix to M. + * P is the 'scaling'-like component, defined in U space. + * + * See https://en.wikipedia.org/wiki/Polar_decomposition for more. + */ +void mat3_polar_decompose(float mat3[3][3], float r_U[3][3], float r_P[3][3]) +{ + /* From svd decomposition (M = WSV*), we have: + * U = WV* + * P = VSV* + */ + float W[3][3], S[3][3], V[3][3], Vt[3][3]; + float sval[3]; + + BLI_svd_m3(mat3, W, sval, V); + + size_to_mat3(S, sval); + + transpose_m3_m3(Vt, V); + mul_m3_m3m3(r_U, W, Vt); + mul_m3_series(r_P, V, S, Vt); +} + + void scale_m3_fl(float m[3][3], float scale) { m[0][0] = m[1][1] = m[2][2] = scale; @@ -1660,6 +1727,75 @@ void blend_m4_m4m4(float out[4][4], float dst[4][4], float src[4][4], const floa loc_quat_size_to_mat4(out, floc, fquat, fsize); } +/** + * 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). + * 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. + */ +void interp_m3_m3m3(float R[3][3], float A[3][3], float B[3][3], const float t) +{ + /* 'Rotation' component ('U' part of polar decomposition, the closest orthogonal matrix to M3 rot/scale + * transformation matrix), spherically interpolated. */ + float U_A[3][3], U_B[3][3], U[3][3]; + float quat_A[4], quat_B[4], quat[4]; + /* 'Scaling' component ('P' part of polar decomposition, i.e. scaling in U-defined space), linearly interpolated. */ + float P_A[3][3], P_B[3][3], P[3][3]; + + int i; + + mat3_polar_decompose(A, U_A, P_A); + mat3_polar_decompose(B, U_B, P_B); + + mat3_to_quat(quat_A, U_A); + mat3_to_quat(quat_B, U_B); + interp_qt_qtqt(quat, quat_A, quat_B, t); + quat_to_mat3(U, quat); + + for (i = 0; i < 3; i++) { + interp_v3_v3v3(P[i], P_A[i], P_B[i], t); + } + + /* And we reconstruct rot/scale matrix from interpolated polar components */ + mul_m3_m3m3(R, U, P); +} + +/** + * 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. + */ +void interp_m4_m4m4(float R[4][4], float A[4][4], float B[4][4], const float t) +{ + float A3[3][3], B3[3][3], R3[3][3]; + + /* Location component, linearly interpolated. */ + float loc_A[3], loc_B[3], loc[3]; + + copy_v3_v3(loc_A, A[3]); + copy_v3_v3(loc_B, B[3]); + interp_v3_v3v3(loc, loc_A, loc_B, t); + + copy_m3_m4(A3, A); + copy_m3_m4(B3, B); + + interp_m3_m3m3(R3, A3, B3, t); + + copy_m4_m3(R, R3); + copy_v3_v3(R[3], loc); +} + bool is_negative_m3(float mat[3][3]) { float vec[3]; diff --git a/source/blender/blenlib/intern/math_rotation.c b/source/blender/blenlib/intern/math_rotation.c index 5f039e89e89..575710e8d75 100644 --- a/source/blender/blenlib/intern/math_rotation.c +++ b/source/blender/blenlib/intern/math_rotation.c @@ -1631,7 +1631,7 @@ void mat4_to_dquat(DualQuat *dq, float basemat[4][4], float mat[4][4]) copy_m3_m4(mat3, mat); - if (!is_orthonormal_m3(mat3) || (determinant_m4(mat) < 0.0f) || len_v3(dscale) > 1e-4f) { + if (!is_orthonormal_m3(mat3) || (determinant_m4(mat) < 0.0f) || len_squared_v3(dscale) > SQUARE(1e-4f)) { /* extract R and S */ float tmp[4][4]; diff --git a/source/blender/blenlib/intern/math_solvers.c b/source/blender/blenlib/intern/math_solvers.c index 2f962714c8c..d1dad9a6269 100644 --- a/source/blender/blenlib/intern/math_solvers.c +++ b/source/blender/blenlib/intern/math_solvers.c @@ -59,3 +59,16 @@ bool BLI_eigen_solve_selfadjoint_m3(const float m3[3][3], float r_eigen_values[3 return EG3_self_adjoint_eigen_solve(3, (const float *)m3, r_eigen_values, (float *)r_eigen_vectors); } + +/** + * \brief Compute the SVD (Singular Values Decomposition) of given 3D matrix (m3 = USV*). + * + * \param m3 the matrix to decompose. + * \return r_U the computed left singular vector of \a m3 (NULL if not needed). + * \return r_S the computed singular values of \a m3 (NULL if not needed). + * \return r_V the computed right singular vector of \a m3 (NULL if not needed). + */ +void BLI_svd_m3(const float m3[3][3], float r_U[3][3], float r_S[3], float r_V[3][3]) +{ + EG3_svd_square_matrix(3, (const float *)m3, (float *)r_U, (float *)r_S, (float *)r_V); +} diff --git a/source/blender/blenlib/intern/math_statistics.c b/source/blender/blenlib/intern/math_statistics.c index f7a6bc496f4..a8cb8e2c40d 100644 --- a/source/blender/blenlib/intern/math_statistics.c +++ b/source/blender/blenlib/intern/math_statistics.c @@ -39,7 +39,7 @@ /** * \brief Compute the covariance matrix of given set of nD coordinates. * - * \param n the dimension of the vectors (and hence, of the covairance matrix to compute). + * \param n the dimension of the vectors (and hence, of the covariance matrix to compute). * \param cos_vn the nD points to compute covariance from. * \param nbr_cos_vn the number of nD coordinates in cos_vn. * \param center the center (or mean point) of cos_vn. If NULL, it is assumed cos_vn is already centered. @@ -60,7 +60,7 @@ void BLI_covariance_m_vn_ex( memset(r_covmat, 0, sizeof(*r_covmat) * (size_t)(n * n)); -#pragma omp parallel for default(shared) private(i, j, k) schedule(static) if((nbr_cos_vn * n) >= 10000) +#pragma omp parallel for default(shared) private(i, j, k) schedule(static) if ((nbr_cos_vn * n) >= 10000) for (i = 0; i < n; i++) { for (j = i; j < n; j++) { r_covmat[i * n + j] = 0.0f; diff --git a/source/blender/blenlib/intern/math_vector.c b/source/blender/blenlib/intern/math_vector.c index 6da0e87355d..8d33e04241a 100644 --- a/source/blender/blenlib/intern/math_vector.c +++ b/source/blender/blenlib/intern/math_vector.c @@ -785,7 +785,7 @@ void minmax_v2v2_v2(float min[2], float max[2], const float vec[2]) if (max[1] < vec[1]) max[1] = vec[1]; } -void minmax_v3v3_v3_array(float r_min[3], float r_max[3], float (*vec_arr)[3], int nbr) +void minmax_v3v3_v3_array(float r_min[3], float r_max[3], const float (*vec_arr)[3], int nbr) { while (nbr--) { minmax_v3v3_v3(r_min, r_max, *vec_arr++); diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c index c21b09748c9..e625ac18685 100644 --- a/source/blender/blenlib/intern/math_vector_inline.c +++ b/source/blender/blenlib/intern/math_vector_inline.c @@ -97,7 +97,29 @@ MINLINE void copy_v4_fl(float r[4], float f) r[3] = f; } -/* short */ +/* unsigned char */ +MINLINE void copy_v2_v2_uchar(unsigned char r[2], const unsigned char a[2]) +{ + r[0] = a[0]; + r[1] = a[1]; +} + +MINLINE void copy_v3_v3_uchar(unsigned char r[3], const unsigned char a[3]) +{ + r[0] = a[0]; + r[1] = a[1]; + r[2] = a[2]; +} + +MINLINE void copy_v4_v4_uchar(unsigned char r[4], const unsigned char a[4]) +{ + r[0] = a[0]; + r[1] = a[1]; + r[2] = a[2]; + r[3] = a[3]; +} + +/* char */ MINLINE void copy_v2_v2_char(char r[2], const char a[2]) { r[0] = a[0]; diff --git a/source/blender/blenlib/intern/memory_utils.c b/source/blender/blenlib/intern/memory_utils.c new file mode 100644 index 00000000000..2ebb8be5bb4 --- /dev/null +++ b/source/blender/blenlib/intern/memory_utils.c @@ -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 ***** + */ + +/** \file blender/blenlib/intern/memory_utils.c + * \ingroup bli + * \brief Generic memory manipulation API. + * + * This is to extend on existing functions + * such as ``memcpy`` & ``memcmp``. + */ +#include <string.h> + +#include "BLI_sys_types.h" +#include "BLI_utildefines.h" + +#include "BLI_memory_utils.h" + +#include "BLI_strict_flags.h" + +/** + * Check if memory is zero'd, as with memset(s, 0, nbytes) + */ +bool BLI_memory_is_zero(const void *s, const size_t nbytes) +{ + const char *s_byte = s; + const char *s_end = (const char *)s + nbytes; + + while ((s_byte != s_end) && (*s_byte == 0)) { + s_byte++; + } + + return (s_byte == s_end); +} diff --git a/source/blender/blenlib/intern/noise.c b/source/blender/blenlib/intern/noise.c index 5febf720b30..4b2ad834d75 100644 --- a/source/blender/blenlib/intern/noise.c +++ b/source/blender/blenlib/intern/noise.c @@ -1546,7 +1546,7 @@ float BLI_gTurbulence(float noisesize, float x, float y, float z, int oct, int h /* * The following code is based on Ken Musgrave's explanations and sample - * source code in the book "Texturing and Modelling: A procedural approach" + * source code in the book "Texturing and Modeling: A procedural approach" */ /* diff --git a/source/blender/blenlib/intern/path_util.c b/source/blender/blenlib/intern/path_util.c index 3a73d4cc0c7..99e512475bb 100644 --- a/source/blender/blenlib/intern/path_util.c +++ b/source/blender/blenlib/intern/path_util.c @@ -191,31 +191,6 @@ int BLI_split_name_num(char *left, int *nr, const char *name, const char delim) } /** - * Looks for a string of digits within name (using BLI_stringdec) and adjusts it by add. - */ -void BLI_newname(char *name, int add) -{ - char head[UNIQUE_NAME_MAX], tail[UNIQUE_NAME_MAX]; - int pic; - unsigned short digits; - - pic = BLI_stringdec(name, head, tail, &digits); - - /* are we going from 100 -> 99 or from 10 -> 9 */ - if (add < 0 && digits < 4 && digits > 0) { - int i, exp; - exp = 1; - for (i = digits; i > 1; i--) exp *= 10; - if (pic >= exp && (pic + add) < exp) digits--; - } - - pic += add; - - if (digits == 4 && pic < 0) pic = 0; - BLI_stringenc(name, head, tail, digits, pic); -} - -/** * 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. * @@ -332,14 +307,15 @@ static int BLI_path_unc_prefix_len(const char *path); /* defined below in same f /* ******************** string encoding ***************** */ -/* This is quite an ugly function... its purpose is to - * take the dir name, make it absolute, and clean it up, replacing - * excess file entry stuff (like /tmp/../tmp/../) - * note that dir isn't protected for max string names... - * - * If relbase is NULL then its ignored +/** + * Remove redundant characters from \a path and optionally make absolute. + * + * \param relbase: The path this is relative to, or ignored when NULL. + * \param path: Can be any input, and this function converts it to a regular full path. + * Also removes garbage from directory paths, like `/../` or double slashes etc. + * + * \note \a path isn't protected for max string names... */ - void BLI_cleanup_path(const char *relabase, char *path) { ptrdiff_t a; @@ -428,6 +404,9 @@ void BLI_cleanup_path(const char *relabase, char *path) #endif } +/** + * Cleanup filepath ensuring a trailing slash. + */ void BLI_cleanup_dir(const char *relabase, char *dir) { BLI_cleanup_path(relabase, dir); @@ -435,6 +414,9 @@ void BLI_cleanup_dir(const char *relabase, char *dir) } +/** + * Cleanup filepath ensuring no trailing slash. + */ void BLI_cleanup_file(const char *relabase, char *path) { BLI_cleanup_path(relabase, path); @@ -453,6 +435,8 @@ void BLI_cleanup_file(const char *relabase, char *path) * * \note Space case ' ' is a bit of an edge case here - in theory it is allowed, but again can be an issue * in some cases, so we simply replace it by an underscore too (good practice anyway). + * REMOVED based on popular demand (see T45900). + * Percent '%' char is a bit same case - not recommended to use it, but supported by all decent FS/OS around... * * \note On Windows, it also ensures there is no '.' (dot char) at the end of the file, this can lead to issues... * @@ -461,9 +445,9 @@ void BLI_cleanup_file(const char *relabase, char *path) */ bool BLI_filename_make_safe(char *fname) { - const char *invalid = "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f" + const char *invalid = "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f" "\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f" - "/\\?%*:|\"<> "; + "/\\?*:|\"<>"; char *fn; bool changed = false; @@ -533,7 +517,7 @@ bool BLI_filename_make_safe(char *fname) bool BLI_path_make_safe(char *path) { /* Simply apply BLI_filename_make_safe() over each component of the path. - * Luckily enough, same 'sfae' rules applies to filenames and dirnames. */ + * Luckily enough, same 'safe' rules applies to filenames and dirnames. */ char *curr_slash, *curr_path = path; bool changed = false; bool skip_first = false; @@ -977,7 +961,7 @@ bool BLI_path_frame_range(char *path, int sta, int end, int digits) */ bool BLI_path_frame_get(char *path, int *r_frame, int *r_numdigits) { - if (path && *path) { + if (*path) { char *file = (char *)BLI_last_slash(path); char *c; int len, numdigits; @@ -1026,9 +1010,9 @@ bool BLI_path_frame_get(char *path, int *r_frame, int *r_numdigits) return false; } -void BLI_path_frame_strip(char *path, bool setsharp, char *ext) +void BLI_path_frame_strip(char *path, bool set_frame_char, char *ext) { - if (path && *path) { + if (*path) { char *file = (char *)BLI_last_slash(path); char *c, *suffix; int len; @@ -1063,15 +1047,12 @@ void BLI_path_frame_strip(char *path, bool setsharp, char *ext) if (numdigits) { /* replace the number with the suffix and terminate the string */ while (numdigits--) { - if (ext) *ext++ = *suffix; - - if (setsharp) *c++ = '#'; - else *c++ = *suffix; - + *ext++ = *suffix; + *c++ = set_frame_char ? '#' : *suffix; suffix++; } - *c = 0; - if (ext) *ext = 0; + *c = '\0'; + *ext = '\0'; } } } @@ -1087,9 +1068,14 @@ bool BLI_path_frame_check_chars(const char *path) } /** - * If path begins with "//", strips that and replaces it with basepath directory. Also converts - * a drive-letter prefix to something more sensible if this is a non-drive-letter-based system. - * Returns true if "//" prefix expansion was done. + * If path begins with "//", strips that and replaces it with basepath directory. + * + * \note Also converts drive-letter prefix to something more sensible + * if this is a non-drive-letter-based system. + * + * \param path: The path to convert. + * \param basepath: The directory to base relative paths with. + * \return true if the path was relative (started with "//"). */ bool BLI_path_abs(char *path, const char *basepath) { @@ -1202,7 +1188,7 @@ bool BLI_path_abs(char *path, const char *basepath) * \note Should only be done with command line paths. * this is _not_ something blenders internal paths support like the "//" prefix */ -bool BLI_path_cwd(char *path) +bool BLI_path_cwd(char *path, const size_t maxlen) { bool wasrelative = true; const int filelen = strlen(path); @@ -1216,24 +1202,15 @@ bool BLI_path_cwd(char *path) #endif if (wasrelative) { - char cwd[FILE_MAX] = ""; - BLI_current_working_dir(cwd, sizeof(cwd)); /* in case the full path to the blend isn't used */ - - if (cwd[0] == '\0') { - printf("Could not get the current working directory - $PWD for an unknown reason.\n"); - } - else { - /* uses the blend path relative to cwd important for loading relative linked files. - * - * cwd should contain c:\ etc on win32 so the relbase can be NULL - * relbase being NULL also prevents // being misunderstood as relative to the current - * blend file which isn't a feature we want to use in this case since were dealing - * with a path from the command line, rather than from inside Blender */ - + char cwd[FILE_MAX]; + /* in case the full path to the blend isn't used */ + if (BLI_current_working_dir(cwd, sizeof(cwd))) { char origpath[FILE_MAX]; BLI_strncpy(origpath, path, FILE_MAX); - - BLI_make_file_string(NULL, path, cwd, origpath); + BLI_join_dirfile(path, maxlen, cwd, origpath); + } + else { + printf("Could not get the current working directory - $PWD for an unknown reason.\n"); } } @@ -1610,17 +1587,16 @@ bool BLI_testextensie_glob(const char *str, const char *ext_fnmatch) while (ext_step[0]) { const char *ext_next; - int len_ext; + size_t len_ext; if ((ext_next = strchr(ext_step, ';'))) { - len_ext = (int)(ext_next - ext_step) + 1; + len_ext = ext_next - ext_step + 1; + BLI_strncpy(pattern, ext_step, (len_ext > sizeof(pattern)) ? sizeof(pattern) : len_ext); } else { - len_ext = sizeof(pattern); + len_ext = BLI_strncpy_rlen(pattern, ext_step, sizeof(pattern)); } - BLI_strncpy(pattern, ext_step, len_ext); - if (fnmatch(pattern, str, FNM_CASEFOLD) == 0) { return true; } @@ -2015,38 +1991,3 @@ void BLI_path_native_slash(char *path) BLI_str_replace_char(path + BLI_path_unc_prefix_len(path), '\\', '/'); #endif } - - -#ifdef WITH_ICONV - -/** - * Converts a string encoded in the charset named by *code to UTF-8. - * Opens a new iconv context each time it is run, which is probably not the - * most efficient. */ -void BLI_string_to_utf8(char *original, char *utf_8, const char *code) -{ - size_t inbytesleft = strlen(original); - size_t outbytesleft = 512; - size_t rv = 0; - iconv_t cd; - - if (NULL == code) { - code = locale_charset(); - } - cd = iconv_open("UTF-8", code); - - if (cd == (iconv_t)(-1)) { - printf("iconv_open Error"); - *utf_8 = '\0'; - return; - } - rv = iconv(cd, &original, &inbytesleft, &utf_8, &outbytesleft); - if (rv == (size_t) -1) { - printf("iconv Error\n"); - iconv_close(cd); - return; - } - *utf_8 = '\0'; - iconv_close(cd); -} -#endif // WITH_ICONV diff --git a/source/blender/blenlib/intern/polyfill2d.c b/source/blender/blenlib/intern/polyfill2d.c index df6caa4b65a..397082b02d2 100644 --- a/source/blender/blenlib/intern/polyfill2d.c +++ b/source/blender/blenlib/intern/polyfill2d.c @@ -799,7 +799,7 @@ static void polyfill_prepare( coords_sign = (cross_poly_v2(coords, coords_tot) >= 0.0f) ? 1 : -1; } else { - /* chech we're passing in correcty args */ + /* check we're passing in correcty args */ #ifdef USE_STRICT_ASSERT #ifndef NDEBUG if (coords_sign == 1) { diff --git a/source/blender/blenlib/intern/rct.c b/source/blender/blenlib/intern/rct.c index 8de5d2ef172..a5f7fe2a008 100644 --- a/source/blender/blenlib/intern/rct.c +++ b/source/blender/blenlib/intern/rct.c @@ -474,7 +474,7 @@ void BLI_rctf_interp(rctf *rect, const rctf *rect_a, const rctf *rect_b, const f /* BLI_rcti_interp() not needed yet */ -bool BLI_rctf_clamp_pt_v(const struct rctf *rect, float xy[2]) +bool BLI_rctf_clamp_pt_v(const rctf *rect, float xy[2]) { bool changed = false; if (xy[0] < rect->xmin) { xy[0] = rect->xmin; changed = true; } @@ -484,7 +484,7 @@ bool BLI_rctf_clamp_pt_v(const struct rctf *rect, float xy[2]) return changed; } -bool BLI_rcti_clamp_pt_v(const struct rcti *rect, int xy[2]) +bool BLI_rcti_clamp_pt_v(const rcti *rect, int xy[2]) { bool changed = false; if (xy[0] < rect->xmin) { xy[0] = rect->xmin; changed = true; } @@ -494,7 +494,96 @@ bool BLI_rcti_clamp_pt_v(const struct rcti *rect, int xy[2]) return changed; } -bool BLI_rctf_compare(const struct rctf *rect_a, const struct rctf *rect_b, const float limit) +/** + * Clamp \a rect within \a rect_bounds, setting \a r_xy to the offset. + * + * \return true if a change is made. + */ +bool BLI_rctf_clamp(rctf *rect, const rctf *rect_bounds, float r_xy[2]) +{ + bool changed = false; + + r_xy[0] = 0.0f; + r_xy[1] = 0.0f; + + if (rect->xmin < rect_bounds->xmin) { + float ofs = rect_bounds->xmin - rect->xmin; + rect->xmin += ofs; + rect->xmax += ofs; + r_xy[0] += ofs; + changed = true; + } + + if (rect->xmax > rect_bounds->xmax) { + float ofs = rect_bounds->xmax - rect->xmax; + rect->xmin += ofs; + rect->xmax += ofs; + r_xy[0] += ofs; + changed = true; + } + + if (rect->ymin < rect_bounds->ymin) { + float ofs = rect_bounds->ymin - rect->ymin; + rect->ymin += ofs; + rect->ymax += ofs; + r_xy[1] += ofs; + changed = true; + } + + if (rect->ymax > rect_bounds->ymax) { + float ofs = rect_bounds->ymax - rect->ymax; + rect->ymin += ofs; + rect->ymax += ofs; + r_xy[1] += ofs; + changed = true; + } + + return changed; +} + +bool BLI_rcti_clamp(rcti *rect, const rcti *rect_bounds, int r_xy[2]) +{ + bool changed = false; + + r_xy[0] = 0; + r_xy[1] = 0; + + if (rect->xmin < rect_bounds->xmin) { + int ofs = rect_bounds->xmin - rect->xmin; + rect->xmin += ofs; + rect->xmax += ofs; + r_xy[0] += ofs; + changed = true; + } + + if (rect->xmax > rect_bounds->xmax) { + int ofs = rect_bounds->xmax - rect->xmax; + rect->xmin += ofs; + rect->xmax += ofs; + r_xy[0] += ofs; + changed = true; + } + + if (rect->ymin < rect_bounds->ymin) { + int ofs = rect_bounds->ymin - rect->ymin; + rect->ymin += ofs; + rect->ymax += ofs; + r_xy[1] += ofs; + changed = true; + } + + if (rect->ymax > rect_bounds->ymax) { + int ofs = rect_bounds->ymax - rect->ymax; + rect->ymin += ofs; + rect->ymax += ofs; + r_xy[1] += ofs; + changed = true; + } + + return changed; +} + +bool BLI_rctf_compare(const rctf *rect_a, const rctf *rect_b, const float limit) { if (fabsf(rect_a->xmin - rect_b->xmin) < limit) if (fabsf(rect_a->xmax - rect_b->xmax) < limit) @@ -505,7 +594,7 @@ bool BLI_rctf_compare(const struct rctf *rect_a, const struct rctf *rect_b, cons return false; } -bool BLI_rcti_compare(const struct rcti *rect_a, const struct rcti *rect_b) +bool BLI_rcti_compare(const rcti *rect_a, const rcti *rect_b) { if (rect_a->xmin == rect_b->xmin) if (rect_a->xmax == rect_b->xmax) @@ -584,6 +673,14 @@ void BLI_rcti_rctf_copy(rcti *dst, const rctf *src) dst->ymax = dst->ymin + floorf(BLI_rctf_size_y(src) + 0.5f); } +void BLI_rcti_rctf_copy_floor(rcti *dst, const rctf *src) +{ + dst->xmin = floorf(src->xmin); + dst->xmax = floorf(src->xmax); + dst->ymin = floorf(src->ymin); + dst->ymax = floorf(src->ymax); +} + void BLI_rctf_rcti_copy(rctf *dst, const rcti *src) { dst->xmin = src->xmin; diff --git a/source/blender/blenlib/intern/storage.c b/source/blender/blenlib/intern/storage.c index 7fdf6ec8101..f7a8664c739 100644 --- a/source/blender/blenlib/intern/storage.c +++ b/source/blender/blenlib/intern/storage.c @@ -91,8 +91,14 @@ char *BLI_current_working_dir(char *dir, const size_t maxncpy) { const char *pwd = getenv("PWD"); if (pwd) { - BLI_strncpy(dir, pwd, maxncpy); - return dir; + size_t srclen = BLI_strnlen(pwd, maxncpy); + if (srclen != maxncpy) { + memcpy(dir, pwd, srclen + 1); + return dir; + } + else { + return NULL; + } } return getcwd(dir, maxncpy); diff --git a/source/blender/blenlib/intern/string.c b/source/blender/blenlib/intern/string.c index 6d75f7c4131..e93d2b7507a 100644 --- a/source/blender/blenlib/intern/string.c +++ b/source/blender/blenlib/intern/string.c @@ -379,12 +379,13 @@ escape_finish: */ char *BLI_str_quoted_substrN(const char *__restrict str, const char *__restrict prefix) { - size_t prefixLen = strlen(prefix); const char *startMatch, *endMatch; - + /* get the starting point (i.e. where prefix starts, and add prefixLen+1 to it to get be after the first " */ - startMatch = strstr(str, prefix) + prefixLen + 1; + startMatch = strstr(str, prefix); if (startMatch) { + const size_t prefixLen = strlen(prefix); + startMatch += prefixLen + 1; /* get the end point (i.e. where the next occurance of " is after the starting point) */ endMatch = startMatch; @@ -755,7 +756,7 @@ void BLI_str_toupper_ascii(char *str, const size_t len) * * \param str * \param pad - * \return The number of zeto's stripped. + * \return The number of zeros stripped. */ int BLI_str_rstrip_float_zero(char *str, const char pad) { diff --git a/source/blender/blenlib/intern/task.c b/source/blender/blenlib/intern/task.c index 08d40a158ca..a125bf7d8d0 100644 --- a/source/blender/blenlib/intern/task.c +++ b/source/blender/blenlib/intern/task.c @@ -207,7 +207,6 @@ TaskScheduler *BLI_task_scheduler_create(int num_threads) 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); - MEM_freeN(thread); } } } diff --git a/source/blender/blenlib/intern/threads.c b/source/blender/blenlib/intern/threads.c index 42f7a744b94..b60981802aa 100644 --- a/source/blender/blenlib/intern/threads.c +++ b/source/blender/blenlib/intern/threads.c @@ -389,56 +389,45 @@ int BLI_system_num_threads_override_get(void) /* Global Mutex Locks */ +static ThreadMutex *global_mutex_from_type(const int type) +{ + switch (type) { + case LOCK_IMAGE: + return &_image_lock; + case LOCK_DRAW_IMAGE: + return &_image_draw_lock; + case LOCK_VIEWER: + return &_viewer_lock; + case LOCK_CUSTOM1: + return &_custom1_lock; + case LOCK_RCACHE: + return &_rcache_lock; + case LOCK_OPENGL: + return &_opengl_lock; + case LOCK_NODES: + return &_nodes_lock; + case LOCK_MOVIECLIP: + return &_movieclip_lock; + case LOCK_COLORMANAGE: + return &_colormanage_lock; + case LOCK_FFTW: + return &_fftw_lock; + case LOCK_VIEW3D: + return &_view3d_lock; + default: + BLI_assert(0); + return NULL; + } +} + void BLI_lock_thread(int type) { - if (type == LOCK_IMAGE) - pthread_mutex_lock(&_image_lock); - else if (type == LOCK_DRAW_IMAGE) - pthread_mutex_lock(&_image_draw_lock); - else if (type == LOCK_VIEWER) - pthread_mutex_lock(&_viewer_lock); - else if (type == LOCK_CUSTOM1) - pthread_mutex_lock(&_custom1_lock); - else if (type == LOCK_RCACHE) - pthread_mutex_lock(&_rcache_lock); - else if (type == LOCK_OPENGL) - pthread_mutex_lock(&_opengl_lock); - else if (type == LOCK_NODES) - pthread_mutex_lock(&_nodes_lock); - else if (type == LOCK_MOVIECLIP) - pthread_mutex_lock(&_movieclip_lock); - else if (type == LOCK_COLORMANAGE) - pthread_mutex_lock(&_colormanage_lock); - else if (type == LOCK_FFTW) - pthread_mutex_lock(&_fftw_lock); - else if (type == LOCK_VIEW3D) - pthread_mutex_lock(&_view3d_lock); + pthread_mutex_lock(global_mutex_from_type(type)); } void BLI_unlock_thread(int type) { - if (type == LOCK_IMAGE) - pthread_mutex_unlock(&_image_lock); - else if (type == LOCK_DRAW_IMAGE) - pthread_mutex_unlock(&_image_draw_lock); - else if (type == LOCK_VIEWER) - pthread_mutex_unlock(&_viewer_lock); - else if (type == LOCK_CUSTOM1) - pthread_mutex_unlock(&_custom1_lock); - else if (type == LOCK_RCACHE) - pthread_mutex_unlock(&_rcache_lock); - else if (type == LOCK_OPENGL) - pthread_mutex_unlock(&_opengl_lock); - else if (type == LOCK_NODES) - pthread_mutex_unlock(&_nodes_lock); - else if (type == LOCK_MOVIECLIP) - pthread_mutex_unlock(&_movieclip_lock); - else if (type == LOCK_COLORMANAGE) - pthread_mutex_unlock(&_colormanage_lock); - else if (type == LOCK_FFTW) - pthread_mutex_unlock(&_fftw_lock); - else if (type == LOCK_VIEW3D) - pthread_mutex_unlock(&_view3d_lock); + pthread_mutex_unlock(global_mutex_from_type(type)); } /* Mutex Locks */ @@ -619,6 +608,11 @@ void BLI_condition_wait(ThreadCondition *cond, ThreadMutex *mutex) pthread_cond_wait(cond, mutex); } +void BLI_condition_wait_global_mutex(ThreadCondition *cond, const int type) +{ + pthread_cond_wait(cond, global_mutex_from_type(type)); +} + void BLI_condition_notify_one(ThreadCondition *cond) { pthread_cond_signal(cond); diff --git a/source/blender/blenlib/intern/timecode.c b/source/blender/blenlib/intern/timecode.c index 4ae9249ec0d..e755a7ae52c 100644 --- a/source/blender/blenlib/intern/timecode.c +++ b/source/blender/blenlib/intern/timecode.c @@ -72,20 +72,20 @@ size_t BLI_timecode_string_from_time( time = -time; } - if (time >= 3600) { + if (time >= 3600.0f) { /* hours */ /* XXX should we only display a single digit for hours since clips are * VERY UNLIKELY to be more than 1-2 hours max? However, that would * go against conventions... */ hours = (int)time / 3600; - time = (float)fmod(time, 3600); + time = fmodf(time, 3600); } - if (time >= 60) { + if (time >= 60.0f) { /* minutes */ minutes = (int)time / 60; - time = (float)fmod(time, 60); + time = fmodf(time, 60); } if (power <= 0) { @@ -163,6 +163,18 @@ size_t BLI_timecode_string_from_time( } break; } + case USER_TIMECODE_SUBRIP: + { + /* SubRip, like SMPTE milliseconds but seconds and milliseconds are separated by a comma, not a dot... */ + + /* precision of decimal part */ + const int ms_dp = (power <= 0) ? (1 - power) : 1; + const int ms = iroundf((time - (float)seconds) * 1000.0f); + + rlen = BLI_snprintf_rlen( + str, maxncpy, "%s%02d:%02d:%02d,%0*d", neg, hours, minutes, seconds, ms_dp, ms); + break; + } case USER_TIMECODE_SECONDS_ONLY: { /* only show the original seconds display */ diff --git a/source/blender/blenlib/intern/winstuff.c b/source/blender/blenlib/intern/winstuff.c index a67e116969e..32ab16b4b5a 100644 --- a/source/blender/blenlib/intern/winstuff.c +++ b/source/blender/blenlib/intern/winstuff.c @@ -93,7 +93,7 @@ void RegisterBlendExtension(void) char RegCmd[MAX_PATH * 2]; char MBox[256]; char *blender_app; -#ifndef WIN64 +#ifndef _WIN64 BOOL IsWOW64; #endif @@ -158,7 +158,7 @@ void RegisterBlendExtension(void) BLI_getInstallationDir(InstallDir); GetSystemDirectory(SysDir, FILE_MAXDIR); -#ifdef WIN64 +#ifdef _WIN64 ThumbHandlerDLL = "BlendThumb64.dll"; #elif defined(__MINGW32__) ThumbHandlerDLL = "BlendThumb.dll"; |