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