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