Cleanup: indentation
[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_edge_filter_cb(BMElem *ele, void *UNUSED(user_data))
45 {
46         return BM_edge_is_manifold((BMEdge *)ele);
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, use the normals of the faces edges.
73  */
74 #define USE_FACE_EDGE_NORMAL_TEST
75
76 /**
77  * The center of the entire island is't necessarily well placed,
78  *
79  * This re-calculated a center relative to this face.
80  */
81 #ifdef USE_FACE_EDGE_NORMAL_TEST
82 #  define USE_FACE_LOCAL_CENTER_TEST
83 #endif
84
85 /**
86  * \return a face index in \a faces and set \a r_is_flip if the face is flipped away from the center.
87  */
88 static int recalc_face_normals_find_index(BMesh *bm, BMFace **faces, const int faces_len, bool *r_is_flip)
89 {
90         float cent_area_accum = 0.0f;
91         float f_len_best_sq;
92
93         float cent[3], tvec[3];
94         const float cent_fac = 1.0f / (float)faces_len;
95
96         float (*faces_center)[3] = MEM_mallocN(sizeof(*faces_center) * faces_len, __func__);
97         float *faces_area = MEM_mallocN(sizeof(*faces_area) * faces_len, __func__);
98         bool is_flip = false;
99         int f_start_index;
100         int i;
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 = faces_center[i];
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                 faces_area[i] = f_area;
114
115                 BLI_assert(BMO_elem_flag_test(bm, faces[i], FACE_TEMP) == 0);
116                 BLI_assert(BM_face_is_normal_valid(faces[i]));
117         }
118
119         if (cent_area_accum != 0.0f) {
120                 mul_v3_fl(cent, 1.0f / cent_area_accum);
121         }
122
123         f_len_best_sq = -FLT_MAX;
124         /* used in degenerate cases only */
125         f_start_index = 0;
126
127         for (i = 0; i < faces_len; i++) {
128                 float f_len_test_sq;
129
130                 if (faces_area[i] > FLT_EPSILON) {
131                         if ((f_len_test_sq = len_squared_v3v3(faces_center[i], cent)) > f_len_best_sq) {
132                                 f_len_best_sq = f_len_test_sq;
133                                 f_start_index = i;
134                         }
135                 }
136         }
137
138 #ifdef USE_FACE_EDGE_NORMAL_TEST
139         {
140                 BMFace *f_test = faces[f_start_index];
141                 BMLoop *l_iter, *l_first;
142                 float e_len_best_sq = -FLT_MAX;
143                 BMLoop *l_other_best = NULL;
144                 float no_edge[3];
145                 const float *no_best;
146
147                 l_iter = l_first = BM_FACE_FIRST_LOOP(f_test);
148                 do {
149                         if (BM_edge_is_manifold(l_iter->e) &&
150                             bmo_recalc_normal_edge_filter_cb((BMElem *)l_iter->e, NULL))
151                         {
152                                 BMLoop *l_other = l_iter->radial_next;
153
154                                 if (len_squared_v3v3(l_iter->v->co, l_iter->next->v->co) > FLT_EPSILON) {
155                                         float e_len_test_sq;
156                                         float e_cent[3];
157                                         mid_v3_v3v3(e_cent, l_iter->v->co, l_iter->next->v->co);
158                                         e_len_test_sq = len_squared_v3v3(cent, e_cent);
159                                         if (e_len_test_sq > e_len_best_sq) {
160                                                 l_other_best = l_other;
161                                                 e_len_best_sq = e_len_test_sq;
162                                         }
163                                 }
164                         }
165                 } while ((l_iter = l_iter->next) != l_first);
166
167                 /* furthest edge on furthest face */
168                 if (l_other_best) {
169                         float e_cent[3];
170
171 #ifdef USE_FACE_LOCAL_CENTER_TEST
172                         {
173                                 float f_cent_other[3];
174                                 BM_face_calc_center_mean_weighted(l_other_best->f, f_cent_other);
175                                 mid_v3_v3v3(cent, f_cent_other, faces_center[f_start_index]);
176                         }
177 #endif
178                         mid_v3_v3v3(e_cent, l_other_best->e->v1->co, l_other_best->e->v2->co);
179                         sub_v3_v3v3(tvec, e_cent, cent);
180
181                         madd_v3_v3v3fl(no_edge, f_test->no, l_other_best->f->no, BM_edge_is_contiguous(l_other_best->e) ? 1 : -1);
182                         no_best = no_edge;
183                 }
184                 else {
185                         sub_v3_v3v3(tvec, faces_center[f_start_index], cent);
186                         no_best = f_test->no;
187                 }
188
189                 is_flip = (dot_v3v3(tvec, no_best) < 0.0f);
190         }
191 #else
192         sub_v3_v3v3(tvec, faces_center[f_start_index], cent);
193         is_flip = (dot_v3v3(tvec, faces[f_start_index]->no) < 0.0f);
194 #endif
195
196         /* make sure the starting face has the correct winding */
197         MEM_freeN(faces_center);
198         MEM_freeN(faces_area);
199
200         *r_is_flip = is_flip;
201         return f_start_index;
202 }
203
204 /**
205  * Given an array of faces, recalculate their normals.
206  * this functions assumes all faces in the array are connected by edges.
207  *
208  * \param bm
209  * \param faces  Array of connected faces.
210  * \param faces_len  Length of \a faces
211  * \param oflag  Flag to check before doing the actual face flipping.
212  */
213 static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int faces_len, const short oflag)
214 {
215         int i, f_start_index;
216         const short oflag_flip = oflag | FACE_FLIP;
217         bool is_flip;
218
219         BMFace *f;
220
221         BLI_LINKSTACK_DECLARE(fstack, BMFace *);
222
223         f_start_index = recalc_face_normals_find_index(bm, faces, faces_len, &is_flip);
224
225         if (is_flip) {
226                 BMO_elem_flag_enable(bm, faces[f_start_index], FACE_FLIP);
227         }
228
229         /* now that we've found our starting face, make all connected faces
230          * have the same winding.  this is done recursively, using a manual
231          * stack (if we use simple function recursion, we'd end up overloading
232          * the stack on large meshes). */
233         BLI_LINKSTACK_INIT(fstack);
234
235         BLI_LINKSTACK_PUSH(fstack, faces[f_start_index]);
236         BMO_elem_flag_enable(bm, faces[f_start_index], FACE_TEMP);
237
238         while ((f = BLI_LINKSTACK_POP(fstack))) {
239                 const bool flip_state = BMO_elem_flag_test_bool(bm, f, FACE_FLIP);
240                 BMLoop *l_iter, *l_first;
241
242                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
243                 do {
244                         BMLoop *l_other = l_iter->radial_next;
245
246                         if ((l_other != l_iter) && bmo_recalc_normal_edge_filter_cb((BMElem *)l_iter->e, NULL)) {
247                                 if (!BMO_elem_flag_test(bm, l_other->f, FACE_TEMP)) {
248                                         BMO_elem_flag_enable(bm, l_other->f, FACE_TEMP);
249                                         BMO_elem_flag_set(bm, l_other->f, FACE_FLIP, (l_other->v == l_iter->v) != flip_state);
250                                         BLI_LINKSTACK_PUSH(fstack, l_other->f);
251                                 }
252                         }
253                 } while ((l_iter = l_iter->next) != l_first);
254         }
255
256         BLI_LINKSTACK_FREE(fstack);
257
258         /* apply flipping to oflag'd faces */
259         for (i = 0; i < faces_len; i++) {
260                 if (BMO_elem_flag_test(bm, faces[i], oflag_flip) == oflag_flip) {
261                         BM_face_normal_flip(bm, faces[i]);
262                 }
263                 BMO_elem_flag_disable(bm, faces[i], FACE_TEMP);
264         }
265 }
266
267 /*
268  * put normal to the outside, and set the first direction flags in edges
269  *
270  * then check the object, and set directions / direction-flags: but only for edges with 1 or 2 faces
271  * this is in fact the 'select connected'
272  *
273  * in case all faces were not done: start over with 'find the ultimate ...' */
274
275 void bmo_recalc_face_normals_exec(BMesh *bm, BMOperator *op)
276 {
277         int *groups_array = MEM_mallocN(sizeof(*groups_array) * bm->totface, __func__);
278         BMFace **faces_grp = MEM_mallocN(sizeof(*faces_grp) * bm->totface, __func__);
279
280         int (*group_index)[2];
281         const int group_tot = BM_mesh_calc_face_groups(bm, groups_array, &group_index,
282                                                        bmo_recalc_normal_edge_filter_cb, NULL,
283                                                        0, BM_EDGE);
284         int i;
285
286         BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces", BM_FACE, FACE_FLAG);
287
288         BM_mesh_elem_table_ensure(bm, BM_FACE);
289
290         for (i = 0; i < group_tot; i++) {
291                 const int fg_sta = group_index[i][0];
292                 const int fg_len = group_index[i][1];
293                 int j;
294                 bool is_calc = false;
295
296                 for (j = 0; j < fg_len; j++) {
297                         faces_grp[j] = BM_face_at_index(bm, groups_array[fg_sta + j]);
298
299                         if (is_calc == false) {
300                                 is_calc = BMO_elem_flag_test_bool(bm, faces_grp[j], FACE_FLAG);
301                         }
302                 }
303
304                 if (is_calc) {
305                         bmo_recalc_face_normals_array(bm, faces_grp, fg_len, FACE_FLAG);
306                 }
307         }
308
309         MEM_freeN(faces_grp);
310
311         MEM_freeN(groups_array);
312         MEM_freeN(group_index);
313 }