1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
|
/*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
/** \file
* \ingroup bmesh
*
* Main functions for boolean on a #BMesh (used by the tool and modifier)
*/
#include "BLI_array.hh"
#include "BLI_math.h"
#include "BLI_math_mpq.hh"
#include "BLI_mesh_boolean.hh"
#include "BLI_mesh_intersect.hh"
#include "bmesh.h"
#include "bmesh_boolean.h"
#include "bmesh_edgesplit.h"
namespace blender::meshintersect {
#ifdef WITH_GMP
/** Make a #blender::meshintersect::Mesh from #BMesh bm.
* We are given a triangulation of it from the caller via #looptris,
* which are looptris_tot triples of loops that together tessellate
* the faces of bm.
* Return a second #IMesh in *r_triangulated that has the triangulated
* mesh, with face "orig" fields that connect the triangles back to
* the faces in the returned (polygonal) mesh.
*/
static IMesh mesh_from_bm(BMesh *bm,
struct BMLoop *(*looptris)[3],
const int looptris_tot,
IMesh *r_triangulated,
IMeshArena *arena)
{
BLI_assert(r_triangulated != nullptr);
BM_mesh_elem_index_ensure(bm, BM_VERT | BM_EDGE | BM_FACE);
BM_mesh_elem_table_ensure(bm, BM_VERT | BM_EDGE | BM_FACE);
/* Account for triangulation and intersects. */
const int estimate_num_outv = (3 * bm->totvert) / 2;
const int estimate_num_outf = 4 * bm->totface;
arena->reserve(estimate_num_outv, estimate_num_outf);
Array<const Vert *> vert(bm->totvert);
for (int v = 0; v < bm->totvert; ++v) {
BMVert *bmv = BM_vert_at_index(bm, v);
vert[v] = arena->add_or_find_vert(mpq3(bmv->co[0], bmv->co[1], bmv->co[2]), v);
}
Array<Face *> face(bm->totface);
constexpr int estimated_max_facelen = 100;
Vector<const Vert *, estimated_max_facelen> face_vert;
Vector<int, estimated_max_facelen> face_edge_orig;
for (int f = 0; f < bm->totface; ++f) {
BMFace *bmf = BM_face_at_index(bm, f);
int flen = bmf->len;
face_vert.clear();
face_edge_orig.clear();
BMLoop *l = bmf->l_first;
for (int i = 0; i < flen; ++i) {
const Vert *v = vert[BM_elem_index_get(l->v)];
face_vert.append(v);
int e_index = BM_elem_index_get(l->e);
face_edge_orig.append(e_index);
l = l->next;
}
face[f] = arena->add_face(face_vert, f, face_edge_orig);
}
/* Now do the triangulation mesh.
* The loop_tris have accurate v and f members for the triangles,
* but their next and e pointers are not correct for the loops
* that start added-diagonal edges. */
Array<Face *> tri_face(looptris_tot);
face_vert.resize(3);
face_edge_orig.resize(3);
for (int i = 0; i < looptris_tot; ++i) {
BMFace *bmf = looptris[i][0]->f;
int f = BM_elem_index_get(bmf);
for (int j = 0; j < 3; ++j) {
BMLoop *l = looptris[i][j];
int v_index = BM_elem_index_get(l->v);
int e_index;
if (l->next->v == looptris[i][(j + 1) % 3]->v) {
e_index = BM_elem_index_get(l->e);
}
else {
e_index = NO_INDEX;
}
face_vert[j] = vert[v_index];
face_edge_orig[j] = e_index;
}
tri_face[i] = arena->add_face(face_vert, f, face_edge_orig);
}
r_triangulated->set_faces(tri_face);
return IMesh(face);
}
static bool bmvert_attached_to_wire(const BMVert *bmv)
{
/* This is not quite right. It returns true if the only edges
* Attached to \a bmv are wire edges. TODO: iterate through edges
* attached to \a bmv and check #BM_edge_is_wire. */
return BM_vert_is_wire(bmv);
}
static bool face_has_verts_in_order(BMesh *bm, BMFace *bmf, const BMVert *v1, const BMVert *v2)
{
BMIter liter;
BMLoop *l = static_cast<BMLoop *>(BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, bmf));
while (l != nullptr) {
if (l->v == v1 && l->next->v == v2) {
return true;
}
l = static_cast<BMLoop *>(BM_iter_step(&liter));
}
return false;
}
/** Use the unused _BM_ELEM_TAG_ALT #BMElem.hflag to mark geometry we will keep. */
constexpr uint KEEP_FLAG = (1 << 6);
/**
* Change #BMesh bm to have the mesh match m_out. Return true if there were any changes at all.
* Vertices, faces, and edges in the current bm that are not used in the output are killed,
* except we don't kill wire edges and we don't kill hidden geometry.
* Also, the #BM_ELEM_TAG header flag is set for those #BMEdge's that come from intersections
* resulting from the intersection needed by the Boolean operation.
*/
static bool apply_mesh_output_to_bmesh(BMesh *bm, IMesh &m_out)
{
bool any_change = false;
m_out.populate_vert();
/* Initially mark all existing verts as "don't keep", except hidden verts
* and verts attached to wire edges. */
for (int v = 0; v < bm->totvert; ++v) {
BMVert *bmv = BM_vert_at_index(bm, v);
if (BM_elem_flag_test(bmv, BM_ELEM_HIDDEN) || bmvert_attached_to_wire(bmv)) {
BM_elem_flag_enable(bmv, KEEP_FLAG);
}
else {
BM_elem_flag_disable(bmv, KEEP_FLAG);
}
}
/* Reuse old or make new #BMVert's, depending on if there's an orig or not.
* For those reused, mark them "keep".
* Store needed old #BMVert's in new_bmvs first, as the table may be unusable after
* creating a new #BMVert. */
Array<BMVert *> new_bmvs(m_out.vert_size());
for (int v : m_out.vert_index_range()) {
const Vert *vertp = m_out.vert(v);
int orig = vertp->orig;
if (orig != NO_INDEX) {
BLI_assert(orig >= 0 && orig < bm->totvert);
BMVert *bmv = BM_vert_at_index(bm, orig);
new_bmvs[v] = bmv;
BM_elem_flag_enable(bmv, KEEP_FLAG);
}
else {
new_bmvs[v] = NULL;
}
}
for (int v : m_out.vert_index_range()) {
const Vert *vertp = m_out.vert(v);
if (new_bmvs[v] == NULL) {
float co[3];
const double3 &d_co = vertp->co;
for (int i = 0; i < 3; ++i) {
co[i] = static_cast<float>(d_co[i]);
}
BMVert *bmv = BM_vert_create(bm, co, nullptr, BM_CREATE_NOP);
new_bmvs[v] = bmv;
BM_elem_flag_enable(bmv, KEEP_FLAG);
any_change = true;
}
}
/* Initially mark all existing faces as "don't keep", except hidden faces.
* Also, save current #BMFace pointers as creating faces will disturb the table. */
Array<BMFace *> old_bmfs(bm->totface);
BM_mesh_elem_index_ensure(bm, BM_FACE);
for (int f = 0; f < bm->totface; ++f) {
BMFace *bmf = BM_face_at_index(bm, f);
old_bmfs[f] = bmf;
if (BM_elem_flag_test(bmf, BM_ELEM_HIDDEN)) {
BM_elem_flag_enable(bmf, KEEP_FLAG);
}
else {
BM_elem_flag_disable(bmf, KEEP_FLAG);
}
}
/* Save the original #BMEdge's so we can use them as examples. */
Array<BMEdge *> old_edges(bm->totedge);
std::copy(bm->etable, bm->etable + bm->totedge, old_edges.begin());
/* Reuse or make new #BMFace's, as the faces are identical to old ones or not.
* If reusing, mark them as "keep". First find the maximum face length
* so we can declare some arrays outside of the face-creating loop. */
int maxflen = 0;
for (const Face *f : m_out.faces()) {
maxflen = max_ii(maxflen, f->size());
}
Array<BMVert *> face_bmverts(maxflen);
Array<BMEdge *> face_bmedges(maxflen);
for (const Face *f : m_out.faces()) {
const Face &face = *f;
int flen = face.size();
for (int i = 0; i < flen; ++i) {
const Vert *v = face[i];
int v_index = m_out.lookup_vert(v);
BLI_assert(v_index < new_bmvs.size());
face_bmverts[i] = new_bmvs[v_index];
}
BMFace *bmf = BM_face_exists(face_bmverts.data(), flen);
/* #BM_face_exists checks if the face exists with the vertices in either order.
* We can only reuse the face if the orientations are the same. */
if (bmf != nullptr && face_has_verts_in_order(bm, bmf, face_bmverts[0], face_bmverts[1])) {
BM_elem_flag_enable(bmf, KEEP_FLAG);
}
else {
int orig = face.orig;
BMFace *orig_face;
/* There should always be an orig face, but just being extra careful here. */
if (orig != NO_INDEX) {
orig_face = old_bmfs[orig];
}
else {
orig_face = nullptr;
}
/* Make or find #BMEdge's. */
for (int i = 0; i < flen; ++i) {
BMVert *bmv1 = face_bmverts[i];
BMVert *bmv2 = face_bmverts[(i + 1) % flen];
BMEdge *bme = BM_edge_exists(bmv1, bmv2);
if (bme == nullptr) {
BMEdge *orig_edge = nullptr;
if (face.edge_orig[i] != NO_INDEX) {
orig_edge = old_edges[face.edge_orig[i]];
}
bme = BM_edge_create(bm, bmv1, bmv2, orig_edge, BM_CREATE_NOP);
if (orig_edge != nullptr) {
BM_elem_select_copy(bm, bme, orig_edge);
}
}
face_bmedges[i] = bme;
if (face.is_intersect[i]) {
BM_elem_flag_enable(bme, BM_ELEM_TAG);
}
else {
BM_elem_flag_disable(bme, BM_ELEM_TAG);
}
}
BMFace *bmf = BM_face_create(
bm, face_bmverts.data(), face_bmedges.data(), flen, orig_face, BM_CREATE_NOP);
if (orig_face != nullptr) {
BM_elem_select_copy(bm, bmf, orig_face);
}
BM_elem_flag_enable(bmf, KEEP_FLAG);
/* Now do interpolation of loop data (e.g., UV's) using the example face. */
if (orig_face != nullptr) {
BMIter liter;
BMLoop *l = static_cast<BMLoop *>(BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, bmf));
while (l != nullptr) {
BM_loop_interp_from_face(bm, l, orig_face, true, true);
l = static_cast<BMLoop *>(BM_iter_step(&liter));
}
}
any_change = true;
}
}
/* Now kill the unused faces and verts, and clear flags for kept ones. */
/* #BM_ITER_MESH_MUTABLE macro needs type casts for C++, so expand here.
* TODO(howard): make some nice C++ iterators for #BMesh. */
BMIter iter;
BMFace *bmf = static_cast<BMFace *>(BM_iter_new(&iter, bm, BM_FACES_OF_MESH, nullptr));
while (bmf != nullptr) {
# ifdef DEBUG
iter.count = BM_iter_mesh_count(BM_FACES_OF_MESH, bm);
# endif
BMFace *bmf_next = static_cast<BMFace *>(BM_iter_step(&iter));
if (BM_elem_flag_test(bmf, KEEP_FLAG)) {
BM_elem_flag_disable(bmf, KEEP_FLAG);
}
else {
BM_face_kill_loose(bm, bmf);
# if 0
BM_face_kill(bm, bmf);
# endif
any_change = true;
}
bmf = bmf_next;
}
BMVert *bmv = static_cast<BMVert *>(BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, nullptr));
while (bmv != nullptr) {
# ifdef DEBUG
iter.count = BM_iter_mesh_count(BM_VERTS_OF_MESH, bm);
# endif
BMVert *bmv_next = static_cast<BMVert *>(BM_iter_step(&iter));
if (BM_elem_flag_test(bmv, KEEP_FLAG)) {
BM_elem_flag_disable(bmv, KEEP_FLAG);
}
else {
BM_vert_kill(bm, bmv);
any_change = true;
}
bmv = bmv_next;
}
return any_change;
}
static bool bmesh_boolean(BMesh *bm,
struct BMLoop *(*looptris)[3],
const int looptris_tot,
int (*test_fn)(BMFace *f, void *user_data),
void *user_data,
int nshapes,
const bool use_self,
const bool use_separate_all,
const BoolOpType boolean_mode)
{
IMeshArena arena;
IMesh m_triangulated;
IMesh m_in = mesh_from_bm(bm, looptris, looptris_tot, &m_triangulated, &arena);
std::function<int(int)> shape_fn;
if (use_self && boolean_mode == BoolOpType::None) {
/* Unary knife operation. Want every face where test_fn doesn't return -1. */
BLI_assert(nshapes == 1);
shape_fn = [bm, test_fn, user_data](int f) {
BMFace *bmf = BM_face_at_index(bm, f);
if (test_fn(bmf, user_data) != -1) {
return 0;
}
return -1;
};
}
else {
shape_fn = [bm, test_fn, user_data](int f) {
BMFace *bmf = BM_face_at_index(bm, f);
int test_val = test_fn(bmf, user_data);
if (test_val >= 0) {
return test_val;
}
return -1;
};
}
IMesh m_out = boolean_mesh(
m_in, boolean_mode, nshapes, shape_fn, use_self, &m_triangulated, &arena);
bool any_change = apply_mesh_output_to_bmesh(bm, m_out);
if (use_separate_all) {
/* We are supposed to separate all faces that are incident on intersection edges. */
BM_mesh_edgesplit(bm, false, true, false);
}
return any_change;
}
#endif // WITH_GMP
} // namespace blender::meshintersect
extern "C" {
/**
* Perform the boolean operation specified by boolean_mode on the mesh bm.
* The inputs to the boolean operation are either one sub-mesh (if use_self is true),
* or two sub-meshes. The sub-meshes are specified by providing a test_fn which takes
* a face and the supplied user_data and says with 'side' of the boolean operation
* that face is for: 0 for the first side (side A), 1 for the second side (side B),
* and -1 if the face is to be ignored completely in the boolean operation.
*
* If use_self is true, all operations do the same: the sub-mesh is self-intersected
* and all pieces inside that result are removed.
* Otherwise, the operations can be one of #BMESH_ISECT_BOOLEAN_ISECT, #BMESH_ISECT_BOOLEAN_UNION,
* or #BMESH_ISECT_BOOLEAN_DIFFERENCE.
*
* (The actual library function called to do the boolean is internally capable of handling
* n-ary operands, so maybe in the future we can expose that functionality to users.)
*/
#ifdef WITH_GMP
bool BM_mesh_boolean(BMesh *bm,
struct BMLoop *(*looptris)[3],
const int looptris_tot,
int (*test_fn)(BMFace *f, void *user_data),
void *user_data,
const int nshapes,
const bool use_self,
const int boolean_mode)
{
return blender::meshintersect::bmesh_boolean(
bm,
looptris,
looptris_tot,
test_fn,
user_data,
nshapes,
use_self,
false,
static_cast<blender::meshintersect::BoolOpType>(boolean_mode));
}
/**
* Perform a Knife Intersection operation on the mesh bm.
* There are either one or two operands, the same as described above for BM_mesh_boolean().
* If use_separate_all is true, each edge that is created from the intersection should
* be used to separate all its incident faces. TODO: implement that.
* TODO: need to ensure that "selected/non-selected" flag of original faces gets propagated
* to the intersection result faces.
*/
bool BM_mesh_boolean_knife(BMesh *bm,
struct BMLoop *(*looptris)[3],
const int looptris_tot,
int (*test_fn)(BMFace *f, void *user_data),
void *user_data,
const int nshapes,
const bool use_self,
const bool use_separate_all)
{
return blender::meshintersect::bmesh_boolean(bm,
looptris,
looptris_tot,
test_fn,
user_data,
nshapes,
use_self,
use_separate_all,
blender::meshintersect::BoolOpType::None);
}
#else
bool BM_mesh_boolean(BMesh *UNUSED(bm),
struct BMLoop *(*looptris)[3],
const int UNUSED(looptris_tot),
int (*test_fn)(BMFace *, void *),
void *UNUSED(user_data),
const int UNUSED(nshapes),
const bool UNUSED(use_self),
const int UNUSED(boolean_mode))
{
UNUSED_VARS(looptris, test_fn);
return false;
}
/**
* Perform a Knife Intersection operation on the mesh bm.
* There are either one or two operands, the same as described above for #BM_mesh_boolean().
* If use_separate_all is true, each edge that is created from the intersection should
* be used to separate all its incident faces. TODO: implement that.
* TODO: need to ensure that "selected/non-selected" flag of original faces gets propagated
* to the intersection result faces.
*/
bool BM_mesh_boolean_knife(BMesh *UNUSED(bm),
struct BMLoop *(*looptris)[3],
const int UNUSED(looptris_tot),
int (*test_fn)(BMFace *, void *),
void *UNUSED(user_data),
const int UNUSED(nshapes),
const bool UNUSED(use_self),
const bool UNUSED(use_separate_all))
{
UNUSED_VARS(looptris, test_fn);
return false;
}
#endif
} /* extern "C" */
|