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