Fix T43848: Wrong direction recalculating normals

Face islands furthest faces could face towards the center point when connected to sharp edges.

Now check the furthest edge of the furthest face, to test for face winding.

1 files changed, 130 insertions, 17 deletions

diff --git a/source/blender/bmesh/operators/bmo_normals.c b/source/blender/bmesh/operators/bmo_normals.c
index ed49d0751ce..34b3380d1f0 100644
--- a/source/blender/bmesh/operators/bmo_normals.c
+++ b/source/blender/bmesh/operators/bmo_normals.c
@@ -47,28 +47,60 @@ static bool bmo_recalc_normal_edge_filter_cb(BMElem *ele, void *UNUSED(user_data
 }
 
 /**
- * Given an array of faces, recalculate their normals.
- * this functions assumes all faces in the array are connected by edges.
+ * This uses a more comprehensive test to see if the furthest face from the center
+ * is pointing towards the center or not.
  *
- * \param bm
- * \param faces  Array of connected faces.
- * \param faces_len  Length of \a faces
- * \param oflag  Flag to check before doing the actual face flipping.
+ * A simple test could just check the dot product of the faces-normal and the direction from the center,
+ * however this can fail for faces which make a sharp spike. eg:
+ *
+ * <pre>
+ * +
+ * |\ <- face
+ * + +
+ *  \ \
+ *   \ \
+ *    \ +--------------+
+ *     \               |
+ *      \ center -> +  |
+ *       \             |
+ *        +------------+
+ * </pre>
+ *
+ * In the example above, the a\ face can point towards the \a center
+ * which would end up flipping the normals inwards.
+ *
+ * To take these spikes into account, use the normals of the faces edges.
+ * (weight by dot product & edge-length).
  */
-static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int faces_len, const short oflag)
+ #define USE_FACE_EDGE_NORMAL_TEST
+
+/**
+ * The center of the entire island is't necessarily well placed,
+ *
+ * This re-calculated a center relative to this face.
+ */
+#ifdef USE_FACE_EDGE_NORMAL_TEST
+#  define USE_FACE_LOCAL_CENTER_TEST
+#endif
+
+/**
+ * \return a face index in \a faces and set \a r_is_flip if the face is flipped away from the center.
+ */
+static int recalc_face_normals_find_index(BMesh *bm, BMFace **faces, const int faces_len, bool *r_is_flip)
 {
+	float cent_area_accum = 0.0f;
+	float f_len_best_sq;
+
 	float cent[3], tvec[3];
-	float (*faces_center)[3] = MEM_mallocN(sizeof(*faces_center) * faces_len, __func__);
-	float *faces_area = MEM_mallocN(sizeof(*faces_area) * faces_len, __func__);
 	const float cent_fac = 1.0f / (float)faces_len;
-	int i, f_start_index;
-	const short oflag_flip = oflag | FACE_FLIP;
 
-	float cent_area_accum = 0.0f;
-	float f_len_best_sq;
-	BMFace *f;
+	float (*faces_center)[3] = MEM_mallocN(sizeof(*faces_center) * faces_len, __func__);
+	float *faces_area = MEM_mallocN(sizeof(*faces_area) * faces_len, __func__);
+	bool is_flip = false;
+	int f_start_index;
+	int i;
 
-	BLI_LINKSTACK_DECLARE(fstack, BMFace *);
+	UNUSED_VARS_NDEBUG(bm);
 
 	zero_v3(cent);
 
@@ -104,13 +136,94 @@ static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int f
 		}
 	}
 
+#ifdef USE_FACE_EDGE_NORMAL_TEST
+	{
+		BMFace *f_test = faces[f_start_index];
+		BMLoop *l_iter, *l_first;
+		float e_len_best_sq = -FLT_MAX;
+		BMLoop *l_other_best = NULL;
+		float no_edge[3];
+		const float *no_best;
 
-	/* make sure the starting face has the correct winding */
+		l_iter = l_first = BM_FACE_FIRST_LOOP(f_test);
+		do {
+			if (BM_edge_is_manifold(l_iter->e) &&
+			    bmo_recalc_normal_edge_filter_cb((BMElem *)l_iter->e, NULL))
+			{
+				BMLoop *l_other = l_iter->radial_next;
+
+				if (len_squared_v3v3(l_iter->v->co, l_iter->next->v->co) > FLT_EPSILON) {
+					float e_len_test_sq;
+					float e_cent[3];
+					mid_v3_v3v3(e_cent, l_iter->v->co, l_iter->next->v->co);
+					e_len_test_sq = len_squared_v3v3(cent, e_cent);
+					if (e_len_test_sq > e_len_best_sq) {
+						l_other_best = l_other;
+						e_len_best_sq = e_len_test_sq;
+					}
+				}
+			}
+		} while ((l_iter = l_iter->next) != l_first);
+
+		/* furthest edge on furthest face */
+		if (l_other_best) {
+			float e_cent[3];
+
+#ifdef USE_FACE_LOCAL_CENTER_TEST
+			{
+				float f_cent_other[3];
+				BM_face_calc_center_mean_weighted(l_other_best->f, f_cent_other);
+				mid_v3_v3v3(cent, f_cent_other, faces_center[f_start_index]);
+			}
+#endif
+			mid_v3_v3v3(e_cent, l_other_best->e->v1->co, l_other_best->e->v2->co);
+			sub_v3_v3v3(tvec, e_cent, cent);
+
+			madd_v3_v3v3fl(no_edge, f_test->no, l_other_best->f->no, BM_edge_is_contiguous(l_other_best->e) ? 1 : -1);
+			no_best = no_edge;
+		}
+		else {
+			sub_v3_v3v3(tvec, faces_center[f_start_index], cent);
+			no_best = f_test->no;
+		}
+
+		is_flip = (dot_v3v3(tvec, no_best) < 0.0f);
+	}
+#else
 	sub_v3_v3v3(tvec, faces_center[f_start_index], cent);
+	is_flip = (dot_v3v3(tvec, faces[f_start_index]->no) < 0.0f);
+#endif
+
+	/* make sure the starting face has the correct winding */
 	MEM_freeN(faces_center);
 	MEM_freeN(faces_area);
 
-	if (dot_v3v3(tvec, faces[f_start_index]->no) < 0.0f) {
+	*r_is_flip = is_flip;
+	return f_start_index;
+}
+
+/**
+ * Given an array of faces, recalculate their normals.
+ * this functions assumes all faces in the array are connected by edges.
+ *
+ * \param bm
+ * \param faces  Array of connected faces.
+ * \param faces_len  Length of \a faces
+ * \param oflag  Flag to check before doing the actual face flipping.
+ */
+static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int faces_len, const short oflag)
+{
+	int i, f_start_index;
+	const short oflag_flip = oflag | FACE_FLIP;
+	bool is_flip;
+
+	BMFace *f;
+
+	BLI_LINKSTACK_DECLARE(fstack, BMFace *);
+
+	f_start_index = recalc_face_normals_find_index(bm, faces, faces_len, &is_flip);
+
+	if (is_flip) {
 		BMO_elem_flag_enable(bm, faces[f_start_index], FACE_FLIP);
 	}