Blender V5.3
uv_pack.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include "GEO_uv_pack.hh"
10
11#include "BKE_global.hh"
12
13#include "BLI_array.hh"
14#include "BLI_bounds.hh"
15#include "BLI_boxpack_2d.hh"
16#include "BLI_convexhull_2d.hh"
17#include "BLI_math_geom_c.hh"
18#include "BLI_math_matrix_c.hh"
20#include "BLI_math_vector_c.hh"
21#include "BLI_polyfill_2d.hh"
23#include "BLI_rect.hh"
24#include "BLI_vector.hh"
25
26#include "MEM_guardedalloc.h"
27
28namespace blender::geometry {
29
31class UVPhi {
32 public:
33 UVPhi() = default;
34 bool is_valid() const;
35
36 float2 translation = float2(-1.0f, -1.0f);
37 float rotation = 0.0f;
38 // bool reflect = false;
39};
40
41bool UVPhi::is_valid() const
42{
43 return translation.x != -1.0f;
44}
45
46void mul_v2_m2_add_v2v2(float r[2], const float mat[2][2], const float a[2], const float b[2])
47{
48 /* Compute `r = mat * (a + b)` with high precision.
49 *
50 * Often, linear transforms are written as:
51 * `A.x + b`
52 *
53 * When transforming UVs, the familiar expression can damage UVs due to round-off error,
54 * especially when using UDIM and if there are large numbers of islands.
55 *
56 * Instead, we provide a helper which evaluates:
57 * `A. (x + b)`
58 *
59 * To further reduce damage, all internal calculations are
60 * performed using double precision. */
61
62 const double x = double(a[0]) + double(b[0]);
63 const double y = double(a[1]) + double(b[1]);
64
65 r[0] = float(mat[0][0] * x + mat[1][0] * y);
66 r[1] = float(mat[0][1] * x + mat[1][1] * y);
67}
68
72static float dist_signed_squared_to_edge(const float2 probe, const float2 uva, const float2 uvb)
73{
74 const float2 edge = uvb - uva;
75 const float2 side = probe - uva;
76
77 const float edge_length_squared = math::length_squared(edge);
78 /* Tolerance here is to avoid division by zero later. */
79 if (edge_length_squared < 1e-40f) {
80 return math::length_squared(side);
81 }
82
83 const float numerator = edge.x * side.y - edge.y * side.x; /* c.f. cross product. */
84 const float numerator_ssq = numerator >= 0.0f ? numerator * numerator : -numerator * numerator;
85
86 return numerator_ssq / edge_length_squared;
87}
88
92static float get_aspect_scaled_extent(const rctf &extent, const UVPackIsland_Params &params)
93{
94 const float width = BLI_rctf_size_x(&extent);
95 const float height = BLI_rctf_size_y(&extent);
96 return std::max(width / params.target_aspect_y, height);
97}
98
102static float get_aspect_scaled_area(const rctf &extent, const UVPackIsland_Params &params)
103{
104 const float width = BLI_rctf_size_x(&extent);
105 const float height = BLI_rctf_size_y(&extent);
106 return (width / params.target_aspect_y) * height;
107}
108
112static bool is_larger(const rctf &a, const rctf &b, const UVPackIsland_Params &params)
113{
114 const float extent_a = get_aspect_scaled_extent(a, params);
115 const float extent_b = get_aspect_scaled_extent(b, params);
116
117 /* Equal extent, use smaller area. */
118 if (compare_ff_relative(extent_a, extent_b, FLT_EPSILON, 64)) {
119 const float area_a = get_aspect_scaled_area(a, params);
120 const float area_b = get_aspect_scaled_area(b, params);
121 return area_b < area_a;
122 }
123
124 return extent_b < extent_a;
125}
126
128{
129 /* Initialize to the identity transform. */
130 aspect_y = 1.0f;
131 pinned = false;
132 pre_translate = float2(0.0f);
133 angle = 0.0f;
134 caller_index = -31415927; /* Accidentally -pi */
135 pivot_ = float2(0.0f);
136 half_diagonal_ = float2(0.0f);
137 pre_rotate_sincos_ = float2(0.0f, 1.0f);
138}
139
140void PackIsland::add_triangle(const float2 uv0, const float2 uv1, const float2 uv2)
141{
142 /* Be careful with winding. */
143 if (dist_signed_squared_to_edge(uv0, uv1, uv2) < 0.0f) {
144 triangle_vertices_.append(uv0);
145 triangle_vertices_.append(uv1);
146 triangle_vertices_.append(uv2);
147 }
148 else {
149 triangle_vertices_.append(uv0);
150 triangle_vertices_.append(uv2);
151 triangle_vertices_.append(uv1);
152 }
153}
154
155void PackIsland::add_polygon(const Span<float2> uvs, MemArena *arena, Heap *heap)
156{
157 /* Internally, PackIsland uses triangles as the primitive, so we have to triangulate. */
158
159 int vert_count = int(uvs.size());
160 BLI_assert(vert_count >= 3);
161 int nfilltri = vert_count - 2;
162 if (nfilltri == 1) {
163 /* Trivial case, just one triangle. */
164 add_triangle(uvs[0], uvs[1], uvs[2]);
165 return;
166 }
167
168 /* Storage. */
169 uint(*tris)[3] = static_cast<uint(*)[3]>(
170 BLI_memarena_alloc(arena, sizeof(*tris) * size_t(nfilltri)));
171 const float (*source)[2] = reinterpret_cast<const float (*)[2]>(uvs.data());
172
173 /* Triangulate. */
174 BLI_polyfill_calc_arena(source, vert_count, 0, tris, arena);
175
176 /* Beautify improves performance of packer. (Optional)
177 * Long thin triangles, especially at 45 degree angles,
178 * can trigger worst-case performance in #trace_triangle.
179 * Using `Beautify` brings more inputs into average-case. */
180 BLI_polyfill_beautify(source, vert_count, tris, arena, heap);
181
182 /* Add as triangles. */
183 for (int j = 0; j < nfilltri; j++) {
184 uint *tri = tris[j];
185 add_triangle(source[tri[0]], source[tri[1]], source[tri[2]]);
186 }
187
188 BLI_heap_clear(heap, nullptr);
189}
190
192{
193 for (const PackIsland *island : islands) {
194 if (!island->can_rotate_(params)) {
195 return false;
196 }
197 }
198 return true;
199}
200
201/* Rotation helpers operating on the sine & cosine of an angle,
202 * avoiding trigonometric functions which can give different results between platforms. */
203
206{
207 return {sincos.y, -sincos.x};
208}
209
217{
218 if (sincos.y <= 0.0f) {
219 return -sincos;
220 }
221 return sincos;
222}
223
226{
228 /* Close enough to the sine of 0.1 degrees. */
229 const float eps = DEG2RADF(0.1f);
230 if (fabsf(result.x) < eps) {
231 result = {0.0f, 1.0f};
232 }
233 else if (fabsf(result.y) < eps) {
234 result = {(result.x < 0.0f) ? -1.0f : 1.0f, 0.0f};
235 }
236 return result;
237}
238
241 const float aspect_y,
242 float r_matrix[2][2])
243{
244 r_matrix[0][0] = sincos.y;
245 r_matrix[0][1] = -sincos.x * aspect_y;
246 r_matrix[1][0] = sincos.x / aspect_y;
247 r_matrix[1][1] = sincos.y;
248}
249
252 const float aspect_y,
253 float r_matrix[2][2])
254{
255 r_matrix[0][0] = sincos.y;
256 r_matrix[0][1] = sincos.x * aspect_y;
257 r_matrix[1][0] = -sincos.x / aspect_y;
258 r_matrix[1][1] = sincos.y;
259}
260
261void PackIsland::calculate_pre_rotation_(const UVPackIsland_Params &params)
262{
263 pre_rotate_sincos_ = float2(0.0f, 1.0f);
264 if (params.rotate_method == ED_UVPACK_ROTATION_CARDINAL) {
265 /* Arbitrary rotations are not allowed. */
266 return;
267 }
268 if (!can_rotate_before_pack_(params)) {
269 return; /* Nothing to do. */
270 }
271
272 BLI_assert(ELEM(params.rotate_method,
277
278 /* As a heuristic to improve layout efficiency, #PackIsland's are first rotated by an
279 * angle which minimizes the area of the enclosing AABB. This angle is stored in the
280 * `pre_rotate_sincos_` member. The different packing strategies will later rotate
281 * the island further, stored in the `angle_` member.
282 *
283 * As AABBs have 180 degree rotational symmetry, we only consider angles in the `[-90, 90]`
284 * range.
285 *
286 * As a further heuristic, we "stand up" the AABBs so they are "tall" rather than "wide". */
287
288 /* TODO: Use "Rotating Calipers" directly. */
289 {
290 Array<float2> coords(triangle_vertices_.size());
291 for (const int64_t i : triangle_vertices_.index_range()) {
292 coords[i].x = triangle_vertices_[i].x * aspect_y;
293 coords[i].y = triangle_vertices_[i].y;
294 }
295
296 /* Using sin-cos directly because MACOS `atan2f` result differs currently, see: #163873. */
297 const float2 fit_sincos = BLI_convexhull_aabb_fit_points_2d_as_sincos(coords);
298 /* Negate the fitting angle. */
299 float2 sincos = {-fit_sincos.x, fit_sincos.y};
300
301 if (true) {
302 /* "Stand-up" islands. */
303
304 /* Equivalent to #angle_to_mat2. */
305 const float matrix[2][2] = {{fit_sincos.y, fit_sincos.x}, {-fit_sincos.x, fit_sincos.y}};
306 for (const int64_t i : coords.index_range()) {
307 mul_m2_v2(matrix, coords[i]);
308 }
309
310 Bounds<float2> island_bounds = *bounds::min_max(coords.as_span());
311 float2 diagonal = island_bounds.max - island_bounds.min;
312 switch (params.rotate_method) {
314 if (diagonal.x < diagonal.y) {
316 }
318 break;
319 }
321 if (diagonal.x > diagonal.y) {
323 }
325 break;
326 }
327 default: {
328 if (diagonal.y < diagonal.x) {
330 }
332 break;
333 }
334 }
335 }
336 if (sincos == float2(0.0f, 1.0f)) {
337 return;
338 }
340 }
341
342 /* Pre-Rotate `triangle_vertices_`. */
343 float matrix[2][2];
345 for (const int64_t i : triangle_vertices_.index_range()) {
346 mul_m2_v2(matrix, triangle_vertices_[i]);
347 }
348}
349
351{
352 BLI_assert(BLI_heap_len(heap) == 0);
353
354 /* After all the triangles and polygons have been added to a #PackIsland, but before we can start
355 * running packing algorithms, there is a one-time finalization process where we can
356 * pre-calculate a few quantities about the island, including pre-rotation, bounding box, or
357 * computing convex hull.
358 * In the future, we might also detect special-cases for speed or efficiency, such as
359 * rectangle approximation, circle approximation, detecting if the shape has any holes,
360 * analyzing the shape for rotational symmetry or removing overlaps. */
361 BLI_assert(triangle_vertices_.size() >= 3);
362
363 calculate_pre_rotation_(params);
364
365 const eUVPackIsland_ShapeMethod shape_method = params.shape_method;
366 if (shape_method == ED_UVPACK_SHAPE_CONVEX) {
367 /* Compute convex hull of existing triangles. */
368 if (triangle_vertices_.size() <= 3) {
369 calculate_pivot_();
370 return; /* Trivial case, calculate pivot only. */
371 }
372
373 int vert_count = int(triangle_vertices_.size());
374
375 /* Allocate storage. */
376 int *index_map = static_cast<int *>(
377 BLI_memarena_alloc(arena, sizeof(*index_map) * vert_count));
378
379 /* Compute convex hull. */
380 int convex_len = BLI_convexhull_2d(triangle_vertices_, index_map);
381 if (convex_len >= 3) {
382 /* Write back. */
383 float2 *convex_verts = static_cast<float2 *>(
384 BLI_memarena_alloc(arena, sizeof(*convex_verts) * convex_len));
385 for (int i = 0; i < convex_len; i++) {
386 convex_verts[i] = triangle_vertices_[index_map[i]];
387 }
388 triangle_vertices_.clear();
389 add_polygon(Span(convex_verts, convex_len), arena, heap);
390 }
391 }
392
393 /* Pivot calculation might be performed multiple times during pre-processing.
394 * To ensure the `pivot_` used during packing includes any changes, we also calculate
395 * the pivot *last* to ensure it is correct.
396 */
397 calculate_pivot_();
398}
399
400void PackIsland::calculate_pivot_()
401{
402 /* The meaning of `pivot_` is somewhat ambiguous, as technically, the only restriction is that it
403 * can't be *outside* the convex hull of the shape. Anywhere in the interior, or even on the
404 * boundary of the convex hull is fine.
405 * (The GJK support function for every direction away from `pivot_` is numerically >= 0.0f)
406 *
407 * Ideally, `pivot_` would be the center of the shape's minimum covering circle (MCC). That would
408 * improve packing performance, and potentially even improve packing efficiency.
409 *
410 * However, computing the MCC *efficiently* is somewhat complicated.
411 *
412 * Instead, we compromise, and `pivot_` is currently calculated as the center of the AABB.
413 *
414 * If we later special-case circle packing, *AND* we can preserve the
415 * numerically-not-outside-the-convex-hull property, we may want to revisit this choice.
416 */
417 Bounds<float2> triangle_bounds = *bounds::min_max(triangle_vertices_.as_span());
418 pivot_ = (triangle_bounds.min + triangle_bounds.max) * 0.5f;
419 half_diagonal_ = (triangle_bounds.max - triangle_bounds.min) * 0.5f;
420 BLI_assert(half_diagonal_.x >= 0.0f);
421 BLI_assert(half_diagonal_.y >= 0.0f);
422}
423
424void PackIsland::place_(const float scale, const UVPhi phi)
425{
426 /* The angle is only used for output, rounding differences between platforms are harmless
427 * since the rotation used for packing is calculated from `pre_rotate_sincos_`. */
429
430 float matrix_inverse[2][2];
431 build_inverse_transformation(scale, phi.rotation, matrix_inverse);
432 mul_v2_m2v2(pre_translate, matrix_inverse, phi.translation);
434
435 if (pre_rotate_sincos_ != float2(0.0f, 1.0f)) {
437 mul_m2_v2(matrix_inverse, pre_translate);
438 }
439}
440
442{
444 scale_to_fit = true;
445 only_selected_uvs = false;
446 only_selected_faces = false;
447 use_seams = false;
448 correct_aspect = false;
450 pin_unselected = false;
451 merge_overlap = false;
452 margin = 0.001f;
454 udim_base_offset[0] = 0.0f;
455 udim_base_offset[1] = 0.0f;
456 target_extent = 1.0f; /* Assume unit square. */
457 target_aspect_y = 1.0f; /* Assume unit square. */
459 stop = nullptr;
460 do_update = nullptr;
461 progress = nullptr;
462}
463
464/* Compact representation for AABB packers. */
471
483static void pack_islands_alpaca_turbo(const int64_t exclude_index,
484 const rctf &exclude,
485 const Span<std::unique_ptr<UVAABBIsland>> islands,
486 const float target_aspect_y,
487 MutableSpan<UVPhi> r_phis,
488 rctf *r_extent)
489{
490 /* Exclude an initial AABB near the origin. */
491 float next_u1 = exclude.xmax;
492 float next_v1 = exclude.ymax;
493 bool zigzag = next_u1 < next_v1 * target_aspect_y; /* Horizontal or Vertical strip? */
494
495 float u0 = zigzag ? next_u1 : 0.0f;
496 float v0 = zigzag ? 0.0f : next_v1;
497
498 /* Visit every island in order, except the excluded islands at the start. */
499 for (int64_t index = exclude_index; index < islands.size(); index++) {
500 UVAABBIsland &island = *islands[index];
501 const float dsm_u = island.uv_diagonal.x;
502 const float dsm_v = island.uv_diagonal.y;
503
504 bool restart = false;
505 if (zigzag) {
506 restart = (next_v1 < v0 + dsm_v);
507 }
508 else {
509 restart = (next_u1 < u0 + dsm_u);
510 }
511 if (restart) {
512 /* We're at the end of a strip. Restart from U axis or V axis. */
513 zigzag = next_u1 < next_v1 * target_aspect_y;
514 u0 = zigzag ? next_u1 : 0.0f;
515 v0 = zigzag ? 0.0f : next_v1;
516 }
517
518 /* Place the island. */
519 UVPhi &phi = r_phis[island.index];
520 phi.rotation = 0.0f;
521 phi.translation.x = u0 + dsm_u * 0.5f;
522 phi.translation.y = v0 + dsm_v * 0.5f;
523 if (zigzag) {
524 /* Move upwards. */
525 v0 += dsm_v;
526 next_u1 = max_ff(next_u1, u0 + dsm_u);
527 next_v1 = max_ff(next_v1, v0);
528 }
529 else {
530 /* Move sideways. */
531 u0 += dsm_u;
532 next_v1 = max_ff(next_v1, v0 + dsm_v);
533 next_u1 = max_ff(next_u1, u0);
534 }
535 }
536
537 /* Write back extent. */
538 *r_extent = {0.0f, next_u1, 0.0f, next_v1};
539}
540
552static void update_hole_rotate(float2 &hole,
553 float2 &hole_diagonal,
554 bool &hole_rotate,
555 const float u0,
556 const float v0,
557 const float u1,
558 const float v1)
559{
560 BLI_assert(hole_diagonal.x <= hole_diagonal.y); /* Confirm invariants. */
561
562 const float hole_area = hole_diagonal.x * hole_diagonal.y;
563 const float quad_area = (u1 - u0) * (v1 - v0);
564 if (quad_area <= hole_area) {
565 return; /* No update, existing hole is larger than candidate. */
566 }
567 hole.x = u0;
568 hole.y = v0;
569 hole_diagonal.x = u1 - u0;
570 hole_diagonal.y = v1 - v0;
571 if (hole_diagonal.y < hole_diagonal.x) {
572 std::swap(hole_diagonal.x, hole_diagonal.y);
573 hole_rotate = true;
574 }
575 else {
576 hole_rotate = false;
577 }
578
579 const float updated_area = hole_diagonal.x * hole_diagonal.y;
580 BLI_assert(hole_area < updated_area); /* Confirm hole grew in size. */
581 UNUSED_VARS(updated_area);
582
583 BLI_assert(hole_diagonal.x <= hole_diagonal.y); /* Confirm invariants. */
584}
585
594static void pack_islands_alpaca_rotate(const int64_t exclude_index,
595 const rctf &exclude,
596 const Span<std::unique_ptr<UVAABBIsland>> islands,
597 const float target_aspect_y,
598 MutableSpan<UVPhi> r_phis,
599 rctf *r_extent)
600{
601 /* Exclude an initial AABB near the origin. */
602 float next_u1 = exclude.xmax;
603 float next_v1 = exclude.ymax;
604 bool zigzag = next_u1 / target_aspect_y < next_v1; /* Horizontal or Vertical strip? */
605
606 /* Track an AABB "hole" which may be filled at any time. */
607 float2 hole(0.0f);
608 float2 hole_diagonal(0.0f);
609 bool hole_rotate = false;
610
611 float u0 = zigzag ? next_u1 : 0.0f;
612 float v0 = zigzag ? 0.0f : next_v1;
613
614 /* Visit every island in order, except the excluded islands at the start. */
615 for (int64_t index = exclude_index; index < islands.size(); index++) {
616 UVAABBIsland &island = *islands[index];
617 UVPhi &phi = r_phis[island.index];
618 const float uvdiag_x = island.uv_diagonal.x * island.aspect_y;
619 float min_dsm = std::min(uvdiag_x, island.uv_diagonal.y);
620 float max_dsm = std::max(uvdiag_x, island.uv_diagonal.y);
621
622 if (min_dsm < hole_diagonal.x && max_dsm < hole_diagonal.y) {
623 /* Place island in the hole. */
624 if (hole_rotate == (min_dsm == island.uv_diagonal.x)) {
625 phi.rotation = DEG2RADF(90.0f);
626 phi.translation.x = hole[0] + island.uv_diagonal.y * 0.5f / island.aspect_y;
627 phi.translation.y = hole[1] + island.uv_diagonal.x * 0.5f * island.aspect_y;
628 }
629 else {
630 phi.rotation = 0.0f;
631 phi.translation.x = hole[0] + island.uv_diagonal.x * 0.5f;
632 phi.translation.y = hole[1] + island.uv_diagonal.y * 0.5f;
633 }
634
635 /* Update space left in the hole. */
636 float p[6];
637 p[0] = hole[0];
638 p[1] = hole[1];
639 p[2] = hole[0] + (hole_rotate ? max_dsm : min_dsm) / island.aspect_y;
640 p[3] = hole[1] + (hole_rotate ? min_dsm : max_dsm);
641 p[4] = hole[0] + (hole_rotate ? hole_diagonal.y : hole_diagonal.x);
642 p[5] = hole[1] + (hole_rotate ? hole_diagonal.x : hole_diagonal.y);
643 hole_diagonal.x = 0; /* Invalidate old hole. */
644 update_hole_rotate(hole, hole_diagonal, hole_rotate, p[0], p[3], p[4], p[5]);
645 update_hole_rotate(hole, hole_diagonal, hole_rotate, p[2], p[1], p[4], p[5]);
646
647 /* Island is placed in the hole, no need to check for restart, or process movement. */
648 continue;
649 }
650
651 bool restart = false;
652 if (zigzag) {
653 restart = (next_v1 < v0 + min_dsm);
654 }
655 else {
656 restart = (next_u1 < u0 + min_dsm / island.aspect_y);
657 }
658 if (restart) {
659 update_hole_rotate(hole, hole_diagonal, hole_rotate, u0, v0, next_u1, next_v1);
660 /* We're at the end of a strip. Restart from U axis or V axis. */
661 zigzag = next_u1 / target_aspect_y < next_v1;
662 u0 = zigzag ? next_u1 : 0.0f;
663 v0 = zigzag ? 0.0f : next_v1;
664 }
665
666 /* Place the island. */
667 if (zigzag == (min_dsm == uvdiag_x)) {
668 phi.rotation = DEG2RADF(90.0f);
669 phi.translation.x = u0 + island.uv_diagonal.y * 0.5f / island.aspect_y;
670 phi.translation.y = v0 + island.uv_diagonal.x * 0.5f * island.aspect_y;
671 }
672 else {
673 phi.rotation = 0.0f;
674 phi.translation.x = u0 + island.uv_diagonal.x * 0.5f;
675 phi.translation.y = v0 + island.uv_diagonal.y * 0.5f;
676 }
677
678 /* Move according to the "Alpaca rules", with rotation. */
679 if (zigzag) {
680 /* Move upwards. */
681 v0 += min_dsm;
682 next_u1 = max_ff(next_u1, u0 + max_dsm / island.aspect_y);
683 next_v1 = max_ff(next_v1, v0);
684 }
685 else {
686 /* Move sideways. */
687 u0 += min_dsm / island.aspect_y;
688 next_v1 = max_ff(next_v1, v0 + max_dsm);
689 next_u1 = max_ff(next_u1, u0);
690 }
691 }
692
693 /* Write back total pack AABB. */
694 *r_extent = {0.0f, next_u1, 0.0f, next_v1};
695}
696
700static void pack_islands_fast(const int64_t exclude_index,
701 const rctf &exclude,
702 const Span<std::unique_ptr<UVAABBIsland>> aabbs,
703 const bool rotate,
704 const float target_aspect_y,
705 MutableSpan<UVPhi> r_phis,
706 rctf *r_extent)
707{
708 if (rotate) {
709 pack_islands_alpaca_rotate(exclude_index, exclude, aabbs, target_aspect_y, r_phis, r_extent);
710 }
711 else {
712 pack_islands_alpaca_turbo(exclude_index, exclude, aabbs, target_aspect_y, r_phis, r_extent);
713 }
714}
715
717static void pack_gobel(const Span<std::unique_ptr<UVAABBIsland>> aabbs,
718 const float scale,
719 const int m,
720 MutableSpan<UVPhi> r_phis)
721{
722 for (const int64_t i : aabbs.index_range()) {
723 UVPhi &phi = *static_cast<UVPhi *>(&r_phis[aabbs[i]->index]);
724 phi.rotation = 0.0f;
725 if (i == 0) {
726 phi.translation.x = 0.5f * scale;
727 phi.translation.y = 0.5f * scale;
728 continue;
729 }
730 int xx = (i - 1) % m;
731 int yy = int(i - 1) / m;
732 phi.translation.x = (xx + 0.5f) * scale;
733 phi.translation.y = (yy + 0.5f) * scale;
734 if (xx >= yy) {
735 phi.translation.x += (1 + sqrtf(0.5f)) * scale;
736 }
737 else {
738 phi.translation.y += sqrtf(0.5f) * scale;
739 }
740
741 if (i == m * (m + 1) + 1) {
742 phi.translation.x += (m + sqrtf(0.5f)) * scale;
743 phi.translation.y -= scale;
744 }
745 else if (i > m * (m + 1) + 1) {
746 phi.rotation = DEG2RADF(45.0f);
747 phi.translation.x = ((i - m * (m + 1) - 1.5f) * cosf(phi.rotation) + 1.0f) * scale;
748 phi.translation.y = phi.translation.x;
749 }
750 }
751}
752
753static bool pack_islands_optimal_pack_table(const int table_count,
754 const float max_extent,
755 const float *optimal,
756 const char * /*unused_comment*/,
757 int64_t island_count,
758 const float large_uv,
759 const Span<std::unique_ptr<UVAABBIsland>> aabbs,
760 const UVPackIsland_Params &params,
761 MutableSpan<UVPhi> r_phis,
762 rctf *r_extent)
763{
764 if (table_count < island_count) {
765 return false;
766 }
767 rctf extent = {0.0f, large_uv * max_extent, 0.0f, large_uv * max_extent};
768 if (is_larger(extent, *r_extent, params)) {
769 return false;
770 }
771 *r_extent = extent;
772
773 for (int i = 0; i < island_count; i++) {
774 UVPhi &phi = r_phis[aabbs[i]->index];
775 phi.translation.x = optimal[i * 3 + 0] * large_uv;
776 phi.translation.y = optimal[i * 3 + 1] * large_uv;
777 phi.rotation = optimal[i * 3 + 2];
778 }
779 return true;
780}
781
782/* Attempt to find an "Optimal" packing of the islands, e.g. assuming squares or circles. */
783static void pack_islands_optimal_pack(const Span<std::unique_ptr<UVAABBIsland>> aabbs,
784 const UVPackIsland_Params &params,
785 MutableSpan<UVPhi> r_phis,
786 rctf *r_extent)
787{
788 if (params.shape_method == ED_UVPACK_SHAPE_AABB) {
789 return;
790 }
791 if (params.target_aspect_y != 1.0f) {
792 return;
793 }
795 return;
796 }
797
798 float large_uv = 0.0f;
799 for (const int64_t i : aabbs.index_range()) {
800 large_uv = max_ff(large_uv, aabbs[i]->uv_diagonal.x);
801 large_uv = max_ff(large_uv, aabbs[i]->uv_diagonal.y);
802 }
803
804 int64_t island_count_patch = aabbs.size();
805
806 const float opt_11[] = {
807 /* Walter Trump, 1979. */
808 2.6238700165660708840676f,
809 2.4365065643739085565755f,
810 0.70130710554829878145f,
811 1.9596047386700836678841f,
812 1.6885655318806973568257f,
813 0.70130710554829878145f,
814 1.9364970731945949644626f,
815 3.1724566890997589752033f,
816 0.70130710554829878145f,
817 1.2722458068219282267819f,
818 2.4245322476118422727609f,
819 0.70130710554829878145f,
820 3.1724918301381124230431f,
821 1.536261617698265524723f,
822 0.70130710554829878145f,
823 3.3770999999999999907629f,
824 3.3770999999999999907629f,
825 0.0f,
826 0.5f,
827 1.5f,
828 0.0f,
829 2.5325444557069398676674f,
830 0.5f,
831 0.0f,
832 0.5f,
833 3.3770999999999999907629f,
834 0.0f,
835 1.5f,
836 0.5f,
837 0.0f,
838 0.5f,
839 0.5f,
840 0.0f,
841 };
843 3.8770999999999999907629f,
844 opt_11,
845 "Walter Trump, 1979",
846 island_count_patch,
847 large_uv,
848 aabbs,
849 params,
850 r_phis,
851 r_extent);
852
853 const float opt_18[] = {
854 /* Pertti Hamalainen, 1979. */
855 2.4700161985907582717914f,
856 2.4335783708246112588824f,
857 0.42403103949074028022892f,
858 1.3528594569415370862941f,
859 2.3892972847076845432923f,
860 0.42403103949074028022892f,
861 2.0585783708246108147932f,
862 1.5221405430584633577951f,
863 0.42403103949074028022892f,
864 1.7642972847076845432923f,
865 3.3007351124738324443797f,
866 0.42403103949074028022892f,
867 3.3228756555322949139963f,
868 1.5f,
869 0.0f,
870 3.3228756555322949139963f,
871 3.3228756555322949139963f,
872 0.0f,
873 0.5f,
874 1.5f,
875 0.0f,
876 2.3228756555322949139963f,
877 4.3228756555322949139963f,
878 0.0f,
879 0.5f,
880 3.3228756555322949139963f,
881 0.0f,
882 1.5f,
883 0.5f,
884 0.0f,
885 3.3228756555322949139963f,
886 0.5f,
887 0.0f,
888 3.3228756555322949139963f,
889 4.3228756555322949139963f,
890 0.0f,
891 4.3228756555322949139963f,
892 1.5f,
893 0.0f,
894 4.3228756555322949139963f,
895 3.3228756555322949139963f,
896 0.0f,
897 0.5f,
898 0.5f,
899 0.0f,
900 0.5f,
901 4.3228756555322949139963f,
902 0.0f,
903 4.3228756555322949139963f,
904 0.5f,
905 0.0f,
906 4.3228756555322949139963f,
907 4.3228756555322949139963f,
908 0.0f,
909 };
911 4.8228756555322949139963f,
912 opt_18,
913 "Pertti Hamalainen, 1979",
914 island_count_patch,
915 large_uv,
916 aabbs,
917 params,
918 r_phis,
919 r_extent);
920
921 const float opt_19[] = {
922 /* Robert Wainwright, 1979. */
923 2.1785113019775792508881f,
924 1.9428090415820631342569f,
925 0.78539816339744827899949f,
926 1.4714045207910317891731f,
927 2.6499158227686105959719f,
928 0.78539816339744827899949f,
929 2.9428090415820640224354f,
930 2.7071067811865479058042f,
931 0.78539816339744827899949f,
932 2.2357022603955165607204f,
933 3.4142135623730953675192f,
934 0.78539816339744827899949f,
935 1.4428090415820635783462f,
936 1.2642977396044836613243f,
937 0.78539816339744827899949f,
938 3.3856180831641271566923f,
939 1.5f,
940 0.0f,
941 0.73570226039551600560884f,
942 1.9714045207910311230393f,
943 0.78539816339744827899949f,
944 3.6213203435596432733234f,
945 3.4428090415820635783462f,
946 0.78539816339744827899949f,
947 2.9142135623730958116084f,
948 4.1499158227686105959719f,
949 0.78539816339744827899949f,
950 2.3856180831641271566923f,
951 0.5f,
952 0.0f,
953 0.5f,
954 3.3856180831641271566923f,
955 0.0f,
956 1.5f,
957 4.3856180831641271566923f,
958 0.0f,
959 4.3856180831641271566923f,
960 2.5f,
961 0.0f,
962 3.3856180831641271566923f,
963 0.5f,
964 0.0f,
965 4.3856180831641271566923f,
966 1.5f,
967 0.0f,
968 0.5f,
969 0.5f,
970 0.0f,
971 0.5f,
972 4.3856180831641271566923f,
973 0.0f,
974 4.3856180831641271566923f,
975 0.5f,
976 0.0f,
977 4.3856180831641271566923f,
978 4.3856180831641271566923f,
979 0.0f,
980 };
982 4.8856180831641271566923f,
983 opt_19,
984 "Robert Wainwright, 1979",
985 island_count_patch,
986 large_uv,
987 aabbs,
988 params,
989 r_phis,
990 r_extent);
991
992 const float opt_26[] = {
993 /* Erich Friedman, 1997. */
994 2.3106601717798209705279f,
995 2.8106601717798214146171f,
996 0.78539816339744827899949f,
997 1.6035533905932735088129f,
998 2.1035533905932739529021f,
999 0.78539816339744827899949f,
1000 3.0177669529663684322429f,
1001 2.1035533905932739529021f,
1002 0.78539816339744827899949f,
1003 2.3106601717798209705279f,
1004 1.3964466094067264911871f,
1005 0.78539816339744827899949f,
1006 1.6035533905932735088129f,
1007 3.5177669529663688763321f,
1008 0.78539816339744827899949f,
1009 0.89644660940672593607559f,
1010 2.8106601717798214146171f,
1011 0.78539816339744827899949f,
1012 3.0177669529663684322429f,
1013 3.5177669529663688763321f,
1014 0.78539816339744827899949f,
1015 3.7248737341529158939579f,
1016 2.8106601717798214146171f,
1017 0.78539816339744827899949f,
1018 2.3106601717798209705279f,
1019 4.2248737341529167821363f,
1020 0.78539816339744827899949f,
1021 0.5f,
1022 1.5f,
1023 0.0f,
1024 1.5f,
1025 0.5f,
1026 0.0f,
1027 3.1213203435596419410558f,
1028 0.5f,
1029 0.0f,
1030 4.1213203435596419410558f,
1031 1.5f,
1032 0.0f,
1033 0.5f,
1034 4.1213203435596419410558f,
1035 0.0f,
1036 0.5f,
1037 0.5f,
1038 0.0f,
1039 4.1213203435596419410558f,
1040 4.1213203435596419410558f,
1041 0.0f,
1042 4.1213203435596419410558f,
1043 0.5f,
1044 0.0f,
1045 1.5f,
1046 5.1213203435596419410558f,
1047 0.0f,
1048 3.1213203435596419410558f,
1049 5.1213203435596419410558f,
1050 0.0f,
1051 5.1213203435596419410558f,
1052 2.5f,
1053 0.0f,
1054 5.1213203435596419410558f,
1055 1.5f,
1056 0.0f,
1057 0.5f,
1058 5.1213203435596419410558f,
1059 0.0f,
1060 4.1213203435596419410558f,
1061 5.1213203435596419410558f,
1062 0.0f,
1063 5.1213203435596419410558f,
1064 4.1213203435596419410558f,
1065 0.0f,
1066 5.1213203435596419410558f,
1067 0.5f,
1068 0.0f,
1069 5.1213203435596419410558f,
1070 5.1213203435596419410558f,
1071 0.0f,
1072 };
1074 5.6213203435596419410558f,
1075 opt_26,
1076 "Erich Friedman, 1997",
1077 island_count_patch,
1078 large_uv,
1079 aabbs,
1080 params,
1081 r_phis,
1082 r_extent);
1083
1084 if (island_count_patch == 37) {
1085 island_count_patch = 38; /* TODO, Cantrell 2002. */
1086 }
1087 if (island_count_patch == 50) {
1088 island_count_patch = 52; /* TODO, Cantrell 2002. */
1089 }
1090 if (island_count_patch == 51) {
1091 island_count_patch = 52; /* TODO, Hajba 2009. */
1092 }
1093 if (island_count_patch == 65) {
1094 island_count_patch = 67; /* TODO, Gobel 1979. */
1095 }
1096 if (island_count_patch == 66) {
1097 island_count_patch = 67; /* TODO, Stenlund 1980. */
1098 }
1099 /* See https://www.combinatorics.org/files/Surveys/ds7/ds7v5-2009/ds7-2009.html
1100 * https://erich-friedman.github.io/packing/squinsqu */
1101 for (int a = 1; a < 20; a++) {
1102 int n = a * a + a + 3 + floorf((a - 1) * sqrtf(2.0f));
1103 if (island_count_patch == n) {
1104 float max_uv_gobel = large_uv * (a + 1 + sqrtf(0.5f));
1105 rctf extent = {0.0f, max_uv_gobel, 0.0f, max_uv_gobel};
1106 if (is_larger(*r_extent, extent, params)) {
1107 *r_extent = extent;
1108 pack_gobel(aabbs, large_uv, a, r_phis);
1109 }
1110 return;
1111 }
1112 }
1113}
1114
1115/* Wrapper around #BLI_box_pack_2d. */
1116static void pack_island_box_pack_2d(const Span<std::unique_ptr<UVAABBIsland>> aabbs,
1117 const UVPackIsland_Params &params,
1118 MutableSpan<UVPhi> r_phis,
1119 rctf *r_extent)
1120{
1121 /* Allocate storage. */
1122 BoxPack *box_array = MEM_new_array_uninitialized<BoxPack>(size_t(aabbs.size()), __func__);
1123
1124 /* Prepare for box_pack_2d. */
1125 for (const int64_t i : aabbs.index_range()) {
1126 BoxPack *box = box_array + i;
1127 box->w = aabbs[i]->uv_diagonal.x / params.target_aspect_y;
1128 box->h = aabbs[i]->uv_diagonal.y;
1129 }
1130
1131 const bool sort_boxes = false; /* Use existing ordering from `aabbs`. */
1132
1133 float box_max_u = 0.0f;
1134 float box_max_v = 0.0f;
1135 BLI_box_pack_2d(box_array, int(aabbs.size()), sort_boxes, &box_max_u, &box_max_v);
1136 box_max_u *= params.target_aspect_y;
1137 rctf extent = {0.0f, box_max_u, 0.0f, box_max_v};
1138
1139 if (is_larger(*r_extent, extent, params)) {
1140 *r_extent = extent;
1141 /* Write back box_pack UVs. */
1142 for (const int64_t i : aabbs.index_range()) {
1143 BoxPack *box = box_array + i;
1144 UVPhi &phi = *static_cast<UVPhi *>(&r_phis[aabbs[i]->index]);
1145 phi.rotation = 0.0f; /* #BLI_box_pack_2d never rotates. */
1146 phi.translation.x = (box->x + box->w * 0.5f) * params.target_aspect_y;
1147 phi.translation.y = (box->y + box->h * 0.5f);
1148 }
1149 }
1150
1151 /* Housekeeping. */
1152 MEM_delete(box_array);
1153}
1154
1163 public:
1164 Occupancy(const float initial_scale);
1165
1166 void increase_scale(); /* Resize the scale of the bitmap and clear it. */
1167 void clear(); /* Clear occupancy information. */
1168
1169 /* Write or Query a triangle on the bitmap. */
1170 float trace_triangle(const float2 &uv0,
1171 const float2 &uv1,
1172 const float2 &uv2,
1173 const float margin,
1174 const bool write) const;
1175
1176 /* Write or Query an island on the bitmap. */
1177 float trace_island(const PackIsland *island,
1178 const UVPhi phi,
1179 const float scale,
1180 const float margin,
1181 const bool write) const;
1182
1183 int bitmap_radix = 800; /* Width and Height of `bitmap`. */
1184 float bitmap_scale_reciprocal = 1.0f; /* == 1.0f / `bitmap_scale`. */
1185 private:
1186 mutable Array<float> bitmap_;
1187
1188 mutable float2 witness_; /* Witness to a previously known occupied pixel. */
1189 mutable float witness_distance_; /* Signed distance to nearest placed island. */
1190 mutable uint triangle_hint_; /* Hint to a previously suspected overlapping triangle. */
1191
1192 const float terminal = 1048576.0f; /* 4 * bitmap_radix < terminal < INT_MAX / 4. */
1193};
1194
1195Occupancy::Occupancy(const float initial_scale) : bitmap_(bitmap_radix * bitmap_radix, false)
1196{
1198 bitmap_scale_reciprocal = bitmap_radix / initial_scale; /* Actually set the value. */
1199}
1200
1202{
1203 BLI_assert(bitmap_scale_reciprocal > 0.0f); /* TODO: Packing has failed, report error. */
1204
1206 clear();
1207}
1208
1210{
1211 for (int i = 0; i < bitmap_radix * bitmap_radix; i++) {
1212 bitmap_[i] = terminal;
1213 }
1214 witness_.x = -1;
1215 witness_.y = -1;
1216 witness_distance_ = 0.0f;
1217 triangle_hint_ = 0;
1218}
1219
1220static float signed_distance_fat_triangle(const float2 probe,
1221 const float2 uv0,
1222 const float2 uv1,
1223 const float2 uv2)
1224{
1225 /* Be careful with ordering, uv0 <- uv1 <- uv2 <- uv0 <- uv1 etc. */
1226 const float dist01_ssq = dist_signed_squared_to_edge(probe, uv0, uv1);
1227 const float dist12_ssq = dist_signed_squared_to_edge(probe, uv1, uv2);
1228 const float dist20_ssq = dist_signed_squared_to_edge(probe, uv2, uv0);
1229 float result_ssq = std::max({dist01_ssq, dist12_ssq, dist20_ssq});
1230 if (result_ssq < 0.0f) {
1231 return -sqrtf(-result_ssq);
1232 }
1233 BLI_assert(result_ssq >= 0.0f);
1234 result_ssq = std::min(result_ssq, math::length_squared(probe - uv0));
1235 result_ssq = std::min(result_ssq, math::length_squared(probe - uv1));
1236 result_ssq = std::min(result_ssq, math::length_squared(probe - uv2));
1237 BLI_assert(result_ssq >= 0.0f);
1238 return sqrtf(result_ssq);
1239}
1240
1242 const float2 &uv1,
1243 const float2 &uv2,
1244 const float margin,
1245 const bool write) const
1246{
1247 const float x0 = std::min({uv0.x, uv1.x, uv2.x});
1248 const float y0 = std::min({uv0.y, uv1.y, uv2.y});
1249 const float x1 = std::max({uv0.x, uv1.x, uv2.x});
1250 const float y1 = std::max({uv0.y, uv1.y, uv2.y});
1251 float spread = write ? margin * 2 : 0.0f;
1252 int ix0 = std::max(int(floorf((x0 - spread) * bitmap_scale_reciprocal)), 0);
1253 int iy0 = std::max(int(floorf((y0 - spread) * bitmap_scale_reciprocal)), 0);
1254 int ix1 = std::min(int(floorf((x1 + spread) * bitmap_scale_reciprocal + 2)), bitmap_radix);
1255 int iy1 = std::min(int(floorf((y1 + spread) * bitmap_scale_reciprocal + 2)), bitmap_radix);
1256
1257 const float2 uv0s = uv0 * bitmap_scale_reciprocal;
1258 const float2 uv1s = uv1 * bitmap_scale_reciprocal;
1259 const float2 uv2s = uv2 * bitmap_scale_reciprocal;
1260
1261 /* TODO: Better epsilon handling here could reduce search size. */
1262 float epsilon = 0.7071f; /* == sqrt(0.5f), rounded up by 0.00002f. */
1263 epsilon = std::max(epsilon, 2 * margin * bitmap_scale_reciprocal);
1264
1265 if (!write) {
1266 if (ix0 <= witness_.x && witness_.x < ix1) {
1267 if (iy0 <= witness_.y && witness_.y < iy1) {
1268 const float distance = signed_distance_fat_triangle(witness_, uv0s, uv1s, uv2s);
1269 const float extent = epsilon - distance - witness_distance_;
1270 const float pixel_round_off = -0.1f; /* Go faster on nearly-axis aligned edges. */
1271 if (extent > pixel_round_off) {
1272 return std::max(0.0f, extent); /* Witness observes occupied. */
1273 }
1274 }
1275 }
1276 }
1277
1278 /* Iterate in opposite direction to outer search to improve witness effectiveness. */
1279 for (int y = iy1 - 1; y >= iy0; y--) {
1280 for (int x = ix1 - 1; x >= ix0; x--) {
1281 float *hotspot = &bitmap_[y * bitmap_radix + x];
1282 if (!write && *hotspot > epsilon) {
1283 continue;
1284 }
1285 const float2 probe(x, y);
1286 const float distance = signed_distance_fat_triangle(probe, uv0s, uv1s, uv2s);
1287 if (write) {
1288 *hotspot = min_ff(distance, *hotspot);
1289 continue;
1290 }
1291 const float extent = epsilon - distance - *hotspot;
1292 if (extent > 0.0f) {
1293 witness_ = probe;
1294 witness_distance_ = *hotspot;
1295 return extent; /* Occupied. */
1296 }
1297 }
1298 }
1299 return -1.0f; /* Available. */
1300}
1301
1303 const float rotation,
1304 /* const bool reflection, */
1305 const float margin) const
1306{
1307 /* Caution: Only "Dihedral Group D4" transforms are calculated exactly.
1308 * if the transform is Non-D4, an upper bound will be returned instead. */
1309
1310 if (rotation == DEG2RADF(-180.0f) || rotation == 0.0f || rotation == DEG2RADF(180.0f)) {
1311 return half_diagonal_ * scale + margin;
1312 }
1313
1314 if (rotation == DEG2RADF(-90.0f) || rotation == DEG2RADF(90.0f) || rotation == DEG2RADF(270.0f))
1315 {
1316 return float2(half_diagonal_.y / aspect_y, half_diagonal_.x * aspect_y) * scale + margin;
1317 }
1318
1319 float matrix[2][2];
1320 build_transformation(scale, rotation, matrix);
1321
1322 /* TODO: Use convex hull to calculate support. */
1323 float diagonal_rotated[2];
1324 mul_v2_m2v2(diagonal_rotated, matrix, half_diagonal_);
1325 float sx = fabsf(diagonal_rotated[0]);
1326 float sy = fabsf(diagonal_rotated[1]);
1327
1328 return float2(sx + sy * 0.7071f + margin, sx * 0.7071f + sy + margin); /* Upper bound. */
1329}
1330
1332 const UVPhi phi,
1333 const float scale,
1334 const float margin,
1335 const bool write) const
1336{
1337 const float2 diagonal_support = island->get_diagonal_support(scale, phi.rotation, margin);
1338
1339 if (!write) {
1340 if (phi.translation.x < diagonal_support.x || phi.translation.y < diagonal_support.y) {
1341 return terminal; /* Occupied. */
1342 }
1343 }
1344 float matrix[2][2];
1345 island->build_transformation(scale, phi.rotation, matrix);
1346 float2 pivot_transformed;
1347 mul_v2_m2v2(pivot_transformed, matrix, island->pivot_);
1348
1349 /* TODO: Support #ED_UVPACK_SHAPE_AABB. */
1350
1351 /* TODO: If the PackIsland has the same shape as it's convex hull, we can trace the hull instead
1352 * of the individual triangles, which is faster and provides a better value of `extent`.
1353 */
1354
1355 const float2 delta = phi.translation - pivot_transformed;
1356 const uint vert_count = uint(
1357 island->triangle_vertices_.size()); /* `uint` is faster than `int`. */
1358 for (uint i = 0; i < vert_count; i += 3) {
1359 const uint j = (i + triangle_hint_) % vert_count;
1360 float2 uv0;
1361 float2 uv1;
1362 float2 uv2;
1363 mul_v2_m2v2(uv0, matrix, island->triangle_vertices_[j]);
1364 mul_v2_m2v2(uv1, matrix, island->triangle_vertices_[j + 1]);
1365 mul_v2_m2v2(uv2, matrix, island->triangle_vertices_[j + 2]);
1366 const float extent = trace_triangle(uv0 + delta, uv1 + delta, uv2 + delta, margin, write);
1367
1368 if (!write && extent >= 0.0f) {
1369 triangle_hint_ = j;
1370 return extent; /* Occupied. */
1371 }
1372 }
1373 return -1.0f; /* Available. */
1374}
1375
1377 const int scan_line,
1378 const Occupancy &occupancy,
1379 const float scale,
1380 const int angle_90_multiple,
1381 /* TODO: const bool reflect, */
1382 const float margin,
1383 const float target_aspect_y)
1384{
1385 /* Discussion: Different xatlas implementation make different choices here, either
1386 * fixing the output bitmap size before packing begins, or sometimes allowing
1387 * for non-square outputs which can make the resulting algorithm a little simpler.
1388 *
1389 * The current implementation is to grow using the "Alpaca Rules" as described above, with calls
1390 * to increase_scale() if the particular packing instance is badly conditioned.
1391 *
1392 * (This particular choice is largely a result of the way packing is used inside the Blender API,
1393 * and isn't strictly required by the xatlas algorithm.)
1394 *
1395 * One nice extension to the xatlas algorithm might be to grow in all 4 directions, i.e. both
1396 * increasing and *decreasing* in the horizontal and vertical axes. The `scan_line` parameter
1397 * would become a #rctf, the occupancy bitmap would be 4x larger, and there will be a translation
1398 * to move the origin back to `(0,0)` at the end.
1399 *
1400 * This `plus-atlas` algorithm, which grows in a "+" shape, will likely have better packing
1401 * efficiency for many real world inputs, at a cost of increased complexity and memory.
1402 */
1403
1404 const float bitmap_scale = 1.0f / occupancy.bitmap_scale_reciprocal;
1405
1406 /* TODO: If `target_aspect_y != 1.0f`, to avoid aliasing issues, we should probably iterate
1407 * Separately on `scan_line_x` and `scan_line_y`. See also: Bresenham's algorithm. */
1408 const float sqrt_target_aspect_y = sqrtf(target_aspect_y);
1409 const int scan_line_x = int(scan_line * sqrt_target_aspect_y);
1410 const int scan_line_y = int(scan_line / sqrt_target_aspect_y);
1411
1412 UVPhi phi;
1413 phi.rotation = DEG2RADF(angle_90_multiple * 90);
1414 // phi.reflect = reflect;
1415 float matrix[2][2];
1416 island->build_transformation(scale, phi.rotation, matrix);
1417
1418 /* Caution, margin is zero for `support_diagonal` as we're tracking the top-right corner. */
1419 float2 support_diagonal = island->get_diagonal_support(scale, phi.rotation, 0.0f);
1420
1421 /* Scan using an "Alpaca"-style search, first horizontally using "less-than". */
1422 int t = int(ceilf((2 * support_diagonal.x + margin) * occupancy.bitmap_scale_reciprocal));
1423 while (t < scan_line_x) { /* "less-than" */
1424 phi.translation = float2(t * bitmap_scale, scan_line_y * bitmap_scale) - support_diagonal;
1425 const float extent = occupancy.trace_island(island, phi, scale, margin, false);
1426 if (extent < 0.0f) {
1427 return phi; /* Success. */
1428 }
1429 t = t + std::max(1, int(extent));
1430 }
1431
1432 /* Then scan vertically using "less-than-or-equal" */
1433 t = int(ceilf((2 * support_diagonal.y + margin) * occupancy.bitmap_scale_reciprocal));
1434 while (t <= scan_line_y) { /* "less-than-or-equal" */
1435 phi.translation = float2(scan_line_x * bitmap_scale, t * bitmap_scale) - support_diagonal;
1436 const float extent = occupancy.trace_island(island, phi, scale, margin, false);
1437 if (extent < 0.0f) {
1438 return phi; /* Success. */
1439 }
1440 t = t + std::max(1, int(extent));
1441 }
1442
1443 return UVPhi(); /* Unable to find a place to fit. */
1444}
1445
1447 const float scale,
1448 const float margin)
1449{
1450 float sum = 1e-40f;
1451 for (int64_t i : islands.index_range()) {
1452 PackIsland *island = islands[i];
1453 sum += island->half_diagonal_.x * 2 * scale + 2 * margin;
1454 sum += island->half_diagonal_.y * 2 * scale + 2 * margin;
1455 }
1456 return sqrtf(sum) / 6.0f;
1457}
1458
1461 public:
1462 const float scale_;
1463 const float margin_;
1465
1469
1472
1474 const float margin,
1475 const UVPackIsland_Params *params)
1476 : scale_(scale), margin_(margin), params_(params)
1477 {
1478 best_angle = 0.0f;
1479 best_quad = 0.0f;
1480 }
1481
1486 float update(const double angle)
1487 {
1488 float2 dir(cos(angle), sin(angle));
1489
1490 /* TODO: Once convexhull_2d bugs are fixed, we can use "rotating calipers" to go faster. */
1491 rctf bounds;
1493 for (const int64_t i : indices.index_range()) {
1494 const float2 &p = points[indices[i]];
1495 const float uv[2] = {p.x * dir.x + p.y * dir.y, -p.x * dir.y + p.y * dir.x};
1497 }
1498 bounds.xmin -= margin_;
1499 bounds.ymin -= margin_;
1500 bounds.xmax += margin_;
1501 bounds.ymax += margin_;
1502 const float current_quad = get_aspect_scaled_extent(bounds, *params_);
1503 if (best_quad > current_quad) {
1504 best_quad = current_quad;
1505 best_angle = angle;
1507 }
1508 return current_quad;
1509 }
1510
1512 void update_recursive(const float angle0,
1513 const float quad0,
1514 const float angle1,
1515 const float quad1)
1516 {
1517 const float angle_mid = (angle0 + angle1) * 0.5f;
1518 const float quad_mid = update(angle_mid);
1519 const float angle_separation = angle1 - angle0;
1520
1521 if (angle_separation < DEG2RADF(0.002f)) {
1522 return; /* Sufficient accuracy achieved. */
1523 }
1524
1525 bool search_mode = DEG2RADF(10.0f) < angle_separation; /* In linear search mode. */
1526
1527 /* TODO: Degenerate inputs could have poor performance here. */
1528 if (search_mode || (quad0 <= quad1)) {
1529 update_recursive(angle0, quad0, angle_mid, quad_mid);
1530 }
1531 if (search_mode || (quad1 <= quad0)) {
1532 update_recursive(angle_mid, quad_mid, angle1, quad1);
1533 }
1534 }
1535};
1536
1542static bool rotate_inside_square(const Span<std::unique_ptr<UVAABBIsland>> island_indices,
1544 const UVPackIsland_Params &params,
1545 const float scale,
1546 const float margin,
1547 MutableSpan<UVPhi> r_phis,
1548 rctf *r_extent)
1549{
1550 if (island_indices.is_empty()) {
1551 return false; /* Nothing to do. */
1552 }
1553 if (params.rotate_method != ED_UVPACK_ROTATION_ANY) {
1554 return false; /* Unable to rotate by arbitrary angle. */
1555 }
1556 if (params.shape_method == ED_UVPACK_SHAPE_AABB) {
1557 /* AABB margin calculations are not preserved under rotations. */
1558 if (island_indices.size() > 1) { /* Unless there's only one island. */
1559
1560 if (params.target_aspect_y != 1.0f) {
1561 /* TODO: Check for possible 90 degree rotation. */
1562 }
1563 return false;
1564 }
1565 }
1566
1567 UVMinimumEnclosingSquareFinder square_finder(scale, margin, &params);
1568 square_finder.best_quad = get_aspect_scaled_extent(*r_extent, params) * 0.999f;
1569
1570 float matrix[2][2];
1571
1572 const float aspect_y = 1.0f; /* TODO: Use `islands[0]->aspect_y`. */
1573 for (const int64_t j : island_indices.index_range()) {
1574 const int64_t i = island_indices[j]->index;
1575 const PackIsland *island = islands[i];
1576 if (island->aspect_y != aspect_y) {
1577 return false; /* Aspect ratios are not preserved under rotation. */
1578 }
1579 const float island_scale = island->can_scale_(params) ? scale : 1.0f;
1580 island->build_transformation(island_scale, r_phis[i].rotation, matrix);
1581 float2 pivot_transformed;
1582 mul_v2_m2v2(pivot_transformed, matrix, island->pivot_);
1583 float2 delta = r_phis[i].translation - pivot_transformed;
1584
1585 for (const int64_t k : island->triangle_vertices_.index_range()) {
1586 float2 p = island->triangle_vertices_[k];
1587 mul_m2_v2(matrix, p);
1588 square_finder.points.append(p + delta);
1589 }
1590 }
1591
1592 /* Now we have all the points in the correct space, compute the 2D convex hull. */
1593 square_finder.indices.resize(square_finder.points.size()); /* Allocate worst-case. */
1594 int convex_size = BLI_convexhull_2d(square_finder.points, square_finder.indices.data());
1595 square_finder.indices.resize(convex_size); /* Resize to actual size. */
1596
1597 /* Run the computation to find the best angle. (Slow!) */
1598 const float quad_180 = square_finder.update(DEG2RADF(-180.0f));
1599 square_finder.update_recursive(DEG2RADF(-180.0f), quad_180, DEG2RADF(180.0f), quad_180);
1600
1601 if (square_finder.best_angle == 0.0f) {
1602 return false; /* Nothing to do. */
1603 }
1604
1605 /* Transform phis, rotate by best_angle, then translate back to the origin. No scale. */
1606 for (const int64_t j : island_indices.index_range()) {
1607 const int64_t i = island_indices[j]->index;
1608 const PackIsland *island = islands[i];
1609 const float identity_scale = 1.0f; /* Don't rescale the placement, just rotate. */
1610 island->build_transformation(identity_scale, square_finder.best_angle, matrix);
1611 r_phis[i].rotation += square_finder.best_angle;
1612 mul_m2_v2(matrix, r_phis[i].translation);
1613 r_phis[i].translation.x -= square_finder.best_bounds.xmin;
1614 r_phis[i].translation.y -= square_finder.best_bounds.ymin;
1615 }
1616
1617 /* Write back new extent, translated to the origin. */
1618 r_extent->xmin = 0.0f;
1619 r_extent->ymin = 0.0f;
1620 r_extent->xmax = BLI_rctf_size_x(&square_finder.best_bounds);
1621 r_extent->ymax = BLI_rctf_size_y(&square_finder.best_bounds);
1622 return true; /* `r_phis` and `r_extent` were modified. */
1623}
1624
1641
1642static int64_t pack_island_xatlas(const Span<std::unique_ptr<UVAABBIsland>> island_indices,
1644 const float scale,
1645 const float margin,
1646 const UVPackIsland_Params &params,
1647 MutableSpan<UVPhi> r_phis,
1648 rctf *r_extent)
1649{
1650 if (params.shape_method == ED_UVPACK_SHAPE_AABB) {
1651 return 0; /* Not yet supported. */
1652 }
1653 Array<UVPhi> phis(r_phis.size());
1655 rctf extent = {0.0f, 0.0f, 0.0f, 0.0f};
1656
1657 /* A heuristic to improve final layout efficiency by making an
1658 * intermediate call to #rotate_inside_square. */
1659 int64_t square_milestone = sqrt(island_indices.size()) / 4 + 2;
1660
1661 int scan_line = 0; /* Current "scan_line" of occupancy bitmap. */
1662 int traced_islands = 0; /* Which islands are currently traced in `occupancy`. */
1663 int i = 0;
1664 bool placed_can_rotate = true;
1665
1666 /* Bound the number of times the search area may be enlarged
1667 * (see #Occupancy::increase_scale). See #159462 for an example
1668 * where even faces of a cube hang, although degenerate UV's may cause the same problem.
1669 *
1670 * TODO(@ideasman42): investigate how other XATLAS implementation handle this,
1671 * as this just avoids hanging, ideally these cases wouldn't perform so poorly. */
1672 int increase_scale_remaining = 32;
1673
1674 /* The following `while` loop is setting up a three-way race:
1675 * `for (scan_line = 0; scan_line < bitmap_radix; scan_line++)`
1676 * `for (i : island_indices.index_range())`
1677 * `while (bitmap_scale_reciprocal > 0) { bitmap_scale_reciprocal *= 0.5f; }`
1678 */
1679
1680 while (i < island_indices.size()) {
1681
1682 if (params.stop && G.is_break) {
1683 *params.stop = true;
1684 }
1685 if (params.isCancelled()) {
1686 break;
1687 }
1688
1689 while (traced_islands < i) {
1690 /* Trace an island that's been solved. (Greedy.) */
1691 const int64_t island_index = island_indices[traced_islands]->index;
1692 PackIsland *island = islands[island_index];
1693 const float island_scale = island->can_scale_(params) ? scale : 1.0f;
1694 occupancy.trace_island(island, phis[island_index], island_scale, margin, true);
1695 traced_islands++;
1696 }
1697
1698 PackIsland *island = islands[island_indices[i]->index];
1699 UVPhi phi; /* Create an identity transform. */
1700
1701 if (!island->can_translate_(params)) {
1702 /* Move the pinned island into the correct coordinate system. */
1703 phi.translation = island->pivot_;
1705 phi.rotation = 0.0f;
1706 phis[island_indices[i]->index] = phi;
1707 i++;
1708 placed_can_rotate = false; /* Further rotation will cause a translation. */
1709 continue; /* `island` is now completed. */
1710 }
1711 const float island_scale = island->can_scale_(params) ? scale : 1.0f;
1712
1713 int max_90_multiple = 1;
1714 if (island->can_rotate_(params)) {
1715 if (i && (i < 50)) {
1716 max_90_multiple = 4;
1717 }
1718 }
1719 else {
1720 placed_can_rotate = false;
1721 }
1722
1723 for (int angle_90_multiple = 0; angle_90_multiple < max_90_multiple; angle_90_multiple++) {
1724 phi = find_best_fit_for_island(island,
1725 scan_line,
1726 occupancy,
1727 island_scale,
1728 angle_90_multiple,
1729 margin,
1730 params.target_aspect_y);
1731 if (phi.is_valid()) {
1732 break;
1733 }
1734 }
1735
1736 if (!phi.is_valid()) {
1737 /* Unable to find a fit on this scan_line. */
1738
1739 island = nullptr; /* Just mark it as null, we won't use it further. */
1740
1741 if (i < 10) {
1742 scan_line++;
1743 }
1744 else {
1745 /* Increasing by 2 here has the effect of changing the sampling pattern.
1746 * The parameter '2' is not "free" in the sense that changing it requires
1747 * a change to `bitmap_radix` and then re-tuning `alpaca_cutoff`.
1748 * Possible values here *could* be 1, 2 or 3, however the only *reasonable*
1749 * choice is 2. */
1750 scan_line += 2;
1751 }
1752 if (scan_line < occupancy.bitmap_radix *
1753 sqrtf(std::min(params.target_aspect_y, 1.0f / params.target_aspect_y)))
1754 {
1755 continue; /* Try again on next scan_line. */
1756 }
1757
1758 /* Enlarge search parameters. */
1759 if (--increase_scale_remaining < 0) {
1760 /* Unable to pack within a reasonable number of enlargements, give up and keep the layout
1761 * from the previous packers (left untouched in `r_phis`). */
1762 return 0;
1763 }
1764 scan_line = 0;
1765 occupancy.increase_scale();
1766 traced_islands = 0; /* Will trigger a re-trace of previously solved islands. */
1767 continue;
1768 }
1769
1770 /* Place island. */
1771 phis[island_indices[i]->index] = phi;
1772 i++; /* Next island. */
1773
1774 if (i == square_milestone && placed_can_rotate) {
1776 island_indices.take_front(i), islands, params, scale, margin, phis, &extent))
1777 {
1778 scan_line = 0;
1779 traced_islands = 0;
1780 occupancy.clear();
1781 continue;
1782 }
1783 }
1784
1785 /* Update top-right corner. */
1786 float2 top_right = island->get_diagonal_support(island_scale, phi.rotation, margin) +
1787 phi.translation;
1788 extent.xmax = std::max(top_right.x, extent.xmax);
1789 extent.ymax = std::max(top_right.y, extent.ymax);
1790
1791 if (!is_larger(*r_extent, extent, params)) {
1792 if (i >= square_milestone) {
1793 return 0; /* Early exit, we already have a better layout. */
1794 }
1795 }
1796
1797 /* Heuristics to reduce size of brute-force search. */
1798 if (i < 128 || (i & 31) == 16) {
1799 scan_line = 0; /* Restart completely. */
1800 }
1801 else {
1802 scan_line = std::max(0, scan_line - 25); /* `-25` must by odd. */
1803 }
1804
1805 if (params.progress) {
1806 /* We don't (yet) have a good model for how long the pack operation is going
1807 * to take, so just update the progress a little bit. */
1808 const float previous_progress = *params.progress;
1809 *params.do_update = true;
1810 const float reduction = island_indices.size() / (island_indices.size() + 0.5f);
1811 *params.progress = 1.0f - (1.0f - previous_progress) * reduction;
1812 }
1813 }
1814
1815 /* TODO: if (i != island_indices.size()) { ??? } */
1816
1817 if (!is_larger(*r_extent, extent, params)) {
1818 return 0;
1819 }
1820
1821 /* Our pack is an improvement on the one passed in. Write it back. */
1822 *r_extent = extent;
1823 for (int64_t j = 0; j < i; j++) {
1824 const int64_t island_index = island_indices[j]->index;
1825 r_phis[island_index] = phis[island_index];
1826 }
1827 return i; /* Return the number of islands which were packed. */
1828}
1829
1840 const float scale,
1841 const float margin,
1842 const UVPackIsland_Params &params,
1843 MutableSpan<UVPhi> r_phis)
1844{
1845 /* #BLI_box_pack_2d produces layouts with high packing efficiency, but has `O(n^3)`
1846 * time complexity, causing poor performance if there are lots of islands. See: #102843.
1847 * #pack_islands_alpaca_turbo is designed to be the fastest packing method, `O(nlogn)`,
1848 * but has poor packing efficiency if the AABBs have a spread of sizes and aspect ratios.
1849 * Here, we merge the best properties of both packers into one combined packer.
1850 *
1851 * The free tuning parameter, `alpaca_cutoff` will determine how many islands are packed
1852 * using each method.
1853 *
1854 * The current strategy is:
1855 * - Sort islands in size order.
1856 * - Try #pack_island_optimal_pack packer first
1857 * - Call #pack_island_xatlas on the first `alpaca_cutoff` islands.
1858 * - Also call #BLI_box_pack_2d on the first `alpaca_cutoff` islands.
1859 * - Choose the best layout so far.
1860 * - Rotate into the minimum bounding square.
1861 * - Call #pack_islands_alpaca_* on the remaining islands.
1862 */
1863
1864 const bool all_can_rotate = can_rotate(islands, params);
1865
1866 /* First, copy information from our input into the AABB structure. */
1868 for (const int64_t i : islands.index_range()) {
1869 PackIsland *pack_island = islands[i];
1870 float island_scale = scale;
1871 if (!pack_island->can_scale_(params)) {
1872 island_scale = 1.0f;
1873 }
1874 std::unique_ptr<UVAABBIsland> aabb = std::make_unique<UVAABBIsland>();
1875 aabb->index = i;
1876 aabb->uv_diagonal.x = pack_island->half_diagonal_.x * 2 * island_scale + 2 * margin;
1877 aabb->uv_diagonal.y = pack_island->half_diagonal_.y * 2 * island_scale + 2 * margin;
1878 aabb->aspect_y = pack_island->aspect_y;
1879 aabbs[i] = std::move(aabb);
1880 }
1881
1882 /* Sort from "biggest" to "smallest". */
1883
1884 if (all_can_rotate) {
1885 std::stable_sort(
1886 aabbs.begin(),
1887 aabbs.end(),
1888 [&](const std::unique_ptr<UVAABBIsland> &a, const std::unique_ptr<UVAABBIsland> &b) {
1889 const bool can_translate_a = islands[a->index]->can_translate_(params);
1890 const bool can_translate_b = islands[b->index]->can_translate_(params);
1891 if (can_translate_a != can_translate_b) {
1892 return can_translate_b; /* Locked islands are placed first. */
1893 }
1894 /* TODO: Fix when (params.target_aspect_y != 1.0f) */
1895
1896 /* Choose the AABB with the longest large edge. */
1897 float a_u = a->uv_diagonal.x * a->aspect_y;
1898 float a_v = a->uv_diagonal.y;
1899 float b_u = b->uv_diagonal.x * b->aspect_y;
1900 float b_v = b->uv_diagonal.y;
1901 if (a_u > a_v) {
1902 std::swap(a_u, a_v);
1903 }
1904 if (b_u > b_v) {
1905 std::swap(b_u, b_v);
1906 }
1907 float diff_u = a_u - b_u;
1908 float diff_v = a_v - b_v;
1909 diff_v += diff_u * 0.05f; /* Robust sort, smooth over round-off errors. */
1910 if (diff_v == 0.0f) { /* Tie break. */
1911 return diff_u > 0.0f;
1912 }
1913 return diff_v > 0.0f;
1914 });
1915 }
1916 else {
1917 std::stable_sort(
1918 aabbs.begin(),
1919 aabbs.end(),
1920 [&](const std::unique_ptr<UVAABBIsland> &a, const std::unique_ptr<UVAABBIsland> &b) {
1921 const bool can_translate_a = islands[a->index]->can_translate_(params);
1922 const bool can_translate_b = islands[b->index]->can_translate_(params);
1923 if (can_translate_a != can_translate_b) {
1924 return can_translate_b; /* Locked islands are placed first. */
1925 }
1926
1927 /* Choose the AABB with larger rectangular area. */
1928 return b->uv_diagonal.x * b->uv_diagonal.y < a->uv_diagonal.x * a->uv_diagonal.y;
1929 });
1930 }
1931
1932 /* If some of the islands are locked, we build a summary about them here. */
1933 rctf locked_bounds = {0.0f}; /* AABB of islands which can't translate. */
1934 int64_t locked_island_count = 0; /* Index of first non-locked island. */
1935 for (int64_t i = 0; i < islands.size(); i++) {
1936 PackIsland *pack_island = islands[aabbs[i]->index];
1937 if (pack_island->can_translate_(params)) {
1938 break;
1939 }
1940 float2 bottom_left = pack_island->pivot_ - pack_island->half_diagonal_;
1941 float2 top_right = pack_island->pivot_ + pack_island->half_diagonal_;
1942 if (i == 0) {
1943 locked_bounds.xmin = bottom_left.x;
1944 locked_bounds.xmax = top_right.x;
1945 locked_bounds.ymin = bottom_left.y;
1946 locked_bounds.ymax = top_right.y;
1947 }
1948 else {
1949 BLI_rctf_do_minmax_v(&locked_bounds, bottom_left);
1950 BLI_rctf_do_minmax_v(&locked_bounds, top_right);
1951 }
1952
1953 UVPhi &phi = r_phis[aabbs[i]->index]; /* Lock in place. */
1954 phi.translation = pack_island->pivot_;
1955 sub_v2_v2(phi.translation, params.udim_base_offset);
1956 phi.rotation = 0.0f;
1957
1958 locked_island_count = i + 1;
1959 }
1960
1961 /* Partition `islands`, largest islands will go to a slow packer, the rest the fast packer.
1962 * See discussion above for details. */
1963 int64_t alpaca_cutoff = 1024; /* Regular situation, pack `32 * 32` islands with slow packer. */
1964 int64_t alpaca_cutoff_fast = 81; /* Reduce problem size, only `N = 9 * 9` with slow packer. */
1965 if (params.margin_method == ED_UVPACK_MARGIN_FRACTION) {
1966 if (margin > 0.0f) {
1967 alpaca_cutoff = alpaca_cutoff_fast;
1968 }
1969 }
1970
1971 alpaca_cutoff = std::max(alpaca_cutoff, locked_island_count); /* ...TODO... */
1972
1973 Span<std::unique_ptr<UVAABBIsland>> slow_aabbs = aabbs.as_span().take_front(
1974 std::min(alpaca_cutoff, islands.size()));
1975 rctf extent = {0.0f, 1e30f, 0.0f, 1e30f};
1976
1977 /* Call the "fast" packer, which can sometimes give optimal results. */
1978 pack_islands_fast(locked_island_count,
1979 locked_bounds,
1980 slow_aabbs,
1981 all_can_rotate,
1982 params.target_aspect_y,
1983 r_phis,
1984 &extent);
1985 rctf fast_extent = extent; /* Remember how large the "fast" packer was. */
1986
1987 /* Call the "optimal" packer. */
1988 if (locked_island_count == 0) {
1989 pack_islands_optimal_pack(slow_aabbs, params, r_phis, &extent);
1990 }
1991
1992 /* Call box_pack_2d (slow for large N.) */
1993 if (locked_island_count == 0) { /* box_pack_2d doesn't yet support locked islands. */
1994 pack_island_box_pack_2d(slow_aabbs, params, r_phis, &extent);
1995 }
1996
1997 /* Call xatlas (slow for large N.) */
1998 int64_t max_xatlas = pack_island_xatlas(
1999 slow_aabbs, islands, scale, margin, params, r_phis, &extent);
2000 if (max_xatlas) {
2001 slow_aabbs = aabbs.as_span().take_front(max_xatlas);
2002 }
2003
2004 /* At this stage, `extent` contains the fast/optimal/box_pack/xatlas UVs. */
2005
2006 /* If more islands remain to be packed, attempt to improve the layout further by finding the
2007 * minimal-bounding-square. Disabled for other cases as users often prefer to avoid diagonal
2008 * islands. */
2009 if (all_can_rotate && aabbs.size() > slow_aabbs.size()) {
2010 rotate_inside_square(slow_aabbs, islands, params, scale, margin, r_phis, &extent);
2011 }
2012
2013 if (BLI_rctf_compare(&extent, &fast_extent, 0.0f)) {
2014 /* The fast packer was the best so far. Lets just use the fast packer for everything. */
2015 slow_aabbs = slow_aabbs.take_front(locked_island_count);
2016 extent = locked_bounds;
2017 }
2018
2019 /* Call fast packer for remaining islands, excluding everything already placed. */
2020 rctf final_extent = {0.0f, 1e30f, 0.0f, 1e30f};
2021 pack_islands_fast(slow_aabbs.size(),
2022 extent,
2023 aabbs,
2024 all_can_rotate,
2025 params.target_aspect_y,
2026 r_phis,
2027 &final_extent);
2028
2029 return get_aspect_scaled_extent(final_extent, params);
2030}
2031
2037 const float margin_fraction,
2038 const bool rescale_margin,
2039 const UVPackIsland_Params &params)
2040{
2041 /*
2042 * Root finding using a combined search / modified-secant method.
2043 * First, use a robust search procedure to bracket the root within a factor of 10.
2044 * Then, use a modified-secant method to converge.
2045 *
2046 * This is a specialized solver using domain knowledge to accelerate convergence. */
2047
2048 float scale_low = 0.0f;
2049 float value_low = 0.0f;
2050 float scale_high = 0.0f;
2051 float value_high = 0.0f;
2052
2053 Array<UVPhi> phis_a(islands.size());
2054 Array<UVPhi> phis_b(islands.size());
2055 Array<UVPhi> *phis_low = nullptr;
2056
2057 /* Scaling smaller than `min_scale_roundoff` is unlikely to fit and
2058 * will destroy information in existing UVs. */
2059 const float min_scale_roundoff = 1e-5f;
2060
2061 /* Certain inputs might have poor convergence properties.
2062 * Use `max_iteration` to prevent an infinite loop. */
2063 const int max_iteration = 25;
2064 for (int iteration = 0; iteration < max_iteration; iteration++) {
2065 float scale = 1.0f;
2066
2067 if (iteration == 0) {
2068 BLI_assert(iteration == 0);
2069 BLI_assert(scale == 1.0f);
2070 BLI_assert(scale_low == 0.0f);
2071 BLI_assert(scale_high == 0.0f);
2072 }
2073 else if (scale_low == 0.0f) {
2074 BLI_assert(scale_high > 0.0f);
2075 /* Search mode, shrink layout until we can find a scale that fits. */
2076 scale = scale_high * 0.1f;
2077 }
2078 else if (scale_high == 0.0f) {
2079 BLI_assert(scale_low > 0.0f);
2080 /* Search mode, grow layout until we can find a scale that doesn't fit. */
2081 scale = scale_low * 10.0f;
2082 }
2083 else {
2084 /* Bracket mode, use modified secant method to find root. */
2085 BLI_assert(scale_low > 0.0f);
2086 BLI_assert(scale_high > 0.0f);
2087 BLI_assert(value_low <= 0.0f);
2088 BLI_assert(value_high >= 0.0f);
2089 if (scale_high < scale_low * 1.0001f) {
2090 /* Convergence. */
2091 break;
2092 }
2093
2094 /* Secant method for area. */
2095 scale = (sqrtf(scale_low) * value_high - sqrtf(scale_high) * value_low) /
2096 (value_high - value_low);
2097 scale = scale * scale;
2098
2099 if (iteration & 1) {
2100 /* Modified binary-search to improve robustness. */
2101 scale = sqrtf(scale * sqrtf(scale_low * scale_high));
2102 }
2103
2104 BLI_assert(scale_low < scale);
2105 BLI_assert(scale < scale_high);
2106 }
2107
2108 scale = std::max(scale, min_scale_roundoff);
2109
2110 /* Evaluate our `f`. */
2111 Array<UVPhi> *phis_target = (phis_low == &phis_a) ? &phis_b : &phis_a;
2112 const float margin = rescale_margin ? margin_fraction * scale : margin_fraction;
2113 const float max_uv = pack_islands_scale_margin(islands, scale, margin, params, *phis_target) /
2114 params.target_extent;
2115 const float value = sqrtf(max_uv) - 1.0f;
2116
2117 if (value <= 0.0f) {
2118 scale_low = scale;
2119 value_low = value;
2120 phis_low = phis_target;
2121 if (value == 0.0f) {
2122 break; /* Target hit exactly. */
2123 }
2124 }
2125 else {
2126 scale_high = scale;
2127 value_high = value;
2128 if (scale == min_scale_roundoff) {
2129 /* Unable to pack without damaging UVs. */
2130 scale_low = scale;
2131 break;
2132 }
2133 if (!phis_low) {
2134 phis_low = phis_target; /* May as well do "something", even if it's wrong. */
2135 }
2136 }
2137 }
2138
2139 if (phis_low) {
2140 /* Write back best pack as a side-effect. */
2141 for (const int64_t i : islands.index_range()) {
2142 PackIsland *island = islands[i];
2143 const float island_scale = island->can_scale_(params) ? scale_low : 1.0f;
2144 island->place_(island_scale, (*phis_low)[i]);
2145 }
2146 }
2147 return scale_low;
2148}
2149
2151 const UVPackIsland_Params &params)
2152{
2153 /* Logic matches previous behavior from #geometry::uv_parametrizer_pack.
2154 * Attempt to give predictable results not dependent on current UV scale by using
2155 * `aabb_length_sum` (was "`area`") to multiply the margin by the length (was "area"). */
2156 double aabb_length_sum = 0.0f;
2157 for (PackIsland *island : island_vector) {
2158 float w = island->half_diagonal_.x * 2.0f;
2159 float h = island->half_diagonal_.y * 2.0f;
2160 aabb_length_sum += sqrtf(w * h);
2161 }
2162 return params.margin * aabb_length_sum * 0.1f;
2163}
2164
2165/* -------------------------------------------------------------------- */
2169
2170static bool overlap_aabb(const float2 &pivot_a,
2171 const float2 &half_diagonal_a,
2172 const float2 &pivot_b,
2173 const float2 &half_diagonal_b)
2174{
2175 if (pivot_a.x + half_diagonal_a.x <= pivot_b.x - half_diagonal_b.x) {
2176 return false;
2177 }
2178 if (pivot_a.y + half_diagonal_a.y <= pivot_b.y - half_diagonal_b.y) {
2179 return false;
2180 }
2181 if (pivot_b.x + half_diagonal_b.x <= pivot_a.x - half_diagonal_a.x) {
2182 return false;
2183 }
2184 if (pivot_b.y + half_diagonal_b.y <= pivot_a.y - half_diagonal_a.y) {
2185 return false;
2186 }
2187 return true;
2188}
2189
2191 public:
2192 static bool overlap(PackIsland *a, PackIsland *b)
2193 {
2194 if (a->aspect_y != b->aspect_y) {
2195 return false; /* Cannot merge islands with different aspect ratios. */
2196 }
2197 if (!overlap_aabb(a->pivot_, a->half_diagonal_, b->pivot_, b->half_diagonal_)) {
2198 return false; /* AABBs are disjoint => islands are separate. */
2199 }
2200 for (int i = 0; i < a->triangle_vertices_.size(); i += 3) {
2201 for (int j = 0; j < b->triangle_vertices_.size(); j += 3) {
2203 a->triangle_vertices_[i + 1],
2204 a->triangle_vertices_[i + 2],
2205 b->triangle_vertices_[j + 0],
2206 b->triangle_vertices_[j + 1],
2207 b->triangle_vertices_[j + 2]))
2208 {
2209 return true; /* Two triangles overlap => islands overlap. */
2210 }
2211 }
2212 }
2213
2214 return false; /* Separate. */
2215 }
2216
2217 static void add_geometry(PackIsland *dest, const PackIsland *source)
2218 {
2219 for (int64_t i = 0; i < source->triangle_vertices_.size(); i += 3) {
2220 dest->add_triangle(source->triangle_vertices_[i],
2221 source->triangle_vertices_[i + 1],
2222 source->triangle_vertices_[i + 2]);
2223 }
2224 }
2225
2228 {
2229 PackIsland *result = new PackIsland();
2230 result->aspect_y = sqrtf(a->aspect_y * b->aspect_y);
2231 result->caller_index = -1;
2232 result->pinned = a->pinned || b->pinned;
2233 add_geometry(result, a);
2235 result->calculate_pivot_();
2236 return result;
2237 }
2238
2240 const UVPackIsland_Params &params)
2241 {
2242
2243 /* Building the binary-tree of merges is complicated to do in a single pass if we proceed in
2244 * the forward order. Instead we'll continuously update the tree as we descend, with
2245 * `sub_islands` doing the work of our stack. See #merge_islands for details.
2246 *
2247 * Technically, performance is O(n^2). In practice, should be fast enough. */
2248
2249 Vector<PackIsland *> sub_islands; /* Pack these islands instead. */
2250 Vector<PackIsland *> merge_trace; /* Trace merge information. */
2251 for (const int64_t i : islands.index_range()) {
2252 PackIsland *island = islands[i];
2253 island->calculate_pivot_();
2254
2255 /* Loop backwards, building a binary tree of all merged islands as we descend. */
2256 for (int64_t j = sub_islands.size() - 1; j >= 0; j--) {
2257 if (overlap(island, sub_islands[j])) {
2258 merge_trace.append(island);
2259 merge_trace.append(sub_islands[j]);
2260 island = merge_islands(island, sub_islands[j]);
2261 merge_trace.append(island);
2262 sub_islands.remove(j);
2263 }
2264 }
2265 sub_islands.append(island);
2266 }
2267
2268 /* Recursively call pack_islands with `merge_overlap = false`. */
2269 UVPackIsland_Params sub_params(params);
2270 sub_params.merge_overlap = false;
2271 const float result = pack_islands(sub_islands, sub_params);
2272
2273 /* Must loop backwards, or we will miss sub-sub-islands. */
2274 for (int64_t i = merge_trace.size() - 3; i >= 0; i -= 3) {
2275 PackIsland *sub_a = merge_trace[i];
2276 PackIsland *sub_b = merge_trace[i + 1];
2277 PackIsland *merge = merge_trace[i + 2];
2278
2279 /* Copy `angle`, `pre_translate` & `pre_rotate_sincos_` from merged island to sub islands. */
2280 sub_a->angle = merge->angle;
2281 sub_b->angle = merge->angle;
2282 sub_a->pre_translate = merge->pre_translate;
2283 sub_b->pre_translate = merge->pre_translate;
2284 sub_a->pre_rotate_sincos_ = merge->pre_rotate_sincos_;
2285 sub_b->pre_rotate_sincos_ = merge->pre_rotate_sincos_;
2286
2287 /* If the merged island is pinned, the sub-islands are also pinned to correct scaling. */
2288 if (merge->pinned) {
2289 sub_a->pinned = true;
2290 sub_b->pinned = true;
2291 }
2292 delete merge;
2293 }
2294
2295 return result;
2296 }
2297};
2298
2300{
2302 Heap *heap = BLI_heap_new();
2303 for (const int64_t i : islands.index_range()) {
2304 islands[i]->finalize_geometry_(params, arena, heap);
2305 BLI_memarena_clear(arena);
2306 }
2307
2308 BLI_heap_free(heap, nullptr);
2309 BLI_memarena_free(arena);
2310}
2311
2313{
2314 BLI_assert(0.0f <= params.margin);
2315 BLI_assert(0.0f <= params.target_aspect_y);
2316
2317 if (islands.is_empty()) {
2318 return 1.0f; /* Nothing to do, just create a safe default. */
2319 }
2320
2321 if (params.merge_overlap) {
2323 }
2324
2325 finalize_geometry(islands, params);
2326
2327 /* Count the number of islands which can scale and which can translate. */
2328 int64_t can_scale_count = 0;
2329 int64_t can_translate_count = 0;
2330 for (const int64_t i : islands.index_range()) {
2331 if (islands[i]->can_scale_(params)) {
2332 can_scale_count++;
2333 }
2334 if (islands[i]->can_translate_(params)) {
2335 can_translate_count++;
2336 }
2337 }
2338
2339 if (can_translate_count == 0) {
2340 return 1.0f; /* Nothing to do, all islands are locked. */
2341 }
2342
2343 if (params.margin_method == ED_UVPACK_MARGIN_FRACTION && params.margin > 0.0f &&
2344 can_scale_count > 0)
2345 {
2346 /* Uses a line search on scale. ~10x slower than other method. */
2347 return pack_islands_margin_fraction(islands, params.margin, false, params);
2348 }
2349
2350 float margin = params.margin;
2351 switch (params.margin_method) {
2352 case ED_UVPACK_MARGIN_ADD: /* Default for Blender 2.8 and earlier. */
2353 break; /* Nothing to do. */
2354 case ED_UVPACK_MARGIN_SCALED: /* Default for Blender 3.3 and later. */
2355 margin = calc_margin_from_aabb_length_sum(islands, params);
2356 break;
2357 case ED_UVPACK_MARGIN_FRACTION: /* Added as an option in Blender 3.4. */
2358 /* Most other cases are handled above, unless pinning is involved. */
2359 break;
2360 default:
2362 }
2363
2364 if (can_scale_count > 0 && can_scale_count != islands.size()) {
2365 /* Search for the best scale parameter. (slow) */
2366 return pack_islands_margin_fraction(islands, margin, true, params);
2367 }
2368
2369 /* Either all of the islands can scale, or none of them can.
2370 * In either case, we pack them all tight to the origin. */
2371 Array<UVPhi> phis(islands.size());
2372 const float scale = 1.0f;
2373 const float max_uv = pack_islands_scale_margin(islands, scale, margin, params, phis);
2374 const float result = can_scale_count && max_uv > 1e-14f ? params.target_extent / max_uv : 1.0f;
2375 for (const int64_t i : islands.index_range()) {
2376 BLI_assert(result == 1.0f || islands[i]->can_scale_(params));
2377 islands[i]->place_(scale, phis[i]);
2378 }
2379 return result;
2380}
2381
2383
2385 const double angle,
2386 float (*r_matrix)[2]) const
2387{
2388 const double cos_angle = cos(angle);
2389 const double sin_angle = sin(angle);
2390 r_matrix[0][0] = cos_angle * scale;
2391 r_matrix[0][1] = -sin_angle * scale * aspect_y;
2392 r_matrix[1][0] = sin_angle * scale / aspect_y;
2393 r_matrix[1][1] = cos_angle * scale;
2394#if 0
2395 if (reflect) {
2396 r_matrix[0][0] *= -1.0f;
2397 r_matrix[0][1] *= -1.0f;
2398 }
2399#endif
2400}
2401
2403 const double angle,
2404 float (*r_matrix)[2]) const
2405{
2406 const double cos_angle = cos(angle);
2407 const double sin_angle = sin(angle);
2408
2409 r_matrix[0][0] = cos_angle / scale;
2410 r_matrix[0][1] = sin_angle / scale * aspect_y;
2411 r_matrix[1][0] = -sin_angle / scale / aspect_y;
2412 r_matrix[1][1] = cos_angle / scale;
2413#if 0
2414 if (reflect) {
2415 r_matrix[0][0] *= -1.0f;
2416 r_matrix[1][0] *= -1.0f;
2417 }
2418#endif
2419}
2420
2421static bool can_rotate_with_method(const PackIsland &island,
2422 const UVPackIsland_Params &params,
2423 const eUVPackIsland_RotationMethod rotate_method)
2424{
2425 /* When axis aligned along X/Y coordinates, rotation is performed once early on,
2426 * but no rotation is allowed when packing. */
2427 if (ELEM(rotate_method,
2431 {
2432 return false;
2433 }
2434 if (!island.pinned) {
2435 return true;
2436 }
2437 switch (params.pin_method) {
2441 return false;
2442 default:
2443 return true;
2444 }
2445}
2446
2448{
2449 eUVPackIsland_RotationMethod rotate_method = params.rotate_method;
2451 rotate_method = ED_UVPACK_ROTATION_AXIS_ALIGNED;
2452 }
2453 return can_rotate_with_method(*this, params, rotate_method);
2454}
2455
2457{
2458 return can_rotate_with_method(*this, params, params.rotate_method);
2459}
2460
2462{
2463 if (!params.scale_to_fit) {
2464 return false;
2465 }
2466 if (!pinned) {
2467 return true;
2468 }
2469 switch (params.pin_method) {
2473 return false;
2474 default:
2475 return true;
2476 }
2477}
2478
2480{
2481 if (!pinned) {
2482 return true;
2483 }
2484 switch (params.pin_method) {
2486 return false;
2487 default:
2488 return true;
2489 }
2490}
2491
2492} // namespace blender::geometry
#define DEG2RADF(_deg)
#define BLI_MEMARENA_STD_BUFSIZE
Read Blender memory allocation and freeing.
#define BLI_assert_unreachable()
#define UNUSED_VARS(...)
#define BLI_assert(a)
#define ELEM(...)
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr Span take_front(int64_t n) const
Definition BLI_span.hh:197
const T * end() const
Definition BLI_array.hh:336
const T * begin() const
Definition BLI_array.hh:332
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr Span()=default
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr Span take_front(int64_t n) const
Definition BLI_span.hh:197
int64_t size() const
void append(const T &value)
void remove(const int64_t index)
IndexRange index_range() const
void resize(const int64_t new_size)
float trace_triangle(const float2 &uv0, const float2 &uv1, const float2 &uv2, const float margin, const bool write) const
Definition uv_pack.cc:1241
Occupancy(const float initial_scale)
Definition uv_pack.cc:1195
float trace_island(const PackIsland *island, const UVPhi phi, const float scale, const float margin, const bool write) const
Definition uv_pack.cc:1331
static float pack_islands_overlap(const Span< PackIsland * > islands, const UVPackIsland_Params &params)
Definition uv_pack.cc:2239
static void add_geometry(PackIsland *dest, const PackIsland *source)
Definition uv_pack.cc:2217
static bool overlap(PackIsland *a, PackIsland *b)
Definition uv_pack.cc:2192
static PackIsland * merge_islands(const PackIsland *a, const PackIsland *b)
Definition uv_pack.cc:2227
void place_(float scale, UVPhi phi)
Definition uv_pack.cc:424
bool can_scale_(const UVPackIsland_Params &params) const
Definition uv_pack.cc:2461
void finalize_geometry_(const UVPackIsland_Params &params, MemArena *arena, Heap *heap)
Definition uv_pack.cc:350
bool can_rotate_before_pack_(const UVPackIsland_Params &params) const
Definition uv_pack.cc:2447
void add_polygon(Span< float2 > uvs, MemArena *arena, Heap *heap)
Definition uv_pack.cc:155
void build_transformation(float scale, double angle, float r_matrix[2][2]) const
Definition uv_pack.cc:2384
void build_inverse_transformation(float scale, double angle, float r_matrix[2][2]) const
Definition uv_pack.cc:2402
bool can_rotate_(const UVPackIsland_Params &params) const
Definition uv_pack.cc:2456
Vector< float2 > triangle_vertices_
bool can_translate_(const UVPackIsland_Params &params) const
Definition uv_pack.cc:2479
void add_triangle(float2 uv0, float2 uv1, float2 uv2)
Definition uv_pack.cc:140
float2 get_diagonal_support(float scale, float rotation, float margin) const
Definition uv_pack.cc:1302
UVMinimumEnclosingSquareFinder(const float scale, const float margin, const UVPackIsland_Params *params)
Definition uv_pack.cc:1473
void update_recursive(const float angle0, const float quad0, const float angle1, const float quad1)
Definition uv_pack.cc:1512
eUVPackIsland_RotationMethod rotate_method
eUVPackIsland_MarginMethod margin_method
eUVPackIsland_ShapeMethod shape_method
eUVPackIsland_PinMethod pin_method
bool is_valid() const
Definition uv_pack.cc:41
#define FLT_EPSILON
#define sin
VecBase< T, D > reflect(VecOp< T, D >, VecOp< T, D >) RET
#define cos
float distance(float, float) RET
float3x3 scale(float3x3 mat, float2 scale)
float3x3 rotate(float3x3 mat, AxisAngle rotation)
OrientationBounds merge(const OrientationBounds &cone_a, const OrientationBounds &cone_b)
ccl_device_inline void sincos(const float3 x, ccl_private float3 *sine, ccl_private float3 *cosine)
std::optional< Bounds< T > > min_max(const std::optional< Bounds< T > > &a, const T &b)
Definition BLI_bounds.hh:56
static int64_t pack_island_xatlas(const Span< std::unique_ptr< UVAABBIsland > > island_indices, const Span< PackIsland * > islands, const float scale, const float margin, const UVPackIsland_Params &params, MutableSpan< UVPhi > r_phis, rctf *r_extent)
Definition uv_pack.cc:1642
static void pack_islands_optimal_pack(const Span< std::unique_ptr< UVAABBIsland > > aabbs, const UVPackIsland_Params &params, MutableSpan< UVPhi > r_phis, rctf *r_extent)
Definition uv_pack.cc:783
static void inverse_transformation_from_sincos(const float2 &sincos, const float aspect_y, float r_matrix[2][2])
Definition uv_pack.cc:251
static float get_aspect_scaled_extent(const rctf &extent, const UVPackIsland_Params &params)
Definition uv_pack.cc:92
static void pack_gobel(const Span< std::unique_ptr< UVAABBIsland > > aabbs, const float scale, const int m, MutableSpan< UVPhi > r_phis)
Definition uv_pack.cc:717
static float2 sincos_plusminus_90(const float2 &sincos)
Definition uv_pack.cc:225
static void pack_islands_alpaca_rotate(const int64_t exclude_index, const rctf &exclude, const Span< std::unique_ptr< UVAABBIsland > > islands, const float target_aspect_y, MutableSpan< UVPhi > r_phis, rctf *r_extent)
Definition uv_pack.cc:594
static void transformation_from_sincos(const float2 &sincos, const float aspect_y, float r_matrix[2][2])
Definition uv_pack.cc:240
static float dist_signed_squared_to_edge(const float2 probe, const float2 uva, const float2 uvb)
Definition uv_pack.cc:72
static float pack_islands_margin_fraction(const Span< PackIsland * > islands, const float margin_fraction, const bool rescale_margin, const UVPackIsland_Params &params)
Definition uv_pack.cc:2036
static void pack_islands_alpaca_turbo(const int64_t exclude_index, const rctf &exclude, const Span< std::unique_ptr< UVAABBIsland > > islands, const float target_aspect_y, MutableSpan< UVPhi > r_phis, rctf *r_extent)
Definition uv_pack.cc:483
static void pack_island_box_pack_2d(const Span< std::unique_ptr< UVAABBIsland > > aabbs, const UVPackIsland_Params &params, MutableSpan< UVPhi > r_phis, rctf *r_extent)
Definition uv_pack.cc:1116
static float get_aspect_scaled_area(const rctf &extent, const UVPackIsland_Params &params)
Definition uv_pack.cc:102
static bool is_larger(const rctf &a, const rctf &b, const UVPackIsland_Params &params)
Definition uv_pack.cc:112
void mul_v2_m2_add_v2v2(float r[2], const float mat[2][2], const float a[2], const float b[2])
Definition uv_pack.cc:46
static float signed_distance_fat_triangle(const float2 probe, const float2 uv0, const float2 uv1, const float2 uv2)
Definition uv_pack.cc:1220
static float pack_islands_scale_margin(const Span< PackIsland * > islands, const float scale, const float margin, const UVPackIsland_Params &params, MutableSpan< UVPhi > r_phis)
Definition uv_pack.cc:1839
static bool overlap_aabb(const float2 &pivot_a, const float2 &half_diagonal_a, const float2 &pivot_b, const float2 &half_diagonal_b)
Definition uv_pack.cc:2170
static bool can_rotate(const Span< PackIsland * > islands, const UVPackIsland_Params &params)
Definition uv_pack.cc:191
static void update_hole_rotate(float2 &hole, float2 &hole_diagonal, bool &hole_rotate, const float u0, const float v0, const float u1, const float v1)
Definition uv_pack.cc:552
static bool pack_islands_optimal_pack_table(const int table_count, const float max_extent, const float *optimal, const char *, int64_t island_count, const float large_uv, const Span< std::unique_ptr< UVAABBIsland > > aabbs, const UVPackIsland_Params &params, MutableSpan< UVPhi > r_phis, rctf *r_extent)
Definition uv_pack.cc:753
static UVPhi find_best_fit_for_island(const PackIsland *island, const int scan_line, const Occupancy &occupancy, const float scale, const int angle_90_multiple, const float margin, const float target_aspect_y)
Definition uv_pack.cc:1376
static bool can_rotate_with_method(const PackIsland &island, const UVPackIsland_Params &params, const eUVPackIsland_RotationMethod rotate_method)
Definition uv_pack.cc:2421
static bool rotate_inside_square(const Span< std::unique_ptr< UVAABBIsland > > island_indices, const Span< PackIsland * > islands, const UVPackIsland_Params &params, const float scale, const float margin, MutableSpan< UVPhi > r_phis, rctf *r_extent)
Definition uv_pack.cc:1542
static float2 sincos_rotate_90(const float2 &sincos)
Definition uv_pack.cc:205
static float2 sincos_wrap(const float2 &sincos)
Definition uv_pack.cc:216
float pack_islands(Span< PackIsland * > islands, const UVPackIsland_Params &params)
static void pack_islands_fast(const int64_t exclude_index, const rctf &exclude, const Span< std::unique_ptr< UVAABBIsland > > aabbs, const bool rotate, const float target_aspect_y, MutableSpan< UVPhi > r_phis, rctf *r_extent)
Definition uv_pack.cc:700
static float guess_initial_scale(const Span< PackIsland * > islands, const float scale, const float margin)
Definition uv_pack.cc:1446
static void finalize_geometry(const Span< PackIsland * > islands, const UVPackIsland_Params &params)
Definition uv_pack.cc:2299
static float calc_margin_from_aabb_length_sum(const Span< PackIsland * > island_vector, const UVPackIsland_Params &params)
Definition uv_pack.cc:2150
T length_squared(const VecBase< T, Size > &a)
MINLINE float min_ff(float a, float b)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
MINLINE int compare_ff_relative(float a, float b, float max_diff, int max_ulps)
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
unsigned int BLI_heap_len(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:276
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
float2 BLI_convexhull_aabb_fit_points_2d_as_sincos(Span< float2 > points)
@ ED_UVPACK_PIN_LOCK_ROTATION
@ ED_UVPACK_PIN_LOCK_SCALE
@ ED_UVPACK_PIN_LOCK_ROTATION_SCALE
@ ED_UVPACK_PIN_NONE
@ ED_UVPACK_PIN_LOCK_ALL
void BLI_rctf_do_minmax_v(struct rctf *rect, const float xy[2])
Definition rct.cc:524
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:193
void BLI_polyfill_calc_arena(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3], struct MemArena *arena)
int BLI_convexhull_2d(Span< float2 > points, int r_points[])
Global G
Definition blender.cc:57
@ ED_UVPACK_MARGIN_ADD
@ ED_UVPACK_MARGIN_FRACTION
@ ED_UVPACK_MARGIN_SCALED
VecBase< float, 2 > float2
bool BLI_rctf_compare(const struct rctf *rect_a, const struct rctf *rect_b, float limit)
BLI_INLINE float BLI_rctf_size_y(const struct rctf *rct)
Definition BLI_rect.hh:215
void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
sqrt(x)+1/max(0
void BLI_rctf_init_minmax(struct rctf *rect)
Definition rct.cc:494
void mul_v2_m2v2(float r[2], const float mat[2][2], const float vec[2])
void mul_m2_v2(const float mat[2][2], float vec[2])
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
BLI_INLINE float BLI_rctf_size_x(const struct rctf *rct)
Definition BLI_rect.hh:211
MINLINE float max_ff(float a, float b)
Heap * BLI_heap_new() ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:188
bool isect_tri_tri_v2(const float t_a0[2], const float t_a1[2], const float t_a2[2], const float t_b0[2], const float t_b1[2], const float t_b2[2])
MINLINE void sub_v2_v2(float r[2], const float a[2])
eUVPackIsland_RotationMethod
@ ED_UVPACK_ROTATION_CARDINAL
@ ED_UVPACK_ROTATION_AXIS_ALIGNED_Y
@ ED_UVPACK_ROTATION_AXIS_ALIGNED
@ ED_UVPACK_ROTATION_NONE
@ ED_UVPACK_ROTATION_AXIS_ALIGNED_X
@ ED_UVPACK_ROTATION_ANY
eUVPackIsland_ShapeMethod
@ ED_UVPACK_SHAPE_CONVEX
@ ED_UVPACK_SHAPE_AABB
void BLI_box_pack_2d(BoxPack *boxarray, unsigned int len, bool sort_boxes, float *r_tot_x, float *r_tot_y)
void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:215
void BLI_polyfill_beautify(const float(*coords)[2], unsigned int coords_num, unsigned int(*tris)[3], struct MemArena *arena, struct Heap *eheap)
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
const btScalar eps
Definition poly34.cpp:11
#define floorf
#define fabsf
#define sqrtf
#define cosf
#define ceilf
#define atan2f
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
float x
float y