Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / bmesh / operators / bmo_normals.c
index 025b855..c1656e9 100644 (file)
@@ -1,6 +1,4 @@
 /*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
  * This program is free software; you can redistribute it and/or
  * modify it under the terms of the GNU General Public License
  * as published by the Free Software Foundation; either version 2
  * You should have received a copy of the GNU General Public License
  * along with this program; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * Contributor(s): Joseph Eagar, Campbell Barton
- *
- * ***** END GPL LICENSE BLOCK *****
  */
 
-/** \file blender/bmesh/operators/bmo_normals.c
- *  \ingroup bmesh
+/** \file \ingroup bmesh
  *
  * normal recalculation.
  */
@@ -29,6 +22,7 @@
 #include "MEM_guardedalloc.h"
 
 #include "BLI_math.h"
+#include "BLI_linklist_stack.h"
 
 #include "bmesh.h"
 
 #define FACE_FLIP      (1 << 1)
 #define FACE_TEMP      (1 << 2)
 
-static bool bmo_recalc_normal_edge_filter_cb(BMElem *ele, void *UNUSED(user_data))
+static bool bmo_recalc_normal_loop_filter_cb(const BMLoop *l, void *UNUSED(user_data))
 {
-       return BM_edge_is_manifold((BMEdge *)ele);
+       return BM_edge_is_manifold(l->e);
 }
 
 /**
- * Given an array of faces, recalcualte 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.
+ *
+ * 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>
  *
- * \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.
+ * 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, find the furthest face-loop-vertex.
  */
