Blender  V3.3
bmo_triangulate.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 "DNA_listBase.h"
12 
13 #include "BLI_math.h"
14 #include "BLI_scanfill.h"
15 #include "BLI_sort_utils.h"
16 
17 #include "bmesh.h"
18 #include "bmesh_tools.h"
20 
21 #define ELE_NEW 1
22 #define EDGE_MARK 4
23 
25 {
26  const int quad_method = BMO_slot_int_get(op->slots_in, "quad_method");
27  const int ngon_method = BMO_slot_int_get(op->slots_in, "ngon_method");
28 
29  BMOpSlot *slot_facemap_out = BMO_slot_get(op->slots_out, "face_map.out");
30  BMOpSlot *slot_facemap_double_out = BMO_slot_get(op->slots_out, "face_map_double.out");
31 
34 
36  bm, quad_method, ngon_method, 4, true, op, slot_facemap_out, slot_facemap_double_out);
37 
40 }
41 
42 struct SortNormal {
43  float value; /* keep first */
44  float no[3];
45 };
46 
48 {
49  const bool use_beauty = BMO_slot_bool_get(op->slots_in, "use_beauty");
50  const bool use_dissolve = BMO_slot_bool_get(op->slots_in, "use_dissolve");
51  BMOIter siter;
52  BMEdge *e;
53  ScanFillContext sf_ctx;
54  /* ScanFillEdge *sf_edge; */ /* UNUSED */
55  ScanFillFace *sf_tri;
56  GHash *sf_vert_map;
57  float normal[3];
58  const int scanfill_flag = BLI_SCANFILL_CALC_HOLES | BLI_SCANFILL_CALC_POLYS |
60  uint nors_tot;
61  bool calc_winding = false;
62 
63  sf_vert_map = BLI_ghash_ptr_new_ex(__func__, BMO_slot_buffer_len(op->slots_in, "edges"));
64 
65  BMO_slot_vec_get(op->slots_in, "normal", normal);
66 
67  BLI_scanfill_begin(&sf_ctx);
68 
69  BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
70  ScanFillVert *sf_verts[2];
71  BMVert **e_verts = &e->v1;
72  uint i;
73 
75 
76  calc_winding = (calc_winding || BM_edge_is_boundary(e));
77 
78  for (i = 0; i < 2; i++) {
79  if ((sf_verts[i] = BLI_ghash_lookup(sf_vert_map, e_verts[i])) == NULL) {
80  sf_verts[i] = BLI_scanfill_vert_add(&sf_ctx, e_verts[i]->co);
81  sf_verts[i]->tmp.p = e_verts[i];
82  BLI_ghash_insert(sf_vert_map, e_verts[i], sf_verts[i]);
83  }
84  }
85 
86  /* sf_edge = */ BLI_scanfill_edge_add(&sf_ctx, UNPACK2(sf_verts));
87  /* sf_edge->tmp.p = e; */ /* UNUSED */
88  }
89  nors_tot = BLI_ghash_len(sf_vert_map);
90  BLI_ghash_free(sf_vert_map, NULL, NULL);
91 
92  if (is_zero_v3(normal)) {
93  /* calculate the normal from the cross product of vert-edge pairs.
94  * Since we don't know winding, just accumulate */
95  ScanFillVert *sf_vert;
96  struct SortNormal *nors;
97  uint i;
98  bool is_degenerate = true;
99 
100  nors = MEM_mallocN(sizeof(*nors) * nors_tot, __func__);
101 
102  for (sf_vert = sf_ctx.fillvertbase.first, i = 0; sf_vert; sf_vert = sf_vert->next, i++) {
103  BMVert *v = sf_vert->tmp.p;
104  BMIter eiter;
105  BMEdge *e_pair[2];
106  uint e_index = 0;
107 
108  nors[i].value = -1.0f;
109 
110  /* only use if 'is_degenerate' stays true */
111  add_v3_v3(normal, v->no);
112 
113  BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
114  if (BMO_edge_flag_test(bm, e, EDGE_MARK)) {
115  if (e_index == 2) {
116  e_index = 0;
117  break;
118  }
119  e_pair[e_index++] = e;
120  }
121  }
122 
123  if (e_index == 2) {
124  float dir_a[3], dir_b[3];
125 
126  is_degenerate = false;
127 
128  sub_v3_v3v3(dir_a, v->co, BM_edge_other_vert(e_pair[0], v)->co);
129  sub_v3_v3v3(dir_b, v->co, BM_edge_other_vert(e_pair[1], v)->co);
130 
131  cross_v3_v3v3(nors[i].no, dir_a, dir_b);
132  nors[i].value = len_squared_v3(nors[i].no);
133 
134  /* only to get deterministic behavior (for initial normal) */
135  if (len_squared_v3(dir_a) > len_squared_v3(dir_b)) {
136  negate_v3(nors[i].no);
137  }
138  }
139  }
140 
141  if (UNLIKELY(is_degenerate)) {
142  /* no vertices have 2 edges?
143  * in this case fall back to the average vertex normals */
144  }
145  else {
146  qsort(nors, nors_tot, sizeof(*nors), BLI_sortutil_cmp_float_reverse);
147 
148  copy_v3_v3(normal, nors[0].no);
149  for (i = 0; i < nors_tot; i++) {
150  if (UNLIKELY(nors[i].value == -1.0f)) {
151  break;
152  }
153  if (dot_v3v3(normal, nors[i].no) < 0.0f) {
154  negate_v3(nors[i].no);
155  }
156  add_v3_v3(normal, nors[i].no);
157  }
159  }
160 
161  MEM_freeN(nors);
162  }
163  else {
164  calc_winding = false;
165  }
166 
167  /* in this case we almost certainly have degenerate geometry,
168  * better set a fallback value as a last resort */
169  if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
170  normal[2] = 1.0f;
171  }
172 
173  BLI_scanfill_calc_ex(&sf_ctx, scanfill_flag, normal);
174 
175  /* if we have existing faces, base winding on those */
176  if (calc_winding) {
177  int winding_votes = 0;
178  for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
179  BMVert *v_tri[3] = {sf_tri->v1->tmp.p, sf_tri->v2->tmp.p, sf_tri->v3->tmp.p};
180  uint i, i_prev;
181 
182  for (i = 0, i_prev = 2; i < 3; i_prev = i++) {
183  e = BM_edge_exists(v_tri[i], v_tri[i_prev]);
185  winding_votes += (e->l->v == v_tri[i]) ? 1 : -1;
186  }
187  }
188  }
189 
190  if (winding_votes < 0) {
191  for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
192  SWAP(struct ScanFillVert *, sf_tri->v2, sf_tri->v3);
193  }
194  }
195  }
196 
197  for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
198  BMFace *f;
199  BMLoop *l;
200  BMIter liter;
201 
203  sf_tri->v1->tmp.p,
204  sf_tri->v2->tmp.p,
205  sf_tri->v3->tmp.p,
206  NULL,
207  NULL,
209 
211  BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
212  if (!BMO_edge_flag_test(bm, l->e, EDGE_MARK)) {
214  }
215  }
216  }
217 
218  BLI_scanfill_end(&sf_ctx);
219 
220  if (use_beauty) {
221  BMOperator bmop;
222 
223  BMO_op_initf(bm, &bmop, op->flag, "beautify_fill faces=%ff edges=%Fe", ELE_NEW, EDGE_MARK);
224  BMO_op_exec(bm, &bmop);
226  BMO_op_finish(bm, &bmop);
227  }
228 
229  if (use_dissolve) {
230  BMEdge *e_next;
231  BMIter iter;
232 
233  BM_ITER_MESH_MUTABLE (e, e_next, &iter, bm, BM_EDGES_OF_MESH) {
234  if (BMO_edge_flag_test(bm, e, ELE_NEW)) {
235  /* in rare cases the edges face will have already been removed from the edge */
236  if (LIKELY(BM_edge_is_manifold(e))) {
237  BMFace *f_new = BM_faces_join_pair(bm, e->l, e->l->radial_next, false);
238  if (f_new) {
240  BM_edge_kill(bm, e);
241  }
242  }
243  else if (e->l == NULL) {
244  BM_edge_kill(bm, e);
245  }
246  else {
247  /* Edges with 1 or 3+ faces attached,
248  * most likely caused by a degenerate mesh. */
249  }
250  }
251  }
252  }
253 
255 }
void * BLI_ghash_lookup(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:734
unsigned int BLI_ghash_len(const GHash *gh) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:705
GHash * BLI_ghash_ptr_new_ex(const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
void BLI_ghash_insert(GHash *gh, void *key, void *val)
Definition: BLI_ghash.c:710
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition: BLI_ghash.c:863
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float normalize_v3(float r[3])
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 bool is_zero_v3(const float a[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void negate_v3(float r[3])
MINLINE void add_v3_v3(float r[3], const float a[3])
void BLI_scanfill_begin(ScanFillContext *sf_ctx)
Definition: scanfill.c:779
struct ScanFillVert * BLI_scanfill_vert_add(ScanFillContext *sf_ctx, const float vec[3])
Definition: scanfill.c:112
struct ScanFillEdge * BLI_scanfill_edge_add(ScanFillContext *sf_ctx, struct ScanFillVert *v1, struct ScanFillVert *v2)
Definition: scanfill.c:134
void BLI_scanfill_end(ScanFillContext *sf_ctx)
Definition: scanfill.c:793
unsigned int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, int flag, const float nor_proj[3])
Definition: scanfill.c:813
@ BLI_SCANFILL_CALC_LOOSE
Definition: BLI_scanfill.h:98
@ BLI_SCANFILL_CALC_POLYS
Definition: BLI_scanfill.h:91
@ BLI_SCANFILL_CALC_HOLES
Definition: BLI_scanfill.h:95
int BLI_sortutil_cmp_float_reverse(const void *a_, const void *b_)
Definition: sort_utils.c:38
unsigned int uint
Definition: BLI_sys_types.h:67
#define UNPACK2(a)
#define SWAP(type, a, b)
#define UNLIKELY(x)
#define LIKELY(x)
These structs are the foundation for all linked lists in the library system.
Read Guarded memory(de)allocation.
@ BM_FACE
Definition: bmesh_class.h:386
@ BM_EDGE
Definition: bmesh_class.h:384
@ BM_ELEM_TAG
Definition: bmesh_class.h:484
BMFace * BM_face_create_quad_tri(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, const BMFace *f_example, const eBMCreateFlag create_flag)
Make Quad/Triangle.
void BM_edge_kill(BMesh *bm, BMEdge *e)
Definition: bmesh_core.c:927
@ BM_CREATE_NO_DOUBLE
Definition: bmesh_core.h:14
#define BM_ITER_ELEM(ele, iter, data, itype)
@ BM_EDGES_OF_MESH
@ BM_EDGES_OF_VERT
@ BM_LOOPS_OF_FACE
#define BM_ITER_MESH_MUTABLE(ele, ele_next, iter, bm, itype)
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
BMFace * BM_faces_join_pair(BMesh *bm, BMLoop *l_a, BMLoop *l_b, const bool do_del)
Faces Join Pair.
Definition: bmesh_mods.c:166
void BMO_slot_buffer_flag_enable(BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, short oflag)
BMO_FLAG_BUFFER.
void BMO_slot_buffer_hflag_enable(BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, char hflag, bool do_flush)
BMO_FLAG_BUFFER.
#define BMO_edge_flag_test(bm, e, oflag)
void BMO_slot_vec_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, float r_vec[3])
#define BMO_edge_flag_enable(bm, e, oflag)
void BMO_slot_buffer_from_enabled_hflag(BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, char hflag)
void BMO_op_exec(BMesh *bm, BMOperator *op)
BMESH OPSTACK EXEC OP.
void BMO_slot_buffer_from_enabled_flag(BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, short oflag)
#define BMO_face_flag_enable(bm, e, oflag)
#define BMO_ITER(ele, iter, slot_args, slot_name, restrict_flag)
bool BMO_op_initf(BMesh *bm, BMOperator *op, int flag, const char *fmt,...)
int BMO_slot_int_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
void BMO_op_finish(BMesh *bm, BMOperator *op)
BMESH OPSTACK FINISH OP.
int BMO_slot_buffer_len(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
BMOpSlot * BMO_slot_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *identifier)
BMESH OPSTACK GET SLOT.
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
Definition: bmesh_query.c:1553
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()
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
void BM_mesh_triangulate(BMesh *bm, const int quad_method, const int ngon_method, const int min_vertices, const bool tag_only, BMOperator *op, BMOpSlot *slot_facemap_out, BMOpSlot *slot_facemap_double_out)
#define ELE_NEW
void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op)
#define EDGE_MARK
void bmo_triangulate_exec(BMesh *bm, BMOperator *op)
IconTextureDrawCall normal
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
struct BMEdge * e
Definition: bmesh_class.h:164
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
float co[3]
Definition: bmesh_class.h:87
float no[3]
Definition: bmesh_class.h:88
void * first
Definition: DNA_listBase.h:31
ListBase fillvertbase
Definition: BLI_scanfill.h:17
ListBase fillfacebase
Definition: BLI_scanfill.h:19
struct ScanFillFace * next
Definition: BLI_scanfill.h:73
struct ScanFillVert * v2
Definition: BLI_scanfill.h:74
struct ScanFillVert * v3
Definition: BLI_scanfill.h:74
struct ScanFillVert * v1
Definition: BLI_scanfill.h:74
struct ScanFillVert * next
Definition: BLI_scanfill.h:39
union ScanFillVert::@121 tmp
float no[3]