Blender V5.3
bmesh_boolean.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 <functional>
12
13#include "BLI_array.hh"
14#include "BLI_math_base_c.hh"
15#include "BLI_math_mpq.hh"
16#include "BLI_mesh_boolean.hh"
17#include "BLI_mesh_intersect.hh"
18
19#include "bmesh.hh"
20#include "bmesh_boolean.hh"
21#include "bmesh_edgesplit.hh"
22
23namespace blender {
24
25// #define PERF_DEBUG
26
27namespace meshintersect {
28
29#ifdef WITH_GMP
30
31static float3 clean_float3(const float3 &co)
32{
33 float3 cleaned = co;
34 if (!isfinite(co[0])) [[unlikely]] {
35 cleaned[0] = 0.0f;
36 }
37 if (!isfinite(co[1])) [[unlikely]] {
38 cleaned[1] = 0.0f;
39 }
40 if (!isfinite(co[2])) [[unlikely]] {
41 cleaned[2] = 0.0f;
42 }
43 return cleaned;
44}
45
55static IMesh mesh_from_bm(BMesh *bm,
56 const Span<std::array<BMLoop *, 3>> looptris,
57 IMesh *r_triangulated,
58 IMeshArena *arena)
59{
60 BLI_assert(r_triangulated != nullptr);
63 /* Account for triangulation and intersects. */
64 const int estimate_num_outv = 3 * bm->totvert;
65 const int estimate_num_outf = 4 * bm->totface;
66 arena->reserve(estimate_num_outv, estimate_num_outf);
67 Array<const Vert *> vert(bm->totvert);
68 for (int v = 0; v < bm->totvert; ++v) {
69 const BMVert *bmv = BM_vert_at_index(bm, v);
70 const float3 co = clean_float3(bmv->co);
71 vert[v] = arena->add_or_find_vert(mpq3(co[0], co[1], co[2]), v);
72 }
73 Array<Face *> face(bm->totface);
74 constexpr int estimated_max_facelen = 100;
75 Vector<const Vert *, estimated_max_facelen> face_vert;
76 Vector<int, estimated_max_facelen> face_edge_orig;
77 for (int f = 0; f < bm->totface; ++f) {
78 BMFace *bmf = BM_face_at_index(bm, f);
79 int flen = bmf->len;
80 face_vert.clear();
81 face_edge_orig.clear();
82 BMLoop *l = bmf->l_first;
83 for (int i = 0; i < flen; ++i) {
84 const Vert *v = vert[BM_elem_index_get(l->v)];
85 face_vert.append(v);
86 int e_index = BM_elem_index_get(l->e);
87 face_edge_orig.append(e_index);
88 l = l->next;
89 }
90 face[f] = arena->add_face(face_vert, f, face_edge_orig);
91 }
92 /* Now do the triangulation mesh.
93 * The loop_tris have accurate v and f members for the triangles,
94 * but their next and e pointers are not correct for the loops
95 * that start added-diagonal edges. */
96 Array<Face *> tri_face(looptris.size());
97 face_vert.resize(3);
98 face_edge_orig.resize(3);
99 for (const int i : looptris.index_range()) {
100 BMFace *bmf = looptris[i][0]->f;
101 int f = BM_elem_index_get(bmf);
102 for (int j = 0; j < 3; ++j) {
103 BMLoop *l = looptris[i][j];
104 int v_index = BM_elem_index_get(l->v);
105 int e_index;
106 if (l->next->v == looptris[i][(j + 1) % 3]->v) {
107 e_index = BM_elem_index_get(l->e);
108 }
109 else {
110 e_index = NO_INDEX;
111 }
112 face_vert[j] = vert[v_index];
113 face_edge_orig[j] = e_index;
114 }
115 tri_face[i] = arena->add_face(face_vert, f, face_edge_orig);
116 }
117 r_triangulated->set_faces(tri_face);
118 return IMesh(face);
119}
120
121static bool bmvert_attached_to_wire(const BMVert *bmv)
122{
123 /* This is not quite right. It returns true if the only edges
124 * Attached to \a bmv are wire edges. TODO: iterate through edges
125 * attached to \a bmv and check #BM_edge_is_wire. */
126 return BM_vert_is_wire(bmv);
127}
128
129static bool bmvert_attached_to_hidden_face(BMVert *bmv)
130{
131 BMIter iter;
132 for (BMFace *bmf = static_cast<BMFace *>(BM_iter_new(&iter, nullptr, BM_FACES_OF_VERT, bmv));
133 bmf;
134 bmf = static_cast<BMFace *>(BM_iter_step(&iter)))
135 {
137 return true;
138 }
139 }
140 return false;
141}
142
144constexpr uint KEEP_FLAG = (1 << 6);
145
153static bool apply_mesh_output_to_bmesh(BMesh *bm, IMesh &m_out, bool keep_hidden)
154{
155 bool any_change = false;
156
157 m_out.populate_vert();
158
159 /* Initially mark all existing verts as "don't keep", except hidden verts
160 * (if keep_hidden is true), and verts attached to wire edges. */
161 for (int v = 0; v < bm->totvert; ++v) {
162 BMVert *bmv = BM_vert_at_index(bm, v);
163 if ((keep_hidden &&
164 (BM_elem_flag_test(bmv, BM_ELEM_HIDDEN) || bmvert_attached_to_hidden_face(bmv))) ||
165 bmvert_attached_to_wire(bmv))
166 {
167 BM_elem_flag_enable(bmv, KEEP_FLAG);
168 }
169 else {
170 BM_elem_flag_disable(bmv, KEEP_FLAG);
171 }
172 }
173
174 /* Reuse old or make new #BMVert's, depending on if there's an orig or not.
175 * For those reused, mark them "keep".
176 * Store needed old #BMVert's in new_bmvs first, as the table may be unusable after
177 * creating a new #BMVert. */
178 Array<BMVert *> new_bmvs(m_out.vert_size());
179 for (int v : m_out.vert_index_range()) {
180 const Vert *vertp = m_out.vert(v);
181 int orig = vertp->orig;
182 if (orig != NO_INDEX) {
183 BLI_assert(orig >= 0 && orig < bm->totvert);
184 BMVert *bmv = BM_vert_at_index(bm, orig);
185 new_bmvs[v] = bmv;
186 BM_elem_flag_enable(bmv, KEEP_FLAG);
187 }
188 else {
189 new_bmvs[v] = nullptr;
190 }
191 }
192 for (int v : m_out.vert_index_range()) {
193 const Vert *vertp = m_out.vert(v);
194 if (new_bmvs[v] == nullptr) {
195 float co[3];
196 const double3 &d_co = vertp->co;
197 for (int i = 0; i < 3; ++i) {
198 co[i] = float(d_co[i]);
199 }
200 BMVert *bmv = BM_vert_create(bm, co, nullptr, BM_CREATE_NOP);
201 new_bmvs[v] = bmv;
202 BM_elem_flag_enable(bmv, KEEP_FLAG);
203 any_change = true;
204 }
205 }
206
207 /* Initially mark all existing faces as "don't keep", except hidden faces (if keep_hidden).
208 * Also, save current #BMFace pointers as creating faces will disturb the table. */
209 Array<BMFace *> old_bmfs(bm->totface);
211 for (int f = 0; f < bm->totface; ++f) {
212 BMFace *bmf = BM_face_at_index(bm, f);
213 old_bmfs[f] = bmf;
214 if (keep_hidden && BM_elem_flag_test(bmf, BM_ELEM_HIDDEN)) {
215 BM_elem_flag_enable(bmf, KEEP_FLAG);
216 }
217 else {
218 BM_elem_flag_disable(bmf, KEEP_FLAG);
219 }
220 }
221
222 /* Save the original #BMEdge's so we can use them as examples. */
223 Array<BMEdge *> old_edges(bm->totedge);
224 std::copy_n(bm->etable, bm->totedge, old_edges.begin());
225
226 /* Reuse or make new #BMFace's, as the faces are identical to old ones or not.
227 * If reusing, mark them as "keep". First find the maximum face length
228 * so we can declare some arrays outside of the face-creating loop. */
229 int maxflen = 0;
230 for (const Face *f : m_out.faces()) {
231 maxflen = max_ii(maxflen, f->size());
232 }
233 Array<BMVert *> face_bmverts(maxflen);
234 Array<BMEdge *> face_bmedges(maxflen);
235 for (const Face *f : m_out.faces()) {
236 const Face &face = *f;
237 int flen = face.size();
238 for (int i = 0; i < flen; ++i) {
239 const Vert *v = face[i];
240 int v_index = m_out.lookup_vert(v);
241 BLI_assert(v_index < new_bmvs.size());
242 face_bmverts[i] = new_bmvs[v_index];
243 }
244 BMFace *bmf = BM_face_exists(face_bmverts.data(), flen);
245 /* Never allow any duplicates (either winding), as this isn't legal mesh data, see: 160437. */
246 if (bmf != nullptr) {
247 BM_elem_flag_enable(bmf, KEEP_FLAG);
248 }
249 else {
250 int orig = face.orig;
251 BMFace *orig_face;
252 /* There should always be an orig face, but just being extra careful here. */
253 if (orig != NO_INDEX) {
254 orig_face = old_bmfs[orig];
255 }
256 else {
257 orig_face = nullptr;
258 }
259 /* Make or find #BMEdge's. */
260 for (int i = 0; i < flen; ++i) {
261 BMVert *bmv1 = face_bmverts[i];
262 BMVert *bmv2 = face_bmverts[(i + 1) % flen];
263 BMEdge *bme = BM_edge_exists(bmv1, bmv2);
264 if (bme == nullptr) {
265 BMEdge *orig_edge = nullptr;
266 if (face.edge_orig[i] != NO_INDEX) {
267 orig_edge = old_edges[face.edge_orig[i]];
268 }
269 bme = BM_edge_create(bm, bmv1, bmv2, orig_edge, BM_CREATE_NOP);
270 if (orig_edge != nullptr) {
271 BM_elem_select_copy(bm, bme, orig_edge);
272 }
273 }
274 face_bmedges[i] = bme;
275 if (face.is_intersect[i]) {
277 }
278 else {
280 }
281 }
282 BMFace *bmf = BM_face_create(
283 bm, face_bmverts.data(), face_bmedges.data(), flen, orig_face, BM_CREATE_NOP);
284 if (orig_face != nullptr) {
285 BM_elem_select_copy(bm, bmf, orig_face);
286 }
287 BM_elem_flag_enable(bmf, KEEP_FLAG);
288 /* Now do interpolation of loop data (e.g., UVs) using the example face. */
289 if (orig_face != nullptr) {
290 BMIter liter;
291 BMLoop *l = static_cast<BMLoop *>(BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, bmf));
292 while (l != nullptr) {
293 BM_loop_interp_from_face(bm, l, orig_face, false, true);
294 l = static_cast<BMLoop *>(BM_iter_step(&liter));
295 }
296 }
297 any_change = true;
298 }
299 }
300
301 /* Now kill the unused faces and verts, and clear flags for kept ones. */
302 /* #BM_ITER_MESH_MUTABLE macro needs type casts for C++, so expand here.
303 * TODO(howard): make some nice C++ iterators for #BMesh. */
304 BMIter iter;
305 BMFace *bmf = static_cast<BMFace *>(BM_iter_new(&iter, bm, BM_FACES_OF_MESH, nullptr));
306 while (bmf != nullptr) {
307# ifndef NDEBUG
309# endif
310 BMFace *bmf_next = static_cast<BMFace *>(BM_iter_step(&iter));
311 if (BM_elem_flag_test(bmf, KEEP_FLAG)) {
312 BM_elem_flag_disable(bmf, KEEP_FLAG);
313 }
314 else {
316# if 0
317 BM_face_kill(bm, bmf);
318# endif
319 any_change = true;
320 }
321 bmf = bmf_next;
322 }
323 BMVert *bmv = static_cast<BMVert *>(BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, nullptr));
324 while (bmv != nullptr) {
325# ifndef NDEBUG
327# endif
328 BMVert *bmv_next = static_cast<BMVert *>(BM_iter_step(&iter));
329 if (BM_elem_flag_test(bmv, KEEP_FLAG)) {
330 BM_elem_flag_disable(bmv, KEEP_FLAG);
331 }
332 else {
333 BM_vert_kill(bm, bmv);
334 any_change = true;
335 }
336 bmv = bmv_next;
337 }
338
339 return any_change;
340}
341
342static bool bmesh_boolean(BMesh *bm,
343 const Span<std::array<BMLoop *, 3>> looptris,
344 int (*test_fn)(BMFace *f, void *user_data),
345 void *user_data,
346 int nshapes,
347 const bool use_self,
348 const bool use_separate_all,
349 const bool keep_hidden,
350 const bool hole_tolerant,
351 const BoolOpType boolean_mode)
352{
353 IMeshArena arena;
354 IMesh m_triangulated;
355# ifdef PERF_DEBUG
356 double start_time = BLI_time_now_seconds();
357# endif
358 IMesh m_in = mesh_from_bm(bm, looptris, &m_triangulated, &arena);
359# ifdef PERF_DEBUG
360 double mesh_time = BLI_time_now_seconds();
361 std::cout << "bmesh_boolean, imesh_from_bm done, time = " << mesh_time - start_time << "\n";
362# endif
363 std::function<int(int)> shape_fn;
364 if (use_self && boolean_mode == BoolOpType::None) {
365 /* Unary knife operation. Want every face where test_fn doesn't return -1. */
366 BLI_assert(nshapes == 1);
367 shape_fn = [bm, test_fn, user_data](int f) {
368 BMFace *bmf = BM_face_at_index(bm, f);
369 if (test_fn(bmf, user_data) != -1) {
370 return 0;
371 }
372 return -1;
373 };
374 }
375 else {
376 shape_fn = [bm, test_fn, user_data](int f) {
377 BMFace *bmf = BM_face_at_index(bm, f);
378 int test_val = test_fn(bmf, user_data);
379 if (test_val >= 0) {
380 return test_val;
381 }
382 return -1;
383 };
384 }
385 IMesh m_out = boolean_mesh(
386 m_in, boolean_mode, nshapes, shape_fn, use_self, hole_tolerant, &m_triangulated, &arena);
387# ifdef PERF_DEBUG
388 double boolean_time = BLI_time_now_seconds();
389 std::cout << "boolean done, time = " << boolean_time - mesh_time << "\n";
390# endif
391 bool any_change = apply_mesh_output_to_bmesh(bm, m_out, keep_hidden);
392# ifdef PERF_DEBUG
393 double apply_mesh_time = BLI_time_now_seconds();
394 std::cout << "applied boolean output to bmesh, time = " << apply_mesh_time - boolean_time
395 << "\n";
396# endif
397 if (use_separate_all) {
398 /* We are supposed to separate all faces that are incident on intersection edges. */
399 BM_mesh_edgesplit(bm, false, true, false);
400 }
401 return any_change;
402}
403
404#endif // WITH_GMP
405
406} // namespace meshintersect
407
424#ifdef WITH_GMP
426 const Span<std::array<BMLoop *, 3>> looptris,
427 int (*test_fn)(BMFace *f, void *user_data),
428 void *user_data,
429 const int nshapes,
430 const bool use_self,
431 const bool keep_hidden,
432 const bool hole_tolerant,
433 const int boolean_mode)
434{
435 return meshintersect::bmesh_boolean(bm,
436 looptris,
437 test_fn,
438 user_data,
439 nshapes,
440 use_self,
441 false,
442 keep_hidden,
443 hole_tolerant,
444 static_cast<meshintersect::BoolOpType>(boolean_mode));
445}
446
448 const Span<std::array<BMLoop *, 3>> looptris,
449 int (*test_fn)(BMFace *f, void *user_data),
450 void *user_data,
451 const int nshapes,
452 const bool use_self,
453 const bool use_separate_all,
454 const bool hole_tolerant,
455 const bool keep_hidden)
456{
457 return meshintersect::bmesh_boolean(bm,
458 looptris,
459 test_fn,
460 user_data,
461 nshapes,
462 use_self,
463 use_separate_all,
464 keep_hidden,
465 hole_tolerant,
466 meshintersect::BoolOpType::None);
467}
468#else
469bool BM_mesh_boolean(BMesh * /*bm*/,
470 Span<std::array<BMLoop *, 3>> looptris,
471 int (*test_fn)(BMFace *, void *),
472 void * /*user_data*/,
473 const int /*nshapes*/,
474 const bool /*use_self*/,
475 const bool /*keep_hidden*/,
476 const bool /*hole_tolerant*/,
477 const int /*boolean_mode*/)
478{
479 UNUSED_VARS(looptris, test_fn);
480 return false;
481}
482
484 Span<std::array<BMLoop *, 3>> looptris,
485 int (*test_fn)(BMFace *, void *),
486 void * /*user_data*/,
487 const int /*nshapes*/,
488 const bool /*use_self*/,
489 const bool /*use_separate_all*/,
490 const bool /*hole_tolerant*/,
491 const bool /*keep_hidden*/)
492{
493 UNUSED_VARS(looptris, test_fn);
494 return false;
495}
496#endif
497
498} // namespace blender
#define UNUSED_VARS(...)
#define BLI_assert(a)
#define BM_elem_index_get(ele)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_iter_new(iter, bm, itype, data)
BMesh Iterators.
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
unsigned int uint
Definition BKE_text.h:55
ATTR_WARN_UNUSED_RESULT const BMLoop * l
bool BM_mesh_boolean(BMesh *, Span< std::array< BMLoop *, 3 > > looptris, int(*test_fn)(BMFace *, void *), void *, const int, const bool, const bool, const bool, const int)
void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
void BM_vert_kill(BMesh *bm, BMVert *v)
bool BM_vert_is_wire(const BMVert *v)
MINLINE int max_ii(int a, int b)
ATTR_WARN_UNUSED_RESULT const BMVert * v
BMVert * BM_vert_create(BMesh *bm, const float co[3], const BMVert *v_example, const eBMCreateFlag create_flag)
Main function for creating a new vertex.
BMFace * BM_face_create(BMesh *bm, BMVert *const *verts, BMEdge *const *edges, const int len, const BMFace *f_example, const eBMCreateFlag create_flag)
int BM_iter_mesh_count(const char itype, BMesh *bm)
@ BM_CREATE_NOP
Definition bmesh_core.hh:34
bool BM_mesh_boolean_knife(BMesh *, Span< std::array< BMLoop *, 3 > > looptris, int(*test_fn)(BMFace *, void *), void *, const int, const bool, const bool, const bool, const bool)
void BM_elem_select_copy(BMesh *bm_dst, void *ele_dst_v, const void *ele_src_v)
void BM_face_kill_loose(BMesh *bm, BMFace *f)
VecBase< double, 3 > double3
BLI_INLINE BMVert * BM_vert_at_index(BMesh *bm, const int index)
BMFace * BM_face_exists(BMVert *const *varr, int len)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
void BM_face_kill(BMesh *bm, BMFace *f)
void BM_mesh_edgesplit(BMesh *bm, const bool use_verts, const bool tag_only, const bool copy_select)
double BLI_time_now_seconds()
Definition time.cc:30
BLI_INLINE BMFace * BM_face_at_index(BMesh *bm, const int index)
VecBase< float, 3 > float3
BMEdge * BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, const BMEdge *e_example, const eBMCreateFlag create_flag)
Main function for creating a new edge.
void BM_loop_interp_from_face(BMesh *bm, BMLoop *l_dst, const BMFace *f_src, const bool do_vertex, const bool do_multires)
void vert(const int vert_id, float4 &position)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
struct BMLoop * next
struct BMEdge * e
struct BMVert * v
BMEdge ** etable