From 5770d691bbed31d05ecf22383f56df2a4371acfa Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Thu, 3 Apr 2014 21:47:03 +1100 Subject: Optimize BLI_convexhull_aabb_fit_hull_2d, avoid atan2, sin, cos add utility functions for using a 2d unit vector as a rotation matrix mul_v2_v2_cw & mul_v2_v2_ccw --- source/blender/blenlib/BLI_math_vector.h | 2 ++ source/blender/blenlib/intern/convexhull2d.c | 16 ++++++-------- source/blender/blenlib/intern/math_vector_inline.c | 25 ++++++++++++++++++++++ 3 files changed, 33 insertions(+), 10 deletions(-) (limited to 'source/blender/blenlib') diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h index 1f4ccf880fb..a9edfa0ccff 100644 --- a/source/blender/blenlib/BLI_math_vector.h +++ b/source/blender/blenlib/BLI_math_vector.h @@ -117,6 +117,8 @@ MINLINE void mul_v3_v3(float r[3], const float a[3]); MINLINE void mul_v3_v3v3(float r[3], const float a[3], const float b[3]); MINLINE void mul_v4_fl(float r[4], float f); MINLINE void mul_v4_v4fl(float r[3], const float a[3], float f); +MINLINE void mul_v2_v2_cw(float r[2], const float mat[2], const float vec[2]); +MINLINE void mul_v2_v2_ccw(float r[2], const float mat[2], const float vec[2]); MINLINE float mul_project_m4_v3_zfac(float mat[4][4], const float co[3]) ATTR_WARN_UNUSED_RESULT; MINLINE float dot_m3_v3_row_x(float M[3][3], const float a[3]) ATTR_WARN_UNUSED_RESULT; MINLINE float dot_m3_v3_row_y(float M[3][3], const float a[3]) ATTR_WARN_UNUSED_RESULT; diff --git a/source/blender/blenlib/intern/convexhull2d.c b/source/blender/blenlib/intern/convexhull2d.c index 2c29ef042a1..9f509638e3b 100644 --- a/source/blender/blenlib/intern/convexhull2d.c +++ b/source/blender/blenlib/intern/convexhull2d.c @@ -253,28 +253,24 @@ float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned in { unsigned int i, i_prev; float area_best = FLT_MAX; - float angle_best = 0.0f; + float dvec_best[2]; /* best angle, delay atan2 */ i_prev = n - 1; for (i = 0; i < n; i++) { const float *ev_a = points_hull[i]; const float *ev_b = points_hull[i_prev]; - float dvec[2]; + float dvec[2]; /* 2d rotation matrix */ sub_v2_v2v2(dvec, ev_a, ev_b); if (normalize_v2(dvec) != 0.0f) { - float mat[2][2]; + /* rotation matrix */ float min[2] = {FLT_MAX, FLT_MAX}, max[2] = {-FLT_MAX, -FLT_MAX}; - unsigned int j; - const float angle = atan2f(dvec[0], dvec[1]); float area; - angle_to_mat2(mat, angle); - for (j = 0; j < n; j++) { float tvec[2]; - mul_v2_m2v2(tvec, mat, points_hull[j]); + mul_v2_v2_cw(tvec, dvec, points_hull[j]); min[0] = min_ff(min[0], tvec[0]); min[1] = min_ff(min[1], tvec[1]); @@ -290,14 +286,14 @@ float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned in if (area < area_best) { area_best = area; - angle_best = angle; + copy_v2_v2(dvec_best, dvec); } } i_prev = i; } - return angle_best; + return (area_best != FLT_MAX) ? atan2f(dvec_best[0], dvec_best[1]) : 0.0f; } /** diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c index 59d5f7e7627..aed604eddb4 100644 --- a/source/blender/blenlib/intern/math_vector_inline.c +++ b/source/blender/blenlib/intern/math_vector_inline.c @@ -432,6 +432,31 @@ MINLINE void mul_v4_v4fl(float r[4], const float a[4], float f) r[3] = a[3] * f; } +/** + * Avoid doing: + * + * angle = atan2f(dvec[0], dvec[1]); + * angle_to_mat2(mat, angle); + * + * instead use a vector as a matrix. + */ + +MINLINE void mul_v2_v2_cw(float r[2], const float mat[2], const float vec[2]) +{ + BLI_assert(r != vec); + + r[0] = mat[0] * vec[0] + (+mat[1]) * vec[1]; + r[1] = mat[1] * vec[0] + (-mat[0]) * vec[1]; +} + +MINLINE void mul_v2_v2_ccw(float r[2], const float mat[2], const float vec[2]) +{ + BLI_assert(r != vec); + + r[0] = mat[0] * vec[0] + (-mat[1]) * vec[1]; + r[1] = mat[1] * vec[0] + (+mat[0]) * vec[1]; +} + /* note: could add a matrix inline */ MINLINE float mul_project_m4_v3_zfac(float mat[4][4], const float co[3]) { -- cgit v1.2.3