Blender  V3.3
bmesh_decimate_collapse.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
9 #include <stddef.h>
10 
11 #include "MEM_guardedalloc.h"
12 
13 #include "BLI_alloca.h"
14 #include "BLI_heap.h"
15 #include "BLI_linklist.h"
16 #include "BLI_math.h"
17 #include "BLI_memarena.h"
18 #include "BLI_polyfill_2d.h"
20 #include "BLI_quadric.h"
21 #include "BLI_utildefines_stack.h"
22 
23 #include "BKE_customdata.h"
24 
25 #include "bmesh.h"
26 #include "bmesh_decimate.h" /* own include */
27 
28 #include "../intern/bmesh_structure.h"
29 
30 #define USE_SYMMETRY
31 #ifdef USE_SYMMETRY
32 # include "BLI_kdtree.h"
33 #endif
34 
35 /* defines for testing */
36 #define USE_CUSTOMDATA
37 #define USE_TRIANGULATE
39 #define USE_VERT_NORMAL_INTERP
40 
42 #define USE_TOPOLOGY_FALLBACK
43 #ifdef USE_TOPOLOGY_FALLBACK
45 # define TOPOLOGY_FALLBACK_EPS 1e-12f
46 #endif
47 
48 #define BOUNDARY_PRESERVE_WEIGHT 100.0f
53 #define OPTIMIZE_EPS 1e-8
54 #define COST_INVALID FLT_MAX
55 
56 typedef enum CD_UseFlag {
57  CD_DO_VERT = (1 << 0),
58  CD_DO_EDGE = (1 << 1),
59  CD_DO_LOOP = (1 << 2),
61 
62 /* BMesh Helper Functions
63  * ********************** */
64 
68 static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics)
69 {
70  BMIter iter;
71  BMFace *f;
72  BMEdge *e;
73 
74  BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
75  BMLoop *l_first;
76  BMLoop *l_iter;
77 
78  float center[3];
79  double plane_db[4];
80  Quadric q;
81 
83  copy_v3db_v3fl(plane_db, f->no);
84  plane_db[3] = -dot_v3db_v3fl(plane_db, center);
85 
86  BLI_quadric_from_plane(&q, plane_db);
87 
88  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
89  do {
90  BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(l_iter->v)], &q);
91  } while ((l_iter = l_iter->next) != l_first);
92  }
93 
94  /* boundary edges */
95  BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
97  float edge_vector[3];
98  float edge_plane[3];
99  double edge_plane_db[4];
100  sub_v3_v3v3(edge_vector, e->v2->co, e->v1->co);
101  f = e->l->f;
102 
103  cross_v3_v3v3(edge_plane, edge_vector, f->no);
104  copy_v3db_v3fl(edge_plane_db, edge_plane);
105 
106  if (normalize_v3_db(edge_plane_db) > (double)FLT_EPSILON) {
107  Quadric q;
108  float center[3];
109 
110  mid_v3_v3v3(center, e->v1->co, e->v2->co);
111 
112  edge_plane_db[3] = -dot_v3db_v3fl(edge_plane_db, center);
113  BLI_quadric_from_plane(&q, edge_plane_db);
115 
116  BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(e->v1)], &q);
117  BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(e->v2)], &q);
118  }
119  }
120  }
121 }
122 
123 static void bm_decim_calc_target_co_db(BMEdge *e, double optimize_co[3], const Quadric *vquadrics)
124 {
125  /* compute an edge contraction target for edge 'e'
126  * this is computed by summing its vertices quadrics and
127  * optimizing the result. */
128  Quadric q;
129 
131  &q, &vquadrics[BM_elem_index_get(e->v1)], &vquadrics[BM_elem_index_get(e->v2)]);
132 
133  if (BLI_quadric_optimize(&q, optimize_co, OPTIMIZE_EPS)) {
134  /* all is good */
135  return;
136  }
137 
138  optimize_co[0] = 0.5 * ((double)e->v1->co[0] + (double)e->v2->co[0]);
139  optimize_co[1] = 0.5 * ((double)e->v1->co[1] + (double)e->v2->co[1]);
140  optimize_co[2] = 0.5 * ((double)e->v1->co[2] + (double)e->v2->co[2]);
141 }
142 
143 static void bm_decim_calc_target_co_fl(BMEdge *e, float optimize_co[3], const Quadric *vquadrics)
144 {
145  double optimize_co_db[3];
146  bm_decim_calc_target_co_db(e, optimize_co_db, vquadrics);
147  copy_v3fl_v3db(optimize_co, optimize_co_db);
148 }
149 
150 static bool bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_co[3])
151 {
152  BMIter liter;
153  BMLoop *l;
154  uint i;
155 
156  for (i = 0; i < 2; i++) {
157  /* loop over both verts */
158  BMVert *v = *((&e->v1) + i);
159 
160  BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
161  if (l->e != e && l->prev->e != e) {
162  const float *co_prev = l->prev->v->co;
163  const float *co_next = l->next->v->co;
164  float cross_exist[3];
165  float cross_optim[3];
166 
167 #if 1
168  /* line between the two outer verts, re-use for both cross products */
169  float vec_other[3];
170  /* before collapse */
171  float vec_exist[3];
172  /* after collapse */
173  float vec_optim[3];
174 
175  sub_v3_v3v3(vec_other, co_prev, co_next);
176  sub_v3_v3v3(vec_exist, co_prev, v->co);
177  sub_v3_v3v3(vec_optim, co_prev, optimize_co);
178 
179  cross_v3_v3v3(cross_exist, vec_other, vec_exist);
180  cross_v3_v3v3(cross_optim, vec_other, vec_optim);
181 
182  /* avoid normalize */
183  if (dot_v3v3(cross_exist, cross_optim) <=
184  (len_squared_v3(cross_exist) + len_squared_v3(cross_optim)) * 0.01f) {
185  return true;
186  }
187 #else
188  normal_tri_v3(cross_exist, v->co, co_prev, co_next);
189  normal_tri_v3(cross_optim, optimize_co, co_prev, co_next);
190 
191  /* use a small value rather than zero so we don't flip a face in multiple steps
192  * (first making it zero area, then flipping again) */
193  if (dot_v3v3(cross_exist, cross_optim) <= FLT_EPSILON) {
194  // printf("no flip\n");
195  return true;
196  }
197 #endif
198  }
199  }
200  }
201 
202  return false;
203 }
204 
205 #ifdef USE_TOPOLOGY_FALLBACK
213 {
214  return fabsf(dot_v3v3(e->v1->no, e->v2->no)) /
215  min_ff(-len_squared_v3v3(e->v1->co, e->v2->co), -FLT_EPSILON);
216 }
218 {
219  return fabsf(dot_v3v3(e->v1->no, e->v2->no)) /
220  min_ff(-len_v3v3(e->v1->co, e->v2->co), -FLT_EPSILON);
221 }
222 
223 #endif /* USE_TOPOLOGY_FALLBACK */
224 
226  const Quadric *vquadrics,
227  const float *vweights,
228  const float vweight_factor,
229  Heap *eheap,
230  HeapNode **eheap_table)
231 {
232  float cost;
233 
234  if (UNLIKELY(vweights && ((vweights[BM_elem_index_get(e->v1)] == 0.0f) ||
235  (vweights[BM_elem_index_get(e->v2)] == 0.0f)))) {
236  goto clear;
237  }
238 
239  /* check we can collapse, some edges we better not touch */
240  if (BM_edge_is_boundary(e)) {
241  if (e->l->f->len == 3) {
242  /* pass */
243  }
244  else {
245  /* only collapse tri's */
246  goto clear;
247  }
248  }
249  else if (BM_edge_is_manifold(e)) {
250  if ((e->l->f->len == 3) && (e->l->radial_next->f->len == 3)) {
251  /* pass */
252  }
253  else {
254  /* only collapse tri's */
255  goto clear;
256  }
257  }
258  else {
259  goto clear;
260  }
261  /* end sanity check */
262 
263  {
264  double optimize_co[3];
265  bm_decim_calc_target_co_db(e, optimize_co, vquadrics);
266 
267  const Quadric *q1, *q2;
268  q1 = &vquadrics[BM_elem_index_get(e->v1)];
269  q2 = &vquadrics[BM_elem_index_get(e->v2)];
270 
271  cost = (BLI_quadric_evaluate(q1, optimize_co) + BLI_quadric_evaluate(q2, optimize_co));
272  }
273 
274  /* NOTE: 'cost' shouldn't be negative but happens sometimes with small values.
275  * this can cause faces that make up a flat surface to over-collapse, see T37121. */
276  cost = fabsf(cost);
277 
278 #ifdef USE_TOPOLOGY_FALLBACK
279  if (UNLIKELY(cost < TOPOLOGY_FALLBACK_EPS)) {
280  /* subtract existing cost to further differentiate edges from one another
281  *
282  * keep topology cost below 0.0 so their values don't interfere with quadric cost,
283  * (and they get handled first). */
284  if (vweights == NULL) {
286  }
287  else {
288  /* with weights we need to use the real length so we can scale them properly */
289  const float e_weight = (vweights[BM_elem_index_get(e->v1)] +
290  vweights[BM_elem_index_get(e->v2)]);
292  /* NOTE: this is rather arbitrary max weight is 2 here,
293  * allow for skipping edges 4x the length, based on weights */
294  if (e_weight) {
295  cost *= 1.0f + (e_weight * vweight_factor);
296  }
297 
298  BLI_assert(cost <= 0.0f);
299  }
300  }
301  else
302 #endif
303  if (vweights) {
304  const float e_weight = 2.0f - (vweights[BM_elem_index_get(e->v1)] +
305  vweights[BM_elem_index_get(e->v2)]);
306  if (e_weight) {
307  cost += (BM_edge_calc_length(e) * ((e_weight * vweight_factor)));
308  }
309  }
310 
311  BLI_heap_insert_or_update(eheap, &eheap_table[BM_elem_index_get(e)], cost, e);
312  return;
313 
314 clear:
315  if (eheap_table[BM_elem_index_get(e)]) {
316  BLI_heap_remove(eheap, eheap_table[BM_elem_index_get(e)]);
317  }
318  eheap_table[BM_elem_index_get(e)] = NULL;
319 }
320 
321 /* use this for degenerate cases - add back to the heap with an invalid cost,
322  * this way it may be calculated again if surrounding geometry changes */
323 static void bm_decim_invalid_edge_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table)
324 {
325  BLI_assert(eheap_table[BM_elem_index_get(e)] == NULL);
326  eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, COST_INVALID, e);
327 }
328 
330  const Quadric *vquadrics,
331  const float *vweights,
332  const float vweight_factor,
333  Heap *eheap,
334  HeapNode **eheap_table)
335 {
336  BMIter iter;
337  BMEdge *e;
338  uint i;
339 
340  BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
341  /* keep sanity check happy */
342  eheap_table[i] = NULL;
343  bm_decim_build_edge_cost_single(e, vquadrics, vweights, vweight_factor, eheap, eheap_table);
344  }
345 }
346 
347 #ifdef USE_SYMMETRY
348 
350  /* pre-flipped coords */
351  float e_v1_co[3], e_v2_co[3];
352  /* Use to compare the correct endpoints in case v1/v2 are swapped. */
353  float e_dir[3];
354 
356 
357  /* same for all */
359  float limit_sq;
360 };
361 
363  int index,
364  const float UNUSED(co[3]),
365  float UNUSED(dist_sq))
366 {
367  struct KD_Symmetry_Data *sym_data = user_data;
368  BMEdge *e_other = sym_data->etable[index];
369  float e_other_dir[3];
370 
371  sub_v3_v3v3(e_other_dir, e_other->v2->co, e_other->v1->co);
372 
373  if (dot_v3v3(e_other_dir, sym_data->e_dir) > 0.0f) {
374  if ((len_squared_v3v3(sym_data->e_v1_co, e_other->v1->co) > sym_data->limit_sq) ||
375  (len_squared_v3v3(sym_data->e_v2_co, e_other->v2->co) > sym_data->limit_sq)) {
376  return true;
377  }
378  }
379  else {
380  if ((len_squared_v3v3(sym_data->e_v1_co, e_other->v2->co) > sym_data->limit_sq) ||
381  (len_squared_v3v3(sym_data->e_v2_co, e_other->v1->co) > sym_data->limit_sq)) {
382  return true;
383  }
384  }
385 
386  /* exit on first-hit, this is OK since the search range is very small */
387  sym_data->e_found_index = index;
388  return false;
389 }
390 
391 static int *bm_edge_symmetry_map(BMesh *bm, uint symmetry_axis, float limit)
392 {
393  struct KD_Symmetry_Data sym_data;
394  BMIter iter;
395  BMEdge *e, **etable;
396  uint i;
397  int *edge_symmetry_map;
398  const float limit_sq = square_f(limit);
399  KDTree_3d *tree;
400 
401  tree = BLI_kdtree_3d_new(bm->totedge);
402 
403  etable = MEM_mallocN(sizeof(*etable) * bm->totedge, __func__);
404  edge_symmetry_map = MEM_mallocN(sizeof(*edge_symmetry_map) * bm->totedge, __func__);
405 
406  BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
407  float co[3];
408  mid_v3_v3v3(co, e->v1->co, e->v2->co);
409  BLI_kdtree_3d_insert(tree, i, co);
410  etable[i] = e;
411  edge_symmetry_map[i] = -1;
412  }
413 
414  BLI_kdtree_3d_balance(tree);
415 
416  sym_data.etable = etable;
417  sym_data.limit_sq = limit_sq;
418 
419  BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
420  if (edge_symmetry_map[i] == -1) {
421  float co[3];
422  mid_v3_v3v3(co, e->v1->co, e->v2->co);
423  co[symmetry_axis] *= -1.0f;
424 
425  copy_v3_v3(sym_data.e_v1_co, e->v1->co);
426  copy_v3_v3(sym_data.e_v2_co, e->v2->co);
427  sym_data.e_v1_co[symmetry_axis] *= -1.0f;
428  sym_data.e_v2_co[symmetry_axis] *= -1.0f;
429  sub_v3_v3v3(sym_data.e_dir, sym_data.e_v2_co, sym_data.e_v1_co);
430  sym_data.e_found_index = -1;
431 
432  BLI_kdtree_3d_range_search_cb(tree, co, limit, bm_edge_symmetry_check_cb, &sym_data);
433 
434  if (sym_data.e_found_index != -1) {
435  const int i_other = sym_data.e_found_index;
436  edge_symmetry_map[i] = i_other;
437  edge_symmetry_map[i_other] = i;
438  }
439  }
440  }
441 
442  MEM_freeN(etable);
443  BLI_kdtree_3d_free(tree);
444 
445  return edge_symmetry_map;
446 }
447 #endif /* USE_SYMMETRY */
448 
449 #ifdef USE_TRIANGULATE
450 /* Temp Triangulation
451  * ****************** */
452 
466  BMFace *f_base,
467  LinkNode **r_faces_double,
468  int *r_edges_tri_tot,
469 
470  MemArena *pf_arena,
471  /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */
472  struct Heap *pf_heap)
473 {
474  const int f_base_len = f_base->len;
475  int faces_array_tot = f_base_len - 3;
476  int edges_array_tot = f_base_len - 3;
477  BMFace **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
478  BMEdge **edges_array = BLI_array_alloca(edges_array, edges_array_tot);
479  const int quad_method = 0, ngon_method = 0; /* beauty */
480 
481  bool has_cut = false;
482 
483  const int f_index = BM_elem_index_get(f_base);
484 
486  f_base,
487  faces_array,
488  &faces_array_tot,
489  edges_array,
490  &edges_array_tot,
491  r_faces_double,
492  quad_method,
493  ngon_method,
494  false,
495  pf_arena,
496  pf_heap);
497 
498  for (int i = 0; i < edges_array_tot; i++) {
499  BMLoop *l_iter, *l_first;
500  l_iter = l_first = edges_array[i]->l;
501  do {
502  BM_elem_index_set(l_iter, f_index); /* set_dirty */
503  has_cut = true;
504  } while ((l_iter = l_iter->radial_next) != l_first);
505  }
506 
507  for (int i = 0; i < faces_array_tot; i++) {
508  BM_face_normal_update(faces_array[i]);
509  }
510 
511  *r_edges_tri_tot += edges_array_tot;
512 
513  return has_cut;
514 }
515 
516 static bool bm_decim_triangulate_begin(BMesh *bm, int *r_edges_tri_tot)
517 {
518  BMIter iter;
519  BMFace *f;
520  bool has_ngon = false;
521  bool has_cut = false;
522 
524 
525  /* first clear loop index values */
526  BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
527  BMLoop *l_iter;
528  BMLoop *l_first;
529 
530  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
531  do {
532  BM_elem_index_set(l_iter, -1); /* set_dirty */
533  } while ((l_iter = l_iter->next) != l_first);
534 
535  has_ngon |= (f->len > 4);
536  }
537 
539 
540  {
541  MemArena *pf_arena;
542  Heap *pf_heap;
543 
544  LinkNode *faces_double = NULL;
545 
546  if (has_ngon) {
547  pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
549  }
550  else {
551  pf_arena = NULL;
552  pf_heap = NULL;
553  }
554 
555  /* Adding new faces as we loop over faces
556  * is normally best avoided, however in this case its not so bad because any face touched twice
557  * will already be triangulated. */
558  BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
559  if (f->len > 3) {
560  has_cut |= bm_face_triangulate(bm,
561  f,
562  &faces_double,
563  r_edges_tri_tot,
564 
565  pf_arena,
566  pf_heap);
567  }
568  }
569 
570  while (faces_double) {
571  LinkNode *next = faces_double->next;
572  BM_face_kill(bm, faces_double->link);
573  MEM_freeN(faces_double);
574  faces_double = next;
575  }
576 
577  if (has_ngon) {
578  BLI_memarena_free(pf_arena);
579  BLI_heap_free(pf_heap, NULL);
580  }
581 
583 
584  if (has_cut) {
585  /* now triangulation is done we need to correct index values */
587  }
588  }
589 
590  return has_cut;
591 }
592 
593 static void bm_decim_triangulate_end(BMesh *bm, const int edges_tri_tot)
594 {
595  /* decimation finished, now re-join */
596  BMIter iter;
597  BMEdge *e;
598 
599  /* we need to collect before merging for ngons since the loops indices will be lost */
600  BMEdge **edges_tri = MEM_mallocN(MIN2(edges_tri_tot, bm->totedge) * sizeof(*edges_tri),
601  __func__);
602  STACK_DECLARE(edges_tri);
603 
604  STACK_INIT(edges_tri, MIN2(edges_tri_tot, bm->totedge));
605 
606  /* boundary edges */
607  BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
608  BMLoop *l_a, *l_b;
609  if (BM_edge_loop_pair(e, &l_a, &l_b)) {
610  const int l_a_index = BM_elem_index_get(l_a);
611  if (l_a_index != -1) {
612  const int l_b_index = BM_elem_index_get(l_b);
613  if (l_a_index == l_b_index) {
614  if (l_a->v != l_b->v) { /* if this is the case, faces have become flipped */
615  /* check we are not making a degenerate quad */
616 
617 # define CAN_LOOP_MERGE(l) \
618  (BM_loop_is_manifold(l) && ((l)->v != (l)->radial_next->v) && \
619  (l_a_index == BM_elem_index_get(l)) && (l_a_index == BM_elem_index_get((l)->radial_next)))
620 
621  if ((l_a->f->len == 3 && l_b->f->len == 3) && (!CAN_LOOP_MERGE(l_a->next)) &&
622  (!CAN_LOOP_MERGE(l_a->prev)) && (!CAN_LOOP_MERGE(l_b->next)) &&
623  (!CAN_LOOP_MERGE(l_b->prev))) {
624  BMVert *vquad[4] = {
625  e->v1,
626  BM_vert_in_edge(e, l_a->next->v) ? l_a->prev->v : l_a->next->v,
627  e->v2,
628  BM_vert_in_edge(e, l_b->next->v) ? l_b->prev->v : l_b->next->v,
629  };
630 
631  BLI_assert(ELEM(vquad[0], vquad[1], vquad[2], vquad[3]) == false);
632  BLI_assert(ELEM(vquad[1], vquad[0], vquad[2], vquad[3]) == false);
633  BLI_assert(ELEM(vquad[2], vquad[1], vquad[0], vquad[3]) == false);
634  BLI_assert(ELEM(vquad[3], vquad[1], vquad[2], vquad[0]) == false);
635 
636  if (!is_quad_convex_v3(vquad[0]->co, vquad[1]->co, vquad[2]->co, vquad[3]->co)) {
637  continue;
638  }
639  }
640 # undef CAN_LOOP_MERGE
641 
642  /* highly unlikely to fail, but prevents possible double-ups */
643  STACK_PUSH(edges_tri, e);
644  }
645  }
646  }
647  }
648  }
649 
650  for (int i = 0; i < STACK_SIZE(edges_tri); i++) {
651  BMLoop *l_a, *l_b;
652  e = edges_tri[i];
653  if (BM_edge_loop_pair(e, &l_a, &l_b)) {
654  BMFace *f_array[2] = {l_a->f, l_b->f};
655  BM_faces_join(bm, f_array, 2, false);
656  if (e->l == NULL) {
657  BM_edge_kill(bm, e);
658  }
659  }
660  }
661  MEM_freeN(edges_tri);
662 }
663 
664 #endif /* USE_TRIANGULATE */
665 
666 /* Edge Collapse Functions
667  * *********************** */
668 
669 #ifdef USE_CUSTOMDATA
670 
675  BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other, const float customdata_fac)
676 {
677  /* Disable seam check - the seam check would have to be done per layer,
678  * its not really that important. */
679  //#define USE_SEAM
680  /* these don't need to be updated, since they will get removed when the edge collapses */
681  BMLoop *l_clear, *l_other;
682  const bool is_manifold = BM_edge_is_manifold(l->e);
683  int side;
684 
685  /* first find the loop of 'v_other' that's attached to the face of 'l' */
686  if (l->v == v_clear) {
687  l_clear = l;
688  l_other = l->next;
689  }
690  else {
691  l_clear = l->next;
692  l_other = l;
693  }
694 
695  BLI_assert(l_clear->v == v_clear);
696  BLI_assert(l_other->v == v_other);
697  /* quiet warnings for release */
698  (void)v_other;
699 
700  /* now we have both corners of the face 'l->f' */
701  for (side = 0; side < 2; side++) {
702 # ifdef USE_SEAM
703  bool is_seam = false;
704 # endif
705  void *src[2];
706  BMFace *f_exit = is_manifold ? l->radial_next->f : NULL;
707  BMEdge *e_prev = l->e;
708  BMLoop *l_first;
709  BMLoop *l_iter;
710  float w[2];
711 
712  if (side == 0) {
713  l_iter = l_first = l_clear;
714  src[0] = l_clear->head.data;
715  src[1] = l_other->head.data;
716 
717  w[0] = customdata_fac;
718  w[1] = 1.0f - customdata_fac;
719  }
720  else {
721  l_iter = l_first = l_other;
722  src[0] = l_other->head.data;
723  src[1] = l_clear->head.data;
724 
725  w[0] = 1.0f - customdata_fac;
726  w[1] = customdata_fac;
727  }
728 
729  // print_v2("weights", w);
730 
731  /* WATCH IT! - should NOT reference (_clear or _other) vars for this while loop */
732 
733  /* walk around the fan using 'e_prev' */
734  while (((l_iter = BM_vert_step_fan_loop(l_iter, &e_prev)) != l_first) && (l_iter != NULL)) {
735  int i;
736  /* quit once we hit the opposite face, if we have one */
737  if (f_exit && UNLIKELY(f_exit == l_iter->f)) {
738  break;
739  }
740 
741 # ifdef USE_SEAM
742  /* break out unless we find a match */
743  is_seam = true;
744 # endif
745 
746  /* ok. we have a loop. now be smart with it! */
747  for (i = 0; i < bm->ldata.totlayer; i++) {
748  if (CustomData_layer_has_math(&bm->ldata, i)) {
749  const int offset = bm->ldata.layers[i].offset;
750  const int type = bm->ldata.layers[i].type;
751  const void *cd_src[2] = {
754  };
755  void *cd_iter = POINTER_OFFSET(l_iter->head.data, offset);
756 
757  /* detect seams */
758  if (CustomData_data_equals(type, cd_src[0], cd_iter)) {
760  cd_src,
761  w,
762  NULL,
763  ARRAY_SIZE(cd_src),
764  POINTER_OFFSET(l_iter->head.data, offset),
765  i);
766 # ifdef USE_SEAM
767  is_seam = false;
768 # endif
769  }
770  }
771  }
772 
773 # ifdef USE_SEAM
774  if (is_seam) {
775  break;
776  }
777 # endif
778  }
779  }
780 
781  //#undef USE_SEAM
782 }
783 #endif /* USE_CUSTOMDATA */
784 
795 {
798  if (e->l) {
800  if (e->l != e->l->radial_next) {
801  BM_elem_flag_enable(e->l->radial_next->f, BM_ELEM_TAG);
802  }
803  }
804 }
805 
807 {
810  if (e->l) {
812  if (e->l != e->l->radial_next) {
813  BM_elem_flag_disable(e->l->radial_next->f, BM_ELEM_TAG);
814  }
815  }
816 }
817 
818 static bool bm_edge_tag_test(BMEdge *e)
819 {
820  /* is the edge or one of its faces tagged? */
822  (e->l &&
823  (BM_elem_flag_test(e->l->f, BM_ELEM_TAG) ||
824  (e->l != e->l->radial_next && BM_elem_flag_test(e->l->radial_next->f, BM_ELEM_TAG)))));
825 }
826 
827 /* takes the edges loop */
829 {
830 #if 0
831  /* less optimized version of check below */
832  return (BM_edge_is_manifold(l->e) || BM_edge_is_boundary(l->e);
833 #else
834  /* if the edge is a boundary it points to itself, else this must be a manifold */
835  return LIKELY(l) && LIKELY(l->radial_next->radial_next == l);
836 #endif
837 }
838 
840 {
841  /* simply check that there is no overlap between faces and edges of each vert,
842  * (excluding the 2 faces attached to 'e' and 'e' itself) */
843 
844  BMEdge *e_iter;
845 
846  /* clear flags on both disks */
847  e_iter = e_first;
848  do {
849  if (!bm_edge_is_manifold_or_boundary(e_iter->l)) {
850  return true;
851  }
852  bm_edge_tag_disable(e_iter);
853  } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v1)) != e_first);
854 
855  e_iter = e_first;
856  do {
857  if (!bm_edge_is_manifold_or_boundary(e_iter->l)) {
858  return true;
859  }
860  bm_edge_tag_disable(e_iter);
861  } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v2)) != e_first);
862 
863  /* now enable one side... */
864  e_iter = e_first;
865  do {
866  bm_edge_tag_enable(e_iter);
867  } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v1)) != e_first);
868 
869  /* ... except for the edge we will collapse, we know that's shared,
870  * disable this to avoid false positive. We could be smart and never enable these
871  * face/edge tags in the first place but easier to do this */
872  // bm_edge_tag_disable(e_first);
873  /* do inline... */
874  {
875 #if 0
876  BMIter iter;
877  BMIter liter;
878  BMLoop *l;
879  BMVert *v;
880  BM_ITER_ELEM (l, &liter, e_first, BM_LOOPS_OF_EDGE) {
882  BM_ITER_ELEM (v, &iter, l->f, BM_VERTS_OF_FACE) {
884  }
885  }
886 #else
887  /* we know each face is a triangle, no looping/iterators needed here */
888 
889  BMLoop *l_radial;
890  BMLoop *l_face;
891 
892  l_radial = e_first->l;
893  l_face = l_radial;
894  BLI_assert(l_face->f->len == 3);
896  BM_elem_flag_disable((l_face = l_radial)->v, BM_ELEM_TAG);
897  BM_elem_flag_disable((l_face = l_face->next)->v, BM_ELEM_TAG);
898  BM_elem_flag_disable((l_face->next)->v, BM_ELEM_TAG);
899  l_face = l_radial->radial_next;
900  if (l_radial != l_face) {
901  BLI_assert(l_face->f->len == 3);
903  BM_elem_flag_disable((l_face = l_radial->radial_next)->v, BM_ELEM_TAG);
904  BM_elem_flag_disable((l_face = l_face->next)->v, BM_ELEM_TAG);
905  BM_elem_flag_disable((l_face->next)->v, BM_ELEM_TAG);
906  }
907 #endif
908  }
909 
910  /* and check for overlap */
911  e_iter = e_first;
912  do {
913  if (bm_edge_tag_test(e_iter)) {
914  return true;
915  }
916  } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v2)) != e_first);
917 
918  return false;
919 }
920 
931 static bool bm_edge_collapse(BMesh *bm,
932  BMEdge *e_clear,
933  BMVert *v_clear,
934  int r_e_clear_other[2],
935 #ifdef USE_SYMMETRY
936  int *edge_symmetry_map,
937 #endif
938 #ifdef USE_CUSTOMDATA
939  const CD_UseFlag customdata_flag,
940  const float customdata_fac
941 #else
942  const CD_UseFlag UNUSED(customdata_flag),
943  const float UNUSED(customdata_fac)
944 #endif
945 )
946 {
947  BMVert *v_other;
948 
949  v_other = BM_edge_other_vert(e_clear, v_clear);
950  BLI_assert(v_other != NULL);
951 
952  if (BM_edge_is_manifold(e_clear)) {
953  BMLoop *l_a, *l_b;
954  BMEdge *e_a_other[2], *e_b_other[2];
955  bool ok;
956 
957  ok = BM_edge_loop_pair(e_clear, &l_a, &l_b);
958 
959  BLI_assert(ok == true);
960  BLI_assert(l_a->f->len == 3);
961  BLI_assert(l_b->f->len == 3);
962  UNUSED_VARS_NDEBUG(ok);
963 
964  /* keep 'v_clear' 0th */
965  if (BM_vert_in_edge(l_a->prev->e, v_clear)) {
966  e_a_other[0] = l_a->prev->e;
967  e_a_other[1] = l_a->next->e;
968  }
969  else {
970  e_a_other[1] = l_a->prev->e;
971  e_a_other[0] = l_a->next->e;
972  }
973 
974  if (BM_vert_in_edge(l_b->prev->e, v_clear)) {
975  e_b_other[0] = l_b->prev->e;
976  e_b_other[1] = l_b->next->e;
977  }
978  else {
979  e_b_other[1] = l_b->prev->e;
980  e_b_other[0] = l_b->next->e;
981  }
982 
983  /* we could assert this case, but better just bail out */
984 #if 0
985  BLI_assert(e_a_other[0] != e_b_other[0]);
986  BLI_assert(e_a_other[0] != e_b_other[1]);
987  BLI_assert(e_b_other[0] != e_a_other[0]);
988  BLI_assert(e_b_other[0] != e_a_other[1]);
989 #endif
990  /* not totally common but we want to avoid */
991  if (ELEM(e_a_other[0], e_b_other[0], e_b_other[1]) ||
992  ELEM(e_a_other[1], e_b_other[0], e_b_other[1])) {
993  return false;
994  }
995 
996  BLI_assert(BM_edge_share_vert(e_a_other[0], e_b_other[0]));
997  BLI_assert(BM_edge_share_vert(e_a_other[1], e_b_other[1]));
998 
999  r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
1000  r_e_clear_other[1] = BM_elem_index_get(e_b_other[0]);
1001 
1002 #ifdef USE_CUSTOMDATA
1003  /* before killing, do customdata */
1004  if (customdata_flag & CD_DO_VERT) {
1005  BM_data_interp_from_verts(bm, v_other, v_clear, v_other, customdata_fac);
1006  }
1007  if (customdata_flag & CD_DO_EDGE) {
1008  BM_data_interp_from_edges(bm, e_a_other[1], e_a_other[0], e_a_other[1], customdata_fac);
1009  BM_data_interp_from_edges(bm, e_b_other[1], e_b_other[0], e_b_other[1], customdata_fac);
1010  }
1011  if (customdata_flag & CD_DO_LOOP) {
1012  bm_edge_collapse_loop_customdata(bm, e_clear->l, v_clear, v_other, customdata_fac);
1014  bm, e_clear->l->radial_next, v_clear, v_other, customdata_fac);
1015  }
1016 #endif
1017 
1018  BM_edge_kill(bm, e_clear);
1019 
1020  v_other->head.hflag |= v_clear->head.hflag;
1021  BM_vert_splice(bm, v_other, v_clear);
1022 
1023  e_a_other[1]->head.hflag |= e_a_other[0]->head.hflag;
1024  e_b_other[1]->head.hflag |= e_b_other[0]->head.hflag;
1025  BM_edge_splice(bm, e_a_other[1], e_a_other[0]);
1026  BM_edge_splice(bm, e_b_other[1], e_b_other[0]);
1027 
1028 #ifdef USE_SYMMETRY
1029  /* update mirror map */
1030  if (edge_symmetry_map) {
1031  if (edge_symmetry_map[r_e_clear_other[0]] != -1) {
1032  edge_symmetry_map[edge_symmetry_map[r_e_clear_other[0]]] = BM_elem_index_get(e_a_other[1]);
1033  }
1034  if (edge_symmetry_map[r_e_clear_other[1]] != -1) {
1035  edge_symmetry_map[edge_symmetry_map[r_e_clear_other[1]]] = BM_elem_index_get(e_b_other[1]);
1036  }
1037  }
1038 #endif
1039 
1040  // BM_mesh_validate(bm);
1041 
1042  return true;
1043  }
1044  if (BM_edge_is_boundary(e_clear)) {
1045  /* same as above but only one triangle */
1046  BMLoop *l_a;
1047  BMEdge *e_a_other[2];
1048 
1049  l_a = e_clear->l;
1050 
1051  BLI_assert(l_a->f->len == 3);
1052 
1053  /* keep 'v_clear' 0th */
1054  if (BM_vert_in_edge(l_a->prev->e, v_clear)) {
1055  e_a_other[0] = l_a->prev->e;
1056  e_a_other[1] = l_a->next->e;
1057  }
1058  else {
1059  e_a_other[1] = l_a->prev->e;
1060  e_a_other[0] = l_a->next->e;
1061  }
1062 
1063  r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
1064  r_e_clear_other[1] = -1;
1065 
1066 #ifdef USE_CUSTOMDATA
1067  /* before killing, do customdata */
1068  if (customdata_flag & CD_DO_VERT) {
1069  BM_data_interp_from_verts(bm, v_other, v_clear, v_other, customdata_fac);
1070  }
1071  if (customdata_flag & CD_DO_EDGE) {
1072  BM_data_interp_from_edges(bm, e_a_other[1], e_a_other[0], e_a_other[1], customdata_fac);
1073  }
1074  if (customdata_flag & CD_DO_LOOP) {
1075  bm_edge_collapse_loop_customdata(bm, e_clear->l, v_clear, v_other, customdata_fac);
1076  }
1077 #endif
1078 
1079  BM_edge_kill(bm, e_clear);
1080 
1081  v_other->head.hflag |= v_clear->head.hflag;
1082  BM_vert_splice(bm, v_other, v_clear);
1083 
1084  e_a_other[1]->head.hflag |= e_a_other[0]->head.hflag;
1085  BM_edge_splice(bm, e_a_other[1], e_a_other[0]);
1086 
1087 #ifdef USE_SYMMETRY
1088  /* update mirror map */
1089  if (edge_symmetry_map) {
1090  if (edge_symmetry_map[r_e_clear_other[0]] != -1) {
1091  edge_symmetry_map[edge_symmetry_map[r_e_clear_other[0]]] = BM_elem_index_get(e_a_other[1]);
1092  }
1093  }
1094 #endif
1095 
1096  // BM_mesh_validate(bm);
1097 
1098  return true;
1099  }
1100  return false;
1101 }
1102 
1109  BMEdge *e,
1110  Quadric *vquadrics,
1111  float *vweights,
1112  const float vweight_factor,
1113  Heap *eheap,
1114  HeapNode **eheap_table,
1115 #ifdef USE_SYMMETRY
1116  int *edge_symmetry_map,
1117 #endif
1118  const CD_UseFlag customdata_flag,
1119  float optimize_co[3],
1120  bool optimize_co_calc)
1121 {
1122  int e_clear_other[2];
1123  BMVert *v_other = e->v1;
1124  const int v_other_index = BM_elem_index_get(e->v1);
1125  /* the vert is removed so only store the index */
1126  const int v_clear_index = BM_elem_index_get(e->v2);
1127  float customdata_fac;
1128 
1129 #ifdef USE_VERT_NORMAL_INTERP
1130  float v_clear_no[3];
1131  copy_v3_v3(v_clear_no, e->v2->no);
1132 #endif
1133 
1134  /* when false, use without degenerate checks */
1135  if (optimize_co_calc) {
1136  /* disallow collapsing which results in degenerate cases */
1138  /* add back with a high cost */
1139  bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);
1140  return false;
1141  }
1142 
1143  bm_decim_calc_target_co_fl(e, optimize_co, vquadrics);
1144 
1145  /* check if this would result in an overlapping face */
1146  if (UNLIKELY(bm_edge_collapse_is_degenerate_flip(e, optimize_co))) {
1147  /* add back with a high cost */
1148  bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);
1149  return false;
1150  }
1151  }
1152 
1153  /* use for customdata merging */
1154  if (LIKELY(compare_v3v3(e->v1->co, e->v2->co, FLT_EPSILON) == false)) {
1155  customdata_fac = line_point_factor_v3(optimize_co, e->v1->co, e->v2->co);
1156 #if 0
1157  /* simple test for stupid collapse */
1158  if (customdata_fac < 0.0 - FLT_EPSILON || customdata_fac > 1.0f + FLT_EPSILON) {
1159  return false;
1160  }
1161 #endif
1162  }
1163  else {
1164  /* avoid divide by zero */
1165  customdata_fac = 0.5f;
1166  }
1167 
1168  if (bm_edge_collapse(bm,
1169  e,
1170  e->v2,
1171  e_clear_other,
1172 #ifdef USE_SYMMETRY
1173  edge_symmetry_map,
1174 #endif
1175  customdata_flag,
1176  customdata_fac)) {
1177  /* update collapse info */
1178  int i;
1179 
1180  if (vweights) {
1181  float v_other_weight = interpf(
1182  vweights[v_other_index], vweights[v_clear_index], customdata_fac);
1183  CLAMP(v_other_weight, 0.0f, 1.0f);
1184  vweights[v_other_index] = v_other_weight;
1185  }
1186 
1187  /* paranoid safety check */
1188  e = NULL;
1189 
1190  copy_v3_v3(v_other->co, optimize_co);
1191 
1192  /* remove eheap */
1193  for (i = 0; i < 2; i++) {
1194  /* highly unlikely 'eheap_table[ke_other[i]]' would be NULL, but do for sanity sake */
1195  if ((e_clear_other[i] != -1) && (eheap_table[e_clear_other[i]] != NULL)) {
1196  BLI_heap_remove(eheap, eheap_table[e_clear_other[i]]);
1197  eheap_table[e_clear_other[i]] = NULL;
1198  }
1199  }
1200 
1201  /* update vertex quadric, add kept vertex from killed vertex */
1202  BLI_quadric_add_qu_qu(&vquadrics[v_other_index], &vquadrics[v_clear_index]);
1203 
1204  /* update connected normals */
1205 
1206  /* in fact face normals are not used for progressive updates, no need to update them */
1207  // BM_vert_normal_update_all(v);
1208 #ifdef USE_VERT_NORMAL_INTERP
1209  interp_v3_v3v3(v_other->no, v_other->no, v_clear_no, customdata_fac);
1210  normalize_v3(v_other->no);
1211 #else
1212  BM_vert_normal_update(v_other);
1213 #endif
1214 
1215  /* update error costs and the eheap */
1216  if (LIKELY(v_other->e)) {
1217  BMEdge *e_iter;
1218  BMEdge *e_first;
1219  e_iter = e_first = v_other->e;
1220  do {
1221  BLI_assert(BM_edge_find_double(e_iter) == NULL);
1223  e_iter, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1224  } while ((e_iter = bmesh_disk_edge_next(e_iter, v_other)) != e_first);
1225  }
1226 
1227  /* this block used to be disabled,
1228  * but enable now since surrounding faces may have been
1229  * set to COST_INVALID because of a face overlap that no longer occurs */
1230 #if 1
1231  /* optional, update edges around the vertex face fan */
1232  {
1233  BMIter liter;
1234  BMLoop *l;
1235  BM_ITER_ELEM (l, &liter, v_other, BM_LOOPS_OF_VERT) {
1236  if (l->f->len == 3) {
1237  BMEdge *e_outer;
1238  if (BM_vert_in_edge(l->prev->e, l->v)) {
1239  e_outer = l->next->e;
1240  }
1241  else {
1242  e_outer = l->prev->e;
1243  }
1244 
1245  BLI_assert(BM_vert_in_edge(e_outer, l->v) == false);
1246 
1248  e_outer, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1249  }
1250  }
1251  }
1252  /* end optional update */
1253  return true;
1254 #endif
1255  }
1256  /* add back with a high cost */
1257  bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);
1258  return false;
1259 }
1260 
1261 /* Main Decimate Function
1262  * ********************** */
1263 
1265  const float factor,
1266  float *vweights,
1267  float vweight_factor,
1268  const bool do_triangulate,
1269  const int symmetry_axis,
1270  const float symmetry_eps)
1271 {
1272  /* edge heap */
1273  Heap *eheap;
1274  /* edge index aligned table pointing to the eheap */
1275  HeapNode **eheap_table;
1276  /* vert index aligned quadrics */
1277  Quadric *vquadrics;
1278  int tot_edge_orig;
1279  int face_tot_target;
1280 
1281  CD_UseFlag customdata_flag = 0;
1282 
1283 #ifdef USE_SYMMETRY
1284  bool use_symmetry = (symmetry_axis != -1);
1285  int *edge_symmetry_map;
1286 #endif
1287 
1288 #ifdef USE_TRIANGULATE
1289  int edges_tri_tot = 0;
1290  /* temp convert quads to triangles */
1291  bool use_triangulate = bm_decim_triangulate_begin(bm, &edges_tri_tot);
1292 #else
1293  UNUSED_VARS(do_triangulate);
1294 #endif
1295 
1296  /* Allocate variables. */
1297  vquadrics = MEM_callocN(sizeof(Quadric) * bm->totvert, __func__);
1298  /* Since some edges may be degenerate, we might be over allocating a little here. */
1299  eheap = BLI_heap_new_ex(bm->totedge);
1300  eheap_table = MEM_mallocN(sizeof(HeapNode *) * bm->totedge, __func__);
1301  tot_edge_orig = bm->totedge;
1302 
1303  /* build initial edge collapse cost data */
1304  bm_decim_build_quadrics(bm, vquadrics);
1305 
1306  bm_decim_build_edge_cost(bm, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1307 
1308  face_tot_target = bm->totface * factor;
1310 
1311 #ifdef USE_SYMMETRY
1312  edge_symmetry_map = (use_symmetry) ? bm_edge_symmetry_map(bm, symmetry_axis, symmetry_eps) :
1313  NULL;
1314 #else
1315  UNUSED_VARS(symmetry_axis, symmetry_eps);
1316 #endif
1317 
1318 #ifdef USE_CUSTOMDATA
1319  /* initialize customdata flag, we only need math for loops */
1320  if (CustomData_has_interp(&bm->vdata)) {
1321  customdata_flag |= CD_DO_VERT;
1322  }
1323  if (CustomData_has_interp(&bm->edata)) {
1324  customdata_flag |= CD_DO_EDGE;
1325  }
1326  if (CustomData_has_math(&bm->ldata)) {
1327  customdata_flag |= CD_DO_LOOP;
1328  }
1329 #endif
1330 
1331  /* iterative edge collapse and maintain the eheap */
1332 #ifdef USE_SYMMETRY
1333  if (use_symmetry == false)
1334 #endif
1335  {
1336  /* simple non-mirror case */
1337  while ((bm->totface > face_tot_target) && (BLI_heap_is_empty(eheap) == false) &&
1338  (BLI_heap_top_value(eheap) != COST_INVALID)) {
1339  // const float value = BLI_heap_node_value(BLI_heap_top(eheap));
1340  BMEdge *e = BLI_heap_pop_min(eheap);
1341  float optimize_co[3];
1342  /* handy to detect corruptions elsewhere */
1343  BLI_assert(BM_elem_index_get(e) < tot_edge_orig);
1344 
1345  /* Under normal conditions won't be accessed again,
1346  * but NULL just in case so we don't use freed node. */
1347  eheap_table[BM_elem_index_get(e)] = NULL;
1348 
1350  e,
1351  vquadrics,
1352  vweights,
1353  vweight_factor,
1354  eheap,
1355  eheap_table,
1356 #ifdef USE_SYMMETRY
1357  edge_symmetry_map,
1358 #endif
1359  customdata_flag,
1360  optimize_co,
1361  true);
1362  }
1363  }
1364 #ifdef USE_SYMMETRY
1365  else {
1366  while ((bm->totface > face_tot_target) && (BLI_heap_is_empty(eheap) == false) &&
1367  (BLI_heap_top_value(eheap) != COST_INVALID)) {
1375  BMEdge *e = BLI_heap_pop_min(eheap);
1376  const int e_index = BM_elem_index_get(e);
1377  const int e_index_mirr = edge_symmetry_map[e_index];
1378  BMEdge *e_mirr = NULL;
1379  float optimize_co[3];
1380  char e_invalidate = 0;
1381 
1382  BLI_assert(e_index < tot_edge_orig);
1383 
1384  eheap_table[e_index] = NULL;
1385 
1386  if (e_index_mirr != -1) {
1387  if (e_index_mirr == e_index) {
1388  /* pass */
1389  }
1390  else if (eheap_table[e_index_mirr]) {
1391  e_mirr = BLI_heap_node_ptr(eheap_table[e_index_mirr]);
1392  /* for now ignore edges with a shared vertex */
1393  if (BM_edge_share_vert_check(e, e_mirr)) {
1394  /* ignore permanently!
1395  * Otherwise we would keep re-evaluating and attempting to collapse. */
1396  // e_invalidate |= (1 | 2);
1397  goto invalidate;
1398  }
1399  }
1400  else {
1401  /* mirror edge can't be operated on (happens with asymmetrical meshes) */
1402  e_invalidate |= 1;
1403  goto invalidate;
1404  }
1405  }
1406 
1407  /* when false, use without degenerate checks */
1408  {
1409  /* run both before checking (since they invalidate surrounding geometry) */
1410  bool ok_a, ok_b;
1411 
1413  ok_b = e_mirr ? !bm_edge_collapse_is_degenerate_topology(e_mirr) : true;
1414 
1415  /* disallow collapsing which results in degenerate cases */
1416 
1417  if (UNLIKELY(!ok_a || !ok_b)) {
1418  e_invalidate |= (1 | (e_mirr ? 2 : 0));
1419  goto invalidate;
1420  }
1421 
1422  bm_decim_calc_target_co_fl(e, optimize_co, vquadrics);
1423 
1424  if (e_index_mirr == e_index) {
1425  optimize_co[symmetry_axis] = 0.0f;
1426  }
1427 
1428  /* check if this would result in an overlapping face */
1429  if (UNLIKELY(bm_edge_collapse_is_degenerate_flip(e, optimize_co))) {
1430  e_invalidate |= (1 | (e_mirr ? 2 : 0));
1431  goto invalidate;
1432  }
1433  }
1434 
1436  e,
1437  vquadrics,
1438  vweights,
1439  vweight_factor,
1440  eheap,
1441  eheap_table,
1442  edge_symmetry_map,
1443  customdata_flag,
1444  optimize_co,
1445  false)) {
1446  if (e_mirr && (eheap_table[e_index_mirr])) {
1447  BLI_assert(e_index_mirr != e_index);
1448  BLI_heap_remove(eheap, eheap_table[e_index_mirr]);
1449  eheap_table[e_index_mirr] = NULL;
1450  optimize_co[symmetry_axis] *= -1.0f;
1452  e_mirr,
1453  vquadrics,
1454  vweights,
1455  vweight_factor,
1456  eheap,
1457  eheap_table,
1458  edge_symmetry_map,
1459  customdata_flag,
1460  optimize_co,
1461  false);
1462  }
1463  }
1464  else {
1465  if (e_mirr && (eheap_table[e_index_mirr])) {
1466  e_invalidate |= 2;
1467  goto invalidate;
1468  }
1469  }
1470 
1471  BLI_assert(e_invalidate == 0);
1472  continue;
1473 
1474  invalidate:
1475  if (e_invalidate & 1) {
1476  bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);
1477  }
1478 
1479  if (e_invalidate & 2) {
1480  BLI_assert(eheap_table[e_index_mirr] != NULL);
1481  BLI_heap_remove(eheap, eheap_table[e_index_mirr]);
1482  eheap_table[e_index_mirr] = NULL;
1483  bm_decim_invalid_edge_cost_single(e_mirr, eheap, eheap_table);
1484  }
1485  }
1486 
1487  MEM_freeN((void *)edge_symmetry_map);
1488  }
1489 #endif /* USE_SYMMETRY */
1490 
1491 #ifdef USE_TRIANGULATE
1492  if (do_triangulate == false) {
1493  /* its possible we only had triangles, skip this step in that case */
1494  if (LIKELY(use_triangulate)) {
1495  /* temp convert quads to triangles */
1496  bm_decim_triangulate_end(bm, edges_tri_tot);
1497  }
1498  }
1499 #endif
1500 
1501  /* free vars */
1502  MEM_freeN(vquadrics);
1503  MEM_freeN(eheap_table);
1504  BLI_heap_free(eheap, NULL);
1505 
1506  /* testing only */
1507  // BM_mesh_validate(bm);
1508 
1509  /* quiet release build warning */
1510  (void)tot_edge_orig;
1511 }
CustomData interface, see also DNA_customdata_types.h.
bool CustomData_has_math(const struct CustomData *data)
void CustomData_bmesh_interp_n(struct CustomData *data, const void **src_blocks, const float *weights, const float *sub_weights, int count, void *dst_block_ofs, int n)
Definition: customdata.cc:4071
bool CustomData_data_equals(int type, const void *data1, const void *data2)
Definition: customdata.cc:3973
bool CustomData_has_interp(const struct CustomData *data)
bool CustomData_layer_has_math(const struct CustomData *data, int layer_n)
#define BLI_array_alloca(arr, realsize)
Definition: BLI_alloca.h:22
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_INLINE
A min-heap / priority queue ADT.
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition: BLI_heap.c:202
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Definition: BLI_heap.c:279
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition: BLI_heap.c:301
float BLI_heap_top_value(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: BLI_heap.c:294
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition: BLI_heap.c:182
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition: BLI_heap.c:245
void * BLI_heap_node_ptr(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: BLI_heap.c:362
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
A KD-tree for nearest neighbor search.
MINLINE float min_ff(float a, float b)
MINLINE float square_f(float a)
MINLINE float interpf(float a, float b, float t)
bool is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition: math_geom.c:5750
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
Definition: math_geom.c:3254
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:33
MINLINE double normalize_v3_db(double n[3])
MINLINE bool compare_v3v3(const float a[3], const float b[3], float limit) ATTR_WARN_UNUSED_RESULT
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float normalize_v3(float r[3])
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE double dot_v3db_v3fl(const double a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
Definition: math_vector.c:29
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void copy_v3fl_v3db(float r[3], const double a[3])
MINLINE void copy_v3db_v3fl(double r[3], const float a[3])
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
Definition: math_vector.c:237
void BLI_memarena_free(struct MemArena *ma) ATTR_NONNULL(1)
Definition: BLI_memarena.c:94
struct MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
Definition: BLI_memarena.c:64
#define BLI_POLYFILL_ARENA_SIZE
#define BLI_POLYFILL_ALLOC_NGON_RESERVE
void BLI_quadric_mul(Quadric *a, double scalar)
Definition: quadric.c:120
bool BLI_quadric_optimize(const Quadric *q, double v[3], double epsilon)
Definition: quadric.c:137
void BLI_quadric_from_plane(Quadric *q, const double v[4])
Definition: quadric.c:26
double BLI_quadric_evaluate(const Quadric *q, const double v[3])
Definition: quadric.c:125
void BLI_quadric_add_qu_qu(Quadric *a, const Quadric *b)
Definition: quadric.c:110
void BLI_quadric_add_qu_ququ(Quadric *r, const Quadric *a, const Quadric *b)
Definition: quadric.c:115
unsigned int uint
Definition: BLI_sys_types.h:67
#define ARRAY_SIZE(arr)
#define UNUSED_VARS(...)
#define UNUSED_VARS_NDEBUG(...)
#define UNUSED(x)
#define UNLIKELY(x)
#define ELEM(...)
#define MIN2(a, b)
#define POINTER_OFFSET(v, ofs)
#define LIKELY(x)
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
typedef double(DMatrix)[4][4]
NSNotificationCenter * center
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum type
Read Guarded memory(de)allocation.
Group Output data from inside of a node group A color picker Mix two input colors RGB to Convert a color s luminance to a grayscale value Generate a normal vector and a dot product Bright Control the brightness and contrast of the input color Vector Map an input vectors to used to fine tune the interpolation of the input Camera Retrieve information about the camera and how it relates to the current shading point s position CLAMP
#define BM_ALL
Definition: bmesh_class.h:410
#define BM_FACE_FIRST_LOOP(p)
Definition: bmesh_class.h:622
@ BM_LOOP
Definition: bmesh_class.h:385
@ BM_FACE
Definition: bmesh_class.h:386
@ BM_VERT
Definition: bmesh_class.h:383
@ BM_EDGE
Definition: bmesh_class.h:384
@ BM_ELEM_TAG
Definition: bmesh_class.h:484
BMFace * BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del)
Join Connected Faces.
Definition: bmesh_core.c:1123
bool BM_edge_splice(BMesh *bm, BMEdge *e_dst, BMEdge *e_src)
Splice Edge.
Definition: bmesh_core.c:2332
bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src)
Splice Vert.
Definition: bmesh_core.c:2046
void BM_face_kill(BMesh *bm, BMFace *f)
Definition: bmesh_core.c:828
void BM_edge_kill(BMesh *bm, BMEdge *e)
Definition: bmesh_core.c:927
static void bm_edge_tag_enable(BMEdge *e)
static void bm_decim_invalid_edge_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table)
static bool bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
static void bm_decim_build_edge_cost(BMesh *bm, const Quadric *vquadrics, const float *vweights, const float vweight_factor, Heap *eheap, HeapNode **eheap_table)
#define TOPOLOGY_FALLBACK_EPS
static int * bm_edge_symmetry_map(BMesh *bm, uint symmetry_axis, float limit)
#define USE_CUSTOMDATA
static void bm_edge_tag_disable(BMEdge *e)
static bool bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_co[3])
static bool bm_face_triangulate(BMesh *bm, BMFace *f_base, LinkNode **r_faces_double, int *r_edges_tri_tot, MemArena *pf_arena, struct Heap *pf_heap)
void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, float vweight_factor, const bool do_triangulate, const int symmetry_axis, const float symmetry_eps)
BM_mesh_decimate.
static void bm_decim_triangulate_end(BMesh *bm, const int edges_tri_tot)
static void bm_decim_calc_target_co_fl(BMEdge *e, float optimize_co[3], const Quadric *vquadrics)
static bool bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e_clear_other[2], int *edge_symmetry_map, const CD_UseFlag customdata_flag, const float customdata_fac)
#define BOUNDARY_PRESERVE_WEIGHT
static void bm_decim_build_edge_cost_single(BMEdge *e, const Quadric *vquadrics, const float *vweights, const float vweight_factor, Heap *eheap, HeapNode **eheap_table)
#define COST_INVALID
#define CAN_LOOP_MERGE(l)
BLI_INLINE int bm_edge_is_manifold_or_boundary(BMLoop *l)
static float bm_decim_build_edge_cost_single__topology(BMEdge *e)
static bool bm_decim_triangulate_begin(BMesh *bm, int *r_edges_tri_tot)
#define USE_SYMMETRY
static bool bm_decim_edge_collapse(BMesh *bm, BMEdge *e, Quadric *vquadrics, float *vweights, const float vweight_factor, Heap *eheap, HeapNode **eheap_table, int *edge_symmetry_map, const CD_UseFlag customdata_flag, float optimize_co[3], bool optimize_co_calc)
static void bm_decim_calc_target_co_db(BMEdge *e, double optimize_co[3], const Quadric *vquadrics)
#define OPTIMIZE_EPS
static float bm_decim_build_edge_cost_single_squared__topology(BMEdge *e)
static bool bm_edge_symmetry_check_cb(void *user_data, int index, const float UNUSED(co[3]), float UNUSED(dist_sq))
static bool bm_edge_tag_test(BMEdge *e)
static void bm_edge_collapse_loop_customdata(BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other, const float customdata_fac)
static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics)
#define BM_elem_index_get(ele)
Definition: bmesh_inline.h:110
#define BM_elem_flag_disable(ele, hflag)
Definition: bmesh_inline.h:15
#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_data_interp_from_edges(BMesh *bm, const BMEdge *e_src_1, const BMEdge *e_src_2, BMEdge *e_dst, const float fac)
Data, Interpolate From Edges.
Definition: bmesh_interp.c:75
void BM_data_interp_from_verts(BMesh *bm, const BMVert *v_src_1, const BMVert *v_src_2, BMVert *v_dst, const float fac)
Data, Interpolate From Verts.
Definition: bmesh_interp.c:68
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
@ BM_EDGES_OF_MESH
@ BM_VERTS_OF_FACE
@ BM_FACES_OF_MESH
@ BM_LOOPS_OF_VERT
@ BM_LOOPS_OF_EDGE
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
Definition: bmesh_mesh.cc:446
void BM_vert_normal_update(BMVert *v)
void BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **r_faces_new, int *r_faces_new_tot, BMEdge **r_edges_new, int *r_edges_new_tot, LinkNode **r_faces_double, const int quad_method, const int ngon_method, const bool use_tag, MemArena *pf_arena, struct Heap *pf_heap)
void BM_face_normal_update(BMFace *f)
void BM_face_calc_center_median(const BMFace *f, float r_cent[3])
BMEdge * BM_edge_find_double(BMEdge *e)
Definition: bmesh_query.c:1581
bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
Definition: bmesh_query.c:553
bool BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2)
Definition: bmesh_query.c:1074
BMVert * BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
Definition: bmesh_query.c:1079
float BM_edge_calc_length(const BMEdge *e)
Definition: bmesh_query.c:528
BMLoop * BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step)
Definition: bmesh_query.c:461
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_vert_in_edge(const BMEdge *e, const BMVert *v) 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 BMLoop * l_b
ATTR_WARN_UNUSED_RESULT const BMVert * v
BLI_INLINE BMEdge * bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
SIMD_FORCE_INLINE void invalidate()
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition: btQuadWord.h:119
void * user_data
SyclQueue void void * src
SyclQueue void void size_t num_bytes void
void * tree
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_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static ulong * next
#define fabsf(x)
Definition: metal/compat.h:219
static void clear(Message *msg)
Definition: msgfmt.c:278
BMHeader head
Definition: bmesh_class.h:111
BMVert * v1
Definition: bmesh_class.h:122
BMVert * v2
Definition: bmesh_class.h:122
struct BMLoop * l
Definition: bmesh_class.h:128
int len
Definition: bmesh_class.h:267
float no[3]
Definition: bmesh_class.h:271
char hflag
Definition: bmesh_class.h:66
void * data
Definition: bmesh_class.h:51
BMHeader head
Definition: bmesh_class.h:145
struct BMVert * v
Definition: bmesh_class.h:153
struct BMEdge * e
Definition: bmesh_class.h:164
struct BMLoop * radial_next
Definition: bmesh_class.h:204
struct BMLoop * prev
Definition: bmesh_class.h:233
struct BMFace * f
Definition: bmesh_class.h:171
struct BMLoop * next
Definition: bmesh_class.h:233
float co[3]
Definition: bmesh_class.h:87
struct BMEdge * e
Definition: bmesh_class.h:97
float no[3]
Definition: bmesh_class.h:88
BMHeader head
Definition: bmesh_class.h:85
int totvert
Definition: bmesh_class.h:297
char elem_index_dirty
Definition: bmesh_class.h:305
CustomData vdata
Definition: bmesh_class.h:337
int totedge
Definition: bmesh_class.h:297
CustomData edata
Definition: bmesh_class.h:337
CustomData ldata
Definition: bmesh_class.h:337
int totface
Definition: bmesh_class.h:297
CustomDataLayer * layers
Definition: BLI_heap.c:43
void * link
Definition: BLI_linklist.h:24
struct LinkNode * next
Definition: BLI_linklist.h:23