Blender V5.3
mesh_mapping.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
11
12#include <algorithm>
13
14#include "MEM_guardedalloc.h"
15
16#include "BLI_array.hh"
17#include "BLI_bitmap.hh"
18#include "BLI_function_ref.hh"
19#include "BLI_math_geom_c.hh"
20#include "BLI_math_vector_c.hh"
21#include "BLI_task.hh"
22#include "BLI_utildefines.hh"
23
24#include "BKE_customdata.hh"
25#include "BKE_mesh.hh"
26#include "BKE_mesh_mapping.hh"
27#include "BLI_memarena.hh"
28
29#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
30
31namespace blender {
32
33/* -------------------------------------------------------------------- */
36
38 Span<int> corner_verts,
39 Span<float2> uv_map,
40 int verts_num,
41 const float2 &limit,
42 bool use_winding)
43{
44 /* NOTE: N-gon version WIP, based on #BM_uv_vert_map_create. */
45 if (faces.is_empty()) {
46 return nullptr;
47 }
48 const int corners_num = faces.total_size();
49
50 UvVertMap *vmap = MEM_new_zeroed<UvVertMap>("UvVertMap");
51 UvMapVert *buf = vmap->buf = MEM_new_array_zeroed<UvMapVert>(size_t(corners_num), "UvMapVert");
52 vmap->vert = MEM_new_array_zeroed<UvMapVert *>(size_t(verts_num), "UvMapVert*");
53
54 if (!vmap->vert || !vmap->buf) {
56 return nullptr;
57 }
58
59 Array<bool> winding;
60 if (use_winding) {
61 winding = Array<bool>(faces.size(), false);
62 threading::parallel_for(faces.index_range(), 1024, [&](const IndexRange range) {
63 for (const int64_t face : range) {
64 const Span<float2> face_uvs = uv_map.slice(faces[face]);
65 winding[face] = cross_poly_v2(reinterpret_cast<const float (*)[2]>(face_uvs.data()),
66 uint(faces[face].size())) < 0.0f;
67 }
68 });
69 }
70
71 for (const int64_t a : faces.index_range()) {
72 const IndexRange face = faces[a];
73 for (const int64_t i : face.index_range()) {
74 buf->loop_of_face_index = ushort(i);
75 buf->face_index = uint(a);
76 buf->separate = false;
77 buf->next = vmap->vert[corner_verts[face[i]]];
78 vmap->vert[corner_verts[face[i]]] = buf;
79 buf++;
80 }
81 }
82
83 /* sort individual uvs for each vert */
84 for (const int64_t vert : IndexRange(verts_num)) {
85 UvMapVert *newvlist = nullptr, *vlist = vmap->vert[vert];
86 UvMapVert *iterv, *v, *lastv, *next;
87 const float *uv, *uv2;
88 float uvdiff[2];
89
90 while (vlist) {
91 v = vlist;
92 vlist = vlist->next;
93 v->next = newvlist;
94 newvlist = v;
95
96 uv = uv_map[faces[v->face_index].start() + v->loop_of_face_index];
97 lastv = nullptr;
98 iterv = vlist;
99
100 while (iterv) {
101 next = iterv->next;
102
103 uv2 = uv_map[faces[iterv->face_index].start() + iterv->loop_of_face_index];
104 sub_v2_v2v2(uvdiff, uv2, uv);
105
106 if (fabsf(uv[0] - uv2[0]) < limit[0] && fabsf(uv[1] - uv2[1]) < limit[1] &&
107 (!use_winding || winding[iterv->face_index] == winding[v->face_index]))
108 {
109 if (lastv) {
110 lastv->next = next;
111 }
112 else {
113 vlist = next;
114 }
115 iterv->next = newvlist;
116 newvlist = iterv;
117 }
118 else {
119 lastv = iterv;
120 }
121
122 iterv = next;
123 }
124
125 newvlist->separate = true;
126 }
127
128 vmap->vert[vert] = newvlist;
129 }
130
131 return vmap;
132}
133
135{
136 return vmap->vert[v];
137}
138
140{
141 if (vmap) {
142 if (vmap->vert) {
143 MEM_delete(vmap->vert);
144 }
145 if (vmap->buf) {
146 MEM_delete(vmap->buf);
147 }
148 MEM_delete(vmap);
149 }
150}
151
153 int **r_mem,
154 const int totvert,
155 const int3 *corner_tris,
156 const int tris_num,
157 const int *corner_verts,
158 const int /*corners_num*/)
159{
160 MeshElemMap *map = MEM_new_array_zeroed<MeshElemMap>(size_t(totvert), __func__);
161 int *indices = MEM_new_array_uninitialized<int>(size_t(tris_num) * 3, __func__);
162 int *index_step;
163 int i;
164
165 /* count face users */
166 for (i = 0; i < tris_num; i++) {
167 for (int j = 3; j--;) {
168 map[corner_verts[corner_tris[i][j]]].count++;
169 }
170 }
171
172 /* create offsets */
173 index_step = indices;
174 for (i = 0; i < totvert; i++) {
175 map[i].indices = index_step;
176 index_step += map[i].count;
177
178 /* re-count, using this as an index below */
179 map[i].count = 0;
180 }
181
182 /* assign corner_tri-edge users */
183 for (i = 0; i < tris_num; i++) {
184 for (int j = 3; j--;) {
185 MeshElemMap *map_ele = &map[corner_verts[corner_tris[i][j]]];
186 map_ele->indices[map_ele->count++] = i;
187 }
188 }
189
190 *r_map = map;
191 *r_mem = indices;
192}
193
195 int **r_mem,
196 const int totsource,
197 const int *final_origindex,
198 const int totfinal)
199{
200 MeshElemMap *map = MEM_new_array_zeroed<MeshElemMap>(size_t(totsource), __func__);
201 int *indices = MEM_new_array_uninitialized<int>(size_t(totfinal), __func__);
202 int *index_step;
203 int i;
204
205 /* count face users */
206 for (i = 0; i < totfinal; i++) {
207 if (final_origindex[i] != ORIGINDEX_NONE) {
208 BLI_assert(final_origindex[i] < totsource);
209 map[final_origindex[i]].count++;
210 }
211 }
212
213 /* create offsets */
214 index_step = indices;
215 for (i = 0; i < totsource; i++) {
216 map[i].indices = index_step;
217 index_step += map[i].count;
218
219 /* re-count, using this as an index below */
220 map[i].count = 0;
221 }
222
223 /* Assign face-tessellation users. */
224 for (i = 0; i < totfinal; i++) {
225 if (final_origindex[i] != ORIGINDEX_NONE) {
226 MeshElemMap *map_ele = &map[final_origindex[i]];
227 map_ele->indices[map_ele->count++] = i;
228 }
229 }
230
231 *r_map = map;
232 *r_mem = indices;
233}
234
236 int **r_mem,
237 const OffsetIndices<int> faces,
238 const int *corner_tri_faces,
239 const int corner_tris_num)
240{
241 MeshElemMap *map = MEM_new_array_zeroed<MeshElemMap>(size_t(faces.size()), __func__);
242 int *indices = MEM_new_array_uninitialized<int>(size_t(corner_tris_num), __func__);
243 int *index_step;
244
245 /* create offsets */
246 index_step = indices;
247 for (const int64_t i : faces.index_range()) {
248 map[i].indices = index_step;
249 index_step += bke::mesh::face_triangles_num(int(faces[i].size()));
250 }
251
252 /* Assign face-tessellation users. */
253 for (int i = 0; i < corner_tris_num; i++) {
254 MeshElemMap *map_ele = &map[corner_tri_faces[i]];
255 map_ele->indices[map_ele->count++] = i;
256 }
257
258 *r_map = map;
259 *r_mem = indices;
260}
261
262namespace bke::mesh {
263
264static Array<int> create_reverse_offsets(const Span<int> indices, const int items_num)
265{
266 Array<int> offsets(items_num + 1, 0);
268 return offsets;
269}
270
272{
273 Array<int> map(faces.total_size());
275 return map;
276}
277
279 const int verts_num,
280 Array<int> &r_offsets,
281 Array<int> &r_indices)
282{
283 const Span<int> edge_verts = edges.cast<int>();
284 r_offsets = create_reverse_offsets(edge_verts, verts_num);
285 const OffsetIndices<int> offsets(r_offsets);
286 r_indices.reinitialize(offsets.total_size());
287
288 /* Group edges by vertex. Each edge stores two vertices consecutively, so the edge index for a
289 * position in #edge_verts is that position divided by two. */
290 offset_indices::reverse_indices_in_groups(edge_verts, offsets, r_indices, 2);
291 return {offsets, r_indices};
292}
293
295 const Span<int> corner_verts,
296 const OffsetIndices<int> offsets,
297 MutableSpan<int> face_indices)
298{
299 offset_indices::reverse_indices_in_groups(corner_verts, offsets, face_indices, faces);
300}
301
303 const Span<int> corner_verts,
304 const int verts_num,
305 Array<int> &r_offsets,
306 Array<int> &r_indices)
307{
308 r_offsets = create_reverse_offsets(corner_verts, verts_num);
309 r_indices.reinitialize(r_offsets.last());
310 build_vert_to_face_indices(faces, corner_verts, OffsetIndices<int>(r_offsets), r_indices);
311 return {OffsetIndices<int>(r_offsets), r_indices};
312}
313
315 const OffsetIndices<int> offsets)
316{
317 Array<int> results(offsets.total_size());
318 offset_indices::reverse_indices_in_groups(corner_verts, offsets, results);
319 return results;
320}
321
323 const int verts_num,
324 Array<int> &r_offsets,
325 Array<int> &r_indices)
326{
327 return offset_indices::build_groups_from_indices(corner_verts, verts_num, r_offsets, r_indices);
328}
329
331 const int edges_num,
332 Array<int> &r_offsets,
333 Array<int> &r_indices)
334{
335 return offset_indices::build_groups_from_indices(corner_edges, edges_num, r_offsets, r_indices);
336}
337
339 const Span<int> corner_edges,
340 const int edges_num,
341 Array<int> &r_offsets,
342 Array<int> &r_indices)
343{
344 r_offsets = create_reverse_offsets(corner_edges, edges_num);
345 r_indices.reinitialize(r_offsets.last());
347 corner_edges, OffsetIndices<int>(r_offsets), r_indices, faces);
348 return {OffsetIndices<int>(r_offsets), r_indices};
349}
350
351} // namespace bke::mesh
352
354
355/* -------------------------------------------------------------------- */
359
363using MeshRemap_CheckIslandBoundary = FunctionRef<bool(int face_index,
364 int corner,
365 int edge_index,
366 int edge_user_count,
367 const Span<int> edge_face_map_elem)>;
368
370 const int *face_groups,
371 const Span<int> faces_from_item,
372 const int face_group_id,
373 const int face_group_id_overflowed,
374 int &r_bit_face_group_mask)
375{
376 /* Find neighbor faces (either from a boundary edge, or a boundary vertex) that already have a
377 * group assigned, and exclude these groups' bits from the available set of groups bits that can
378 * be assigned to the currently processed group. */
379 for (const int face_idx : faces_from_item) {
380 int bit = face_groups[face_idx];
381 if (!ELEM(bit, 0, face_group_id, face_group_id_overflowed) && !(r_bit_face_group_mask & bit)) {
382 r_bit_face_group_mask |= bit;
383 }
384 }
385}
386
403static void face_edge_loop_islands_calc(const int totedge,
404 const int totvert,
405 const OffsetIndices<int> faces,
406 const Span<int> corner_edges,
407 const Span<int> corner_verts,
408 GroupedSpan<int> edge_face_map,
409 GroupedSpan<int> vert_face_map,
410 const bool use_bitflags,
411 const bool use_boundary_vertices_for_bitflags,
412 MeshRemap_CheckIslandBoundary edge_boundary_check,
413 int **r_face_groups,
414 int *r_totgroup,
415 BLI_bitmap **r_edge_boundaries,
416 int *r_totedgeboundaries)
417{
418 int *face_groups;
419 int *face_stack;
420
421 BLI_bitmap *edge_boundaries = nullptr;
422 int num_edgeboundaries = 0;
423
424 int face_prev = 0;
425 constexpr int temp_face_group_id = 3; /* Placeholder value. */
426
427 /* For bitflags groups, group we could not find any available bit for, will be reset to 0 at the
428 * end. */
429 constexpr int face_group_id_overflowed = 5;
430
431 int tot_group = 0;
432 bool group_id_overflow = false;
433
434 if (faces.is_empty()) {
435 *r_totgroup = 0;
436 *r_face_groups = nullptr;
437 if (r_edge_boundaries) {
438 *r_edge_boundaries = nullptr;
439 *r_totedgeboundaries = 0;
440 }
441 return;
442 }
443
444 if (r_edge_boundaries) {
445 edge_boundaries = BLI_BITMAP_NEW(totedge, __func__);
446 *r_totedgeboundaries = 0;
447 }
448
449 Array<int> edge_to_face_src_offsets;
450 Array<int> edge_to_face_src_indices;
451 if (edge_face_map.is_empty()) {
452 edge_face_map = bke::mesh::build_edge_to_face_map(
453 faces, corner_edges, totedge, edge_to_face_src_offsets, edge_to_face_src_indices);
454 }
455 Array<int> vert_to_face_src_offsets;
456 Array<int> vert_to_face_src_indices;
457 if (use_bitflags && vert_face_map.is_empty()) {
458 vert_face_map = bke::mesh::build_vert_to_face_map(
459 faces, corner_verts, totvert, vert_to_face_src_offsets, vert_to_face_src_indices);
460 }
461
462 face_groups = MEM_new_array_zeroed<int>(size_t(faces.size()), __func__);
463 face_stack = MEM_new_array_uninitialized<int>(size_t(faces.size()), __func__);
464
465 while (true) {
466 int face;
467 int bit_face_group_mask = 0;
468 int face_group_id;
469 int ps_curr_idx = 0, ps_end_idx = 0; /* stack indices */
470
471 for (face = face_prev; face < int(faces.size()); face++) {
472 if (face_groups[face] == 0) {
473 break;
474 }
475 }
476
477 if (face == int(faces.size())) {
478 /* all done */
479 break;
480 }
481
482 face_group_id = use_bitflags ? temp_face_group_id : ++tot_group;
483
484 /* start searching from here next time */
485 face_prev = face + 1;
486
487 face_groups[face] = face_group_id;
488 face_stack[ps_end_idx++] = face;
489
490 while (ps_curr_idx != ps_end_idx) {
491 face = face_stack[ps_curr_idx++];
492 BLI_assert(face_groups[face] == face_group_id);
493
494 for (const int64_t loop : faces[face]) {
495 const int edge = corner_edges[loop];
496 /* loop over face users */
497 const Span<int> map_ele = edge_face_map[edge];
498 const int *p = map_ele.data();
499 int i = int(map_ele.size());
500 if (!edge_boundary_check(face, int(loop), edge, i, map_ele)) {
501 for (; i--; p++) {
502 /* if we meet other non initialized its a bug */
503 BLI_assert(ELEM(face_groups[*p], 0, face_group_id));
504
505 if (face_groups[*p] == 0) {
506 face_groups[*p] = face_group_id;
507 face_stack[ps_end_idx++] = *p;
508 }
509 }
510 }
511 else {
512 if (edge_boundaries && !BLI_BITMAP_TEST(edge_boundaries, edge)) {
513 BLI_BITMAP_ENABLE(edge_boundaries, edge);
514 num_edgeboundaries++;
515 }
516 if (use_bitflags) {
517 /* Exclude bits used in other groups sharing the same boundary edge. */
519 map_ele,
520 face_group_id,
521 face_group_id_overflowed,
522 bit_face_group_mask);
523 if (use_boundary_vertices_for_bitflags) {
524 /* Exclude bits used in other groups sharing the same boundary vertex. */
525 /* NOTE: Checking one vertex for each edge (the corner vertex) should be enough:
526 * - Thanks to winding, a fully boundary vertex (i.e. a vertex for which at least
527 * two of the adjacent edges in the same group are boundary ones) will be
528 * processed by at least one of the edges/corners. If not when processing the
529 * first face's corner, then when processing the other face's corner in the same
530 * group.
531 * - Isolated boundary edges (i.e. boundary edges only connected to faces of the
532 * same group) cannot be represented by bit-flags groups, at least not with
533 * current algorithm (they cannot define more than one group).
534 * - Inversions of winding (aka flipped faces) always generate boundary edges in
535 * current use-case (smooth groups), i.e. two faces with opposed winding cannot
536 * belong to the same group. */
537 const int vert = corner_verts[loop];
539 vert_face_map[vert],
540 face_group_id,
541 face_group_id_overflowed,
542 bit_face_group_mask);
543 }
544 }
545 }
546 }
547 }
548 /* And now, we have all our face from current group in face_stack
549 * (from 0 to (ps_end_idx - 1)),
550 * as well as all smoothgroups bits we can't use in bit_face_group_mask.
551 */
552 if (use_bitflags) {
553 int i, *p, gid_bit = 0;
554 face_group_id = 1;
555
556 /* Find first bit available! */
557 for (; (face_group_id & bit_face_group_mask) && (gid_bit < 32); gid_bit++) {
558 face_group_id <<= 1; /* will 'overflow' on last possible iteration. */
559 }
560 if (gid_bit > 31) [[unlikely]] {
561 /* All bits used in contiguous smooth groups, not much to do.
562 *
563 * NOTE: If only considering boundary edges, this is *very* unlikely to happen.
564 * Theoretically, four groups are enough, this is probably not achievable with such a
565 * simple algorithm, but 32 groups should always be more than enough.
566 *
567 * When also considering boundary vertices (which is the case currently, see comment
568 * above), a fairly simple fan case with over 30 faces all belonging to different groups
569 * will be enough to cause an overflow.
570 */
571 printf(
572 "Warning, could not find an available id for current smooth group, faces will me "
573 "marked "
574 "as out of any smooth group...\n");
575
576 /* Can't use 0, will have to set them to this value later. */
577 face_group_id = face_group_id_overflowed;
578
579 group_id_overflow = true;
580 }
581 tot_group = std::max(gid_bit, tot_group);
582 /* And assign the final smooth group id to that face group! */
583 for (i = ps_end_idx, p = face_stack; i--; p++) {
584 face_groups[*p] = face_group_id;
585 }
586 }
587 }
588
589 if (use_bitflags) {
590 /* used bits are zero-based. */
591 tot_group++;
592 }
593
594 if (group_id_overflow) [[unlikely]] {
595 int i = int(faces.size()), *gid = face_groups;
596 for (; i--; gid++) {
597 if (*gid == face_group_id_overflowed) {
598 *gid = 0;
599 }
600 }
601 /* Using 0 as group id adds one more group! */
602 tot_group++;
603 }
604
605 MEM_delete(face_stack);
606
607 *r_totgroup = tot_group;
608 *r_face_groups = face_groups;
609 if (r_edge_boundaries) {
610 *r_edge_boundaries = edge_boundaries;
611 *r_totedgeboundaries = num_edgeboundaries;
612 }
613}
614
615static int *mesh_calc_smoothgroups(const int edges_num,
616 const int verts_num,
617 const OffsetIndices<int> faces,
618 const Span<int> corner_edges,
619 const Span<int> corner_verts,
620 const Span<bool> sharp_edges,
621 const Span<bool> sharp_faces,
622 int *r_totgroup,
623 const bool use_bitflags,
624 const bool use_boundary_vertices_for_bitflags)
625{
626 int *face_groups = nullptr;
627
628 auto face_is_smooth = [&](const int i) { return sharp_faces.is_empty() || !sharp_faces[i]; };
629
630 auto face_is_island_boundary_smooth = [&](const int face_index,
631 const int /*corner*/,
632 const int edge_index,
633 const int edge_user_count,
634 const Span<int> edge_face_map_elem) {
635 /* Edge is sharp if one of its faces is flat, or edge itself is sharp,
636 * or edge is not used by exactly two faces. */
637 if (face_is_smooth(face_index) && !(!sharp_edges.is_empty() && sharp_edges[edge_index]) &&
638 (edge_user_count == 2))
639 {
640 /* In that case, edge appears to be smooth, but we need to check its other face too. */
641 const int other_face_index = (face_index == edge_face_map_elem[0]) ? edge_face_map_elem[1] :
642 edge_face_map_elem[0];
643 return !face_is_smooth(other_face_index);
644 }
645 return true;
646 };
647
649 verts_num,
650 faces,
651 corner_edges,
652 corner_verts,
653 {},
654 {},
655 use_bitflags,
656 use_boundary_vertices_for_bitflags,
657 face_is_island_boundary_smooth,
658 &face_groups,
659 r_totgroup,
660 nullptr,
661 nullptr);
662
663 return face_groups;
664}
665
666int *BKE_mesh_calc_smoothgroups(int edges_num,
667 const OffsetIndices<int> faces,
668 const Span<int> corner_edges,
669 const Span<bool> sharp_edges,
670 const Span<bool> sharp_faces,
671 int *r_totgroup)
672{
674 edges_num, 0, faces, corner_edges, {}, sharp_edges, sharp_faces, r_totgroup, false, false);
675}
676
678 int verts_num,
679 const OffsetIndices<int> faces,
680 const Span<int> corner_edges,
681 const Span<int> corner_verts,
682 const Span<bool> sharp_edges,
683 const Span<bool> sharp_faces,
684 const bool use_boundary_vertices_for_bitflags,
685 int *r_totgroup)
686{
687 return mesh_calc_smoothgroups(edges_num,
688 verts_num,
689 faces,
690 corner_edges,
691 corner_verts,
692 sharp_edges,
693 sharp_faces,
694 r_totgroup,
695 true,
696 use_boundary_vertices_for_bitflags);
697}
698
699#define MISLAND_DEFAULT_BUFSIZE 64
700
702 const short item_type,
703 const int items_num,
704 const short island_type,
705 const short innercut_type)
706{
707 MemArena *mem = island_store->mem;
708
709 if (mem == nullptr) {
711 island_store->mem = mem;
712 }
713 /* else memarena should be cleared */
714
719
720 island_store->item_type = item_type;
721 island_store->items_to_islands_num = items_num;
722 island_store->items_to_islands = static_cast<int *>(
723 BLI_memarena_alloc(mem, sizeof(*island_store->items_to_islands) * size_t(items_num)));
724
725 island_store->island_type = island_type;
727 island_store->islands = static_cast<MeshElemMap **>(
728 BLI_memarena_alloc(mem, sizeof(*island_store->islands) * island_store->islands_num_alloc));
729
730 island_store->innercut_type = innercut_type;
731 island_store->innercuts = static_cast<MeshElemMap **>(
732 BLI_memarena_alloc(mem, sizeof(*island_store->innercuts) * island_store->islands_num_alloc));
733}
734
736{
737 island_store->item_type = MISLAND_TYPE_NONE;
738 island_store->items_to_islands_num = 0;
739 island_store->items_to_islands = nullptr;
740
741 island_store->island_type = MISLAND_TYPE_NONE;
742 island_store->islands_num = 0;
743 island_store->islands = nullptr;
744
745 island_store->innercut_type = MISLAND_TYPE_NONE;
746 island_store->innercuts = nullptr;
747
748 if (island_store->mem) {
749 BLI_memarena_clear(island_store->mem);
750 }
751
752 island_store->islands_num_alloc = 0;
753}
754
756{
757 if (island_store->mem) {
758 BLI_memarena_free(island_store->mem);
759 island_store->mem = nullptr;
760 }
761}
762
764 const int item_num,
765 const int *items_indices,
766 const int num_island_items,
767 int *island_item_indices,
768 const int num_innercut_items,
769 int *innercut_item_indices)
770{
771 MemArena *mem = island_store->mem;
772
773 MeshElemMap *isld, *innrcut;
774 const int curr_island_idx = island_store->islands_num++;
775 const size_t curr_num_islands = size_t(island_store->islands_num);
776 int i = item_num;
777
778 while (i--) {
779 island_store->items_to_islands[items_indices[i]] = curr_island_idx;
780 }
781
782 if (curr_num_islands > island_store->islands_num_alloc) [[unlikely]] {
783 MeshElemMap **islds, **innrcuts;
784
785 island_store->islands_num_alloc *= 2;
786 islds = static_cast<MeshElemMap **>(
787 BLI_memarena_alloc(mem, sizeof(*islds) * island_store->islands_num_alloc));
788 memcpy(islds, island_store->islands, sizeof(*islds) * (curr_num_islands - 1));
789 island_store->islands = islds;
790
791 innrcuts = static_cast<MeshElemMap **>(
792 BLI_memarena_alloc(mem, sizeof(*innrcuts) * island_store->islands_num_alloc));
793 memcpy(innrcuts, island_store->innercuts, sizeof(*innrcuts) * (curr_num_islands - 1));
794 island_store->innercuts = innrcuts;
795 }
796
797 island_store->islands[curr_island_idx] = isld = static_cast<MeshElemMap *>(
798 BLI_memarena_alloc(mem, sizeof(*isld)));
799 isld->count = num_island_items;
800 isld->indices = static_cast<int *>(
801 BLI_memarena_alloc(mem, sizeof(*isld->indices) * size_t(num_island_items)));
802 memcpy(isld->indices, island_item_indices, sizeof(*isld->indices) * size_t(num_island_items));
803
804 island_store->innercuts[curr_island_idx] = innrcut = static_cast<MeshElemMap *>(
805 BLI_memarena_alloc(mem, sizeof(*innrcut)));
806 innrcut->count = num_innercut_items;
807 innrcut->indices = static_cast<int *>(
808 BLI_memarena_alloc(mem, sizeof(*innrcut->indices) * size_t(num_innercut_items)));
809 memcpy(innrcut->indices,
810 innercut_item_indices,
811 sizeof(*innrcut->indices) * size_t(num_innercut_items));
812}
813
814static bool mesh_calc_islands_loop_face_uv(const int totedge,
815 const Span<bool> uv_seams,
816 const OffsetIndices<int> faces,
817 const Span<int> corner_edges,
818 MeshIslandStore *r_island_store)
819{
820 int *face_groups = nullptr;
821 int num_face_groups;
822
823 int *face_indices;
824 int *loop_indices;
825 int num_pidx, num_lidx;
826
827 /* Those are used to detect 'inner cuts', i.e. edges that are boundaries,
828 * and yet have two or more faces of a same group using them
829 * (typical case: seam used to unwrap properly a cylinder). */
830 BLI_bitmap *edge_boundaries = nullptr;
831 int num_edge_boundaries = 0;
832 char *edge_boundary_count = nullptr;
833 int *edge_innercut_indices = nullptr;
834 int num_einnercuts = 0;
835
836 int grp_idx;
837
838 BKE_mesh_loop_islands_clear(r_island_store);
839 BKE_mesh_loop_islands_init(r_island_store,
841 int(corner_edges.size()),
844
845 Array<int> edge_to_face_offsets;
846 Array<int> edge_to_face_indices;
848 faces, corner_edges, totedge, edge_to_face_offsets, edge_to_face_indices);
849
850 /* TODO: I'm not sure edge seam flag is enough to define UV islands?
851 * Maybe we should also consider UV-maps values
852 * themselves (i.e. different UV-edges for a same mesh-edge => boundary edge too?).
853 * Would make things much more complex though,
854 * and each UVMap would then need its own mesh mapping, not sure we want that at all!
855 */
856 auto mesh_check_island_boundary_uv = [&](const int /*face_index*/,
857 const int /*corner*/,
858 const int edge_index,
859 const int /*edge_user_count*/,
860 const Span<int> /*edge_face_map_elem*/) -> bool {
861 /* Edge is UV boundary if tagged as seam. */
862 return !uv_seams.is_empty() && uv_seams[edge_index];
863 };
864
866 0,
867 faces,
868 corner_edges,
869 {},
870 edge_to_face_map,
871 {},
872 false,
873 false,
874 mesh_check_island_boundary_uv,
875 &face_groups,
876 &num_face_groups,
877 &edge_boundaries,
878 &num_edge_boundaries);
879
880 if (!num_face_groups) {
881 if (num_edge_boundaries) {
882 MEM_delete(edge_boundaries);
883 }
884 return false;
885 }
886
887 if (num_edge_boundaries) {
888 edge_boundary_count = MEM_new_array_uninitialized<char>(size_t(totedge), __func__);
889 edge_innercut_indices = MEM_new_array_uninitialized<int>(size_t(num_edge_boundaries),
890 __func__);
891 }
892
893 face_indices = MEM_new_array_uninitialized<int>(size_t(faces.size()), __func__);
894 loop_indices = MEM_new_array_uninitialized<int>(size_t(corner_edges.size()), __func__);
895
896 /* NOTE: here we ignore '0' invalid group - this should *never* happen in this case anyway? */
897 for (grp_idx = 1; grp_idx <= num_face_groups; grp_idx++) {
898 num_pidx = num_lidx = 0;
899 if (num_edge_boundaries) {
900 num_einnercuts = 0;
901 memset(edge_boundary_count, 0, sizeof(*edge_boundary_count) * size_t(totedge));
902 }
903
904 for (const int64_t p_idx : faces.index_range()) {
905 if (face_groups[p_idx] != grp_idx) {
906 continue;
907 }
908 face_indices[num_pidx++] = int(p_idx);
909 for (const int64_t corner : faces[p_idx]) {
910 const int edge_i = corner_edges[corner];
911 loop_indices[num_lidx++] = int(corner);
912 if (num_edge_boundaries && BLI_BITMAP_TEST(edge_boundaries, edge_i) &&
913 (edge_boundary_count[edge_i] < 2))
914 {
915 edge_boundary_count[edge_i]++;
916 if (edge_boundary_count[edge_i] == 2) {
917 edge_innercut_indices[num_einnercuts++] = edge_i;
918 }
919 }
920 }
921 }
922
923 BKE_mesh_loop_islands_add(r_island_store,
924 num_lidx,
925 loop_indices,
926 num_pidx,
927 face_indices,
928 num_einnercuts,
929 edge_innercut_indices);
930 }
931
932 MEM_delete(face_indices);
933 MEM_delete(loop_indices);
934 MEM_delete(face_groups);
935
936 if (num_edge_boundaries) {
937 MEM_delete(edge_boundaries);
938 }
939
940 if (num_edge_boundaries) {
941 MEM_delete(edge_boundary_count);
942 MEM_delete(edge_innercut_indices);
943 }
944 return true;
945}
946
948 const Span<int2> edges,
949 const Span<bool> uv_seams,
950 const OffsetIndices<int> faces,
951 const Span<int> /*corner_verts*/,
952 const Span<int> corner_edges,
953 MeshIslandStore *r_island_store)
954{
955 UNUSED_VARS(vert_positions);
957 int(edges.size()), uv_seams, faces, corner_edges, r_island_store);
958}
959
961
962} // namespace blender
CustomData interface, see also DNA_customdata_types.h.
#define ORIGINDEX_NONE
#define BLI_BITMAP_NEW(_num, _alloc_string)
Definition BLI_bitmap.hh:39
#define BLI_BITMAP_TEST(_bitmap, _index)
Definition BLI_bitmap.hh:63
#define BLI_BITMAP_ENABLE(_bitmap, _index)
Definition BLI_bitmap.hh:80
#define BLI_MEMARENA_STD_BUFSIZE
Read Blender memory allocation and freeing.
#define UNUSED_VARS(...)
#define ELEM(...)
long long int int64_t
const T & last(const int64_t n=0) const
Definition BLI_array.hh:307
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
constexpr IndexRange()=default
Span< NewT > constexpr cast() const
Definition BLI_span.hh:422
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr bool is_empty() const
Definition BLI_span.hh:264
#define MISLAND_DEFAULT_BUFSIZE
void build_vert_to_face_indices(OffsetIndices< int > faces, Span< int > corner_verts, OffsetIndices< int > offsets, MutableSpan< int > face_indices)
GroupedSpan< int > build_vert_to_corner_map(Span< int > corner_verts, int verts_num, Array< int > &r_offsets, Array< int > &r_indices)
GroupedSpan< int > build_edge_to_corner_map(Span< int > corner_edges, int edges_num, Array< int > &r_offsets, Array< int > &r_indices)
static Array< int > create_reverse_offsets(const Span< int > indices, const int items_num)
int face_triangles_num(const int face_size)
Definition BKE_mesh.hh:350
GroupedSpan< int > build_edge_to_face_map(OffsetIndices< int > faces, Span< int > corner_edges, int edges_num, Array< int > &r_offsets, Array< int > &r_indices)
Array< int > build_corner_to_face_map(OffsetIndices< int > faces)
Array< int > build_vert_to_corner_indices(Span< int > corner_verts, OffsetIndices< int > offsets)
GroupedSpan< int > build_vert_to_face_map(OffsetIndices< int > faces, Span< int > corner_verts, int verts_num, Array< int > &r_offsets, Array< int > &r_indices)
GroupedSpan< int > build_vert_to_edge_map(Span< int2 > edges, int verts_num, Array< int > &r_offsets, Array< int > &r_indices)
void build_reverse_map(OffsetIndices< int > offsets, MutableSpan< int > r_map)
GroupedSpan< int > build_groups_from_indices(Span< int > indices, int groups_num, Array< int > &offset_data, Array< int > &index_data)
OffsetIndices< int > build_reverse_offsets(Span< int > indices, MutableSpan< int > offsets)
void reverse_indices_in_groups(Span< int > group_indices, OffsetIndices< int > offsets, MutableSpan< int > results, bool sort=true)
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
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void BKE_mesh_uv_vert_map_free(UvVertMap *vmap)
__int64 int64_t
Definition BKE_text.h:90
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
static void face_edge_loop_islands_calc_bitflags_exclude_at_boundary(const int *face_groups, const Span< int > faces_from_item, const int face_group_id, const int face_group_id_overflowed, int &r_bit_face_group_mask)
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
UvMapVert * BKE_mesh_uv_vert_map_get_vert(UvVertMap *vmap, unsigned int v)
unsigned short ushort
Definition BKE_text.h:56
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
ATTR_WARN_UNUSED_RESULT const BMVert * v
int * BKE_mesh_calc_smoothgroups(int edges_num, OffsetIndices< int > faces, Span< int > corner_edges, Span< bool > sharp_edges, Span< bool > sharp_faces, int *r_totgroup)
VecBase< float, 2 > float2
VecBase< int32_t, 3 > int3
static void face_edge_loop_islands_calc(const int totedge, const int totvert, const OffsetIndices< int > faces, const Span< int > corner_edges, const Span< int > corner_verts, GroupedSpan< int > edge_face_map, GroupedSpan< int > vert_face_map, const bool use_bitflags, const bool use_boundary_vertices_for_bitflags, MeshRemap_CheckIslandBoundary edge_boundary_check, int **r_face_groups, int *r_totgroup, BLI_bitmap **r_edge_boundaries, int *r_totedgeboundaries)
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
void BKE_mesh_origindex_map_create_corner_tri(MeshElemMap **r_map, int **r_mem, OffsetIndices< int > faces, const int *corner_tri_faces, int corner_tris_num)
UvVertMap * BKE_mesh_uv_vert_map_create(OffsetIndices< int > faces, Span< int > corner_verts, Span< float2 > uv_map, int verts_num, const float2 &limit, bool use_winding)
void BKE_mesh_loop_islands_add(MeshIslandStore *island_store, int item_num, const int *items_indices, int num_island_items, int *island_item_indices, int num_innercut_items, int *innercut_item_indices)
void BKE_mesh_vert_corner_tri_map_create(MeshElemMap **r_map, int **r_mem, int totvert, const int3 *corner_tris, int tris_num, const int *corner_verts, int corners_num)
static int * mesh_calc_smoothgroups(const int edges_num, const int verts_num, const OffsetIndices< int > faces, const Span< int > corner_edges, const Span< int > corner_verts, const Span< bool > sharp_edges, const Span< bool > sharp_faces, int *r_totgroup, const bool use_bitflags, const bool use_boundary_vertices_for_bitflags)
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
void BKE_mesh_loop_islands_clear(MeshIslandStore *island_store)
unsigned int BLI_bitmap
Definition BLI_bitmap.hh:15
static bool mesh_calc_islands_loop_face_uv(const int totedge, const Span< bool > uv_seams, const OffsetIndices< int > faces, const Span< int > corner_edges, MeshIslandStore *r_island_store)
void BKE_mesh_loop_islands_free(MeshIslandStore *island_store)
void BKE_mesh_origindex_map_create(MeshElemMap **r_map, int **r_mem, int totsource, const int *final_origindex, int totfinal)
FunctionRef< bool(int face_index, int corner, int edge_index, int edge_user_count, const Span< int > edge_face_map_elem)> MeshRemap_CheckIslandBoundary
bool BKE_mesh_calc_islands_loop_face_edgeseam(Span< float3 > vert_positions, Span< int2 > edges, Span< bool > uv_seams, OffsetIndices< int > faces, Span< int > corner_verts, Span< int > corner_edges, MeshIslandStore *r_island_store)
void BKE_mesh_loop_islands_init(MeshIslandStore *island_store, short item_type, int items_num, short island_type, short innercut_type)
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
int * BKE_mesh_calc_smoothgroups_bitflags(int edges_num, int verts_num, OffsetIndices< int > faces, Span< int > corner_edges, Span< int > corner_verts, Span< bool > sharp_edges, Span< bool > sharp_faces, bool use_boundary_vertices_for_bitflags, int *r_totgroup)
void vert(const int vert_id, float4 &position)
#define fabsf