1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 */
16
17 /** \file
18 * \ingroup bmesh
19 *
20 * BMesh decimator that uses a grid un-subdivide method.
21 */
22
23 #include "MEM_guardedalloc.h"
24
25 #include "BLI_math.h"
26
27 #include "bmesh.h"
28 #include "bmesh_decimate.h" /* own include */
29
bm_vert_dissolve_fan_test(BMVert * v)30 static bool bm_vert_dissolve_fan_test(BMVert *v)
31 {
32 /* check if we should walk over these verts */
33 BMIter iter;
34 BMEdge *e;
35
36 BMVert *varr[4];
37
38 uint tot_edge = 0;
39 uint tot_edge_boundary = 0;
40 uint tot_edge_manifold = 0;
41 uint tot_edge_wire = 0;
42
43 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
44 if (BM_edge_is_boundary(e)) {
45 tot_edge_boundary++;
46 }
47 else if (BM_edge_is_manifold(e)) {
48 tot_edge_manifold++;
49 }
50 else if (BM_edge_is_wire(e)) {
51 tot_edge_wire++;
52 }
53
54 /* bail out early */
55 if (tot_edge == 4) {
56 return false;
57 }
58
59 /* used to check overlapping faces */
60 varr[tot_edge] = BM_edge_other_vert(e, v);
61
62 tot_edge++;
63 }
64
65 if (((tot_edge == 4) && (tot_edge_boundary == 0) && (tot_edge_manifold == 4)) ||
66 ((tot_edge == 3) && (tot_edge_boundary == 0) && (tot_edge_manifold == 3)) ||
67 ((tot_edge == 3) && (tot_edge_boundary == 2) && (tot_edge_manifold == 1))) {
68 if (!BM_face_exists(varr, tot_edge)) {
69 return true;
70 }
71 }
72 else if ((tot_edge == 2) && (tot_edge_wire == 2)) {
73 return true;
74 }
75 return false;
76 }
77
bm_vert_dissolve_fan(BMesh * bm,BMVert * v)78 static bool bm_vert_dissolve_fan(BMesh *bm, BMVert *v)
79 {
80 /* collapse under 2 conditions.
81 * - vert connects to 4 manifold edges (and 4 faces).
82 * - vert connects to 1 manifold edge, 2 boundary edges (and 2 faces).
83 *
84 * This covers boundary verts of a quad grid and center verts.
85 * note that surrounding faces dont have to be quads.
86 */
87
88 BMIter iter;
89 BMEdge *e;
90
91 uint tot_loop = 0;
92 uint tot_edge = 0;
93 uint tot_edge_boundary = 0;
94 uint tot_edge_manifold = 0;
95 uint tot_edge_wire = 0;
96
97 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
98 if (BM_edge_is_boundary(e)) {
99 tot_edge_boundary++;
100 }
101 else if (BM_edge_is_manifold(e)) {
102 tot_edge_manifold++;
103 }
104 else if (BM_edge_is_wire(e)) {
105 tot_edge_wire++;
106 }
107 tot_edge++;
108 }
109
110 if (tot_edge == 2) {
111 /* check for 2 wire verts only */
112 if (tot_edge_wire == 2) {
113 return (BM_vert_collapse_edge(bm, v->e, v, true, true) != NULL);
114 }
115 }
116 else if (tot_edge == 4) {
117 /* check for 4 faces surrounding */
118 if (tot_edge_boundary == 0 && tot_edge_manifold == 4) {
119 /* good to go! */
120 tot_loop = 4;
121 }
122 }
123 else if (tot_edge == 3) {
124 /* check for 2 faces surrounding at a boundary */
125 if (tot_edge_boundary == 2 && tot_edge_manifold == 1) {
126 /* good to go! */
127 tot_loop = 2;
128 }
129 else if (tot_edge_boundary == 0 && tot_edge_manifold == 3) {
130 /* good to go! */
131 tot_loop = 3;
132 }
133 }
134
135 if (tot_loop) {
136 BMLoop *f_loop[4];
137 uint i;
138
139 /* ensure there are exactly tot_loop loops */
140 BLI_assert(BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v, tot_loop) == NULL);
141 BM_iter_as_array(bm, BM_LOOPS_OF_VERT, v, (void **)f_loop, tot_loop);
142
143 for (i = 0; i < tot_loop; i++) {
144 BMLoop *l = f_loop[i];
145 if (l->f->len > 3) {
146 BMLoop *l_new;
147 BLI_assert(l->prev->v != l->next->v);
148 BM_face_split(bm, l->f, l->prev, l->next, &l_new, NULL, true);
149 BM_elem_flag_merge_into(l_new->e, l->e, l->prev->e);
150 }
151 }
152
153 return BM_vert_dissolve(bm, v);
154 }
155
156 return false;
157 }
158
159 enum {
160 VERT_INDEX_DO_COLLAPSE = -1,
161 VERT_INDEX_INIT = 0,
162 VERT_INDEX_IGNORE = 1,
163 };
164
165 // #define USE_WALKER /* gives uneven results, disable for now */
166
167 /* - BMVert.flag & BM_ELEM_TAG: shows we touched this vert
168 * - BMVert.index == -1: shows we will remove this vert
169 */
170
171 /**
172 * \param tag_only: so we can call this from an operator */
BM_mesh_decimate_unsubdivide_ex(BMesh * bm,const int iterations,const bool tag_only)173 void BM_mesh_decimate_unsubdivide_ex(BMesh *bm, const int iterations, const bool tag_only)
174 {
175 #ifdef USE_WALKER
176 # define ELE_VERT_TAG 1
177 #else
178 BMVert **vert_seek_a = MEM_mallocN(sizeof(BMVert *) * bm->totvert, __func__);
179 BMVert **vert_seek_b = MEM_mallocN(sizeof(BMVert *) * bm->totvert, __func__);
180 uint vert_seek_a_tot = 0;
181 uint vert_seek_b_tot = 0;
182 #endif
183
184 BMIter iter;
185
186 const uint offset = 0;
187 const uint nth = 2;
188
189 int iter_step;
190
191 /* if tag_only is set, we assume the caller knows what verts to tag
192 * needed for the operator */
193 if (tag_only == false) {
194 BMVert *v;
195 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
196 BM_elem_flag_enable(v, BM_ELEM_TAG);
197 }
198 }
199
200 for (iter_step = 0; iter_step < iterations; iter_step++) {
201 BMVert *v, *v_next;
202 bool iter_done;
203
204 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
205 if (BM_elem_flag_test(v, BM_ELEM_TAG) && bm_vert_dissolve_fan_test(v)) {
206 #ifdef USE_WALKER
207 BMO_vert_flag_enable(bm, v, ELE_VERT_TAG);
208 #endif
209 BM_elem_index_set(v, VERT_INDEX_INIT); /* set_dirty! */
210 }
211 else {
212 BM_elem_index_set(v, VERT_INDEX_IGNORE); /* set_dirty! */
213 }
214 }
215 /* done with selecting tagged verts */
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 uint depth = 1;
223 uint 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_vert_flag_test(bm, v, ELE_VERT_TAG))
232 #endif
233 {
234 /* Check again in case 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,
249 bm,
250 BMW_CONNECTED_VERTEX,
251 ELE_VERT_TAG,
252 BMW_MASK_NOP,
253 BMW_MASK_NOP,
254 BMW_FLAG_NOP, /* don't use BMW_FLAG_TEST_HIDDEN here since we want to desel all */
255 BMW_NIL_LAY);
256
257 BLI_assert(walker.order == BMW_BREADTH_FIRST);
258 for (v = BMW_begin(&walker, v_first); v != NULL; v = BMW_step(&walker)) {
259 /* Deselect elements that aren't at "nth" depth from active */
260 if (BM_elem_index_get(v) == VERT_INDEX_INIT) {
261 if ((offset + BMW_current_depth(&walker)) % nth) {
262 /* tag for removal */
263 BM_elem_index_set(v, VERT_INDEX_DO_COLLAPSE); /* set_dirty! */
264 }
265 else {
266 /* works better to allow these verts to be checked again */
267 // BM_elem_index_set(v, VERT_INDEX_IGNORE); /* set_dirty! */
268 }
269 }
270 }
271 BMW_end(&walker);
272 #else
273
274 BM_elem_index_set(v_first,
275 ((offset + depth) % nth) ? VERT_INDEX_IGNORE :
276 VERT_INDEX_DO_COLLAPSE); /* set_dirty! */
277
278 vert_seek_b_tot = 0;
279 vert_seek_b[vert_seek_b_tot++] = v_first;
280
281 while (true) {
282 BMEdge *e;
283
284 if ((offset + depth) % nth) {
285 vert_seek_a_tot = 0;
286 for (i = 0; i < vert_seek_b_tot; i++) {
287 v = vert_seek_b[i];
288 BLI_assert(BM_elem_index_get(v) == VERT_INDEX_IGNORE);
289 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
290 BMVert *v_other = BM_edge_other_vert(e, v);
291 if (BM_elem_index_get(v_other) == VERT_INDEX_INIT) {
292 BM_elem_index_set(v_other, VERT_INDEX_DO_COLLAPSE); /* set_dirty! */
293 vert_seek_a[vert_seek_a_tot++] = v_other;
294 }
295 }
296 }
297 if (vert_seek_a_tot == 0) {
298 break;
299 }
300 }
301 else {
302 vert_seek_b_tot = 0;
303 for (i = 0; i < vert_seek_a_tot; i++) {
304 v = vert_seek_a[i];
305 BLI_assert(BM_elem_index_get(v) == VERT_INDEX_DO_COLLAPSE);
306 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
307 BMVert *v_other = BM_edge_other_vert(e, v);
308 if (BM_elem_index_get(v_other) == VERT_INDEX_INIT) {
309 BM_elem_index_set(v_other, VERT_INDEX_IGNORE); /* set_dirty! */
310 vert_seek_b[vert_seek_b_tot++] = v_other;
311 }
312 }
313 }
314 if (vert_seek_b_tot == 0) {
315 break;
316 }
317 }
318
319 depth++;
320 }
321 #endif /* USE_WALKER */
322 }
323
324 /* now we tagged all verts -1 for removal, lets loop over and rebuild faces */
325 iter_done = false;
326 BM_ITER_MESH_MUTABLE (v, v_next, &iter, bm, BM_VERTS_OF_MESH) {
327 if (BM_elem_index_get(v) == VERT_INDEX_DO_COLLAPSE) {
328 if (bm_vert_dissolve_fan(bm, v)) {
329 iter_done = true;
330 }
331 }
332 }
333
334 if (iter_done == false) {
335 break;
336 }
337 }
338
339 bm->elem_index_dirty |= BM_VERT;
340
341 #ifndef USE_WALKER
342 MEM_freeN(vert_seek_a);
343 MEM_freeN(vert_seek_b);
344 #endif
345 }
346
BM_mesh_decimate_unsubdivide(BMesh * bm,const int iterations)347 void BM_mesh_decimate_unsubdivide(BMesh *bm, const int iterations)
348 {
349 BM_mesh_decimate_unsubdivide_ex(bm, iterations, false);
350 }
351