Blender V5.3
geometry/intern/mesh_boolean.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2001-2002 NaN Holding BV. All rights reserved.
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <iostream>
10
11#include "BKE_attribute.hh"
13#include "BKE_attribute_math.hh"
14#include "BKE_geometry_set.hh"
15#include "BKE_instances.hh"
16#include "BKE_lib_id.hh"
17#include "BKE_mesh.hh"
18
19#include "BLI_array.hh"
20#include "BLI_array_utils.hh"
21#include "BLI_math_geom_c.hh"
22#include "BLI_math_matrix.hh"
23#include "BLI_math_matrix_c.hh"
24#include "BLI_math_vector_c.hh"
25#include "BLI_mesh_boolean.hh"
26#include "BLI_mesh_intersect.hh"
27#include "BLI_span.hh"
28#include "BLI_task.hh"
29#include "BLI_virtual_array.hh"
30
31#include "GEO_mesh_boolean.hh"
35
36#include "bmesh.hh"
38
39// #define BENCHMARK_TIME
40#ifdef BENCHMARK_TIME
41# include "BLI_threads.hh"
42# include "BLI_timeit.hh"
43# include <filesystem>
44# include <fstream>
45# define BENCHMARK_FILE "/tmp/blender_benchmark.csv"
46#endif
47
49
50/* -------------------------------------------------------------------- */
53
54#if defined(WITH_GMP) || defined(WITH_MANIFOLD)
55
56MeshOffsets::MeshOffsets(Span<const Mesh *> meshes)
57{
58 const int meshes_num = meshes.size();
59 this->vert_start.reinitialize(meshes_num + 1);
60 this->face_start.reinitialize(meshes_num + 1);
61 this->edge_start.reinitialize(meshes_num + 1);
62 this->corner_start.reinitialize(meshes_num + 1);
63 for (const int i : meshes.index_range()) {
64 this->vert_start[i] = meshes[i]->verts_num;
65 this->face_start[i] = meshes[i]->faces_num;
66 this->edge_start[i] = meshes[i]->edges_num;
67 this->corner_start[i] = meshes[i]->corners_num;
68 }
73}
74
75int mesh_id_for_face(const int face_id, const MeshOffsets &mesh_offsets)
76{
77 for (const int mesh_id : mesh_offsets.face_offsets.index_range()) {
78 if (mesh_offsets.face_offsets[mesh_id].contains(face_id)) {
79 return mesh_id;
80 }
81 }
82 return -1;
83}
84
85IndexRange vertex_range_for_face(const int face_id, const MeshOffsets &mesh_offsets)
86{
87 const int mesh_id = mesh_id_for_face(face_id, mesh_offsets);
88 if (mesh_id == -1) {
89 return IndexRange();
90 }
91 return IndexRange::from_begin_end(mesh_offsets.vert_start[mesh_id],
92 mesh_offsets.vert_start[mesh_id + 1]);
93}
94
95void copy_attribute_using_map(const GSpan src, const Span<int> out_to_in_map, GMutableSpan dst)
96{
97 const CPPType &type = dst.type();
98 IndexMaskMemory memory;
99 const IndexMask valid_mask = array_utils::indices_non_negative(
100 IndexRange(dst.size()), out_to_in_map, memory);
101 bke::attribute_math::gather(src, out_to_in_map, valid_mask, dst);
102 type.value_initialize_indices(dst.data(), valid_mask.complement(IndexRange(dst.size()), memory));
103}
104
109struct CornerInterpolation {
110 IndexMaskMemory memory;
112 IndexMask copy_mask;
114 IndexMask interp_mask;
116 Array<int> group_offsets;
117 Array<int> src_corners;
118 Array<float> weights;
121 Array<bool> flipped;
122};
123
124static void calc_corner_interpolation(const Mesh &output_mesh,
125 const Mesh &input_mesh,
126 const Span<int> out_to_in_corner_map,
127 const Span<int> out_to_in_face_map,
128 CornerInterpolation &r_interp)
129{
130 const OffsetIndices<int> output_faces = output_mesh.faces();
131 const OffsetIndices<int> input_faces = input_mesh.faces();
132 const Span<int> input_corner_verts = input_mesh.corner_verts();
133 const Span<float3> input_vert_positions = input_mesh.vert_positions();
134 const Span<int> output_corner_verts = output_mesh.corner_verts();
135 const Span<float3> output_vert_positions = output_mesh.vert_positions();
136
137 /* Count the interpolated corners and their weights per face to allocate flat arrays. */
138 Array<int> interp_corner_offsets_data(output_faces.size() + 1);
139 Array<int> weight_offsets_data(output_faces.size() + 1);
140 threading::parallel_for(output_faces.index_range(), 4096, [&](const IndexRange range) {
141 for (const int out_face : range) {
142 const Span<int> face_map = out_to_in_corner_map.slice(output_faces[out_face]);
143 const int interp_num = std::count(face_map.begin(), face_map.end(), -1);
144 const int in_face_size = input_faces[out_to_in_face_map[out_face]].size();
145 interp_corner_offsets_data[out_face] = interp_num;
146 weight_offsets_data[out_face] = interp_num * in_face_size;
147 }
148 });
149 const OffsetIndices<int> interp_corner_offsets = offset_indices::accumulate_counts_to_offsets(
150 interp_corner_offsets_data);
151 const OffsetIndices<int> weight_offsets = offset_indices::accumulate_counts_to_offsets(
152 weight_offsets_data);
153
154 Array<int> interp_corners(interp_corner_offsets.total_size());
155 r_interp.group_offsets.reinitialize(interp_corner_offsets.total_size() + 1);
156 r_interp.flipped.reinitialize(interp_corner_offsets.total_size());
157 r_interp.src_corners.reinitialize(weight_offsets.total_size());
158 r_interp.weights.reinitialize(weight_offsets.total_size());
159
160 /* Loop per output face, as there is an expensive calculation that needs to be done per face. */
161 threading::parallel_for(output_faces.index_range(), 256, [&](const IndexRange range) {
162 Vector<float2, 20> cos_2d;
163 for (const int out_face_index : range) {
164 const IndexRange interp_range = interp_corner_offsets[out_face_index];
165 if (interp_range.is_empty()) {
166 continue;
167 }
168 const int in_face_index = out_to_in_face_map[out_face_index];
169 const IndexRange in_face = input_faces[in_face_index];
170 const IndexRange out_face = output_faces[out_face_index];
171
172 /* First get coordinates of input face projected onto 2d. */
173 const Span<int> in_face_verts = input_corner_verts.slice(in_face);
174 const int in_face_size = in_face.size();
175 const Span<int> out_face_verts = output_corner_verts.slice(out_face);
176 cos_2d.resize(in_face_size);
177 float (*cos_2d_p)[2] = reinterpret_cast<float (*)[2]>(cos_2d.data());
178 const float3 axis_dominant = bke::mesh::face_normal_calc(input_vert_positions,
179 in_face_verts);
180 float3x3 axis_mat;
181 axis_dominant_v3_to_m3(axis_mat.ptr(), axis_dominant);
182 /* We also need to know if the output face has a flipped normal compared
183 * to the corresponding input face (used if we have custom normals).
184 */
185 const float3 out_face_normal = bke::mesh::face_normal_calc(output_vert_positions,
186 out_face_verts);
187 const bool face_is_flipped = math::dot(axis_dominant, out_face_normal) < 0.0;
188 for (const int i : in_face_verts.index_range()) {
189 const float3 &co = input_vert_positions[in_face_verts[i]];
190 cos_2d[i] = (axis_mat * co).xy();
191 }
192
193 const int weights_start = weight_offsets[out_face_index].start();
194 int interp_i = 0;
195 for (const int out_c : out_face) {
196 if (out_to_in_corner_map[out_c] != -1) {
197 continue;
198 }
199 const int corner_i = interp_range[interp_i];
200 const IndexRange group(weights_start + interp_i * in_face_size, in_face_size);
201 interp_corners[corner_i] = out_c;
202 r_interp.group_offsets[corner_i] = group.start();
203 r_interp.flipped[corner_i] = face_is_flipped;
204 array_utils::fill_index_range<int>(r_interp.src_corners.as_mutable_span().slice(group),
205 in_face.start());
206
207 const int out_v = output_corner_verts[out_c];
208 float2 co;
209 mul_v2_m3v3(co, axis_mat.ptr(), output_vert_positions[out_v]);
210 interp_weights_poly_v2(&r_interp.weights[group.start()], cos_2d_p, in_face_size, co);
211 interp_i++;
212 }
213 }
214 });
215 r_interp.group_offsets.last() = weight_offsets.total_size();
216
217 r_interp.interp_mask = IndexMask::from_indices(interp_corners.as_span(), r_interp.memory);
218 r_interp.copy_mask = r_interp.interp_mask.complement(IndexRange(out_to_in_corner_map.size()),
219 r_interp.memory);
220}
221
222void interpolate_corner_attributes(bke::MutableAttributeAccessor output_attrs,
223 const bke::AttributeAccessor input_attrs,
224 Mesh *output_mesh,
225 const Mesh *input_mesh,
226 const Span<int> out_to_in_corner_map,
227 const Span<int> out_to_in_face_map)
228{
229# ifdef DEBUG_TIME
230 timeit::ScopedTimer timer("interpolate corner attributes");
231# endif
232 /* Only calculated when there is an attribute to interpolate. */
233 std::optional<CornerInterpolation> interp;
234
235 input_attrs.foreach_attribute([&](const bke::AttributeIter &iter) {
236 if (iter.domain != bke::AttrDomain::Corner || ELEM(iter.name, ".corner_vert", ".corner_edge"))
237 {
238 return;
239 }
240 const bke::GAttributeReader reader = iter.get();
241 if (!reader) {
242 return;
243 }
244
245 const CommonVArrayInfo info = reader.varray.common_info();
246 if (info.type == CommonVArrayInfo::Type::Single) {
247 const bke::AttributeInitValue init(GPointer(reader.varray.type(), info.data));
248 output_attrs.add(iter.name, iter.domain, iter.data_type, init);
249 return;
250 }
251
252 if (!interp) {
253 interp.emplace();
254 calc_corner_interpolation(
255 *output_mesh, *input_mesh, out_to_in_corner_map, out_to_in_face_map, *interp);
256 }
257
258 bke::GSpanAttributeWriter dst = output_attrs.lookup_or_add_for_write_only_span(
259 iter.name, iter.domain, iter.data_type);
260 const GVArraySpan src(*reader);
261 bke::attribute_math::gather(src, out_to_in_corner_map, interp->copy_mask, dst.span);
263 OffsetIndices<int>(interp->group_offsets),
264 interp->src_corners,
265 interp->weights.as_span(),
266 interp->interp_mask,
267 dst.span);
268 if (iter.name == "custom_normal" && dst.span.type().is<float3>()) {
269 /* The joined mesh has converted custom normals to float3. */
270 MutableSpan<float3> normals = dst.span.typed<float3>();
271 interp->interp_mask.foreach_index(
272 [&](const int corner, const int pos) {
273 if (interp->flipped[pos]) {
274 normals[corner] = -normals[corner];
275 }
276 },
278 }
279 dst.finish();
280 });
281}
282
283void set_material_from_map(const Span<int> out_to_in_map,
284 const Span<Array<short>> material_remaps,
285 const Span<const Mesh *> meshes,
286 const MeshOffsets &mesh_offsets,
287 const MutableSpan<int> dst)
288{
289 BLI_assert(material_remaps.size() > 0);
290 Array<VArray<int>> material_varrays(meshes.size());
291 for (const int i : meshes.index_range()) {
292 bke::AttributeAccessor input_attrs = meshes[i]->attributes();
293 material_varrays[i] = *input_attrs.lookup_or_default<int>(
294 "material_index", bke::AttrDomain::Face, 0);
295 }
296 threading::parallel_for(out_to_in_map.index_range(), 8192, [&](const IndexRange range) {
297 for (const int out_f : range) {
298 const int in_f = out_to_in_map[out_f];
299 const int mesh_id = mesh_id_for_face(in_f, mesh_offsets);
300 const int in_f_local = in_f - mesh_offsets.face_start[mesh_id];
301 const int orig = material_varrays[mesh_id][in_f_local];
302 const Array<short> &map = material_remaps[mesh_id];
303 dst[out_f] = (orig >= 0 && orig < map.size()) ? map[orig] : orig;
304 }
305 });
306}
307
308bke::GeometrySet join_meshes_with_transforms(const Span<const Mesh *> meshes,
309 const Span<float4x4> transforms)
310{
311# ifdef DEBUG_TIME
312 timeit::ScopedTimer jtimer(__func__);
313# endif
314 bke::Instances instances;
315 instances.resize(meshes.size());
316 instances.transforms_for_write().copy_from(transforms);
317 MutableSpan<int> handles = instances.reference_handles_for_write();
318
319 Map<const Mesh *, int> handle_by_mesh;
320 for (const int i : meshes.index_range()) {
321 handles[i] = handle_by_mesh.lookup_or_add_cb(meshes[i], [&]() {
322 bke::GeometrySet geometry = bke::GeometrySet::from_mesh(
323 const_cast<Mesh *>(meshes[i]), bke::GeometryOwnershipType::ReadOnly);
324 return instances.add_new_reference(std::move(geometry));
325 });
326 }
329 geometry::RealizeInstancesOptions())
330 .geometry;
331}
332
333#endif /* WITH_GMP || WITH_MANIFOLD */
334
336
337/* -------------------------------------------------------------------- */
340
341#ifdef WITH_GMP
342
343constexpr int estimated_max_facelen = 100; /* Used for initial size of some Vectors. */
344
345/* Snap entries that are near 0 or 1 or -1 to those values.
346 * Sometimes Blender's rotation matrices for multiples of 90 degrees have
347 * tiny numbers where there should be zeros. That messes makes some things
348 * every so slightly non-coplanar when users expect coplanarity,
349 * so this is a hack to clean up such matrices.
350 * Would be better to change the transformation code itself.
351 */
352static float4x4 clean_transform(const float4x4 &mat)
353{
354 float4x4 cleaned;
355 const float fuzz = 1e-6f;
356 for (int i = 0; i < 4; i++) {
357 for (int j = 0; j < 4; j++) {
358 float f = mat[i][j];
359 if (fabsf(f) <= fuzz) {
360 f = 0.0f;
361 }
362 else if (fabsf(f - 1.0f) <= fuzz) {
363 f = 1.0f;
364 }
365 else if (fabsf(f + 1.0f) <= fuzz) {
366 f = -1.0f;
367 }
368 cleaned[i][j] = f;
369 }
370 }
371 return cleaned;
372}
373
374static float3 clean_float3(const float3 &co)
375{
376 float3 cleaned = co;
377 if (!isfinite(co[0])) [[unlikely]] {
378 cleaned[0] = 0.0f;
379 }
380 if (!isfinite(co[1])) [[unlikely]] {
381 cleaned[1] = 0.0f;
382 }
383 if (!isfinite(co[2])) [[unlikely]] {
384 cleaned[2] = 0.0f;
385 }
386 return cleaned;
387}
388
389/* `MeshesToIMeshInfo` keeps track of information used when combining a number
390 * of `Mesh`es into a single `IMesh` for doing boolean on.
391 * Mostly this means keeping track of the index offsets for various mesh elements. */
392class MeshesToIMeshInfo {
393 public:
394 /* The input meshes, */
395 Span<const Mesh *> meshes;
396 MeshOffsets mesh_offsets;
398 const Mesh *joined_mesh;
399 /* For each Mesh vertex in all the meshes (with concatenated indexing),
400 * what is the IMesh Vert* allocated for it in the input IMesh? */
401 Array<const meshintersect::Vert *> mesh_to_imesh_vert;
402 /* Similarly for each Mesh face. */
403 Array<meshintersect::Face *> mesh_to_imesh_face;
404 /* Transformation matrix to transform a coordinate in the corresponding
405 * Mesh to the local space of the first Mesh. */
406 Array<float4x4> to_target_transform;
407 /* For each input mesh, whether or not their transform is negative. */
408 Array<bool> has_negative_transform;
409 /* For each input mesh, how to remap the material slot numbers to
410 * the material slots in the first mesh. */
411 Span<Array<short>> material_remaps;
412
413 MeshesToIMeshInfo(Span<const Mesh *> meshes) : mesh_offsets(meshes) {}
414
415 int input_mesh_for_imesh_vert(int imesh_v) const;
416 int input_mesh_for_imesh_edge(int imesh_e) const;
417 int input_mesh_for_imesh_face(int imesh_f) const;
418};
419
420/* Given an index `imesh_v` in the `IMesh`, return the index of the
421 * input `Mesh` that contained the vertex that it came from. */
422int MeshesToIMeshInfo::input_mesh_for_imesh_vert(int imesh_v) const
423{
424 const Span<int> offsets = this->mesh_offsets.vert_offsets.data();
425 int n = int(offsets.size());
426 for (int i = 0; i < n - 1; ++i) {
427 if (imesh_v < offsets[i + 1]) {
428 return i;
429 }
430 }
431 return n - 1;
432}
433
434/* Given an index `imesh_e` used as an original index in the `IMesh`,
435 * return the index of the input `Mesh` that contained the vertex that it came from. */
436int MeshesToIMeshInfo::input_mesh_for_imesh_edge(int imesh_e) const
437{
438 const Span<int> offsets = this->mesh_offsets.edge_offsets.data();
439 int n = int(offsets.size());
440 for (int i = 0; i < n - 1; ++i) {
441 if (imesh_e < offsets[i + 1]) {
442 return i;
443 }
444 }
445 return n - 1;
446}
447
448/* Given an index `imesh_f` in the `IMesh`, return the index of the
449 * input `Mesh` that contained the face that it came from. */
450int MeshesToIMeshInfo::input_mesh_for_imesh_face(int imesh_f) const
451{
452 const Span<int> offsets = this->mesh_offsets.face_offsets.data();
453 int n = int(offsets.size());
454 for (int i = 0; i < n - 1; ++i) {
455 if (imesh_f < offsets[i + 1]) {
456 return i;
457 }
458 }
459 return n - 1;
460}
461
474static meshintersect::IMesh meshes_to_imesh(Span<const Mesh *> meshes,
475 Span<float4x4> transforms,
476 Span<Array<short>> material_remaps,
477 meshintersect::IMeshArena &arena,
478 MeshesToIMeshInfo *r_info)
479{
480 int nmeshes = meshes.size();
481 BLI_assert(nmeshes > 0);
482 r_info->meshes = meshes;
483 const int totvert = r_info->mesh_offsets.vert_offsets.total_size();
484 const int faces_num = r_info->mesh_offsets.face_offsets.total_size();
485
486 /* Estimate the number of vertices and faces in the boolean output,
487 * so that the memory arena can reserve some space. It is OK if these
488 * estimates are wrong. */
489 const int estimate_num_outv = 3 * totvert;
490 const int estimate_num_outf = 4 * faces_num;
491 arena.reserve(estimate_num_outv, estimate_num_outf);
492 r_info->mesh_to_imesh_vert.reinitialize(totvert);
493 r_info->mesh_to_imesh_face.reinitialize(faces_num);
494 r_info->to_target_transform.reinitialize(nmeshes);
495 r_info->has_negative_transform.reinitialize(nmeshes);
496 r_info->material_remaps = material_remaps;
497 int v = 0;
498 int e = 0;
499 int f = 0;
500
501 /* Put these Vectors here, with a size unlikely to need resizing,
502 * so that the loop to make new Faces will likely not need to allocate
503 * over and over. */
506
507 /* To convert the coordinates of meshes 1, 2, etc. into the local space
508 * of the target, multiply each transform by the inverse of the
509 * target matrix. Exact Boolean works better if these matrices are 'cleaned'
510 * -- see the comment for the `clean_transform` function, above. */
511
512 /* For each input `Mesh`, make `Vert`s and `Face`s for the corresponding
513 * vertices and polygons, and keep track of the original indices (using the
514 * concatenating offset scheme) inside the `Vert`s and `Face`s.
515 * When making `Face`s, we also put in the original indices for edges that
516 * make up the polygons using the same scheme. */
517 for (int mi : meshes.index_range()) {
518 const Mesh *mesh = meshes[mi];
519 /* Get matrix that transforms a coordinate in meshes[mi]'s local space
520 * to the target space. */
521 r_info->to_target_transform[mi] = transforms.is_empty() ? float4x4::identity() :
522 clean_transform(transforms[mi]);
523 r_info->has_negative_transform[mi] = math::is_negative(r_info->to_target_transform[mi]);
524
525 /* All meshes 1 and up will be transformed into the local space of operand 0.
526 * Historical behavior of the modifier has been to flip the faces of any meshes
527 * that would have a negative transform if you do that. */
528 bool need_face_flip = r_info->has_negative_transform[mi] != r_info->has_negative_transform[0];
529
530 Vector<meshintersect::Vert *> verts(mesh->verts_num);
531 const Span<float3> vert_positions = mesh->vert_positions();
532 const OffsetIndices faces = mesh->faces();
533 const Span<int> corner_verts = mesh->corner_verts();
534 const Span<int> corner_edges = mesh->corner_edges();
535
536 /* Allocate verts
537 * Skip the matrix multiplication for each point when there is no transform for a mesh,
538 * for example when the first mesh is already in the target space. (Note the logic
539 * directly above, which uses an identity matrix with an empty input transform). */
540 if (transforms.is_empty() || r_info->to_target_transform[mi] == float4x4::identity()) {
541 threading::parallel_for(vert_positions.index_range(), 2048, [&](IndexRange range) {
542 for (int i : range) {
543 float3 co = clean_float3(vert_positions[i]);
544 mpq3 mco = mpq3(co.x, co.y, co.z);
545 double3 dco(mco[0].get_d(), mco[1].get_d(), mco[2].get_d());
546 verts[i] = new meshintersect::Vert(mco, dco, meshintersect::NO_INDEX, i);
547 }
548 });
549 }
550 else {
551 threading::parallel_for(vert_positions.index_range(), 2048, [&](IndexRange range) {
552 for (int i : range) {
553 float3 co = math::transform_point(r_info->to_target_transform[mi],
554 clean_float3(vert_positions[i]));
555 mpq3 mco = mpq3(co.x, co.y, co.z);
556 double3 dco(mco[0].get_d(), mco[1].get_d(), mco[2].get_d());
557 verts[i] = new meshintersect::Vert(mco, dco, meshintersect::NO_INDEX, i);
558 }
559 });
560 }
561 for (int i : vert_positions.index_range()) {
562 r_info->mesh_to_imesh_vert[v] = arena.add_or_find_vert(verts[i]);
563 ++v;
564 }
565
566 for (const int face_i : faces.index_range()) {
567 const IndexRange face = faces[face_i];
568 int flen = face.size();
569 face_vert.resize(flen);
570 face_edge_orig.resize(flen);
571 for (int i = 0; i < flen; ++i) {
572 const int corner_i = face[i];
573 int mverti = r_info->mesh_offsets.vert_offsets[mi][corner_verts[corner_i]];
574 const meshintersect::Vert *fv = r_info->mesh_to_imesh_vert[mverti];
575 if (need_face_flip) {
576 face_vert[flen - i - 1] = fv;
577 int iedge = i < flen - 1 ? flen - i - 2 : flen - 1;
578 face_edge_orig[iedge] = e + corner_edges[corner_i];
579 }
580 else {
581 face_vert[i] = fv;
582 face_edge_orig[i] = e + corner_edges[corner_i];
583 }
584 }
585 r_info->mesh_to_imesh_face[f] = arena.add_face(face_vert, f, face_edge_orig);
586 ++f;
587 }
588 e += mesh->edges_num;
589 }
590 return meshintersect::IMesh(r_info->mesh_to_imesh_face);
591}
592
603static int fill_orig_loops(const meshintersect::Face *f,
604 const IndexRange orig_face,
605 const Span<int> orig_corner_verts,
606 int orig_me_index,
607 MeshesToIMeshInfo &mim,
608 MutableSpan<int> r_orig_loops)
609{
610 r_orig_loops.fill(-1);
611 const IndexRange orig_mesh_verts_range = mim.mesh_offsets.vert_offsets[orig_me_index];
612
613 int orig_mplen = orig_face.size();
614 if (f->size() != orig_mplen) {
615 return 0;
616 }
617 BLI_assert(r_orig_loops.size() == orig_mplen);
618 /* We'll look for the case where the first vertex in f has an original vertex
619 * that is the same as one in orig_me (after correcting for offset in mim meshes).
620 * Then see that loop and any subsequent ones have the same start and end vertex.
621 * This may miss some cases of partial alignment, but that's OK since discovering
622 * aligned loops is only an optimization to avoid some re-interpolation.
623 */
624 int first_orig_v = f->vert[0]->orig;
625 if (first_orig_v == meshintersect::NO_INDEX) {
626 return 0;
627 }
628 /* It is possible that the original vert was merged with another in another mesh. */
629 if (orig_me_index != mim.input_mesh_for_imesh_vert(first_orig_v)) {
630 return 0;
631 }
632 /* Assume all vertices in each face is unique. */
633 int offset = -1;
634 for (int i = 0; i < orig_mplen; ++i) {
635 int loop_i = i + orig_face.start();
636 if (orig_corner_verts[loop_i] == first_orig_v) {
637 offset = i;
638 break;
639 }
640 }
641 if (offset == -1) {
642 return 0;
643 }
644 int num_orig_loops_found = 0;
645 for (int mp_loop_index = 0; mp_loop_index < orig_mplen; ++mp_loop_index) {
646 int orig_mp_loop_index = (mp_loop_index + offset) % orig_mplen;
647 const int vert_i = orig_corner_verts[orig_face.start() + orig_mp_loop_index];
648 int fv_orig = f->vert[mp_loop_index]->orig;
649 if (fv_orig != meshintersect::NO_INDEX) {
650 if (!orig_mesh_verts_range.contains(fv_orig)) {
651 fv_orig = meshintersect::NO_INDEX;
652 }
653 }
654 if (vert_i == fv_orig) {
655 const int vert_next =
656 orig_corner_verts[orig_face.start() + ((orig_mp_loop_index + 1) % orig_mplen)];
657 int fvnext_orig = f->vert[(mp_loop_index + 1) % orig_mplen]->orig;
658 if (fvnext_orig != meshintersect::NO_INDEX) {
659 if (!orig_mesh_verts_range.contains(fvnext_orig)) {
660 fvnext_orig = meshintersect::NO_INDEX;
661 }
662 }
663 if (vert_next == fvnext_orig) {
664 r_orig_loops[mp_loop_index] = orig_face.start() + orig_mp_loop_index;
665 ++num_orig_loops_found;
666 }
667 }
668 }
669 return num_orig_loops_found;
670}
671
672/* For the loops of `face`, see if the face is unchanged from `orig_face`, and if so,
673 * copy the Loop attributes from corresponding loops to corresponding loops.
674 * Otherwise, interpolate the Loop attributes in the face `orig_face`. */
675static void copy_or_interp_loop_attributes(const meshintersect::IMesh *im,
676 Mesh *dest_mesh,
677 const Span<int> dst_to_src_face_map,
678 MeshesToIMeshInfo &mim)
679{
680 const OffsetIndices<int> src_faces = mim.joined_mesh->faces();
681 const Span<int> orig_corner_verts = mim.joined_mesh->corner_verts();
682 const OffsetIndices<int> dst_faces = dest_mesh->faces();
683
684 Array<int> dst_to_src_corner_map(dst_faces.total_size());
685 for (const int face : dst_faces.index_range()) {
686 const meshintersect::Face *f = im->face(face);
687 const int mesh_index = mesh_id_for_face(f->orig, mim.mesh_offsets);
688 fill_orig_loops(f,
689 src_faces[f->orig],
690 orig_corner_verts,
691 mesh_index,
692 mim,
693 dst_to_src_corner_map.as_mutable_span().slice(dst_faces[face]));
694 }
695
696 interpolate_corner_attributes(dest_mesh->attributes_for_write(),
697 mim.joined_mesh->attributes(),
698 dest_mesh,
699 mim.joined_mesh,
700 dst_to_src_corner_map,
701 dst_to_src_face_map);
702}
703
704static void gather_attributes_with_check(const bke::AttributeAccessor src_attributes,
705 const bke::AttrDomain src_domain,
706 const bke::AttrDomain dst_domain,
707 const bke::AttributeFilter &attribute_filter,
708 const Span<int> dst_to_src_map,
709 bke::MutableAttributeAccessor dst_attributes)
710{
711 src_attributes.foreach_attribute([&](const bke::AttributeIter &iter) {
712 if (iter.domain != src_domain) {
713 return;
714 }
715 if (iter.data_type == bke::AttrType::String) {
716 return;
717 }
718 if (attribute_filter.allow_skip(iter.name)) {
719 return;
720 }
721 const bke::GAttributeReader src = iter.get(src_domain);
722 const CommonVArrayInfo info = src.varray.common_info();
723 if (info.type == CommonVArrayInfo::Type::Single) {
724 const bke::AttributeInitValue init(GPointer(src.varray.type(), info.data));
725 dst_attributes.add(iter.name, iter.domain, iter.data_type, init);
726 return;
727 }
728 bke::GSpanAttributeWriter dst = dst_attributes.lookup_or_add_for_write_only_span(
729 iter.name, dst_domain, iter.data_type);
730 if (!dst) {
731 return;
732 }
733 copy_attribute_using_map(GVArraySpan(*src), dst_to_src_map, dst.span);
734 dst.finish();
735 });
736}
737
742static Mesh *imesh_to_mesh(meshintersect::IMesh *im, MeshesToIMeshInfo &mim)
743{
744 constexpr int dbg_level = 0;
745
746 im->populate_vert();
747 int out_totvert = im->vert_size();
748 int out_faces_num = im->face_size();
749 int out_totloop = 0;
750 for (const meshintersect::Face *f : im->faces()) {
751 out_totloop += f->size();
752 }
753 /* Will calculate edges later. */
754 Mesh *result = BKE_mesh_new_nomain(out_totvert, 0, out_faces_num, out_totloop);
756 bke::MutableAttributeAccessor dst_attributes = result->attributes_for_write();
757
758 static_assert(meshintersect::NO_INDEX == -1);
759
760 /* Set the vertex coordinate values and other data. */
761 MutableSpan<float3> positions = result->vert_positions_for_write();
762 threading::parallel_for(im->vert_index_range(), 4096, [&](const IndexRange range) {
763 for (const int vert : range) {
764 const meshintersect::Vert *v = im->vert(vert);
765 copy_v3fl_v3db(positions[vert], v->co);
766 }
767 });
768
769 {
770 Array<int> dst_to_src_vert(out_totvert);
771 threading::parallel_for(positions.index_range(), 4096, [&](const IndexRange range) {
772 for (const int vert : range) {
773 const meshintersect::Vert *v = im->vert(vert);
774 dst_to_src_vert[vert] = v->orig;
775 }
776 });
777 gather_attributes_with_check(mim.joined_mesh->attributes(),
781 dst_to_src_vert,
782 dst_attributes);
783 }
784
785 {
786 OffsetIndices<int> dst_faces;
787 if (out_faces_num != 0) {
788 MutableSpan<int> face_offsets = result->face_offsets_for_write();
789 threading::parallel_for(im->face_index_range(), 4096, [&](const IndexRange range) {
790 for (const int face : range) {
791 const meshintersect::Face *f = im->face(face);
792 face_offsets[face] = f->size();
793 }
794 });
795 dst_faces = offset_indices::accumulate_counts_to_offsets(face_offsets);
796 }
797
798 MutableSpan<int> dst_corner_verts = result->corner_verts_for_write();
799 threading::parallel_for(im->face_index_range(), 4096, [&](const IndexRange range) {
800 for (const int face : range) {
801 const meshintersect::Face *f = im->face(face);
802 MutableSpan<int> face_verts = dst_corner_verts.slice(dst_faces[face]);
803 for (const int i : face_verts.index_range()) {
804 face_verts[i] = im->lookup_vert(f->vert[i]);
805 }
806 }
807 });
808
809 Array<int> dst_to_src_face(out_faces_num);
810 threading::parallel_for(im->face_index_range(), 4096, [&](const IndexRange range) {
811 for (const int face : range) {
812 const meshintersect::Face *f = im->face(face);
813 dst_to_src_face[face] = f->orig;
814 }
815 });
816 gather_attributes_with_check(mim.joined_mesh->attributes(),
819 bke::attribute_filter_from_skip_ref({"material_index"}),
820 dst_to_src_face,
821 dst_attributes);
822
823 if (mim.joined_mesh->attributes().contains("material_index")) {
824 bke::SpanAttributeWriter dst_indices = dst_attributes.lookup_or_add_for_write_only_span<int>(
825 "material_index", bke::AttrDomain::Face);
826 if (mim.material_remaps.is_empty()) {
827 const VArraySpan src = *mim.joined_mesh->attributes().lookup<int>("material_index");
828 copy_attribute_using_map(src, dst_to_src_face, dst_indices.span);
829 }
830 else {
832 dst_to_src_face, mim.material_remaps, mim.meshes, mim.mesh_offsets, dst_indices.span);
833 }
834 dst_indices.finish();
835 }
836
837 copy_or_interp_loop_attributes(im, result, dst_to_src_face, mim);
838 }
839
840 bke::mesh_calc_edges(*result, false, false);
841
842 {
843 Array<int> dst_to_src_edge(result->edges_num, -1);
844 const OffsetIndices dst_polys = result->faces();
845 const Span<int> dst_corner_edges = result->corner_edges();
846 for (int fi : im->face_index_range()) {
847 const meshintersect::Face *f = im->face(fi);
848 const IndexRange face = dst_polys[fi];
849 for (int j : f->index_range()) {
850 if (f->edge_orig[j] != meshintersect::NO_INDEX) {
851 dst_to_src_edge[dst_corner_edges[face[j]]] = f->edge_orig[j];
852 }
853 }
854 }
855 gather_attributes_with_check(mim.joined_mesh->attributes(),
859 dst_to_src_edge,
860 dst_attributes);
861 }
862
863 if (dbg_level > 0) {
865 }
866 return result;
867}
868
869static meshintersect::BoolOpType operation_to_mesh_arr_mode(const Operation operation)
870{
871 switch (operation) {
872 case Operation::Intersect:
873 return meshintersect::BoolOpType::Intersect;
874 case Operation::Union:
875 return meshintersect::BoolOpType::Union;
876 case Operation::Difference:
877 return meshintersect::BoolOpType::Difference;
878 }
880 return meshintersect::BoolOpType::None;
881}
882
883static Mesh *mesh_boolean_mesh_arr(Span<const Mesh *> meshes,
884 Span<float4x4> transforms,
885 Span<Array<short>> material_remaps,
886 const bool use_self,
887 const bool hole_tolerant,
888 const meshintersect::BoolOpType boolean_mode,
889 Vector<int> *r_intersecting_edges)
890{
891 BLI_assert(transforms.is_empty() || meshes.size() == transforms.size());
892 BLI_assert(material_remaps.is_empty() || material_remaps.size() == meshes.size());
893 if (meshes.size() <= 0) {
894 return nullptr;
895 }
896
897 bke::GeometrySet joined_meshes_set = join_meshes_with_transforms(meshes, transforms);
898 const Mesh *joined_mesh = joined_meshes_set.get_mesh();
899 if (!joined_mesh) {
900 return nullptr;
901 }
902
903 const int dbg_level = 0;
904 if (dbg_level > 0) {
905 std::cout << "\nOLD_MESH_INTERSECT, nmeshes = " << meshes.size() << "\n";
906 }
907 MeshesToIMeshInfo mim(meshes);
908 mim.joined_mesh = joined_mesh;
909 meshintersect::IMeshArena arena;
910 meshintersect::IMesh m_in = meshes_to_imesh(meshes, transforms, material_remaps, arena, &mim);
911 const auto shape_fn = [&](int f) { return mesh_id_for_face(f, mim.mesh_offsets); };
912 meshintersect::IMesh m_out = boolean_mesh(
913 m_in, boolean_mode, meshes.size(), shape_fn, use_self, hole_tolerant, nullptr, &arena);
914 if (dbg_level > 0) {
915 std::cout << m_out;
916 write_obj_mesh(m_out, "m_out");
917 }
918
919 Mesh *result = imesh_to_mesh(&m_out, mim);
920
921 /* Store intersecting edge indices. */
922 if (r_intersecting_edges != nullptr) {
923 const OffsetIndices faces = result->faces();
924 const Span<int> corner_edges = result->corner_edges();
925 for (int fi : m_out.face_index_range()) {
926 const meshintersect::Face &face = *m_out.face(fi);
927 const IndexRange mesh_face = faces[fi];
928 for (int i : face.index_range()) {
929 if (face.is_intersect[i]) {
930 int e_index = corner_edges[mesh_face[i]];
931 r_intersecting_edges->append(e_index);
932 }
933 }
934 }
935 }
936
937 return result;
938}
939
940#endif // WITH_GMP
941
943
944/* -------------------------------------------------------------------- */
947
948/* has no meaning for faces, do this so we can tell which face is which */
949#define BM_FACE_TAG BM_ELEM_SELECT_UV
950
955static int face_boolean_operand(BMFace *f, void * /*user_data*/)
956{
957 return BM_elem_flag_test(f, BM_FACE_TAG) ? 0 : 1;
958}
959
960/* Create a BMesh that is the concatenation of the given meshes.
961 * The corresponding mesh-to-world transformations are also given,
962 * as well as a target_tranform.
963 * A triangulation is also calculated and returned in the last two
964 * parameters.
965 * The faces of the first mesh are tagged with BM_FACE_TAG so that the
966 * face_boolean_operand() function can distinguish those faces from the
967 * rest.
968 * The caller is responsible for using `BM_mesh_free` on the returned
969 * BMesh, and calling `MEM_delete` on the returned looptris.
970 *
971 * TODO: maybe figure out how to use the join_geometries() function
972 * to join all the meshes into one mesh first, and then convert
973 * that single mesh to BMesh. Issues with that include needing
974 * to apply the transforms and material remaps.
975 */
977 Span<float4x4> transforms,
978 Span<Array<short>> material_remaps,
979 Array<std::array<BMLoop *, 3>> &r_looptris)
980{
981 const int meshes_num = meshes.size();
982 BLI_assert(meshes_num >= 1);
983 Array<bool> is_negative_transform(meshes_num);
984 Array<bool> is_flip(meshes_num);
985 const int tsize = transforms.size();
986 for (const int i : IndexRange(meshes_num)) {
987 if (tsize > i) {
988 is_negative_transform[i] = math::is_negative(transforms[i]);
989 is_flip[i] = is_negative_transform[i] != is_negative_transform[0];
990 }
991 else {
992 is_negative_transform[i] = false;
993 is_flip[i] = false;
994 }
995 }
996
997 /* Make a BMesh that will be a concatenation of the elements of all the meshes */
998 BMAllocTemplate allocsize;
999 allocsize.totvert = 0;
1000 allocsize.totedge = 0;
1001 allocsize.totloop = 0;
1002 allocsize.totface = 0;
1003 for (const int i : meshes.index_range()) {
1004 allocsize.totvert += meshes[i]->verts_num;
1005 allocsize.totedge += meshes[i]->edges_num;
1006 allocsize.totloop += meshes[i]->corners_num;
1007 allocsize.totface += meshes[i]->faces_num;
1008 }
1009
1010 BMeshCreateParams bmesh_create_params{};
1011 BMesh *bm = BM_mesh_create(&allocsize, &bmesh_create_params);
1012
1014 bm, const_cast<const Mesh **>(meshes.begin()), meshes_num, &allocsize);
1015
1016 BMeshFromMeshParams bmesh_from_mesh_params{};
1017 bmesh_from_mesh_params.calc_face_normal = true;
1018 bmesh_from_mesh_params.calc_vert_normal = true;
1019
1020 Array<int> verts_end(meshes_num);
1021 Array<int> faces_end(meshes_num);
1022 verts_end[0] = meshes[0]->verts_num;
1023 faces_end[0] = meshes[0]->faces_num;
1024 for (const int i : meshes.index_range()) {
1025 /* Append meshes[i] elements and data to bm. */
1026 BM_mesh_bm_from_me(bm, meshes[i], &bmesh_from_mesh_params);
1027 if (i > 0) {
1028 verts_end[i] = verts_end[i - 1] + meshes[i]->verts_num;
1029 faces_end[i] = faces_end[i - 1] + meshes[i]->faces_num;
1030 if (is_flip[i]) {
1031 /* Need to flip face normals to match that of mesh[0]. */
1032 const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
1034 for (int j = faces_end[i - 1]; j < faces_end[i]; j++) {
1035 BMFace *efa = bm->ftable[j];
1036 BM_face_normal_flip_ex(bm, efa, cd_loop_mdisp_offset, true);
1037 }
1038 }
1039 }
1040 }
1041
1042 /* Make a triangulation of all polys before transforming vertices
1043 * so we can use the original normals. */
1044 const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop);
1045 r_looptris.reinitialize(looptris_tot);
1047
1048 /* Transform the vertices that into the desired target_transform space. */
1049 BMIter iter;
1050 BMVert *eve;
1051 int i = 0;
1052 int mesh_index = 0;
1053 BM_ITER_MESH (eve, &iter, bm, BM_VERTS_OF_MESH) {
1054 copy_v3_v3(eve->co, math::transform_point(transforms[mesh_index], float3(eve->co)));
1055 ++i;
1056 if (i == verts_end[mesh_index]) {
1057 mesh_index++;
1058 }
1059 }
1060
1061 /* Transform face normals and tag the first-operand faces.
1062 * Also, apply material remaps. */
1063 BMFace *efa;
1064 i = 0;
1065 mesh_index = 0;
1066 BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
1067 copy_v3_v3(efa->no, math::transform_direction(transforms[mesh_index], float3(efa->no)));
1068 if (is_negative_transform[mesh_index]) {
1069 negate_v3(efa->no);
1070 }
1071 normalize_v3(efa->no);
1072
1073 /* Temp tag used in `face_boolean_operand()` to test for operand 0. */
1074 if (i < faces_end[0]) {
1076 }
1077
1078 /* Remap material. */
1079 int cur_mat = efa->mat_nr;
1080 if (cur_mat < material_remaps[mesh_index].size()) {
1081 int new_mat = material_remaps[mesh_index][cur_mat];
1082 if (new_mat >= 0) {
1083 efa->mat_nr = material_remaps[mesh_index][cur_mat];
1084 }
1085 }
1086
1087 ++i;
1088 if (i == faces_end[mesh_index]) {
1089 mesh_index++;
1090 }
1091 }
1092
1093 return bm;
1094}
1095
1096static int operation_to_float_mode(const Operation operation)
1097{
1098 switch (operation) {
1101 case Operation::Union:
1105 }
1108}
1109
1111 Span<float4x4> transforms,
1112 Span<Array<short>> material_remaps,
1113 const int boolean_mode,
1114 Vector<int> * /*r_intersecting_edges*/)
1115{
1116 BLI_assert(meshes.size() == transforms.size() || transforms.size() == 0);
1117 BLI_assert(material_remaps.size() == 0 || material_remaps.size() == meshes.size());
1118 if (meshes.is_empty()) {
1119 return nullptr;
1120 }
1121
1122 if (meshes.size() == 1) {
1123 /* The float solver doesn't do self union. Just return nullptr, which will
1124 * cause geometry nodes to leave the input as is. */
1125 return BKE_mesh_copy_for_eval(*meshes[0]);
1126 }
1127
1129 if (meshes.size() == 2) {
1130 BMesh *bm = mesh_bm_concat(meshes, transforms, material_remaps, looptris);
1132 looptris,
1134 nullptr,
1135 false,
1136 false,
1137 true,
1138 true,
1139 false,
1140 false,
1141 boolean_mode,
1142 1e-6f);
1143 Mesh *result = BKE_mesh_from_bmesh_for_eval_nomain(bm, nullptr, meshes[0]);
1145 return result;
1146 }
1147
1148 /* Iteratively operate with each operand. */
1149 Array<const Mesh *> two_meshes = {meshes[0], meshes[1]};
1150 Array<float4x4> two_transforms = {transforms[0], transforms[1]};
1151 Array<Array<short>> two_remaps = {material_remaps[0], material_remaps[1]};
1152 Mesh *prev_result_mesh = nullptr;
1153 for (const int i : meshes.index_range().drop_back(1)) {
1154 BMesh *bm = mesh_bm_concat(two_meshes, two_transforms, two_remaps, looptris);
1156 looptris,
1158 nullptr,
1159 false,
1160 false,
1161 true,
1162 true,
1163 false,
1164 false,
1165 boolean_mode,
1166 1e-6f);
1167 Mesh *result_i_mesh = BKE_mesh_from_bmesh_for_eval_nomain(bm, nullptr, meshes[0]);
1169 if (prev_result_mesh != nullptr) {
1170 /* Except in the first iteration, two_meshes[0] holds the intermediate
1171 * mesh result from the previous iteration. */
1172 BKE_id_free(nullptr, prev_result_mesh);
1173 }
1174 if (i < meshes.size() - 2) {
1175 two_meshes[0] = result_i_mesh;
1176 two_meshes[1] = meshes[i + 2];
1177 two_transforms[0] = float4x4::identity();
1178 two_transforms[1] = transforms[i + 2];
1179 two_remaps[0] = {};
1180 two_remaps[1] = material_remaps[i + 2];
1181 prev_result_mesh = result_i_mesh;
1182 }
1183 else {
1184 return result_i_mesh;
1185 }
1186 }
1187
1189 return nullptr;
1190}
1191
1192#ifdef BENCHMARK_TIME
1193/* Append benchmark time and other information for boolean operations to a /tmp file. */
1194static void write_boolean_benchmark_time(
1195 StringRef solver, StringRef op, const Mesh *mesh1, const Mesh *mesh2, float time_ms)
1196{
1197 StringRef mesh1_name = mesh1 ? mesh1->id.name + 2 : "";
1198 StringRef mesh2_name = mesh2 ? mesh2->id.name + 2 : "";
1199 const int num_faces_1 = mesh1 ? mesh1->faces_num : 0;
1200 const int num_faces_2 = mesh2 ? mesh2->faces_num : 0;
1201 const int num_tris_1 = mesh1 ? mesh1->corner_tris().size() : 0;
1202 const int num_tris_2 = mesh2 ? mesh2->corner_tris().size() : 0;
1203 const int threads = BLI_system_num_threads_override_get();
1204
1205 /* Add header line if file doesn't exist yet. */
1206 bool first_time = false;
1207 if (!std::filesystem::exists(BENCHMARK_FILE)) {
1208 first_time = true;
1209 }
1210 /* Open the benchmark file in append mode. */
1211 std::ofstream outfile(BENCHMARK_FILE, std::ios_base::app);
1212
1213 if (outfile.is_open()) {
1214 if (first_time) {
1215 outfile << "solver,op,mesh1,mesh2,face1,face2,tris1,tris2,time_in_ms,threads" << std::endl;
1216 }
1217 outfile << solver << "," << op << ",\"" << mesh1_name << "\",\"" << mesh2_name << "\","
1218 << num_faces_1 << "," << num_faces_2 << "," << num_tris_1 << "," << num_tris_2 << ","
1219 << time_ms << "," << threads << std::endl;
1220 outfile.close();
1221 }
1222 else {
1223 std::cerr << "Unable to open benchmark file: " << BENCHMARK_FILE << std::endl;
1224 }
1225}
1226#endif
1227
1229
1231 Span<float4x4> transforms,
1232 Span<Array<short>> material_remaps,
1233 BooleanOpParameters op_params,
1234 Solver solver,
1235 Vector<int> *r_intersecting_edges,
1236 BooleanError *r_error)
1237{
1238 Mesh *ans = nullptr;
1239#ifdef BENCHMARK_TIME
1240 const timeit::TimePoint start_time = timeit::Clock::now();
1241#endif
1242 switch (solver) {
1243 case Solver::Float:
1245 ans = mesh_boolean_float(meshes,
1246 transforms,
1247 material_remaps,
1249 r_intersecting_edges);
1250 break;
1251 case Solver::MeshArr:
1252#ifdef WITH_GMP
1254 ans = mesh_boolean_mesh_arr(meshes,
1255 transforms,
1256 material_remaps,
1257 !op_params.no_self_intersections,
1258 !op_params.watertight,
1259 operation_to_mesh_arr_mode(op_params.boolean_mode),
1260 r_intersecting_edges);
1261#else
1263#endif
1264 break;
1265 case Solver::Manifold:
1266#ifdef WITH_MANIFOLD
1268 meshes, transforms, material_remaps, op_params, r_intersecting_edges, r_error);
1269#else
1271#endif
1272 break;
1273 default:
1275 }
1276#ifdef BENCHMARK_TIME
1277 const timeit::TimePoint end_time = timeit::Clock::now();
1278 const timeit::Nanoseconds duration = end_time - start_time;
1279 float time_ms = duration.count() / 1.0e6f;
1280 Operation op = op_params.boolean_mode;
1281 const char *opstr = op == Operation::Intersect ?
1282 "intersect" :
1283 (op == Operation::Union ? "union" : "difference");
1284 const Mesh *mesh1 = meshes.size() > 0 ? meshes[0] : nullptr;
1285 const Mesh *mesh2 = meshes.size() > 0 ? meshes[1] : nullptr;
1286 const char *solverstr = solver == Solver::Float ? "float" :
1287 solver == Solver::MeshArr ? "mesharr" :
1288 "manifold";
1289 write_boolean_benchmark_time(solverstr, opstr, mesh1, mesh2, time_ms);
1290#endif
1291 return ans;
1292}
1293
1294} // namespace blender::geometry::boolean
#define BLI_assert_unreachable()
#define BLI_assert(a)
#define ELEM(...)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_ITER_MESH(ele, iter, bm, itype)
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr bool is_empty() const
Definition BLI_span.hh:264
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
GPointer()=default
static IndexMask from_indices(Span< T > indices, LinearAllocator<> &memory)
constexpr IndexRange drop_back(int64_t n) const
static constexpr IndexRange from_begin_end(const int64_t begin, const int64_t end)
constexpr IndexRange()=default
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr const T * begin() const
Definition BLI_span.hh:224
constexpr bool is_empty() const
Definition BLI_span.hh:264
ccl_device_inline float interp(const float a, const float b, const float t)
Definition math_base.h:549
IndexMask indices_non_negative(const IndexMask &universe, Span< int > values, LinearAllocator<> &memory)
void gather(GSpan src, Span< int > map, GMutableSpan dst)
void mix_groups(GSpan src, OffsetIndices< int > groups, Span< int > all_indices, std::optional< Span< float > > all_weights, GMutableSpan dst)
auto attribute_filter_from_skip_ref(const Span< StringRef > skip)
void mesh_calc_edges(Mesh &mesh, bool keep_existing_edges, bool select_new_edges)
bool mesh_validate(Mesh &mesh, bool verbose=false, bool allow_missing_edges=false)
constexpr ParallelGrainSize grain_size(int grain_size)
static int operation_to_float_mode(const Operation operation)
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)
static Mesh * mesh_boolean_float(Span< const Mesh * > meshes, Span< float4x4 > transforms, Span< Array< short > > material_remaps, const int boolean_mode, Vector< int > *)
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)
static BMesh * mesh_bm_concat(Span< const Mesh * > meshes, Span< float4x4 > transforms, Span< Array< short > > material_remaps, Array< std::array< BMLoop *, 3 > > &r_looptris)
bke::GeometrySet join_meshes_with_transforms(Span< const Mesh * > meshes, Span< float4x4 > transforms)
Mesh * mesh_boolean(Span< const Mesh * > meshes, Span< float4x4 > transforms, Span< Array< short > > material_remaps, BooleanOpParameters op_params, Solver solver, Vector< int > *r_intersecting_edges, BooleanError *r_error)
static int face_boolean_operand(BMFace *f, void *)
RealizeInstancesResult realize_instances(bke::GeometrySet geometry_set, const RealizeInstancesOptions &options)
bool is_negative(const MatBase< T, 3, 3 > &mat)
VecBase< T, 3 > transform_direction(const MatBase< T, 3, 3 > &mat, const VecBase< T, 3 > &direction)
VecBase< T, 3 > transform_point(const CartesianBasis &basis, const VecBase< T, 3 > &v)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
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
std::chrono::nanoseconds Nanoseconds
Definition BLI_timeit.hh:21
Clock::time_point TimePoint
Definition BLI_timeit.hh:20
int CustomData_get_offset(const CustomData *data, eCustomDataType type)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void BM_mesh_free(BMesh *bm)
BMesh Free Mesh.
MINLINE void copy_v3_v3(float r[3], const float a[3])
void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
Mesh * BKE_mesh_copy_for_eval(const Mesh &source)
ATTR_WARN_UNUSED_RESULT const BMVert * v
MatBase< float, 4, 4 > float4x4
void BM_mesh_bm_from_me(BMesh *bm, const Mesh *mesh, const BMeshFromMeshParams *params)
Mesh -> BMesh.
void BKE_mesh_copy_parameters_for_eval(Mesh *me_dst, const Mesh *me_src)
bool BM_mesh_intersect(BMesh *bm, const Span< std::array< BMLoop *, 3 > > looptris, int(*test_fn)(BMFace *f, void *user_data), void *user_data, const bool use_self, const bool use_separate, const bool use_dissolve, const bool use_island_connect, const bool use_partial_connect, const bool use_edge_tag, const int boolean_mode, const float eps)
Mesh * BKE_mesh_new_nomain(int verts_num, int edges_num, int faces_num, int corners_num)
void BM_mesh_calc_tessellation_beauty(BMesh *bm, MutableSpan< std::array< BMLoop *, 3 > > looptris)
@ BMESH_ISECT_BOOLEAN_NONE
@ BMESH_ISECT_BOOLEAN_DIFFERENCE
@ BMESH_ISECT_BOOLEAN_UNION
@ BMESH_ISECT_BOOLEAN_ISECT
MINLINE void negate_v3(float r[3])
MINLINE int poly_to_tri_count(int poly_count, int corner_count)
void BKE_id_free(Main *bmain, void *idv)
MINLINE float normalize_v3(float n[3])
int BLI_system_num_threads_override_get()
Definition threads.cc:299
void BM_face_normal_flip_ex(BMesh *bm, BMFace *f, const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip)
Face Flip Normal.
Mesh * BKE_mesh_from_bmesh_for_eval_nomain(BMesh *bm, const CustomData_MeshMasks *cd_mask_extra, const Mesh *me_settings)
void BM_mesh_copy_init_customdata_from_mesh_array(BMesh *bm_dst, const Mesh *me_src_array[], const int me_src_array_len, const BMAllocTemplate *allocsize)
VecBase< float, 3 > float3
BMesh * BM_mesh_create(const BMAllocTemplate *allocsize, const BMeshCreateParams *params)
BMesh Make Mesh.
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
#define fabsf
CustomData ldata
BMFace ** ftable
char name[258]
Definition DNA_ID.h:433
static GeometrySet from_mesh(Mesh *mesh, GeometryOwnershipType ownership=GeometryOwnershipType::Owned)
static GeometrySet from_instances(std::unique_ptr< Instances > instances)