Merge branch 'master' into blender2.8
[blender.git] / source / blender / bmesh / operators / bmo_normals.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar, Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/operators/bmo_normals.c
24  *  \ingroup bmesh
25  *
26  * normal recalculation.
27  */
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_math.h"
32 #include "BLI_linklist_stack.h"
33
34 #include "bmesh.h"
35
36 #include "intern/bmesh_operators_private.h" /* own include */
37
38 /********* righthand faces implementation ****** */
39
40 #define FACE_FLAG       (1 << 0)
41 #define FACE_FLIP       (1 << 1)
42 #define FACE_TEMP       (1 << 2)
43
44 static bool bmo_recalc_normal_loop_filter_cb(const BMLoop *l, void *UNUSED(user_data))
45 {
46         return BM_edge_is_manifold(l->e);
47 }
48
49 /**
50  * This uses a more comprehensive test to see if the furthest face from the center
51  * is pointing towards the center or not.
52  *
53  * A simple test could just check the dot product of the faces-normal and the direction from the center,
54  * however this can fail for faces which make a sharp spike. eg:
55  *
56  * <pre>
57  * +
58  * |\ <- face
59  * + +
60  *  \ \
61  *   \ \
62  *    \ +--------------+
63  *     \               |
64  *      \ center -> +  |
65  *       \             |
66  *        +------------+
67  * </pre>
68  *
69  * In the example above, the a\ face can point towards the \a center
70  * which would end up flipping the normals inwards.
71  *
72  * To take these spikes into account, find the furthest face-loop-vertex.
73  */
74
75 /**
76  * \return a face index in \a faces and set \a r_is_flip if the face is flipped away from the center.
77  */
78 static int recalc_face_normals_find_index(BMesh *bm, BMFace **faces, const int faces_len, bool *r_is_flip)
79 {
80         const float eps = FLT_EPSILON;
81         float cent_area_accum = 0.0f;
82         float cent[3];
83         const float cent_fac = 1.0f / (float)faces_len;
84
85         bool is_flip = false;
86         int f_start_index;
87         int i;
88
89         /* Search for the best loop. Members are compared in-order defined here. */
90         struct {
91                 /* Squared distance from the center to the loops vertex 'l->v'.
92                  * The normalized direction between the center and this vertex is also used for the dot-products below. */
93                 float dist_sq;
94                 /* Signed dot product using the normalized edge vector,
95                  * (best of 'l->prev->v' or 'l->next->v'). */
96                 float edge_dot;
97                 /* Unsigned dot product using the loop-normal
98                  * (sign is used to check if we need to flip) */
99                 float loop_dot;
100         } best, test;
101
102         UNUSED_VARS_NDEBUG(bm);
103
104         zero_v3(cent);
105
106         /* first calculate the center */
107         for (i = 0; i < faces_len; i++) {
108                 float f_cent[3];
109                 const float f_area = BM_face_calc_area(faces[i]);
110                 BM_face_calc_center_mean_weighted(faces[i], f_cent);
111                 madd_v3_v3fl(cent, f_cent, cent_fac * f_area);
112                 cent_area_accum += f_area;
113
114                 BLI_assert(BMO_face_flag_test(bm, faces[i], FACE_TEMP) == 0);
115                 BLI_assert(BM_face_is_normal_valid(faces[i]));
116         }
117
118         if (cent_area_accum != 0.0f) {
119                 mul_v3_fl(cent, 1.0f / cent_area_accum);
120         }
121
122         /* Distances must start above zero,
123          * or we can't do meaningful calculations based on the direction to the center */
124         best.dist_sq = eps;
125         best.edge_dot = best.loop_dot = -FLT_MAX;
126
127         /* used in degenerate cases only */
128         f_start_index = 0;
129
130         /**
131          * Find the outer-most vertex, comparing distance to the center,
132          * then the outer-most loop attached to that vertex.
133          *
134          * Important this is correctly detected,
135          * where casting a ray from the center wont hit any loops past this one.
136          * Otherwise the result may be incorrect.
137          */
138         for (i = 0; i < faces_len; i++) {
139                 BMLoop *l_iter, *l_first;
140
141                 l_iter = l_first = BM_FACE_FIRST_LOOP(faces[i]);
142                 do {
143                         bool is_best_dist_sq;
144                         float dir[3];
145                         sub_v3_v3v3(dir, l_iter->v->co, cent);
146                         test.dist_sq = len_squared_v3(dir);
147                         is_best_dist_sq =      (test.dist_sq  > best.dist_sq);
148                         if (is_best_dist_sq || (test.dist_sq == best.dist_sq)) {
149                                 float edge_dir_pair[2][3];
150                                 mul_v3_fl(dir, 1.0f / sqrtf(test.dist_sq));
151
152                                 sub_v3_v3v3(edge_dir_pair[0], l_iter->next->v->co, l_iter->v->co);
153                                 sub_v3_v3v3(edge_dir_pair[1], l_iter->prev->v->co, l_iter->v->co);
154
155                                 if ((normalize_v3(edge_dir_pair[0]) > eps) &&
156                                     (normalize_v3(edge_dir_pair[1]) > eps))
157                                 {
158                                         bool is_best_edge_dot;
159                                         test.edge_dot = max_ff(dot_v3v3(dir, edge_dir_pair[0]),
160                                                                dot_v3v3(dir, edge_dir_pair[1]));
161                                         is_best_edge_dot =                         (test.edge_dot  > best.edge_dot);
162                                         if (is_best_dist_sq || is_best_edge_dot || (test.edge_dot == best.edge_dot)) {
163                                                 float loop_dir[3];
164                                                 cross_v3_v3v3(loop_dir, edge_dir_pair[0], edge_dir_pair[1]);
165                                                 if (normalize_v3(loop_dir) > eps) {
166                                                         float loop_dir_dot;
167                                                         /* Highly unlikely the furthest loop is also the concave part of an ngon,
168                                                          * but it can be contrived with _very_ non-planar faces - so better check. */
169                                                         if (UNLIKELY(dot_v3v3(loop_dir, l_iter->f->no) < 0.0f)) {
170                                                                 negate_v3(loop_dir);
171                                                         }
172                                                         loop_dir_dot = dot_v3v3(dir, loop_dir);
173                                                         test.loop_dot = fabsf(loop_dir_dot);
174                                                         if (is_best_dist_sq || is_best_edge_dot || (test.loop_dot > best.loop_dot)) {
175                                                                 best = test;
176                                                                 f_start_index = i;
177                                                                 is_flip = (loop_dir_dot < 0.0f);
178                                                         }
179                                                 }
180                                         }
181                                 }
182                         }
183                 } while ((l_iter = l_iter->next) != l_first);
184         }
185
186         *r_is_flip = is_flip;
187         return f_start_index;
188 }
189
190 /**
191  * Given an array of faces, recalculate their normals.
192  * this functions assumes all faces in the array are connected by edges.
193  *
194  * \param bm
195  * \param faces  Array of connected faces.
196  * \param faces_len  Length of \a faces
197  * \param oflag  Flag to check before doing the actual face flipping.
198  */
199 static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int faces_len, const short oflag)
200 {
201         int i, f_start_index;
202         const short oflag_flip = oflag | FACE_FLIP;
203         bool is_flip;
204
205         BMFace *f;
206
207         BLI_LINKSTACK_DECLARE(fstack, BMFace *);
208
209         f_start_index = recalc_face_normals_find_index(bm, faces, faces_len, &is_flip);
210
211         if (is_flip) {
212                 BMO_face_flag_enable(bm, faces[f_start_index], FACE_FLIP);
213         }
214
215         /* now that we've found our starting face, make all connected faces
216          * have the same winding.  this is done recursively, using a manual
217          * stack (if we use simple function recursion, we'd end up overloading
218          * the stack on large meshes). */
219         BLI_LINKSTACK_INIT(fstack);
220
221         BLI_LINKSTACK_PUSH(fstack, faces[f_start_index]);
222         BMO_face_flag_enable(bm, faces[f_start_index], FACE_TEMP);
223
224         while ((f = BLI_LINKSTACK_POP(fstack))) {
225                 const bool flip_state = BMO_face_flag_test_bool(bm, f, FACE_FLIP);
226                 BMLoop *l_iter, *l_first;
227
228                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
229                 do {
230                         BMLoop *l_other = l_iter->radial_next;
231
232                         if ((l_other != l_iter) && bmo_recalc_normal_loop_filter_cb(l_iter, NULL)) {
233                                 if (!BMO_face_flag_test(bm, l_other->f, FACE_TEMP)) {
234                                         BMO_face_flag_enable(bm, l_other->f, FACE_TEMP);
235                                         BMO_face_flag_set(bm, l_other->f, FACE_FLIP, (l_other->v == l_iter->v) != flip_state);
236                                         BLI_LINKSTACK_PUSH(fstack, l_other->f);
237                                 }
238                         }
239                 } while ((l_iter = l_iter->next) != l_first);
240         }
241
242         BLI_LINKSTACK_FREE(fstack);
243
244         /* apply flipping to oflag'd faces */
245         for (i = 0; i < faces_len; i++) {
246                 if (BMO_face_flag_test(bm, faces[i], oflag_flip) == oflag_flip) {
247                         BM_face_normal_flip(bm, faces[i]);
248                 }
249                 BMO_face_flag_disable(bm, faces[i], FACE_TEMP);
250         }
251 }
252
253 /*
254  * put normal to the outside, and set the first direction flags in edges
255  *
256  * then check the object, and set directions / direction-flags: but only for edges with 1 or 2 faces
257  * this is in fact the 'select connected'
258  *
259  * in case all faces were not done: start over with 'find the ultimate ...' */
260
261 void bmo_recalc_face_normals_exec(BMesh *bm, BMOperator *op)
262 {
263         int *groups_array = MEM_mallocN(sizeof(*groups_array) * bm->totface, __func__);
264         BMFace **faces_grp = MEM_mallocN(sizeof(*faces_grp) * bm->totface, __func__);
265
266         int (*group_index)[2];
267         const int group_tot = BM_mesh_calc_face_groups(
268                 bm, groups_array, &group_index,
269                 bmo_recalc_normal_loop_filter_cb, NULL,
270                 0, BM_EDGE);
271         int i;
272
273         BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces", BM_FACE, FACE_FLAG);
274
275         BM_mesh_elem_table_ensure(bm, BM_FACE);
276
277         for (i = 0; i < group_tot; i++) {
278                 const int fg_sta = group_index[i][0];
279                 const int fg_len = group_index[i][1];
280                 int j;
281                 bool is_calc = false;
282
283                 for (j = 0; j < fg_len; j++) {
284                         faces_grp[j] = BM_face_at_index(bm, groups_array[fg_sta + j]);
285
286                         if (is_calc == false) {
287                                 is_calc = BMO_face_flag_test_bool(bm, faces_grp[j], FACE_FLAG);
288                         }
289                 }
290
291                 if (is_calc) {
292                         bmo_recalc_face_normals_array(bm, faces_grp, fg_len, FACE_FLAG);
293                 }
294         }
295
296         MEM_freeN(faces_grp);
297
298         MEM_freeN(groups_array);
299         MEM_freeN(group_index);
300 }