[Bf-blender-cvs] [1e9003a] surface-deform-modifier: Add is_poly_convex_v3 function

[Luca Rood]

Commit: 1e9003aea5a9da97974fa3bafcc20eb4a0b3c925
Author: Luca Rood
Date:   Fri Nov 25 14:46:11 2016 -0200
Branches: surface-deform-modifier
https://developer.blender.org/rB1e9003aea5a9da97974fa3bafcc20eb4a0b3c925

Add is_poly_convex_v3 function

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

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

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

diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index 514b030..9039225 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -85,6 +85,7 @@ float volume_tetrahedron_v3(const float v1[3], const float v2[3], const float v3
 float volume_tetrahedron_signed_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]);
 
 bool is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]);
+bool is_poly_convex_v3(const float verts[][3], unsigned int nr);
 bool is_quad_convex_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2]);
 bool is_poly_convex_v2(const float verts[][2], unsigned int nr);
 int  is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]);
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index f31d093..654c2ae 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -4791,54 +4791,56 @@ float form_factor_hemi_poly(float p[3], float n[3], float v1[3], float v2[3], fl
  */
 bool is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
 {
-	/**
-	 * Method projects points onto a plane and checks its convex using following method:
-	 *
-	 * - Create a plane from the cross-product of both diagonal vectors.
-	 * - Project all points onto the plane.
-	 * - Subtract for direction vectors.
-	 * - Return true if all corners cross-products point the direction of the plane.
-	 */
+	const float verts[4][3] = {{UNPACK3(v1)}, {UNPACK3(v2)}, {UNPACK3(v3)}, {UNPACK3(v4)}};
+	return is_poly_convex_v3(verts, 4);
+}
+
+/**
+ * Check if polygon is convex
+ */
+bool is_poly_convex_v3(const float verts[][3], unsigned int nr)
+{
+	const float *co_curr, *co_prev;
+	float vec_curr[3], vec_prev[3];
+	float normal[3];
+	unsigned int i;
 
-	/* non-unit length normal, used as a projection plane */
-	float plane[3];
+	if (nr == 3)
+		return true;
 
-	{
-		float v13[3], v24[3];
+	co_prev = verts[nr - 1];
+	co_curr = verts[0];
 
-		sub_v3_v3v3(v13, v1, v3);
-		sub_v3_v3v3(v24, v2, v4);
+	/* Non-unit length normal, just to check angle directions */
+	cross_poly_v3(normal, verts, nr);
 
-		cross_v3_v3v3(plane, v13, v24);
+	sub_v3_v3v3(vec_prev, co_prev, verts[nr - 2]);
 
-		if (len_squared_v3(plane) < FLT_EPSILON) {
-			return false;
-		}
-	}
+	/**
+	 * Implementation note: there is no need to project the vertices onto the normal plane,
+	 * because even if the polygon is highly non-planar, the cross product between
+	 * adjacent edges will always point to the same side as the normal when convex,
+	 * and to the opposite side when concave.
+	 */
 
-	const float *quad_coords[4] = {v1, v2, v3, v4};
-	float        quad_proj[4][3];
+	for (i = 0; i < nr; i++) {
+		float cross[3];
 
-	for (int i = 0; i < 4; i++) {
-		project_plane_v3_v3v3(quad_proj[i], quad_coords[i], plane);
-	}
+		sub_v3_v3v3(vec_curr, co_curr, co_prev);
 
-	float        quad_dirs[4][3];
-	for (int i = 0, j = 3; i < 4; j = i++) {
-		sub_v3_v3v3(quad_dirs[i], quad_proj[i], quad_proj[j]);
-	}
+		cross_v3_v3v3(cross, vec_prev, vec_curr);
 
-	float test_dir[3];
+		if (dot_v3v3(cross, normal) < 0.0f) {
+			return false;
+		}
 
-#define CROSS_SIGN(dir_a, dir_b) \
-	((void)cross_v3_v3v3(test_dir, dir_a, dir_b), (dot_v3v3(plane, test_dir) > 0.0f))
+		copy_v3_v3(vec_prev, vec_curr);
 
-	return (CROSS_SIGN(quad_dirs[0], quad_dirs[1]) &&
-	        CROSS_SIGN(quad_dirs[1], quad_dirs[2]) &&
-	        CROSS_SIGN(quad_dirs[2], quad_dirs[3]) &&
-	        CROSS_SIGN(quad_dirs[3], quad_dirs[0]));
+		co_prev = co_curr;
+		co_curr += 3;
+	}
 
-#undef CROSS_SIGN
+	return true;
 }
 
 bool is_quad_convex_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2])