fix/improve normal calculation, noticed when checking on the previous bugfix.

- normals depended on the meshes rotation, so you could rotate Suzzane and in some cases one of the eye normals would be flipped.
- normals depended on the meshes placement in relation to the meshes center, now find the outer most face by each face-island center.

1 files changed, 115 insertions, 70 deletions

diff --git a/source/blender/bmesh/operators/bmo_normals.c b/source/blender/bmesh/operators/bmo_normals.c
index 88a4d4478be..7116ef82a32 100644
--- a/source/blender/bmesh/operators/bmo_normals.c
+++ b/source/blender/bmesh/operators/bmo_normals.c
@@ -36,103 +36,148 @@
 
 /********* righthand faces implementation ****** */
 
-#define FACE_VIS	1
-#define FACE_FLAG	2
+#define FACE_FLAG	(1 << 0)
+#define FACE_FLIP	(1 << 1)
+#define FACE_TEMP	(1 << 2)
 
-/*
- * put normal to the outside, and set the first direction flags in edges
- *
- * then check the object, and set directions / direction-flags: but only for edges with 1 or 2 faces
- * this is in fact the 'select connected'
+static bool bmo_recalc_normal_edge_filter_cb(BMEdge *e, void *UNUSED(user_data))
+{
+	return BM_edge_is_manifold(e);
+}
+
+/**
+ * Given an array of faces, recalcualte their normals.
+ * this functions assumes all faces in the array are connected by edges.
  *
- * in case all faces were not done: start over with 'find the ultimate ...' */
+ * \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)
+{
+	float cent[3];
+	float (*faces_center)[3] = MEM_mallocN(sizeof(*faces_center) * faces_len, __func__);
+	const float cent_fac = 1.0f / (float)faces_len;
+	int i, f_start_index;
+	const short oflag_flip = oflag | FACE_FLIP;
 
-/* NOTE: BM_ELEM_TAG is used on faces to tell if they are flipped. */
+	float f_len_best;
+	BMFace *f;
 
-void bmo_recalc_face_normals_exec(BMesh *bm, BMOperator *op)
-{
-	BMFace **fstack;
+	BMFace **fstack = MEM_mallocN(sizeof(*fstack) * faces_len, __func__);
 	STACK_DECLARE(fstack);
-	const unsigned int tot_faces = BMO_slot_buffer_count(op->slots_in, "faces");
-	unsigned int tot_touch = 0;
 
-	BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces", BM_FACE, FACE_FLAG);
+	zero_v3(cent);
 
-	fstack = MEM_mallocN(sizeof(*fstack) * tot_faces, __func__);
+	/* first calculate the center */
+	for (i = 0; i < faces_len; i++) {
+		float *f_cent = faces_center[i];
+		BM_face_calc_center_mean_weighted(faces[i], f_cent);
+		madd_v3_v3fl(cent, f_cent, cent_fac);
 
-	while (tot_touch != tot_faces) {
-		BMOIter siter;
-		float f_len_best = -FLT_MAX;
-		BMFace *f, *f_start = NULL;
-		float f_start_cent[3];
+		BLI_assert(BMO_elem_flag_test(bm, faces[i], FACE_TEMP) == 0);
+	}
 
-		/* find a starting face */
-		BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
-			float f_cent[3];
-			float f_len_test;
+	f_len_best = -FLT_MAX;
 
-			/* clear dirty flag */
-			BM_elem_flag_disable(f, BM_ELEM_TAG);
+	for (i = 0; i < faces_len; i++) {
+		float f_len_test;
 
-			if (BMO_elem_flag_test(bm, f, FACE_VIS))
-				continue;
+		if ((f_len_test = len_squared_v3v3(faces_center[i], cent)) > f_len_best) {
+			f_len_best = f_len_test;
+			f_start_index = i;
+		}
+	}
 
-			if (!f_start) f_start = f;
+	/* make sure the starting face has the correct winding */
+	if (dot_v3v3(faces_center[f_start_index], faces[f_start_index]->no) < 0.0f) {
+		BMO_elem_flag_enable(bm, faces[f_start_index], FACE_FLIP);
+	}
 
-			BM_face_calc_center_bounds(f, f_cent);
+	MEM_freeN(faces_center);
 
-			if ((f_len_test = len_squared_v3(f_cent)) > f_len_best) {
-				f_len_best = f_len_test;
-				f_start = f;
-				copy_v3_v3(f_start_cent, f_cent);
+	/* now that we've found our starting face, make all connected faces
+	 * have the same winding.  this is done recursively, using a manual
+	 * stack (if we use simple function recursion, we'd end up overloading
+	 * the stack on large meshes). */
+	STACK_INIT(fstack);
+
+	STACK_PUSH(fstack, faces[f_start_index]);
+	BMO_elem_flag_enable(bm, faces[f_start_index], FACE_TEMP);
+
+	while ((f = STACK_POP(fstack))) {
+		const bool flip_state = BMO_elem_flag_test_bool(bm, f, FACE_FLIP);
+		BMLoop *l_iter, *l_first;
+
+		l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+		do {
+			BMLoop *l_other = l_iter->radial_next;
+
+			if ((l_other != l_iter) && bmo_recalc_normal_edge_filter_cb(l_iter->e, NULL)) {
+				if (!BMO_elem_flag_test(bm, l_other->f, FACE_TEMP)) {
+					BMO_elem_flag_enable(bm, l_other->f, FACE_TEMP);
+					BMO_elem_flag_set(bm, l_other->f, FACE_FLIP, (l_other->v == l_iter->v) != flip_state);
+					STACK_PUSH(fstack, l_other->f);
+				}
 			}
-		}
+		} while ((l_iter = l_iter->next) != l_first);
+	}
 
-		/* check sanity (while loop ensures) */
-		BLI_assert(f_start != NULL);
+	MEM_freeN(fstack);
 
-		/* make sure the starting face has the correct winding */
-		if (dot_v3v3(f_start_cent, f_start->no) < 0.0f) {
-			BM_face_normal_flip(bm, f_start);
+	/* apply flipping to oflag'd faces */
+	for (i = 0; i < faces_len; i++) {
+		if (BMO_elem_flag_test(bm, faces[i], oflag_flip) == oflag_flip) {
+			BM_face_normal_flip(bm, faces[i]);
 		}
+		BMO_elem_flag_disable(bm, faces[i], FACE_TEMP);
+	}
+}
 
-		/* now that we've found our starting face, make all connected faces
-		 * have the same winding.  this is done recursively, using a manual
-		 * stack (if we use simple function recursion, we'd end up overloading
-		 * the stack on large meshes). */
-		STACK_INIT(fstack);
-
-		STACK_PUSH(fstack, f_start);
-		BMO_elem_flag_enable(bm, f_start, FACE_VIS);
-		tot_touch++;
+/*
+ * put normal to the outside, and set the first direction flags in edges
+ *
+ * then check the object, and set directions / direction-flags: but only for edges with 1 or 2 faces
+ * this is in fact the 'select connected'
+ *
+ * in case all faces were not done: start over with 'find the ultimate ...' */
 
-		while ((f = STACK_POP(fstack))) {
-			BMIter liter;
-			BMLoop *l;
+void bmo_recalc_face_normals_exec(BMesh *bm, BMOperator *op)
+{
+	int *groups_array = MEM_mallocN(sizeof(groups_array) * bm->totface, __func__);
+	int faces_len;
+	BMFace **faces_arr = BM_iter_as_arrayN(bm, BM_FACES_OF_MESH, NULL, &faces_len, NULL, 0);
+	BMFace **faces_grp = MEM_mallocN(sizeof(faces_grp) * bm->totface, __func__);
 
-			BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
-				BMLoop *l_other = l->radial_next;
+	int (*group_index)[2];
+	const int group_tot = BM_mesh_calc_face_groups(bm, groups_array, &group_index,
+	                                               NULL, bmo_recalc_normal_edge_filter_cb);
+	int i;
 
-				if ((l_other == l) || l_other->radial_next != l) {
-					continue;
-				}
 
-				if (BMO_elem_flag_test(bm, l_other->f, FACE_FLAG)) {
-					if (!BMO_elem_flag_test(bm, l_other->f, FACE_VIS)) {
-						BMO_elem_flag_enable(bm, l_other->f, FACE_VIS);
-						tot_touch++;
+	BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces", BM_FACE, FACE_FLAG);
 
+	for (i = 0; i < group_tot; i++) {
+		const int fg_sta = group_index[i][0];
+		const int fg_len = group_index[i][1];
+		int j;
+		bool is_calc = false;
 
-						if (l_other->v == l->v) {
-							BM_face_normal_flip(bm, l_other->f);
-						}
+		for (j = 0; j < fg_len; j++) {
+			faces_grp[j] = faces_arr[groups_array[fg_sta + j]];
+			is_calc |= BMO_elem_flag_test_bool(bm, faces_grp[j], FACE_FLAG);
+		}
 
-						STACK_PUSH(fstack, l_other->f);
-					}
-				}
-			}
+		if (is_calc) {
+			bmo_recalc_face_normals_array(bm, faces_grp, fg_len, FACE_FLAG);
 		}
 	}
 
-	MEM_freeN(fstack);
+
+	if (faces_arr) MEM_freeN(faces_arr);
+	MEM_freeN(faces_grp);
+
+	MEM_freeN(groups_array);
+	MEM_freeN(group_index);
 }