Blender  V3.3
bmesh_decimate_unsubdivide.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
9 #include "MEM_guardedalloc.h"
10 
11 #include "BLI_math.h"
12 
13 #include "bmesh.h"
14 #include "bmesh_decimate.h" /* own include */
15 
17 {
18  /* check if we should walk over these verts */
19  BMIter iter;
20  BMEdge *e;
21 
22  BMVert *varr[4];
23 
24  uint tot_edge = 0;
25  uint tot_edge_boundary = 0;
26  uint tot_edge_manifold = 0;
27  uint tot_edge_wire = 0;
28 
29  BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
30  if (BM_edge_is_boundary(e)) {
31  tot_edge_boundary++;
32  }
33  else if (BM_edge_is_manifold(e)) {
34  tot_edge_manifold++;
35  }
36  else if (BM_edge_is_wire(e)) {
37  tot_edge_wire++;
38  }
39 
40  /* bail out early */
41  if (tot_edge == 4) {
42  return false;
43  }
44 
45  /* used to check overlapping faces */
46  varr[tot_edge] = BM_edge_other_vert(e, v);
47 
48  tot_edge++;
49  }
50 
51  if (((tot_edge == 4) && (tot_edge_boundary == 0) && (tot_edge_manifold == 4)) ||
52  ((tot_edge == 3) && (tot_edge_boundary == 0) && (tot_edge_manifold == 3)) ||
53  ((tot_edge == 3) && (tot_edge_boundary == 2) && (tot_edge_manifold == 1))) {
54  if (!BM_face_exists(varr, tot_edge)) {
55  return true;
56  }
57  }
58  else if ((tot_edge == 2) && (tot_edge_wire == 2)) {
59  return true;
60  }
61  return false;
62 }
63 
65 {
66  /* Collapse under 2 conditions:
67  * - vert connects to 4 manifold edges (and 4 faces).
68  * - vert connects to 1 manifold edge, 2 boundary edges (and 2 faces).
69  *
70  * This covers boundary verts of a quad grid and center verts.
71  * note that surrounding faces don't have to be quads.
72  */
73 
74  BMIter iter;
75  BMEdge *e;
76 
77  uint tot_loop = 0;
78  uint tot_edge = 0;
79  uint tot_edge_boundary = 0;
80  uint tot_edge_manifold = 0;
81  uint tot_edge_wire = 0;
82 
83  BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
84  if (BM_edge_is_boundary(e)) {
85  tot_edge_boundary++;
86  }
87  else if (BM_edge_is_manifold(e)) {
88  tot_edge_manifold++;
89  }
90  else if (BM_edge_is_wire(e)) {
91  tot_edge_wire++;
92  }
93  tot_edge++;
94  }
95 
96  if (tot_edge == 2) {
97  /* check for 2 wire verts only */
98  if (tot_edge_wire == 2) {
99  return (BM_vert_collapse_edge(bm, v->e, v, true, true, true) != NULL);
100  }
101  }
102  else if (tot_edge == 4) {
103  /* check for 4 faces surrounding */
104  if (tot_edge_boundary == 0 && tot_edge_manifold == 4) {
105  /* good to go! */
106  tot_loop = 4;
107  }
108  }
109  else if (tot_edge == 3) {
110  /* check for 2 faces surrounding at a boundary */
111  if (tot_edge_boundary == 2 && tot_edge_manifold == 1) {
112  /* good to go! */
113  tot_loop = 2;
114  }
115  else if (tot_edge_boundary == 0 && tot_edge_manifold == 3) {
116  /* good to go! */
117  tot_loop = 3;
118  }
119  }
120 
121  if (tot_loop) {
122  BMLoop *f_loop[4];
123  uint i;
124 
125  /* ensure there are exactly tot_loop loops */
127  BM_iter_as_array(bm, BM_LOOPS_OF_VERT, v, (void **)f_loop, tot_loop);
128 
129  for (i = 0; i < tot_loop; i++) {
130  BMLoop *l = f_loop[i];
131  if (l->f->len > 3) {
132  BMLoop *l_new;
133  BLI_assert(l->prev->v != l->next->v);
134  BM_face_split(bm, l->f, l->prev, l->next, &l_new, NULL, true);
135  BM_elem_flag_merge_into(l_new->e, l->e, l->prev->e);
136  }
137  }
138 
139  return BM_vert_dissolve(bm, v);
140  }
141 
142  return false;
143 }
144 
145 enum {
149 };
150 
151 // #define USE_WALKER /* gives uneven results, disable for now */
152 
153 /* - BMVert.flag & BM_ELEM_TAG: shows we touched this vert
154  * - BMVert.index == -1: shows we will remove this vert
155  */
156 
157 void BM_mesh_decimate_unsubdivide_ex(BMesh *bm, const int iterations, const bool tag_only)
158 {
159 #ifdef USE_WALKER
160 # define ELE_VERT_TAG 1
161 #else
162  BMVert **vert_seek_a = MEM_mallocN(sizeof(BMVert *) * bm->totvert, __func__);
163  BMVert **vert_seek_b = MEM_mallocN(sizeof(BMVert *) * bm->totvert, __func__);
164  uint vert_seek_a_tot = 0;
165  uint vert_seek_b_tot = 0;
166 #endif
167 
168  BMIter iter;
169 
170  const uint offset = 0;
171  const uint nth = 2;
172 
173  int iter_step;
174 
175  /* if tag_only is set, we assume the caller knows what verts to tag
176  * needed for the operator */
177  if (tag_only == false) {
178  BMVert *v;
179  BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
181  }
182  }
183 
184  for (iter_step = 0; iter_step < iterations; iter_step++) {
185  BMVert *v, *v_next;
186  bool iter_done;
187 
188  BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
190 #ifdef USE_WALKER
191  BMO_vert_flag_enable(bm, v, ELE_VERT_TAG);
192 #endif
193  BM_elem_index_set(v, VERT_INDEX_INIT); /* set_dirty! */
194  }
195  else {
196  BM_elem_index_set(v, VERT_INDEX_IGNORE); /* set_dirty! */
197  }
198  }
199  /* done with selecting tagged verts */
200 
201  /* main loop, keep tagging until we can't tag any more islands */
202  while (true) {
203 #ifdef USE_WALKER
204  BMWalker walker;
205 #else
206  uint depth = 1;
207  uint i;
208 #endif
209  BMVert *v_first = NULL;
210 
211  /* we could avoid iterating from the start each time */
212  BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
213  if (v->e && (BM_elem_index_get(v) == VERT_INDEX_INIT)) {
214 #ifdef USE_WALKER
215  if (BMO_vert_flag_test(bm, v, ELE_VERT_TAG))
216 #endif
217  {
218  /* Check again in case the topology changed. */
220  v_first = v;
221  }
222  break;
223  }
224  }
225  }
226  if (v_first == NULL) {
227  break;
228  }
229 
230 #ifdef USE_WALKER
231  /* Walk over selected elements starting at active */
232  BMW_init(&walker,
233  bm,
235  ELE_VERT_TAG,
236  BMW_MASK_NOP,
237  BMW_MASK_NOP,
238  BMW_FLAG_NOP, /* don't use BMW_FLAG_TEST_HIDDEN here since we want to desel all */
239  BMW_NIL_LAY);
240 
242  for (v = BMW_begin(&walker, v_first); v != NULL; v = BMW_step(&walker)) {
243  /* Deselect elements that aren't at "nth" depth from active */
245  if ((offset + BMW_current_depth(&walker)) % nth) {
246  /* tag for removal */
247  BM_elem_index_set(v, VERT_INDEX_DO_COLLAPSE); /* set_dirty! */
248  }
249  else {
250  /* works better to allow these verts to be checked again */
251  // BM_elem_index_set(v, VERT_INDEX_IGNORE); /* set_dirty! */
252  }
253  }
254  }
255  BMW_end(&walker);
256 #else
257 
258  BM_elem_index_set(v_first,
259  ((offset + depth) % nth) ? VERT_INDEX_IGNORE :
260  VERT_INDEX_DO_COLLAPSE); /* set_dirty! */
261 
262  vert_seek_b_tot = 0;
263  vert_seek_b[vert_seek_b_tot++] = v_first;
264 
265  while (true) {
266  BMEdge *e;
267 
268  if ((offset + depth) % nth) {
269  vert_seek_a_tot = 0;
270  for (i = 0; i < vert_seek_b_tot; i++) {
271  v = vert_seek_b[i];
273  BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
274  BMVert *v_other = BM_edge_other_vert(e, v);
275  if (BM_elem_index_get(v_other) == VERT_INDEX_INIT) {
276  BM_elem_index_set(v_other, VERT_INDEX_DO_COLLAPSE); /* set_dirty! */
277  vert_seek_a[vert_seek_a_tot++] = v_other;
278  }
279  }
280  }
281  if (vert_seek_a_tot == 0) {
282  break;
283  }
284  }
285  else {
286  vert_seek_b_tot = 0;
287  for (i = 0; i < vert_seek_a_tot; i++) {
288  v = vert_seek_a[i];
290  BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
291  BMVert *v_other = BM_edge_other_vert(e, v);
292  if (BM_elem_index_get(v_other) == VERT_INDEX_INIT) {
293  BM_elem_index_set(v_other, VERT_INDEX_IGNORE); /* set_dirty! */
294  vert_seek_b[vert_seek_b_tot++] = v_other;
295  }
296  }
297  }
298  if (vert_seek_b_tot == 0) {
299  break;
300  }
301  }
302 
303  depth++;
304  }
305 #endif /* USE_WALKER */
306  }
307 
308  /* now we tagged all verts -1 for removal, lets loop over and rebuild faces */
309  iter_done = false;
310  BM_ITER_MESH_MUTABLE (v, v_next, &iter, bm, BM_VERTS_OF_MESH) {
312  if (bm_vert_dissolve_fan(bm, v)) {
313  iter_done = true;
314  }
315  }
316  }
317 
318  if (iter_done == false) {
319  break;
320  }
321  }
322 
324 
325 #ifndef USE_WALKER
326  MEM_freeN(vert_seek_a);
327  MEM_freeN(vert_seek_b);
328 #endif
329 }
330 
331 void BM_mesh_decimate_unsubdivide(BMesh *bm, const int iterations)
332 {
333  BM_mesh_decimate_unsubdivide_ex(bm, iterations, false);
334 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
unsigned int uint
Definition: BLI_sys_types.h:67
Read Guarded memory(de)allocation.
@ BM_VERT
Definition: bmesh_class.h:383
@ BM_ELEM_TAG
Definition: bmesh_class.h:484
static bool bm_vert_dissolve_fan_test(BMVert *v)
@ VERT_INDEX_DO_COLLAPSE
static bool bm_vert_dissolve_fan(BMesh *bm, BMVert *v)
void BM_mesh_decimate_unsubdivide(BMesh *bm, const int iterations)
void BM_mesh_decimate_unsubdivide_ex(BMesh *bm, const int iterations, const bool tag_only)
#define BM_elem_index_get(ele)
Definition: bmesh_inline.h:110
#define BM_elem_flag_merge_into(ele, ele_a, ele_b)
Definition: bmesh_inline.h:21
#define BM_elem_index_set(ele, index)
Definition: bmesh_inline.h:111
#define BM_elem_flag_test(ele, hflag)
Definition: bmesh_inline.h:12
#define BM_elem_flag_enable(ele, hflag)
Definition: bmesh_inline.h:14
void * BM_iter_at_index(BMesh *bm, const char itype, void *data, int index)
int BM_iter_as_array(BMesh *bm, const char itype, void *data, void **array, const int len)
Iterator as Array.
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
@ BM_VERTS_OF_MESH
@ BM_LOOPS_OF_VERT
@ BM_EDGES_OF_VERT
#define BM_ITER_MESH_MUTABLE(ele, ele_next, iter, bm, itype)
ATTR_WARN_UNUSED_RESULT BMesh * bm
bool BM_vert_dissolve(BMesh *bm, BMVert *v)
Dissolve Vert.
Definition: bmesh_mods.c:20
BMEdge * BM_vert_collapse_edge(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool kill_degenerate_faces, const bool kill_duplicate_faces)
Vert Collapse Faces.
Definition: bmesh_mods.c:402
BMFace * BM_face_split(BMesh *bm, BMFace *f, BMLoop *l_a, BMLoop *l_b, BMLoop **r_l, BMEdge *example, const bool no_double)
Face Split.
Definition: bmesh_mods.c:179
#define BMO_vert_flag_enable(bm, e, oflag)
#define BMO_vert_flag_test(bm, e, oflag)
BMFace * BM_face_exists(BMVert **varr, int len)
Definition: bmesh_query.c:1612
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
void BMW_init(BMWalker *walker, BMesh *bm, int type, short mask_vert, short mask_edge, short mask_face, BMWFlag flag, int layer)
Init Walker.
Definition: bmesh_walkers.c:49
void BMW_end(BMWalker *walker)
End Walker.
int BMW_current_depth(BMWalker *walker)
Walker Current Depth.
void * BMW_begin(BMWalker *walker, void *start)
Definition: bmesh_walkers.c:40
void * BMW_step(BMWalker *walker)
Step Walker.
@ BMW_BREADTH_FIRST
Definition: bmesh_walkers.h:15
#define BMW_NIL_LAY
@ BMW_FLAG_NOP
Definition: bmesh_walkers.h:19
#define BMW_MASK_NOP
Definition: bmesh_walkers.h:54
@ BMW_CONNECTED_VERTEX
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
int len
Definition: bmesh_class.h:267
struct BMVert * v
Definition: bmesh_class.h:153
struct BMEdge * e
Definition: bmesh_class.h:164
struct BMLoop * prev
Definition: bmesh_class.h:233
struct BMFace * f
Definition: bmesh_class.h:171
struct BMLoop * next
Definition: bmesh_class.h:233
struct BMEdge * e
Definition: bmesh_class.h:97
BMWOrder order
Definition: bmesh_walkers.h:30
int totvert
Definition: bmesh_class.h:297
char elem_index_dirty
Definition: bmesh_class.h:305