Cycles / Sky Texture:
[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  * Given an array of faces, recalcualte their normals.
51  * this functions assumes all faces in the array are connected by edges.
52  *
53  * \param bm
54  * \param faces  Array of connected faces.
55  * \param faces_len  Length of \a faces
56  * \param oflag  Flag to check before doing the actual face flipping.
57  */
58 static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int faces_len, const short oflag)
59 {
60         float cent[3], tvec[3];
61         float (*faces_center)[3] = MEM_mallocN(sizeof(*faces_center) * faces_len, __func__);
62         const float cent_fac = 1.0f / (float)faces_len;
63         int i, f_start_index;
64         const short oflag_flip = oflag | FACE_FLIP;
65
66         float f_len_best;
67         BMFace *f;
68
69         BLI_LINKSTACK_DECLARE(fstack, BMFace *);
70
71         zero_v3(cent);
72
73         /* first calculate the center */
74         for (i = 0; i < faces_len; i++) {
75                 float *f_cent = faces_center[i];
76                 BM_face_calc_center_mean_weighted(faces[i], f_cent);
77                 madd_v3_v3fl(cent, f_cent, cent_fac);
78
79                 BLI_assert(BMO_elem_flag_test(bm, faces[i], FACE_TEMP) == 0);
80                 BLI_assert(BM_face_is_normal_valid(faces[i]));
81         }
82
83         f_len_best = -FLT_MAX;
84
85         for (i = 0; i < faces_len; i++) {
86                 float f_len_test;
87
88                 if ((f_len_test = len_squared_v3v3(faces_center[i], cent)) > f_len_best) {
89                         f_len_best = f_len_test;
90                         f_start_index = i;
91                 }
92         }
93
94         /* make sure the starting face has the correct winding */
95         sub_v3_v3v3(tvec, faces_center[f_start_index], cent);
96         if (dot_v3v3(tvec, faces[f_start_index]->no) < 0.0f) {
97                 BMO_elem_flag_enable(bm, faces[f_start_index], FACE_FLIP);
98         }
99
100         MEM_freeN(faces_center);
101
102         /* now that we've found our starting face, make all connected faces
103          * have the same winding.  this is done recursively, using a manual
104          * stack (if we use simple function recursion, we'd end up overloading
105          * the stack on large meshes). */
106         BLI_LINKSTACK_INIT(fstack);
107
108         BLI_LINKSTACK_PUSH(fstack, faces[f_start_index]);
109         BMO_elem_flag_enable(bm, faces[f_start_index], FACE_TEMP);
110
111         while ((f = BLI_LINKSTACK_POP(fstack))) {
112                 const bool flip_state = BMO_elem_flag_test_bool(bm, f, FACE_FLIP);
113                 BMLoop *l_iter, *l_first;
114
115                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
116                 do {
117                         BMLoop *l_other = l_iter->radial_next;
118
119                         if ((l_other != l_iter) && bmo_recalc_normal_edge_filter_cb((BMElem *)l_iter->e, NULL)) {
120                                 if (!BMO_elem_flag_test(bm, l_other->f, FACE_TEMP)) {
121                                         BMO_elem_flag_enable(bm, l_other->f, FACE_TEMP);
122                                         BMO_elem_flag_set(bm, l_other->f, FACE_FLIP, (l_other->v == l_iter->v) != flip_state);
123                                         BLI_LINKSTACK_PUSH(fstack, l_other->f);
124                                 }
125                         }
126                 } while ((l_iter = l_iter->next) != l_first);
127         }
128
129         BLI_LINKSTACK_FREE(fstack);
130
131         /* apply flipping to oflag'd faces */
132         for (i = 0; i < faces_len; i++) {
133                 if (BMO_elem_flag_test(bm, faces[i], oflag_flip) == oflag_flip) {
134                         BM_face_normal_flip(bm, faces[i]);
135                 }
136                 BMO_elem_flag_disable(bm, faces[i], FACE_TEMP);
137         }
138 }
139
140 /*
141  * put normal to the outside, and set the first direction flags in edges
142  *
143  * then check the object, and set directions / direction-flags: but only for edges with 1 or 2 faces
144  * this is in fact the 'select connected'
145  *
146  * in case all faces were not done: start over with 'find the ultimate ...' */
147
148 void bmo_recalc_face_normals_exec(BMesh *bm, BMOperator *op)
149 {
150         int *groups_array = MEM_mallocN(sizeof(*groups_array) * bm->totface, __func__);
151         int faces_len;
152         BMFace **faces_arr = BM_iter_as_arrayN(bm, BM_FACES_OF_MESH, NULL, &faces_len, NULL, 0);
153         BMFace **faces_grp = MEM_mallocN(sizeof(*faces_grp) * bm->totface, __func__);
154
155         int (*group_index)[2];
156         const int group_tot = BM_mesh_calc_face_groups(bm, groups_array, &group_index,
157                                                        bmo_recalc_normal_edge_filter_cb, NULL,
158                                                        0, BM_EDGE);
159         int i;
160
161
162         BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces", BM_FACE, FACE_FLAG);
163
164         for (i = 0; i < group_tot; i++) {
165                 const int fg_sta = group_index[i][0];
166                 const int fg_len = group_index[i][1];
167                 int j;
168                 bool is_calc = false;
169
170                 for (j = 0; j < fg_len; j++) {
171                         faces_grp[j] = faces_arr[groups_array[fg_sta + j]];
172
173                         if (is_calc == false) {
174                                 is_calc = BMO_elem_flag_test_bool(bm, faces_grp[j], FACE_FLAG);
175                         }
176                 }
177
178                 if (is_calc) {
179                         bmo_recalc_face_normals_array(bm, faces_grp, fg_len, FACE_FLAG);
180                 }
181         }
182
183
184         if (faces_arr) MEM_freeN(faces_arr);
185         MEM_freeN(faces_grp);
186
187         MEM_freeN(groups_array);
188         MEM_freeN(group_index);
189 }