Blender V5.3
mesh_boolean_manifold.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2025 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#ifdef WITH_MANIFOLD
10# include <algorithm>
11# include <iomanip>
12# include <iostream>
13
14# include "BLI_array.hh"
15# include "BLI_array_utils.hh"
16# include "BLI_map.hh"
17# include "BLI_math_geom_c.hh"
18# include "BLI_math_matrix.hh"
19# include "BLI_math_matrix_c.hh"
21# include "BLI_math_vector.hh"
23# include "BLI_offset_indices.hh"
24# include "BLI_span.hh"
25# include "BLI_task.hh"
26# include "BLI_vector.hh"
27
28// #define DEBUG_TIME
29# ifdef DEBUG_TIME
30# include "BLI_timeit.hh"
31# endif
32
33# include "BKE_attribute.hh"
34# include "BKE_attribute_math.hh"
35# include "BKE_deform.hh"
36# include "BKE_geometry_set.hh"
37# include "BKE_instances.hh"
38# include "BKE_lib_id.hh"
39# include "BKE_mesh.hh"
40
42
43# include "mesh_boolean_intern.hh"
45
46# include "manifold/manifold.h"
47
48using manifold::Manifold;
49using manifold::MeshGL;
50
51/* Using this for now for debug printing of materials. Can remove later. */
52# include "DNA_material_types.h"
53
55
56/* Some debug output functions. */
57
58template<typename T> static void dump_span(Span<T> span, const std::string &name)
59{
60 std::cout << name << ":";
61 for (const int i : span.index_range()) {
62 if (i % 10 == 0) {
63 std::cout << "\n[" << i << "] ";
64 }
65 std::cout << span[i] << " ";
66 }
67 std::cout << "\n";
68}
69
70template<typename T>
71static void dump_span_with_stride(Span<T> span, int stride, const std::string &name)
72{
73 std::cout << name << ":";
74 for (const int i : span.index_range()) {
75 if (i % 10 == 0) {
76 std::cout << "\n[" << i << "] ";
77 }
78 std::cout << span[i] << " ";
79 if (stride > 1 && (i % stride) == stride - 1) {
80 std::cout << "/ ";
81 }
82 }
83 std::cout << "\n";
84}
85
86template<typename T>
87static void dump_vector(const std::vector<T> &vec, int stride, const std::string &name)
88{
89 std::cout << name << ":";
90 for (int i = 0; i < vec.size(); i++) {
91 if (i % 10 == 0) {
92 std::cout << "\n[" << i << "] ";
93 }
94 std::cout << vec[i] << " ";
95 if (stride > 1 && (i % stride) == stride - 1) {
96 std::cout << "/ ";
97 }
98 }
99 std::cout << "\n";
100}
101
102template<typename T>
103static void dump_vector_values(const std::string indent,
104 const std::string &assign_to,
105 const std::vector<T> &vec)
106{
107 std::cout << indent << assign_to << " = { ";
108 for (int i = 0; i < vec.size(); i++) {
109 if (i > 0 && (i % 10) == 0) {
110 std::cout << "\n" << indent << indent;
111 }
112 std::cout << vec[i];
113 if (i == vec.size() - 1) {
114 std::cout << " };\n";
115 }
116 else {
117 std::cout << ", ";
118 }
119 }
120}
121
122static void dump_meshgl(const MeshGL &mgl, const std::string &name)
123{
124 std::cout << "\nMeshGL " << name << ":\n"
125 << "num verts = " << mgl.NumVert() << "\nnum triangles = " << mgl.NumTri() << "\n"
126 << "\n";
127 dump_vector(mgl.vertProperties, mgl.numProp, "vertProperties");
128 dump_vector(mgl.triVerts, 3, "triVerts");
129 dump_vector(mgl.faceID, 1, "faceID");
130 if (!mgl.mergeFromVert.empty()) {
131 dump_vector(mgl.mergeFromVert, 1, "mergeFromVert");
132 dump_vector(mgl.mergeToVert, 1, "mergeToVert");
133 }
134 dump_vector(mgl.runIndex, 1, "runIndex");
135 dump_vector(mgl.runOriginalID, 1, "runOrigiinalID");
136}
137
138[[maybe_unused]] static void dump_meshgl_for_debug(const MeshGL &mgl)
139{
140 std::string indent = " ";
141 std::cout << indent << "MeshGL m;\n";
142 std::cout << std::setprecision(9);
143 std::cout << indent << "m.numProp = " << mgl.numProp << ";\n";
144 dump_vector_values(indent, "m.vertProperties", mgl.vertProperties);
145 dump_vector_values(indent, "m.triVerts", mgl.triVerts);
146 if (!mgl.mergeFromVert.empty()) {
147 dump_vector_values(indent, "m.mergeFromVert", mgl.mergeFromVert);
148 dump_vector_values(indent, "m.mergeToVert", mgl.mergeToVert);
149 }
150 dump_vector_values(indent, "m.runIndex", mgl.runIndex);
151 dump_vector_values(indent, "m.runOriginalID", mgl.runOriginalID);
152 dump_vector_values(indent, "m.faceID", mgl.faceID);
153 if (!mgl.runTransform.empty()) {
154 dump_vector_values(indent, "m.runTransform", mgl.runTransform);
155 }
156 if (!mgl.halfedgeTangent.empty()) {
157 dump_vector_values(indent, "m.halfedgeTangent", mgl.halfedgeTangent);
158 }
159 if (mgl.tolerance != 0) {
160 std::cout << indent << "m.tolerance = " << mgl.tolerance << ";\n";
161 }
162}
163
164[[maybe_unused]] static void dump_meshgl_as_obj(const MeshGL &mgl)
165{
166 std::cout << "\n# Meshgl as OBJ\n";
167 std::cout << std::setprecision(9);
168 for (const int v : IndexRange(mgl.NumVert())) {
169 const int k = v * 3;
170 std::cout << "v " << mgl.vertProperties[k] << " " << mgl.vertProperties[k + 1] << " "
171 << mgl.vertProperties[k + 2] << "\n";
172 }
173 std::cout << "\n";
174 for (const int t : IndexRange(mgl.NumTri())) {
175 const int k = t * 3;
176 std::cout << "f " << mgl.triVerts[k] << " " << mgl.triVerts[k + 1] << " "
177 << mgl.triVerts[k + 2] << "\n";
178 }
179 std::cout << "\n";
180}
181
182static const char *domain_names[] = {
183 "point", "edge", "face", "corner", "curve", "instance", "layer"};
184
185static void dump_mesh(const Mesh *mesh, const std::string &name)
186{
187 std::cout << "\nMesh " << name << ":\n"
188 << "verts_num = " << mesh->verts_num << "\nfaces_num = " << mesh->faces_num
189 << "\nedges_num = " << mesh->edges_num << "\ncorners_num = " << mesh->corners_num
190 << "\n";
191 dump_span(mesh->vert_positions(), "verts");
192 dump_span(mesh->edges(), "edges");
193 dump_span(mesh->corner_verts(), "corner_verts");
194 dump_span(mesh->corner_edges(), "corner_edges");
195 dump_span(mesh->face_offsets(), "face_offsets");
196 std::cout << "triangulation:\n";
197 dump_span(mesh->corner_tris(), "corner_tris");
198 dump_span(mesh->corner_tri_faces(), "corner_tri_faces");
199 std::cout << "attributes:\n";
200 bke::AttributeAccessor attrs = mesh->attributes();
201 attrs.foreach_attribute([&](const bke::AttributeIter &iter) {
202 if (ELEM(iter.name, "position", ".edge_verts", ".corner_vert", ".corner_edge")) {
203 return;
204 }
205 const int di = int8_t(iter.domain);
206 const char *domain = (di >= 0 && di < ATTR_DOMAIN_NUM) ? domain_names[di] : "?";
207 std::string label = std::string(domain) + ": " + iter.name;
208 switch (iter.data_type) {
210 VArraySpan<float> floatspan(*attrs.lookup<float>(iter.name));
211 dump_span(floatspan, label);
212 } break;
214 case bke::AttrType::Bool: {
215 const VArraySpan<int> intspan(*attrs.lookup<int>(iter.name));
216 dump_span(intspan, label);
217 } break;
219 const VArraySpan<float3> float3span(*attrs.lookup<float3>(iter.name));
220 dump_span(float3span, label);
221 } break;
223 const VArraySpan<float2> float2span(*attrs.lookup<float2>(iter.name));
224 dump_span(float2span, label);
225 } break;
226 default:
227 std::cout << label << " attribute not dumped\n";
228 break;
229 }
230 });
231 std::cout << "materials:\n";
232 for (int i = 0; i < mesh->totcol; i++) {
233 std::cout << "[" << i << "]: " << (mesh->mat[i] ? mesh->mat[i]->id.name + 2 : "none") << "\n";
234 }
235}
236
253static void get_manifold(Manifold &manifold,
254 const Span<const Mesh *> meshes,
255 int mesh_index,
256 const MeshOffsets &mesh_offsets)
257{
258 constexpr int dbg_level = 0;
259 if (dbg_level > 0) {
260 std::cout << "get_manifold for mesh " << mesh_index << "\n";
261 }
262 /* Use the original mesh for simplicity for some things, and use the joined mesh for data that
263 * could have been affected by a transform input. A potential optimization would be retrieving
264 * the data from an original mesh instead if the corresponding transform was the identity. */
265 const Mesh &mesh = *meshes[mesh_index];
266 const OffsetIndices<int> faces = mesh.faces();
267 const Span<int> corner_verts = mesh.corner_verts();
268 const Span<int3> corner_tris = mesh.corner_tris();
269
270 MeshGL meshgl;
271
272 constexpr int props_num = 3;
273 meshgl.numProp = props_num;
274 meshgl.vertProperties.resize(size_t(mesh.verts_num) * props_num);
275 array_utils::copy(mesh.vert_positions(), MutableSpan(meshgl.vertProperties).cast<float3>());
276
277 /* Using separate a OriginalID for each input face will prevent co-planar
278 * faces from being merged. We need this until the fix introduced in
279 * Manifold at version 3.1.0. */
280 constexpr bool use_runids = false;
281 if (use_runids) {
282 meshgl.runIndex.resize(mesh.faces_num);
283 meshgl.runOriginalID.resize(mesh.faces_num);
284 }
285
286 const int face_start = mesh_offsets.face_start[mesh_index];
287
288 meshgl.faceID.resize(corner_tris.size());
289 /* Inlined copy of #corner_tris_calc_face_indices with an offset added to the face index. */
290 MutableSpan face_ids = MutableSpan(meshgl.faceID);
291 threading::parallel_for(faces.index_range(), 1024, [&](const IndexRange range) {
292 for (const int i : range) {
293 const IndexRange face = faces[i];
294 const int start = poly_to_tri_count(int(i), int(face.start()));
295 const int num = bke::mesh::face_triangles_num(int(face.size()));
296 face_ids.slice(start, num).fill(uint32_t(i + face_start));
297 if (use_runids) {
298 meshgl.runOriginalID[i] = face_start + i;
299 meshgl.runIndex[i] = start * 3;
300 }
301 }
302 });
303
304 meshgl.triVerts.resize(corner_tris.size() * 3);
305 MutableSpan vert_tris = MutableSpan(meshgl.triVerts).cast<int3>();
306 bke::mesh::vert_tris_from_corner_tris(corner_verts, corner_tris, vert_tris);
307
308 if (!use_runids) {
309 meshgl.runIndex.resize(2);
310 meshgl.runOriginalID.resize(1);
311 meshgl.runIndex[0] = 0;
312 meshgl.runIndex[1] = corner_tris.size() * 3;
313 meshgl.runOriginalID[0] = mesh_index;
314 }
315 if (dbg_level > 0) {
316 dump_meshgl(meshgl, "converted result for mesh " + std::to_string(mesh_index));
317 if (dbg_level > 1) {
318 dump_meshgl_for_debug(meshgl);
319 }
320 }
321 {
322# ifdef DEBUG_TIME
323 timeit::ScopedTimer mtimer("manifold constructor from meshgl");
324# endif
325 manifold = Manifold(meshgl);
326 }
327}
328
333static void get_manifolds(MutableSpan<Manifold> manifolds,
334 const Span<const Mesh *> meshes,
335 const Span<float4x4> transforms,
336 const MeshOffsets &mesh_offsets)
337{
338 constexpr int dbg_level = 0;
339 if (dbg_level > 0) {
340 std::cout << "GET_MANIFOLDS\n";
341 std::cout << "\nMesh Offset (starts):\n";
342 dump_span(mesh_offsets.vert_start.as_span(), "vert");
343 dump_span(mesh_offsets.face_start.as_span(), "face");
344 dump_span(mesh_offsets.edge_start.as_span(), "edge");
345 dump_span(mesh_offsets.corner_start.as_span(), "corner");
346 }
347 const int meshes_num = manifolds.size();
348
349 /* Transforming the original input meshes is a simple way to reuse the #Mesh::corner_tris() cache
350 * for un-transformed meshes. This should reduce memory usage and help to avoid unnecessary cache
351 * re-computations. */
352 Array<const Mesh *> transformed_meshes(meshes_num);
353 for (const int i : meshes.index_range()) {
354 if (math::is_identity(transforms[i])) {
355 transformed_meshes[i] = meshes[i];
356 }
357 else {
358 Mesh *transformed_mesh = BKE_mesh_copy_for_eval(*meshes[i]);
359 bke::mesh_transform(*transformed_mesh, transforms[i], false);
360 transformed_meshes[i] = transformed_mesh;
361 }
362 }
363
364 if (dbg_level > 0) {
365 for (const int mesh_index : IndexRange(meshes_num)) {
366 get_manifold(manifolds[mesh_index], transformed_meshes, mesh_index, mesh_offsets);
367 }
368 }
369 else {
370 threading::parallel_for_each(IndexRange(meshes_num), [&](int mesh_index) {
371 get_manifold(manifolds[mesh_index], transformed_meshes, mesh_index, mesh_offsets);
372 });
373 }
374
375 for (const int i : transformed_meshes.index_range()) {
376 if (transformed_meshes[i] != meshes[i]) {
377 BKE_id_free(nullptr, const_cast<Mesh *>(transformed_meshes[i]));
378 }
379 }
380}
381
382/* Check if the MeshGL \a mgl has problems like bad faces, and if so, correct them
383 * in place by removing the bad faces.
384 * This shouldn't happen but happens sometimes in Manifold library v3.2.0.
385 * (See Issue #155657). It might be possible to remove this function in the future.
386 */
387static void clean_meshgl(MeshGL &mgl)
388{
389 /* See if any triangle has out-of-bounds or repeated vertex indices.
390 * Usually there won't be any, so do this test as fast as possible.
391 */
392 const int numtri = mgl.NumTri();
393 const int numvert = mgl.NumVert();
394 auto bad_tri = [&mgl, numvert](const int t) {
395 const int k = t * 3;
396 const uint32_t i0 = mgl.triVerts[k];
397 const uint32_t i1 = mgl.triVerts[k + 1];
398 const uint32_t i2 = mgl.triVerts[k + 2];
399 if (i0 >= numvert || i1 >= numvert || i2 >= numvert || i0 == i1 || i0 == i2 || i1 == i2) {
400 return true;
401 }
402 return false;
403 };
404 const bool any_bad_faces = threading::parallel_reduce(
405 IndexRange(numtri),
406 20000,
407 false,
408 [&](const IndexRange range, const bool init) {
409 if (init) {
410 return true;
411 }
412 for (const int t : range) {
413 if (bad_tri(t)) {
414 return true;
415 }
416 }
417 return false;
418 },
419 [](const bool a, const bool b) { return a || b; });
420 if (!any_bad_faces) {
421 /* No cleaning necessary. */
422 return;
423 }
424
425 int from_t = 0;
426 int to_t = 0;
427 int from_3t = 0;
428 int to_3t = 0;
429 while (from_t < numtri) {
430 if (bad_tri(from_t)) {
431 from_t++;
432 from_3t += 3;
433 }
434 else {
435 mgl.triVerts[to_3t++] = mgl.triVerts[from_3t++];
436 mgl.triVerts[to_3t++] = mgl.triVerts[from_3t++];
437 mgl.triVerts[to_3t++] = mgl.triVerts[from_3t++];
438 mgl.faceID[to_t++] = mgl.faceID[from_t++];
439 }
440 }
441 const int num_deleted = from_t - to_t;
442 mgl.triVerts.resize(mgl.triVerts.size() - 3 * num_deleted);
443 mgl.faceID.resize(mgl.faceID.size() - num_deleted);
444 /* Note: if need runOriginalIDs those should be adjusted too,
445 * but we aren't currently using those.*/
446}
447
448constexpr int inline_outface_size = 8;
449
450struct OutFace {
451 /* Vertex ids in meshgl indexing space. */
452 Vector<int, inline_outface_size> verts;
453 /* The faceID input to manifold, i.e. original face id in combined input mesh indexing space.
454 */
455 int face_id;
456
457 /* Find the first index (should be only one) of verts that contains v, else -1. */
458 int find_vert_index(int v) const
459 {
460 return verts.first_index_of_try(v);
461 }
462};
463
465struct MeshAssembly {
466 /* Vertex positions, linearized (use vertpos_stride to multiply index). */
467 MutableSpan<float> vertpos;
468 int vertpos_stride = 3;
469 /* How many vertices were in the combined input meshes. */
470 int input_verts_num;
471 /* How many vertices are in the output (i.e., in vertpos). */
472 int output_verts_num;
473 /* The new output faces. */
474 Vector<OutFace> new_faces;
475 /* If we have to delete vertices, this map will have non-zero size and
476 * will map the MeshGL vertex index to final vertex index.
477 * Also, if this mapping happens, the vertpos array will be modified
478 * accordingly.
479 */
480 Vector<int> old_to_new_vert_map;
481
482 float3 vert_position(const int v) const
483 {
484 const int start = vertpos_stride * v;
485 return float3(vertpos[start], vertpos[start + 1], vertpos[start + 2]);
486 }
487
488 int mapped_vert(const int v) const
489 {
490 if (!new_faces.is_empty()) {
491 return old_to_new_vert_map[v];
492 }
493 return v;
494 }
495};
496
503class OutToInMaps {
504 Array<int> vertex_map_;
505 Array<int> face_map_;
506 Array<int> edge_map_;
507 Array<int> corner_map_;
508
509 const MeshAssembly *mesh_assembly_;
510 const Mesh *joined_mesh_;
511 const Mesh *output_mesh_;
512 const MeshOffsets *mesh_offsets_;
513
514 public:
515 OutToInMaps(const MeshAssembly *mesh_assembly,
516 const Mesh *joined_mesh,
517 const Mesh *output_mesh,
518 const MeshOffsets *mesh_offsets)
519 : mesh_assembly_(mesh_assembly),
520 joined_mesh_(joined_mesh),
521 output_mesh_(output_mesh),
522 mesh_offsets_(mesh_offsets)
523 {
524 }
525
526 Span<int> ensure_vertex_map();
527 Span<int> ensure_face_map();
528 Span<int> ensure_edge_map();
529 Span<int> ensure_corner_map();
530};
531
532Span<int> OutToInMaps::ensure_face_map()
533{
534 if (!face_map_.is_empty()) {
535 return face_map_;
536 }
537 /* The MeshAssembly's new_faces should map one to one with output faces. */
538# ifdef DEBUG_TIME
539 timeit::ScopedTimer timer("filling face map");
540# endif
541 face_map_.reinitialize(output_mesh_->faces_num);
542 BLI_assert(mesh_assembly_->new_faces.size() == face_map_.size());
543 constexpr int grain_size = 50000;
544 threading::parallel_for(
545 mesh_assembly_->new_faces.index_range(), grain_size, [&](const IndexRange range) {
546 for (const int i : range) {
547 face_map_[i] = mesh_assembly_->new_faces[i].face_id;
548 }
549 });
550 return face_map_;
551}
552
553Span<int> OutToInMaps::ensure_vertex_map()
554{
555 if (!vertex_map_.is_empty()) {
556 return vertex_map_;
557 }
558 /* There may be better ways, but for now we discover the output to input
559 * vertex mapping by going through the output faces, and for each, looking
560 * through the vertices of the corresponding input face for matches.
561 */
562 const Span<int> face_map = this->ensure_face_map();
563# ifdef DEBUG_TIME
564 timeit::ScopedTimer timer("filling vertex map");
565# endif
566 vertex_map_ = Array<int>(output_mesh_->verts_num, -1);
567 /* To parallelize this, need to deal with the fact that this will
568 * have different threads wanting to write vertex_map, and also want
569 * determinism of which one wins if there is more than one possibility.
570 */
571 const OffsetIndices<int> in_faces = joined_mesh_->faces();
572 const OffsetIndices<int> out_faces = output_mesh_->faces();
573 const Span<int> in_corner_verts = joined_mesh_->corner_verts();
574 const Span<int> out_corner_verts = output_mesh_->corner_verts();
575 const Span<float3> out_vert_positions = output_mesh_->vert_positions();
576 const Span<float3> in_vert_positions = joined_mesh_->vert_positions();
577 for (const int out_face_index : IndexRange(output_mesh_->faces_num)) {
578 const int in_face_index = face_map[out_face_index];
579 const IndexRange in_face = in_faces[in_face_index];
580 const IndexRange out_face = out_faces[out_face_index];
581 const Span<int> in_face_verts = in_corner_verts.slice(in_face);
582 for (const int out_v : out_corner_verts.slice(out_face)) {
583 if (vertex_map_[out_v] != -1) {
584 continue;
585 }
586 float3 out_pos = out_vert_positions[out_v];
587 const auto *it = std::find_if(in_face_verts.begin(), in_face_verts.end(), [&](int in_v) {
588 return out_pos == in_vert_positions[in_v];
589 });
590 if (it != in_face_verts.end()) {
591 int in_v = in_face_verts[std::distance(in_face_verts.begin(), it)];
592 vertex_map_[out_v] = in_v;
593 }
594 }
595 }
596 return vertex_map_;
597}
598
599Span<int> OutToInMaps::ensure_corner_map()
600{
601 if (!corner_map_.is_empty()) {
602 return corner_map_;
603 }
604 /* There may be better ways, but for now we discover the output to input
605 * corner mapping by going through the output faces, and for each, looking
606 * through the corners of the corresponding input face for matches of the
607 * vertex involved.
608 */
609 const Span<int> face_map = this->ensure_face_map();
610 const Span<int> vert_map = this->ensure_vertex_map();
611# ifdef DEBUG_TIME
612 timeit::ScopedTimer timer("filling corner map");
613# endif
614 corner_map_ = Array<int>(output_mesh_->corners_num, -1);
615 const OffsetIndices<int> in_faces = joined_mesh_->faces();
616 const OffsetIndices<int> out_faces = output_mesh_->faces();
617 const Span<int> in_corner_verts = joined_mesh_->corner_verts();
618 const Span<int> out_corner_verts = output_mesh_->corner_verts();
619 constexpr int grain_size = 10000;
620 threading::parallel_for(
621 IndexRange(output_mesh_->faces_num), grain_size, [&](const IndexRange range) {
622 for (const int out_face_index : range) {
623 const int in_face_index = face_map[out_face_index];
624 const IndexRange in_face = in_faces[in_face_index];
625 for (const int out_c : out_faces[out_face_index]) {
626 BLI_assert(corner_map_[out_c] == -1);
627 const int out_v = out_corner_verts[out_c];
628 const int in_v = vert_map[out_v];
629 if (in_v == -1) {
630 continue;
631 }
632 const int in_face_i = in_corner_verts.slice(in_face).first_index_try(in_v);
633 if (in_face_i != -1) {
634 const int in_c = in_face[in_face_i];
635 corner_map_[out_c] = in_c;
636 }
637 }
638 }
639 });
640 return corner_map_;
641}
642
643static bool same_dir(const float3 &p1, const float3 &p2, const float3 &q1, const float3 &q2)
644{
645 float3 p = p1 - p2;
646 float3 q = q1 - q2;
647 float pq = math::length(p) * math::length(q);
648 if (pq == 0.0f) {
649 return true;
650 }
651 float abs_cos_pq = math::abs(math::dot(p, q) / pq);
652 return (math::abs(abs_cos_pq - 1.0f) <= 1e-5f);
653}
654
655Span<int> OutToInMaps::ensure_edge_map()
656{
657 constexpr int dbg_level = 0;
658 if (!edge_map_.is_empty()) {
659 return edge_map_;
660 }
661 if (dbg_level > 0) {
662 std::cout << "\nensure_edge_map\n";
663 if (dbg_level > 1) {
664 dump_mesh(joined_mesh_, "joined_mesh");
665 dump_mesh(output_mesh_, "output_mesh");
666 }
667 }
668 /* There may be better ways to get the edge map, but for now
669 * we go through the output faces, and for each edge, see if
670 * there is an input edge in the corresponding input face that
671 * has one or the other end in common, and if only one end is
672 * in common, is in approximately the same direction.
673 * We can assume that the output and input are manifold.
674 * So if there is an edge that starts or ends at a corner in
675 * the corresponding input face, then we need only look for the
676 * "starts at" case, because if it is "ends at" in this face, it
677 * should be "starts at" in the matching face.
678 */
679 const Span<int> face_map = this->ensure_face_map();
680 const Span<int> vert_map = this->ensure_vertex_map();
681 const Span<int> corner_map = this->ensure_corner_map();
682 /* To parallelize this, would need a way to figure out that
683 * this is the "canonical" edge representative so that only
684 * one thread tries to write this. Or could use atomic operations.
685 */
686# ifdef DEBUG_TIME
687 timeit::ScopedTimer timer("filling edge map");
688# endif
689 edge_map_ = Array<int>(output_mesh_->edges_num, -1);
690 const Span<int> out_corner_edges = output_mesh_->corner_edges();
691 const Span<int> out_corner_verts = output_mesh_->corner_verts();
692 const Span<int2> out_edges = output_mesh_->edges();
693 const Span<float3> out_positions = output_mesh_->vert_positions();
694 const Span<int> in_corner_edges = joined_mesh_->corner_edges();
695 const Span<int> in_corner_verts = joined_mesh_->corner_verts();
696 const Span<int2> in_edges = joined_mesh_->edges();
697 const Span<float3> in_positions = joined_mesh_->vert_positions();
698 const OffsetIndices<int> in_faces = joined_mesh_->faces();
699 const OffsetIndices<int> out_faces = output_mesh_->faces();
700 Array<bool> done_edge(output_mesh_->edges_num, false);
701 for (const int out_face_index : IndexRange(output_mesh_->faces_num)) {
702 const int in_face_index = face_map[out_face_index];
703 const IndexRange in_face = in_faces[in_face_index];
704 const IndexRange in_face_vert_range = vertex_range_for_face(in_face_index, *mesh_offsets_);
705 if (dbg_level > 0) {
706 std::cout << "process out_face = " << out_face_index << ", in_face = " << in_face_index
707 << "\n";
708 }
709 for (const int out_c : out_faces[out_face_index]) {
710 const int in_c = corner_map[out_c];
711 if (dbg_level > 0) {
712 std::cout << " out_c = " << out_c << ", in_c = " << in_c << "\n";
713 }
714 if (in_c == -1) {
715 /* No possible "starts at" match here. */
716 continue;
717 }
718 const int out_e = out_corner_edges[out_c];
719 if (dbg_level > 0) {
720 std::cout << " out_e = " << out_e << ", done = " << done_edge[out_e] << "\n";
721 }
722 if (done_edge[out_e]) {
723 continue;
724 }
725 const int out_v = out_corner_verts[out_c];
726 const int in_e = in_corner_edges[in_c];
727 const int in_v = in_corner_verts[in_c];
728 /* Because of corner mapping, the output vertex should map to the input one. */
729 BLI_assert(vert_map[out_v] == in_v);
730 int2 out_e_v = out_edges[out_e];
731 if (out_e_v[0] != out_v) {
732 out_e_v = {out_e_v[1], out_e_v[0]};
733 }
734 int2 in_e_v = in_edges[in_e];
735 if (in_e_v[0] != in_v) {
736 in_e_v = {in_e_v[1], in_e_v[0]};
737 }
738 if (dbg_level > 0) {
739 std::cout << " out_v = " << out_v << ", in_e = " << in_e << ", in_v = " << in_v << "\n";
740 std::cout << " out_e_v = " << out_e_v << ", in_e_v = " << in_e_v << "\n";
741 std::cout << " vertex_map(out_e_v) = " << int2(vert_map[out_e_v[0]], vert_map[out_e_v[1]])
742 << "\n";
743 }
744 /* Here out_e_v should hold the output vertices in out_e, with the first
745 * one being out_v, the vertex at corner out_c.
746 * Similarly for in_e_v, with the first one being in_v.
747 */
748 BLI_assert(vert_map[out_e_v[0]] == in_e_v[0]);
749 int edge_rep = -1;
750 if (vert_map[out_e_v[1]] == in_e_v[1]) {
751 /* Here both ends of the edges match. */
752 if (dbg_level > 0) {
753 std::cout << " case 1, edge_rep = in_e = " << in_e << "\n";
754 }
755 edge_rep = in_e;
756 }
757 else if (!in_face_vert_range.contains(vert_map[out_e_v[1]])) {
758 /* Here the "ends at" vertex of the output edge is a new vertex or in a different mesh.
759 * Does the edge at least go in the same direction as in_e?
760 */
761 if (same_dir(out_positions[out_e_v[0]],
762 out_positions[out_e_v[1]],
763 in_positions[in_e_v[0]],
764 in_positions[in_e_v[1]]))
765 {
766 if (dbg_level > 0) {
767 std::cout << " case 2, edge_rep = in_e = " << in_e << "\n";
768 }
769 edge_rep = in_e;
770 }
771 }
772 /* It is possible that the output face and corresponding
773 * input face have opposite winding. So do all of the previous
774 * again with the previous edge of input face but same edge of
775 * output face.
776 */
777 if (edge_rep == -1) {
778 const int in_c_prev = bke::mesh::face_corner_prev(in_face, in_c);
779 const int in_e_prev = in_corner_edges[in_c_prev];
780 const int in_v_prev = in_corner_verts[in_c_prev];
781 int2 in_e_v_prev = in_edges[in_e_prev];
782 if (in_e_v_prev[0] != in_v_prev) {
783 in_e_v_prev = {in_e_v_prev[1], in_e_v_prev[0]};
784 }
785 if (dbg_level > 0) {
786 std::cout << " in_c_prev = " << in_c_prev << ", in_e_prev = " << in_e_prev
787 << ", in_v_prev = " << in_v_prev << "\n";
788 std::cout << " in_e_v_prev = " << in_e_v_prev << "\n";
789 }
790 if (vert_map[out_e_v[0]] == in_e_v_prev[1]) {
791 if (vert_map[out_e_v[1]] == in_e_v_prev[0]) {
792 if (dbg_level > 0) {
793 std::cout << " case 3, edge_rep = in_e_prev = " << in_e_prev << "\n";
794 }
795 edge_rep = in_e_prev;
796 }
797 else if (vert_map[out_e_v[1]] == -1) {
798 if (same_dir(out_positions[out_e_v[0]],
799 out_positions[out_e_v[1]],
800 in_positions[in_e_v_prev[0]],
801 in_positions[in_e_v_prev[1]]))
802 {
803 if (dbg_level > 0) {
804 std::cout << " case 4, edge_rep = in_e_prev = " << in_e_prev << "\n";
805 }
806 edge_rep = in_e_prev;
807 }
808 }
809 }
810 }
811 if (edge_rep != -1) {
812 if (dbg_level > 0) {
813 std::cout << " found: set edge_map[" << out_e << "] = " << edge_rep << "\n";
814 }
815 edge_map_[out_e] = edge_rep;
816 done_edge[out_e] = true;
817 }
818 }
819 }
820 return edge_map_;
821}
822
824constexpr int face_group_inline = 4;
825
831static Array<Vector<int, face_group_inline>> get_face_groups(const MeshGL &mgl,
832 int input_faces_num)
833{
834# ifdef DEBUG_TIME
835 timeit::ScopedTimer timer("get_face_groups");
836# endif
837 constexpr int dbg_level = 0;
838 Array<Vector<int, face_group_inline>> fg(input_faces_num);
839 const int tris_num = mgl.NumTri();
840 BLI_assert(mgl.faceID.size() == tris_num);
841 for (const int t : IndexRange(tris_num)) {
842 const int faceid = mgl.faceID[t];
843 fg[faceid].append(t);
844 }
845 if (dbg_level > 0) {
846 std::cout << "face_groups\n";
847 for (const int i : fg.index_range()) {
848 std::cout << "orig face " << i;
849 dump_span(fg[i].as_span(), "");
850 }
851 }
852 return fg;
853}
854
855# if 0
856/* TODO: later */
863static uchar check_original_face(const Vector<int, face_group_inline> &group,
864 const MeshGL &mgl,
865 const Mesh *mesh,
866 int face_index)
867{
868 BLI_assert(0 <= face_index && face_index < mesh->faces_num);
869 const IndexRange orig_face = mesh->faces()[face_index];
870 /* The face can't be original if the number of triangles isn't equal
871 * to the original face size minus 2. */
872 int orig_face_size = orig_face.size();
873 if (orig_face_size != group.size() + 2) {
874 return 0;
875 }
876 Span<int> orig_face_verts = mesh->corner_verts().slice(mesh->faces()[face_index]);
877 /* edge_value[i] will be 1 if that edge is identical to an output edge,
878 * and -1 if it is the reverse of an output edge. */
879 Array<uchar, 20> edge_value(orig_face_size, 0);
880 int stride = mgl.numProp;
881 for (const int t : group) {
882 /* face_vert_index[i] will hold the position in input face face_index
883 * where the i'th vertex of triangle t is (assuming that no position
884 * is exactly repeated in an output face). -1 if there is no such. */
885 Array<int, 3> face_vert_index(3);
886 for (const int i : IndexRange(3)) {
887 int v = mgl.triVerts[3 * t + i];
888 int prop_offset = v * stride;
889 float3 pos(mgl.vertProperties[prop_offset],
890 mgl.vertProperties[prop_offset + 1],
891 mgl.vertProperties[prop_offset + 2]);
892 auto it = std::find_if(orig_face_verts.begin(), orig_face_verts.end(), [&](int orig_v) {
893 return pos == mesh->vert_positions()[orig_v];
894 });
895 face_vert_index[i] = it == orig_face_verts.end() ?
896 -1 :
897 std::distance(orig_face_verts.begin(), it);
898 }
899 /* Now we can tell which original edges are covered by t. */
900 for (const int i : IndexRange(3)) {
901 const int a = face_vert_index[i];
902 const int b = face_vert_index[(i + 1) % 3];
903 if (a != -1 && b != -1) {
904 if ((a + 1) % orig_face_size == b) {
905 edge_value[a] = 1;
906 }
907 else if ((b + 1) % orig_face_size == a) {
908 edge_value[b] = -1;
909 }
910 }
911 }
912 }
913 if (std::all_of(edge_value.begin(), edge_value.end(), [](int x) { return x == 1; })) {
914 return 1;
915 }
916 else if (std::all_of(edge_value.begin(), edge_value.end(), [](int x) { return x == -1; })) {
917 return 2;
918 }
919 return 0;
920}
921# endif
922
923static OutFace make_out_face(const MeshGL &mgl, int tri_index, int orig_face)
924{
925 OutFace ans;
926 ans.verts = Vector<int, inline_outface_size>(3);
927 const int k = 3 * tri_index;
928 ans.verts[0] = mgl.triVerts[k];
929 ans.verts[1] = mgl.triVerts[k + 1];
930 ans.verts[2] = mgl.triVerts[k + 2];
931 ans.face_id = orig_face;
932 return ans;
933}
934
942struct SharedEdge {
943 /* First shared edge ("group edge" indexing). */
944 int e1;
945 /* Second shared edge. */
946 int e2;
947 /* First vertex for e1 (second for e2). */
948 int v1;
949 /* Second vertex for e1 (first for e2). */
950 int v2;
951
952 SharedEdge(int e1, int e2, int v1, int v2) : e1(e1), e2(e2), v1(v1), v2(v2) {}
953
954 /* Return the indices (in the linearized triangle space of an OutFace group)
955 * corresponding to e1 and e2. */
956 int2 outface_group_face_indices() const
957 {
958 return int2(e1 / 3, e2 / 3);
959 }
960};
961
963static inline SharedEdge canon_shared_edge(int e1, int e2, int v1, int v2)
964{
965 if (v1 < v2) {
966 return SharedEdge(e1, e2, v1, v2);
967 }
968 return SharedEdge(e2, e1, v2, v1);
969}
970
976static SharedEdge get_shared_edge_from_pair(const OutFace &tri1, const OutFace &tri2)
977{
978 /* There should be at most one shared edge between the tri1 and tri2. Find it. */
979 SharedEdge shared_edge(-1, -1, -1, -1);
980 for (const int i1 : IndexRange(3)) {
981 for (const int i2 : IndexRange(3)) {
982 const int v1 = tri1.verts[i1];
983 const int v2 = tri2.verts[i2];
984 if (v1 == v2) {
985 const int v1_next = tri1.verts[(i1 + 1) % 3];
986 const int v2_prev = tri2.verts[(i2 + 2) % 3];
987 if (v1_next == v2_prev) {
988 shared_edge = SharedEdge(i1, 3 + ((i2 + 2) % 3), v1, v1_next);
989 break;
990 }
991 const int v1_prev = tri1.verts[(i1 + 2) % 3];
992 const int v2_next = tri2.verts[(i2 + 1) % 3];
993 if (v1_prev == v2_next) {
994 shared_edge = SharedEdge((i1 + 2) % 3, 3 + i2, v1_prev, v1);
995 break;
996 }
997 }
998 }
999 if (shared_edge.e1 != -1) {
1000 break;
1001 }
1002 }
1003 return shared_edge;
1004}
1005
1011static Vector<SharedEdge> get_shared_edges(Span<OutFace> faces)
1012{
1013 Vector<SharedEdge> ans;
1014 /* Map from two vert indices making an edge to where that edge appears
1015 * in list of group edges. */
1016 Map<int2, int> edge_verts_to_tri;
1017 for (const int face_index : faces.index_range()) {
1018 const OutFace &f = faces[face_index];
1019 for (const int i : IndexRange(3)) {
1020 int v1 = f.verts[i];
1021 int v2 = f.verts[(i + 1) % 3];
1022 int this_e = face_index * 3 + i;
1023 edge_verts_to_tri.add_new(int2(v1, v2), this_e);
1024 int other_e = edge_verts_to_tri.lookup_default(int2(v2, v1), -1);
1025 if (other_e != -1) {
1026 ans.append(canon_shared_edge(this_e, other_e, v1, v2));
1027 }
1028 }
1029 }
1030 return ans;
1031}
1032
1038static bool is_legal_merge(const OutFace &f1, const OutFace &f2, int v1, int v2)
1039{
1040 /* For now, just look for each non-splice-involved vertex of each face to see if
1041 * it is in the other face.
1042 * TODO: if the faces are big, sort both together and look for repeats after sorting.
1043 */
1044 for (const int v : f1.verts) {
1045 if (!ELEM(v, v1, v2)) {
1046 if (f2.find_vert_index(v) != -1) {
1047 return false;
1048 }
1049 }
1050 }
1051 for (const int v : f2.verts) {
1052 if (!ELEM(v, v1, v2)) {
1053 if (f1.find_vert_index(v) != -1) {
1054 return false;
1055 }
1056 }
1057 }
1058 return true;
1059}
1060
1069static bool try_merge_out_face_pair(OutFace &f1, const OutFace &f2, const SharedEdge &se)
1070{
1071
1072 constexpr int dbg_level = 0;
1073 if (dbg_level > 0) {
1074 std::cout << "try_merge_out_face_pair\n";
1075 dump_span(f1.verts.as_span(), "f1");
1076 dump_span(f2.verts.as_span(), "f2");
1077 std::cout << "shared edge: "
1078 << "(e" << se.e1 << ",e" << se.e2 << ";v" << se.v1 << ",v" << se.v2 << ")\n";
1079 }
1080 const int f1_len = f1.verts.size();
1081 const int f2_len = f2.verts.size();
1082 const int v1 = se.v1;
1083 const int v2 = se.v2;
1084 /* Find i1, the index of the earlier of v1 and v2 in f1,
1085 * and i2, the index of the earlier of v1 and v2 in f2. */
1086 const int i1 = f1.find_vert_index(v1);
1087 BLI_assert(i1 != -1);
1088 const int i1_next = (i1 + 1) % f1_len;
1089 const int i2 = f2.find_vert_index(v2);
1090 BLI_assert(i2 != -1);
1091 const int i2_next = (i2 + 1) % f2_len;
1092 BLI_assert(f1.verts[i1] == v1 && f1.verts[i1_next] == v2);
1093 BLI_assert(f2.verts[i2] == v2 && f2.verts[i2_next] == v1);
1094 const bool can_merge = is_legal_merge(f1, f2, v1, v2);
1095 if (dbg_level > 0) {
1096 std::cout << "i1 = " << i1 << ", i2 = " << i2 << ", can_merge = " << can_merge << "\n";
1097 }
1098 if (!can_merge) {
1099 return false;
1100 }
1101 /* The merged face is the concatenation of these slices
1102 * (giving inclusive indices, with implied wrap-around at end of faces):
1103 * f1 : [0, i1]
1104 * f2 : [i2_next+1, i2_prev]
1105 * f1 : [i1_next, f1_len-1]
1106 */
1107 const int i2_prev = (i2 + f2_len - 1) % f2_len;
1108 const int i2_next_next = (i2_next + 1) % f2_len;
1109 const auto *f2_start_it = f2.verts.begin() + i2_next_next;
1110 const auto *f2_end_it = f2.verts.begin() + i2_prev + 1;
1111 if (f2_end_it > f2_start_it) {
1112 f1.verts.insert(i1_next, f2_start_it, f2_end_it);
1113 }
1114 else {
1115 const int n1 = std::distance(f2_start_it, f2.verts.end());
1116 if (n1 > 0) {
1117 f1.verts.insert(i1_next, f2_start_it, f2.verts.end());
1118 }
1119 if (n1 < f2_len - 2) {
1120 f1.verts.insert(i1_next + n1, f2.verts.begin(), f2_end_it);
1121 }
1122 }
1123 if (dbg_level > 0) {
1124 dump_span(f1.verts.as_span(), "merge result");
1125 }
1126 return true;
1127}
1128
1130static void merge_out_face_pair(Vector<OutFace> &faces)
1131{
1132 constexpr int dbg_level = 0;
1133 BLI_assert(faces.size() == 2);
1134 OutFace &tri1 = faces[0];
1135 OutFace &tri2 = faces[1];
1136 if (dbg_level > 0) {
1137 std::cout << "\nmerge_out_face_pair for faceid " << faces[0].face_id << "\n";
1138 dump_span(tri1.verts.as_span(), "tri1");
1139 dump_span(tri2.verts.as_span(), "tri2");
1140 }
1141 const SharedEdge shared_edge = get_shared_edge_from_pair(tri1, tri2);
1142 if (shared_edge.e1 == -1) {
1143 /* No shared edge, so no merging possible. */
1144 return;
1145 }
1146 const int va = shared_edge.v1;
1147 const int vb = shared_edge.v2;
1148 const int e1 = shared_edge.e1;
1149 const int e2 = shared_edge.e2;
1150 if (dbg_level > 0) {
1151 std::cout << "shared_edge = e" << e1 << ", e" << e2 << "; " << va << ", " << vb << "\n";
1152 }
1153 BLI_assert(e1 < 3 && e2 >= 3);
1154 /* Say tri1 has verts starting at pos e1 called a, b, c.
1155 * Then tri2 has verts starting at pos e2-3 called b, a, d.
1156 * So the quad we want is b, c, a, d.
1157 */
1158 const int vc = tri1.verts[(e1 + 2) % 3];
1159 const int vd = tri2.verts[(e2 - 3 + 2) % 3];
1160 BLI_assert(tri1.verts[e1] == va && tri1.verts[(e1 + 1) % 3] == vb && tri2.verts[e2 - 3] == vb &&
1161 tri2.verts[(e2 - 3 + 1) % 3] == va);
1162 if (vc == vd) {
1163 /* This can't happen geometrically, but maybe in extreme cases... */
1164 return;
1165 }
1166 tri1.verts.resize(4);
1167 tri1.verts[0] = vb;
1168 tri1.verts[1] = vc;
1169 tri1.verts[2] = va;
1170 tri1.verts[3] = vd;
1171 if (dbg_level > 0) {
1172 dump_span(tri1.verts.as_span(), "merged quad");
1173 }
1174 faces.resize(1);
1175}
1176
1182static void merge_out_faces(Vector<OutFace> &faces)
1183{
1184 constexpr int dbg_level = 0;
1185 if (faces.size() <= 1) {
1186 return;
1187 }
1188 if (faces.size() == 2) {
1189 merge_out_face_pair(faces);
1190 return;
1191 }
1192 if (dbg_level > 0) {
1193 std::cout << "\nmerge_out_faces for faceid " << faces[0].face_id << "\n";
1194 for (const int i : faces.index_range()) {
1195 const OutFace &f = faces[i];
1196 dump_span(f.verts.as_span(), std::to_string(i));
1197 }
1198 }
1199 Vector<SharedEdge> shared_edges = get_shared_edges(faces);
1200 if (dbg_level > 0) {
1201 std::cout << "shared edges:\n";
1202 for (const SharedEdge &se : shared_edges) {
1203 std::cout << "(e" << se.e1 << ",e" << se.e2 << ";v" << se.v1 << ",v" << se.v2 << ")";
1204 }
1205 std::cout << "\n";
1206 // dump_span(shared_edges.as_span(), "shared edges");
1207 }
1208 if (shared_edges.is_empty()) {
1209 return;
1210 }
1211 /* `shared_edge_valid[i]` is true if both edges in shared_edges[i] are still alive. */
1212 Array<bool> shared_edge_valid(shared_edges.size(), true);
1213 /* If `merged_to_faces[i]` is not -1, then argument faces[i] has been merged to that other face.
1214 */
1215 Array<int> merged_to(faces.size(), -1);
1216 /* Local function to follow merged_to mappings as far as possible. */
1217 auto final_merged_to = [&](int f_orig) {
1218 BLI_assert(f_orig != -1);
1219 int f_mapped = f_orig;
1220 do {
1221 if (merged_to[f_mapped] != -1) {
1222 f_mapped = merged_to[f_mapped];
1223 }
1224 } while (merged_to[f_mapped] != -1);
1225 return f_mapped;
1226 };
1227 /* TODO: sort shared_edges by decreasing length. */
1228 for (const int i : shared_edges.index_range()) {
1229 if (!shared_edge_valid[i]) {
1230 continue;
1231 }
1232 const SharedEdge se = shared_edges[i];
1233 const int2 orig_faces = se.outface_group_face_indices();
1234 const int2 cur_faces = int2(final_merged_to(orig_faces[0]), final_merged_to(orig_faces[1]));
1235 const int f1 = cur_faces[0];
1236 const int f2 = cur_faces[1];
1237 if (f1 == -1 || f2 == -2) {
1238 continue;
1239 }
1240 if (dbg_level > 0) {
1241 std::cout << "try merge of faces " << f1 << " and " << f2 << "\n";
1242 }
1243 if (try_merge_out_face_pair(faces[f1], faces[f2], se)) {
1244 if (dbg_level > 0) {
1245 std::cout << "successful merge\n";
1246 dump_span(faces[f1].verts.as_span(), "new f1");
1247 }
1248 merged_to[f2] = f1;
1249 }
1250 }
1251 /* Now compress the surviving faces. */
1252 int move_from = 0;
1253 int move_to = 0;
1254 const int orig_faces_num = faces.size();
1255 while (move_from < orig_faces_num) {
1256 /* Don't move faces that have been merged elsewhere. */
1257 while (move_from < orig_faces_num && merged_to[move_from] != -1) {
1258 move_from++;
1259 }
1260 if (move_from >= orig_faces_num) {
1261 break;
1262 }
1263 if (move_to < move_from) {
1264 faces[move_to] = faces[move_from];
1265 }
1266 move_to++;
1267 move_from++;
1268 }
1269 if (move_to < orig_faces_num) {
1270 faces.resize(move_to);
1271 }
1272 if (dbg_level > 0) {
1273 std::cout << "final faces:\n";
1274 for (const int i : faces.index_range()) {
1275 dump_span(faces[i].verts.as_span(), std::to_string(i));
1276 }
1277 }
1278}
1279
1281static inline bool approx_in_line(const float3 &p0, const float3 &p1, const float3 &p2)
1282{
1283 float cos_ang = math::dot(math::normalize(p1 - p0), math::normalize(p2 - p1));
1284 return math::abs(cos_ang - 1.0) < 1e-4;
1285}
1286
1298static void dissolve_valence2_verts(MeshAssembly &ma)
1299{
1300 const int vnum = ma.output_verts_num;
1301 Array<bool> dissolve(vnum, false);
1302 /* We'll remember up to two vertex neighbors for each vertex. */
1303 Array<std::pair<int, int>> neighbors(ma.output_verts_num, std::pair<int, int>(-1, -1));
1304 /* First, tentatively set dissolve based on neighbors. Alignment will be checked later. */
1305 for (const int f : ma.new_faces.index_range()) {
1306 const OutFace &face = ma.new_faces[f];
1307 const int fsize = face.verts.size();
1308 for (const int i : IndexRange(fsize)) {
1309 const int vprev = face.verts[(i - 1 + fsize) % fsize];
1310 const int v = face.verts[i];
1311 const int vnext = face.verts[(i + 1) % fsize];
1312 std::pair<int, int> &v_nbrs = neighbors[v];
1313 if (v_nbrs.first == -1) {
1314 /* First time we've seen v. Set the tentative neighbors. */
1315 v_nbrs.first = vprev;
1316 v_nbrs.second = vnext;
1317 /* Don't want to dissolve any vert of a triangle, even if triangle is degenerate. */
1318 dissolve[v] = fsize <= 3 ? false : true;
1319 }
1320 else {
1321 /* Some previous face had v. Disable dissolve unless if neighbors are the same, reversed,
1322 * or if this face is a triangle.
1323 */
1324 if (fsize == 3 || !(vprev == v_nbrs.second && vnext == v_nbrs.first)) {
1325 dissolve[v] = false;
1326 }
1327 }
1328 }
1329 }
1330 /* We can't dissolve so many verts in a face that it leaves less than a triangle.
1331 * This should be rare, since the above logic will prevent dissolving a vert from a triangle,
1332 * but it is possible that two or more verts are to be dissolved from a quad or ngon.
1333 * Do a pass to remove the possibility of dissolving anything from such faces. */
1334 for (const int f : ma.new_faces.index_range()) {
1335 const OutFace &face = ma.new_faces[f];
1336 const int fsize = face.verts.size();
1337 int num_dissolved = 0;
1338 for (const int i : IndexRange(fsize)) {
1339 if (dissolve[face.verts[i]]) {
1340 num_dissolved++;
1341 }
1342 }
1343 if (fsize - num_dissolved < 3) {
1344 for (const int i : IndexRange(fsize)) {
1345 dissolve[face.verts[i]] = false;
1346 }
1347 }
1348 }
1349 /* Now, for tentative dissolves, check "in a straight line" condition. */
1350 const int grain_size = 15000;
1351 bool any_dissolve = false;
1352 threading::parallel_for(IndexRange(vnum), grain_size, [&](const IndexRange range) {
1353 bool range_any_dissolve = false;
1354 for (const int v : range) {
1355 if (dissolve[v]) {
1356 std::pair<int, int> &v_nbrs = neighbors[v];
1357 BLI_assert(v_nbrs.first != -1 && v_nbrs.second != -1);
1358 const float3 p0 = ma.vert_position(v_nbrs.first);
1359 const float3 p1 = ma.vert_position(v);
1360 const float3 p2 = ma.vert_position(v_nbrs.second);
1361 if (!approx_in_line(p0, p1, p2)) {
1362 dissolve[v] = false;
1363 }
1364 else {
1365 range_any_dissolve = true;
1366 }
1367 }
1368 }
1369 if (range_any_dissolve) {
1370 /* No need for atomics here as this is a single byte. */
1371 any_dissolve = true;
1372 }
1373 });
1374 if (!any_dissolve) {
1375 return;
1376 }
1377
1378 /* We need to compress out the dissolved vertices out of `ma.vertpos`,
1379 * remap all the faces to account for that compression,
1380 * and rebuild any faces containing those compressed verts.
1381 * The compressing part is a bit like #mesh_copy_selection. */
1382 IndexMaskMemory memory;
1383 IndexMask keep = IndexMask::from_bools_inverse(
1384 dissolve.index_range(), dissolve.as_span(), memory);
1385 const int new_vnum = keep.size();
1386 ma.old_to_new_vert_map.reinitialize(vnum);
1387 ma.old_to_new_vert_map.fill(-1);
1388 index_mask::build_reverse_map<int>(keep, ma.old_to_new_vert_map);
1389
1390 /* Compress `vertpos` in place. Is there a parallel way to do this? */
1391 float *vpos_data = ma.vertpos.data();
1392 BLI_assert(ma.vertpos_stride == 3);
1393 for (const int old_v : IndexRange(vnum)) {
1394 const int new_v = ma.old_to_new_vert_map[old_v];
1395 BLI_assert(new_v <= old_v);
1396 if (new_v >= 0) {
1397 std::copy_n(vpos_data + 3 * old_v, 3, vpos_data + 3 * new_v);
1398 }
1399 }
1400 ma.vertpos = ma.vertpos.take_front(new_vnum * ma.vertpos_stride);
1401 ma.output_verts_num = new_vnum;
1402
1403 /* Remap verts and compress dissolved verts in output faces. */
1404 threading::parallel_for(ma.new_faces.index_range(), 10000, [&](IndexRange range) {
1405 for (const int f : range) {
1406 OutFace &face = ma.new_faces[f];
1407 int i_to = 0;
1408 for (const int i_from : face.verts.index_range()) {
1409 const int mapped_v_from = ma.mapped_vert(face.verts[i_from]);
1410 if (mapped_v_from >= 0) {
1411 face.verts[i_to++] = mapped_v_from;
1412 }
1413 }
1414 if (i_to < face.verts.size()) {
1415 BLI_assert(i_to >= 3);
1416 face.verts.resize(i_to);
1417 }
1418 }
1419 });
1420}
1421
1431static MeshAssembly assemble_mesh_from_meshgl(MeshGL &mgl, const MeshOffsets &mesh_offsets)
1432{
1433# ifdef DEBUG_TIME
1434 timeit::ScopedTimer timer("calculating assemble_mesh_from_meshgl");
1435# endif
1436 constexpr int dbg_level = 0;
1437 if (dbg_level > 0) {
1438 std::cout << "assemble_mesh_from_meshgl\n";
1439 }
1440 MeshAssembly ma;
1441 ma.vertpos = MutableSpan<float>(&*mgl.vertProperties.begin(), mgl.vertProperties.size());
1442 ma.vertpos_stride = mgl.numProp;
1443 ma.input_verts_num = mesh_offsets.vert_start.last();
1444 ma.output_verts_num = ma.vertpos.size() / ma.vertpos_stride;
1445 const int input_faces_num = mesh_offsets.face_start.last();
1446
1447 /* For each offset input mesh face, what mgl triangles have it as id? */
1448 Array<Vector<int, face_group_inline>> face_groups = get_face_groups(mgl, input_faces_num);
1449 if (dbg_level > 1) {
1450 std::cout << "groups:\n";
1451 for (const int i : face_groups.index_range()) {
1452 std::cout << "orig (offset) face " << i << ": ";
1453 dump_span(face_groups[i].as_span(), "");
1454 }
1455 }
1456 {
1457# ifdef DEBUG_TIME
1458 timeit::ScopedTimer timer("face merging");
1459# endif
1460 Vector<Vector<OutFace>> new_groups(face_groups.size());
1461 const int grain_size = 15000;
1462 threading::parallel_for(face_groups.index_range(), grain_size, [&](const IndexRange range) {
1463 for (const int gid : range) {
1464 const Span<int> group = face_groups[gid].as_span();
1465 Vector<OutFace> &group_faces = new_groups[gid] = Vector<OutFace, 4>(group.size());
1466 for (const int i : group_faces.index_range()) {
1467 int tri_index = group[i];
1468 group_faces[i] = make_out_face(mgl, tri_index, gid);
1469 }
1470 merge_out_faces(group_faces);
1471 }
1472 });
1473# ifdef DEBUG_TIME
1474 timeit::ScopedTimer xtimer("copying groups at end");
1475# endif
1476 for (const int i : new_groups.index_range()) {
1477 ma.new_faces.extend(new_groups[i].as_span());
1478 }
1479 }
1480 {
1481# ifdef DEBUG_TIME
1482 timeit::ScopedTimer timer("valence-2-vertex dissolving");
1483# endif
1484 dissolve_valence2_verts(ma);
1485 if (ma.old_to_new_vert_map.size() > 0) {
1486 /* We compressed ma.vertpos in place, but that really means
1487 * we compressed mgl.VertProperties, so we need to change its size. */
1488 mgl.vertProperties.resize(ma.vertpos.size());
1489 }
1490 }
1491 if (dbg_level > 0) {
1492 std::cout << "mesh_assembly result:\n";
1493 std::cout << "input_verts_num = " << ma.input_verts_num
1494 << ", output_verts_num = " << ma.output_verts_num << "\n";
1495 dump_span_with_stride(ma.vertpos.as_span(), ma.vertpos_stride, "vertpos");
1496 std::cout << "new_faces:\n";
1497 for (const int i : ma.new_faces.index_range()) {
1498 std::cout << i << ": face_id = " << ma.new_faces[i].face_id << "\nverts ";
1499 dump_span(ma.new_faces[i].verts.as_span(), "");
1500 }
1501 }
1502 return ma;
1503}
1504
1509static void get_intersecting_edges(Vector<int> *r_intersecting_edges,
1510 const Mesh *mesh,
1511 OutToInMaps &out_to_in,
1512 const MeshOffsets &mesh_offsets)
1513{
1514/* In a manifold mesh, every edge is adjacent to exactly two faces.
1515 * Find them, and when we have a pair, check to see if those faces came
1516 * from separate input meshes, and add the edge to r_intersecting_Edges if so. */
1517# ifdef DEBUG_TIME
1518 timeit::ScopedTimer timer("get_intersecting_edges");
1519# endif
1520 const OffsetIndices<int> faces = mesh->faces();
1521 const Span<int> corner_edges = mesh->corner_edges();
1522 const Span<int> face_map = out_to_in.ensure_face_map();
1523 Array<int> edge_first_face(mesh->edges_num, -1);
1524 for (int face_i : faces.index_range()) {
1525 for (const int edge_i : corner_edges.slice(faces[face_i])) {
1526 int face2_i = edge_first_face[edge_i];
1527 if (face2_i == -1) {
1528 edge_first_face[edge_i] = face_i;
1529 }
1530 else {
1531 int in_face_i = face_map[face_i];
1532 int in_face2_i = face_map[face2_i];
1533 int m1 = mesh_id_for_face(in_face_i, mesh_offsets);
1534 int m2 = mesh_id_for_face(in_face2_i, mesh_offsets);
1535 BLI_assert(m1 != -1 && m2 != -1);
1536 if (m1 != m2) {
1537 r_intersecting_edges->append(edge_i);
1538 }
1539 }
1540 }
1541 }
1542}
1543
1549static bool is_plane(const Mesh *mesh,
1550 const float4x4 &transform,
1551 float3 *r_normal,
1552 float *r_origin_offset)
1553{
1554 if (mesh->faces_num != 1 || mesh->verts_num != 4) {
1555 return false;
1556 }
1557 float3 vpos[4];
1558 const Span<float3> positions = mesh->vert_positions();
1559 const Span<int> f_corners = mesh->corner_verts().slice(mesh->faces()[0]);
1560 for (int i = 0; i < 4; i++) {
1561 mul_v3_m4v3(vpos[i], transform.ptr(), positions[f_corners[i]]);
1562 }
1563 float3 norm1 = math::normal_tri(vpos[0], vpos[1], vpos[2]);
1564 float3 norm2 = math::normal_tri(vpos[0], vpos[2], vpos[3]);
1565 if (math::almost_equal_relative(norm1, norm2, 1e-5f)) {
1566 *r_normal = norm1;
1567 *r_origin_offset = math::dot(norm1, vpos[0]);
1568 return true;
1569 }
1570 return false;
1571}
1572
1579static MeshGL mesh_trim_manifold(Manifold &manifold0,
1580 float3 normal,
1581 float origin_offset,
1582 const MeshOffsets &mesh_offsets,
1583 BooleanError *r_error)
1584{
1585 Manifold man_result = manifold0.TrimByPlane(manifold::vec3(normal[0], normal[1], normal[2]),
1586 double(origin_offset));
1587 MeshGL meshgl = man_result.GetMeshGL();
1588 if (man_result.Status() != Manifold::Error::NoError) {
1589 if (man_result.Status() == Manifold::Error::ResultTooLarge) {
1590 r_error->type = BooleanErrorType::ResultTooBig;
1591 }
1592 else if (man_result.Status() == Manifold::Error::NotManifold) {
1593 r_error->type = BooleanErrorType::NonManifold;
1594 }
1595 else {
1596 r_error->type = BooleanErrorType::UnknownError;
1597 }
1598 return meshgl;
1599 }
1600 /* This meshgl_result has a non-standard (but non-zero) original ID for the
1601 * plane faces, and faceIDs that make no sense for them. Fix this.
1602 * But only do this if the result is not empty. */
1603 if (!meshgl.vertProperties.empty()) {
1604 BLI_assert(meshgl.runOriginalID.size() == 2 && meshgl.runOriginalID[1] > 0);
1605 meshgl.runOriginalID[1] = 1;
1606 BLI_assert(meshgl.runIndex.size() == 3);
1607 int plane_face_start = meshgl.runIndex[1] / 3;
1608 int plane_face_end = meshgl.runIndex[2] / 3;
1609 for (int i = plane_face_start; i < plane_face_end; i++) {
1610 meshgl.faceID[i] = mesh_offsets.face_offsets[1][0];
1611 }
1612 }
1613 return meshgl;
1614}
1615
1622static Mesh *meshgl_to_mesh(MeshGL &mgl,
1623 const Mesh *joined_mesh,
1624 Span<const Mesh *> meshes,
1625 const Span<Array<short>> material_remaps,
1626 const MeshOffsets &mesh_offsets,
1627 Vector<int> *r_intersecting_edges)
1628{
1629 constexpr int dbg_level = 0;
1630 if (dbg_level > 0) {
1631 std::cout << "MESHGL_TO_MESH\n";
1632 }
1633# ifdef DEBUG_TIME
1634 timeit::ScopedTimer timer("meshgl to mesh from joined_mesh");
1635# endif
1636 BLI_assert(mgl.mergeFromVert.empty());
1637
1638 if (mgl.vertProperties.empty() || mgl.triVerts.empty()) {
1639 Mesh *mesh = BKE_mesh_new_nomain(0, 0, 0, 0);
1640 BKE_mesh_copy_parameters_for_eval(mesh, joined_mesh);
1641 return mesh;
1642 }
1643
1644 MeshAssembly ma = assemble_mesh_from_meshgl(mgl, mesh_offsets);
1645 const int verts_num = ma.output_verts_num;
1646 const int faces_num = ma.new_faces.size();
1647
1648 /* Make a new Mesh, now that we know the number of vertices and faces. Corners will be counted
1649 * using the mesh's face offsets, and we will use Blender's parallelized function to calculate
1650 * edges later. */
1651 Mesh *mesh = bke::mesh_new_no_attributes(verts_num, 0, faces_num, 0);
1652 BKE_mesh_copy_parameters_for_eval(mesh, joined_mesh);
1653
1654 /* First the face offsets store the size of each result face, then we accumulate them to form the
1655 * final offsets. */
1656 MutableSpan<int> face_offsets = mesh->face_offsets_for_write();
1657 threading::parallel_for(IndexRange(faces_num), 10'000, [&](const IndexRange range) {
1658 for (const int face : range) {
1659 face_offsets[face] = ma.new_faces[face].verts.size();
1660 }
1661 });
1662 const OffsetIndices<int> faces = offset_indices::accumulate_counts_to_offsets(face_offsets);
1663 mesh->corners_num = faces.total_size();
1664
1665 bke::MutableAttributeAccessor output_attrs = mesh->attributes_for_write();
1666
1667 /* Write corner vertex references. */
1668 {
1669# ifdef DEBUG_TIME
1670 timeit::ScopedTimer timer_c("calculate faces");
1671# endif
1672 output_attrs.add<int>(".corner_vert", bke::AttrDomain::Corner, bke::AttributeInitConstruct());
1673 MutableSpan<int> corner_verts = mesh->corner_verts_for_write();
1674 threading::parallel_for(IndexRange(faces_num), 10'000, [&](const IndexRange range) {
1675 for (const int face : range) {
1676 corner_verts.slice(faces[face]).copy_from(ma.new_faces[face].verts);
1677 }
1678 });
1679 }
1680
1681 /* Set the vertex positions, using implicit sharing to avoid copying any data. */
1682 {
1683# ifdef DEBUG_TIME
1684 timeit::ScopedTimer timer_c("set positions");
1685# endif
1686 BLI_assert(!output_attrs.contains("position"));
1687 BLI_assert(mgl.numProp == 3);
1688 auto *sharing_info = new ImplicitSharedValue<std::vector<float>>(
1689 std::move(mgl.vertProperties));
1690 const bke::AttributeInitShared init(sharing_info->data.data(), *sharing_info);
1691 output_attrs.add<float3>("position", bke::AttrDomain::Point, init);
1692 sharing_info->remove_user_and_delete_if_last();
1693 }
1694
1695 {
1696# ifdef DEBUG_TIME
1697 timeit::ScopedTimer timer_e("calculating edges");
1698# endif
1699 bke::mesh_calc_edges(*mesh, false, false);
1700 }
1701
1702 BLI_assert(bke::mesh_is_valid(*mesh));
1703
1704 OutToInMaps out_to_in(&ma, joined_mesh, mesh, &mesh_offsets);
1705
1706 {
1707# ifdef DEBUG_TIME
1708 timeit::ScopedTimer timer_a("copying and interpolating attributes");
1709# endif
1710
1711 /* Copy attributes from joined_mesh to elements they are mapped to
1712 * in the new mesh. For most attributes, if there is no input element
1713 * mapping to it, the attribute value is left at default.
1714 * But for corner attributes (most importantly, UV maps), missing
1715 * values are interpolated in their containing face.
1716 * We'll do corner interpolation in a separate pass so as to do
1717 * such attributes at once for a given face.
1718 */
1719 bke::AttributeAccessor join_attrs = joined_mesh->attributes();
1720
1721 join_attrs.foreach_attribute([&](const bke::AttributeIter &iter) {
1722 if (iter.domain == bke::AttrDomain::Corner) {
1723 /* Handled separately below. */
1724 return;
1725 }
1726 if (ELEM(iter.name,
1727 "position",
1728 ".edge_verts",
1729 ".corner_vert",
1730 ".corner_edge",
1731 "material_index"))
1732 {
1733 return;
1734 }
1735 const GVArray src = *iter.get();
1736 const CommonVArrayInfo info = src.common_info();
1737 if (info.type == CommonVArrayInfo::Type::Single) {
1738 const bke::AttributeInitValue init(GPointer(src.type(), info.data));
1739 output_attrs.add(iter.name, iter.domain, iter.data_type, init);
1740 return;
1741 }
1742 const GVArraySpan src_span = src;
1743 bke::GSpanAttributeWriter dst = output_attrs.lookup_or_add_for_write_only_span(
1744 iter.name, iter.domain, iter.data_type);
1745 switch (iter.domain) {
1746 case bke::AttrDomain::Point: {
1747 copy_attribute_using_map(src_span, out_to_in.ensure_vertex_map(), dst.span);
1748 break;
1749 }
1750 case bke::AttrDomain::Face: {
1751 copy_attribute_using_map(src_span, out_to_in.ensure_face_map(), dst.span);
1752 break;
1753 }
1754 case bke::AttrDomain::Edge: {
1755 copy_attribute_using_map(src_span, out_to_in.ensure_edge_map(), dst.span);
1756 break;
1757 }
1758 default: {
1760 break;
1761 }
1762 }
1763 dst.finish();
1764 });
1765
1766 if (join_attrs.contains("material_index")) {
1767 /* If #material_remaps is non-empty, we need to use that map to set the
1768 * face "material_index" property instead of taking it from the joined mesh.
1769 * This should only happen if the user wants something other than the default
1770 * "transfer the materials" mode, which has already happened in the joined mesh. */
1771 bke::SpanAttributeWriter dst = output_attrs.lookup_or_add_for_write_only_span<int>(
1772 "material_index", bke::AttrDomain::Face);
1773 if (material_remaps.is_empty()) {
1774 const VArraySpan src = *join_attrs.lookup<int>("material_index");
1775 copy_attribute_using_map(src, out_to_in.ensure_face_map(), dst.span);
1776 }
1777 else {
1779 out_to_in.ensure_face_map(), material_remaps, meshes, mesh_offsets, dst.span);
1780 }
1781 dst.finish();
1782 }
1783
1784 interpolate_corner_attributes(output_attrs,
1785 join_attrs,
1786 mesh,
1787 joined_mesh,
1788 out_to_in.ensure_corner_map(),
1789 out_to_in.ensure_face_map());
1790
1791 if (r_intersecting_edges != nullptr) {
1792 get_intersecting_edges(r_intersecting_edges, mesh, out_to_in, mesh_offsets);
1793 }
1794 }
1795
1796 mesh->tag_loose_verts_none();
1797 mesh->tag_overlapping_none();
1798
1799 BLI_assert(bke::mesh_is_valid(*mesh));
1800
1801 return mesh;
1802}
1803
1805 const Span<float4x4> transforms,
1806 const Span<Array<short>> material_remaps,
1807 const BooleanOpParameters op_params,
1808 Vector<int> *r_intersecting_edges,
1809 BooleanError *r_error)
1810{
1811 constexpr int dbg_level = 0;
1812 if (dbg_level > 0) {
1813 std::cout << "\nMESH_BOOLEAN_MANIFOLD with " << meshes.size() << " args\n";
1814 }
1815 r_error->type = BooleanErrorType::NoError;
1816 try {
1817# ifdef DEBUG_TIME
1818 timeit::ScopedTimer timer("MANIFOLD BOOLEAN");
1819# endif
1820
1821 const int meshes_num = meshes.size();
1822
1823 bke::GeometrySet joined_meshes_set = join_meshes_with_transforms(meshes, transforms);
1824 const Mesh *joined_mesh = joined_meshes_set.get_mesh();
1825 if (joined_mesh == nullptr) {
1826 return nullptr;
1827 }
1828
1829 const MeshOffsets mesh_offsets(meshes);
1830 std::vector<Manifold> manifolds(meshes_num);
1831 get_manifolds(manifolds, meshes, transforms, mesh_offsets);
1832
1833 MeshGL meshgl_result;
1834 Operation op = op_params.boolean_mode;
1835 if (std::any_of(manifolds.begin(),
1836 manifolds.end(),
1837 [](const Manifold &m) { return m.Status() != Manifold::Error::NoError; }))
1838 {
1839 /* Check special case of subtracting a plane, which Manifold can handle. */
1840 float3 normal;
1841 float origin_offset;
1842 if (meshes_num == 2 && op == Operation::Difference &&
1843 manifolds[0].Status() == Manifold::Error::NoError &&
1844 is_plane(meshes[1], transforms[1], &normal, &origin_offset))
1845 {
1846# ifdef DEBUG_TIME
1847 timeit::ScopedTimer timer_trim("DOING BOOLEAN SLICE, GETTING MESH_GL RESULT");
1848# endif
1849 meshgl_result = mesh_trim_manifold(
1850 manifolds[0], normal, origin_offset, mesh_offsets, r_error);
1851 if (r_error->type != BooleanErrorType::NoError) {
1852 return nullptr;
1853 }
1854 }
1855 else {
1856 for (int i = 0; i < manifolds.size(); i++) {
1857 if (manifolds[i].Status() == Manifold::Error::NotManifold) {
1858 r_error->type = BooleanErrorType::NonManifold;
1859 r_error->non_manifold_mesh_indices.append(i);
1860 }
1861 }
1862
1863 if (r_error->non_manifold_mesh_indices.is_empty()) {
1864 r_error->type = BooleanErrorType::UnknownError;
1865 }
1866 return nullptr;
1867 }
1868 }
1869 else {
1870 manifold::OpType mop = op == Operation::Intersect ?
1871 manifold::OpType::Intersect :
1872 (op == Operation::Union ? manifold::OpType::Add :
1873 manifold::OpType::Subtract);
1874# ifdef DEBUG_TIME
1875 timeit::ScopedTimer timer_bool("DOING BOOLEAN, GETTING MESH_GL RESULT");
1876# endif
1877 Manifold man_result = Manifold::BatchBoolean(manifolds, mop);
1878 meshgl_result = man_result.GetMeshGL();
1879 /* Have to wait until after converting to MeshGL to check status. */
1880 if (man_result.Status() != Manifold::Error::NoError) {
1881 if (man_result.Status() == Manifold::Error::ResultTooLarge) {
1882 r_error->type = BooleanErrorType::ResultTooBig;
1883 }
1884 else {
1885 r_error->type = BooleanErrorType::UnknownError;
1886 }
1887 if (dbg_level > 0) {
1888 std::cout << "manifold boolean returned with error status\n";
1889 }
1890 return nullptr;
1891 }
1892 }
1893 if (dbg_level > 0) {
1894 std::cout << "boolean result has " << meshgl_result.NumTri() << " tris\n";
1895 dump_meshgl(meshgl_result, "boolean result meshgl");
1896 if (dbg_level > 1) {
1897 dump_meshgl_as_obj(meshgl_result);
1898 }
1899 }
1900 clean_meshgl(meshgl_result);
1901 Mesh *mesh_result;
1902 {
1903# ifdef DEBUG_TIME
1904 timeit::ScopedTimer timer_out("MESHGL RESULT TO MESH");
1905# endif
1906 mesh_result = meshgl_to_mesh(
1907 meshgl_result, joined_mesh, meshes, material_remaps, mesh_offsets, r_intersecting_edges);
1908 }
1909 return mesh_result;
1910 }
1911 catch (const std::exception &e) {
1912 std::cout << "mesh_boolean_manifold: exception: " << e.what() << "\n";
1913 }
1914 catch (...) {
1915 std::cout << "mesh_boolean_manifold: unknown exception\n";
1916 }
1917 r_error->type = BooleanErrorType::UnknownError;
1918 return nullptr;
1919}
1920
1921} // namespace blender::geometry::boolean
1922
1923#endif // WITH_MANIFOLD
#define ATTR_DOMAIN_NUM
support for deformation groups and hooks.
#define BLI_assert_unreachable()
#define BLI_assert(a)
#define ELEM(...)
SIMD_FORCE_INLINE btVector3 transform(const btVector3 &point) const
void init()
AttributeSet attributes
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr const T * end() const
Definition BLI_span.hh:228
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr const T * begin() const
Definition BLI_span.hh:224
constexpr IndexRange()=default
constexpr MutableSpan()=default
MatBase< 4, 4 > float4x4
unsigned int uchar
VecBase< int, 2 > int2
VecBase< float, 3 > float3
void copy(const GVArray &src, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
void vert_tris_from_corner_tris(Span< int > corner_verts, Span< int3 > corner_tris, MutableSpan< int3 > vert_tris)
constexpr ParallelGrainSize grain_size(int grain_size)
void copy_attribute_using_map(GSpan src, Span< int > out_to_in_map, GMutableSpan dst)
int mesh_id_for_face(int face_id, const MeshOffsets &mesh_offsets)
Mesh * mesh_boolean_manifold(Span< const Mesh * > meshes, Span< float4x4 > transforms, Span< Array< short > > material_remaps, BooleanOpParameters op_params, Vector< int > *r_intersecting_edges, BooleanError *r_error)
void interpolate_corner_attributes(bke::MutableAttributeAccessor output_attrs, bke::AttributeAccessor input_attrs, Mesh *output_mesh, const Mesh *input_mesh, Span< int > out_to_in_corner_map, Span< int > out_to_in_face_map)
IndexRange vertex_range_for_face(int face_id, const MeshOffsets &mesh_offsets)
void set_material_from_map(Span< int > out_to_in_map, Span< Array< short > > material_remaps, Span< const Mesh * > meshes, const MeshOffsets &mesh_offsets, MutableSpan< int > dst)
bke::GeometrySet join_meshes_with_transforms(Span< const Mesh * > meshes, Span< float4x4 > transforms)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
Mesh * BKE_mesh_copy_for_eval(const Mesh &source)
void mul_v3_m4v3(float r[3], const float mat[4][4], const float vec[3])
ATTR_WARN_UNUSED_RESULT const BMVert * v
void BKE_mesh_copy_parameters_for_eval(Mesh *me_dst, const Mesh *me_src)
unsigned int uint32_t
Definition BKE_text.h:81
VecBase< float, 2 > float2
VecBase< int32_t, 3 > int3
Mesh * BKE_mesh_new_nomain(int verts_num, int edges_num, int faces_num, int corners_num)
void BKE_id_free(Main *bmain, void *idv)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
VecBase< float, 3 > float3
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
signed char int8_t
Definition BKE_text.h:76
ustring name
Definition graph/node.h:178