Blender V5.3
mesh_triangulate.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include "BLI_array_utils.hh"
11#include "BLI_index_mask.hh"
14#include "BLI_math_geom_c.hh"
15#include "BLI_math_matrix_c.hh"
16#include "BLI_polyfill_2d.hh"
18#include "BLI_vector_set.hh"
19
20#include "BLI_heap.hh"
21#include "BLI_memarena.hh"
22
23#include "BKE_attribute.hh"
24#include "BKE_attribute_math.hh"
26#include "BKE_customdata.hh"
27#include "BKE_mesh.hh"
28
30
31namespace blender::geometry {
32
33static void gather(const Span<int> src, const Span<int16_t> indices, MutableSpan<int> dst)
34{
35 for (const int i : indices.index_range()) {
36 dst[i] = src[indices[i]];
37 }
38}
39
41 const Span<int16_t> indices,
42 Vector<int> &dst)
43{
45 return src.slice(indices[0], indices.size());
46 }
47 dst.reinitialize(indices.size());
48 gather(src, indices, dst);
49 return dst.as_span();
50}
51
54 Vector<int> &dst)
55{
56 return gather_or_reference(src.drop_front(mask.offset()), mask.base_span(), dst);
57}
58
63static Span<float3> face_normals_if_worthwhile(const Mesh &src_mesh, const int selection_size)
64{
65 if (src_mesh.runtime->face_normals_cache.is_cached()) {
66 return src_mesh.face_normals();
67 }
68 if (selection_size > src_mesh.faces_num / 4) {
69 return src_mesh.face_normals();
70 }
71 return {};
72}
73
74static void copy_loose_vert_hint(const Mesh &src, Mesh &dst)
75{
76 const auto &src_cache = src.runtime->loose_verts_cache;
77 if (src_cache.is_cached() && src_cache.data().mask.is_empty()) {
78 dst.tag_loose_verts_none();
79 }
80}
81
82namespace quad {
83
93enum class QuadDirection : int8_t {
96};
97
103 const float3 &v1,
104 const float3 &v2,
105 const float3 &v3)
106{
107 const int flip_flag = is_quad_flip_v3(v1, v2, v3, v0);
108 if (flip_flag & (1 << 0)) [[unlikely]] {
110 }
111 if (flip_flag & (1 << 1)) [[unlikely]] {
113 }
114 return BLI_polyfill_edge_calc_rotate_beauty__area(v1, v2, v3, v0, false) > 0.0f ?
117}
118
119static void calc_quad_directions(const Span<float3> positions,
120 const Span<int> face_offsets,
121 const Span<int> corner_verts,
122 const TriangulateQuadMode quad_mode,
124{
125 switch (quad_mode) {
127 directions.fill(QuadDirection::Edge_0_2);
128 break;
129 }
131 directions.fill(QuadDirection::Edge_1_3);
132 break;
133 }
135 for (const int i : face_offsets.index_range()) {
136 const Span<int> verts = corner_verts.slice(face_offsets[i], 4);
137 const float dist_0_2 = math::distance_squared(positions[verts[0]], positions[verts[2]]);
138 const float dist_1_3 = math::distance_squared(positions[verts[1]], positions[verts[3]]);
139 directions[i] = dist_0_2 < dist_1_3 ? QuadDirection::Edge_0_2 : QuadDirection::Edge_1_3;
140 }
141 break;
142 }
144 for (const int i : face_offsets.index_range()) {
145 const Span<int> verts = corner_verts.slice(face_offsets[i], 4);
146 const float dist_0_2 = math::distance_squared(positions[verts[0]], positions[verts[2]]);
147 const float dist_1_3 = math::distance_squared(positions[verts[1]], positions[verts[3]]);
148 directions[i] = dist_0_2 > dist_1_3 ? QuadDirection::Edge_0_2 : QuadDirection::Edge_1_3;
149 }
150 break;
151 }
153 for (const int i : face_offsets.index_range()) {
154 const Span<int> verts = corner_verts.slice(face_offsets[i], 4);
155 directions[i] = calc_quad_direction_beauty(
156 positions[verts[0]], positions[verts[1]], positions[verts[2]], positions[verts[3]]);
157 }
158
159 break;
160 }
161 }
162}
163
164static void calc_corner_tris(const Span<int> face_offsets,
165 const Span<QuadDirection> directions,
166 MutableSpan<int3> corner_tris)
167{
168 for (const int i : face_offsets.index_range()) {
169 MutableSpan<int> quad_map = corner_tris.slice(2 * i, 2).cast<int>();
170 /* These corner orders give new edges based on the first vertex of each triangle. */
171 switch (directions[i]) {
173 quad_map.copy_from({2, 0, 1, 0, 2, 3});
174 break;
176 quad_map.copy_from({1, 3, 0, 3, 1, 2});
177 break;
178 }
179 const int src_face_start = face_offsets[i];
180 for (int &i : quad_map) {
181 i += src_face_start;
182 }
183 }
184}
185
186static void calc_corner_tris(const Span<float3> positions,
187 const OffsetIndices<int> src_faces,
188 const Span<int> src_corner_verts,
189 const IndexMask &quads,
190 const TriangulateQuadMode quad_mode,
191 MutableSpan<int3> corner_tris)
192{
193 struct TLS {
194 Vector<int> offsets;
195 Vector<QuadDirection> directions;
196 };
198
199 quads.foreach_segment(
200 [&](const IndexMaskSegment quads, const int64_t pos) {
201 TLS &data = tls.local();
202 data.directions.reinitialize(quads.size());
203
204 /* Find the offsets of each face in the local selection. We can gather them together even
205 * if they aren't contiguous because we only need to know the start of each face; the size
206 * is just 4. */
207 const Span<int> offsets = gather_or_reference(src_faces.data(), quads, data.offsets);
208 calc_quad_directions(positions, offsets, src_corner_verts, quad_mode, data.directions);
209 const IndexRange tris_range(pos * 2, offsets.size() * 2);
210 quad::calc_corner_tris(offsets, data.directions, corner_tris.slice(tris_range));
211 },
213}
214
215} // namespace quad
216
218 const IndexMaskSegment selection,
219 MutableSpan<int> dst_offsets)
220{
221 int offset = 0;
222 for (const int64_t i : selection.index_range()) {
223 dst_offsets[i] = offset;
224 offset += src_offsets[selection[i]].size();
225 }
226 dst_offsets.last() = offset;
227 return OffsetIndices<int>(dst_offsets);
228}
229
230namespace ngon {
231
233 const IndexMask &ngons,
234 MutableSpan<int> face_offset_data)
235{
236 ngons.foreach_index(
237 [&](const int face, const int mask) {
238 face_offset_data[mask] = bke::mesh::face_triangles_num(src_faces[face].size());
239 },
241 return offset_indices::accumulate_counts_to_offsets(face_offset_data);
242}
243
244static void calc_corner_tris(const Span<float3> positions,
245 const OffsetIndices<int> src_faces,
246 const Span<int> src_corner_verts,
247 const Span<float3> face_normals,
248 const IndexMask &ngons,
249 const OffsetIndices<int> tris_by_ngon,
250 const TriangulateNGonMode ngon_mode,
251 MutableSpan<int3> corner_tris)
252{
253 struct LocalData {
254 Vector<float3x3> projections;
255 Array<int> offset_data;
256 Vector<float2> projected_positions;
257
258 /* Only used for the "Beauty" method. */
259 MemArena *arena = nullptr;
260 Heap *heap = nullptr;
261
262 ~LocalData()
263 {
264 if (arena) {
265 BLI_memarena_free(arena);
266 }
267 if (heap) {
268 BLI_heap_free(heap, nullptr);
269 }
270 }
271 };
273
274 ngons.foreach_segment(
275 [&](const IndexMaskSegment ngons, const int pos) {
276 LocalData &data = tls.local();
277
278 /* In order to simplify and "parallelize" the next loops, gather offsets used to group an
279 * array large enough for all the local face corners. */
280 data.offset_data.reinitialize(ngons.size() + 1);
281 const OffsetIndices local_corner_offsets = gather_selected_offsets(
282 src_faces, ngons, data.offset_data);
283
284 /* Use face normals to build projection matrices to make the face positions 2D. */
285 data.projections.reinitialize(ngons.size());
286 MutableSpan<float3x3> projections = data.projections;
287 if (face_normals.is_empty()) {
288 for (const int i : ngons.index_range()) {
289 const IndexRange src_face = src_faces[ngons[i]];
290 const Span<int> face_verts = src_corner_verts.slice(src_face);
291 const float3 normal = bke::mesh::face_normal_calc(positions, face_verts);
292 axis_dominant_v3_to_m3_negate(projections[i].ptr(), normal);
293 }
294 }
295 else {
296 for (const int i : ngons.index_range()) {
297 axis_dominant_v3_to_m3_negate(projections[i].ptr(), face_normals[ngons[i]]);
298 }
299 }
300
301 /* Project the face positions into 2D using the matrices calculated above. */
302 data.projected_positions.reinitialize(local_corner_offsets.total_size());
303 MutableSpan<float2> projected_positions = data.projected_positions;
304 for (const int i : ngons.index_range()) {
305 const IndexRange src_face = src_faces[ngons[i]];
306 const Span<int> face_verts = src_corner_verts.slice(src_face);
307 const float3x3 &matrix = projections[i];
308
309 MutableSpan<float2> positions_2d = projected_positions.slice(local_corner_offsets[i]);
310 for (const int i : face_verts.index_range()) {
311 mul_v2_m3v3(positions_2d[i], matrix.ptr(), positions[face_verts[i]]);
312 }
313 }
314
315 if (ngon_mode == TriangulateNGonMode::Beauty) {
316 if (!data.arena) {
317 data.arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, "calc_corner_tris data.arena");
318 }
319 if (!data.heap) {
321 }
322 }
323
324 /* Calculate the triangulation of corners indices local to each face. */
325 for (const int i : ngons.index_range()) {
326 const Span<float2> positions_2d = projected_positions.slice(local_corner_offsets[i]);
327 const IndexRange tris_range = tris_by_ngon[pos + i];
328 MutableSpan<int> map = corner_tris.slice(tris_range).cast<int>();
329 BLI_polyfill_calc(reinterpret_cast<const float (*)[2]>(positions_2d.data()),
330 positions_2d.size(),
331 1,
332 reinterpret_cast<uint(*)[3]>(map.data()));
333 if (ngon_mode == TriangulateNGonMode::Beauty) {
334 BLI_polyfill_beautify(reinterpret_cast<const float (*)[2]>(positions_2d.data()),
335 positions_2d.size(),
336 reinterpret_cast<uint(*)[3]>(map.data()),
337 data.arena,
338 data.heap);
340 }
341 }
342
343 /* "Globalize" the triangulation created above so the map source indices reference _all_ of
344 * the source vertices, not just within the source face. */
345 for (const int i : ngons.index_range()) {
346 const IndexRange tris_range = tris_by_ngon[pos + i];
347 const int src_face_start = src_faces[ngons[i]].start();
348 MutableSpan<int> map = corner_tris.slice(tris_range).cast<int>();
349 for (int &vert : map) {
350 vert += src_face_start;
351 }
352 }
353 },
355}
356
357} // namespace ngon
358
359struct TriKey {
361 /* The lowest vertex index in the face is used as a hash value and a way to compare face keys to
362 * avoid memory lookup in all false cases. */
364
365 TriKey(const int tri_index, Span<int3> tris)
367 {
368 [[maybe_unused]] const int3 &tri_verts = tris[tri_index];
369 BLI_assert(std::is_sorted(&tri_verts[0], &tri_verts[0] + 3));
370 }
371};
372
373struct FaceHash {
374 uint64_t operator()(const TriKey value) const
375 {
376 return uint64_t(value.tri_lower_vert);
377 }
378
379 uint64_t operator()(const int3 value) const
380 {
381 BLI_assert(std::is_sorted(&value[0], &value[0] + 3));
382 return uint64_t(value[0]);
383 }
384};
385
388 bool operator()(const TriKey a, const TriKey b) const
389 {
390 return a.tri_lower_vert == b.tri_lower_vert && tris[a.tri_index] == tris[b.tri_index];
391 }
392
393 bool operator()(const int3 a, const TriKey b) const
394 {
395 BLI_assert(std::is_sorted(&a[0], &a[0] + 3));
396 return b.tri_lower_vert == a[0] && tris[b.tri_index] == a;
397 }
398};
399
400static int3 tri_to_ordered(const int3 tri)
401{
402 int3 res;
403 res[0] = std::min({tri[0], tri[1], tri[2]});
404 res[2] = std::max({tri[0], tri[1], tri[2]});
405 res[1] = (tri[0] - res[0]) + (tri[2] - res[2]) + tri[1];
406 return res;
407}
408
410{
411 threading::parallel_for(tris.index_range(), 4096, [&](const IndexRange range) {
412 for (int3 &tri : tris.slice(range)) {
413 tri = tri_to_ordered(tri);
414 }
415 });
416 return tris;
417}
418
420 const IndexMask &mask,
421 IndexMaskMemory &memory)
422{
424 mask,
425 memory,
426 [&](const IndexMaskSegment universe_segment, IndexRangesBuilder<int16_t> &builder) {
429 universe_segment.base_span());
430 const IndexRange segment_range = universe_as_range.shift(universe_segment.offset());
431 const OffsetIndices segment_faces = src_faces.slice(segment_range);
432 if (segment_faces.total_size() == segment_faces.size() * 3) {
433 /* All faces in segment are triangles. */
434 builder.add_range(universe_as_range.start(), universe_as_range.one_after_last());
435 return universe_segment.offset();
436 }
437 }
438
439 for (const int16_t i : universe_segment.base_span()) {
440 const int face = int(universe_segment.offset() + i);
441 if (src_faces[face].size() == 3) {
442 builder.add(i);
443 }
444 }
445 return universe_segment.offset();
446 });
447}
448
449static IndexMask tris_in_set(const IndexMask &tri_mask,
450 const OffsetIndices<int> faces,
451 const Span<int> corner_verts,
452 const VectorSet<TriKey,
453 4,
455 FaceHash,
458 IndexMaskMemory &memory)
459{
460 return IndexMask::from_predicate(tri_mask, memory, [&](const int face_i) {
461 BLI_assert(faces[face_i].size() == 3);
462 const int3 corner_tri(&corner_verts[faces[face_i].start()]);
463 return unique_tris.contains_as(tri_to_ordered(corner_tri));
464 });
465}
466
468{
469 BLI_assert(faces.size() == indices.size());
470 threading::parallel_for(faces.index_range(), 4096, [&](const IndexRange range) {
471 for (const int face_i : range) {
472 indices[face_i] = faces[face_i].tri_index;
473 }
474 });
475}
476
477static void quad_indices_of_tris(const IndexMask &quads, MutableSpan<int> indices)
478{
479 BLI_assert(quads.size() * 2 == indices.size());
480 quads.foreach_index_optimized<int>(
481 [&](const int index, const int pos) {
482 indices[2 * pos + 0] = index;
483 indices[2 * pos + 1] = index;
484 },
486}
487
488static void ngon_indices_of_tris(const IndexMask &ngons,
489 const OffsetIndices<int> tris_by_ngon,
490 MutableSpan<int> indices)
491{
492 BLI_assert(tris_by_ngon.size() == ngons.size());
493 BLI_assert(tris_by_ngon.total_size() == indices.size());
494 ngons.foreach_index_optimized<int>(
495 [&](const int index, const int pos) { indices.slice(tris_by_ngon[pos]).fill(index); },
497}
498
499std::optional<Mesh *> mesh_triangulate(const Mesh &src_mesh,
500 const IndexMask &selection_with_tris,
501 const TriangulateNGonMode ngon_mode,
502 const TriangulateQuadMode quad_mode,
503 const bke::AttributeFilter &attribute_filter)
504{
505 const Span<float3> positions = src_mesh.vert_positions();
506 const OffsetIndices src_faces = src_mesh.faces();
507 const Span<int> src_corner_verts = src_mesh.corner_verts();
508 const bke::AttributeAccessor src_attributes = src_mesh.attributes();
509
510 IndexMaskMemory memory;
511
512 /* If there are a lot of triangles, they can be skipped quickly for filtering. */
513 const IndexMask src_tris = face_tris_mask(src_faces, src_faces.index_range(), memory);
514 const IndexMask selection = IndexMask::from_difference(selection_with_tris, src_tris, memory);
515
516 /* Divide the input selection into separate selections for each face type. This isn't necessary
517 * for correctness, but considering groups of each face type separately simplifies optimizing
518 * for each type. For example, quad triangulation is much simpler than Ngon triangulation. */
520 selection, memory, [&](const int i) { return src_faces[i].size() == 4; });
522 selection, memory, [&](const int i) { return src_faces[i].size() > 4; });
523 if (quads.is_empty() && ngons.is_empty()) {
524 /* All selected faces are already triangles. */
525 return std::nullopt;
526 }
527
528 /* Calculate group of triangle indices for each selected Ngon to facilitate calculating them in
529 * parallel later. */
530 Array<int> tris_by_ngon_data(ngons.size() + 1);
531 const OffsetIndices tris_by_ngon = ngon::calc_tris_by_ngon(src_faces, ngons, tris_by_ngon_data);
532 const int ngon_tris_num = tris_by_ngon.total_size();
533 const int quad_tris_num = quads.size() * 2;
534 const IndexRange tris_range(ngon_tris_num + quad_tris_num);
535 const IndexRange ngon_tris_range = tris_range.take_front(ngon_tris_num);
536 const IndexRange quad_tris_range = tris_range.take_back(quad_tris_num);
537
538 Array<int3> corner_tris(ngon_tris_num + quad_tris_num);
539
540 if (!ngons.is_empty()) {
541 ngon::calc_corner_tris(positions,
542 src_faces,
543 src_corner_verts,
544 face_normals_if_worthwhile(src_mesh, ngons.size()),
545 ngons,
546 tris_by_ngon,
547 ngon_mode,
548 corner_tris.as_mutable_span().slice(ngon_tris_range));
549 }
550 if (!quads.is_empty()) {
551 quad::calc_corner_tris(positions,
552 src_faces,
553 src_corner_verts,
554 quads,
555 quad_mode,
556 corner_tris.as_mutable_span().slice(quad_tris_range));
557 }
558
559 /* There are 3 separate sets of triangles: original mesh triangles, new triangles from quads,
560 * and triangles from n-gons. Deduplication can result in a mix of parts of multiple quads,
561 * multiple quads, original triangle, and even concatenation of parts of multiple n-gons.
562 * So we have to deduplicate all triangles together. */
563 Array<int3> vert_tris(ngon_tris_num + quad_tris_num);
564 array_utils::gather(src_corner_verts,
565 corner_tris.as_span().cast<int>(),
566 vert_tris.as_mutable_span().cast<int>());
567 const Span<int3> ordered_vert_tris = tri_to_ordered_tri(vert_tris.as_mutable_span());
568
569 /* Use ordered vertex triplets (a < b < c) to represent all new triangles.
570 * #TriKey knows indices of the face and points into #ordered_vert_tris, but probe can be done
571 * without #TriKey but directly with a triplet so probe not necessary to be a part of
572 * #ordered_vert_tris. */
574 4,
576 FaceHash,
579 unique_tris(FaceHash{}, FacesEquality{ordered_vert_tris});
580
581 /* Could be done parallel using grouping of faces by their lowest vertex and the next linear
582 * deduplication, but right now this is just a sequential hash-set. */
583 for (const int face_i : ordered_vert_tris.index_range()) {
584 const TriKey face_key(face_i, ordered_vert_tris);
585 unique_tris.add(face_key);
586 }
587 const int unique_tri_num = unique_tris.size();
588
589 /* Since currently deduplication is greedy, there is no mix of data of deduplicated triangles,
590 * instead some of them are removed. Priority: Original triangles removed if any of new triangles
591 * are the same. For all new triangles here is direct order dependency. */
592 const IndexMask src_tris_duplicated = tris_in_set(
593 src_tris, src_faces, src_corner_verts, unique_tris, memory);
594
595 index_mask::ExprBuilder mask_builder;
596 const IndexMask unique_src_faces = index_mask::evaluate_expression(
597 mask_builder.subtract(src_faces.index_range(), {&quads, &ngons, &src_tris_duplicated}),
598 memory);
599
600 const IndexRange unique_faces_range(unique_tri_num + unique_src_faces.size());
601 const IndexRange unique_tri_range = unique_faces_range.take_front(unique_tri_num);
602 const IndexRange unique_src_faces_range = unique_faces_range.take_back(unique_src_faces.size());
603
604 /* Create a mesh with no face corners.
605 * - We haven't yet counted the number of corners from unselected faces. Creating the final face
606 * offsets will give us that number anyway, so wait to create the edges.
607 * - Don't create attributes to facilitate implicit sharing of the positions array. */
609 src_mesh.verts_num, src_mesh.edges_num, unique_faces_range.size(), 0);
611
612 MutableSpan<int> dst_offsets = mesh->face_offsets_for_write();
614 3, 0, dst_offsets.take_front(unique_tri_range.size() + 1));
615 const int total_new_tri_corners = unique_tri_range.size() * 3;
617 src_faces,
618 unique_src_faces,
619 total_new_tri_corners,
620 dst_offsets.take_back(unique_src_faces_range.size() + 1));
621
622 const OffsetIndices<int> faces(dst_offsets);
623 mesh->corners_num = faces.total_size();
624
625 /* Vertex attributes are totally unaffected and can be shared with implicit sharing.
626 * Use the #CustomData API for simpler support for vertex groups. Edge attributes are the same
627 * for original edges. New edges will be generated by #bke::mesh_calc_edges later.*/
628 CustomData_merge(&src_mesh.vert_data, &mesh->vert_data, CD_MASK_MESH.vmask, mesh->verts_num);
629 CustomData_merge(&src_mesh.edge_data, &mesh->edge_data, CD_MASK_MESH.emask, mesh->edges_num);
630 for (const bke::Attribute &attr : src_mesh.attribute_storage.wrap()) {
631 if (!ELEM(attr.domain(), bke::AttrDomain::Point, bke::AttrDomain::Edge)) {
632 continue;
633 }
634 mesh->attribute_storage.wrap().add(attr.name(), attr.domain(), attr.data_type(), attr.data());
635 }
636
637 bke::MutableAttributeAccessor attributes = mesh->attributes_for_write();
638
639 const bool has_duplicate_faces = unique_tri_num != (ngon_tris_num + quad_tris_num);
640
641 Array<int> dst_tri_to_src_face(unique_tri_num);
642 face_keys_to_face_indices(unique_tris.as_span(), dst_tri_to_src_face.as_mutable_span());
643
644 Array<int3> unique_corner_tris_data;
645 if (has_duplicate_faces) {
646 unique_corner_tris_data.reinitialize(unique_tri_num);
647 array_utils::gather(corner_tris.as_span(),
648 dst_tri_to_src_face.as_span(),
649 unique_corner_tris_data.as_mutable_span());
650 }
651
652 {
653 Array<int> src_to_unique_map(ngon_tris_num + quad_tris_num);
654 quad_indices_of_tris(quads, src_to_unique_map.as_mutable_span().slice(quad_tris_range));
656 ngons, tris_by_ngon, src_to_unique_map.as_mutable_span().slice(ngon_tris_range));
657
658 array_utils::gather(src_to_unique_map.as_span(),
659 dst_tri_to_src_face.as_span(),
660 dst_tri_to_src_face.as_mutable_span());
661 }
662
663 const Span<int3> unique_corner_tris = has_duplicate_faces ? unique_corner_tris_data.as_span() :
664 corner_tris.as_span();
665
667 src_attributes, attributes, {bke::AttrDomain::Face}, attribute_filter))
668 {
670 attribute.src, dst_tri_to_src_face.as_span(), attribute.dst.span.slice(unique_tri_range));
672 attribute.src, unique_src_faces, attribute.dst.span.slice(unique_src_faces_range));
673 attribute.dst.finish();
674 }
676 const Span src(
677 static_cast<const int *>(CustomData_get_layer(&src_mesh.face_data, CD_ORIGINDEX)),
678 src_mesh.faces_num);
679 MutableSpan dst(static_cast<int *>(CustomData_add_layer(
680 &mesh->face_data, CD_ORIGINDEX, CD_CONSTRUCT, mesh->faces_num)),
681 mesh->faces_num);
682
683 array_utils::gather(src, dst_tri_to_src_face.as_span(), dst.slice(unique_tri_range));
684 array_utils::gather(src, unique_src_faces, dst.slice(unique_src_faces_range));
685 }
686
687 attributes.add<int>(".corner_vert", bke::AttrDomain::Corner, bke::AttributeInitConstruct());
688
689 MutableSpan<int> corner_verts = mesh->corner_verts_for_write();
691 faces.slice(unique_src_faces_range),
692 unique_src_faces,
693 src_corner_verts,
694 corner_verts);
695 array_utils::gather(src_corner_verts,
696 unique_corner_tris.cast<int>(),
697 corner_verts.take_front(total_new_tri_corners));
698
700 src_attributes,
701 attributes,
704 {".corner_vert", ".corner_edge"})))
705 {
707 src_faces,
708 faces.slice(IndexRange(unique_tri_num, unique_src_faces.size())),
709 unique_src_faces,
710 attribute.src,
711 attribute.dst.span);
713 unique_corner_tris.cast<int>(),
714 attribute.dst.span.slice(0, unique_tri_num * 3));
715 attribute.dst.finish();
716 }
717
718 /* Automatically generate new edges between new triangles, with necessary deduplication. */
719 bke::mesh_calc_edges(*mesh, true, false, attribute_filter);
720
721 mesh->runtime->bounds_cache = src_mesh.runtime->bounds_cache;
722 copy_loose_vert_hint(src_mesh, *mesh);
723 if (src_mesh.no_overlapping_topology()) {
724 mesh->tag_overlapping_none();
725 }
727 return mesh;
728}
729
730} // namespace blender::geometry
CustomData interface, see also DNA_customdata_types.h.
A min-heap / priority queue ADT.
#define BLI_POLYFILL_ARENA_SIZE
#define BLI_POLYFILL_ALLOC_NGON_RESERVE
#define ELEM(...)
Span< T > as_span() const
Definition BLI_array.hh:254
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
static IndexMask from_predicate(const IndexMask &universe, LinearAllocator<> &memory, Fn &&predicate, exec_mode::Mode mode=exec_mode::parallel)
static IndexMask from_difference(const IndexMask &mask_a, const IndexMask &mask_b, LinearAllocator<> &memory)
static IndexMask from_batch_predicate(const IndexMask &universe, LinearAllocator<> &memory, FunctionRef< int64_t(const IndexMaskSegment &universe_segment, IndexRangesBuilder< int16_t > &builder)> batch_predicate, exec_mode::Mode mode=exec_mode::parallel)
constexpr int64_t one_after_last() const
constexpr IndexRange shift(int64_t n) const
constexpr int64_t size() const
constexpr int64_t start() const
constexpr IndexRange take_back(int64_t n) const
constexpr IndexRange take_front(int64_t n) const
bool add_range(const T start, const T end)
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr MutableSpan< NewT > cast() const
Definition BLI_span.hh:755
constexpr MutableSpan take_back(const int64_t n) const
Definition BLI_span.hh:646
constexpr T * data() const
Definition BLI_span.hh:545
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr void copy_from(Span< T > values) const
Definition BLI_span.hh:745
constexpr MutableSpan take_front(const int64_t n) const
Definition BLI_span.hh:635
constexpr T & last(const int64_t n=0) const
Definition BLI_span.hh:695
IndexRange index_range() const
Span< BaseT > base_span() const
constexpr Span drop_front(int64_t n) const
Definition BLI_span.hh:175
Span< NewT > constexpr cast() const
Definition BLI_span.hh:422
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
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)
Span< T > as_span() const
bool add(const StringRef name, const AttrDomain domain, const AttrType data_type, const AttributeInit &initializer)
const DifferenceExpr & subtract(const Term &main_term, const Span< Term > subtract_terms)
void foreach_index_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
void foreach_segment(Fn &&fn, Mode mode=exec_mode::serial) const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
OffsetIndices slice(const IndexRange range) const
#define attribute(slot)
void gather(const GVArray &src, const IndexMask &indices, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
void gather_group_to_group(const OffsetIndices< int > src_offsets, const OffsetIndices< int > dst_offsets, const IndexMask &selection, const Span< T > src, MutableSpan< T > dst)
void gather(GSpan src, Span< int > map, GMutableSpan dst)
void gather_group_to_group(OffsetIndices< int > src_offsets, OffsetIndices< int > dst_offsets, const IndexMask &selection, GSpan src, GMutableSpan dst)
float3 face_normal_calc(Span< float3 > vert_positions, Span< int > face_verts)
int face_triangles_num(const int face_size)
Definition BKE_mesh.hh:350
auto attribute_filter_with_skip_ref(const AttributeFilter &filter, const Span< StringRef > skip)
bool mesh_is_valid(const Mesh &mesh, bool verbose=true)
Vector< AttributeTransferData > retrieve_attributes_for_transfer(const AttributeAccessor src_attributes, MutableAttributeAccessor dst_attributes, Span< AttrDomain > domains, const AttributeFilter &attribute_filter={})
Mesh * mesh_new_no_attributes(int verts_num, int edges_num, int faces_num, int corners_num)
void mesh_calc_edges(Mesh &mesh, bool keep_existing_edges, bool select_new_edges)
constexpr ParallelGrainSize grain_size(int grain_size)
static void calc_corner_tris(const Span< float3 > positions, const OffsetIndices< int > src_faces, const Span< int > src_corner_verts, const Span< float3 > face_normals, const IndexMask &ngons, const OffsetIndices< int > tris_by_ngon, const TriangulateNGonMode ngon_mode, MutableSpan< int3 > corner_tris)
static OffsetIndices< int > calc_tris_by_ngon(const OffsetIndices< int > src_faces, const IndexMask &ngons, MutableSpan< int > face_offset_data)
static void calc_corner_tris(const Span< int > face_offsets, const Span< QuadDirection > directions, MutableSpan< int3 > corner_tris)
static void calc_quad_directions(const Span< float3 > positions, const Span< int > face_offsets, const Span< int > corner_verts, const TriangulateQuadMode quad_mode, MutableSpan< QuadDirection > directions)
static QuadDirection calc_quad_direction_beauty(const float3 &v0, const float3 &v1, const float3 &v2, const float3 &v3)
std::optional< Mesh * > mesh_triangulate(const Mesh &src_mesh, const IndexMask &selection, TriangulateNGonMode ngon_mode, TriangulateQuadMode quad_mode, const bke::AttributeFilter &attribute_filter)
static void ngon_indices_of_tris(const IndexMask &ngons, const OffsetIndices< int > tris_by_ngon, MutableSpan< int > indices)
static void gather(const Span< int > src, const Span< int16_t > indices, MutableSpan< int > dst)
static Span< int3 > tri_to_ordered_tri(MutableSpan< int3 > tris)
static void quad_indices_of_tris(const IndexMask &quads, MutableSpan< int > indices)
static int3 tri_to_ordered(const int3 tri)
static void face_keys_to_face_indices(const Span< TriKey > faces, MutableSpan< int > indices)
static OffsetIndices< int > gather_selected_offsets(const OffsetIndices< int > src_offsets, const IndexMaskSegment selection, MutableSpan< int > dst_offsets)
static Span< float3 > face_normals_if_worthwhile(const Mesh &src_mesh, const int selection_size)
static Span< int > gather_or_reference(const Span< int > src, const Span< int16_t > indices, Vector< int > &dst)
static IndexMask face_tris_mask(const OffsetIndices< int > src_faces, const IndexMask &mask, IndexMaskMemory &memory)
static void copy_loose_vert_hint(const Mesh &src, Mesh &dst)
static IndexMask tris_in_set(const IndexMask &tri_mask, const OffsetIndices< int > faces, const Span< int > corner_verts, const VectorSet< TriKey, 4, DefaultProbingStrategy, FaceHash, FacesEquality, SimpleVectorSetSlot< TriKey, int > > &unique_tris, IndexMaskMemory &memory)
IndexMask evaluate_expression(const Expr &expression, LinearAllocator<> &memory)
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
void fill_constant_group_size(int size, int start_offset, MutableSpan< int > offsets)
OffsetIndices< int > gather_selected_offsets(OffsetIndices< int > src_offsets, const IndexMask &selection, int start_offset, MutableSpan< int > dst_offsets)
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
bool non_empty_is_range(const Span< T > indices)
IndexRange non_empty_as_range(const Span< T > indices)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
unsigned __int64 uint64_t
Definition BKE_text.h:91
__int64 int64_t
Definition BKE_text.h:90
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:173
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
unsigned int uint
Definition BKE_text.h:55
bool CustomData_has_layer(const CustomData *data, eCustomDataType type)
void BLI_polyfill_calc(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3])
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:193
void BKE_mesh_copy_parameters_for_eval(Mesh *me_dst, const Mesh *me_src)
VecBase< int32_t, 3 > int3
float BLI_polyfill_edge_calc_rotate_beauty__area(const float v1[3], const float v2[3], const float v3[3], const float v4[3], bool lock_degenerate)
BMesh const char void * data
void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
const void * CustomData_get_layer(const CustomData *data, eCustomDataType type)
bool CustomData_merge(const CustomData *source, CustomData *dest, eCustomDataMask mask, int totelem)
MatBase< float, 3, 3 > float3x3
ATTR_WARN_UNUSED_RESULT const BMVert * v2
const CustomData_MeshMasks CD_MASK_MESH
PythonProbingStrategy<> DefaultProbingStrategy
int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
VecBase< float, 3 > float3
signed char int8_t
Definition BKE_text.h:76
void BLI_polyfill_beautify(const float(*coords)[2], unsigned int coords_num, unsigned int(*tris)[3], struct MemArena *arena, struct Heap *eheap)
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
signed short int16_t
Definition BKE_text.h:77
void * CustomData_add_layer(CustomData *data, eCustomDataType type, eCDAllocType alloctype, int totelem)
const c_style_mat & ptr() const
struct AttributeStorage attribute_storage
bke::MeshRuntime * runtime
CustomData face_data
CustomData edge_data
CustomData vert_data
SharedCache< Bounds< float3 > > bounds_cache
SharedCache< NormalsCache > face_normals_cache
SharedCache< LooseGeomCache > loose_verts_cache
uint64_t operator()(const TriKey value) const
uint64_t operator()(const int3 value) const
bool operator()(const TriKey a, const TriKey b) const
bool operator()(const int3 a, const TriKey b) const
TriKey(const int tri_index, Span< int3 > tris)