minor changes
[blender.git] / source / blender / bmesh / operators / bmo_unsubdivide.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): Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/operators/bmo_unsubdivide.c
24  *  \ingroup bmesh
25  */
26
27 #include "MEM_guardedalloc.h"
28
29 #include "BLI_math.h"
30
31 #include "bmesh.h"
32
33 #include "intern/bmesh_operators_private.h" /* own include */
34
35
36 static int bm_vert_dissolve_fan_test(BMVert *v)
37 {
38         /* check if we should walk over these verts */
39         BMIter iter;
40         BMEdge *e;
41
42         unsigned int tot_edge = 0;
43         unsigned int tot_edge_boundary = 0;
44         unsigned int tot_edge_manifold = 0;
45         unsigned int tot_edge_wire     = 0;
46
47         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
48                 if (BM_edge_is_boundary(e)) {
49                         tot_edge_boundary++;
50                 }
51                 else if (BM_edge_is_manifold(e)) {
52                         tot_edge_manifold++;
53                 }
54                 else if (BM_edge_is_wire(e)) {
55                         tot_edge_wire++;
56                 }
57                 tot_edge++;
58         }
59
60         if ((tot_edge == 4) && (tot_edge_boundary == 0) && (tot_edge_manifold == 4)) {
61                 return TRUE;
62         }
63         else if ((tot_edge == 3) && (tot_edge_boundary == 0) && (tot_edge_manifold == 3)) {
64                 return TRUE;
65         }
66         else if ((tot_edge == 3) && (tot_edge_boundary == 2) && (tot_edge_manifold == 1)) {
67                 return TRUE;
68         }
69         else if ((tot_edge == 2) && (tot_edge_wire == 2)) {
70                 return TRUE;
71         }
72         return FALSE;
73 }
74
75 static int bm_vert_dissolve_fan(BMesh *bm, BMVert *v)
76 {
77         /* collapse under 2 conditions.
78          * - vert connects to 4 manifold edges (and 4 faces).
79          * - vert connecrs to 1 manifold edge, 2 boundary edges (and 2 faces).
80          *
81          * This covers boundary verts of a quad grid and center verts.
82          * note that surrounding faces dont have to be quads.
83          */
84
85         BMIter iter;
86         BMEdge *e;
87
88         unsigned int tot_loop = 0;
89         unsigned int tot_edge = 0;
90         unsigned int tot_edge_boundary = 0;
91         unsigned int tot_edge_manifold = 0;
92         unsigned int tot_edge_wire     = 0;
93
94         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
95                 if (BM_edge_is_boundary(e)) {
96                         tot_edge_boundary++;
97                 }
98                 else if (BM_edge_is_manifold(e)) {
99                         tot_edge_manifold++;
100                 }
101                 else if (BM_edge_is_wire(e)) {
102                         tot_edge_wire++;
103                 }
104                 tot_edge++;
105         }
106
107         if (tot_edge == 2) {
108                 /* check for 2 wire verts only */
109                 if (tot_edge_wire == 2) {
110                         return (BM_vert_collapse_edge(bm, v->e, v, TRUE) != NULL);
111                 }
112         }
113         else if (tot_edge == 4) {
114                 /* check for 4 faces surrounding */
115                 if (tot_edge_boundary == 0 && tot_edge_manifold == 4) {
116                         /* good to go! */
117                         tot_loop = 4;
118                 }
119         }
120         else if (tot_edge == 3) {
121                 /* check for 2 faces surrounding at a boundary */
122                 if (tot_edge_boundary == 2 && tot_edge_manifold == 1) {
123                         /* good to go! */
124                         tot_loop = 2;
125                 }
126                 else if (tot_edge_boundary == 0 && tot_edge_manifold == 3) {
127                         /* good to go! */
128                         tot_loop = 3;
129                 }
130         }
131
132         if (tot_loop) {
133                 BMLoop *f_loop[4];
134                 unsigned int i;
135
136                 /* ensure there are exactly tot_loop loops */
137                 BLI_assert(BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v, tot_loop) == NULL);
138                 BM_iter_as_array(bm, BM_LOOPS_OF_VERT, v, (void **)f_loop, tot_loop);
139
140                 for (i = 0; i < tot_loop; i++) {
141                         BMLoop *l = f_loop[i];
142                         if (l->f->len > 3) {
143                                 BLI_assert(l->prev->v != l->next->v);
144                                 BM_face_split(bm, l->f, l->prev->v, l->next->v, NULL, NULL, TRUE);
145                         }
146                 }
147
148                 return BM_vert_dissolve(bm, v);
149         }
150
151         return FALSE;
152 }
153
154 enum {
155         VERT_INDEX_DO_COLLAPSE  = -1,
156         VERT_INDEX_INIT         =  0,
157         VERT_INDEX_IGNORE       =  1
158 };
159
160 // #define USE_WALKER  /* gives uneven results, disable for now */
161 // #define USE_ALL_VERTS
162
163 /* - BMVert.flag & BM_ELEM_TAG:  shows we touched this vert
164  * - BMVert.index == -1:         shows we will remove this vert
165  */
166 void bmo_unsubdivide_exec(BMesh *bm, BMOperator *op)
167 {
168 #ifdef USE_WALKER
169 #  define ELE_VERT_TAG 1
170 #else
171         BMVert **vert_seek_a = MEM_mallocN(sizeof(BMVert *) * bm->totvert, __func__);
172         BMVert **vert_seek_b = MEM_mallocN(sizeof(BMVert *) * bm->totvert, __func__);
173         unsigned vert_seek_a_tot = 0;
174         unsigned vert_seek_b_tot = 0;
175 #endif
176
177         BMVert *v;
178         BMIter iter;
179
180         const unsigned int offset = 0;
181         const unsigned int nth = 2;
182
183         const int iterations = maxi(1, BMO_slot_int_get(op, "iterations"));
184         int iter_step;
185
186 #ifdef USE_ALL_VERTS
187         (void)op;
188         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
189                 BM_elem_flag_enable(v, BM_ELEM_TAG);
190         }
191 #else  /* USE_ALL_VERTS */
192         BMOpSlot *vinput = BMO_slot_get(op, "verts");
193         BMVert **vinput_arr = (BMVert **)vinput->data.p;
194         int v_index;
195
196         /* tag verts */
197         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
198                 BM_elem_flag_disable(v, BM_ELEM_TAG);
199         }
200         for (v_index = 0; v_index < vinput->len; v_index++) {
201                 v = vinput_arr[v_index];
202                 BM_elem_flag_enable(v, BM_ELEM_TAG);
203         }
204 #endif  /* USE_ALL_VERTS */
205
206
207         for (iter_step = 0; iter_step < iterations; iter_step++) {
208                 int iter_done;
209
210                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
211                         if (BM_elem_flag_test(v, BM_ELEM_TAG) && bm_vert_dissolve_fan_test(v)) {
212 #ifdef USE_WALKER
213                                 BMO_elem_flag_enable(bm, v, ELE_VERT_TAG);
214 #endif
215                                 BM_elem_index_set(v, VERT_INDEX_INIT);  /* set_dirty! */
216                         }
217                         else {
218                                 BM_elem_index_set(v, VERT_INDEX_IGNORE);  /* set_dirty! */
219                         }
220                 }
221                 /* done with selecting tagged verts */
222
223
224                 /* main loop, keep tagging until we can't tag any more islands */
225                 while (TRUE) {
226 #ifdef USE_WALKER
227                         BMWalker walker;
228 #else
229                         unsigned int depth = 1;
230                         unsigned int i;
231 #endif
232                         BMVert *v_first = NULL;
233                         BMVert *v;
234
235                         /* we could avoid iterating from the start each time */
236                         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
237                                 if (v->e && (BM_elem_index_get(v) == VERT_INDEX_INIT)) {
238 #ifdef USE_WALKER
239                                         if (BMO_elem_flag_test(bm, v, ELE_VERT_TAG))
240 #endif
241                                         {
242                                                 /* check again incase the topology changed */
243                                                 if (bm_vert_dissolve_fan_test(v)) {
244                                                         v_first = v;
245                                                 }
246                                                 break;
247                                         }
248                                 }
249                         }
250                         if (v_first == NULL) {
251                                 break;
252                         }
253
254 #ifdef USE_WALKER
255                         /* Walk over selected elements starting at active */
256                         BMW_init(&walker, bm, BMW_CONNECTED_VERTEX,
257                                          ELE_VERT_TAG, BMW_MASK_NOP, BMW_MASK_NOP,
258                                          BMW_FLAG_NOP, /* don't use BMW_FLAG_TEST_HIDDEN here since we want to desel all */
259                                          BMW_NIL_LAY);
260
261                         BLI_assert(walker.order == BMW_BREADTH_FIRST);
262                         for (v = BMW_begin(&walker, v_first); v != NULL; v = BMW_step(&walker)) {
263                                 /* Deselect elements that aren't at "nth" depth from active */
264                                 if (BM_elem_index_get(v) == VERT_INDEX_INIT) {
265                                         if ((offset + BMW_current_depth(&walker)) % nth) {
266                                                 /* tag for removal */
267                                                 BM_elem_index_set(v, VERT_INDEX_DO_COLLAPSE);  /* set_dirty! */
268                                         }
269                                         else {
270                                                 /* works better to allow these verts to be checked again */
271                                                 //BM_elem_index_set(v, VERT_INDEX_IGNORE);  /* set_dirty! */
272                                         }
273                                 }
274                         }
275                         BMW_end(&walker);
276 #else
277
278                         BM_elem_index_set(v_first, (offset + depth) % nth ? VERT_INDEX_IGNORE : VERT_INDEX_DO_COLLAPSE);  /* set_dirty! */
279
280                         vert_seek_b_tot = 0;
281                         vert_seek_b[vert_seek_b_tot++] = v_first;
282
283                         while (TRUE) {
284                                 BMEdge *e;
285
286                                 if ((offset + depth) % nth) {
287                                         vert_seek_a_tot = 0;
288                                         for (i = 0; i < vert_seek_b_tot; i++) {
289                                                 v = vert_seek_b[i];
290                                                 BLI_assert(BM_elem_index_get(v) == VERT_INDEX_IGNORE);
291                                                 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
292                                                         BMVert *v_other = BM_edge_other_vert(e, v);
293                                                         if (BM_elem_index_get(v_other) == VERT_INDEX_INIT) {
294                                                                 BM_elem_index_set(v_other, VERT_INDEX_DO_COLLAPSE);  /* set_dirty! */
295                                                                 vert_seek_a[vert_seek_a_tot++] = v_other;
296                                                         }
297                                                 }
298                                         }
299                                         if (vert_seek_a_tot == 0) {
300                                                 break;
301                                         }
302                                 }
303                                 else {
304                                         vert_seek_b_tot = 0;
305                                         for (i = 0; i < vert_seek_a_tot; i++) {
306                                                 v = vert_seek_a[i];
307                                                 BLI_assert(BM_elem_index_get(v) == VERT_INDEX_DO_COLLAPSE);
308                                                 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
309                                                         BMVert *v_other = BM_edge_other_vert(e, v);
310                                                         if (BM_elem_index_get(v_other) == VERT_INDEX_INIT) {
311                                                                 BM_elem_index_set(v_other, VERT_INDEX_IGNORE);  /* set_dirty! */
312                                                                 vert_seek_b[vert_seek_b_tot++] = v_other;
313                                                         }
314                                                 }
315                                         }
316                                         if (vert_seek_b_tot == 0) {
317                                                 break;
318                                         }
319                                 }
320
321                                 depth++;
322                         }
323 #endif  /* USE_WALKER */
324
325                 }
326
327                 /* now we tagged all verts -1 for removal, lets loop over and rebuild faces */
328                 iter_done = FALSE;
329                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
330                         if (BM_elem_index_get(v) == VERT_INDEX_DO_COLLAPSE) {
331                                 iter_done |= bm_vert_dissolve_fan(bm, v);
332                         }
333                 }
334
335                 if (iter_done == FALSE) {
336                         break;
337                 }
338         }
339
340         bm->elem_index_dirty |= BM_VERT;
341
342 #ifndef USE_WALKER
343         MEM_freeN(vert_seek_a);
344         MEM_freeN(vert_seek_b);
345 #endif
346
347 }
348