Blender V5.3
pbvh_uv_islands.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
10#include "BLI_bit_span_ops.hh"
11#include "BLI_bit_vector.hh"
12#include "BLI_map.hh"
13#include "BLI_math_geom_c.hh"
14#include "BLI_math_matrix.hh"
15#include "BLI_math_vector_c.hh"
16#include "BLI_offset_indices.hh"
17#include "BLI_task.hh"
18#include "BLI_vector_set.hh"
19
20#include "BKE_mesh.hh"
21#include "BKE_mesh_mapping.hh"
22
23#include "PRF_profile.hh"
24
26#include "pbvh_uv_islands.hh"
27
28#include <atomic>
29#include <cmath>
30#include <iostream>
31#include <optional>
32#include <queue>
33#include <sstream>
34
36
37static void uv_edge_append_to_uv_verts(UVIsland &island, const int uv_edge_i)
38{
39 for (const int uv_vert_i : island.uv_edges[uv_edge_i].verts) {
40 island.uv_verts[uv_vert_i].uv_edges.append_non_duplicates(uv_edge_i);
41 }
42}
43
44static void uv_primitive_append_to_uv_edges(UVIsland &island, UVPrimitive &uv_primitive)
45{
46 for (const int uv_edge_i : uv_primitive.edges) {
47 island.uv_edges[uv_edge_i].uv_primitive_indices.append_non_duplicates(
48 uv_primitive.primitive_i);
49 }
50}
51
52static void uv_primitive_append_to_uv_verts(UVIsland &island, UVPrimitive &uv_primitive)
53{
54 for (const int uv_edge_i : uv_primitive.edges) {
55 uv_edge_append_to_uv_verts(island, uv_edge_i);
56 }
57}
58
59/* -------------------------------------------------------------------- */
62
63static int primitive_get_other_uv_vert(const MeshData &mesh_data,
64 const int3 &tri,
65 const int v1,
66 const int v2)
67{
68 const Span<int> corner_verts = mesh_data.corner_verts;
69 BLI_assert(ELEM(v1, corner_verts[tri[0]], corner_verts[tri[1]], corner_verts[tri[2]]));
70 BLI_assert(ELEM(v2, corner_verts[tri[0]], corner_verts[tri[1]], corner_verts[tri[2]]));
71 for (const int corner : {tri[0], tri[1], tri[2]}) {
72 const int vert = corner_verts[corner];
73 if (!ELEM(vert, v1, v2)) {
74 return vert;
75 }
76 }
77 return -1;
78}
79
80static int get_uv_corner(const MeshData &mesh_data, const int3 &tri, const int vert)
81{
82 for (const int corner : {tri[0], tri[1], tri[2]}) {
83 if (mesh_data.corner_verts[corner] == vert) {
84 return corner;
85 }
86 }
88 return tri[0];
89}
90
92
93/* -------------------------------------------------------------------- */
96
98static bool tri_contains_verts(const MeshData &mesh_data,
99 const int tri_i,
100 const int v0,
101 const int v1)
102{
103 const int3 &tri = mesh_data.corner_tris[tri_i];
104 bool has_0 = false;
105 bool has_1 = false;
106 for (int k = 0; k < 3; k++) {
107 const int v = mesh_data.corner_verts[tri[k]];
108 has_0 |= v == v0;
109 has_1 |= v == v1;
110 }
111 return has_0 && has_1;
112}
113
115static int face_corner_of_edge(const MeshData &mesh_data, const int face, const int edge_i)
116{
117 for (const int corner : mesh_data.faces[face]) {
118 if (mesh_data.corner_edges[corner] == edge_i) {
119 return corner;
120 }
121 }
122 return -1;
123}
124
125static bool faces_have_shared_uv_edge(const MeshData &mesh_data,
126 const int face_0,
127 const int face_1,
128 const int edge_i)
129{
130 const int c0 = face_corner_of_edge(mesh_data, face_0, edge_i);
131 const int c1 = face_corner_of_edge(mesh_data, face_1, edge_i);
132 if (c0 == -1 || c1 == -1) {
133 return false;
134 }
135 const int c0_next = mesh::face_corner_next(mesh_data.faces[face_0], c0);
136 const int c1_next = mesh::face_corner_next(mesh_data.faces[face_1], c1);
137
138 const Span<float2> uv_map = mesh_data.uv_map;
139 if (mesh_data.corner_verts[c0] == mesh_data.corner_verts[c1]) {
140 return uv_map[c0] == uv_map[c1] && uv_map[c0_next] == uv_map[c1_next];
141 }
142 return uv_map[c0] == uv_map[c1_next] && uv_map[c0_next] == uv_map[c1];
143}
144
145static void mesh_data_init_topology(MeshData &mesh_data)
146{
148 mesh_data.corner_edges,
149 mesh_data.mesh_edges.size(),
150 mesh_data.edge_to_face_offsets,
151 mesh_data.edge_to_face_indices);
152}
153
155{
156 /* Group primitives into UV islands, connected through shared UV edges. */
157 const int64_t primitives_num = mesh_data.corner_tris.size();
158 mesh_data.uv_island_ids.reinitialize(primitives_num);
159 mesh_data.uv_edge_is_border = Array<bool>(mesh_data.mesh_edges.size(), false);
160
161 AtomicDisjointSet disjoint_set(primitives_num);
162
163 /* Initialize with one island per face. */
164 threading::parallel_for(mesh_data.faces.index_range(), 1024, [&](const IndexRange range) {
165 for (const int face : range) {
166 const IndexRange tris = mesh::face_triangles_range(mesh_data.faces, int(face));
167 for (const int tri : tris.drop_front(1)) {
168 disjoint_set.join(tris.first(), tri);
169 }
170 }
171 });
172
173 /* Merge the islands of two faces when their UVs match along an edge,
174 * and store which edges are on the border. */
175 threading::parallel_for(mesh_data.mesh_edges.index_range(), 1024, [&](const IndexRange range) {
176 for (const int edge_i : range) {
177 const Span<int> edge_faces = mesh_data.edge_to_face_map[edge_i];
178 if (edge_faces.size() == 2 &&
179 faces_have_shared_uv_edge(mesh_data, edge_faces[0], edge_faces[1], edge_i))
180 {
181 disjoint_set.join(mesh::face_triangles_range(mesh_data.faces, edge_faces[0]).first(),
182 mesh::face_triangles_range(mesh_data.faces, edge_faces[1]).first());
183 }
184 else {
185 const bool is_loose_edge = edge_faces.is_empty();
186 mesh_data.uv_edge_is_border[edge_i] = !is_loose_edge;
187 }
188 }
189 });
190
191 return disjoint_set.calc_reduced_ids(mesh_data.uv_island_ids);
192}
193
194static void mesh_data_init(MeshData &mesh_data)
195{
197 mesh_data_init_topology(mesh_data);
199}
200
220
222
223/* -------------------------------------------------------------------- */
226
227static void uv_vert_init_flags(UVVert &uv_vert)
228{
229 uv_vert.flags.is_border = false;
230 uv_vert.flags.is_extended = false;
231}
232
234{
235 uv_vert_init_flags(*this);
236}
237
238UVVert::UVVert(const MeshData &mesh_data, const int corner)
239 : vert(mesh_data.corner_verts[corner]), uv(mesh_data.uv_map[corner])
240{
241 uv_vert_init_flags(*this);
242}
243
245
246/* -------------------------------------------------------------------- */
249
250bool UVEdge::has_same_verts(const UVIsland &island, const int vert1, const int vert2) const
251{
252 return (island.uv_verts[verts[0]].vert == vert1 && island.uv_verts[verts[1]].vert == vert2) ||
253 (island.uv_verts[verts[0]].vert == vert2 && island.uv_verts[verts[1]].vert == vert1);
254}
255
256bool UVEdge::has_same_verts(const UVIsland &island, const int2 &edge) const
257{
258 return has_same_verts(island, edge[0], edge[1]);
259}
260
261int UVEdge::get_other_uv_vert(const UVIsland &island, const int vert)
262{
263 if (island.uv_verts[verts[0]].vert == vert) {
264 return verts[1];
265 }
266 return verts[0];
267}
268
270
271/* -------------------------------------------------------------------- */
274int UVIsland::lookup(const UVVert &vert)
275{
276 const int vert_index = vert.vert;
277 const Vector<int> &verts = uv_vert_lookup.lookup_or_add_default(vert_index);
278 for (const int uv_vert_i : verts) {
279 if (uv_verts[uv_vert_i].uv == vert.uv) {
280 return uv_vert_i;
281 }
282 }
283 return -1;
284}
285
287{
288 const int found_vert = lookup(vert);
289 if (found_vert != -1) {
290 return found_vert;
291 }
292
293 uv_verts.append(vert);
294 uv_verts.last().uv_edges.clear();
295 /* v is already a key. Ensured by UVIsland::lookup in this method. */
296 uv_vert_lookup.lookup(vert.vert).append(uv_verts.size() - 1);
297 return uv_verts.size() - 1;
298}
299
300int UVIsland::lookup(const UVEdge &edge)
301{
302 const UVVert &edge_vert_0 = this->uv_verts[edge.verts[0]];
303 const UVVert &edge_vert_1 = this->uv_verts[edge.verts[1]];
304 const int found_vert_i = lookup(edge_vert_0);
305 if (found_vert_i == -1) {
306 return -1;
307 }
308 const UVVert &found_vert = this->uv_verts[found_vert_i];
309 for (const int uv_edge_i : found_vert.uv_edges) {
310 UVEdge *e = &this->uv_edges[uv_edge_i];
311 const int other_vert_i = e->get_other_uv_vert(*this, found_vert.vert);
312 const UVVert &other_vert = this->uv_verts[other_vert_i];
313 if (other_vert.vert == edge_vert_1.vert && other_vert.uv == edge_vert_1.uv) {
314 return uv_edge_i;
315 }
316 }
317 return -1;
318}
319
321{
322 int found_edge = lookup(edge);
323 if (found_edge != -1) {
324 return found_edge;
325 }
326
327 uv_edges.append(edge);
328 UVEdge *result = &uv_edges.last();
329 result->uv_primitive_indices.clear();
330 return uv_edges.size() - 1;
331}
332
333static UVPrimitive *add_primitive(const MeshData &mesh_data,
334 UVIsland &uv_island,
335 const int primitive_i,
336 const Span<bool> tri_corner_near_border)
337{
338 UVPrimitive uv_primitive(primitive_i);
339 const int3 &tri = mesh_data.corner_tris[primitive_i];
340 uv_island.uv_primitives.append(uv_primitive);
341 UVPrimitive *uv_primitive_ptr = &uv_island.uv_primitives.last();
342 for (const int i : IndexRange(3)) {
343 const int corner_1 = tri[i];
344 const int corner_2 = tri[(i + 1) % 3];
345 UVEdge uv_edge_template;
346 uv_edge_template.is_border = tri_corner_near_border[int64_t(primitive_i) * 3 + i];
347 uv_edge_template.verts[0] = uv_island.lookup_or_create(UVVert(mesh_data, corner_1));
348 uv_edge_template.verts[1] = uv_island.lookup_or_create(UVVert(mesh_data, corner_2));
349 const int uv_edge_i = uv_island.lookup_or_create(uv_edge_template);
350 uv_primitive_ptr->edges[i] = uv_edge_i;
351 uv_edge_append_to_uv_verts(uv_island, uv_edge_i);
352 uv_island.uv_edges[uv_edge_i].uv_primitive_indices.append(uv_primitive_ptr->primitive_i);
353 }
354 return uv_primitive_ptr;
355}
356
357std::optional<UVBorder> extract_border_from_edges(const UVIsland &island,
359 MutableBoundedBitSpan borders_used);
360
362{
364 /* Lookup all borders of the island. */
366 for (const int uv_prim_i : uv_primitives.index_range()) {
367 const UVPrimitive &prim = uv_primitives[uv_prim_i];
368 for (const int uv_edge_i : prim.edges) {
369 const UVEdge &edge = this->uv_edges[uv_edge_i];
370 if (edge.is_border) {
371 edges.append(UVBorderEdge(uv_edge_i, uv_prim_i));
372 }
373 }
374 }
375
376 BitVector<128> borders_used(edges.size(), false);
377 while (true) {
378 std::optional<UVBorder> border = extract_border_from_edges(*this, edges, borders_used);
379 if (!border.has_value()) {
380 break;
381 }
382 if (!border->is_ccw(*this)) {
383 border->flip_order();
384 }
385 borders.append(std::move(*border));
386 }
387}
388
394
395 struct {
396 bool found : 1;
398
399 FanSegment(const MeshData &mesh_data, const int primitive_index, const int3 tri, int vert)
401 {
402 flags.found = false;
403
404 /* Reorder so the first edge starts with the given vert. */
405 if (mesh_data.corner_verts[tri[1]] == vert) {
406 vert_order[0] = 1;
407 vert_order[1] = 2;
408 vert_order[2] = 0;
409 }
410 else if (mesh_data.corner_verts[tri[2]] == vert) {
411 vert_order[0] = 2;
412 vert_order[1] = 0;
413 vert_order[2] = 1;
414 }
415 else {
416 BLI_assert(mesh_data.corner_verts[tri[0]] == vert);
417 vert_order[0] = 0;
418 vert_order[1] = 1;
419 vert_order[2] = 2;
420 }
421 }
422
423 void print_debug(const MeshData &mesh_data) const
424 {
425 std::stringstream ss;
426 ss << " v1:" << mesh_data.corner_verts[tri[vert_order[0]]];
427 ss << " v2:" << mesh_data.corner_verts[tri[vert_order[1]]];
428 ss << " v3:" << mesh_data.corner_verts[tri[vert_order[2]]];
429 if (flags.found) {
430 ss << " *found";
431 }
432 ss << "\n";
433 std::cout << ss.str();
434 }
435};
436
437struct Fan {
438 /* Blades of the fan. */
440
441 struct {
446 bool is_manifold : 1;
447
449
450 /* Other vertices in the fan triangle. */
451 static int2 other_fan_edge_verts(const MeshData &mesh_data, const int vert, const int tri_i)
452 {
453 const int3 &tri = mesh_data.corner_tris[tri_i];
454 int2 verts;
455 int n = 0;
456 for (int k = 0; k < 3; k++) {
457 const int v = mesh_data.corner_verts[tri[k]];
458 if (v != vert) {
459 verts[n++] = v;
460 }
461 }
462 return verts;
463 }
464
465 /* Adjacent triangle in the fan, sharing (vert, other_vert) edge. Returns -1 if there is none. */
466 static int adjacent_tri(const MeshData &mesh_data,
467 const Span<int> tris,
468 const int vert,
469 const int other_vert,
470 const int tri_i)
471 {
472 int result = -1;
473 for (const int t : tris) {
474 if (t != tri_i && tri_contains_verts(mesh_data, t, vert, other_vert)) {
475 if (result != -1) {
476 return -1;
477 }
478 result = t;
479 }
480 }
481 return result;
482 }
483
484 Fan(const MeshData &mesh_data, const int vert)
485 {
486 flags.is_manifold = true;
487
488 /* Gather triangles adjacent to the vertex. */
489 Vector<int, 16> tris;
490 for (const int face : mesh_data.vert_to_face_map[vert]) {
491 for (const int t : mesh::face_triangles_range(mesh_data.faces, face)) {
492 const int3 &tri = mesh_data.corner_tris[t];
493 if (ELEM(vert,
494 mesh_data.corner_verts[tri[0]],
495 mesh_data.corner_verts[tri[1]],
496 mesh_data.corner_verts[tri[2]]))
497 {
498 tris.append(t);
499 }
500 }
501 }
502 if (tris.is_empty()) {
503 flags.is_manifold = false;
504 return;
505 }
506
507 /* Walk the fan around the vertex. */
508 const int start_tri = tris.first();
509 int current_tri = start_tri;
510 int incoming_vert = other_fan_edge_verts(mesh_data, vert, start_tri)[0];
511 segments.append(FanSegment(mesh_data, start_tri, mesh_data.corner_tris[start_tri], vert));
512
513 while (true) {
514 const int2 verts = other_fan_edge_verts(mesh_data, vert, current_tri);
515 const int outgoing_vert = incoming_vert == verts[0] ? verts[1] : verts[0];
516 const int next_tri = adjacent_tri(mesh_data, tris, vert, outgoing_vert, current_tri);
517 if (next_tri == -1) {
518 /* Reached a mesh boundary or non-manifold edge. */
519 flags.is_manifold = false;
520 break;
521 }
522 if (next_tri == start_tri) {
523 break;
524 }
525 segments.append(FanSegment(mesh_data, next_tri, mesh_data.corner_tris[next_tri], vert));
526 incoming_vert = outgoing_vert;
527 current_tri = next_tri;
528 }
529 }
530
532 {
533 int result = 0;
534 for (const FanSegment &fan_edge : segments) {
535 if (!fan_edge.flags.found) {
536 result++;
537 }
538 }
539 return result;
540 }
541
542 void mark_already_added_segments(const UVIsland &uv_island, const UVVert &uv_vert)
543 {
544 /* Go over all fan edges to find if they can be found as primitive around the uv vertex. */
545 for (FanSegment &fan_edge : segments) {
546 fan_edge.flags.found = false;
547 for (const int uv_edge_i : uv_vert.uv_edges) {
548 const UVEdge &uv_edge = uv_island.uv_edges[uv_edge_i];
549 if (uv_edge.uv_primitive_indices.contains(fan_edge.primitive_index)) {
550 fan_edge.flags.found = true;
551 break;
552 }
553 }
554 }
555 }
556
557#ifndef NDEBUG
562 bool contains_vert_on_outside(const MeshData &mesh_data, const int vert) const
563 {
564 for (const FanSegment &segment : segments) {
565 int v2 = mesh_data.corner_verts[segment.tri[segment.vert_order[1]]];
566 if (vert == v2) {
567 return true;
568 }
569 }
570 return false;
571 }
572
573#endif
574
575 static bool is_path_valid(const Span<FanSegment *> path,
576 const MeshData &mesh_data,
577 const int from_vert,
578 const int to_vert)
579 {
580 int current_vert = from_vert;
581 for (FanSegment *segment : path) {
582 int v1 = mesh_data.corner_verts[segment->tri[segment->vert_order[1]]];
583 int v2 = mesh_data.corner_verts[segment->tri[segment->vert_order[2]]];
584 if (!ELEM(current_vert, v1, v2)) {
585 return false;
586 }
587 current_vert = v1 == current_vert ? v2 : v1;
588 }
589 return current_vert == to_vert;
590 }
591
599 const MeshData &mesh_data,
600 const int from_vert,
601 const int to_vert,
602 const bool reversed)
603 {
604 const int from_vert_order = 1;
605 const int to_vert_order = 2;
606 const int index_increment = reversed ? -1 : 1;
607
609 result.reserve(edge_order.size());
610 int index = 0;
611 while (true) {
612 FanSegment *segment = edge_order[index];
613 int v2 = mesh_data.corner_verts[segment->tri[segment->vert_order[from_vert_order]]];
614 if (v2 == from_vert) {
615 break;
616 }
617 index = (index + index_increment + edge_order.size()) % edge_order.size();
618 }
619
620 while (true) {
621 FanSegment *segment = edge_order[index];
622 result.append(segment);
623
624 int v3 = mesh_data.corner_verts[segment->tri[segment->vert_order[to_vert_order]]];
625 if (v3 == to_vert) {
626 break;
627 }
628
629 index = (index + index_increment + edge_order.size()) % edge_order.size();
630 }
631
632 return result;
633 }
634
641 static int64_t score(const Span<FanSegment *> solution)
642 {
643 int64_t not_visited_steps = 0;
644 for (FanSegment *segment : solution) {
645 if (!segment->flags.found) {
646 not_visited_steps++;
647 }
648 }
649 return solution.size() - not_visited_steps;
650 }
651
653 const int from_vert,
654 const int to_vert)
655 {
656 BLI_assert_msg(contains_vert_on_outside(mesh_data, from_vert),
657 "Inconsistency detected, `from_vert` isn't part of the outside of the fan.");
658 BLI_assert_msg(contains_vert_on_outside(mesh_data, to_vert),
659 "Inconsistency detected, `to_vert` isn't part of the outside of the fan.");
660 if (to_vert == from_vert) {
661 return Vector<FanSegment *>();
662 }
663
666 edges[index] = &segments[index];
667 }
668
669 Vector<FanSegment *> winding_1 = path_between(edges, mesh_data, from_vert, to_vert, false);
670 Vector<FanSegment *> winding_2 = path_between(edges, mesh_data, from_vert, to_vert, true);
671
672 bool winding_1_valid = is_path_valid(winding_1, mesh_data, from_vert, to_vert);
673 bool winding_2_valid = is_path_valid(winding_2, mesh_data, from_vert, to_vert);
674
675 if (winding_1_valid && !winding_2_valid) {
676 return winding_1;
677 }
678 if (!winding_1_valid && winding_2_valid) {
679 return winding_2;
680 }
681 if (!winding_1_valid && !winding_2_valid) {
682 BLI_assert_msg(false, "Both solutions aren't valid.");
683 return Vector<FanSegment *>();
684 }
685 if (score(winding_1) < score(winding_2)) {
686 return winding_1;
687 }
688 return winding_2;
689 }
690
691 void print_debug(const MeshData &mesh_data) const
692 {
693 for (const FanSegment &segment : segments) {
694 segment.print_debug(mesh_data);
695 }
696 std::cout << "\n";
697 }
698};
699
700static void add_uv_primitive_shared_uv_edge(const MeshData &mesh_data,
701 UVIsland &island,
702 const UVVert &connected_vert_1,
703 const UVVert &connected_vert_2,
704 float2 uv_unconnected,
705 const int mesh_primitive_i)
706{
707 UVPrimitive prim1(mesh_primitive_i);
708 const int3 &tri = mesh_data.corner_tris[mesh_primitive_i];
709 /* Extract data before vector reallocation invalidates existing UVVert references. */
710 const int mesh_vert_1 = connected_vert_1.vert;
711 const int mesh_vert_2 = connected_vert_2.vert;
712 const float2 uv_1 = connected_vert_1.uv;
713 const float2 uv_2 = connected_vert_2.uv;
714
715 const int other_vert_i = primitive_get_other_uv_vert(mesh_data, tri, mesh_vert_1, mesh_vert_2);
716 UVVert vert_template;
717 vert_template.uv = uv_unconnected;
718 vert_template.vert = other_vert_i;
719 const int uv_vert_i = island.lookup_or_create(vert_template);
720
721 const int corner_1 = get_uv_corner(mesh_data, tri, mesh_vert_1);
722 vert_template.uv = uv_1;
723 vert_template.vert = mesh_data.corner_verts[corner_1];
724 const int uv_vert_1_i = island.lookup_or_create(vert_template);
725
726 const int corner_2 = get_uv_corner(mesh_data, tri, mesh_vert_2);
727 vert_template.uv = uv_2;
728 vert_template.vert = mesh_data.corner_verts[corner_2];
729 const int uv_vert_2_i = island.lookup_or_create(vert_template);
730
731 UVEdge edge_template;
732 edge_template.verts[0] = uv_vert_1_i;
733 edge_template.verts[1] = uv_vert_2_i;
734 prim1.edges[0] = island.lookup_or_create(edge_template);
735 edge_template.verts[0] = uv_vert_2_i;
736 edge_template.verts[1] = uv_vert_i;
737 prim1.edges[1] = island.lookup_or_create(edge_template);
738 edge_template.verts[0] = uv_vert_i;
739 edge_template.verts[1] = uv_vert_1_i;
740 prim1.edges[2] = island.lookup_or_create(edge_template);
741 uv_primitive_append_to_uv_edges(island, prim1);
742 uv_primitive_append_to_uv_verts(island, prim1);
743 island.uv_primitives.append(prim1);
744}
745
749static int find_fill_primitive(const MeshData &mesh_data,
750 const UVIsland &island,
751 UVBorderCorner &corner)
752{
753 if (corner.first->get_uv_vert(island, 1) != corner.second->get_uv_vert(island, 0)) {
754 return -1;
755 }
756 if (corner.first->get_uv_vert(island, 0) == corner.second->get_uv_vert(island, 1)) {
757 return -1;
758 }
759 const int shared_vert = island.uv_verts[corner.second->get_uv_vert(island, 0)].vert;
760 const UVEdge &corner_edge = island.uv_edges[corner.first->uv_edge_i];
761 const int2 edge(island.uv_verts[corner_edge.verts[0]].vert,
762 island.uv_verts[corner_edge.verts[1]].vert);
763 const int target_vert = island.uv_verts[corner.second->get_uv_vert(island, 1)].vert;
764
765 /* Find the triangle around the shared vertex whose edge is `corner.first` and
766 * remaining vertex is the corner's outer vertex. */
767 for (const int face : mesh_data.vert_to_face_map[shared_vert]) {
768 for (const int primitive_i : mesh::face_triangles_range(mesh_data.faces, int(face))) {
769 if (!tri_contains_verts(mesh_data, primitive_i, edge[0], edge[1])) {
770 continue;
771 }
772 const int3 &tri = mesh_data.corner_tris[primitive_i];
773 const int other_vert = primitive_get_other_uv_vert(mesh_data, tri, edge[0], edge[1]);
774 if (other_vert == target_vert) {
775 return primitive_i;
776 }
777 }
778 }
779 return -1;
780}
781
782static void add_uv_primitive_fill(UVIsland &island,
783 const int uv_vert1_i,
784 const int uv_vert2_i,
785 const int uv_vert3_i,
786 const int fill_primitive_i)
787{
788 UVPrimitive uv_primitive(fill_primitive_i);
789 UVEdge edge_template;
790 edge_template.verts[0] = uv_vert1_i;
791 edge_template.verts[1] = uv_vert2_i;
792 uv_primitive.edges[0] = island.lookup_or_create(edge_template);
793 edge_template.verts[0] = uv_vert2_i;
794 edge_template.verts[1] = uv_vert3_i;
795 uv_primitive.edges[1] = island.lookup_or_create(edge_template);
796 edge_template.verts[0] = uv_vert3_i;
797 edge_template.verts[1] = uv_vert1_i;
798 uv_primitive.edges[2] = island.lookup_or_create(edge_template);
799 uv_primitive_append_to_uv_edges(island, uv_primitive);
800 uv_primitive_append_to_uv_verts(island, uv_primitive);
801 island.uv_primitives.append(uv_primitive);
802}
803
804static void extend_at_vert(const MeshData &mesh_data,
805 UVIsland &island,
806 UVBorderCorner &corner,
807 float min_uv_distance,
808 int64_t &order_counter,
809 Vector<UVBorderEdge *> &r_modified)
810{
811
812 int border_index = corner.first->border_index;
813 UVBorder &border = island.borders[border_index];
814 if (!corner.connected_in_mesh(island)) {
815 return;
816 }
817
818 UVBorderEdge *after_edge = corner.second->next;
819
820 const int uv_vert_i = corner.second->get_uv_vert(island, 0);
821 const UVVert uv_vert = island.uv_verts[uv_vert_i];
822 Fan fan(mesh_data, uv_vert.vert);
823 if (!fan.flags.is_manifold) {
824 return;
825 }
826 fan.mark_already_added_segments(island, uv_vert);
827 int num_to_add = fan.count_edges_not_added();
828
829 /* In 3d space everything can connected, but in uv space it may not.
830 * in this case in the space between we should extract the primitives to be added
831 * from the fan. */
832 Vector<FanSegment *> winding_solution = fan.best_path_between(
833 mesh_data,
834 island.uv_verts[corner.first->get_uv_vert(island, 0)].vert,
835 island.uv_verts[corner.second->get_uv_vert(island, 1)].vert);
836
837 /*
838 * When all edges are already added and its winding solution contains one segment to be added,
839 * the segment should be split into two segments in order one for both sides.
840 *
841 * Although the tri_fill can fill the missing segment it could lead to a squashed
842 * triangle when the corner angle is near 180 degrees. In order to fix this we will
843 * always add two segments both using the same fill primitive.
844 */
845 if (winding_solution.size() < 2 && (num_to_add == 0 || corner.angle > 2.0f)) {
846 int fill_primitive_1_i = island.uv_primitives[corner.second->uv_primitive].primitive_i;
847 int fill_primitive_2_i = island.uv_primitives[corner.first->uv_primitive].primitive_i;
848
849 const int fill_primitive_i = winding_solution.size() == 1 ?
850 winding_solution[0]->primitive_index :
851 find_fill_primitive(mesh_data, island, corner);
852
853 if (fill_primitive_i != -1) {
854 fill_primitive_1_i = fill_primitive_i;
855 fill_primitive_2_i = fill_primitive_i;
856 }
857
858 float2 center_uv = corner.uv(island, 0.5f, min_uv_distance);
860 island,
861 island.uv_verts[corner.first->get_uv_vert(island, 1)],
862 island.uv_verts[corner.first->get_uv_vert(island, 0)],
863 center_uv,
864 fill_primitive_1_i);
865 const int new_prim_1_i = island.uv_primitives.size() - 1;
867 island,
868 island.uv_verts[corner.second->get_uv_vert(island, 0)],
869 island.uv_verts[corner.second->get_uv_vert(island, 1)],
870 center_uv,
871 fill_primitive_2_i);
872 const int new_prim_2_i = island.uv_primitives.size() - 1;
873
874 /* Update border after adding the new geometry. */
875 {
876 UVBorderEdge *border_edge = corner.first;
877 border_edge->uv_primitive = new_prim_1_i;
878 border_edge->uv_edge_i = island.uv_primitives[border_edge->uv_primitive].get_uv_edge(
879 island, island.uv_verts[corner.first->get_uv_vert(island, 0)].uv, center_uv);
880 border_edge->reverse_order =
881 island.uv_verts[island.uv_edges[border_edge->uv_edge_i].verts[0]].uv == center_uv;
882 }
883 {
884 UVBorderEdge *border_edge = corner.second;
885 border_edge->uv_primitive = new_prim_2_i;
886 border_edge->uv_edge_i = island.uv_primitives[border_edge->uv_primitive].get_uv_edge(
887 island, island.uv_verts[corner.second->get_uv_vert(island, 1)].uv, center_uv);
888 border_edge->reverse_order =
889 island.uv_verts[island.uv_edges[border_edge->uv_edge_i].verts[1]].uv == center_uv;
890 }
891
892 r_modified.append(corner.first);
893 r_modified.append(after_edge);
894 }
895 else {
896 int current_edge = corner.first->uv_edge_i;
897 Vector<UVBorderEdge> new_border_edges;
898
899 num_to_add = winding_solution.size();
900 for (int64_t segment_index : winding_solution.index_range()) {
901
902 float2 old_uv =
903 island.uv_verts[island.uv_edges[current_edge].get_other_uv_vert(island, uv_vert.vert)]
904 .uv;
905 int shared_edge_vert =
906 island.uv_verts[island.uv_edges[current_edge].get_other_uv_vert(island, uv_vert.vert)]
907 .vert;
908
909 float factor = (segment_index + 1.0f) / num_to_add;
910 float2 new_uv = corner.uv(island, factor, min_uv_distance);
911
912 FanSegment &segment = *winding_solution[segment_index];
913
914 const int fill_primitive_i = segment.primitive_index;
915 const int3 &tri_fill = mesh_data.corner_tris[fill_primitive_i];
916 const int other_prim_vert = primitive_get_other_uv_vert(
917 mesh_data, tri_fill, uv_vert.vert, shared_edge_vert);
918
919 UVVert uv_vert_template;
920 uv_vert_template.vert = uv_vert.vert;
921 uv_vert_template.uv = uv_vert.uv;
922 const int vert_1_i = island.lookup_or_create(uv_vert_template);
923 uv_vert_template.vert = shared_edge_vert;
924 uv_vert_template.uv = old_uv;
925 const int vert_2_i = island.lookup_or_create(uv_vert_template);
926 uv_vert_template.vert = other_prim_vert;
927 uv_vert_template.uv = new_uv;
928 const int vert_3_i = island.lookup_or_create(uv_vert_template);
929
930 add_uv_primitive_fill(island, vert_1_i, vert_2_i, vert_3_i, fill_primitive_i);
931
932 const int new_prim_i = island.uv_primitives.size() - 1;
933 current_edge = island.uv_primitives[new_prim_i].get_uv_edge(
934 island, uv_vert.vert, other_prim_vert);
935 UVBorderEdge new_border(
936 island.uv_primitives[new_prim_i].get_uv_edge(island, shared_edge_vert, other_prim_vert),
937 new_prim_i);
938 new_border_edges.append(new_border);
939 }
940
941 /* Replace two border edges with new_border_edges in the linked list. */
942 corner.first->removed = true;
943 corner.second->removed = true;
944 UVBorderEdge *prev_edge = corner.first->prev;
945 for (UVBorderEdge &new_border : new_border_edges) {
946 border.edges_extend_border.append(new_border);
947 UVBorderEdge *new_edge = &border.edges_extend_border.last();
948 new_edge->border_index = border_index;
949 new_edge->order = order_counter++;
950 new_edge->removed = false;
951 new_edge->prev = prev_edge;
952 prev_edge->next = new_edge;
953 prev_edge = new_edge;
954 r_modified.append(new_edge);
955 }
956 prev_edge->next = after_edge;
957 after_edge->prev = prev_edge;
958 r_modified.append(after_edge);
959 }
960}
961
962/* Marks vertices that can be extended. Only vertices that are part of a border can be extended. */
964{
965 for (UVVert &uv_vert : island.uv_verts) {
966 uv_vert.flags.is_border = false;
967 uv_vert.flags.is_extended = false;
968 }
969 for (const UVBorder &border : island.borders) {
970 for (const UVBorderEdge &border_edge : border.edges) {
971 const UVEdge &uv_edge = island.uv_edges[border_edge.uv_edge_i];
972 island.uv_verts[uv_edge.verts[0]].flags.is_border = true;
973 island.uv_verts[uv_edge.verts[1]].flags.is_border = true;
974 }
975 }
976}
977
978void UVIsland::extend_border(const MeshData &mesh_data,
979 const UVIslandsMask &mask,
980 const short island_index)
981{
984
985 /* Set up double linked list and stable order ID. */
986 int64_t order_counter = 0;
987 for (const int64_t border_index : borders.index_range()) {
988 borders[border_index].setup_links(border_index);
989 for (UVBorderEdge &border_edge : borders[border_index].edges) {
990 border_edge.order = order_counter++;
991 }
992 }
993
994 /* Process the border ordered from smallest to largest angle. On high poly meshes this
995 * border can be very long, so use priority queue to avoid quadratic time complexity. */
996 struct HeapEntry {
997 float angle;
998 UVBorderEdge *edge;
999
1000 bool operator<(const HeapEntry &other) const
1001 {
1002 if (angle != other.angle) {
1003 return angle > other.angle;
1004 }
1005 return edge->order > other.edge->order;
1006 }
1007 };
1008 std::priority_queue<HeapEntry> queue;
1009
1010 auto queue_edge = [&](const float angle, UVBorderEdge &border_edge) {
1011 /* Guard against NaN causing infinite loop, leave such borders without extension. */
1012 if (std::isfinite(angle)) {
1013 queue.push({angle, &border_edge});
1014 }
1015 };
1016
1017 /* Queue initial border edges. */
1018 for (UVBorder &border : borders) {
1019 for (UVBorderEdge &border_edge : border.edges) {
1020 const float angle = border.outside_angle(*this, border_edge);
1021 queue_edge(angle, border_edge);
1022 }
1023 }
1024
1025 /* Process border edges in order. */
1026 Vector<UVBorderEdge *> modified_edges;
1027 while (!queue.empty()) {
1028 const HeapEntry entry = queue.top();
1029 queue.pop();
1030 UVBorderEdge *border_edge = entry.edge;
1031 if (!border_edge->is_extendable(*this)) {
1032 continue;
1033 }
1034
1035 const int uv_vert_i = border_edge->get_uv_vert(*this, 0);
1036 float2 uv_vert_uv = uv_verts[uv_vert_i].uv;
1037 UVBorder &border = borders[border_edge->border_index];
1038
1039 /* If the angle changed, re-queue with new angle. */
1040 const float angle = border.outside_angle(*this, *border_edge);
1041 if (angle != entry.angle) {
1042 queue_edge(angle, *border_edge);
1043 continue;
1044 }
1045
1046 UVBorderCorner extension_corner(border_edge->prev, border_edge, angle);
1047
1048 /* Found corner is outside the mask, the corner should not be considered for extension. */
1049 const UVIslandsMask::Tile *tile = mask.find_tile(uv_vert_uv);
1050 if (tile && tile->is_masked(island_index, uv_vert_uv)) {
1051 modified_edges.clear();
1052 extend_at_vert(mesh_data,
1053 *this,
1054 extension_corner,
1055 tile->get_pixel_size_in_uv_space() * 2.0f,
1056 order_counter,
1057 modified_edges);
1058
1059 /* Queue modified and newly generated edges. */
1060 for (UVBorderEdge *modified_edge : modified_edges) {
1061 if (modified_edge->is_extendable(*this)) {
1062 UVBorder &modified_border = borders[modified_edge->border_index];
1063 const float angle = modified_border.outside_angle(*this, *modified_edge);
1064 queue_edge(angle, *modified_edge);
1065 }
1066 }
1067 }
1068 /* Mark that the vert is extended. */
1069 this->uv_verts[uv_vert_i].flags.is_extended = true;
1070 }
1071}
1072
1073void UVIsland::print_debug(const MeshData &mesh_data) const
1074{
1075 std::stringstream ss;
1076 ss << "#### Start UVIsland ####\n";
1077 ss << "import bpy\n";
1078 ss << "import bpy_extras.object_utils\n";
1079 ss << "import mathutils\n";
1080
1081 ss << "uvisland_vertices = [\n";
1082 for (const float3 &vert_position : mesh_data.vert_positions) {
1083 ss << " mathutils.Vector((" << vert_position.x << ", " << vert_position.y << ", "
1084 << vert_position.z << ")),\n";
1085 }
1086 ss << "]\n";
1087
1088 ss << "uvisland_edges = []\n";
1089
1090 ss << "uvisland_faces = [\n";
1091 for (const UVPrimitive &uvprimitive : uv_primitives) {
1092 ss << " [" << this->uv_verts[this->uv_edges[uvprimitive.edges[0]].verts[0]].vert << ", "
1093 << this->uv_verts[this->uv_edges[uvprimitive.edges[0]].verts[1]].vert << ", "
1094 << this->uv_verts[uvprimitive.get_other_uv_vert(
1095 *this,
1096 this->uv_edges[uvprimitive.edges[0]].verts[0],
1097 this->uv_edges[uvprimitive.edges[0]].verts[1])]
1098 .vert
1099 << "],\n";
1100 }
1101 ss << "]\n";
1102
1103 ss << "uvisland_uvs = [\n";
1104 for (const UVPrimitive &uvprimitive : uv_primitives) {
1105 float2 uv = this->uv_verts[this->uv_edges[uvprimitive.edges[0]].verts[0]].uv;
1106 ss << " " << uv.x << ", " << uv.y << ",\n";
1107 uv = this->uv_verts[this->uv_edges[uvprimitive.edges[0]].verts[1]].uv;
1108 ss << " " << uv.x << ", " << uv.y << ",\n";
1109 uv = this->uv_verts[uvprimitive.get_other_uv_vert(
1110 *this,
1111 this->uv_edges[uvprimitive.edges[0]].verts[0],
1112 this->uv_edges[uvprimitive.edges[0]].verts[1])]
1113 .uv;
1114 ss << " " << uv.x << ", " << uv.y << ",\n";
1115 }
1116 ss << "]\n";
1117
1118 ss << "uvisland_mesh = bpy.data.meshes.new(name='UVIsland')\n";
1119 ss << "uvisland_mesh.from_pydata(uvisland_vertices, uvisland_edges, uvisland_faces)\n";
1120 ss << "uv_map = uvisland_mesh.attributes.new('UVMap', 'FLOAT2', 'CORNER')\n";
1121 ss << "uv_map.data.foreach_set('vector', uvisland_uvs)\n";
1122 ss << "bpy_extras.object_utils.object_data_add(bpy.context, uvisland_mesh)\n";
1123 ss << "#### End UVIsland ####\n\n\n";
1124
1125 std::cout << ss.str();
1126}
1127
1129
1130/* -------------------------------------------------------------------- */
1133
1134std::optional<UVBorder> extract_border_from_edges(const UVIsland &island,
1136 MutableBoundedBitSpan borders_used)
1137{
1138 /* Find a part of the border that haven't been extracted yet. */
1139 const std::optional<int64_t> start_index = bits::find_first_0_index(borders_used);
1140 if (!start_index) {
1141 return std::nullopt;
1142 }
1143 UVBorderEdge &start_edge = edges[*start_index];
1144 UVBorder border;
1145 border.edges.append(start_edge);
1146 borders_used[*start_index].set();
1147
1148 float2 first_uv = island.uv_verts[start_edge.get_uv_vert(island, 0)].uv;
1149 float2 current_uv = island.uv_verts[start_edge.get_uv_vert(island, 1)].uv;
1150 while (current_uv != first_uv) {
1151 bool edge_added = false;
1152 for (const int edge_i : edges.index_range()) {
1153 if (borders_used[edge_i].test()) {
1154 continue;
1155 }
1156 UVBorderEdge &border_edge = edges[edge_i];
1157 int i;
1158 for (i = 0; i < 2; i++) {
1159 if (island.uv_verts[island.uv_edges[border_edge.uv_edge_i].verts[i]].uv == current_uv) {
1160 border_edge.reverse_order = i == 1;
1161 borders_used[edge_i].set();
1162 current_uv = island.uv_verts[border_edge.get_uv_vert(island, 1)].uv;
1163 border.edges.append(border_edge);
1164 edge_added = true;
1165 break;
1166 }
1167 }
1168 if (i != 2) {
1169 break;
1170 }
1171 }
1172 if (!edge_added) {
1173 /* TODO Add a user-facing warning to notify users that the model's UVs are invalid for
1174 * texture painting and should be fixed for optimal results. */
1175 break;
1176 }
1177 }
1178 return border;
1179}
1180
1181bool UVBorder::is_ccw(const UVIsland &island) const
1182{
1183 const UVBorderEdge &edge = edges.first();
1184 const int uv_vert1_i = edge.get_uv_vert(island, 0);
1185 const int uv_vert2_i = edge.get_uv_vert(island, 1);
1186 const int uv_vert3_i = edge.get_other_uv_vert(island);
1187 float poly[3][2];
1188 copy_v2_v2(poly[0], island.uv_verts[uv_vert1_i].uv);
1189 copy_v2_v2(poly[1], island.uv_verts[uv_vert2_i].uv);
1190 copy_v2_v2(poly[2], island.uv_verts[uv_vert3_i].uv);
1191 const bool ccw = cross_poly_v2(poly, 3) > 0.0;
1192 return ccw;
1193}
1194
1196{
1197 for (UVBorderEdge &edge : edges) {
1198 edge.reverse_order = !edge.reverse_order;
1199 }
1200 std::reverse(edges.begin(), edges.end());
1201}
1202
1203float UVBorder::outside_angle(const UVIsland &island, const UVBorderEdge &edge) const
1204{
1205 const UVBorderEdge &prev = *edge.prev;
1206 return M_PI - angle_signed_v2v2(island.uv_verts[prev.get_uv_vert(island, 1)].uv -
1207 island.uv_verts[prev.get_uv_vert(island, 0)].uv,
1208 island.uv_verts[edge.get_uv_vert(island, 1)].uv -
1209 island.uv_verts[edge.get_uv_vert(island, 0)].uv);
1210}
1211
1212void UVBorder::setup_links(const int64_t border_index)
1213{
1214 const int64_t n = edges.size();
1215 for (int64_t i = 0; i < n; i++) {
1216 edges[i].prev = &edges[(i - 1 + n) % n];
1217 edges[i].next = &edges[(i + 1) % n];
1218 edges[i].border_index = border_index;
1219 edges[i].removed = false;
1220 }
1221}
1222
1224
1225/* -------------------------------------------------------------------- */
1228
1233
1234float2 UVBorderCorner::uv(const UVIsland &island, float factor, float min_uv_distance)
1235{
1236 using namespace blender::math;
1237 float2 origin = island.uv_verts[first->get_uv_vert(island, 1)].uv;
1238 float angle_between = angle * factor;
1239 float desired_len = max_ff(
1240 second->length(island) * factor + first->length(island) * (1.0 - factor), min_uv_distance);
1241 float2 v = normalize(island.uv_verts[first->get_uv_vert(island, 0)].uv - origin);
1242
1244 float2 rotated = rot_mat * v;
1245 float2 result = rotated * desired_len + island.uv_verts[first->get_uv_vert(island, 1)].uv;
1246 return result;
1247}
1248
1250{
1251 return island.uv_verts[first->get_uv_vert(island, 1)].vert ==
1252 island.uv_verts[second->get_uv_vert(island, 0)].vert;
1253}
1254
1255void UVBorderCorner::print_debug(const UVIsland &island) const
1256{
1257 std::stringstream ss;
1258 ss << "# ";
1259 if (connected_in_mesh(island)) {
1260 ss << island.uv_verts[first->get_uv_vert(island, 0)].vert << "-";
1261 ss << island.uv_verts[first->get_uv_vert(island, 1)].vert << "-";
1262 ss << island.uv_verts[second->get_uv_vert(island, 1)].vert << "\n";
1263 }
1264 else {
1265 ss << island.uv_verts[first->get_uv_vert(island, 0)].vert << "-";
1266 ss << island.uv_verts[first->get_uv_vert(island, 1)].vert << ", ";
1267 ss << island.uv_verts[second->get_uv_vert(island, 0)].vert << "-";
1268 ss << island.uv_verts[second->get_uv_vert(island, 1)].vert << "\n";
1269 }
1270 std::cout << ss.str();
1271}
1272
1274
1275/* -------------------------------------------------------------------- */
1278
1280
1282 const MeshData &mesh_data,
1283 const uint8_t mesh_vert_index) const
1284{
1285 const int3 &tri = mesh_data.corner_tris[this->primitive_i];
1286 const int mesh_vert = mesh_data.corner_verts[tri[mesh_vert_index]];
1287 for (const int uv_edge_i : edges) {
1288 for (const int uv_vert_i : island.uv_edges[uv_edge_i].verts) {
1289 const UVVert &uv_vert = island.uv_verts[uv_vert_i];
1290 if (uv_vert.vert == mesh_vert) {
1291 return uv_vert_i;
1292 }
1293 }
1294 }
1296 return -1;
1297}
1298
1299int UVPrimitive::get_uv_edge(const UVIsland &island, const float2 uv1, const float2 uv2) const
1300{
1301 for (const int uv_edge_i : edges) {
1302 const float2 &e1 = island.uv_verts[island.uv_edges[uv_edge_i].verts[0]].uv;
1303 const float2 &e2 = island.uv_verts[island.uv_edges[uv_edge_i].verts[1]].uv;
1304 if ((e1 == uv1 && e2 == uv2) || (e1 == uv2 && e2 == uv1)) {
1305 return uv_edge_i;
1306 }
1307 }
1309 return -1;
1310}
1311
1312int UVPrimitive::get_uv_edge(const UVIsland &island, const int v1, const int v2) const
1313{
1314 for (int uv_edge_i : edges) {
1315 const int e1 = island.uv_verts[island.uv_edges[uv_edge_i].verts[0]].vert;
1316 const int e2 = island.uv_verts[island.uv_edges[uv_edge_i].verts[1]].vert;
1317 if ((e1 == v1 && e2 == v2) || (e1 == v2 && e2 == v1)) {
1318 return uv_edge_i;
1319 }
1320 }
1322 return -1;
1323}
1324
1325bool UVPrimitive::contains_uv_vert(const UVIsland &island, const int uv_vert_i) const
1326{
1327 for (int uv_edge_i : edges) {
1328 const UVEdge &edge = island.uv_edges[uv_edge_i];
1329 if (std::find(edge.verts.begin(), edge.verts.end(), uv_vert_i) != edge.verts.end()) {
1330 return true;
1331 }
1332 }
1333 return false;
1334}
1335
1336int UVPrimitive::get_other_uv_vert(const UVIsland &island, const int v1, const int v2) const
1337{
1338 BLI_assert(contains_uv_vert(island, v1));
1339 BLI_assert(contains_uv_vert(island, v2));
1340
1341 for (int uv_edge_i : edges) {
1342 const UVEdge &edge = island.uv_edges[uv_edge_i];
1343 for (const int uv_vert_i : edge.verts) {
1344 if (!ELEM(uv_vert_i, v1, v2)) {
1345 return uv_vert_i;
1346 }
1347 }
1348 }
1350 return -1;
1351}
1352
1354
1355/* -------------------------------------------------------------------- */
1362
1363int UVBorderEdge::get_uv_vert(const UVIsland &island, int index) const
1364{
1365 const UVEdge &edge = island.uv_edges[uv_edge_i];
1366 int actual_index = reverse_order ? 1 - index : index;
1367 return edge.verts[actual_index];
1368}
1369
1371{
1372 const UVEdge &edge = island.uv_edges[uv_edge_i];
1373 return island.uv_primitives[uv_primitive].get_other_uv_vert(
1374 island, edge.verts[0], edge.verts[1]);
1375}
1376
1377bool UVBorderEdge::is_extendable(const UVIsland &island) const
1378{
1379 if (removed) {
1380 return false;
1381 }
1382 const int uv_vert_i = get_uv_vert(island, 0);
1383 const UVVert &uv_vert = island.uv_verts[uv_vert_i];
1384 return uv_vert.flags.is_border && !uv_vert.flags.is_extended;
1385}
1386
1387float UVBorderEdge::length(const UVIsland &island) const
1388{
1389 const UVEdge &edge = island.uv_edges[uv_edge_i];
1390 return len_v2v2(island.uv_verts[edge.verts[0]].uv, island.uv_verts[edge.verts[1]].uv);
1391}
1392
1394
1395/* -------------------------------------------------------------------- */
1398
1404static void find_triangles_near_border(const MeshData &mesh_data,
1405 MutableSpan<bool> r_tri_corner_near_border,
1406 MutableSpan<bool> r_tri_near_border)
1407{
1408 const Span<int3> corner_tris = mesh_data.corner_tris;
1409 const Span<bool> edge_is_border = mesh_data.uv_edge_is_border;
1410 const int64_t tris_num = corner_tris.size();
1411
1412 Array<bool> vert_is_border(mesh_data.vert_positions.size(), false);
1413
1414 /* Mark all triangle corners and vertices on the border. */
1415 threading::parallel_for(IndexRange(tris_num), 2048, [&](const IndexRange range) {
1416 for (const int64_t tri_index : range) {
1417 const int3 real_edges = mesh::corner_tri_get_real_edges(mesh_data.mesh_edges,
1418 mesh_data.corner_verts,
1419 mesh_data.corner_edges,
1420 corner_tris[tri_index]);
1421 for (int j = 0; j < 3; j++) {
1422 const int edge_i = real_edges[j];
1423 if (edge_i != -1 && edge_is_border[edge_i]) {
1424 const int2 edge = mesh_data.mesh_edges[edge_i];
1425 vert_is_border[edge[0]] = true;
1426 vert_is_border[edge[1]] = true;
1427 r_tri_corner_near_border[tri_index * 3 + j] = true;
1428 }
1429 }
1430 }
1431 });
1432
1433 /* Mark triangles near the border. */
1434 threading::parallel_for(IndexRange(tris_num), 4096, [&](const IndexRange range) {
1435 for (const int64_t tri_index : range) {
1436 const int3 &tri = corner_tris[tri_index];
1437 r_tri_near_border[tri_index] = vert_is_border[mesh_data.corner_verts[tri[0]]] ||
1438 vert_is_border[mesh_data.corner_verts[tri[1]]] ||
1439 vert_is_border[mesh_data.corner_verts[tri[2]]];
1440 }
1441 });
1442}
1443
1445 const GroupedSpan<int> tris_by_island,
1446 const UVIslandsMask &uv_masks)
1447{
1449
1450 const int64_t tris_num = mesh_data.corner_tris.size();
1451 Array<bool> tri_corner_near_border(tris_num * 3, false);
1452 Array<bool> tri_near_border(tris_num);
1453 find_triangles_near_border(mesh_data, tri_corner_near_border, tri_near_border);
1454
1455 Array<UVIsland> islands(tris_by_island.size());
1456
1457 /* Add primitives near the island border to each island. Interior primitives are not
1458 * stored, their UVs are read directly from the mesh where needed. */
1459 threading::parallel_for(islands.index_range(), 1, [&](const IndexRange range) {
1460 for (const int64_t uv_island_id : range) {
1461 UVIsland &uv_island = islands[uv_island_id];
1462 uv_island.id = uv_island_id;
1463 for (const int primitive_i : tris_by_island[uv_island_id]) {
1464 if (tri_near_border[primitive_i]) {
1465 add_primitive(mesh_data, uv_island, primitive_i, tri_corner_near_border);
1466 }
1467 }
1468 uv_island.num_original_primitives = uv_island.uv_primitives.size();
1469 uv_island.extract_borders();
1470 uv_island.extend_border(mesh_data, uv_masks, short(uv_island_id));
1471 }
1472 });
1473
1474 return islands;
1475}
1476
1478
1479/* -------------------------------------------------------------------- */
1482
1484{
1485 return ushort2(max_ii(tile_resolution.x >> 2, 256), max_ii(tile_resolution.y >> 2, 256));
1486}
1487
1496
1498{
1499 const float2 tile_uv = uv - udim_offset;
1500 return IN_RANGE_INCL(tile_uv.x, 0.0f, 1.0f) && IN_RANGE_INCL(tile_uv.y, 0.0f, 1.0f);
1501}
1502
1504{
1505 return min_ff(1.0f / tile_resolution.x, 1.0f / tile_resolution.y);
1506}
1507
1508static void add_uv_island(const MeshData &mesh_data,
1510 const Span<int> tris,
1511 int16_t island_index)
1512{
1514 for (const int tri_i : tris) {
1515 const int3 &tri = mesh_data.corner_tris[tri_i];
1516
1517 /* Transform UV coordinates to pixel space in the tile. */
1518 const float2 uv0 = mesh_data.uv_map[tri[0]];
1519 const float2 uv1 = mesh_data.uv_map[tri[1]];
1520 const float2 uv2 = mesh_data.uv_map[tri[2]];
1521 const float2 p0 = (uv0 - tile.udim_offset);
1522 const float2 p1 = (uv1 - tile.udim_offset);
1523 const float2 p2 = (uv2 - tile.udim_offset);
1524
1525 /* Rasterize within the bounds in the tile. */
1526 const TriRasterizer rasterizer(p0, p1, p2, int2(tile.mask_resolution));
1527 const Bounds<int2> bounds = rasterizer.bounds;
1528 for (int y = bounds.min.y; y < bounds.max.y; y++) {
1529 for (int x = bounds.min.x; x < bounds.max.x; x++) {
1530 if (rasterizer.inside(x, y)) {
1531 tile.mask[int64_t(tile.mask_resolution.x) * y + x] = island_index;
1532 }
1533 }
1534 }
1535 }
1536}
1537
1538void UVIslandsMask::add(const MeshData &mesh_data, const GroupedSpan<int> tris_by_island)
1539{
1541
1542 threading::parallel_for(IndexRange(tiles.size()), 1, [&](const IndexRange range) {
1543 for (const int tile_index : range) {
1544 for (const int i : tris_by_island.index_range()) {
1545 add_uv_island(mesh_data, tiles[tile_index], tris_by_island[i], i);
1546 }
1547 }
1548 });
1549}
1550
1551void UVIslandsMask::add_tile(const float2 udim_offset, ushort2 resolution)
1552{
1553 tiles.append_as(Tile(udim_offset, resolution));
1554}
1555
1556static bool dilate_x(const Span<uint16_t> prev_mask,
1558 const ushort2 resolution)
1559{
1560 std::atomic<bool> changed = false;
1561 threading::parallel_for(IndexRange(resolution.y), 32, [&](const IndexRange y_range) {
1562 bool local_changed = false;
1563 for (const int y : y_range) {
1564 const int row = y * resolution.x;
1565 for (int x = 0; x < resolution.x; x++) {
1566 const int offset = row + x;
1567 uint16_t value = prev_mask[offset];
1568 if (value == 0xffff) {
1569 if (x != 0 && prev_mask[offset - 1] != 0xffff) {
1570 value = prev_mask[offset - 1];
1571 local_changed = true;
1572 }
1573 else if (x < resolution.x - 1 && prev_mask[offset + 1] != 0xffff) {
1574 value = prev_mask[offset + 1];
1575 local_changed = true;
1576 }
1577 }
1578 mask[offset] = value;
1579 }
1580 }
1581 if (local_changed) {
1582 changed = true;
1583 }
1584 });
1585 return changed;
1586}
1587
1588static bool dilate_y(const Span<uint16_t> prev_mask,
1590 const ushort2 resolution)
1591{
1592 std::atomic<bool> changed = false;
1593 threading::parallel_for(IndexRange(resolution.y), 32, [&](const IndexRange y_range) {
1594 bool local_changed = false;
1595 for (const int y : y_range) {
1596 const int row = y * resolution.x;
1597 for (int x = 0; x < resolution.x; x++) {
1598 const int offset = row + x;
1599 uint16_t value = prev_mask[offset];
1600 if (value == 0xffff) {
1601 if (y != 0 && prev_mask[offset - resolution.x] != 0xffff) {
1602 value = prev_mask[offset - resolution.x];
1603 local_changed = true;
1604 }
1605 else if (y < resolution.y - 1 && prev_mask[offset + resolution.x] != 0xffff) {
1606 value = prev_mask[offset + resolution.x];
1607 local_changed = true;
1608 }
1609 }
1610 mask[offset] = value;
1611 }
1612 }
1613 if (local_changed) {
1614 changed = true;
1615 }
1616 });
1617 return changed;
1618}
1619
1620static void dilate_tile(UVIslandsMask::Tile &tile, int max_iterations)
1621{
1623
1624 /* Ping-pong between the mask and a scratch buffer for multithreading. */
1625 Array<uint16_t> scratch_buffer(tile.mask.size());
1627 MutableSpan<uint16_t> scratch_mask = scratch_buffer;
1628 for (int index = 0; index < max_iterations; index++) {
1629 bool changed = dilate_x(mask, scratch_mask, tile.mask_resolution);
1630 changed |= dilate_y(scratch_mask, mask, tile.mask_resolution);
1631 if (!changed) {
1632 break;
1633 }
1634 }
1635}
1636
1637void UVIslandsMask::dilate(int max_iterations)
1638{
1640 threading::parallel_for(tiles.index_range(), 1, [&](const IndexRange range) {
1641 for (const int i : range) {
1642 dilate_tile(tiles[i], max_iterations);
1643 }
1644 });
1645}
1646
1647bool UVIslandsMask::Tile::is_masked(const uint16_t island_index, const float2 uv) const
1648{
1649 float2 local_uv = uv - udim_offset;
1650 if (local_uv.x < 0.0f || local_uv.y < 0.0f || local_uv.x > 1.0f || local_uv.y > 1.0f) {
1651 return false;
1652 }
1653 float2 pixel_pos_f = local_uv * float2(mask_resolution.x, mask_resolution.y);
1654 ushort2 pixel_pos = ushort2(clamp_i(pixel_pos_f.x, 0, mask_resolution.x - 1),
1655 clamp_i(pixel_pos_f.y, 0, mask_resolution.y - 1));
1656 uint64_t offset = pixel_pos.y * mask_resolution.x + pixel_pos.x;
1657 return mask[offset] == island_index;
1658}
1659
1661{
1662 for (const Tile &tile : tiles) {
1663 if (tile.contains(uv)) {
1664 return &tile;
1665 }
1666 }
1667 return nullptr;
1668}
1669
1670bool UVIslandsMask::is_masked(const uint16_t island_index, const float2 uv) const
1671{
1672 const Tile *tile = find_tile(uv);
1673 if (tile == nullptr) {
1674 return false;
1675 }
1676 return tile->is_masked(island_index, uv);
1677}
1678
1680
1681} // namespace blender::bke::pbvh::uv_islands
#define M_PI
#define PRF_scope(category)
#define BLI_assert_unreachable()
#define ELEM(...)
#define BLI_assert_msg(a, msg)
#define IN_RANGE_INCL(a, b, c)
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
Tile()=default
void fill(const T &value) const
Definition BLI_array.hh:283
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
constexpr IndexRange()=default
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr int64_t size() const
Definition BLI_span.hh:256
int64_t size() const
void append(const T &value)
friend class Vector
bool is_empty() const
IndexRange index_range() const
const T & first() const
VecBase< float, D > normalize(VecOp< float, D >) RET
float2x2 from_rotation(AngleRadian rotation)
const ccl_global KernelWorkTile * tile
std::optional< int64_t > find_first_0_index(const BitSpanT &data)
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)
int3 corner_tri_get_real_edges(Span< int2 > edges, Span< int > corner_verts, Span< int > corner_edges, const int3 &corner_tri)
IndexRange face_triangles_range(OffsetIndices< int > faces, int face_i)
Definition BKE_mesh.hh:359
int face_corner_next(const IndexRange face, const int corner)
Definition BKE_mesh.hh:315
std::optional< UVBorder > extract_border_from_edges(const UVIsland &island, MutableSpan< UVBorderEdge > edges, MutableBoundedBitSpan borders_used)
static void find_triangles_near_border(const MeshData &mesh_data, MutableSpan< bool > r_tri_corner_near_border, MutableSpan< bool > r_tri_near_border)
static void add_uv_island(const MeshData &mesh_data, UVIslandsMask::Tile &tile, const Span< int > tris, int16_t island_index)
static void add_uv_primitive_fill(UVIsland &island, const int uv_vert1_i, const int uv_vert2_i, const int uv_vert3_i, const int fill_primitive_i)
static int face_corner_of_edge(const MeshData &mesh_data, const int face, const int edge_i)
static int find_fill_primitive(const MeshData &mesh_data, const UVIsland &island, UVBorderCorner &corner)
static void add_uv_primitive_shared_uv_edge(const MeshData &mesh_data, UVIsland &island, const UVVert &connected_vert_1, const UVVert &connected_vert_2, float2 uv_unconnected, const int mesh_primitive_i)
static void dilate_tile(UVIslandsMask::Tile &tile, int max_iterations)
static void mesh_data_init_topology(MeshData &mesh_data)
static bool tri_contains_verts(const MeshData &mesh_data, const int tri_i, const int v0, const int v1)
Array< UVIsland > build_uv_islands(const MeshData &mesh_data, const GroupedSpan< int > tris_by_island, const UVIslandsMask &uv_masks)
static void uv_primitive_append_to_uv_verts(UVIsland &island, UVPrimitive &uv_primitive)
static void uv_primitive_append_to_uv_edges(UVIsland &island, UVPrimitive &uv_primitive)
static void uv_vert_init_flags(UVVert &uv_vert)
static UVPrimitive * add_primitive(const MeshData &mesh_data, UVIsland &uv_island, const int primitive_i, const Span< bool > tri_corner_near_border)
static void reset_extendability_flags(UVIsland &island)
static bool dilate_x(const Span< uint16_t > prev_mask, MutableSpan< uint16_t > mask, const ushort2 resolution)
static bool faces_have_shared_uv_edge(const MeshData &mesh_data, const int face_0, const int face_1, const int edge_i)
static void extend_at_vert(const MeshData &mesh_data, UVIsland &island, UVBorderCorner &corner, float min_uv_distance, int64_t &order_counter, Vector< UVBorderEdge * > &r_modified)
static void uv_edge_append_to_uv_verts(UVIsland &island, const int uv_edge_i)
static int primitive_get_other_uv_vert(const MeshData &mesh_data, const int3 &tri, const int v1, const int v2)
static bool dilate_y(const Span< uint16_t > prev_mask, MutableSpan< uint16_t > mask, const ushort2 resolution)
static ushort2 mask_resolution_from_tile_resolution(ushort2 tile_resolution)
static int mesh_data_init_primitive_uv_island_ids(MeshData &mesh_data)
static int get_uv_corner(const MeshData &mesh_data, const int3 &tri, const int vert)
static void mesh_data_init(MeshData &mesh_data)
AngleRadianBase< T > angle_between(const QuaternionBase< T > &a, const QuaternionBase< T > &b)
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
MINLINE float min_ff(float a, float b)
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
MINLINE void copy_v2_v2(float r[2], const float a[2])
float cross_poly_v2(const float verts[][2], unsigned int nr)
Definition math_geom.cc:153
MatBase< float, 2, 2 > float2x2
float angle_signed_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
MINLINE int max_ii(int a, int b)
ATTR_WARN_UNUSED_RESULT const BMVert * v
unsigned short uint16_t
Definition BKE_text.h:80
VecBase< int32_t, 2 > int2
VecBase< float, 2 > float2
VecBase< int32_t, 3 > int3
unsigned char uint8_t
Definition BKE_text.h:79
VecBase< uint16_t, 2 > ushort2
constexpr bool operator<(StringRef a, StringRef b)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE float max_ff(float a, float b)
MINLINE float len_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
VecBase< float, 3 > float3
MINLINE int clamp_i(int value, int min, int max)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
signed short int16_t
Definition BKE_text.h:77
bool inside(const int x, const int y) const
struct blender::bke::pbvh::uv_islands::FanSegment::@064320177100241246374204120011012026341104001376 flags
void print_debug(const MeshData &mesh_data) const
FanSegment(const MeshData &mesh_data, const int primitive_index, const int3 tri, int vert)
void print_debug(const MeshData &mesh_data) const
bool contains_vert_on_outside(const MeshData &mesh_data, const int vert) const
static bool is_path_valid(const Span< FanSegment * > path, const MeshData &mesh_data, const int from_vert, const int to_vert)
Vector< FanSegment * > best_path_between(const MeshData &mesh_data, const int from_vert, const int to_vert)
void mark_already_added_segments(const UVIsland &uv_island, const UVVert &uv_vert)
struct blender::bke::pbvh::uv_islands::Fan::@234112160234372313155145205237032056146315266100 flags
static int2 other_fan_edge_verts(const MeshData &mesh_data, const int vert, const int tri_i)
static int adjacent_tri(const MeshData &mesh_data, const Span< int > tris, const int vert, const int other_vert, const int tri_i)
static Vector< FanSegment * > path_between(const Span< FanSegment * > edge_order, const MeshData &mesh_data, const int from_vert, const int to_vert, const bool reversed)
static int64_t score(const Span< FanSegment * > solution)
Fan(const MeshData &mesh_data, const int vert)
MeshData(OffsetIndices< int > faces, Span< int3 > corner_tris, Span< int > corner_verts, Span< int > corner_edges, Span< int2 > mesh_edges, GroupedSpan< int > vert_to_face_map, Span< float2 > uv_map, Span< float3 > vert_positions)
void print_debug(const UVIsland &island) const
bool connected_in_mesh(const UVIsland &island) const
float2 uv(const UVIsland &island, float factor, float min_uv_distance)
UVBorderCorner(UVBorderEdge *first, UVBorderEdge *second, float angle)
int get_other_uv_vert(const UVIsland &island) const
UVBorderEdge(int uv_edge_i, int uv_primitive)
int get_uv_vert(const UVIsland &island, int index) const
bool is_extendable(const UVIsland &island) const
float length(const UVIsland &island) const
VectorList< UVBorderEdge > edges_extend_border
float outside_angle(const UVIsland &island, const UVBorderEdge &edge) const
bool is_ccw(const UVIsland &island) const
bool has_same_verts(const UVIsland &island, const int2 &edge) const
int get_other_uv_vert(const UVIsland &island, int vert)
void print_debug(const MeshData &mesh_data) const
void extend_border(const MeshData &mesh_data, const UVIslandsMask &mask, short island_index)
bool is_masked(uint16_t island_index, float2 uv) const
Tile(float2 udim_offset, ushort2 tile_resolution)
bool is_masked(uint16_t island_index, float2 uv) const
void add(const MeshData &mesh_data, GroupedSpan< int > tris_by_island)
void add_tile(float2 udim_offset, ushort2 resolution)
int get_uv_vert(const UVIsland &island, const MeshData &mesh_data, uint8_t mesh_vert_index) const
int get_other_uv_vert(const UVIsland &island, const int v1, const int v2) const
bool contains_uv_vert(const UVIsland &island, const int uv_vert) const
int get_uv_edge(const UVIsland &island, float2 uv1, float2 uv2) const
struct blender::bke::pbvh::uv_islands::UVVert::@006002110014127050064304055317211247224121323337 flags