[Bf-blender-cvs] [07851dd] master: Math Lib: replace point in polygon function with one thats ~23x faster.

Campbell Barton noreply at git.blender.org
Sun Dec 29 04:55:45 CET 2013


Commit: 07851dd8df23f716b60aa215c8cd9f7c591b0fde
Author: Campbell Barton
Date:   Sun Dec 29 14:46:56 2013 +1100
https://developer.blender.org/rB07851dd8df23f716b60aa215c8cd9f7c591b0fde

Math Lib: replace point in polygon function with one thats ~23x faster.

rather then using angle summing, use line intersection checks.

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

M	source/blender/blenlib/intern/math_geom.c

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

diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index bf5ae8f..cfbf814 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -735,6 +735,7 @@ int isect_line_sphere_v2(const float l1[2], const float l2[2],
 }
 
 /* point in polygon (keep float and int versions in sync) */
+#if 0
 bool isect_point_poly_v2(const float pt[2], const float verts[][2], const unsigned int nr,
                          const bool use_holes)
 {
@@ -816,6 +817,39 @@ bool isect_point_poly_v2_int(const int pt[2], const int verts[][2], const unsign
 	}
 }
 
+#else
+
+bool isect_point_poly_v2(const float pt[2], const float verts[][2], const unsigned int nr,
+                         const bool UNUSED(use_holes))
+{
+	unsigned int i, j;
+	bool isect = false;
+	for (i = 0, j = nr - 1; i < nr; j = i++) {
+		if (((verts[i][1] > pt[1]) != (verts[j][1] > pt[1])) &&
+		    (pt[0] < (verts[j][0] - verts[i][0]) * (pt[1] - verts[i][1]) / (verts[j][1] - verts[i][1]) + verts[i][0]))
+		{
+			isect = !isect;
+		}
+	}
+	return isect;
+}
+bool isect_point_poly_v2_int(const int pt[2], const int verts[][2], const unsigned int nr,
+                             const bool UNUSED(use_holes))
+{
+	unsigned int i, j;
+	bool isect = false;
+	for (i = 0, j = nr - 1; i < nr; j = i++) {
+		if (((verts[i][1] > pt[1]) != (verts[j][1] > pt[1])) &&
+		    (pt[0] < (verts[j][0] - verts[i][0]) * (pt[1] - verts[i][1]) / (verts[j][1] - verts[i][1]) + verts[i][0]))
+		{
+			isect = !isect;
+		}
+	}
+	return isect;
+}
+
+#endif
+
 /* point in tri */
 
 /* only single direction */




More information about the Bf-blender-cvs mailing list