Blender V5.3
bmo_triangulate.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include "MEM_guardedalloc.h"
12
13#include "DNA_listBase.h"
14
15#include "BLI_listbase.hh"
16#include "BLI_math_vector_c.hh"
17#include "BLI_scanfill.hh"
18#include "BLI_sort_utils.hh"
19
20#include "bmesh.hh"
21#include "bmesh_tools.hh"
23
24namespace blender {
25
26#define ELE_NEW 1
27#define EDGE_MARK 4
28
30{
31 const int quad_method = BMO_slot_int_get(op->slots_in, "quad_method");
32 const int ngon_method = BMO_slot_int_get(op->slots_in, "ngon_method");
33
34 BMOpSlot *slot_facemap_out = BMO_slot_get(op->slots_out, "face_map.out");
35 BMOpSlot *slot_facemap_double_out = BMO_slot_get(op->slots_out, "face_map_double.out");
36
39
41 bm, quad_method, ngon_method, 4, true, op, slot_facemap_out, slot_facemap_double_out);
42
45}
46
47struct SortNormal {
48 float value; /* keep first */
49 float no[3];
50};
51
53{
54 const bool use_beauty = BMO_slot_bool_get(op->slots_in, "use_beauty");
55 const bool use_dissolve = BMO_slot_bool_get(op->slots_in, "use_dissolve");
56 BMOIter siter;
57 BMEdge *e;
58 ScanFillContext sf_ctx;
59 // ScanFillEdge *sf_edge; /* UNUSED */
60 float normal[3];
61 const int scanfill_flag = BLI_SCANFILL_CALC_HOLES | BLI_SCANFILL_CALC_POLYS |
63 uint nors_tot;
64 bool calc_winding = false;
65
67 sf_vert_map.reserve(BMO_slot_buffer_len(op->slots_in, "edges"));
68
69 BMO_slot_vec_get(op->slots_in, "normal", normal);
70
71 BLI_scanfill_begin(&sf_ctx);
72
73 BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
74 ScanFillVert *sf_verts[2];
75 BMVert **e_verts = &e->v1;
76 uint i;
77
79
80 calc_winding = (calc_winding || BM_edge_is_boundary(e));
81
82 for (i = 0; i < 2; i++) {
83 sf_verts[i] = sf_vert_map.lookup_or_add_cb(e_verts[i], [&]() {
84 ScanFillVert *sf_vert = BLI_scanfill_vert_add(&sf_ctx, e_verts[i]->co);
85 sf_vert->tmp.p = e_verts[i];
86 return sf_vert;
87 });
88 }
89
90 /* sf_edge = */ BLI_scanfill_edge_add(&sf_ctx, UNPACK2(sf_verts));
91 // sf_edge->tmp.p = e; /* UNUSED */
92 }
93 nors_tot = sf_vert_map.size();
94
95 if (is_zero_v3(normal)) {
96 /* calculate the normal from the cross product of vert-edge pairs.
97 * Since we don't know winding, just accumulate */
98 ScanFillVert *sf_vert;
99 SortNormal *nors;
100 uint i;
101 bool is_degenerate = true;
102
103 nors = MEM_new_array_uninitialized<SortNormal>(nors_tot, __func__);
104
105 for (sf_vert = sf_ctx.fillvertbase.first(), i = 0; sf_vert; sf_vert = sf_vert->next, i++) {
106 BMVert *v = static_cast<BMVert *>(sf_vert->tmp.p);
107 BMIter eiter;
108 BMEdge *e_pair[2];
109 uint e_index = 0;
110
111 nors[i].value = -1.0f;
112
113 /* only use if 'is_degenerate' stays true */
114 add_v3_v3(normal, v->no);
115
116 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
118 if (e_index == 2) {
119 e_index = 0;
120 break;
121 }
122 e_pair[e_index++] = e;
123 }
124 }
125
126 if (e_index == 2) {
127 float dir_a[3], dir_b[3];
128
129 is_degenerate = false;
130
131 sub_v3_v3v3(dir_a, v->co, BM_edge_other_vert(e_pair[0], v)->co);
132 sub_v3_v3v3(dir_b, v->co, BM_edge_other_vert(e_pair[1], v)->co);
133
134 cross_v3_v3v3(nors[i].no, dir_a, dir_b);
135 nors[i].value = len_squared_v3(nors[i].no);
136
137 /* only to get deterministic behavior (for initial normal) */
138 if (len_squared_v3(dir_a) > len_squared_v3(dir_b)) {
139 negate_v3(nors[i].no);
140 }
141 }
142 }
143
144 if (is_degenerate) [[unlikely]] {
145 /* no vertices have 2 edges?
146 * in this case fall back to the average vertex normals */
147 }
148 else {
149 qsort(nors, nors_tot, sizeof(*nors), BLI_sortutil_cmp_float_reverse);
150
151 copy_v3_v3(normal, nors[0].no);
152 for (i = 0; i < nors_tot; i++) {
153 if (nors[i].value == -1.0f) [[unlikely]] {
154 break;
155 }
156 if (dot_v3v3(normal, nors[i].no) < 0.0f) {
157 negate_v3(nors[i].no);
158 }
159 add_v3_v3(normal, nors[i].no);
160 }
161 normalize_v3(normal);
162 }
163
164 MEM_delete(nors);
165 }
166 else {
167 calc_winding = false;
168 }
169
170 /* in this case we almost certainly have degenerate geometry,
171 * better set a fallback value as a last resort */
172 if (normalize_v3(normal) == 0.0f) [[unlikely]] {
173 normal[2] = 1.0f;
174 }
175
176 BLI_scanfill_calc_ex(&sf_ctx, scanfill_flag, normal);
177
178 /* if we have existing faces, base winding on those */
179 if (calc_winding) {
180 int winding_votes = 0;
181 for (ScanFillFace &sf_tri : sf_ctx.fillfacebase) {
182 BMVert *v_tri[3] = {static_cast<BMVert *>(sf_tri.v1->tmp.p),
183 static_cast<BMVert *>(sf_tri.v2->tmp.p),
184 static_cast<BMVert *>(sf_tri.v3->tmp.p)};
185 uint i, i_prev;
186
187 for (i = 0, i_prev = 2; i < 3; i_prev = i++) {
188 e = BM_edge_exists(v_tri[i], v_tri[i_prev]);
190 winding_votes += (e->l->v == v_tri[i]) ? 1 : -1;
191 }
192 }
193 }
194
195 if (winding_votes < 0) {
196 for (ScanFillFace &sf_tri : sf_ctx.fillfacebase) {
197 std::swap(sf_tri.v2, sf_tri.v3);
198 }
199 }
200 }
201
202 for (ScanFillFace &sf_tri : sf_ctx.fillfacebase) {
203 BMFace *f;
204 BMLoop *l;
205 BMIter liter;
206
208 static_cast<BMVert *>(sf_tri.v1->tmp.p),
209 static_cast<BMVert *>(sf_tri.v2->tmp.p),
210 static_cast<BMVert *>(sf_tri.v3->tmp.p),
211 nullptr,
212 nullptr,
214
216 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
217 if (!BMO_edge_flag_test(bm, l->e, EDGE_MARK)) {
219 }
220 }
221 }
222
223 BLI_scanfill_end(&sf_ctx);
224
225 if (use_beauty) {
226 BMOperator bmop;
227
228 BMO_op_initf(bm, &bmop, op->flag, "beautify_fill faces=%ff edges=%Fe", ELE_NEW, EDGE_MARK);
229 BMO_op_exec(bm, &bmop);
231 BMO_op_finish(bm, &bmop);
232 }
233
234 if (use_dissolve) {
235 BMEdge *e_next;
236 BMIter iter;
237
238 BM_ITER_MESH_MUTABLE (e, e_next, &iter, bm, BM_EDGES_OF_MESH) {
240 /* in rare cases the edges face will have already been removed from the edge */
241 BMLoop *l_a, *l_b;
242 if (BM_edge_loop_pair(e, &l_a, &l_b) &&
243 /* This ensures we don't delete existing faces attached to the geometry being filled.
244 * The likely cause of this will have been a duplicate, where the newly created
245 * face was removed and the existing (un-tagged) face kept.
246 * Follow the rule of not deleting geometry unrelated to the fill. */
248 [[likely]]
249 {
250 BMFace *f_double;
251 BMFace *f_new = BM_faces_join_pair(bm, e->l, e->l->radial_next, false, &f_double);
252
253 if (f_double) [[unlikely]] {
254 /* NOTE(@ideasman42): Regarding duplicate faces.
255 * The common case for filling is to select an empty region and fill it.
256 * In general filling over and existing filled area isn't likely to work well,
257 * so anything done here is more to avoid errors - not part of a typical workflow.
258 *
259 * - It's important never to finish with duplicate faces (an *invalid* mesh).
260 * - Remove the "new" face because having a "fill" action
261 * delete existing geometry is unexpected and could cause problems
262 * if the caller doesn't know to account for this.
263 * - This face may be an *intermediate* state - where multiple edges
264 * would be collapsed to create the final face.
265 * Unfortunately this isn't currently handled as well as it might be,
266 * it may be better to fill a temporary mesh, then apply the final result,
267 * so we only have to deal with final duplicates (not intermediate ones).
268 */
269 if (f_new) {
270 BM_face_kill(bm, f_new);
271 }
272 BM_edge_kill(bm, e);
273 }
274 else if (f_new) {
276 BM_edge_kill(bm, e);
277 }
278 }
279 else if (e->l == nullptr) {
280 BM_edge_kill(bm, e);
281 }
282 else {
283 /* Edges with 1 or 3+ faces attached,
284 * most likely caused by a degenerate mesh. */
285 }
286 }
287 }
288 }
289
291}
292
293} // namespace blender
These structs are the foundation for all linked lists in the library system.
Read Blender memory allocation and freeing.
#define UNPACK2(a)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH_MUTABLE(ele, ele_next, iter, bm, itype)
#define BMO_edge_flag_test(bm, e, oflag)
#define BMO_edge_flag_enable(bm, e, oflag)
#define BMO_face_flag_enable(bm, e, oflag)
#define BMO_ITER(ele, iter, slot_args, slot_name, restrict_flag)
#define BMO_face_flag_test(bm, e, oflag)
#define ELE_NEW
#define EDGE_MARK
Definition bmo_bridge.cc:28
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
Definition BLI_map.hh:620
int64_t size() const
Definition BLI_map.hh:976
void reserve(int64_t n)
Definition BLI_map.hh:1028
BMesh Iterators.
int BMO_slot_int_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
int BMO_slot_buffer_len(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
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.
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void bmo_triangulate_exec(BMesh *bm, BMOperator *op)
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 BLI_scanfill_end(ScanFillContext *sf_ctx)
Definition scanfill.cc:798
@ BLI_SCANFILL_CALC_LOOSE
@ BLI_SCANFILL_CALC_POLYS
@ BLI_SCANFILL_CALC_HOLES
bool BMO_op_initf(BMesh *bm, BMOperator *op, int flag, const char *fmt,...)
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
ATTR_WARN_UNUSED_RESULT const BMVert * v
void BMO_op_exec(BMesh *bm, BMOperator *op)
BMESH OPSTACK EXEC OP.
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
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.
@ BM_CREATE_NO_DOUBLE
Definition bmesh_core.hh:36
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
void BM_edge_kill(BMesh *bm, BMEdge *e)
void BMO_slot_vec_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, float r_vec[3])
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)
struct ScanFillVert * BLI_scanfill_vert_add(ScanFillContext *sf_ctx, const float vec[3])
Definition scanfill.cc:105
int BLI_sortutil_cmp_float_reverse(const void *a_, const void *b_)
Definition sort_utils.cc:41
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
void BLI_scanfill_begin(ScanFillContext *sf_ctx)
Definition scanfill.cc:784
MINLINE void negate_v3(float r[3])
BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
struct ScanFillEdge * BLI_scanfill_edge_add(ScanFillContext *sf_ctx, struct ScanFillVert *v1, struct ScanFillVert *v2)
Definition scanfill.cc:127
BMOpSlot * BMO_slot_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *identifier)
BMESH OPSTACK GET SLOT.
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
MINLINE float normalize_v3(float n[3])
MINLINE void add_v3_v3(float r[3], const float a[3])
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
void BM_face_kill(BMesh *bm, BMFace *f)
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
unsigned int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, int flag, const float nor_proj[3])
Definition scanfill.cc:818
BMFace * BM_faces_join_pair(BMesh *bm, BMLoop *l_a, BMLoop *l_b, const bool do_del, BMFace **r_double)
Faces Join Pair.
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)
void BMO_op_finish(BMesh *bm, BMOperator *op)
BMESH OPSTACK FINISH OP.
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)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE bool is_zero_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op)
struct BMFace * f
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]
ListBaseT< ScanFillFace > fillfacebase
ListBaseT< ScanFillVert > fillvertbase
struct ScanFillVert * v2
struct ScanFillVert * v1
struct ScanFillVert * v3
struct ScanFillVert * next
union blender::ScanFillVert::@124355022001164321030006076112165043115032300246 tmp