[Bf-blender-cvs] [5770d69] master: Optimize BLI_convexhull_aabb_fit_hull_2d, avoid atan2, sin, cos

[Campbell Barton]

Commit: 5770d691bbed31d05ecf22383f56df2a4371acfa
Author: Campbell Barton
Date:   Thu Apr 3 21:47:03 2014 +1100
https://developer.blender.org/rB5770d691bbed31d05ecf22383f56df2a4371acfa

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

===================================================================

M	source/blender/blenlib/BLI_math_vector.h
M	source/blender/blenlib/intern/convexhull2d.c
M	source/blender/blenlib/intern/math_vector_inline.c

===================================================================

diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h
index 1f4ccf8..a9edfa0 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 2c29ef0..9f50963 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 59d5f7e..aed604e 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])
 {