[Bf-blender-cvs] [dbf1257] master: Minor optimization for scanfill

[Campbell Barton]

Commit: dbf1257b14582d5c6cabbed01ef1bf89860106fd
Author: Campbell Barton
Date:   Wed Apr 20 09:52:27 2016 +1000
Branches: master
https://developer.blender.org/rBdbf1257b14582d5c6cabbed01ef1bf89860106fd

Minor optimization for scanfill

Replace angle with with cosine calculation.

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

M	source/blender/blenlib/BLI_math_vector.h
M	source/blender/blenlib/intern/math_vector.c
M	source/blender/blenlib/intern/scanfill.c

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

diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h
index c51446d..c44fcf4 100644
--- a/source/blender/blenlib/BLI_math_vector.h
+++ b/source/blender/blenlib/BLI_math_vector.h
@@ -272,6 +272,7 @@ float angle_normalized_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED
 float angle_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT;
 float angle_v3v3v3(const float a[3], const float b[3], const float c[3]) ATTR_WARN_UNUSED_RESULT;
 float cos_v3v3v3(const float p1[3], const float p2[3], const float p3[3]) ATTR_WARN_UNUSED_RESULT;
+float cos_v2v2v2(const float p1[2], const float p2[2], const float p3[2]) ATTR_WARN_UNUSED_RESULT;
 float angle_normalized_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT;
 float angle_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT;
 float angle_signed_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT;
diff --git a/source/blender/blenlib/intern/math_vector.c b/source/blender/blenlib/intern/math_vector.c
index 8d33e04..72a3da2 100644
--- a/source/blender/blenlib/intern/math_vector.c
+++ b/source/blender/blenlib/intern/math_vector.c
@@ -397,6 +397,19 @@ float angle_v2v2v2(const float v1[2], const float v2[2], const float v3[2])
 	return angle_normalized_v2v2(vec1, vec2);
 }
 
+/* Quicker than full angle computation */
+float cos_v2v2v2(const float p1[2], const float p2[2], const float p3[2])
+{
+	float vec1[2], vec2[2];
+
+	sub_v2_v2v2(vec1, p2, p1);
+	sub_v2_v2v2(vec2, p2, p3);
+	normalize_v2(vec1);
+	normalize_v2(vec2);
+
+	return dot_v2v2(vec1, vec2);
+}
+
 /* Return the shortest angle in radians between the 2 vectors */
 float angle_v2v2(const float v1[2], const float v2[2])
 {
diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c
index 8a96dae..e913499 100644
--- a/source/blender/blenlib/intern/scanfill.c
+++ b/source/blender/blenlib/intern/scanfill.c
@@ -602,7 +602,7 @@ static unsigned int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int fl
 			else {
 				/* test rest of vertices */
 				ScanFillVertLink *best_sc = NULL;
-				float best_angle = 3.14f;
+				float angle_best_cos = -1.0f;
 				float miny;
 				bool firsttime = false;
 				
@@ -633,21 +633,18 @@ static unsigned int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int fl
 										best_sc = sc1;
 									}
 									else {
-										float angle;
-										
 										/* prevent angle calc for the simple cases only 1 vertex is found */
 										if (firsttime == false) {
-											best_angle = angle_v2v2v2(v2->xy, v1->xy, best_sc->vert->xy);
+											angle_best_cos = cos_v2v2v2(v2->xy, v1->xy, best_sc->vert->xy);
 											firsttime = true;
 										}
 
-										angle = angle_v2v2v2(v2->xy, v1->xy, sc1->vert->xy);
-										if (angle < best_angle) {
+										const float angle_test_cos = cos_v2v2v2(v2->xy, v1->xy, sc1->vert->xy);
+										if (angle_test_cos > angle_best_cos) {
 											best_sc = sc1;
-											best_angle = angle;
+											angle_best_cos = angle_test_cos;
 										}
 									}
-										
 								}
 							}
 						}