fix/improve normal calculation, noticed when checking on the previous bugfix.
authorCampbell Barton <ideasman42@gmail.com>
Mon, 8 Jul 2013 13:30:11 +0000 (13:30 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Mon, 8 Jul 2013 13:30:11 +0000 (13:30 +0000)
- 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.

source/blender/bmesh/intern/bmesh_queries.c
source/blender/bmesh/intern/bmesh_queries.h
source/blender/bmesh/operators/bmo_normals.c

index be186e0441b68ed8f99c233b90cf9c91d654f507..c0c4e0f020901e95a92b6103351cf3bcfbac1ea9 100644 (file)
@@ -1758,6 +1758,119 @@ float BM_mesh_calc_volume(BMesh *bm, bool is_signed)
        return vol;
 }
 
+
+/**
+ * TODO (as we need)
+ * - option to walk over edges.
+ * - option to walk over non manifold edges.
+ *
+ * \param bm  the BMesh.
+ * \param r_groups_array  Array of ints to fill in, length of bm->totface.
+ * \param r_group_index  index, length pairs into \a r_groups_array, size of return value
+ * int pairs: (array_start, array_length).
+ * \return The number of groups found.
+ */
+int BM_mesh_calc_face_groups(BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
+                             void *user_data, bool (*filter_fn)(BMEdge *, void *user_data))
+{
+#ifdef DEBUG
+       int group_index_len = 1;
+#else
+       int group_index_len = 32;
+#endif
+
+       int (*group_index)[2] = MEM_mallocN(sizeof(*group_index) * group_index_len, __func__);
+
+       int *group_array = r_groups_array;
+       STACK_DECLARE(group_array);
+
+       int group_curr = 0;
+
+       const unsigned int tot_faces = bm->totface;
+       unsigned int tot_touch = 0;
+
+       BMFace **fstack;
+       STACK_DECLARE(fstack);
+
+       BMIter iter;
+       BMFace *f;
+       int i;
+
+       STACK_INIT(group_array);
+
+       /* init the array */
+       BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
+               BM_elem_index_set(f, i); /* set_inline */
+               BM_elem_flag_disable(f, BM_ELEM_TAG);
+       }
+       bm->elem_index_dirty &= ~BM_FACE;
+
+       /* detect groups */
+       fstack = MEM_mallocN(sizeof(*fstack) * tot_faces, __func__);
+
+       while (tot_touch != tot_faces) {
+               int *fg;
+               bool ok = false;
+
+               BLI_assert(tot_touch < tot_faces);
+
+               STACK_INIT(fstack);
+
+               BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
+                       if (BM_elem_flag_test(f, BM_ELEM_TAG) == false) {
+                               BM_elem_flag_enable(f, BM_ELEM_TAG);
+                               STACK_PUSH(fstack, f);
+                               ok = true;
+                               break;
+                       }
+               }
+
+               BLI_assert(ok == true);
+
+               /* manage arrays */
+               if (group_index_len == group_curr) {
+                       group_index_len *= 2;
+                       group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_index_len);
+               }
+
+               fg = group_index[group_curr];
+               fg[0] = STACK_SIZE(group_array);
+               fg[1] = 0;
+
+               while ((f = STACK_POP(fstack))) {
+                       BMLoop *l_iter, *l_first;
+
+                       /* add face */
+                       STACK_PUSH(group_array, BM_elem_index_get(f));
+                       tot_touch++;
+                       fg[1]++;
+                       /* done */
+
+                       /* search for other faces */
+                       l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+                       do {
+                               BMLoop *l_other = l_iter->radial_next;
+                               if ((l_other != l_iter) && filter_fn(l_iter->e, user_data)) {
+                                       if (BM_elem_flag_test(l_other->f, BM_ELEM_TAG) == false) {
+                                               BM_elem_flag_enable(l_other->f, BM_ELEM_TAG);
+                                               STACK_PUSH(fstack, l_other->f);
+                                       }
+                               }
+                       } while ((l_iter = l_iter->next) != l_first);
+               }
+
+               group_curr++;
+       }
+
+       MEM_freeN(fstack);
+
+       /* reduce alloc to required size */
+       group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_curr);
+       *r_group_index = group_index;
+
+       return group_curr;
+}
+
 float bmesh_subd_falloff_calc(const int falloff, float val)
 {
        switch (falloff) {
index 7d599a9c8afc83af451d621c7d368990e88019ce..94dae1d1d239cb28044a76bc0e8c113369316b45 100644 (file)
@@ -115,6 +115,8 @@ bool BM_face_is_any_vert_flag_test(BMFace *f, const char hflag);
 bool BM_face_is_any_edge_flag_test(BMFace *f, const char hflag);
 
 float BM_mesh_calc_volume(BMesh *bm, bool is_signed);
+int   BM_mesh_calc_face_groups(BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
+                               void *user_data, bool (*filter_fn)(BMEdge *, void *user_data));
 
 /* not really any good place  to put this */
 float bmesh_subd_falloff_calc(const int falloff, float val);
index 88a4d4478bed307c32a5e5b4730ca8be64d0cd6a..7116ef82a320b5633485d482cf5698c90257d47a 100644 (file)
 
 /********* 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);
 }