-static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int faces_len, const short oflag)
+
+/**
+ * \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[3], tvec[3];
-       float (*faces_center)[3] = MEM_mallocN(sizeof(*faces_center) * faces_len, __func__);
+       const float eps = FLT_EPSILON;
+       float cent_area_accum = 0.0f;
+       float cent[3];
        const float cent_fac = 1.0f / (float)faces_len;
-       int i, f_start_index;
-       const short oflag_flip = oflag | FACE_FLIP;
 
-       float f_len_best;
-       BMFace *f;
+       bool is_flip = false;
+       int f_start_index;
+       int i;
 
-       BMFace **fstack = MEM_mallocN(sizeof(*fstack) * faces_len, __func__);
-       STACK_DECLARE(fstack);
+       /* Search for the best loop. Members are compared in-order defined here. */
+       struct {
+               /* Squared distance from the center to the loops vertex 'l->v'.
+                * The normalized direction between the center and this vertex is also used for the dot-products below. */
+               float dist_sq;
+               /* Signed dot product using the normalized edge vector,
+                * (best of 'l->prev->v' or 'l->next->v'). */
+               float edge_dot;
+               /* Unsigned dot product using the loop-normal
+                * (sign is used to check if we need to flip) */
+               float loop_dot;
+       } best, test;
+
+       UNUSED_VARS_NDEBUG(bm);
 
        zero_v3(cent);
 
        /* 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);
-
-               BLI_assert(BMO_elem_flag_test(bm, faces[i], FACE_TEMP) == 0);
+               float f_cent[3];
+               const float f_area = BM_face_calc_area(faces[i]);
+               BM_face_calc_center_median_weighted(faces[i], f_cent);
+               madd_v3_v3fl(cent, f_cent, cent_fac * f_area);
+               cent_area_accum += f_area;
+
+               BLI_assert(BMO_face_flag_test(bm, faces[i], FACE_TEMP) == 0);
+               BLI_assert(BM_face_is_normal_valid(faces[i]));
        }
 
-       f_len_best = -FLT_MAX;
+       if (cent_area_accum != 0.0f) {
+               mul_v3_fl(cent, 1.0f / cent_area_accum);
+       }
 
+       /* Distances must start above zero,
+        * or we can't do meaningful calculations based on the direction to the center */
+       best.dist_sq = eps;
+       best.edge_dot = best.loop_dot = -FLT_MAX;
+
+       /* used in degenerate cases only */
+       f_start_index = 0;
+
+       /**
+        * Find the outer-most vertex, comparing distance to the center,
+        * then the outer-most loop attached to that vertex.
+        *
+        * Important this is correctly detected,
+        * where casting a ray from the center wont hit any loops past this one.
+        * Otherwise the result may be incorrect.
+        */
        for (i = 0; i < faces_len; i++) {
-               float f_len_test;
+               BMLoop *l_iter, *l_first;
 
-               if ((f_len_test = len_squared_v3v3(faces_center[i], cent)) > f_len_best) {
-                       f_len_best = f_len_test;
-                       f_start_index = i;
-               }
+               l_iter = l_first = BM_FACE_FIRST_LOOP(faces[i]);
+               do {
+                       bool is_best_dist_sq;
+                       float dir[3];
+                       sub_v3_v3v3(dir, l_iter->v->co, cent);
+                       test.dist_sq = len_squared_v3(dir);
+                       is_best_dist_sq =      (test.dist_sq  > best.dist_sq);
+                       if (is_best_dist_sq || (test.dist_sq == best.dist_sq)) {
+                               float edge_dir_pair[2][3];
+                               mul_v3_fl(dir, 1.0f / sqrtf(test.dist_sq));
+
+                               sub_v3_v3v3(edge_dir_pair[0], l_iter->next->v->co, l_iter->v->co);
+                               sub_v3_v3v3(edge_dir_pair[1], l_iter->prev->v->co, l_iter->v->co);
+
+                               if ((normalize_v3(edge_dir_pair[0]) > eps) &&
+                                   (normalize_v3(edge_dir_pair[1]) > eps))
+                               {
+                                       bool is_best_edge_dot;
+                                       test.edge_dot = max_ff(dot_v3v3(dir, edge_dir_pair[0]),
+                                                              dot_v3v3(dir, edge_dir_pair[1]));
+                                       is_best_edge_dot =                         (test.edge_dot  > best.edge_dot);
+                                       if (is_best_dist_sq || is_best_edge_dot || (test.edge_dot == best.edge_dot)) {
+                                               float loop_dir[3];
+                                               cross_v3_v3v3(loop_dir, edge_dir_pair[0], edge_dir_pair[1]);
+                                               if (normalize_v3(loop_dir) > eps) {
+                                                       float loop_dir_dot;
+                                                       /* Highly unlikely the furthest loop is also the concave part of an ngon,
+                                                        * but it can be contrived with _very_ non-planar faces - so better check. */
+                                                       if (UNLIKELY(dot_v3v3(loop_dir, l_iter->f->no) < 0.0f)) {
+                                                               negate_v3(loop_dir);
+                                                       }
+                                                       loop_dir_dot = dot_v3v3(dir, loop_dir);
+                                                       test.loop_dot = fabsf(loop_dir_dot);
+                                                       if (is_best_dist_sq || is_best_edge_dot || (test.loop_dot > best.loop_dot)) {
+                                                               best = test;
+                                                               f_start_index = i;
+                                                               is_flip = (loop_dir_dot < 0.0f);
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+               } while ((l_iter = l_iter->next) != l_first);
        }
 
-       /* make sure the starting face has the correct winding */
-       sub_v3_v3v3(tvec, faces_center[f_start_index], cent);
-       if (dot_v3v3(tvec, faces[f_start_index]->no) < 0.0f) {
-               BMO_elem_flag_enable(bm, faces[f_start_index], FACE_FLIP);
-       }
+       *r_is_flip = is_flip;
+       return f_start_index;
+}
 
-       MEM_freeN(faces_center);
+/**
+ * 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_face_flag_enable(bm, faces[f_start_index], FACE_FLIP);
+       }
 
        /* 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);
+       BLI_LINKSTACK_INIT(fstack);
 
-       STACK_PUSH(fstack, faces[f_start_index]);
-       BMO_elem_flag_enable(bm, faces[f_start_index], FACE_TEMP);
+       BLI_LINKSTACK_PUSH(fstack, faces[f_start_index]);
+       BMO_face_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);
+       while ((f = BLI_LINKSTACK_POP(fstack))) {
+               const bool flip_state = BMO_face_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((BMElem *)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);
+                       if ((l_other != l_iter) && bmo_recalc_normal_loop_filter_cb(l_iter, NULL)) {
+                               if (!BMO_face_flag_test(bm, l_other->f, FACE_TEMP)) {
+                                       BMO_face_flag_enable(bm, l_other->f, FACE_TEMP);
+                                       BMO_face_flag_set(bm, l_other->f, FACE_FLIP, (l_other->v == l_iter->v) != flip_state);
+                                       BLI_LINKSTACK_PUSH(fstack, l_other->f);
                                }
                        }
                } while ((l_iter = l_iter->next) != l_first);
        }
 
-       MEM_freeN(fstack);
+       BLI_LINKSTACK_FREE(fstack);
 
        /* 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) {
+               if (BMO_face_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);
+               BMO_face_flag_disable(bm, faces[i], FACE_TEMP);
        }
 }
 
@@ -147,19 +254,19 @@ static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int f
 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__);
 
        int (*group_index)[2];
-       const int group_tot = BM_mesh_calc_face_groups(bm, groups_array, &group_index,
-                                                      bmo_recalc_normal_edge_filter_cb, NULL,
-                                                      0, BM_EDGE);
+       const int group_tot = BM_mesh_calc_face_groups(
+               bm, groups_array, &group_index,
+               bmo_recalc_normal_loop_filter_cb, NULL,
+               0, BM_EDGE);
        int i;
 
-
        BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces", BM_FACE, FACE_FLAG);
 
+       BM_mesh_elem_table_ensure(bm, BM_FACE);
+
        for (i = 0; i < group_tot; i++) {
                const int fg_sta = group_index[i][0];
                const int fg_len = group_index[i][1];
@@ -167,10 +274,10 @@ void bmo_recalc_face_normals_exec(BMesh *bm, BMOperator *op)
                bool is_calc = false;
 
                for (j = 0; j < fg_len; j++) {
-                       faces_grp[j] = faces_arr[groups_array[fg_sta + j]];
+                       faces_grp[j] = BM_face_at_index(bm, groups_array[fg_sta + j]);
 
                        if (is_calc == false) {
-                               is_calc = BMO_elem_flag_test_bool(bm, faces_grp[j], FACE_FLAG);
+                               is_calc = BMO_face_flag_test_bool(bm, faces_grp[j], FACE_FLAG);
                        }
                }
 
@@ -179,8 +286,6 @@ void bmo_recalc_face_normals_exec(BMesh *bm, BMOperator *op)
                }
        }
 
-
-       if (faces_arr) MEM_freeN(faces_arr);
        MEM_freeN(faces_grp);
 
        MEM_freeN(groups_array);