Blender V5.3
uv_parametrizer.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 <functional>
10#include <vector>
11
13
14#include "BLI_array.hh"
15#include "BLI_bounds.hh"
16#include "BLI_convexhull_2d.hh"
17#include "BLI_ghash.hh"
18#include "BLI_math_base_safe.hh"
19#include "BLI_math_geom_c.hh"
20#include "BLI_math_matrix_c.hh"
22#include "BLI_math_vector_c.hh"
23#include "BLI_polyfill_2d.hh"
25#include "BLI_rand_c.hh"
26#include "BLI_vector.hh"
27
28#ifdef WITH_UV_SLIM
29# include "slim_matrix_transfer.h"
30#endif
31
32#include "GEO_uv_pack.hh"
33
34#include "eigen_capi.h"
35
36/* Utils */
37
38namespace blender::geometry {
39
40#define param_warning(message) \
41 {/* `printf("Warning %s:%d: %s\n", __FILE__, __LINE__, message);` */}(void)0
42
43/* Prevent unused function warnings when slim is disabled. */
44#ifdef WITH_UV_SLIM
45# define UNUSED_FUNCTION_NO_SLIM(x) x
46#else
47# define UNUSED_FUNCTION_NO_SLIM UNUSED_FUNCTION
48#endif
49
50/* Special Purpose Hash */
51
53
58
64
65/* Simplices */
66
67struct PVert {
69
70 union PVertUnion {
71 PHashKey key; /* Construct. */
72 int id; /* ABF/LSCM matrix index. */
73 HeapNode *heaplink; /* Edge collapsing. */
74 } u;
75
76 struct PEdge *edge;
77 float co[3];
78 float uv[2];
80
81 float weight;
84};
85
86struct PEdge {
88
89 union PEdgeUnion {
90 PHashKey key; /* Construct. */
91 int id; /* ABF matrix index. */
92 PEdge *nextcollapse; /* Simplification. */
93 } u;
94
98 struct PFace *face;
99 float *orig_uv, old_uv[2];
101};
102
103struct PFace {
105
107 PHashKey key; /* Construct. */
108 int chart; /* Construct splitting. */
109 float area3d; /* Stretch. */
110 int id; /* ABF matrix index. */
111 } u;
112
115};
116
117constexpr static int P_NGON_STACK_NUM = 32;
118
126
138
139/* for flipping faces */
140#define PEDGE_VERTEX_FLAGS (PEDGE_PIN)
141
148
149/* Chart */
150
156
185
186static float p_chart_minimum_area_angle(PChart *chart);
187
188/* PHash
189 * - special purpose hash that keeps all its elements in a single linked list.
190 * - after construction, this hash is thrown away, and the list remains.
191 * - removing elements is not possible efficiently.
192 */
193
194static int PHashSizes[] = {
195 1, 3, 5, 11, 17, 37, 67, 131, 257, 521,
196 1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309,
197 1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459,
198};
199
200#define PHASH_hash(ph, item) (uintptr_t(item) % uint((ph)->cursize))
201#define PHASH_edge(v1, v2) (((v1) < (v2)) ? ((v1) * 39) ^ ((v2) * 31) : ((v1) * 31) ^ ((v2) * 39))
202
203static PHash *phash_new(PHashLink **list, int sizehint)
204{
205 PHash *ph = MEM_new_zeroed<PHash>("PHash");
206 ph->size = 0;
207 ph->cursize_id = 0;
208 ph->list = list;
209
210 while (PHashSizes[ph->cursize_id] < sizehint) {
211 ph->cursize_id++;
212 }
213
214 ph->cursize = PHashSizes[ph->cursize_id];
215 ph->buckets = MEM_new_array_zeroed<PHashLink *>(ph->cursize, "PHashBuckets");
216
217 return ph;
218}
219
220static void phash_safe_delete(PHash **pph)
221{
222 if (!*pph) {
223 return;
224 }
225 MEM_SAFE_DELETE((*pph)->buckets);
226 MEM_delete(*pph);
227 *pph = nullptr;
228}
229
230static int phash_size(PHash *ph)
231{
232 return ph->size;
233}
234
235static void phash_insert(PHash *ph, PHashLink *link)
236{
237 int size = ph->cursize;
238 uintptr_t hash = PHASH_hash(ph, link->key);
239 PHashLink *lookup = ph->buckets[hash];
240
241 if (lookup == nullptr) {
242 /* insert in front of the list */
243 ph->buckets[hash] = link;
244 link->next = *(ph->list);
245 *(ph->list) = link;
246 }
247 else {
248 /* insert after existing element */
249 link->next = lookup->next;
250 lookup->next = link;
251 }
252
253 ph->size++;
254
255 if (ph->size > (size * 3)) {
256 PHashLink *next = nullptr, *first = *(ph->list);
257
258 ph->cursize = PHashSizes[++ph->cursize_id];
259 MEM_delete(ph->buckets);
260 ph->buckets = MEM_new_array_zeroed<PHashLink *>(ph->cursize, "PHashBuckets");
261 ph->size = 0;
262 *(ph->list) = nullptr;
263
264 for (link = first; link; link = next) {
265 next = link->next;
266 phash_insert(ph, link);
267 }
268 }
269}
270
272{
273 PHashLink *link;
274 uintptr_t hash = PHASH_hash(ph, key);
275
276 for (link = ph->buckets[hash]; link; link = link->next) {
277 if (link->key == key) {
278 return link;
279 }
280 if (PHASH_hash(ph, link->key) != hash) {
281 return nullptr;
282 }
283 }
284
285 return link;
286}
287
289{
290 uintptr_t hash = PHASH_hash(ph, key);
291
292 for (link = link->next; link; link = link->next) {
293 if (link->key == key) {
294 return link;
295 }
296 if (PHASH_hash(ph, link->key) != hash) {
297 return nullptr;
298 }
299 }
300
301 return link;
302}
303
304/* Angles close to 0 or 180 degrees cause rows filled with zeros in the linear_solver.
305 * The matrix will then be rank deficient and / or have poor conditioning.
306 * => Reduce the maximum angle to 179 degrees, and spread the remainder to the other angles.
307 */
308static void fix_large_angle(const float v_fix[3],
309 const float v1[3],
310 const float v2[3],
311 double *r_fix,
312 double *r_a1,
313 double *r_a2)
314{
315 const double max_angle = DEG2RAD(179.0);
316 const double fix_amount = *r_fix - max_angle;
317 if (fix_amount < 0.0f) {
318 return; /* angle is reasonable, i.e. less than 179 degrees. */
319 }
320
321 /* The triangle is probably degenerate, or close to it.
322 * Without loss of generality, transform the triangle such that
323 * v_fix == { 0, s}, *r_fix = 180 degrees
324 * v1 == {-x1, 0}, *r_a1 = 0
325 * v2 == { x2, 0}, *r_a2 = 0
326 *
327 * With `s = 0`, `x1 > 0`, `x2 > 0`
328 *
329 * Now make `s` a small number and do some math:
330 * tan(*r_a1) = s / x1
331 * tan(*r_a2) = s / x2
332 *
333 * Remember that `tan(angle) ~= angle`
334 *
335 * Rearrange to obtain:
336 * *r_a1 = fix_amount * x2 / (x1 + x2)
337 * *r_a2 = fix_amount * x1 / (x1 + x2)
338 */
339
340 const double dist_v1 = len_v3v3(v_fix, v1);
341 const double dist_v2 = len_v3v3(v_fix, v2);
342 const double sum = dist_v1 + dist_v2;
343 const double weight = (sum > 1e-20f) ? dist_v2 / sum : 0.5f;
344
345 /* Ensure sum of angles in triangle is unchanged. */
346 *r_fix -= fix_amount;
347 *r_a1 += fix_amount * weight;
348 *r_a2 += fix_amount * (1.0f - weight);
349}
350
351static void p_triangle_angles(const float v1[3],
352 const float v2[3],
353 const float v3[3],
354 double *r_a1,
355 double *r_a2,
356 double *r_a3)
357{
358 *r_a1 = angle_v3v3v3(v3, v1, v2);
359 *r_a2 = angle_v3v3v3(v1, v2, v3);
360 *r_a3 = angle_v3v3v3(v2, v3, v1);
361
362 /* Fix for degenerate geometry e.g. v1 = sum(v2 + v3). See #100874 */
363 fix_large_angle(v1, v2, v3, r_a1, r_a2, r_a3);
364 fix_large_angle(v2, v3, v1, r_a2, r_a3, r_a1);
365 fix_large_angle(v3, v1, v2, r_a3, r_a1, r_a2);
366
367 /* Workaround for degenerate geometry, e.g. v1 == v2 == v3. */
368 *r_a1 = max_dd(*r_a1, 0.001f);
369 *r_a2 = max_dd(*r_a2, 0.001f);
370 *r_a3 = max_dd(*r_a3, 0.001f);
371}
372
373static void p_face_angles(PFace *f, double *r_a1, double *r_a2, double *r_a3)
374{
375 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
376 PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
377
378 p_triangle_angles(v1->co, v2->co, v3->co, r_a1, r_a2, r_a3);
379}
380
381static float p_vec_cos(const float v1[3], const float v2[3], const float v3[3])
382{
383 return cos_v3v3v3(v1, v2, v3);
384}
385
386static void p_triangle_cos(const float v1[3],
387 const float v2[3],
388 const float v3[3],
389 float *r_cos1,
390 float *r_cos2,
391 float *r_cos3)
392{
393 *r_cos1 = p_vec_cos(v3, v1, v2);
394 *r_cos2 = p_vec_cos(v1, v2, v3);
395 *r_cos3 = p_vec_cos(v2, v3, v1);
396}
397
398static void UNUSED_FUNCTION(p_face_cos)(PFace *f, float *r_cos1, float *r_cos2, float *r_cos3)
399{
400 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
401 PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
402
403 p_triangle_cos(v1->co, v2->co, v3->co, r_cos1, r_cos2, r_cos3);
404}
405
406static float p_face_area(PFace *f)
407{
408 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
409 PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
410
411 return area_tri_v3(v1->co, v2->co, v3->co);
412}
413
414static float p_area_signed(const float v1[2], const float v2[2], const float v3[2])
415{
416 return 0.5f * (((v2[0] - v1[0]) * (v3[1] - v1[1])) - ((v3[0] - v1[0]) * (v2[1] - v1[1])));
417}
418
420{
421 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
422 PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
423
424 return 0.5f * (((v2->uv[0] - v1->uv[0]) * (v3->uv[1] - v1->uv[1])) -
425 ((v3->uv[0] - v1->uv[0]) * (v2->uv[1] - v1->uv[1])));
426}
427
428static float p_edge_length(PEdge *e)
429{
430 return len_v3v3(e->vert->co, e->next->vert->co);
431}
432
434{
435 return len_squared_v3v3(e->vert->co, e->next->vert->co);
436}
437
439{
440 return len_v2v2(e->vert->uv, e->next->vert->uv);
441}
442
443static void p_chart_uv_bbox(PChart *chart, float minv[2], float maxv[2])
444{
445 PVert *v;
446
447 INIT_MINMAX2(minv, maxv);
448
449 for (v = chart->verts; v; v = v->nextlink) {
450 minmax_v2v2_v2(minv, maxv, v->uv);
451 }
452}
453
454static float p_chart_uv_area(PChart *chart)
455{
456 float area = 0.0f;
457
458 for (PFace *f = chart->faces; f; f = f->nextlink) {
459 area += fabsf(p_face_uv_area_signed(f));
460 }
461
462 return area;
463}
464
465static void p_chart_uv_scale(PChart *chart, const float scale)
466{
467 if (scale == 1.0f) {
468 return; /* Identity transform. */
469 }
470
471 for (PVert *v = chart->verts; v; v = v->nextlink) {
472 v->uv[0] *= scale;
473 v->uv[1] *= scale;
474 }
475}
476
477static void uv_parametrizer_scale_x(ParamHandle *phandle, const float scale_x)
478{
479 if (scale_x == 1.0f) {
480 return; /* Identity transform. */
481 }
482
483 /* Scale every chart. */
484 for (int i = 0; i < phandle->ncharts; i++) {
485 PChart *chart = phandle->charts[i];
486 for (PVert *v = chart->verts; v; v = v->nextlink) {
487 v->uv[0] *= scale_x; /* Only scale x axis. */
488 }
489 }
490}
491
492static void p_chart_uv_rotate(PChart *chart, float angle)
493{
494 if (angle == 0.0f) {
495 return;
496 }
497 const float cos_angle = cosf(angle);
498 const float sin_angle = sinf(angle);
499 for (PVert *v = chart->verts; v; v = v->nextlink) {
500 float x = v->uv[0] - chart->origin[0];
501 float y = v->uv[1] - chart->origin[1];
502 float x_rot = cos_angle * x - sin_angle * y;
503 float y_rot = sin_angle * x + cos_angle * y;
504 v->uv[0] = x_rot + chart->origin[0];
505 v->uv[1] = y_rot + chart->origin[1];
506 }
507}
508
509static void p_chart_uv_translate(PChart *chart, const float trans[2])
510{
511 for (PVert *v = chart->verts; v; v = v->nextlink) {
512 v->uv[0] += trans[0];
513 v->uv[1] += trans[1];
514 }
515}
516
517static void p_chart_uv_transform(PChart *chart, const float mat[2][2])
518{
519 for (PVert *v = chart->verts; v; v = v->nextlink) {
520 mul_m2_v2(mat, v->uv);
521 }
522}
523
525{
526 PVert *v;
527 uint i = 0;
528
529 for (v = chart->verts; v; v = v->nextlink) {
530 copy_v2_v2(points[i++], v->uv);
531 }
532}
533
534static bool p_intersect_line_2d_dir(const float v1[2],
535 const float dir1[2],
536 const float v2[2],
537 const float dir2[2],
538 float r_isect[2])
539{
540 float lmbda, div;
541
542 div = dir2[0] * dir1[1] - dir2[1] * dir1[0];
543
544 if (div == 0.0f) {
545 return false;
546 }
547
548 lmbda = ((v1[1] - v2[1]) * dir1[0] - (v1[0] - v2[0]) * dir1[1]) / div;
549 r_isect[0] = v1[0] + lmbda * dir2[0];
550 r_isect[1] = v1[1] + lmbda * dir2[1];
551
552 return true;
553}
554
555/* Topological Utilities */
556
558{
559 return e->next->next->pair;
560}
561
562static const PEdge *p_wheel_edge_next(const PEdge *e)
563{
564 return e->next->next->pair;
565}
566
568{
569 return (e->pair) ? e->pair->next : nullptr;
570}
571
573{
574 return e->next->vert->edge;
575}
576
578{
579 PEdge *we = e, *last;
580
581 do {
582 last = we;
583 we = p_wheel_edge_next(we);
584 } while (we && (we != e));
585
586 return last->next->next;
587}
588
590{
591 return v->edge->pair;
592}
593
594static void p_face_flip(PFace *f)
595{
596 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
597 PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
598 int f1 = e1->flag, f2 = e2->flag, f3 = e3->flag;
599 float *orig_uv1 = e1->orig_uv, *orig_uv2 = e2->orig_uv, *orig_uv3 = e3->orig_uv;
600
601 e1->vert = v2;
602 e1->next = e3;
603 e1->orig_uv = orig_uv2;
604 e1->flag = (f1 & ~PEDGE_VERTEX_FLAGS) | (f2 & PEDGE_VERTEX_FLAGS);
605
606 e2->vert = v3;
607 e2->next = e1;
608 e2->orig_uv = orig_uv3;
609 e2->flag = (f2 & ~PEDGE_VERTEX_FLAGS) | (f3 & PEDGE_VERTEX_FLAGS);
610
611 e3->vert = v1;
612 e3->next = e2;
613 e3->orig_uv = orig_uv1;
614 e3->flag = (f3 & ~PEDGE_VERTEX_FLAGS) | (f1 & PEDGE_VERTEX_FLAGS);
615}
616
617#if 0
618static void p_chart_topological_sanity_check(PChart *chart)
619{
620 PVert *v;
621 PEdge *e;
622
623 for (v = chart->verts; v; v = v->nextlink) {
624 GEO_uv_parametrizer_test_equals_ptr("v->edge->vert", v, v->edge->vert);
625 }
626
627 for (e = chart->edges; e; e = e->nextlink) {
628 if (e->pair) {
629 GEO_uv_parametrizer_test_equals_ptr("e->pair->pair", e, e->pair->pair);
630 GEO_uv_parametrizer_test_equals_ptr("pair->vert", e->vert, e->pair->next->vert);
631 GEO_uv_parametrizer_test_equals_ptr("pair->next->vert", e->next->vert, e->pair->vert);
632 }
633 }
634}
635#endif
636
637/* Loading / Flushing */
638
640{
641 PEdge *e;
642 int nedges = 0, npins = 0;
643 float pinuv[2];
644
645 v->uv[0] = v->uv[1] = 0.0f;
646 pinuv[0] = pinuv[1] = 0.0f;
647 e = v->edge;
648 do {
649 if (e->orig_uv) {
650 if (e->flag & PEDGE_SELECT) {
651 v->flag |= PVERT_SELECT;
652 }
653
654 if (e->flag & PEDGE_PIN) {
655 pinuv[0] += e->orig_uv[0] * handle->aspect_y;
656 pinuv[1] += e->orig_uv[1];
657 npins++;
658 }
659 else {
660 v->uv[0] += e->orig_uv[0] * handle->aspect_y;
661 v->uv[1] += e->orig_uv[1];
662 }
663
664 nedges++;
665 }
666
668 } while (e && e != (v->edge));
669
670 if (npins > 0) {
671 v->uv[0] = pinuv[0] / npins;
672 v->uv[1] = pinuv[1] / npins;
673 v->flag |= PVERT_PIN;
674 }
675 else if (nedges > 0) {
676 v->uv[0] /= nedges;
677 v->uv[1] /= nedges;
678 }
679}
680
681static void p_chart_flush_collapsed_uvs(PChart *chart);
682
683static void p_flush_uvs(ParamHandle *handle, PChart *chart)
684{
685 const float blend = handle->blend;
686 const float invblend = 1.0f - blend;
687 const float invblend_x = invblend / handle->aspect_y;
688 for (PEdge *e = chart->edges; e; e = e->nextlink) {
689 if (e->orig_uv) {
690 e->orig_uv[0] = blend * e->old_uv[0] + invblend_x * e->vert->uv[0];
691 e->orig_uv[1] = blend * e->old_uv[1] + invblend * e->vert->uv[1];
692 }
693 }
694
695 if (chart->collapsed_edges) {
697
698 for (PEdge *e = chart->collapsed_edges; e; e = e->nextlink) {
699 if (e->orig_uv) {
700 e->orig_uv[0] = blend * e->old_uv[0] + invblend_x * e->vert->uv[0];
701 e->orig_uv[1] = blend * e->old_uv[1] + invblend * e->vert->uv[1];
702 }
703 }
704 }
705}
706
708{
709 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
710
711 if (e1->orig_uv) {
712 e1->old_uv[0] = e1->orig_uv[0];
713 e1->old_uv[1] = e1->orig_uv[1];
714 }
715 if (e2->orig_uv) {
716 e2->old_uv[0] = e2->orig_uv[0];
717 e2->old_uv[1] = e2->orig_uv[1];
718 }
719 if (e3->orig_uv) {
720 e3->old_uv[0] = e3->orig_uv[0];
721 e3->old_uv[1] = e3->orig_uv[1];
722 }
723}
724
726{
727 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
728
729 if (e1->orig_uv) {
730 e1->orig_uv[0] = e1->old_uv[0];
731 e1->orig_uv[1] = e1->old_uv[1];
732 }
733 if (e2->orig_uv) {
734 e2->orig_uv[0] = e2->old_uv[0];
735 e2->orig_uv[1] = e2->old_uv[1];
736 }
737 if (e3->orig_uv) {
738 e3->orig_uv[0] = e3->old_uv[0];
739 e3->orig_uv[1] = e3->old_uv[1];
740 }
741}
742
743/* Construction (use only during construction, relies on `u.key` being set). */
744
746 ParamHandle *handle, PHashKey key, const float co[3], const float weight, PEdge *e)
747{
748 PVert *v = static_cast<PVert *>(BLI_memarena_alloc(handle->arena, sizeof(*v)));
749 copy_v3_v3(v->co, co);
750 v->weight = weight;
751
752 /* Sanity check, a single nan/inf point causes the entire result to be invalid.
753 * Note that values within the calculation may _become_ non-finite,
754 * so the rest of the code still needs to take this possibility into account. */
755 for (int i = 0; i < 3; i++) {
756 if (!isfinite(v->co[i])) [[unlikely]] {
757 v->co[i] = 0.0f;
758 }
759 }
760
761 v->u.key = key;
762 v->edge = e;
763 v->flag = 0;
764
765 /* Unused, prevent uninitialized memory access on duplication. */
766 v->on_boundary_flag = false;
767 v->slim_id = 0;
768
769 phash_insert(handle->hash_verts, reinterpret_cast<PHashLink *>(v));
770
771 return v;
772}
773
775 ParamHandle *handle, PHashKey key, const float co[3], const float weight, PEdge *e)
776{
777 PVert *v = reinterpret_cast<PVert *>(phash_lookup(handle->hash_verts, key));
778
779 if (v) {
780 return v;
781 }
782 return p_vert_add(handle, key, co, weight, e);
783}
784
786{
787 PVert *nv = static_cast<PVert *>(BLI_memarena_alloc(handle->arena, sizeof(*nv)));
788
789 copy_v3_v3(nv->co, v->co);
790 nv->uv[0] = v->uv[0];
791 nv->uv[1] = v->uv[1];
792 nv->u.key = v->u.key;
793 nv->edge = v->edge;
794 nv->flag = v->flag;
795
796 nv->weight = v->weight;
797 nv->on_boundary_flag = v->on_boundary_flag;
798 nv->slim_id = v->slim_id;
799
800 return nv;
801}
802
803static PEdge *p_edge_lookup(ParamHandle *handle, const PHashKey *vkeys)
804{
805 PHashKey key = PHASH_edge(vkeys[0], vkeys[1]);
806 PEdge *e = reinterpret_cast<PEdge *>(phash_lookup(handle->hash_edges, key));
807
808 while (e) {
809 if ((e->vert->u.key == vkeys[0]) && (e->next->vert->u.key == vkeys[1])) {
810 return e;
811 }
812 if ((e->vert->u.key == vkeys[1]) && (e->next->vert->u.key == vkeys[0])) {
813 return e;
814 }
815
816 e = reinterpret_cast<PEdge *>(
817 phash_next(handle->hash_edges, key, reinterpret_cast<PHashLink *>(e)));
818 }
819
820 return nullptr;
821}
822
823static int p_face_exists(ParamHandle *handle, const ParamKey *pvkeys, int i1, int i2, int i3)
824{
825 PHashKey *vkeys = const_cast<PHashKey *>(pvkeys);
826 PHashKey key = PHASH_edge(vkeys[i1], vkeys[i2]);
827 PEdge *e = reinterpret_cast<PEdge *>(phash_lookup(handle->hash_edges, key));
828
829 while (e) {
830 if ((e->vert->u.key == vkeys[i1]) && (e->next->vert->u.key == vkeys[i2])) {
831 if (e->next->next->vert->u.key == vkeys[i3]) {
832 return true;
833 }
834 }
835 else if ((e->vert->u.key == vkeys[i2]) && (e->next->vert->u.key == vkeys[i1])) {
836 if (e->next->next->vert->u.key == vkeys[i3]) {
837 return true;
838 }
839 }
840
841 e = reinterpret_cast<PEdge *>(
842 phash_next(handle->hash_edges, key, reinterpret_cast<PHashLink *>(e)));
843 }
844
845 return false;
846}
847
849{
850 const float *uv1, *uv2, *uvp1, *uvp2;
851 float limit[2];
852
853 limit[0] = 0.00001;
854 limit[1] = 0.00001;
855
856 uv1 = e->orig_uv;
857 uv2 = e->next->orig_uv;
858
859 if (e->vert->u.key == ep->vert->u.key) {
860 uvp1 = ep->orig_uv;
861 uvp2 = ep->next->orig_uv;
862 }
863 else {
864 uvp1 = ep->next->orig_uv;
865 uvp2 = ep->orig_uv;
866 }
867
868 if ((fabsf(uv1[0] - uvp1[0]) > limit[0]) || (fabsf(uv1[1] - uvp1[1]) > limit[1])) {
869 e->flag |= PEDGE_SEAM;
870 ep->flag |= PEDGE_SEAM;
871 return true;
872 }
873 if ((fabsf(uv2[0] - uvp2[0]) > limit[0]) || (fabsf(uv2[1] - uvp2[1]) > limit[1])) {
874 e->flag |= PEDGE_SEAM;
875 ep->flag |= PEDGE_SEAM;
876 return true;
877 }
878
879 return false;
880}
881
882static bool p_edge_has_pair(ParamHandle *handle, PEdge *e, bool topology_from_uvs, PEdge **r_pair)
883{
884 PHashKey key;
885 PEdge *pe;
886 const PVert *v1, *v2;
887 PHashKey key1 = e->vert->u.key;
888 PHashKey key2 = e->next->vert->u.key;
889
890 if (e->flag & PEDGE_SEAM) {
891 return false;
892 }
893
894 key = PHASH_edge(key1, key2);
895 pe = reinterpret_cast<PEdge *>(phash_lookup(handle->hash_edges, key));
896 *r_pair = nullptr;
897
898 while (pe) {
899 if (pe != e) {
900 v1 = pe->vert;
901 v2 = pe->next->vert;
902
903 if (((v1->u.key == key1) && (v2->u.key == key2)) ||
904 ((v1->u.key == key2) && (v2->u.key == key1)))
905 {
906
907 /* don't connect seams and t-junctions */
908 if ((pe->flag & PEDGE_SEAM) || *r_pair ||
909 (topology_from_uvs && p_edge_implicit_seam(e, pe)))
910 {
911 *r_pair = nullptr;
912 return false;
913 }
914
915 *r_pair = pe;
916 }
917 }
918
919 pe = reinterpret_cast<PEdge *>(
920 phash_next(handle->hash_edges, key, reinterpret_cast<PHashLink *>(pe)));
921 }
922
923 if (*r_pair && (e->vert == (*r_pair)->vert)) {
924 if ((*r_pair)->next->pair || (*r_pair)->next->next->pair) {
925 /* non unfoldable, maybe mobius ring or klein bottle */
926 *r_pair = nullptr;
927 return false;
928 }
929 }
930
931 return (*r_pair != nullptr);
932}
933
935 PEdge *e,
936 bool topology_from_uvs,
937 PEdge ***stack)
938{
939 PEdge *pair = nullptr;
940
941 if (!e->pair && p_edge_has_pair(handle, e, topology_from_uvs, &pair)) {
942 if (e->vert == pair->vert) {
943 p_face_flip(pair->face);
944 }
945
946 e->pair = pair;
947 pair->pair = e;
948
949 if (!(pair->face->flag & PFACE_CONNECTED)) {
950 **stack = pair;
951 (*stack)++;
952 }
953 }
954
955 return (e->pair != nullptr);
956}
957
958static int p_connect_pairs(ParamHandle *handle, bool topology_from_uvs)
959{
961 "Pstackbase");
962 PEdge **stack = stackbase;
963 PFace *f, *first;
964 PEdge *e, *e1, *e2;
965 PChart *chart = handle->construction_chart;
966 int ncharts = 0;
967
968 /* Connect pairs, count edges, set vertex-edge pointer to a pair-less edge. */
969 for (first = chart->faces; first; first = first->nextlink) {
970 if (first->flag & PFACE_CONNECTED) {
971 continue;
972 }
973
974 *stack = first->edge;
975 stack++;
976
977 while (stack != stackbase) {
978 stack--;
979 e = *stack;
980 e1 = e->next;
981 e2 = e1->next;
982
983 f = e->face;
984 f->flag |= PFACE_CONNECTED;
985
986 /* assign verts to charts so we can sort them later */
987 f->u.chart = ncharts;
988
989 if (!p_edge_connect_pair(handle, e, topology_from_uvs, &stack)) {
990 e->vert->edge = e;
991 }
992 if (!p_edge_connect_pair(handle, e1, topology_from_uvs, &stack)) {
993 e1->vert->edge = e1;
994 }
995 if (!p_edge_connect_pair(handle, e2, topology_from_uvs, &stack)) {
996 e2->vert->edge = e2;
997 }
998 }
999
1000 ncharts++;
1001 }
1002
1003 MEM_delete(stackbase);
1004
1005 return ncharts;
1006}
1007
1008static void p_split_vert(ParamHandle *handle, PChart *chart, PEdge *e)
1009{
1010 PEdge *we, *lastwe = nullptr;
1011 PVert *v = e->vert;
1012 bool copy = true;
1013
1014 if (e->flag & PEDGE_PIN) {
1015 chart->has_pins = true;
1016 }
1017
1018 if (e->flag & PEDGE_VERTEX_SPLIT) {
1019 return;
1020 }
1021
1022 /* rewind to start */
1023 lastwe = e;
1024 for (we = p_wheel_edge_prev(e); we && (we != e); we = p_wheel_edge_prev(we)) {
1025 lastwe = we;
1026 }
1027
1028 /* go over all edges in wheel */
1029 for (we = lastwe; we; we = p_wheel_edge_next(we)) {
1030 if (we->flag & PEDGE_VERTEX_SPLIT) {
1031 break;
1032 }
1033
1034 we->flag |= PEDGE_VERTEX_SPLIT;
1035
1036 if (we == v->edge) {
1037 /* found it, no need to copy */
1038 copy = false;
1039 v->nextlink = chart->verts;
1040 chart->verts = v;
1041 chart->nverts++;
1042 }
1043 }
1044
1045 if (copy) {
1046 /* not found, copying */
1047 v->flag |= PVERT_SPLIT;
1048 v = p_vert_copy(handle, v);
1049 v->flag |= PVERT_SPLIT;
1050
1051 v->nextlink = chart->verts;
1052 chart->verts = v;
1053 chart->nverts++;
1054
1055 v->edge = lastwe;
1056
1057 we = lastwe;
1058 do {
1059 we->vert = v;
1060 we = p_wheel_edge_next(we);
1061 } while (we && (we != lastwe));
1062 }
1063}
1064
1065static PChart **p_split_charts(ParamHandle *handle, PChart *chart, int ncharts)
1066{
1067 PChart **charts = MEM_new_array_zeroed<PChart *>(ncharts, "PCharts");
1068
1069 for (int i = 0; i < ncharts; i++) {
1070 charts[i] = MEM_new_zeroed<PChart>("PChart");
1071 }
1072
1073 PFace *f = chart->faces;
1074 while (f) {
1075 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
1076 PFace *nextf = f->nextlink;
1077
1078 PChart *nchart = charts[f->u.chart];
1079
1080 f->nextlink = nchart->faces;
1081 nchart->faces = f;
1082 e1->nextlink = nchart->edges;
1083 nchart->edges = e1;
1084 e2->nextlink = nchart->edges;
1085 nchart->edges = e2;
1086 e3->nextlink = nchart->edges;
1087 nchart->edges = e3;
1088
1089 nchart->nfaces++;
1090 nchart->nedges += 3;
1091
1092 p_split_vert(handle, nchart, e1);
1093 p_split_vert(handle, nchart, e2);
1094 p_split_vert(handle, nchart, e3);
1095
1096 f = nextf;
1097 }
1098
1099 return charts;
1100}
1101
1103{
1104 PFace *f;
1105
1106 /* allocate */
1107 f = static_cast<PFace *>(BLI_memarena_alloc(handle->arena, sizeof(*f)));
1108 f->flag = 0;
1109
1110 PEdge *e1 = static_cast<PEdge *>(BLI_memarena_calloc(handle->arena, sizeof(*e1)));
1111 PEdge *e2 = static_cast<PEdge *>(BLI_memarena_calloc(handle->arena, sizeof(*e2)));
1112 PEdge *e3 = static_cast<PEdge *>(BLI_memarena_calloc(handle->arena, sizeof(*e3)));
1113
1114 /* set up edges */
1115 f->edge = e1;
1116 e1->face = e2->face = e3->face = f;
1117
1118 e1->next = e2;
1119 e2->next = e3;
1120 e3->next = e1;
1121
1122 return f;
1123}
1124
1126 ParamKey key,
1127 const ParamKey *vkeys,
1128 const float **co,
1129 float **uv,
1130 const float *weight,
1131 int i1,
1132 int i2,
1133 int i3,
1134 const bool *pin,
1135 const bool *select)
1136{
1137 PFace *f = p_face_add(handle);
1138 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
1139
1140 float weight1, weight2, weight3;
1141 if (weight) {
1142 weight1 = weight[i1];
1143 weight2 = weight[i2];
1144 weight3 = weight[i3];
1145 }
1146 else {
1147 weight1 = 1.0f;
1148 weight2 = 1.0f;
1149 weight3 = 1.0f;
1150 }
1151
1152 e1->vert = p_vert_lookup(handle, vkeys[i1], co[i1], weight1, e1);
1153 e2->vert = p_vert_lookup(handle, vkeys[i2], co[i2], weight2, e2);
1154 e3->vert = p_vert_lookup(handle, vkeys[i3], co[i3], weight3, e3);
1155
1156 e1->orig_uv = uv[i1];
1157 e2->orig_uv = uv[i2];
1158 e3->orig_uv = uv[i3];
1159
1160 if (pin) {
1161 if (pin[i1]) {
1162 e1->flag |= PEDGE_PIN;
1163 }
1164 if (pin[i2]) {
1165 e2->flag |= PEDGE_PIN;
1166 }
1167 if (pin[i3]) {
1168 e3->flag |= PEDGE_PIN;
1169 }
1170 }
1171
1172 if (select) {
1173 if (select[i1]) {
1174 e1->flag |= PEDGE_SELECT;
1175 }
1176 if (select[i2]) {
1177 e2->flag |= PEDGE_SELECT;
1178 }
1179 if (select[i3]) {
1180 e3->flag |= PEDGE_SELECT;
1181 }
1182 }
1183
1184 f->u.key = key;
1185 phash_insert(handle->hash_faces, reinterpret_cast<PHashLink *>(f));
1186
1187 e1->u.key = PHASH_edge(vkeys[i1], vkeys[i2]);
1188 e2->u.key = PHASH_edge(vkeys[i2], vkeys[i3]);
1189 e3->u.key = PHASH_edge(vkeys[i3], vkeys[i1]);
1190
1191 phash_insert(handle->hash_edges, reinterpret_cast<PHashLink *>(e1));
1192 phash_insert(handle->hash_edges, reinterpret_cast<PHashLink *>(e2));
1193 phash_insert(handle->hash_edges, reinterpret_cast<PHashLink *>(e3));
1194
1195 return f;
1196}
1197
1198static PFace *p_face_add_fill(ParamHandle *handle, PChart *chart, PVert *v1, PVert *v2, PVert *v3)
1199{
1200 PFace *f = p_face_add(handle);
1201 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
1202
1203 e1->vert = v1;
1204 e2->vert = v2;
1205 e3->vert = v3;
1206
1207 e1->orig_uv = e2->orig_uv = e3->orig_uv = nullptr;
1208
1209 f->nextlink = chart->faces;
1210 chart->faces = f;
1211 e1->nextlink = chart->edges;
1212 chart->edges = e1;
1213 e2->nextlink = chart->edges;
1214 chart->edges = e2;
1215 e3->nextlink = chart->edges;
1216 chart->edges = e3;
1217
1218 chart->nfaces++;
1219 chart->nedges += 3;
1220
1221 return f;
1222}
1223
1224/* Construction: boundary filling */
1225
1226static void p_chart_boundaries(PChart *chart, PEdge **r_outer)
1227{
1228 PEdge *e, *be;
1229 float len, maxlen = -1.0;
1230
1231 chart->nboundaries = 0;
1232 if (r_outer) {
1233 *r_outer = nullptr;
1234 }
1235
1236 for (e = chart->edges; e; e = e->nextlink) {
1237 if (e->pair || (e->flag & PEDGE_DONE)) {
1238 continue;
1239 }
1240
1241 chart->nboundaries++;
1242
1243 len = 0.0f;
1244
1245 be = e;
1246 do {
1247 be->flag |= PEDGE_DONE;
1248 len += p_edge_length(be);
1249 be = be->next->vert->edge;
1250 } while (be != e);
1251
1252 if (r_outer && (len > maxlen)) {
1253 *r_outer = e;
1254 maxlen = len;
1255 }
1256 }
1257
1258 for (e = chart->edges; e; e = e->nextlink) {
1259 e->flag &= ~PEDGE_DONE;
1260 }
1261}
1262
1264 const float **co,
1265 uint (**r_tris)[3],
1266 uint nverts)
1267{
1272 MemArena *arena = handle->polyfill_arena;
1273 Heap *heap = handle->polyfill_heap;
1274 uint nfilltri = nverts - 2;
1275 *r_tris = static_cast<uint(*)[3]>(
1276 BLI_memarena_alloc(arena, sizeof(**r_tris) * size_t(nfilltri)));
1277 float (*projverts)[2] = static_cast<float (*)[2]>(
1278 BLI_memarena_alloc(arena, sizeof(*projverts) * size_t(nverts)));
1279
1280 /* Calc normal, flipped: to get a positive 2d cross product. */
1281 float normal[3];
1282 zero_v3(normal);
1283 const float *co_curr, *co_prev = co[nverts - 1];
1284 for (int j = 0; j < nverts; j++) {
1285 co_curr = co[j];
1286 add_newell_cross_v3_v3v3(normal, co_prev, co_curr);
1287 co_prev = co_curr;
1288 }
1289 if (normalize_v3(normal) == 0.0f) [[unlikely]] {
1290 normal[2] = 1.0f;
1291 }
1292
1293 /* Project verts to 2d. */
1294 float axis_mat[3][3];
1295 axis_dominant_v3_to_m3_negate(axis_mat, normal);
1296 for (int j = 0; j < nverts; j++) {
1297 mul_v2_m3v3(projverts[j], axis_mat, co[j]);
1298 }
1299
1300 BLI_polyfill_calc_arena(projverts, nverts, 1, *r_tris, arena);
1301
1302 /* Beautify helps avoid thin triangles that give numerical problems. */
1303 BLI_polyfill_beautify(projverts, nverts, *r_tris, arena, heap);
1304}
1305
1307 PChart *chart,
1308 MutableSpan<PEdge *> border_edges,
1309 const float **co)
1310{
1311 uint(*tris)[3];
1312 int nedges = border_edges.size();
1313 uint nfilltri = nedges - 2;
1314 Array<bool> filled_indices(nfilltri, false);
1315
1316 p_polygon_calc_tris(handle, co, &tris, nedges);
1317
1318 while (nedges >= 3) {
1319
1320 for (uint tris_idx = 0; tris_idx < nfilltri; tris_idx++) {
1321 if (filled_indices[tris_idx] == true) {
1322 continue;
1323 }
1324
1325 uint i1 = tris[tris_idx][0];
1326 uint i2 = tris[tris_idx][1];
1327 uint i3 = tris[tris_idx][2];
1328
1329 for (int i = 0; i < 3; i++) {
1330 PEdge *inner_edge = border_edges[i2];
1331
1332 PEdge *prev_bound_edge = p_boundary_edge_prev(inner_edge);
1333 PEdge *next_bound_edge = p_boundary_edge_next(inner_edge);
1334
1335 if ((prev_bound_edge->vert->u.id != i1) || (next_bound_edge->vert->u.id != i3)) {
1336 SHIFT3(uint, i3, i1, i2);
1337 continue;
1338 }
1339
1340 inner_edge->flag |= PEDGE_FILLED;
1341 prev_bound_edge->flag |= PEDGE_FILLED;
1342
1344 handle, chart, inner_edge->vert, prev_bound_edge->vert, next_bound_edge->vert);
1345 f->flag |= PFACE_FILLED;
1346
1347 PEdge *new_inner_edge = f->edge->next->next;
1348 PEdge *new_next_edge = f->edge;
1349 PEdge *new_prev_edge = f->edge->next;
1350
1351 new_inner_edge->flag = new_next_edge->flag = new_prev_edge->flag = PEDGE_FILLED;
1352
1353 inner_edge->pair = new_inner_edge;
1354 new_inner_edge->pair = inner_edge;
1355 prev_bound_edge->pair = new_next_edge;
1356 new_next_edge->pair = prev_bound_edge;
1357
1358 new_inner_edge->vert = next_bound_edge->vert;
1359 new_next_edge->vert = inner_edge->vert;
1360 new_prev_edge->vert = prev_bound_edge->vert;
1361
1362 if (nedges == 3) {
1363 next_bound_edge->pair = new_prev_edge;
1364 new_prev_edge->pair = next_bound_edge;
1365 }
1366 else {
1367 filled_indices[tris_idx] = true;
1368 new_prev_edge->vert->edge = new_prev_edge;
1369
1370 border_edges[new_prev_edge->vert->u.id] = new_prev_edge;
1371 border_edges[next_bound_edge->vert->u.id] = next_bound_edge;
1372 }
1373
1374 nedges--;
1375 break;
1376 }
1377 }
1378 }
1380}
1381static void p_chart_fill_boundaries(ParamHandle *handle, PChart *chart, const PEdge *outer)
1382{
1383 PEdge *e; /* *enext - as yet unused */
1384
1385 for (e = chart->edges; e; e = e->nextlink) {
1386 /* enext = e->nextlink; - as yet unused */
1387
1388 if (e->pair || (e->flag & PEDGE_FILLED)) {
1389 continue;
1390 }
1391
1393 int nedges = 0;
1394 PEdge *be = e;
1395 do {
1396 border_edges.append(be);
1397
1398 be->flag |= PEDGE_FILLED;
1399 be = be->next->vert->edge;
1400 nedges++;
1401 } while (be != e);
1402
1403 if (e != outer) {
1404 if (nedges == 2) {
1405 /* no real boundary, but an isolated seam */
1406 be = e->next->vert->edge;
1407 e->pair = be;
1408 be->pair = e;
1409 continue;
1410 }
1411
1413 Array<PHashKey, P_NGON_STACK_NUM> stored_indexes(nedges);
1414 for (int i = 0; i < nedges; i++) {
1415 PVert *bv = border_edges[i]->vert;
1416 co[i] = bv->co;
1417 stored_indexes[i] = bv->u.key;
1418 bv->u.id = i;
1419 }
1420
1421 p_chart_fill_boundary(handle, chart, border_edges, co.data());
1422
1423 for (int i = 0; i < nedges; i++) {
1424 border_edges[i]->vert->u.key = stored_indexes[i];
1425 }
1426 }
1427 }
1428}
1429
1430#if 0
1431/* Polygon kernel for inserting uv's non overlapping */
1432
1433static int p_polygon_point_in(const float cp1[2], const float cp2[2], const float p[2])
1434{
1435 if ((cp1[0] == p[0]) && (cp1[1] == p[1])) {
1436 return 2;
1437 }
1438 else if ((cp2[0] == p[0]) && (cp2[1] == p[1])) {
1439 return 3;
1440 }
1441 else {
1442 return (p_area_signed(cp1, cp2, p) >= 0.0f);
1443 }
1444}
1445
1446static void p_polygon_kernel_clip(float (*oldpoints)[2],
1447 int noldpoints,
1448 float (*newpoints)[2],
1449 int *r_nnewpoints,
1450 const float cp1[2],
1451 const float cp2[2])
1452{
1453 float *p2, *p1, isect[2];
1454 int i, p2in, p1in;
1455
1456 p1 = oldpoints[noldpoints - 1];
1457 p1in = p_polygon_point_in(cp1, cp2, p1);
1458 *r_nnewpoints = 0;
1459
1460 for (i = 0; i < noldpoints; i++) {
1461 p2 = oldpoints[i];
1462 p2in = p_polygon_point_in(cp1, cp2, p2);
1463
1464 if ((p2in >= 2) || (p1in && p2in)) {
1465 newpoints[*r_nnewpoints][0] = p2[0];
1466 newpoints[*r_nnewpoints][1] = p2[1];
1467 (*r_nnewpoints)++;
1468 }
1469 else if (p1in && !p2in) {
1470 if (p1in != 3) {
1471 p_intersect_line_2d(p1, p2, cp1, cp2, isect);
1472 newpoints[*r_nnewpoints][0] = isect[0];
1473 newpoints[*r_nnewpoints][1] = isect[1];
1474 (*r_nnewpoints)++;
1475 }
1476 }
1477 else if (!p1in && p2in) {
1478 p_intersect_line_2d(p1, p2, cp1, cp2, isect);
1479 newpoints[*r_nnewpoints][0] = isect[0];
1480 newpoints[*r_nnewpoints][1] = isect[1];
1481 (*r_nnewpoints)++;
1482
1483 newpoints[*r_nnewpoints][0] = p2[0];
1484 newpoints[*r_nnewpoints][1] = p2[1];
1485 (*r_nnewpoints)++;
1486 }
1487
1488 p1in = p2in;
1489 p1 = p2;
1490 }
1491}
1492
1493static void p_polygon_kernel_center(float (*points)[2], int npoints, float *center)
1494{
1495 int i, size, nnewpoints = npoints;
1496 float(*oldpoints)[2], (*newpoints)[2], *p1, *p2;
1497
1498 size = npoints * 3;
1499 oldpoints = MEM_new_array_uninitialized<float[2]>(size_t(size), "PPolygonOldPoints");
1500 newpoints = MEM_new_array_uninitialized<float[2]>(size_t(size), "PPolygonNewPoints");
1501
1502 memcpy(oldpoints, points, sizeof(float[2]) * npoints);
1503
1504 for (i = 0; i < npoints; i++) {
1505 p1 = points[i];
1506 p2 = points[(i + 1) % npoints];
1507 p_polygon_kernel_clip(oldpoints, nnewpoints, newpoints, &nnewpoints, p1, p2);
1508
1509 if (nnewpoints == 0) {
1510 /* degenerate case, use center of original face */
1511 memcpy(oldpoints, points, sizeof(float[2]) * npoints);
1512 nnewpoints = npoints;
1513 break;
1514 }
1515 else if (nnewpoints == 1) {
1516 /* degenerate case, use remaining point */
1517 center[0] = newpoints[0][0];
1518 center[1] = newpoints[0][1];
1519
1520 MEM_delete(oldpoints);
1521 MEM_delete(newpoints);
1522
1523 return;
1524 }
1525
1526 if (nnewpoints * 2 > size) {
1527 size *= 2;
1528 MEM_delete(oldpoints);
1529 oldpoints = MEM_new_array_uninitialized<float[2]>(size, "oldpoints");
1530 memcpy(oldpoints, newpoints, sizeof(float[2]) * nnewpoints);
1531 MEM_delete(newpoints);
1532 newpoints = MEM_new_array_uninitialized<float[2]>(size, "newpoints");
1533 }
1534 else {
1535 float(*sw_points)[2] = oldpoints;
1536 oldpoints = newpoints;
1537 newpoints = sw_points;
1538 }
1539 }
1540
1541 center[0] = center[1] = 0.0f;
1542
1543 for (i = 0; i < nnewpoints; i++) {
1544 center[0] += oldpoints[i][0];
1545 center[1] += oldpoints[i][1];
1546 }
1547
1548 center[0] /= nnewpoints;
1549 center[1] /= nnewpoints;
1550
1551 MEM_delete(oldpoints);
1552 MEM_delete(newpoints);
1553}
1554#endif
1555
1556/* Simplify/Complexity
1557 *
1558 * This is currently used for eliminating degenerate vertex coordinates.
1559 * In the future this can be used for efficient unwrapping of high resolution
1560 * charts at lower resolution. */
1561
1562#if 0
1563
1564static float p_vert_cotan(const float v1[3], const float v2[3], const float v3[3])
1565{
1566 float a[3], b[3], c[3], clen;
1567
1568 sub_v3_v3v3(a, v2, v1);
1569 sub_v3_v3v3(b, v3, v1);
1570 cross_v3_v3v3(c, a, b);
1571
1572 clen = len_v3(c);
1573
1574 if (clen == 0.0f) {
1575 return 0.0f;
1576 }
1577
1578 return dot_v3v3(a, b) / clen;
1579}
1580
1581static bool p_vert_flipped_wheel_triangle(PVert *v)
1582{
1583 PEdge *e = v->edge;
1584
1585 do {
1586 if (p_face_uv_area_signed(e->face) < 0.0f) {
1587 return true;
1588 }
1589
1591 } while (e && (e != v->edge));
1592
1593 return false;
1594}
1595
1596static bool p_vert_map_harmonic_weights(PVert *v)
1597{
1598 float weightsum, positionsum[2], olduv[2];
1599
1600 weightsum = 0.0f;
1601 positionsum[0] = positionsum[1] = 0.0f;
1602
1603 if (p_vert_interior(v)) {
1604 PEdge *e = v->edge;
1605
1606 do {
1607 float t1, t2, weight;
1608 PVert *v1, *v2;
1609
1610 v1 = e->next->vert;
1611 v2 = e->next->next->vert;
1612 t1 = p_vert_cotan(v2->co, e->vert->co, v1->co);
1613
1614 v1 = e->pair->next->vert;
1615 v2 = e->pair->next->next->vert;
1616 t2 = p_vert_cotan(v2->co, e->pair->vert->co, v1->co);
1617
1618 weight = 0.5f * (t1 + t2);
1619 weightsum += weight;
1620 positionsum[0] += weight * e->pair->vert->uv[0];
1621 positionsum[1] += weight * e->pair->vert->uv[1];
1622
1624 } while (e && (e != v->edge));
1625 }
1626 else {
1627 PEdge *e = v->edge;
1628
1629 do {
1630 float t1, t2;
1631 PVert *v1, *v2;
1632
1633 v2 = e->next->vert;
1634 v1 = e->next->next->vert;
1635
1636 t1 = p_vert_cotan(v1->co, v->co, v2->co);
1637 t2 = p_vert_cotan(v2->co, v->co, v1->co);
1638
1639 weightsum += t1 + t2;
1640 positionsum[0] += (v2->uv[1] - v1->uv[1]) + (t1 * v2->uv[0] + t2 * v1->uv[0]);
1641 positionsum[1] += (v1->uv[0] - v2->uv[0]) + (t1 * v2->uv[1] + t2 * v1->uv[1]);
1642
1644 } while (e && (e != v->edge));
1645 }
1646
1647 if (weightsum != 0.0f) {
1648 weightsum = 1.0f / weightsum;
1649 positionsum[0] *= weightsum;
1650 positionsum[1] *= weightsum;
1651 }
1652
1653 olduv[0] = v->uv[0];
1654 olduv[1] = v->uv[1];
1655 v->uv[0] = positionsum[0];
1656 v->uv[1] = positionsum[1];
1657
1658 if (p_vert_flipped_wheel_triangle(v)) {
1659 v->uv[0] = olduv[0];
1660 v->uv[1] = olduv[1];
1661
1662 return false;
1663 }
1664
1665 return true;
1666}
1667
1668static void p_vert_harmonic_insert(PVert *v)
1669{
1670 PEdge *e;
1671
1672 if (!p_vert_map_harmonic_weights(v)) {
1673 /* do face kernel center insertion: this is quite slow, but should
1674 * only be needed for 0.01 % of verts or so, when insert with harmonic
1675 * weights fails */
1676
1677 int npoints = 0, i;
1678 float(*points)[2];
1679
1680 e = v->edge;
1681 do {
1682 npoints++;
1684 } while (e && (e != v->edge));
1685
1686 if (e == nullptr) {
1687 npoints++;
1688 }
1689
1690 points = MEM_new_array_uninitialized<float[2]>(size_t(npoints), "PHarmonicPoints");
1691
1692 e = v->edge;
1693 i = 0;
1694 do {
1695 PEdge *nexte = p_wheel_edge_next(e);
1696
1697 points[i][0] = e->next->vert->uv[0];
1698 points[i][1] = e->next->vert->uv[1];
1699
1700 if (nexte == nullptr) {
1701 i++;
1702 points[i][0] = e->next->next->vert->uv[0];
1703 points[i][1] = e->next->next->vert->uv[1];
1704 break;
1705 }
1706
1707 e = nexte;
1708 i++;
1709 } while (e != v->edge);
1710
1711 p_polygon_kernel_center(points, npoints, v->uv);
1712
1713 MEM_delete(points);
1714 }
1715
1716 e = v->edge;
1717 do {
1718 if (!(e->next->vert->flag & PVERT_PIN)) {
1719 p_vert_map_harmonic_weights(e->next->vert);
1720 }
1722 } while (e && (e != v->edge));
1723
1724 p_vert_map_harmonic_weights(v);
1725}
1726#endif
1727
1729{
1730 PEdge *start = v->edge;
1731
1732 /* set v->edge pointer to the edge with no pair, if there is one */
1733 while (v->edge->pair) {
1734 v->edge = p_wheel_edge_prev(v->edge);
1735
1736 if (v->edge == start) {
1737 break;
1738 }
1739 }
1740}
1741
1742static void p_collapsing_verts(PEdge *edge, PEdge *pair, PVert **r_newv, PVert **r_keepv)
1743{
1744 /* the two vertices that are involved in the collapse */
1745 if (edge) {
1746 *r_newv = edge->vert;
1747 *r_keepv = edge->next->vert;
1748 }
1749 else {
1750 *r_newv = pair->next->vert;
1751 *r_keepv = pair->vert;
1752 }
1753}
1754
1755static void p_collapse_edge(PEdge *edge, PEdge *pair)
1756{
1757 PVert *oldv, *keepv;
1758 PEdge *e;
1759
1760 p_collapsing_verts(edge, pair, &oldv, &keepv);
1761
1762 /* change e->vert pointers from old vertex to the target vertex */
1763 e = oldv->edge;
1764 do {
1765 if ((e != edge) && !(pair && pair->next == e)) {
1766 e->vert = keepv;
1767 }
1768
1770 } while (e && (e != oldv->edge));
1771
1772 /* set keepv->edge pointer */
1773 if ((edge && (keepv->edge == edge->next)) || (keepv->edge == pair)) {
1774 if (edge && edge->next->pair) {
1775 keepv->edge = edge->next->pair->next;
1776 }
1777 else if (pair && pair->next->next->pair) {
1778 keepv->edge = pair->next->next->pair;
1779 }
1780 else if (edge && edge->next->next->pair) {
1781 keepv->edge = edge->next->next->pair;
1782 }
1783 else {
1784 keepv->edge = pair->next->pair->next;
1785 }
1786 }
1787
1788 /* update pairs and v->edge pointers */
1789 if (edge) {
1790 PEdge *e1 = edge->next, *e2 = e1->next;
1791
1792 if (e1->pair) {
1793 e1->pair->pair = e2->pair;
1794 }
1795
1796 if (e2->pair) {
1797 e2->pair->pair = e1->pair;
1798 e2->vert->edge = p_wheel_edge_prev(e2);
1799 }
1800 else {
1801 e2->vert->edge = p_wheel_edge_next(e2);
1802 }
1803
1804 p_vert_fix_edge_pointer(e2->vert);
1805 }
1806
1807 if (pair) {
1808 PEdge *e1 = pair->next, *e2 = e1->next;
1809
1810 if (e1->pair) {
1811 e1->pair->pair = e2->pair;
1812 }
1813
1814 if (e2->pair) {
1815 e2->pair->pair = e1->pair;
1816 e2->vert->edge = p_wheel_edge_prev(e2);
1817 }
1818 else {
1819 e2->vert->edge = p_wheel_edge_next(e2);
1820 }
1821
1822 p_vert_fix_edge_pointer(e2->vert);
1823 }
1824
1826
1827 /* mark for move to collapsed list later */
1828 oldv->flag |= PVERT_COLLAPSE;
1829
1830 if (edge) {
1831 PFace *f = edge->face;
1832 PEdge *e1 = edge->next, *e2 = e1->next;
1833
1834 f->flag |= PFACE_COLLAPSE;
1835 edge->flag |= PEDGE_COLLAPSE;
1836 e1->flag |= PEDGE_COLLAPSE;
1837 e2->flag |= PEDGE_COLLAPSE;
1838 }
1839
1840 if (pair) {
1841 PFace *f = pair->face;
1842 PEdge *e1 = pair->next, *e2 = e1->next;
1843
1844 f->flag |= PFACE_COLLAPSE;
1845 pair->flag |= PEDGE_COLLAPSE;
1846 e1->flag |= PEDGE_COLLAPSE;
1847 e2->flag |= PEDGE_COLLAPSE;
1848 }
1849}
1850
1851#if 0
1852static void p_split_vertex(PEdge *edge, PEdge *pair)
1853{
1854 PVert *newv, *keepv;
1855 PEdge *e;
1856
1857 p_collapsing_verts(edge, pair, &newv, &keepv);
1858
1859 /* update edge pairs */
1860 if (edge) {
1861 PEdge *e1 = edge->next, *e2 = e1->next;
1862
1863 if (e1->pair) {
1864 e1->pair->pair = e1;
1865 }
1866 if (e2->pair) {
1867 e2->pair->pair = e2;
1868 }
1869
1870 e2->vert->edge = e2;
1871 p_vert_fix_edge_pointer(e2->vert);
1872 keepv->edge = e1;
1873 }
1874
1875 if (pair) {
1876 PEdge *e1 = pair->next, *e2 = e1->next;
1877
1878 if (e1->pair) {
1879 e1->pair->pair = e1;
1880 }
1881 if (e2->pair) {
1882 e2->pair->pair = e2;
1883 }
1884
1885 e2->vert->edge = e2;
1886 p_vert_fix_edge_pointer(e2->vert);
1887 keepv->edge = pair;
1888 }
1889
1891
1892 /* set e->vert pointers to restored vertex */
1893 e = newv->edge;
1894 do {
1895 e->vert = newv;
1897 } while (e && (e != newv->edge));
1898}
1899#endif
1900
1902{
1903 PVert *oldv, *keepv;
1904
1905 p_collapsing_verts(edge, pair, &oldv, &keepv);
1906
1907 /* boundary edges */
1908 if (!edge || !pair) {
1909 /* avoid collapsing chart into an edge */
1910 if (edge && !edge->next->pair && !edge->next->next->pair) {
1911 return false;
1912 }
1913 if (pair && !pair->next->pair && !pair->next->next->pair) {
1914 return false;
1915 }
1916 }
1917 /* avoid merging two boundaries (oldv and keepv are on the 'other side' of
1918 * the chart) */
1919 else if (!p_vert_interior(oldv) && !p_vert_interior(keepv)) {
1920 return false;
1921 }
1922
1923 return true;
1924}
1925
1926#if 0
1927static bool p_collapse_normal_flipped(float *v1, float *v2, float *vold, float *vnew)
1928{
1929 float nold[3], nnew[3], sub1[3], sub2[3];
1930
1931 sub_v3_v3v3(sub1, vold, v1);
1932 sub_v3_v3v3(sub2, vold, v2);
1933 cross_v3_v3v3(nold, sub1, sub2);
1934
1935 sub_v3_v3v3(sub1, vnew, v1);
1936 sub_v3_v3v3(sub2, vnew, v2);
1937 cross_v3_v3v3(nnew, sub1, sub2);
1938
1939 return (dot_v3v3(nold, nnew) <= 0.0f);
1940}
1941
1942static bool p_collapse_allowed_geometric(PEdge *edge, PEdge *pair)
1943{
1944 PVert *oldv, *keepv;
1945 PEdge *e;
1946 float angulardefect, angle;
1947
1948 p_collapsing_verts(edge, pair, &oldv, &keepv);
1949
1950 angulardefect = 2 * M_PI;
1951
1952 e = oldv->edge;
1953 do {
1954 float a[3], b[3], minangle, maxangle;
1955 PEdge *e1 = e->next, *e2 = e1->next;
1956 PVert *v1 = e1->vert, *v2 = e2->vert;
1957 int i;
1958
1959 angle = p_vec_angle(v1->co, oldv->co, v2->co);
1960 angulardefect -= angle;
1961
1962 /* skip collapsing faces */
1963 if (v1 == keepv || v2 == keepv) {
1965 continue;
1966 }
1967
1968 if (p_collapse_normal_flipped(v1->co, v2->co, oldv->co, keepv->co)) {
1969 return false;
1970 }
1971
1972 a[0] = angle;
1973 a[1] = p_vec_angle(v2->co, v1->co, oldv->co);
1974 a[2] = M_PI - a[0] - a[1];
1975
1976 b[0] = p_vec_angle(v1->co, keepv->co, v2->co);
1977 b[1] = p_vec_angle(v2->co, v1->co, keepv->co);
1978 b[2] = M_PI - b[0] - b[1];
1979
1980 /* ABF criterion 1: avoid sharp and obtuse angles. */
1981 minangle = DEG2RADF(15.0);
1982 maxangle = M_PI - minangle;
1983
1984 for (i = 0; i < 3; i++) {
1985 if ((b[i] < a[i]) && (b[i] < minangle)) {
1986 return false;
1987 }
1988 else if ((b[i] > a[i]) && (b[i] > maxangle)) {
1989 return false;
1990 }
1991 }
1992
1994 } while (e && (e != oldv->edge));
1995
1996 if (p_vert_interior(oldv)) {
1997 /* HLSCM criterion: angular defect smaller than threshold. */
1998 if (fabsf(angulardefect) > DEG2RADF(30.0)) {
1999 return false;
2000 }
2001 }
2002 else {
2003 PVert *v1 = p_boundary_edge_next(oldv->edge)->vert;
2004 PVert *v2 = p_boundary_edge_prev(oldv->edge)->vert;
2005
2006 /* ABF++ criterion 2: avoid collapsing verts inwards. */
2007 if (p_vert_interior(keepv)) {
2008 return false;
2009 }
2010
2011 /* Don't collapse significant boundary changes. */
2012 angle = p_vec_angle(v1->co, oldv->co, v2->co);
2013 if (angle < DEG2RADF(160.0)) {
2014 return false;
2015 }
2016 }
2017
2018 return true;
2019}
2020
2021static bool p_collapse_allowed(PEdge *edge, PEdge *pair)
2022{
2023 PVert *oldv, *keepv;
2024
2025 p_collapsing_verts(edge, pair, &oldv, &keepv);
2026
2027 if (oldv->flag & PVERT_PIN) {
2028 return false;
2029 }
2030
2031 return (p_collapse_allowed_topologic(edge, pair) && p_collapse_allowed_geometric(edge, pair));
2032}
2033
2034static float p_collapse_cost(PEdge *edge, PEdge *pair)
2035{
2036 /* based on volume and boundary optimization from:
2037 * "Fast and Memory Efficient Polygonal Simplification" P. Lindstrom, G. Turk */
2038
2039 PVert *oldv, *keepv;
2040 PEdge *e;
2041 PFace *oldf1, *oldf2;
2042 float volumecost = 0.0f, areacost = 0.0f, edgevec[3], cost, weight, elen;
2043 float shapecost = 0.0f;
2044 float shapeold = 0.0f, shapenew = 0.0f;
2045 int nshapeold = 0, nshapenew = 0;
2046
2047 p_collapsing_verts(edge, pair, &oldv, &keepv);
2048 oldf1 = (edge) ? edge->face : nullptr;
2049 oldf2 = (pair) ? pair->face : nullptr;
2050
2051 sub_v3_v3v3(edgevec, keepv->co, oldv->co);
2052
2053 e = oldv->edge;
2054 do {
2055 float a1, a2, a3;
2056 float *co1 = e->next->vert->co;
2057 float *co2 = e->next->next->vert->co;
2058
2059 if (!ELEM(e->face, oldf1, oldf2)) {
2060 float tetrav2[3], tetrav3[3];
2061
2062 /* tetrahedron volume = (1/3!)*|a.(b x c)| */
2063 sub_v3_v3v3(tetrav2, co1, oldv->co);
2064 sub_v3_v3v3(tetrav3, co2, oldv->co);
2065 volumecost += fabsf(volume_tri_tetrahedron_signed_v3(tetrav2, tetrav3, edgevec));
2066
2067# if 0
2068 shapecost += dot_v3v3(co1, keepv->co);
2069
2070 if (p_wheel_edge_next(e) == nullptr) {
2071 shapecost += dot_v3v3(co2, keepv->co);
2072 }
2073# endif
2074
2075 p_triangle_angles(oldv->co, co1, co2, &a1, &a2, &a3);
2076 a1 = a1 - M_PI / 3.0;
2077 a2 = a2 - M_PI / 3.0;
2078 a3 = a3 - M_PI / 3.0;
2079 shapeold = (a1 * a1 + a2 * a2 + a3 * a3) / (M_PI_2 * M_PI_2);
2080
2081 nshapeold++;
2082 }
2083 else {
2084 p_triangle_angles(keepv->co, co1, co2, &a1, &a2, &a3);
2085 a1 = a1 - M_PI / 3.0;
2086 a2 = a2 - M_PI / 3.0;
2087 a3 = a3 - M_PI / 3.0;
2088 shapenew = (a1 * a1 + a2 * a2 + a3 * a3) / (M_PI_2 * M_PI_2);
2089
2090 nshapenew++;
2091 }
2092
2094 } while (e && (e != oldv->edge));
2095
2096 if (!p_vert_interior(oldv)) {
2097 PVert *v1 = p_boundary_edge_prev(oldv->edge)->vert;
2098 PVert *v2 = p_boundary_edge_next(oldv->edge)->vert;
2099
2100 areacost = area_tri_v3(oldv->co, v1->co, v2->co);
2101 }
2102
2103 elen = len_v3(edgevec);
2104 weight = 1.0f; /* 0.2f */
2105 cost = weight * volumecost * volumecost + elen * elen * areacost * areacost;
2106# if 0
2107 cost += shapecost;
2108# else
2109 shapeold /= nshapeold;
2110 shapenew /= nshapenew;
2111 shapecost = (shapeold + 0.00001) / (shapenew + 0.00001);
2112
2113 cost *= shapecost;
2114# endif
2115
2116 return cost;
2117}
2118#endif
2119
2121 PVert *vert,
2122 float *r_mincost,
2123 PEdge **r_mine,
2124 const std::function<float(PEdge *, PEdge *)> &collapse_cost_fn,
2125 const std::function<float(PEdge *, PEdge *)> &collapse_allowed_fn)
2126{
2127 PEdge *e, *enext, *pair;
2128
2129 *r_mine = nullptr;
2130 *r_mincost = 0.0f;
2131 e = vert->edge;
2132 do {
2133 if (collapse_allowed_fn(e, e->pair)) {
2134 float cost = collapse_cost_fn(e, e->pair);
2135
2136 if ((*r_mine == nullptr) || (cost < *r_mincost)) {
2137 *r_mincost = cost;
2138 *r_mine = e;
2139 }
2140 }
2141
2142 enext = p_wheel_edge_next(e);
2143
2144 if (enext == nullptr) {
2145 /* The other boundary edge, where we only have the pair half-edge. */
2146 pair = e->next->next;
2147
2148 if (collapse_allowed_fn(nullptr, pair)) {
2149 float cost = collapse_cost_fn(nullptr, pair);
2150
2151 if ((*r_mine == nullptr) || (cost < *r_mincost)) {
2152 *r_mincost = cost;
2153 *r_mine = pair;
2154 }
2155 }
2156
2157 break;
2158 }
2159
2160 e = enext;
2161 } while (e != vert->edge);
2162}
2163
2164static void p_chart_post_collapse_flush(PChart *chart, PEdge *collapsed)
2165{
2166 /* Move to `collapsed_*`. */
2167
2168 PVert *v, *nextv = nullptr, *verts = chart->verts;
2169 PEdge *e, *nexte = nullptr, *edges = chart->edges, *laste = nullptr;
2170 PFace *f, *nextf = nullptr, *faces = chart->faces;
2171
2172 chart->verts = chart->collapsed_verts = nullptr;
2173 chart->edges = chart->collapsed_edges = nullptr;
2174 chart->faces = chart->collapsed_faces = nullptr;
2175
2176 chart->nverts = chart->nedges = chart->nfaces = 0;
2177
2178 for (v = verts; v; v = nextv) {
2179 nextv = v->nextlink;
2180
2181 if (v->flag & PVERT_COLLAPSE) {
2182 v->nextlink = chart->collapsed_verts;
2183 chart->collapsed_verts = v;
2184 }
2185 else {
2186 v->nextlink = chart->verts;
2187 chart->verts = v;
2188 chart->nverts++;
2189 }
2190 }
2191
2192 for (e = edges; e; e = nexte) {
2193 nexte = e->nextlink;
2194
2195 if (!collapsed || !(e->flag & PEDGE_COLLAPSE_EDGE)) {
2196 if (e->flag & PEDGE_COLLAPSE) {
2197 e->nextlink = chart->collapsed_edges;
2198 chart->collapsed_edges = e;
2199 }
2200 else {
2201 e->nextlink = chart->edges;
2202 chart->edges = e;
2203 chart->nedges++;
2204 }
2205 }
2206 }
2207
2208 /* these are added last so they can be popped of in the right order
2209 * for splitting */
2210 for (e = collapsed; e; e = e->nextlink) {
2211 e->nextlink = e->u.nextcollapse;
2212 laste = e;
2213 }
2214 if (laste) {
2215 laste->nextlink = chart->collapsed_edges;
2216 chart->collapsed_edges = collapsed;
2217 }
2218
2219 for (f = faces; f; f = nextf) {
2220 nextf = f->nextlink;
2221
2222 if (f->flag & PFACE_COLLAPSE) {
2223 f->nextlink = chart->collapsed_faces;
2224 chart->collapsed_faces = f;
2225 }
2226 else {
2227 f->nextlink = chart->faces;
2228 chart->faces = f;
2229 chart->nfaces++;
2230 }
2231 }
2232}
2233
2235 std::function<float(PEdge *, PEdge *)> collapse_cost_fn,
2236 std::function<float(PEdge *, PEdge *)> collapse_allowed_fn)
2237{
2238 /* For debugging. */
2239 static const int MAX_SIMPLIFY = INT_MAX;
2240
2241 /* Computes a list of edge collapses / vertex splits. The collapsed
2242 * simplices go in the `chart->collapsed_*` lists, The original and
2243 * collapsed may then be view as stacks, where the next collapse/split
2244 * is at the top of the respective lists. */
2245
2246 Heap *heap = BLI_heap_new();
2247 PEdge *collapsededges = nullptr;
2248 int ncollapsed = 0;
2249 Vector<PVert *> wheelverts;
2250 wheelverts.reserve(16);
2251
2252 /* insert all potential collapses into heap */
2253 for (PVert *v = chart->verts; v; v = v->nextlink) {
2254 float cost;
2255 PEdge *e = nullptr;
2256
2257 p_collapse_cost_vertex(v, &cost, &e, collapse_cost_fn, collapse_allowed_fn);
2258
2259 if (e) {
2260 v->u.heaplink = BLI_heap_insert(heap, cost, e);
2261 }
2262 else {
2263 v->u.heaplink = nullptr;
2264 }
2265 }
2266
2267 for (PEdge *e = chart->edges; e; e = e->nextlink) {
2268 e->u.nextcollapse = nullptr;
2269 }
2270
2271 /* pop edge collapse out of heap one by one */
2272 while (!BLI_heap_is_empty(heap)) {
2273 if (ncollapsed == MAX_SIMPLIFY) {
2274 break;
2275 }
2276
2277 HeapNode *link = BLI_heap_top(heap);
2278 PEdge *edge = static_cast<PEdge *>(BLI_heap_pop_min(heap)), *pair = edge->pair;
2279 PVert *oldv, *keepv;
2280 PEdge *wheele, *nexte;
2281
2282 /* remember the edges we collapsed */
2283 edge->u.nextcollapse = collapsededges;
2284 collapsededges = edge;
2285
2286 if (edge->vert->u.heaplink != link) {
2288 edge->next->vert->u.heaplink = nullptr;
2289 std::swap(edge, pair);
2290 }
2291 else {
2292 edge->flag |= PEDGE_COLLAPSE_EDGE;
2293 edge->vert->u.heaplink = nullptr;
2294 }
2295
2296 p_collapsing_verts(edge, pair, &oldv, &keepv);
2297
2298 /* gather all wheel verts and remember them before collapse */
2299 wheelverts.clear();
2300 wheele = oldv->edge;
2301
2302 do {
2303 wheelverts.append(wheele->next->vert);
2304 nexte = p_wheel_edge_next(wheele);
2305
2306 if (nexte == nullptr) {
2307 wheelverts.append(wheele->next->next->vert);
2308 }
2309
2310 wheele = nexte;
2311 } while (wheele && (wheele != oldv->edge));
2312
2313 /* collapse */
2314 p_collapse_edge(edge, pair);
2315
2316 for (PVert *v : wheelverts) {
2317 float cost;
2318 PEdge *collapse = nullptr;
2319
2320 if (v->u.heaplink) {
2321 BLI_heap_remove(heap, v->u.heaplink);
2322 v->u.heaplink = nullptr;
2323 }
2324
2325 p_collapse_cost_vertex(v, &cost, &collapse, collapse_cost_fn, collapse_allowed_fn);
2326
2327 if (collapse) {
2328 v->u.heaplink = BLI_heap_insert(heap, cost, collapse);
2329 }
2330 }
2331
2332 ncollapsed++;
2333 }
2334
2335 BLI_heap_free(heap, nullptr);
2336
2337 p_chart_post_collapse_flush(chart, collapsededges);
2338}
2339
2340#if 0
2341static void p_chart_post_split_flush(PChart *chart)
2342{
2343 /* Move from `collapsed_*`. */
2344
2345 PVert *v, *nextv = nullptr;
2346 PEdge *e, *nexte = nullptr;
2347 PFace *f, *nextf = nullptr;
2348
2349 for (v = chart->collapsed_verts; v; v = nextv) {
2350 nextv = v->nextlink;
2351 v->nextlink = chart->verts;
2352 chart->verts = v;
2353 chart->nverts++;
2354 }
2355
2356 for (e = chart->collapsed_edges; e; e = nexte) {
2357 nexte = e->nextlink;
2358 e->nextlink = chart->edges;
2359 chart->edges = e;
2360 chart->nedges++;
2361 }
2362
2363 for (f = chart->collapsed_faces; f; f = nextf) {
2364 nextf = f->nextlink;
2365 f->nextlink = chart->faces;
2366 chart->faces = f;
2367 chart->nfaces++;
2368 }
2369
2370 chart->collapsed_verts = nullptr;
2371 chart->collapsed_edges = nullptr;
2372 chart->collapsed_faces = nullptr;
2373}
2374
2375static void p_chart_complexify(PChart *chart)
2376{
2377 /* For debugging. */
2378 static const int MAX_COMPLEXIFY = INT_MAX;
2379
2380 PEdge *e, *pair, *edge;
2381 PVert *newv, *keepv;
2382 int x = 0;
2383
2384 for (e = chart->collapsed_edges; e; e = e->nextlink) {
2385 if (!(e->flag & PEDGE_COLLAPSE_EDGE)) {
2386 break;
2387 }
2388
2389 edge = e;
2390 pair = e->pair;
2391
2392 if (edge->flag & PEDGE_COLLAPSE_PAIR) {
2393 std::swap(edge, pair);
2394 }
2395
2396 p_split_vertex(edge, pair);
2397 p_collapsing_verts(edge, pair, &newv, &keepv);
2398
2399 if (x >= MAX_COMPLEXIFY) {
2400 newv->uv[0] = keepv->uv[0];
2401 newv->uv[1] = keepv->uv[1];
2402 }
2403 else {
2404 p_vert_harmonic_insert(newv);
2405 x++;
2406 }
2407 }
2408
2409 p_chart_post_split_flush(chart);
2410}
2411
2412static void p_chart_simplify(PChart *chart)
2413{
2414 /* Not implemented, needs proper reordering in split_flush. */
2415}
2416#endif
2417
2418/* ABF */
2419
2420#define ABF_MAX_ITER 20
2421
2439
2441{
2442 sys->alpha.reinitialize(sys->nangles);
2443 sys->beta.reinitialize(sys->nangles);
2444 sys->sine.reinitialize(sys->nangles);
2445 sys->cosine.reinitialize(sys->nangles);
2446 sys->weight.reinitialize(sys->nangles);
2447
2448 sys->bAlpha.reinitialize(sys->nangles);
2449 sys->bTriangle.reinitialize(sys->nfaces);
2450 sys->bInterior.reinitialize(2 * size_t(sys->ninterior));
2451
2453 sys->lambdaTriangle.as_mutable_span().fill(0.0f);
2455 sys->lambdaPlanar.as_mutable_span().fill(0.0f);
2457 sys->lambdaLength.as_mutable_span().fill(1.0f);
2458
2459 sys->J2dt.reinitialize(sys->nangles);
2460 sys->bstar.reinitialize(sys->nfaces);
2461 sys->dstar.reinitialize(sys->nfaces);
2462}
2463
2465{
2466 for (int i = 0; i < sys->nangles; i++) {
2467 const double angle = sys->alpha[i];
2468 sys->sine[i] = sin(angle);
2469 sys->cosine[i] = cos(angle);
2470 }
2471}
2472
2473static float p_abf_compute_sin_product(PAbfSystem *sys, PVert *v, int aid)
2474{
2475 PEdge *e, *e1, *e2;
2476 float sin1, sin2;
2477
2478 sin1 = sin2 = 1.0;
2479
2480 e = v->edge;
2481 do {
2482 e1 = e->next;
2483 e2 = e->next->next;
2484
2485 if (aid == e1->u.id) {
2486 /* we are computing a derivative for this angle,
2487 * so we use cos and drop the other part */
2488 sin1 *= sys->cosine[e1->u.id];
2489 sin2 = 0.0;
2490 }
2491 else {
2492 sin1 *= sys->sine[e1->u.id];
2493 }
2494
2495 if (aid == e2->u.id) {
2496 /* see above */
2497 sin1 = 0.0;
2498 sin2 *= sys->cosine[e2->u.id];
2499 }
2500 else {
2501 sin2 *= sys->sine[e2->u.id];
2502 }
2503
2504 e = e->next->next->pair;
2505 } while (e && (e != v->edge));
2506
2507 return (sin1 - sin2);
2508}
2509
2511{
2512 PVert *v = e->vert, *v1 = e->next->vert, *v2 = e->next->next->vert;
2513 float deriv;
2514
2515 deriv = (sys->alpha[e->u.id] - sys->beta[e->u.id]) * sys->weight[e->u.id];
2516 deriv += sys->lambdaTriangle[f->u.id];
2517
2518 if (v->flag & PVERT_INTERIOR) {
2519 deriv += sys->lambdaPlanar[v->u.id];
2520 }
2521
2522 if (v1->flag & PVERT_INTERIOR) {
2523 float product = p_abf_compute_sin_product(sys, v1, e->u.id);
2524 deriv += sys->lambdaLength[v1->u.id] * product;
2525 }
2526
2527 if (v2->flag & PVERT_INTERIOR) {
2528 float product = p_abf_compute_sin_product(sys, v2, e->u.id);
2529 deriv += sys->lambdaLength[v2->u.id] * product;
2530 }
2531
2532 return deriv;
2533}
2534
2535static float p_abf_compute_gradient(PAbfSystem *sys, PChart *chart)
2536{
2537 PFace *f;
2538 PEdge *e;
2539 PVert *v;
2540 float norm = 0.0;
2541
2542 for (f = chart->faces; f; f = f->nextlink) {
2543 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
2544 float gtriangle, galpha1, galpha2, galpha3;
2545
2546 galpha1 = p_abf_compute_grad_alpha(sys, f, e1);
2547 galpha2 = p_abf_compute_grad_alpha(sys, f, e2);
2548 galpha3 = p_abf_compute_grad_alpha(sys, f, e3);
2549
2550 sys->bAlpha[e1->u.id] = -galpha1;
2551 sys->bAlpha[e2->u.id] = -galpha2;
2552 sys->bAlpha[e3->u.id] = -galpha3;
2553
2554 norm += galpha1 * galpha1 + galpha2 * galpha2 + galpha3 * galpha3;
2555
2556 gtriangle = sys->alpha[e1->u.id] + sys->alpha[e2->u.id] + sys->alpha[e3->u.id] - float(M_PI);
2557 sys->bTriangle[f->u.id] = -gtriangle;
2558 norm += gtriangle * gtriangle;
2559 }
2560
2561 for (v = chart->verts; v; v = v->nextlink) {
2562 if (v->flag & PVERT_INTERIOR) {
2563 float gplanar = -2 * M_PI, glength;
2564
2565 e = v->edge;
2566 do {
2567 gplanar += sys->alpha[e->u.id];
2568 e = e->next->next->pair;
2569 } while (e && (e != v->edge));
2570
2571 sys->bInterior[v->u.id] = -gplanar;
2572 norm += gplanar * gplanar;
2573
2574 glength = p_abf_compute_sin_product(sys, v, -1);
2575 sys->bInterior[sys->ninterior + v->u.id] = -glength;
2576 norm += glength * glength;
2577 }
2578 }
2579
2580 return norm;
2581}
2582
2584 const int id,
2585 const float dlambda1,
2586 const float pre)
2587{
2588 float alpha = sys->alpha[id];
2589 const float dalpha = (sys->bAlpha[id] - dlambda1);
2590 alpha += dalpha / sys->weight[id] - pre;
2591 sys->alpha[id] = clamp_f(alpha, 0.0f, float(M_PI));
2592}
2593
2594static bool p_abf_matrix_invert(PAbfSystem *sys, PChart *chart)
2595{
2596 int ninterior = sys->ninterior;
2597 int nvar = 2 * ninterior;
2598 LinearSolver *context = EIG_linear_solver_new(0, nvar, 1);
2599
2600 for (int i = 0; i < nvar; i++) {
2601 EIG_linear_solver_right_hand_side_add(context, 0, i, sys->bInterior[i]);
2602 }
2603
2604 for (PFace *f = chart->faces; f; f = f->nextlink) {
2605 float wi1, wi2, wi3, b, si, beta[3], j2[3][3], W[3][3];
2606 float row1[6], row2[6], row3[6];
2607 int vid[6];
2608 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
2609 PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
2610
2611 wi1 = 1.0f / sys->weight[e1->u.id];
2612 wi2 = 1.0f / sys->weight[e2->u.id];
2613 wi3 = 1.0f / sys->weight[e3->u.id];
2614
2615 /* bstar1 = (J1*dInv*bAlpha - bTriangle) */
2616 b = sys->bAlpha[e1->u.id] * wi1;
2617 b += sys->bAlpha[e2->u.id] * wi2;
2618 b += sys->bAlpha[e3->u.id] * wi3;
2619 b -= sys->bTriangle[f->u.id];
2620
2621 /* si = J1*d*J1t */
2622 si = 1.0f / (wi1 + wi2 + wi3);
2623
2624 /* J1t*si*bstar1 - bAlpha */
2625 beta[0] = b * si - sys->bAlpha[e1->u.id];
2626 beta[1] = b * si - sys->bAlpha[e2->u.id];
2627 beta[2] = b * si - sys->bAlpha[e3->u.id];
2628
2629 /* use this later for computing other lambda's */
2630 sys->bstar[f->u.id] = b;
2631 sys->dstar[f->u.id] = si;
2632
2633 /* set matrix */
2634 W[0][0] = si - sys->weight[e1->u.id];
2635 W[0][1] = si;
2636 W[0][2] = si;
2637 W[1][0] = si;
2638 W[1][1] = si - sys->weight[e2->u.id];
2639 W[1][2] = si;
2640 W[2][0] = si;
2641 W[2][1] = si;
2642 W[2][2] = si - sys->weight[e3->u.id];
2643
2644 vid[0] = vid[1] = vid[2] = vid[3] = vid[4] = vid[5] = -1;
2645
2646 if (v1->flag & PVERT_INTERIOR) {
2647 vid[0] = v1->u.id;
2648 vid[3] = ninterior + v1->u.id;
2649
2650 sys->J2dt[e1->u.id][0] = j2[0][0] = 1.0f * wi1;
2651 sys->J2dt[e2->u.id][0] = j2[1][0] = p_abf_compute_sin_product(sys, v1, e2->u.id) * wi2;
2652 sys->J2dt[e3->u.id][0] = j2[2][0] = p_abf_compute_sin_product(sys, v1, e3->u.id) * wi3;
2653
2654 EIG_linear_solver_right_hand_side_add(context, 0, v1->u.id, j2[0][0] * beta[0]);
2656 context, 0, ninterior + v1->u.id, j2[1][0] * beta[1] + j2[2][0] * beta[2]);
2657
2658 row1[0] = j2[0][0] * W[0][0];
2659 row2[0] = j2[0][0] * W[1][0];
2660 row3[0] = j2[0][0] * W[2][0];
2661
2662 row1[3] = j2[1][0] * W[0][1] + j2[2][0] * W[0][2];
2663 row2[3] = j2[1][0] * W[1][1] + j2[2][0] * W[1][2];
2664 row3[3] = j2[1][0] * W[2][1] + j2[2][0] * W[2][2];
2665 }
2666
2667 if (v2->flag & PVERT_INTERIOR) {
2668 vid[1] = v2->u.id;
2669 vid[4] = ninterior + v2->u.id;
2670
2671 sys->J2dt[e1->u.id][1] = j2[0][1] = p_abf_compute_sin_product(sys, v2, e1->u.id) * wi1;
2672 sys->J2dt[e2->u.id][1] = j2[1][1] = 1.0f * wi2;
2673 sys->J2dt[e3->u.id][1] = j2[2][1] = p_abf_compute_sin_product(sys, v2, e3->u.id) * wi3;
2674
2675 EIG_linear_solver_right_hand_side_add(context, 0, v2->u.id, j2[1][1] * beta[1]);
2677 context, 0, ninterior + v2->u.id, j2[0][1] * beta[0] + j2[2][1] * beta[2]);
2678
2679 row1[1] = j2[1][1] * W[0][1];
2680 row2[1] = j2[1][1] * W[1][1];
2681 row3[1] = j2[1][1] * W[2][1];
2682
2683 row1[4] = j2[0][1] * W[0][0] + j2[2][1] * W[0][2];
2684 row2[4] = j2[0][1] * W[1][0] + j2[2][1] * W[1][2];
2685 row3[4] = j2[0][1] * W[2][0] + j2[2][1] * W[2][2];
2686 }
2687
2688 if (v3->flag & PVERT_INTERIOR) {
2689 vid[2] = v3->u.id;
2690 vid[5] = ninterior + v3->u.id;
2691
2692 sys->J2dt[e1->u.id][2] = j2[0][2] = p_abf_compute_sin_product(sys, v3, e1->u.id) * wi1;
2693 sys->J2dt[e2->u.id][2] = j2[1][2] = p_abf_compute_sin_product(sys, v3, e2->u.id) * wi2;
2694 sys->J2dt[e3->u.id][2] = j2[2][2] = 1.0f * wi3;
2695
2696 EIG_linear_solver_right_hand_side_add(context, 0, v3->u.id, j2[2][2] * beta[2]);
2698 context, 0, ninterior + v3->u.id, j2[0][2] * beta[0] + j2[1][2] * beta[1]);
2699
2700 row1[2] = j2[2][2] * W[0][2];
2701 row2[2] = j2[2][2] * W[1][2];
2702 row3[2] = j2[2][2] * W[2][2];
2703
2704 row1[5] = j2[0][2] * W[0][0] + j2[1][2] * W[0][1];
2705 row2[5] = j2[0][2] * W[1][0] + j2[1][2] * W[1][1];
2706 row3[5] = j2[0][2] * W[2][0] + j2[1][2] * W[2][1];
2707 }
2708
2709 for (int i = 0; i < 3; i++) {
2710 int r = vid[i];
2711
2712 if (r == -1) {
2713 continue;
2714 }
2715
2716 for (int j = 0; j < 6; j++) {
2717 int c = vid[j];
2718
2719 if (c == -1) {
2720 continue;
2721 }
2722
2723 if (i == 0) {
2724 EIG_linear_solver_matrix_add(context, r, c, j2[0][i] * row1[j]);
2725 }
2726 else {
2727 EIG_linear_solver_matrix_add(context, r + ninterior, c, j2[0][i] * row1[j]);
2728 }
2729
2730 if (i == 1) {
2731 EIG_linear_solver_matrix_add(context, r, c, j2[1][i] * row2[j]);
2732 }
2733 else {
2734 EIG_linear_solver_matrix_add(context, r + ninterior, c, j2[1][i] * row2[j]);
2735 }
2736
2737 if (i == 2) {
2738 EIG_linear_solver_matrix_add(context, r, c, j2[2][i] * row3[j]);
2739 }
2740 else {
2741 EIG_linear_solver_matrix_add(context, r + ninterior, c, j2[2][i] * row3[j]);
2742 }
2743 }
2744 }
2745 }
2746
2747 bool success = EIG_linear_solver_solve(context);
2748
2749 if (success) {
2750 for (PFace *f = chart->faces; f; f = f->nextlink) {
2751 float pre[3];
2752 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
2753 PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
2754
2755 pre[0] = pre[1] = pre[2] = 0.0f;
2756
2757 if (v1->flag & PVERT_INTERIOR) {
2758 float x = EIG_linear_solver_variable_get(context, 0, v1->u.id);
2759 float x2 = EIG_linear_solver_variable_get(context, 0, ninterior + v1->u.id);
2760 pre[0] += sys->J2dt[e1->u.id][0] * x;
2761 pre[1] += sys->J2dt[e2->u.id][0] * x2;
2762 pre[2] += sys->J2dt[e3->u.id][0] * x2;
2763 }
2764
2765 if (v2->flag & PVERT_INTERIOR) {
2766 float x = EIG_linear_solver_variable_get(context, 0, v2->u.id);
2767 float x2 = EIG_linear_solver_variable_get(context, 0, ninterior + v2->u.id);
2768 pre[0] += sys->J2dt[e1->u.id][1] * x2;
2769 pre[1] += sys->J2dt[e2->u.id][1] * x;
2770 pre[2] += sys->J2dt[e3->u.id][1] * x2;
2771 }
2772
2773 if (v3->flag & PVERT_INTERIOR) {
2774 float x = EIG_linear_solver_variable_get(context, 0, v3->u.id);
2775 float x2 = EIG_linear_solver_variable_get(context, 0, ninterior + v3->u.id);
2776 pre[0] += sys->J2dt[e1->u.id][2] * x2;
2777 pre[1] += sys->J2dt[e2->u.id][2] * x2;
2778 pre[2] += sys->J2dt[e3->u.id][2] * x;
2779 }
2780
2781 float dlambda1 = pre[0] + pre[1] + pre[2];
2782 dlambda1 = sys->dstar[f->u.id] * (sys->bstar[f->u.id] - dlambda1);
2783
2784 sys->lambdaTriangle[f->u.id] += dlambda1;
2785
2786 p_abf_adjust_alpha(sys, e1->u.id, dlambda1, pre[0]);
2787 p_abf_adjust_alpha(sys, e2->u.id, dlambda1, pre[1]);
2788 p_abf_adjust_alpha(sys, e3->u.id, dlambda1, pre[2]);
2789 }
2790
2791 for (int i = 0; i < ninterior; i++) {
2792 sys->lambdaPlanar[i] += float(EIG_linear_solver_variable_get(context, 0, i));
2793 sys->lambdaLength[i] += float(EIG_linear_solver_variable_get(context, 0, ninterior + i));
2794 }
2795 }
2796
2797 EIG_linear_solver_delete(context);
2798
2799 return success;
2800}
2801
2802static bool p_chart_abf_solve(PChart *chart)
2803{
2804 PVert *v;
2805 PFace *f;
2806 PEdge *e, *e1, *e2, *e3;
2807 PAbfSystem sys;
2808 int i;
2809 float /* lastnorm, */ /* UNUSED */ limit = (chart->nfaces > 100) ? 1.0f : 0.001f;
2810
2811 /* setup id's */
2812 sys.ninterior = sys.nfaces = sys.nangles = 0;
2813
2814 for (v = chart->verts; v; v = v->nextlink) {
2815 if (p_vert_interior(v)) {
2816 v->flag |= PVERT_INTERIOR;
2817 v->u.id = sys.ninterior++;
2818 }
2819 else {
2820 v->flag &= ~PVERT_INTERIOR;
2821 }
2822 }
2823
2824 for (f = chart->faces; f; f = f->nextlink) {
2825 e1 = f->edge;
2826 e2 = e1->next;
2827 e3 = e2->next;
2828 f->u.id = sys.nfaces++;
2829
2830 /* angle id's are conveniently stored in half edges */
2831 e1->u.id = sys.nangles++;
2832 e2->u.id = sys.nangles++;
2833 e3->u.id = sys.nangles++;
2834 }
2835
2836 p_abf_setup_system(&sys);
2837
2838 /* compute initial angles */
2839 for (f = chart->faces; f; f = f->nextlink) {
2840 double a1, a2, a3;
2841
2842 e1 = f->edge;
2843 e2 = e1->next;
2844 e3 = e2->next;
2845 p_face_angles(f, &a1, &a2, &a3);
2846
2847 sys.alpha[e1->u.id] = sys.beta[e1->u.id] = a1;
2848 sys.alpha[e2->u.id] = sys.beta[e2->u.id] = a2;
2849 sys.alpha[e3->u.id] = sys.beta[e3->u.id] = a3;
2850
2851 sys.weight[e1->u.id] = 2.0f / (a1 * a1);
2852 sys.weight[e2->u.id] = 2.0f / (a2 * a2);
2853 sys.weight[e3->u.id] = 2.0f / (a3 * a3);
2854 }
2855
2856 for (v = chart->verts; v; v = v->nextlink) {
2857 if (v->flag & PVERT_INTERIOR) {
2858 float anglesum = 0.0, scale;
2859
2860 e = v->edge;
2861 do {
2862 anglesum += sys.beta[e->u.id];
2863 e = e->next->next->pair;
2864 } while (e && (e != v->edge));
2865
2866 scale = (anglesum == 0.0f) ? 0.0f : 2.0f * float(M_PI) / anglesum;
2867
2868 e = v->edge;
2869 do {
2870 sys.beta[e->u.id] = sys.alpha[e->u.id] = sys.beta[e->u.id] * scale;
2871 e = e->next->next->pair;
2872 } while (e && (e != v->edge));
2873 }
2874 }
2875
2876 if (sys.ninterior > 0) {
2877 p_abf_compute_sines(&sys);
2878
2879 /* iteration */
2880 // lastnorm = 1e10; /* UNUSED. */
2881
2882 for (i = 0; i < ABF_MAX_ITER; i++) {
2883 float norm = p_abf_compute_gradient(&sys, chart);
2884
2885 // lastnorm = norm; /* UNUSED. */
2886
2887 if (norm < limit) {
2888 break;
2889 }
2890
2891 if (!p_abf_matrix_invert(&sys, chart)) {
2892 param_warning("ABF failed to invert matrix");
2893 return false;
2894 }
2895
2896 p_abf_compute_sines(&sys);
2897 }
2898
2899 if (i == ABF_MAX_ITER) {
2900 param_warning("ABF maximum iterations reached");
2901 return false;
2902 }
2903 }
2904
2905 chart->abf_alpha = MEM_new_array_uninitialized<float>(sys.alpha.size(), __func__);
2907
2908 return true;
2909}
2910
2911/* Least Squares Conformal Maps */
2912
2913static void p_chart_pin_positions(PChart *chart, PVert **pin1, PVert **pin2)
2914{
2915 if (!*pin1 || !*pin2 || *pin1 == *pin2) {
2916 /* degenerate case */
2917 PFace *f = chart->faces;
2918 *pin1 = f->edge->vert;
2919 *pin2 = f->edge->next->vert;
2920
2921 (*pin1)->uv[0] = 0.0f;
2922 (*pin1)->uv[1] = 0.5f;
2923 (*pin2)->uv[0] = 1.0f;
2924 (*pin2)->uv[1] = 0.5f;
2925 }
2926 else {
2927 int diru, dirv, dirx, diry;
2928 float sub[3];
2929
2930 sub_v3_v3v3(sub, (*pin1)->co, (*pin2)->co);
2931 sub[0] = fabsf(sub[0]);
2932 sub[1] = fabsf(sub[1]);
2933 sub[2] = fabsf(sub[2]);
2934
2935 if ((sub[0] > sub[1]) && (sub[0] > sub[2])) {
2936 dirx = 0;
2937 diry = (sub[1] > sub[2]) ? 1 : 2;
2938 }
2939 else if ((sub[1] > sub[0]) && (sub[1] > sub[2])) {
2940 dirx = 1;
2941 diry = (sub[0] > sub[2]) ? 0 : 2;
2942 }
2943 else {
2944 dirx = 2;
2945 diry = (sub[0] > sub[1]) ? 0 : 1;
2946 }
2947
2948 if (dirx == 2) {
2949 diru = 1;
2950 dirv = 0;
2951 }
2952 else {
2953 diru = 0;
2954 dirv = 1;
2955 }
2956
2957 (*pin1)->uv[diru] = (*pin1)->co[dirx];
2958 (*pin1)->uv[dirv] = (*pin1)->co[diry];
2959 (*pin2)->uv[diru] = (*pin2)->co[dirx];
2960 (*pin2)->uv[dirv] = (*pin2)->co[diry];
2961 }
2962}
2963
2964static bool p_chart_symmetry_pins(PChart *chart, PEdge *outer, PVert **pin1, PVert **pin2)
2965{
2966 PEdge *be, *lastbe = nullptr, *maxe1 = nullptr, *maxe2 = nullptr, *be1, *be2;
2967 PEdge *cure = nullptr, *firste1 = nullptr, *firste2 = nullptr, *nextbe;
2968 float maxlen = 0.0f, curlen = 0.0f, totlen = 0.0f, firstlen = 0.0f;
2969 float len1, len2;
2970
2971 /* find longest series of verts split in the chart itself, these are
2972 * marked during construction */
2973 be = outer;
2974 lastbe = p_boundary_edge_prev(be);
2975 do {
2976 float len = p_edge_length(be);
2977 totlen += len;
2978
2979 nextbe = p_boundary_edge_next(be);
2980
2981 if ((be->vert->flag & PVERT_SPLIT) || (lastbe->vert->flag & nextbe->vert->flag & PVERT_SPLIT))
2982 {
2983 if (!cure) {
2984 if (be == outer) {
2985 firste1 = be;
2986 }
2987 cure = be;
2988 }
2989 else {
2990 curlen += p_edge_length(lastbe);
2991 }
2992 }
2993 else if (cure) {
2994 if (curlen > maxlen) {
2995 maxlen = curlen;
2996 maxe1 = cure;
2997 maxe2 = lastbe;
2998 }
2999
3000 if (firste1 == cure) {
3001 firstlen = curlen;
3002 firste2 = lastbe;
3003 }
3004
3005 curlen = 0.0f;
3006 cure = nullptr;
3007 }
3008
3009 lastbe = be;
3010 be = nextbe;
3011 } while (be != outer);
3012
3013 /* make sure we also count a series of splits over the starting point */
3014 if (cure && (cure != outer)) {
3015 firstlen += curlen + p_edge_length(be);
3016
3017 if (firstlen > maxlen) {
3018 maxlen = firstlen;
3019 maxe1 = cure;
3020 maxe2 = firste2;
3021 }
3022 }
3023
3024 if (!maxe1 || !maxe2 || (maxlen < 0.5f * totlen)) {
3025 return false;
3026 }
3027
3028 /* find pin1 in the split vertices */
3029 be1 = maxe1;
3030 be2 = maxe2;
3031 len1 = 0.0f;
3032 len2 = 0.0f;
3033
3034 do {
3035 if (len1 < len2) {
3036 len1 += p_edge_length(be1);
3037 be1 = p_boundary_edge_next(be1);
3038 }
3039 else {
3040 be2 = p_boundary_edge_prev(be2);
3041 len2 += p_edge_length(be2);
3042 }
3043 } while (be1 != be2);
3044
3045 *pin1 = be1->vert;
3046
3047 /* find pin2 outside the split vertices */
3048 be1 = maxe1;
3049 be2 = maxe2;
3050 len1 = 0.0f;
3051 len2 = 0.0f;
3052
3053 do {
3054 if (len1 < len2) {
3055 be1 = p_boundary_edge_prev(be1);
3056 len1 += p_edge_length(be1);
3057 }
3058 else {
3059 len2 += p_edge_length(be2);
3060 be2 = p_boundary_edge_next(be2);
3061 }
3062 } while (be1 != be2);
3063
3064 *pin2 = be1->vert;
3065
3066 p_chart_pin_positions(chart, pin1, pin2);
3067
3068 return !equals_v3v3((*pin1)->co, (*pin2)->co);
3069}
3070
3071static void p_chart_extrema_verts(PChart *chart, PVert **pin1, PVert **pin2)
3072{
3073 float minv[3], maxv[3], dirlen;
3074 PVert *v, *minvert[3], *maxvert[3];
3075 int i, dir;
3076
3077 /* find minimum and maximum verts over x/y/z axes */
3078 minv[0] = minv[1] = minv[2] = 1e20;
3079 maxv[0] = maxv[1] = maxv[2] = -1e20;
3080
3081 minvert[0] = minvert[1] = minvert[2] = nullptr;
3082 maxvert[0] = maxvert[1] = maxvert[2] = nullptr;
3083
3084 for (v = chart->verts; v; v = v->nextlink) {
3085 for (i = 0; i < 3; i++) {
3086 if (v->co[i] < minv[i]) {
3087 minv[i] = v->co[i];
3088 minvert[i] = v;
3089 }
3090 if (v->co[i] > maxv[i]) {
3091 maxv[i] = v->co[i];
3092 maxvert[i] = v;
3093 }
3094 }
3095 }
3096
3097 /* find axes with longest distance */
3098 dir = 0;
3099 dirlen = -1.0;
3100
3101 for (i = 0; i < 3; i++) {
3102 if (maxv[i] - minv[i] > dirlen) {
3103 dir = i;
3104 dirlen = maxv[i] - minv[i];
3105 }
3106 }
3107
3108 *pin1 = minvert[dir];
3109 *pin2 = maxvert[dir];
3110
3111 p_chart_pin_positions(chart, pin1, pin2);
3112}
3113
3119{
3120 chart->orig_bounds = MEM_new<PChartOrigBounds>("PChartOrigBounds");
3122 p_chart_uv_bbox(chart, chart->orig_bounds->bounds.min, chart->orig_bounds->bounds.max);
3123}
3124
3125static void p_chart_lscm_begin(PChart *chart, bool live, bool abf, const bool use_original_bounds)
3126{
3127 BLI_assert(chart->context == nullptr);
3128
3129 bool select = false;
3130 bool deselect = false;
3131 int npins = 0;
3132 if (use_original_bounds) {
3134 }
3135 /* Give vertices matrix indices, count pins and check selections. */
3136 for (PVert *v = chart->verts; v; v = v->nextlink) {
3137 if (v->flag & PVERT_PIN) {
3138 npins++;
3139 if (v->flag & PVERT_SELECT) {
3140 select = true;
3141 }
3142 }
3143
3144 if (!(v->flag & PVERT_SELECT)) {
3145 deselect = true;
3146 }
3147 }
3148
3149 if (live && (!select || !deselect)) {
3150 chart->skip_flush = true;
3151 return;
3152 }
3153#if 0
3154 p_chart_simplify_compute(chart, p_collapse_cost, p_collapse_allowed);
3155 p_chart_topological_sanity_check(chart);
3156#endif
3157
3158 if (npins == 1) {
3159 chart->area_uv = p_chart_uv_area(chart);
3160 for (PVert *v = chart->verts; v; v = v->nextlink) {
3161 if (v->flag & PVERT_PIN) {
3162 chart->single_pin = v;
3163 break;
3164 }
3165 }
3166 }
3167
3168 if (abf) {
3169 if (!p_chart_abf_solve(chart)) {
3170 param_warning("ABF solving failed: falling back to LSCM.\n");
3171 }
3172 }
3173
3174 /* ABF uses these indices for it's internal references.
3175 * Set the indices afterwards. */
3176 int id = 0;
3177 for (PVert *v = chart->verts; v; v = v->nextlink) {
3178 v->u.id = id++;
3179 }
3180
3181 if (npins <= 1) {
3182 /* No pins, let's find some ourself. */
3183 PEdge *outer;
3184 p_chart_boundaries(chart, &outer);
3185
3186 PVert *pin1, *pin2;
3187 /* Outer can be null with non-finite coordinates. */
3188 if (!(outer && p_chart_symmetry_pins(chart, outer, &pin1, &pin2))) {
3189 p_chart_extrema_verts(chart, &pin1, &pin2);
3190 }
3191
3192 chart->pin1 = pin1;
3193 chart->pin2 = pin2;
3194 }
3195
3196 chart->context = EIG_linear_least_squares_solver_new(2 * chart->nfaces, 2 * chart->nverts, 1);
3197}
3198
3199static bool p_chart_lscm_solve(ParamHandle *handle, PChart *chart)
3200{
3201 LinearSolver *context = chart->context;
3202
3203 for (PVert *v = chart->verts; v; v = v->nextlink) {
3204 if (v->flag & PVERT_PIN) {
3205 p_vert_load_pin_select_uvs(handle, v); /* Reload for Live Unwrap. */
3206 }
3207 }
3208
3209 if (chart->single_pin) {
3210 /* If only one pin, save location as origin. */
3211 copy_v2_v2(chart->origin, chart->single_pin->uv);
3212 }
3213
3214 if (chart->pin1) {
3215 PVert *pin1 = chart->pin1;
3216 PVert *pin2 = chart->pin2;
3217 EIG_linear_solver_variable_lock(context, 2 * pin1->u.id);
3218 EIG_linear_solver_variable_lock(context, 2 * pin1->u.id + 1);
3219 EIG_linear_solver_variable_lock(context, 2 * pin2->u.id);
3220 EIG_linear_solver_variable_lock(context, 2 * pin2->u.id + 1);
3221
3222 EIG_linear_solver_variable_set(context, 0, 2 * pin1->u.id, pin1->uv[0]);
3223 EIG_linear_solver_variable_set(context, 0, 2 * pin1->u.id + 1, pin1->uv[1]);
3224 EIG_linear_solver_variable_set(context, 0, 2 * pin2->u.id, pin2->uv[0]);
3225 EIG_linear_solver_variable_set(context, 0, 2 * pin2->u.id + 1, pin2->uv[1]);
3226 }
3227 else {
3228 /* Set and lock the pins. */
3229 for (PVert *v = chart->verts; v; v = v->nextlink) {
3230 if (v->flag & PVERT_PIN) {
3231 EIG_linear_solver_variable_lock(context, 2 * v->u.id);
3232 EIG_linear_solver_variable_lock(context, 2 * v->u.id + 1);
3233
3234 EIG_linear_solver_variable_set(context, 0, 2 * v->u.id, v->uv[0]);
3235 EIG_linear_solver_variable_set(context, 0, 2 * v->u.id + 1, v->uv[1]);
3236 }
3237 }
3238 }
3239
3240 /* Detect "up" direction based on pinned vertices. */
3241 float area_pinned_up = 0.0f;
3242 float area_pinned_down = 0.0f;
3243
3244 for (PFace *f = chart->faces; f; f = f->nextlink) {
3245 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
3246 PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
3247
3248 if ((v1->flag & PVERT_PIN) && (v2->flag & PVERT_PIN) && (v3->flag & PVERT_PIN)) {
3249 const float area = p_face_uv_area_signed(f);
3250
3251 if (area > 0.0f) {
3252 area_pinned_up += area;
3253 }
3254 else {
3255 area_pinned_down -= area;
3256 }
3257 }
3258 }
3259
3260 const bool flip_faces = (area_pinned_down > area_pinned_up);
3261
3262 /* Construct matrix. */
3263 const float *alpha = chart->abf_alpha;
3264 int row = 0;
3265 for (PFace *f = chart->faces; f; f = f->nextlink) {
3266 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
3267 PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
3268 double a1, a2, a3;
3269
3270 if (alpha) {
3271 /* Use abf angles if present. */
3272 a1 = *(alpha++);
3273 a2 = *(alpha++);
3274 a3 = *(alpha++);
3275 }
3276 else {
3277 p_face_angles(f, &a1, &a2, &a3);
3278 }
3279
3280 if (flip_faces) {
3281 std::swap(a2, a3);
3282 std::swap(e2, e3);
3283 std::swap(v2, v3);
3284 }
3285
3286 double sina1 = sin(a1);
3287 double sina2 = sin(a2);
3288 double sina3 = sin(a3);
3289
3290 const double sinmax = std::max({sina1, sina2, sina3});
3291
3292 /* Shift vertices to find most stable order. */
3293 if (sina3 != sinmax) {
3294 SHIFT3(PVert *, v1, v2, v3);
3295 SHIFT3(double, a1, a2, a3);
3296 SHIFT3(double, sina1, sina2, sina3);
3297
3298 if (sina2 == sinmax) {
3299 SHIFT3(PVert *, v1, v2, v3);
3300 SHIFT3(double, a1, a2, a3);
3301 SHIFT3(double, sina1, sina2, sina3);
3302 }
3303 }
3304
3305 /* Angle based lscm formulation. */
3306 const double ratio = (sina3 == 0.0f) ? 1.0f : sina2 / sina3;
3307 const double cosine = cos(a1) * ratio;
3308 const double sine = sina1 * ratio;
3309
3310 EIG_linear_solver_matrix_add(context, row, 2 * v1->u.id, cosine - 1.0f);
3311 EIG_linear_solver_matrix_add(context, row, 2 * v1->u.id + 1, -sine);
3312 EIG_linear_solver_matrix_add(context, row, 2 * v2->u.id, -cosine);
3313 EIG_linear_solver_matrix_add(context, row, 2 * v2->u.id + 1, sine);
3314 EIG_linear_solver_matrix_add(context, row, 2 * v3->u.id, 1.0);
3315 row++;
3316
3317 EIG_linear_solver_matrix_add(context, row, 2 * v1->u.id, sine);
3318 EIG_linear_solver_matrix_add(context, row, 2 * v1->u.id + 1, cosine - 1.0f);
3319 EIG_linear_solver_matrix_add(context, row, 2 * v2->u.id, -sine);
3320 EIG_linear_solver_matrix_add(context, row, 2 * v2->u.id + 1, -cosine);
3321 EIG_linear_solver_matrix_add(context, row, 2 * v3->u.id + 1, 1.0);
3322 row++;
3323 }
3324
3325 if (EIG_linear_solver_solve(context)) {
3326 for (PVert *v = chart->verts; v; v = v->nextlink) {
3327 v->uv[0] = EIG_linear_solver_variable_get(context, 0, 2 * v->u.id);
3328 v->uv[1] = EIG_linear_solver_variable_get(context, 0, 2 * v->u.id + 1);
3329 }
3330 return true;
3331 }
3332
3333 for (PVert *v = chart->verts; v; v = v->nextlink) {
3334 v->uv[0] = 0.0f;
3335 v->uv[1] = 0.0f;
3336 }
3337
3338 return false;
3339}
3340
3342{
3343 PVert *pin = chart->single_pin;
3344
3345 /* If only one pin, keep UV area the same. */
3346 const float new_area = p_chart_uv_area(chart);
3347 if (new_area > 0.0f) {
3348 const float scale = chart->area_uv / new_area;
3349 if (scale > 0.0f) {
3350 p_chart_uv_scale(chart, sqrtf(scale));
3351 }
3352 }
3353
3354 /* Translate to keep the pinned UV in place. */
3355 float offset[2];
3356 sub_v2_v2v2(offset, chart->origin, pin->uv);
3357 p_chart_uv_translate(chart, offset);
3358}
3359
3360static void p_chart_lscm_end(PChart *chart)
3361{
3363 chart->context = nullptr;
3364
3365 MEM_SAFE_DELETE(chart->abf_alpha);
3366
3367 chart->pin1 = nullptr;
3368 chart->pin2 = nullptr;
3369 chart->single_pin = nullptr;
3370}
3371
3372/* Stretch */
3373
3374#define P_STRETCH_ITER 20
3375
3377{
3378 PVert *v;
3379
3380 for (v = chart->verts; v; v = v->nextlink) {
3381 if (v->edge->pair == nullptr) {
3382 v->flag |= PVERT_PIN;
3383 }
3384 else {
3385 v->flag &= ~PVERT_PIN;
3386 }
3387 }
3388}
3389
3390static float p_face_stretch(PFace *f)
3391{
3392 float T, w, tmp[3];
3393 float Ps[3], Pt[3];
3394 float a, c, area;
3395 PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
3396 PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
3397
3398 area = p_face_uv_area_signed(f);
3399
3400 if (area <= 0.0f) {
3401 /* When a face is flipped, provide a large penalty.
3402 * Add on a slight gradient to unflip the face, see also: #99781. */
3403 return 1e8f * (1.0f + p_edge_uv_length(e1) + p_edge_uv_length(e2) + p_edge_uv_length(e3));
3404 }
3405
3406 w = 1.0f / (2.0f * area);
3407
3408 /* compute derivatives */
3409 copy_v3_v3(Ps, v1->co);
3410 mul_v3_fl(Ps, (v2->uv[1] - v3->uv[1]));
3411
3412 copy_v3_v3(tmp, v2->co);
3413 mul_v3_fl(tmp, (v3->uv[1] - v1->uv[1]));
3414 add_v3_v3(Ps, tmp);
3415
3416 copy_v3_v3(tmp, v3->co);
3417 mul_v3_fl(tmp, (v1->uv[1] - v2->uv[1]));
3418 add_v3_v3(Ps, tmp);
3419
3420 mul_v3_fl(Ps, w);
3421
3422 copy_v3_v3(Pt, v1->co);
3423 mul_v3_fl(Pt, (v3->uv[0] - v2->uv[0]));
3424
3425 copy_v3_v3(tmp, v2->co);
3426 mul_v3_fl(tmp, (v1->uv[0] - v3->uv[0]));
3427 add_v3_v3(Pt, tmp);
3428
3429 copy_v3_v3(tmp, v3->co);
3430 mul_v3_fl(tmp, (v2->uv[0] - v1->uv[0]));
3431 add_v3_v3(Pt, tmp);
3432
3433 mul_v3_fl(Pt, w);
3434
3435 /* Sander Tensor */
3436 a = dot_v3v3(Ps, Ps);
3437 c = dot_v3v3(Pt, Pt);
3438
3439 T = sqrtf(0.5f * (a + c));
3440 if (f->flag & PFACE_FILLED) {
3441 T *= 0.2f;
3442 }
3443
3444 return T;
3445}
3446
3448{
3449 PEdge *e = v->edge;
3450 float sum = 0.0f;
3451
3452 do {
3453 sum += p_face_stretch(e->face);
3455 } while (e && e != (v->edge));
3456
3457 return sum;
3458}
3459
3460static void p_chart_stretch_minimize(PChart *chart, RNG *rng)
3461{
3462 PVert *v;
3463 PEdge *e;
3464 int j, nedges;
3465 float orig_stretch, low, stretch_low, high, stretch_high, mid, stretch;
3466 float orig_uv[2], dir[2], random_angle, trusted_radius;
3467
3468 for (v = chart->verts; v; v = v->nextlink) {
3469 if ((v->flag & PVERT_PIN) || !(v->flag & PVERT_SELECT)) {
3470 continue;
3471 }
3472
3473 orig_stretch = p_stretch_compute_vertex(v);
3474 orig_uv[0] = v->uv[0];
3475 orig_uv[1] = v->uv[1];
3476
3477 /* move vertex in a random direction */
3478 trusted_radius = 0.0f;
3479 nedges = 0;
3480 e = v->edge;
3481
3482 do {
3483 trusted_radius += p_edge_uv_length(e);
3484 nedges++;
3485
3487 } while (e && e != (v->edge));
3488
3489 trusted_radius /= 2 * nedges;
3490
3491 random_angle = BLI_rng_get_float(rng) * 2.0f * float(M_PI);
3492 dir[0] = trusted_radius * cosf(random_angle);
3493 dir[1] = trusted_radius * sinf(random_angle);
3494
3495 /* calculate old and new stretch */
3496 low = 0;
3497 stretch_low = orig_stretch;
3498
3499 add_v2_v2v2(v->uv, orig_uv, dir);
3500 high = 1;
3501 stretch = stretch_high = p_stretch_compute_vertex(v);
3502
3503 /* binary search for lowest stretch position */
3504 for (j = 0; j < P_STRETCH_ITER; j++) {
3505 mid = 0.5f * (low + high);
3506 v->uv[0] = orig_uv[0] + mid * dir[0];
3507 v->uv[1] = orig_uv[1] + mid * dir[1];
3508 stretch = p_stretch_compute_vertex(v);
3509
3510 if (stretch_low < stretch_high) {
3511 high = mid;
3512 stretch_high = stretch;
3513 }
3514 else {
3515 low = mid;
3516 stretch_low = stretch;
3517 }
3518 }
3519
3520 /* no luck, stretch has increased, reset to old values */
3521 if (stretch >= orig_stretch) {
3522 copy_v2_v2(v->uv, orig_uv);
3523 }
3524 }
3525}
3526
3527/* Minimum area enclosing rectangle for packing */
3528
3529static int p_compare_geometric_uv(const void *a, const void *b)
3530{
3531 const PVert *v1 = *static_cast<const PVert *const *>(a);
3532 const PVert *v2 = *static_cast<const PVert *const *>(b);
3533
3534 if (v1->uv[0] < v2->uv[0]) {
3535 return -1;
3536 }
3537 if (v1->uv[0] == v2->uv[0]) {
3538 if (v1->uv[1] < v2->uv[1]) {
3539 return -1;
3540 }
3541 if (v1->uv[1] == v2->uv[1]) {
3542 return 0;
3543 }
3544 return 1;
3545 }
3546 return 1;
3547}
3548
3549static bool p_chart_convex_hull(PChart *chart, PVert ***r_verts, int *r_nverts, int *r_right)
3550{
3551 /* Graham algorithm, taken from:
3552 * http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117225 */
3553
3554 PEdge *be, *e;
3555 int npoints = 0, i, ulen, llen;
3556 PVert **U, **L, **points, **p;
3557
3558 p_chart_boundaries(chart, &be);
3559
3560 if (!be) {
3561 return false;
3562 }
3563
3564 e = be;
3565 do {
3566 npoints++;
3568 } while (e != be);
3569
3570 p = points = MEM_new_array_uninitialized<PVert *>(2 * size_t(npoints), "PCHullpoints");
3571 U = MEM_new_array_uninitialized<PVert *>(size_t(npoints), "PCHullU");
3572 L = MEM_new_array_uninitialized<PVert *>(size_t(npoints), "PCHullL");
3573
3574 e = be;
3575 do {
3576 *p = e->vert;
3577 p++;
3579 } while (e != be);
3580
3581 qsort(points, npoints, sizeof(PVert *), p_compare_geometric_uv);
3582
3583 ulen = llen = 0;
3584 for (p = points, i = 0; i < npoints; i++, p++) {
3585 while ((ulen > 1) && (p_area_signed(U[ulen - 2]->uv, (*p)->uv, U[ulen - 1]->uv) <= 0)) {
3586 ulen--;
3587 }
3588 while ((llen > 1) && (p_area_signed(L[llen - 2]->uv, (*p)->uv, L[llen - 1]->uv) >= 0)) {
3589 llen--;
3590 }
3591
3592 U[ulen] = *p;
3593 ulen++;
3594 L[llen] = *p;
3595 llen++;
3596 }
3597
3598 npoints = 0;
3599 for (p = points, i = 0; i < ulen; i++, p++, npoints++) {
3600 *p = U[i];
3601 }
3602
3603 /* the first and last point in L are left out, since they are also in U */
3604 for (i = llen - 2; i > 0; i--, p++, npoints++) {
3605 *p = L[i];
3606 }
3607
3608 *r_verts = points;
3609 *r_nverts = npoints;
3610 *r_right = ulen - 1;
3611
3612 MEM_delete(U);
3613 MEM_delete(L);
3614
3615 return true;
3616}
3617
3618static float p_rectangle_area(float *p1, float *dir, float *p2, float *p3, float *p4)
3619{
3620 /* given 4 points on the rectangle edges and the direction of on edge,
3621 * compute the area of the rectangle */
3622
3623 float orthodir[2], corner1[2], corner2[2], corner3[2];
3624
3625 orthodir[0] = dir[1];
3626 orthodir[1] = -dir[0];
3627
3628 if (!p_intersect_line_2d_dir(p1, dir, p2, orthodir, corner1)) {
3629 return 1e10;
3630 }
3631
3632 if (!p_intersect_line_2d_dir(p1, dir, p4, orthodir, corner2)) {
3633 return 1e10;
3634 }
3635
3636 if (!p_intersect_line_2d_dir(p3, dir, p4, orthodir, corner3)) {
3637 return 1e10;
3638 }
3639
3640 return len_v2v2(corner1, corner2) * len_v2v2(corner2, corner3);
3641}
3642
3644{
3645 /* minimum area enclosing rectangle with rotating calipers, info:
3646 * http://cgm.cs.mcgill.ca/~orm/maer.html */
3647
3648 float rotated, minarea, minangle, area, len;
3649 float *angles, miny, maxy, v[2], a[4], mina;
3650 int npoints, right, i_min, i_max, i, idx[4], nextidx;
3651 PVert **points, *p1, *p2, *p3, *p4, *p1n;
3652
3653 /* compute convex hull */
3654 if (!p_chart_convex_hull(chart, &points, &npoints, &right)) {
3655 return 0.0;
3656 }
3657
3658 /* find left/top/right/bottom points, and compute angle for each point */
3659 angles = MEM_new_array_uninitialized<float>(size_t(npoints), "PMinAreaAngles");
3660
3661 i_min = i_max = 0;
3662 miny = 1e10;
3663 maxy = -1e10;
3664
3665 for (i = 0; i < npoints; i++) {
3666 p1 = (i == 0) ? points[npoints - 1] : points[i - 1];
3667 p2 = points[i];
3668 p3 = (i == npoints - 1) ? points[0] : points[i + 1];
3669
3670 angles[i] = float(M_PI) - angle_v2v2v2(p1->uv, p2->uv, p3->uv);
3671
3672 if (points[i]->uv[1] < miny) {
3673 miny = points[i]->uv[1];
3674 i_min = i;
3675 }
3676 if (points[i]->uv[1] > maxy) {
3677 maxy = points[i]->uv[1];
3678 i_max = i;
3679 }
3680 }
3681
3682 /* left, top, right, bottom */
3683 idx[0] = 0;
3684 idx[1] = i_max;
3685 idx[2] = right;
3686 idx[3] = i_min;
3687
3688 v[0] = points[idx[0]]->uv[0];
3689 v[1] = points[idx[0]]->uv[1] + 1.0f;
3690 a[0] = angle_v2v2v2(points[(idx[0] + 1) % npoints]->uv, points[idx[0]]->uv, v);
3691
3692 v[0] = points[idx[1]]->uv[0] + 1.0f;
3693 v[1] = points[idx[1]]->uv[1];
3694 a[1] = angle_v2v2v2(points[(idx[1] + 1) % npoints]->uv, points[idx[1]]->uv, v);
3695
3696 v[0] = points[idx[2]]->uv[0];
3697 v[1] = points[idx[2]]->uv[1] - 1.0f;
3698 a[2] = angle_v2v2v2(points[(idx[2] + 1) % npoints]->uv, points[idx[2]]->uv, v);
3699
3700 v[0] = points[idx[3]]->uv[0] - 1.0f;
3701 v[1] = points[idx[3]]->uv[1];
3702 a[3] = angle_v2v2v2(points[(idx[3] + 1) % npoints]->uv, points[idx[3]]->uv, v);
3703
3704 /* 4 rotating calipers */
3705
3706 rotated = 0.0;
3707 minarea = 1e10;
3708 minangle = 0.0;
3709
3710 while (rotated <= float(M_PI_2)) { /* INVESTIGATE: how far to rotate? */
3711 /* rotate with the smallest angle */
3712 i_min = 0;
3713 mina = 1e10;
3714
3715 for (i = 0; i < 4; i++) {
3716 if (a[i] < mina) {
3717 mina = a[i];
3718 i_min = i;
3719 }
3720 }
3721
3722 rotated += mina;
3723 nextidx = (idx[i_min] + 1) % npoints;
3724
3725 a[i_min] = angles[nextidx];
3726 a[(i_min + 1) % 4] = a[(i_min + 1) % 4] - mina;
3727 a[(i_min + 2) % 4] = a[(i_min + 2) % 4] - mina;
3728 a[(i_min + 3) % 4] = a[(i_min + 3) % 4] - mina;
3729
3730 /* compute area */
3731 p1 = points[idx[i_min]];
3732 p1n = points[nextidx];
3733 p2 = points[idx[(i_min + 1) % 4]];
3734 p3 = points[idx[(i_min + 2) % 4]];
3735 p4 = points[idx[(i_min + 3) % 4]];
3736
3737 len = len_v2v2(p1->uv, p1n->uv);
3738
3739 if (len > 0.0f) {
3740 len = 1.0f / len;
3741 v[0] = (p1n->uv[0] - p1->uv[0]) * len;
3742 v[1] = (p1n->uv[1] - p1->uv[1]) * len;
3743
3744 area = p_rectangle_area(p1->uv, v, p2->uv, p3->uv, p4->uv);
3745
3746 /* remember smallest area */
3747 if (area < minarea) {
3748 minarea = area;
3749 minangle = rotated;
3750 }
3751 }
3752
3753 idx[i_min] = nextidx;
3754 }
3755
3756 /* try keeping rotation as small as possible */
3757 if (minangle > float(M_PI_4)) {
3758 minangle -= float(M_PI_2);
3759 }
3760
3761 MEM_delete(angles);
3762 MEM_delete(points);
3763
3764 return minangle;
3765}
3766
3768{
3769 float angle = p_chart_minimum_area_angle(chart);
3770 float sine = sinf(angle);
3771 float cosine = cosf(angle);
3772 PVert *v;
3773
3774 for (v = chart->verts; v; v = v->nextlink) {
3775 float oldu = v->uv[0], oldv = v->uv[1];
3776 v->uv[0] = cosine * oldu - sine * oldv;
3777 v->uv[1] = sine * oldu + cosine * oldv;
3778 }
3779}
3780
3782{
3783 Array<float2> points(chart->nverts);
3784
3785 p_chart_uv_to_array(chart, points);
3786
3788
3789 if (sincos != float2(0.0f, 1.0f)) {
3790 /* Equivalent to #angle_to_mat2. */
3791 const float mat[2][2] = {{sincos[1], sincos[0]}, {-sincos[0], sincos[1]}};
3792 p_chart_uv_transform(chart, mat);
3793 }
3794}
3795
3797{
3798 arena = BLI_memarena_new(MEM_SIZE_OPTIMAL(1 << 16), "param construct arena");
3799 polyfill_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "param polyfill arena");
3801
3803
3804 hash_verts = phash_new(reinterpret_cast<PHashLink **>(&construction_chart->verts), 1);
3805 hash_edges = phash_new(reinterpret_cast<PHashLink **>(&construction_chart->edges), 1);
3806 hash_faces = phash_new(reinterpret_cast<PHashLink **>(&construction_chart->faces), 1);
3807}
3808
3810{
3812 arena = nullptr;
3814 polyfill_arena = nullptr;
3815 BLI_heap_free(polyfill_heap, nullptr);
3816 polyfill_heap = nullptr;
3817
3818 MEM_SAFE_DELETE(construction_chart);
3819
3823
3824 if (pin_hash) {
3825 BLI_ghash_free(pin_hash, nullptr, nullptr);
3826 pin_hash = nullptr;
3827 }
3828
3829 for (int i = 0; i < ncharts; i++) {
3830 MEM_SAFE_DELETE(charts[i]->orig_bounds);
3831 MEM_SAFE_DELETE(charts[i]);
3832 }
3833 MEM_SAFE_DELETE(charts);
3834
3835 if (rng) {
3837 rng = nullptr;
3838 }
3839}
3840
3841void uv_parametrizer_aspect_ratio(ParamHandle *phandle, const float aspect_y)
3842{
3843 BLI_assert(aspect_y > 0.0f);
3844 phandle->aspect_y = aspect_y;
3845}
3846
3852
3853ParamKey uv_find_pin_index(ParamHandle *handle, const int bmvertindex, const float uv[2])
3854{
3855 if (!handle->pin_hash) {
3856 return bmvertindex; /* No verts pinned. */
3857 }
3858
3859 const GeoUVPinIndex *pinuvlist = static_cast<const GeoUVPinIndex *>(
3860 BLI_ghash_lookup(handle->pin_hash, POINTER_FROM_INT(bmvertindex)));
3861 if (!pinuvlist) {
3862 return bmvertindex; /* Vert not pinned. */
3863 }
3864
3865 /* At least one of the UVs associated with bmvertindex is pinned. Find the best one. */
3866 float bestdistsquared = len_squared_v2v2(pinuvlist->uv, uv);
3867 ParamKey bestkey = pinuvlist->reindex;
3868 pinuvlist = pinuvlist->next;
3869 while (pinuvlist) {
3870 const float distsquared = len_squared_v2v2(pinuvlist->uv, uv);
3871 if (bestdistsquared > distsquared) {
3872 bestdistsquared = distsquared;
3873 bestkey = pinuvlist->reindex;
3874 }
3875 pinuvlist = pinuvlist->next;
3876 }
3877 return bestkey;
3878}
3879
3880static GeoUVPinIndex *new_geo_uv_pinindex(ParamHandle *handle, const float uv[2])
3881{
3882 GeoUVPinIndex *pinuv = static_cast<GeoUVPinIndex *>(
3883 BLI_memarena_alloc(handle->arena, sizeof(*pinuv)));
3884 pinuv->next = nullptr;
3885 copy_v2_v2(pinuv->uv, uv);
3886 pinuv->reindex = PARAM_KEY_MAX - (handle->unique_pin_count++);
3887 return pinuv;
3888}
3889
3890void uv_prepare_pin_index(ParamHandle *handle, const int bmvertindex, const float uv[2])
3891{
3892 if (!handle->pin_hash) {
3893 handle->pin_hash = BLI_ghash_int_new("uv pin reindex");
3894 }
3895
3896 GeoUVPinIndex *pinuvlist = static_cast<GeoUVPinIndex *>(
3897 BLI_ghash_lookup(handle->pin_hash, POINTER_FROM_INT(bmvertindex)));
3898 if (!pinuvlist) {
3900 handle->pin_hash, POINTER_FROM_INT(bmvertindex), new_geo_uv_pinindex(handle, uv));
3901 return;
3902 }
3903
3904 while (true) {
3905 if (equals_v2v2(pinuvlist->uv, uv)) {
3906 return;
3907 }
3908 if (!pinuvlist->next) {
3909 pinuvlist->next = new_geo_uv_pinindex(handle, uv);
3910 return;
3911 }
3912 pinuvlist = pinuvlist->next;
3913 }
3914}
3915
3916static void p_add_ngon(ParamHandle *handle,
3917 const ParamKey key,
3918 const int nverts,
3919 const ParamKey *vkeys,
3920 const float **co,
3921 float **uv, /* Output will eventually be written to `uv`. */
3922 const float *weight,
3923 const bool *pin,
3924 const bool *select)
3925{
3926 uint(*tris)[3];
3927 uint nfilltri = nverts - 2;
3928
3929 p_polygon_calc_tris(handle, co, &tris, nverts);
3930
3931 /* Add triangles. */
3932 for (uint j = 0; j < nfilltri; j++) {
3933 uint *tri = tris[j];
3934 uint v0 = tri[0];
3935 uint v1 = tri[1];
3936 uint v2 = tri[2];
3937
3938 const ParamKey tri_vkeys[3] = {vkeys[v0], vkeys[v1], vkeys[v2]};
3939 const float *tri_co[3] = {co[v0], co[v1], co[v2]};
3940 float *tri_uv[3] = {uv[v0], uv[v1], uv[v2]};
3941
3942 const float *tri_weight = nullptr;
3943 float tri_weight_tmp[3];
3944
3945 if (weight) {
3946 tri_weight_tmp[0] = weight[v0];
3947 tri_weight_tmp[1] = weight[v1];
3948 tri_weight_tmp[2] = weight[v2];
3949 tri_weight = tri_weight_tmp;
3950 };
3951
3952 const bool tri_pin[3] = {pin[v0], pin[v1], pin[v2]};
3953 const bool tri_select[3] = {select[v0], select[v1], select[v2]};
3954
3956 handle, key, 3, tri_vkeys, tri_co, tri_uv, tri_weight, tri_pin, tri_select);
3957 }
3958
3960}
3961
3963 const ParamKey key,
3964 const int nverts,
3965 const ParamKey *vkeys,
3966 const float **co,
3967 float **uv,
3968 const float *weight,
3969 const bool *pin,
3970 const bool *select)
3971{
3972 BLI_assert(nverts >= 3);
3974
3975 if (nverts > 3) {
3976 /* Protect against (manifold) geometry which has a non-manifold triangulation.
3977 * See #102543. */
3978
3980 permute.reserve(nverts);
3981 for (int i = 0; i < nverts; i++) {
3982 permute.append_unchecked(i);
3983 }
3984
3985 for (int i = nverts - 1; i >= 0;) {
3986 /* Just check the "ears" of the n-gon.
3987 * For quads, this is sufficient.
3988 * For pentagons and higher, we might miss internal duplicate triangles, but note
3989 * that such cases are rare if the source geometry is manifold and non-intersecting. */
3990 const int pm = int(permute.size());
3991 BLI_assert(pm > 3);
3992 int i0 = permute[i];
3993 int i1 = permute[(i + 1) % pm];
3994 int i2 = permute[(i + 2) % pm];
3995 if (!p_face_exists(phandle, vkeys, i0, i1, i2)) {
3996 i--; /* All good. */
3997 continue;
3998 }
3999
4000 /* An existing triangle has already been inserted.
4001 * As a heuristic, attempt to add the *previous* triangle.
4002 * NOTE: Should probably call `uv_parametrizer_face_add`
4003 * instead of `p_face_add_construct`. */
4004 int iprev = permute[(i + pm - 1) % pm];
4005 p_face_add_construct(phandle, key, vkeys, co, uv, weight, iprev, i0, i1, pin, select);
4006
4007 permute.remove(i);
4008 if (permute.size() == 3) {
4009 break;
4010 }
4011 i--;
4012 }
4013 if (permute.size() != nverts) {
4014 const int pm = int(permute.size());
4015 /* Add the remaining `pm-gon` data. */
4016 Array<ParamKey> vkeys_sub(pm);
4017 Array<const float *> co_sub(pm);
4018 Array<float *> uv_sub(pm);
4019 Array<float> weight_sub(weight ? pm : 0);
4020 Array<bool> pin_sub(pm);
4021 Array<bool> select_sub(pm);
4022 for (int i = 0; i < pm; i++) {
4023 int j = permute[i];
4024 vkeys_sub[i] = vkeys[j];
4025 co_sub[i] = co[j];
4026 uv_sub[i] = uv[j];
4027 if (weight) {
4028 weight_sub[i] = weight[j];
4029 }
4030 pin_sub[i] = pin && pin[j];
4031 select_sub[i] = select && select[j];
4032 }
4033 p_add_ngon(phandle,
4034 key,
4035 pm,
4036 &vkeys_sub.first(),
4037 &co_sub.first(),
4038 &uv_sub.first(),
4039 weight ? &weight_sub.first() : nullptr,
4040 &pin_sub.first(),
4041 &select_sub.first());
4042 return; /* Nothing more to do. */
4043 }
4044 /* No "ears" have previously been inserted. Continue as normal. */
4045 }
4046 if (nverts > 3) {
4047 /* ngon */
4048 p_add_ngon(phandle, key, nverts, vkeys, co, uv, weight, pin, select);
4049 }
4050 else if (!p_face_exists(phandle, vkeys, 0, 1, 2)) {
4051 /* triangle */
4052 p_face_add_construct(phandle, key, vkeys, co, uv, weight, 0, 1, 2, pin, select);
4053 }
4054}
4055
4057{
4059
4060 PEdge *e = p_edge_lookup(phandle, vkeys);
4061 if (e) {
4062 e->flag |= PEDGE_SEAM;
4063 }
4064}
4065
4067 bool fill_holes,
4068 bool topology_from_uvs,
4069 int *r_count_failed)
4070{
4071 int i, j;
4072
4074
4075 phandle->ncharts = p_connect_pairs(phandle, topology_from_uvs);
4076 phandle->charts = p_split_charts(phandle, phandle->construction_chart, phandle->ncharts);
4077
4078 MEM_delete(phandle->construction_chart);
4079 phandle->construction_chart = nullptr;
4080
4081 phash_safe_delete(&phandle->hash_verts);
4082 phash_safe_delete(&phandle->hash_edges);
4083 phash_safe_delete(&phandle->hash_faces);
4084
4085 for (i = j = 0; i < phandle->ncharts; i++) {
4086 PChart *chart = phandle->charts[i];
4087
4088 PEdge *outer;
4089 p_chart_boundaries(chart, &outer);
4090
4091 if (!topology_from_uvs && chart->nboundaries == 0) {
4092 MEM_delete(chart);
4093 if (r_count_failed) {
4094 *r_count_failed += 1;
4095 }
4096 continue;
4097 }
4098
4099 phandle->charts[j++] = chart;
4100
4101 if (fill_holes && chart->nboundaries > 1) {
4102 p_chart_fill_boundaries(phandle, chart, outer);
4103 }
4104
4105 for (PVert *v = chart->verts; v; v = v->nextlink) {
4106 p_vert_load_pin_select_uvs(phandle, v);
4107 }
4108 }
4109
4110 phandle->ncharts = j;
4111
4113}
4114
4116 bool live,
4117 bool abf,
4118 const bool use_original_bounds)
4119{
4121 phandle->state = PHANDLE_STATE_LSCM;
4122
4123 for (int i = 0; i < phandle->ncharts; i++) {
4124 for (PFace *f = phandle->charts[i]->faces; f; f = f->nextlink) {
4126 }
4127 p_chart_lscm_begin(phandle->charts[i], live, abf, use_original_bounds);
4128 }
4129}
4130
4131void uv_parametrizer_lscm_solve(ParamHandle *phandle, int *count_changed, int *count_failed)
4132{
4133 BLI_assert(phandle->state == PHANDLE_STATE_LSCM);
4134
4135 for (int i = 0; i < phandle->ncharts; i++) {
4136 PChart *chart = phandle->charts[i];
4137
4138 if (!chart->context) {
4139 continue;
4140 }
4141 const bool result = p_chart_lscm_solve(phandle, chart);
4142
4143 if (result && !chart->has_pins) {
4144 /* Every call to LSCM will eventually call uv_pack, so rotating here might be redundant. */
4146 }
4147 else if (result && chart->single_pin) {
4150 }
4151
4152 if (!result || !chart->has_pins) {
4153 p_chart_lscm_end(chart);
4154 }
4155
4156 if (result) {
4157 if (count_changed != nullptr) {
4158 *count_changed += 1;
4159 }
4160 }
4161 else {
4162 if (count_failed != nullptr) {
4163 *count_failed += 1;
4164 }
4165 }
4166 }
4167}
4168
4170{
4171 BLI_assert(phandle->state == PHANDLE_STATE_LSCM);
4172
4173 for (int i = 0; i < phandle->ncharts; i++) {
4174 p_chart_lscm_end(phandle->charts[i]);
4175#if 0
4176 p_chart_complexify(phandle->charts[i]);
4177#endif
4178 }
4179
4181}
4182
4184{
4186 phandle->state = PHANDLE_STATE_STRETCH;
4187
4188 phandle->rng = BLI_rng_new(31415926);
4189 phandle->blend = 0.0f;
4190
4191 for (int i = 0; i < phandle->ncharts; i++) {
4192 PChart *chart = phandle->charts[i];
4193
4194 for (PVert *v = chart->verts; v; v = v->nextlink) {
4195 v->flag &= ~PVERT_PIN; /* don't use user-defined pins */
4196 }
4197
4199
4200 for (PFace *f = chart->faces; f; f = f->nextlink) {
4202 f->u.area3d = p_face_area(f);
4203 }
4204 }
4205}
4206
4208{
4210 phandle->blend = blend;
4211}
4212
4214{
4216 for (int i = 0; i < phandle->ncharts; i++) {
4217 p_chart_stretch_minimize(phandle->charts[i], phandle->rng);
4218 }
4219}
4220
4226
4228{
4229 if (handle->ncharts == 0) {
4230 return;
4231 }
4232
4233 uv_parametrizer_scale_x(handle, 1.0f / handle->aspect_y);
4234
4235 Vector<PackIsland *> pack_island_vector;
4236
4237 for (int i = 0; i < handle->ncharts; i++) {
4238 PChart *chart = handle->charts[i];
4239 if (params.pin_method == ED_UVPACK_PIN_NONE && chart->has_pins) {
4240 continue;
4241 }
4242
4243 geometry::PackIsland *pack_island = new geometry::PackIsland();
4244 pack_island->caller_index = i;
4245 pack_island->aspect_y = handle->aspect_y;
4246 pack_island->pinned = chart->has_pins;
4247
4248 for (PFace *f = chart->faces; f; f = f->nextlink) {
4249 PVert *v0 = f->edge->vert;
4250 PVert *v1 = f->edge->next->vert;
4251 PVert *v2 = f->edge->next->next->vert;
4252 pack_island->add_triangle(v0->uv, v1->uv, v2->uv);
4253 }
4254
4255 pack_island_vector.append(pack_island);
4256 }
4257
4258 const float scale = pack_islands(pack_island_vector, params);
4259
4260 for (const int64_t i : pack_island_vector.index_range()) {
4261 PackIsland *pack_island = pack_island_vector[i];
4262 const float island_scale = pack_island->can_scale_(params) ? scale : 1.0f;
4263 PChart *chart = handle->charts[pack_island->caller_index];
4264
4265 float matrix[2][2];
4266 pack_island->build_transformation(island_scale, pack_island->angle, matrix);
4267 for (PVert *v = chart->verts; v; v = v->nextlink) {
4268 geometry::mul_v2_m2_add_v2v2(v->uv, matrix, v->uv, pack_island->pre_translate);
4269 }
4271
4272 pack_island_vector[i] = nullptr;
4273 delete pack_island;
4274 }
4275
4276 uv_parametrizer_scale_x(handle, handle->aspect_y);
4277}
4278
4280{
4281 /* Already in aspect-corrected space (necessary for rotation). */
4282 float trans[2], minv[2], maxv[2], new_size[2];
4283 for (int index = 0; index < phandle->ncharts; index++) {
4284
4285 PChart *chart = phandle->charts[index];
4286 bool all_verts_selected = true;
4287 for (PVert *v = chart->verts; v; v = v->nextlink) {
4288 if (!(v->flag & PVERT_SELECT)) {
4289 all_verts_selected = false;
4290 break;
4291 }
4292 }
4293 if (!all_verts_selected) {
4294 continue;
4295 }
4296 /* Allocated when unwrapping with `use_original_bounds`. */
4297 BLI_assert(chart->orig_bounds != nullptr);
4298 float new_angle = p_chart_minimum_area_angle(chart);
4299 p_chart_uv_rotate(chart, chart->orig_bounds->angle - new_angle);
4300
4301 p_chart_uv_bbox(chart, minv, maxv);
4302 sub_v2_v2v2(new_size, maxv, minv);
4303 const float2 orig_size = chart->orig_bounds->bounds.size();
4304 const float size = std::max(orig_size.x, orig_size.y);
4305 float scale = safe_divide(size, std::max(new_size[0], new_size[1]));
4306 p_chart_uv_scale(chart, scale);
4307 p_chart_uv_bbox(chart, minv, maxv);
4308
4309 mid_v2_v2v2(trans, minv, maxv);
4310 sub_v2_v2v2(trans, chart->orig_bounds->bounds.center(), trans);
4311 p_chart_uv_translate(chart, trans);
4312 }
4313}
4314
4315void uv_parametrizer_average(ParamHandle *phandle, bool ignore_pinned, bool scale_uv, bool shear)
4316{
4317 int i;
4318 float tot_area_3d = 0.0f;
4319 float tot_area_uv = 0.0f;
4320 float minv[2], maxv[2], trans[2];
4321
4322 if (phandle->ncharts == 0) {
4323 return;
4324 }
4325
4326 for (i = 0; i < phandle->ncharts; i++) {
4327 PChart *chart = phandle->charts[i];
4328
4329 if (ignore_pinned && chart->has_pins) {
4330 continue;
4331 }
4332
4333 /* Store original bounding box midpoint. */
4334 p_chart_uv_bbox(chart, minv, maxv);
4335 mid_v2_v2v2(chart->origin, minv, maxv);
4336
4337 if (scale_uv || shear) {
4338 /* It's possible that for some "bad" inputs, the following iteration will converge slowly or
4339 * perhaps even diverge. Rather than infinite loop, we only iterate a maximum of `max_iter`
4340 * times. (Also useful when making changes to the calculation.) */
4341 int max_iter = 10;
4342 for (int j = 0; j < max_iter; j++) {
4343 /* An island could contain millions of polygons. When summing many small values, we need to
4344 * use double precision in the accumulator to maintain accuracy. Note that the individual
4345 * calculations only need to be at single precision. */
4346 double scale_cou = 0;
4347 double scale_cov = 0;
4348 double scale_cross = 0;
4349 double weight_sum = 0;
4350 for (PFace *f = chart->faces; f; f = f->nextlink) {
4351 float m[2][2], s[2][2];
4352 PVert *va = f->edge->vert;
4353 PVert *vb = f->edge->next->vert;
4354 PVert *vc = f->edge->next->next->vert;
4355 s[0][0] = va->uv[0] - vc->uv[0];
4356 s[0][1] = va->uv[1] - vc->uv[1];
4357 s[1][0] = vb->uv[0] - vc->uv[0];
4358 s[1][1] = vb->uv[1] - vc->uv[1];
4359 /* Find the "U" axis and "V" axis in triangle coordinates. Normally this would require
4360 * SVD, but in 2D we can use a cheaper matrix inversion instead. */
4361 if (!invert_m2_m2(m, s)) {
4362 continue;
4363 }
4364 float cou[3], cov[3]; /* i.e. Texture "U" and texture "V" in 3D co-ordinates. */
4365 for (int k = 0; k < 3; k++) {
4366 cou[k] = m[0][0] * (va->co[k] - vc->co[k]) + m[0][1] * (vb->co[k] - vc->co[k]);
4367 cov[k] = m[1][0] * (va->co[k] - vc->co[k]) + m[1][1] * (vb->co[k] - vc->co[k]);
4368 }
4369 const float weight = p_face_area(f);
4370 scale_cou += len_v3(cou) * weight;
4371 scale_cov += len_v3(cov) * weight;
4372 if (shear) {
4373 normalize_v3(cov);
4374 normalize_v3(cou);
4375
4376 /* Why is scale_cross called `cross` when we call `dot`? The next line calculates:
4377 * `scale_cross += length(cross(cross(cou, face_normal), cov))`
4378 * By construction, both `cou` and `cov` are orthogonal to the face normal.
4379 * By definition, the normal vector has unit length. */
4380 scale_cross += dot_v3v3(cou, cov) * weight;
4381 }
4382 weight_sum += weight;
4383 }
4384 if (scale_cou * scale_cov < 1e-10f) {
4385 break;
4386 }
4387 const float scale_factor_u = scale_uv ? sqrtf(scale_cou / scale_cov) : 1.0f;
4388
4389 /* Compute correction transform. */
4390 float t[2][2];
4391 t[0][0] = scale_factor_u;
4392 t[1][0] = clamp_f(float(scale_cross / weight_sum), -0.5f, 0.5f);
4393 t[0][1] = 0;
4394 t[1][1] = 1.0f / scale_factor_u;
4395
4396 /* Apply the correction. */
4397 p_chart_uv_transform(chart, t);
4398
4399 /* How far from the identity transform are we? [[1,0],[0,1]] */
4400 const float err = fabsf(t[0][0] - 1.0f) + fabsf(t[1][0]) + fabsf(t[0][1]) +
4401 fabsf(t[1][1] - 1.0f);
4402
4403 const float tolerance = 1e-6f; /* Trade accuracy for performance. */
4404 if (err < tolerance) {
4405 /* Too slow? Use Richardson Extrapolation to accelerate the convergence. */
4406 break;
4407 }
4408 }
4409 }
4410
4411 chart->area_3d = 0.0f;
4412 chart->area_uv = 0.0f;
4413
4414 for (PFace *f = chart->faces; f; f = f->nextlink) {
4415 chart->area_3d += p_face_area(f);
4416 chart->area_uv += fabsf(p_face_uv_area_signed(f));
4417 }
4418
4419 tot_area_3d += chart->area_3d;
4420 tot_area_uv += chart->area_uv;
4421 }
4422
4423 if (tot_area_3d == 0.0f || tot_area_uv == 0.0f) {
4424 /* Prevent divide by zero. */
4425 return;
4426 }
4427
4428 const float tot_fac = tot_area_3d / tot_area_uv;
4429
4430 for (i = 0; i < phandle->ncharts; i++) {
4431 PChart *chart = phandle->charts[i];
4432
4433 if (ignore_pinned && chart->has_pins) {
4434 continue;
4435 }
4436
4437 if (chart->area_3d != 0.0f && chart->area_uv != 0.0f) {
4438 const float fac = chart->area_3d / chart->area_uv;
4439
4440 /* Average scale. */
4441 p_chart_uv_scale(chart, sqrtf(fac / tot_fac));
4442
4443 /* Get the current island bounding box. */
4444 p_chart_uv_bbox(chart, minv, maxv);
4445
4446 /* Move back to original midpoint. */
4447 mid_v2_v2v2(trans, minv, maxv);
4448 sub_v2_v2v2(trans, chart->origin, trans);
4449
4450 p_chart_uv_translate(chart, trans);
4451 }
4452 }
4453}
4454
4456{
4457 for (int i = 0; i < phandle->ncharts; i++) {
4458 PChart *chart = phandle->charts[i];
4459 if (chart->skip_flush) {
4460 continue;
4461 }
4462
4463 p_flush_uvs(phandle, chart);
4464 }
4465}
4466
4468{
4469 for (int i = 0; i < phandle->ncharts; i++) {
4470 PChart *chart = phandle->charts[i];
4471 for (PFace *f = chart->faces; f; f = f->nextlink) {
4473 }
4474 }
4475}
4476
4477/* -------------------------------------------------------------------- */
4480
4481static bool p_collapse_doubles_allowed(PEdge *edge, PEdge *pair, float threshold_squared)
4482{
4483 PVert *oldv, *keepv;
4484
4485 p_collapsing_verts(edge, pair, &oldv, &keepv);
4486
4487 /* Do not collapse a pinned vertex unless the target vertex
4488 * is also pinned. */
4489 if ((oldv->flag & PVERT_PIN) && !(keepv->flag & PVERT_PIN)) {
4490 return false;
4491 }
4492
4493 if (!p_collapse_allowed_topologic(edge, pair)) {
4494 return false;
4495 }
4496
4497 PEdge *collapse_e = edge ? edge : pair;
4498 return p_edge_length_squared(collapse_e) < threshold_squared;
4499}
4500
4501static float p_collapse_doubles_cost(PEdge *edge, PEdge *pair)
4502{
4503 PEdge *collapse_e = edge ? edge : pair;
4504 return p_edge_length_squared(collapse_e);
4505}
4506
4507static void UNUSED_FUNCTION(p_chart_collapse_doubles)(PChart *chart, const float threshold)
4508{
4509 const float threshold_squared = threshold * threshold;
4510
4512 return p_collapse_doubles_allowed(e, pair, threshold_squared);
4513 });
4514}
4515
4517{
4518 PEdge *e, *pair, *edge;
4519 PVert *newv, *keepv;
4520
4521 for (e = chart->collapsed_edges; e; e = e->nextlink) {
4522 if (!(e->flag & PEDGE_COLLAPSE_EDGE)) {
4523 break;
4524 }
4525 edge = e;
4526 pair = e->pair;
4527 if (edge->flag & PEDGE_COLLAPSE_PAIR) {
4528 std::swap(edge, pair);
4529 }
4530 p_collapsing_verts(edge, pair, &newv, &keepv);
4531
4532 if (!(newv->flag & PVERT_PIN)) {
4533 newv->uv[0] = keepv->uv[0];
4534 newv->uv[1] = keepv->uv[1];
4535 }
4536 }
4537}
4538
4540 const float corr_co1[3],
4541 const float corr_co2[3],
4542 const float min_area,
4543 const float min_angle_cos)
4544{
4545 /* Check whether the given corrected coordinates don't result in any other triangle with area
4546 * lower than min_area. */
4547
4548 const PVert *corr_v = corr_e->vert;
4549 const PEdge *e = corr_v->edge;
4550
4551 do {
4552 float area;
4553
4554 if (e == corr_e) {
4555 continue;
4556 }
4557
4558 if (!(e->face->flag & PFACE_DONE)) {
4559 continue;
4560 }
4561
4562 if (e->next->next == corr_e->pair) {
4563 PVert *other_v = e->next->next->vert;
4564 area = area_tri_v3(corr_co1, corr_co2, other_v->co);
4565 }
4566 else {
4567 const PVert *other_v1 = e->next->vert;
4568 const PVert *other_v2 = e->next->next->vert;
4569 area = area_tri_v3(corr_co1, other_v1->co, other_v2->co);
4570 }
4571
4572 if (area < min_area) {
4573 return false;
4574 }
4575
4576 float f_cos[3];
4577
4578 if (e->next->next == corr_e->pair) {
4579 PVert *other_v = e->next->next->vert;
4580 p_triangle_cos(corr_co1, corr_co2, other_v->co, f_cos, f_cos + 1, f_cos + 2);
4581 }
4582 else {
4583 const PVert *other_v1 = e->next->vert;
4584 const PVert *other_v2 = e->next->next->vert;
4585 p_triangle_cos(corr_co1, other_v1->co, other_v2->co, f_cos, f_cos + 1, f_cos + 2);
4586 }
4587
4588 for (int i = 0; i < 3; i++) {
4589 if (f_cos[i] > min_angle_cos) {
4590 return false;
4591 }
4592 }
4593
4594 } while ((e = p_wheel_edge_next(e)) && (e != corr_v->edge));
4595
4596 return true;
4597}
4598
4599static bool p_validate_corrected_coords(const PEdge *corr_e,
4600 const float corr_co[3],
4601 float min_area,
4602 float min_angle_cos)
4603{
4604 /* Check whether the given corrected coordinates don't result in any other triangle with area
4605 * lower than min_area. */
4606
4607 const PVert *corr_v = corr_e->vert;
4608 const PEdge *e = corr_v->edge;
4609
4610 do {
4611 if (!(e->face->flag & PFACE_DONE) && (e != corr_e)) {
4612 continue;
4613 }
4614
4615 const PVert *other_v1 = e->next->vert;
4616 const PVert *other_v2 = e->next->next->vert;
4617
4618 const float area = area_tri_v3(corr_co, other_v1->co, other_v2->co);
4619
4620 if (area < min_area) {
4621 return false;
4622 }
4623
4624 float f_cos[3];
4625 p_triangle_cos(corr_co, other_v1->co, other_v2->co, f_cos, f_cos + 1, f_cos + 2);
4626
4627 for (int i = 0; i < 3; i++) {
4628 if (f_cos[i] > min_angle_cos) {
4629 return false;
4630 }
4631 }
4632
4633 } while ((e = p_wheel_edge_next(e)) && (e != corr_v->edge));
4634
4635 return true;
4636}
4637
4638static bool p_edge_matrix(float R[3][3], const float edge_dir[3])
4639{
4640 static const constexpr float eps = 1.0e-5;
4641 static const constexpr float n1[3] = {0.0f, 0.0f, 1.0f};
4642 static const constexpr float n2[3] = {0.0f, 1.0f, 0.0f};
4643
4644 float edge_len = len_v3(edge_dir);
4645 if (edge_len < eps) {
4646 return false;
4647 }
4648
4649 float edge_dir_norm[3];
4650 copy_v3_v3(edge_dir_norm, edge_dir);
4651 mul_v3_fl(edge_dir_norm, 1.0f / edge_len);
4652
4653 float normal_dir[3];
4654 cross_v3_v3v3(normal_dir, edge_dir_norm, n1);
4655 float normal_len = len_v3(normal_dir);
4656
4657 if (normal_len < eps) {
4658 cross_v3_v3v3(normal_dir, edge_dir_norm, n2);
4659 normal_len = len_v3(normal_dir);
4660
4661 if (normal_len < eps) {
4662 return false;
4663 }
4664 }
4665
4666 mul_v3_fl(normal_dir, 1.0f / normal_len);
4667
4668 float tangent_dir[3];
4669 cross_v3_v3v3(tangent_dir, edge_dir_norm, normal_dir);
4670
4671 R[0][0] = edge_dir_norm[0];
4672 R[1][0] = edge_dir_norm[1];
4673 R[2][0] = edge_dir_norm[2];
4674
4675 R[0][1] = normal_dir[0];
4676 R[1][1] = normal_dir[1];
4677 R[2][1] = normal_dir[2];
4678
4679 R[0][2] = tangent_dir[0];
4680 R[1][2] = tangent_dir[1];
4681 R[2][2] = tangent_dir[2];
4682
4683 return true;
4684}
4685
4686static bool p_edge_matrix(float R[3][3], const PEdge *e)
4687{
4688 float edge_dir[3];
4689 copy_v3_v3(edge_dir, e->next->vert->co);
4690 sub_v3_v3(edge_dir, e->vert->co);
4691
4692 return p_edge_matrix(R, edge_dir);
4693}
4694
4695static const float CORR_ZERO_AREA_EPS = 1.0e-10f;
4696
4698 float min_area,
4699 float min_angle_cos)
4700{
4701 static const float3 ref_edges[] = {
4702 {1.0f, 0.0f, 0.0f},
4703 {0.0f, 1.0f, 0.0f},
4704 {0.0f, 0.0f, 1.0f},
4705 {0.0f, 1.0f, 1.0f},
4706 {1.0f, 0.0f, 1.0f},
4707 {1.0f, 1.0f, 0.0f},
4708
4709 {0.0f, 0.5f, 1.0f},
4710 {0.5f, 0.0f, 1.0f},
4711 {0.5f, 1.0f, 0.0f},
4712
4713 {0.0f, 1.0f, 0.5f},
4714 {1.0f, 0.0f, 0.5f},
4715 {1.0f, 0.5f, 0.0f},
4716 };
4717 static const int ref_edge_count = ARRAY_SIZE(ref_edges);
4718 static const int LEN_MULTIPLIER_COUNT = 3;
4719 bool corr_co_found = false;
4720
4721 float corr_len = 2.0f * std::sqrt((min_area + CORR_ZERO_AREA_EPS) / 3.0f / std::sqrt(3.0f));
4722
4723 for (int m = 0; m < LEN_MULTIPLIER_COUNT; m++) {
4724 for (int re = 0; re < ref_edge_count; re++) {
4725 float M[3][3];
4726
4727 if (!p_edge_matrix(M, ref_edges[re])) {
4728 continue;
4729 }
4730
4731 float corr_co[3][3];
4732 PEdge *e = f->edge;
4733
4734 for (int i = 0; i < 3; i++) {
4735 const float angle = (float(i) / 3.0f) * float(2.0 * M_PI);
4736 float corr_dir[3] = {0.0f, cos(angle), sin(angle)};
4737
4738 float corr_len_multiplied = corr_len * (m + 1);
4739
4740 mul_m3_v3(M, corr_dir);
4741 mul_v3_fl(corr_dir, corr_len_multiplied);
4742
4743 copy_v3_v3(corr_co[i], e->vert->co);
4744 add_v3_v3(corr_co[i], corr_dir);
4745 e = e->next;
4746 }
4747
4748 e = f->edge;
4749 for (int i = 0; i < 3; i++) {
4751 e, corr_co[i], corr_co[(i + 1) % 3], min_area, min_angle_cos))
4752 {
4753 return false;
4754 }
4755
4756 e = e->next;
4757 }
4758
4759 e = f->edge;
4760 for (int i = 0; i < 3; i++) {
4761 copy_v3_v3(e->vert->co, corr_co[i]);
4762 e = e->next;
4763 }
4764
4765 corr_co_found = true;
4766 break;
4767 }
4768
4769 if (corr_co_found) {
4770 break;
4771 }
4772 }
4773
4774 if (!corr_co_found) {
4775 return false;
4776 }
4777
4778 f->flag |= PFACE_DONE;
4779 return true;
4780}
4781
4782static bool p_chart_correct_degenerate_triangles2(PChart *chart, float min_area, float min_angle)
4783{
4784 static const float eps = 1.0e-6;
4785
4786 float min_angle_cos = std::cos(min_angle);
4787 float min_angle_sin = std::sin(min_angle + CORR_ZERO_AREA_EPS);
4788
4789 for (PFace *f = chart->faces; f; f = f->nextlink) {
4790 if (f->flag & PFACE_DONE) {
4791 continue;
4792 }
4793
4794 float face_area = p_face_area(f);
4795
4796 PEdge *max_edge = nullptr;
4797 float max_edge_len = -std::numeric_limits<float>::infinity();
4798
4799 PEdge *min_edge = nullptr;
4800 float min_edge_len = std::numeric_limits<float>::infinity();
4801
4802 PEdge *middle_edge = nullptr;
4803
4804 PEdge *e = f->edge;
4805 do {
4806 float len = p_edge_length(e);
4807
4808 if (len > max_edge_len) {
4809 max_edge = e;
4810 max_edge_len = len;
4811
4812 middle_edge = max_edge->next == min_edge ? min_edge->next : max_edge->next;
4813 }
4814
4815 if (len < min_edge_len) {
4816 min_edge = e;
4817 min_edge_len = len;
4818
4819 middle_edge = min_edge->next == max_edge ? max_edge->next : min_edge->next;
4820 }
4821
4822 e = e->next;
4823 } while (e != f->edge);
4824
4825 BLI_assert(max_edge);
4826 BLI_assert(min_edge);
4827 BLI_assert(middle_edge);
4828
4829 bool small_uniside_tri = (face_area <= min_area) && (min_edge == max_edge);
4830
4831 if ((max_edge_len < eps) || small_uniside_tri) {
4832 p_chart_correct_degenerate_triangle_point(f, min_area, min_angle_cos);
4833 continue;
4834 }
4835
4836 if (min_edge == max_edge) {
4837 BLI_assert(face_area > min_area);
4838 f->flag |= PFACE_DONE;
4839 continue;
4840 }
4841
4842 BLI_assert(middle_edge != max_edge);
4843 BLI_assert(middle_edge != min_edge);
4844
4845 float M[3][3];
4846 if (!p_edge_matrix(M, max_edge)) {
4847 continue;
4848 }
4849
4850 float max_face_cos =
4851 middle_edge->next == max_edge ?
4852 p_vec_cos(middle_edge->vert->co, max_edge->vert->co, min_edge->vert->co) :
4853 p_vec_cos(max_edge->vert->co, middle_edge->vert->co, min_edge->vert->co);
4854
4855 float angle_corr_len = max_face_cos > min_angle_cos ?
4856 p_edge_length(middle_edge) * min_angle_sin :
4857 0.0f;
4858
4859 if ((face_area > min_area) && (angle_corr_len == 0.0f)) {
4860 f->flag |= PFACE_DONE;
4861 continue;
4862 }
4863
4864 float corr_len = (min_area + CORR_ZERO_AREA_EPS) * 2.0f / max_edge_len;
4865 corr_len = std::max(corr_len, angle_corr_len);
4866
4867 PEdge *corr_e = max_edge->next->next;
4868 PVert *corr_v = corr_e->vert;
4869
4870 /* Check 4 distinct directions. */
4871 static const constexpr int DIR_COUNT = 16;
4872 static const constexpr int LEN_MULTIPLIER_COUNT = 2;
4873 float corr_co[3];
4874 bool corr_co_found = false;
4875
4876 for (int m = 0; m < LEN_MULTIPLIER_COUNT; m++) {
4877 for (int d = 0; d < DIR_COUNT; d++) {
4878 const float angle = (float(d) / DIR_COUNT) * float(2.0 * M_PI);
4879 float corr_dir[3] = {0.0f, cos(angle), sin(angle)};
4880
4881 const float corr_len_multiplied = corr_len * (m + 1);
4882
4883 mul_m3_v3(M, corr_dir);
4884 mul_v3_fl(corr_dir, corr_len_multiplied);
4885
4886 copy_v3_v3(corr_co, corr_v->co);
4887 add_v3_v3(corr_co, corr_dir);
4888
4889 if (p_validate_corrected_coords(corr_e, corr_co, min_area, min_angle_cos)) {
4890 corr_co_found = true;
4891 break;
4892 }
4893 }
4894
4895 if (corr_co_found) {
4896 break;
4897 }
4898 }
4899
4900 if (!corr_co_found) {
4901 continue;
4902 }
4903
4904 f->flag |= PFACE_DONE;
4905 copy_v3_v3(corr_v->co, corr_co);
4906 }
4907
4908 return true;
4909}
4910
4911#ifndef NDEBUG
4912
4913static bool p_validate_triangle_angles(const PVert *vert1,
4914 const PVert *vert2,
4915 const PVert *vert3,
4916 const float min_angle_cos)
4917{
4918 float t_cos[3];
4919 p_triangle_cos(vert1->co, vert2->co, vert3->co, t_cos, t_cos + 1, t_cos + 2);
4920
4921 for (int i = 0; i < 3; i++) {
4922 if (t_cos[i] > min_angle_cos) {
4923 return false;
4924 }
4925 }
4926
4927 return true;
4928}
4929
4930#endif
4931
4933 const float min_area,
4934 const float min_angle)
4935{
4936 /* Look for degenerate triangles: triangles with angles lower than `min_angle` or having area
4937 * lower than `min_area` and try to correct vertex coordinates so that the resulting triangle is
4938 * not degenerate.
4939 *
4940 * The return value indicates whether all triangles could be corrected.
4941 */
4942
4943 bool ret = p_chart_correct_degenerate_triangles2(chart, min_area, min_angle);
4944
4945#ifndef NDEBUG
4946 float min_angle_cos = std::cos(min_angle - CORR_ZERO_AREA_EPS);
4947#endif
4948
4949 for (PFace *f = chart->faces; f; f = f->nextlink) {
4950 if (!(f->flag & PFACE_DONE)) {
4951 ret = false;
4952 }
4953 else {
4954#ifndef NDEBUG
4955 float f_area = p_face_area(f);
4956 BLI_assert(f_area > (min_area - CORR_ZERO_AREA_EPS));
4957
4958 PVert *vert1 = f->edge->vert;
4959 PVert *vert2 = f->edge->next->vert;
4960 PVert *vert3 = f->edge->next->next->vert;
4961
4962 BLI_assert(p_validate_triangle_angles(vert1, vert2, vert3, min_angle_cos));
4963#endif
4964 }
4965
4966 f->flag &= ~PFACE_DONE;
4967 }
4968
4969 return ret;
4970}
4971
4973
4974/* -------------------------------------------------------------------- */
4977
4978#ifdef WITH_UV_SLIM
4979
4983static slim::MatrixTransfer *slim_matrix_transfer(const ParamSlimOptions *slim_options)
4984{
4986
4987 mt->use_weights = slim_options->weight_influence > 0.0f;
4988 mt->weight_influence = slim_options->weight_influence;
4989 mt->n_iterations = slim_options->iterations;
4990 mt->reflection_mode = slim_options->no_flip;
4991 mt->skip_initialization = slim_options->skip_init;
4992
4993 return mt;
4994}
4995
5000static void slim_allocate_matrices(const PChart *chart, slim::MatrixTransferChart *mt_chart)
5001{
5002 mt_chart->verts_num = chart->nverts;
5003 mt_chart->faces_num = chart->nfaces;
5004 mt_chart->edges_num = chart->nedges;
5005
5006 mt_chart->v_matrices.resize(mt_chart->verts_num * 3);
5007 mt_chart->uv_matrices.resize(mt_chart->verts_num * 2);
5008 mt_chart->pp_matrices.resize(mt_chart->verts_num * 2);
5009
5010 mt_chart->f_matrices.resize(mt_chart->faces_num * 3);
5011 mt_chart->p_matrices.resize(mt_chart->verts_num);
5012 mt_chart->b_vectors.resize(mt_chart->verts_num);
5013 /* Also clear memory for weight vectors, hence 'new' followed by `()`. */
5014 mt_chart->w_vectors.resize(mt_chart->verts_num, 0.0);
5015
5016 mt_chart->e_matrices.resize(mt_chart->edges_num * 2 * 2);
5017 mt_chart->el_vectors.resize(mt_chart->edges_num * 2);
5018}
5019
5023static void slim_transfer_edges(PChart *chart, slim::MatrixTransferChart *mt_chart)
5024{
5025 std::vector<int> &E = mt_chart->e_matrices;
5026 std::vector<double> &EL = mt_chart->el_vectors;
5027
5028 PEdge *outer;
5029 p_chart_boundaries(chart, &outer);
5030
5031 PEdge *be = outer;
5032 int eid = 0;
5033
5034 static const float DOUBLED_VERT_THRESHOLD = 1.0e-5;
5035
5036 do {
5037 E[eid] = be->vert->slim_id;
5038 const float edge_len = p_edge_length(be);
5039 EL[eid] = edge_len;
5040
5041 /* Temporary solution : SLIM doesn't support doubled vertices for now. */
5042 if (edge_len < DOUBLED_VERT_THRESHOLD) {
5043 mt_chart->succeeded = false;
5044 }
5045
5046 be = p_boundary_edge_next(be);
5047 E[eid + mt_chart->edges_num + mt_chart->boundary_vertices_num] = be->vert->slim_id;
5048 eid++;
5049
5050 } while (be != outer);
5051
5052 for (PEdge *e = chart->edges; e; e = e->nextlink) {
5053 PEdge *e1 = e->next;
5054
5055 E[eid] = e->vert->slim_id;
5056 const float edge_len = p_edge_length(e);
5057 EL[eid] = edge_len;
5058
5059 /* Temporary solution : SLIM doesn't support doubled vertices for now. */
5060 if (edge_len < DOUBLED_VERT_THRESHOLD) {
5061 mt_chart->succeeded = false;
5062 }
5063
5064 E[eid + mt_chart->edges_num + mt_chart->boundary_vertices_num] = e1->vert->slim_id;
5065 eid++;
5066 }
5067}
5068
5072static void slim_transfer_vertices(const PChart *chart,
5073 slim::MatrixTransferChart *mt_chart,
5074 slim::MatrixTransfer *mt)
5075{
5076 int r = mt_chart->verts_num;
5077 std::vector<double> &v_mat = mt_chart->v_matrices;
5078 std::vector<double> &uv_mat = mt_chart->uv_matrices;
5079 std::vector<int> &p_mat = mt_chart->p_matrices;
5080 std::vector<double> &pp_mat = mt_chart->pp_matrices;
5081 std::vector<float> &w_vec = mt_chart->w_vectors;
5082
5083 int p_vid = 0;
5084 int vid = mt_chart->boundary_vertices_num;
5085
5086 /* For every vertex, fill up V matrix and P matrix (pinned vertices) */
5087 for (PVert *v = chart->verts; v; v = v->nextlink) {
5088 if (!v->on_boundary_flag) {
5089 if (mt->use_weights) {
5090 w_vec[vid] = v->weight;
5091 }
5092
5093 v->slim_id = vid;
5094 vid++;
5095 }
5096
5097 v_mat[v->slim_id] = v->co[0];
5098 v_mat[r + v->slim_id] = v->co[1];
5099 v_mat[2 * r + v->slim_id] = v->co[2];
5100
5101 uv_mat[v->slim_id] = v->uv[0];
5102 uv_mat[r + v->slim_id] = v->uv[1];
5103
5104 if (v->flag & PVERT_PIN || (mt->is_minimize_stretch && !(v->flag & PVERT_SELECT))) {
5105 mt_chart->pinned_vertices_num += 1;
5106
5107 p_mat[p_vid] = v->slim_id;
5108 pp_mat[2 * p_vid] = double(v->uv[0]);
5109 pp_mat[2 * p_vid + 1] = double(v->uv[1]);
5110 p_vid += 1;
5111 }
5112 }
5113}
5114
5118static void slim_transfer_boundary_vertices(PChart *chart,
5119 slim::MatrixTransferChart *mt_chart,
5120 const slim::MatrixTransfer *mt)
5121{
5122 std::vector<int> &b_vec = mt_chart->b_vectors;
5123 std::vector<float> &w_vec = mt_chart->w_vectors;
5124
5125 /* For every vertex, set slim_flag to 0 */
5126 for (PVert *v = chart->verts; v; v = v->nextlink) {
5127 v->on_boundary_flag = false;
5128 }
5129
5130 /* Find vertices on boundary and save into vector B */
5131 PEdge *outer;
5132 p_chart_boundaries(chart, &outer);
5133
5134 PEdge *be = outer;
5135 int vid = 0;
5136
5137 do {
5138 if (mt->use_weights) {
5139 w_vec[vid] = be->vert->weight;
5140 }
5141
5142 mt_chart->boundary_vertices_num += 1;
5143 be->vert->slim_id = vid;
5144 be->vert->on_boundary_flag = true;
5145 b_vec[vid] = vid;
5146
5147 vid += 1;
5148 be = p_boundary_edge_next(be);
5149
5150 } while (be != outer);
5151}
5152
5156static void slim_transfer_faces(const PChart *chart, slim::MatrixTransferChart *mt_chart)
5157{
5158 int fid = 0;
5159
5160 for (PFace *f = chart->faces; f; f = f->nextlink) {
5161 PEdge *e = f->edge;
5162 PEdge *e1 = e->next;
5163 PEdge *e2 = e1->next;
5164
5165 int r = mt_chart->faces_num;
5166 std::vector<int> &F = mt_chart->f_matrices;
5167
5168 F[fid] = e->vert->slim_id;
5169 F[r + fid] = e1->vert->slim_id;
5170 F[2 * r + fid] = e2->vert->slim_id;
5171 fid++;
5172 }
5173}
5174
5178static void slim_convert_blender(ParamHandle *phandle,
5179 slim::MatrixTransfer *mt,
5180 const bool use_original_bounds)
5181{
5182 static const float SLIM_CORR_MIN_AREA = 1.0e-8;
5183 static const float SLIM_CORR_MIN_ANGLE = DEG2RADF(1.0f);
5184
5185 mt->charts.resize(phandle->ncharts);
5186
5187 for (int i = 0; i < phandle->ncharts; i++) {
5188 PChart *chart = phandle->charts[i];
5189 if (use_original_bounds) {
5191 }
5192 slim::MatrixTransferChart *mt_chart = &mt->charts[i];
5193
5194 p_chart_correct_degenerate_triangles(chart, SLIM_CORR_MIN_AREA, SLIM_CORR_MIN_ANGLE);
5195
5196 mt_chart->succeeded = true;
5197 mt_chart->pinned_vertices_num = 0;
5198 mt_chart->boundary_vertices_num = 0;
5199
5200 /* Allocate memory for matrices of Vertices,Faces etc. for each chart. */
5201 slim_allocate_matrices(chart, mt_chart);
5202
5203 /* For each chart, fill up matrices. */
5204 slim_transfer_boundary_vertices(chart, mt_chart, mt);
5205 slim_transfer_vertices(chart, mt_chart, mt);
5206 slim_transfer_edges(chart, mt_chart);
5207 slim_transfer_faces(chart, mt_chart);
5208
5209 mt_chart->pp_matrices.resize(mt_chart->pinned_vertices_num * 2);
5210 mt_chart->pp_matrices.shrink_to_fit();
5211
5212 mt_chart->p_matrices.resize(mt_chart->pinned_vertices_num);
5213 mt_chart->p_matrices.shrink_to_fit();
5214
5215 mt_chart->b_vectors.resize(mt_chart->boundary_vertices_num);
5216 mt_chart->b_vectors.shrink_to_fit();
5217
5218 mt_chart->e_matrices.resize((mt_chart->edges_num + mt_chart->boundary_vertices_num) * 2);
5219 mt_chart->e_matrices.shrink_to_fit();
5220 }
5221}
5222
5223static void slim_transfer_data_to_slim(ParamHandle *phandle,
5224 const ParamSlimOptions *slim_options,
5225 const bool use_original_bounds)
5226{
5227 slim::MatrixTransfer *mt = slim_matrix_transfer(slim_options);
5228
5229 slim_convert_blender(phandle, mt, use_original_bounds);
5230 phandle->slim_mt = mt;
5231}
5232
5236static void slim_flush_uvs(ParamHandle *phandle,
5237 slim::MatrixTransfer *mt,
5238 int *count_changed,
5239 int *count_failed,
5240 bool live = false)
5241{
5242 int vid;
5243 PVert *v;
5244
5245 for (int i = 0; i < phandle->ncharts; i++) {
5246 PChart *chart = phandle->charts[i];
5247 slim::MatrixTransferChart *mt_chart = &mt->charts[i];
5248
5249 if (mt_chart->succeeded) {
5250 if (count_changed) {
5251 (*count_changed)++;
5252 }
5253
5254 const std::vector<double> &UV = mt_chart->uv_matrices;
5255 for (v = chart->verts; v; v = v->nextlink) {
5256 if (v->flag & PVERT_PIN) {
5257 continue;
5258 }
5259
5260 vid = v->slim_id;
5261 v->uv[0] = UV[vid];
5262 v->uv[1] = UV[mt_chart->verts_num + vid];
5263 }
5264 }
5265 else {
5266 if (count_failed) {
5267 (*count_failed)++;
5268 }
5269
5270 if (!live) {
5271 for (v = chart->verts; v; v = v->nextlink) {
5272 v->uv[0] = 0.0f;
5273 v->uv[1] = 0.0f;
5274 }
5275 }
5276 }
5277 }
5278}
5279
5283static void slim_free_matrix_transfer(ParamHandle *phandle)
5284{
5285 delete phandle->slim_mt;
5286 phandle->slim_mt = nullptr;
5287}
5288
5289static void slim_get_pinned_vertex_data(ParamHandle *phandle,
5290 PChart *chart,
5291 slim::MatrixTransferChart &mt_chart,
5292 slim::PinnedVertexData &pinned_vertex_data)
5293{
5294 std::vector<int> &pinned_vertex_indices = pinned_vertex_data.pinned_vertex_indices;
5295 std::vector<double> &pinned_vertex_positions_2D = pinned_vertex_data.pinned_vertex_positions_2D;
5296 std::vector<int> &selected_pins = pinned_vertex_data.selected_pins;
5297
5298 pinned_vertex_indices.clear();
5299 pinned_vertex_positions_2D.clear();
5300 selected_pins.clear();
5301
5302 /* Boundary vertices have lower slim_ids, process them first. */
5303 PEdge *outer;
5304 p_chart_boundaries(chart, &outer);
5305 PEdge *be = outer;
5306 do {
5307 if (be->vert->flag & PVERT_PIN) {
5308 /* Reload vertex position. */
5309 p_vert_load_pin_select_uvs(phandle, be->vert);
5310
5311 if (be->vert->flag & PVERT_SELECT) {
5312 selected_pins.push_back(be->vert->slim_id);
5313 }
5314
5315 pinned_vertex_indices.push_back(be->vert->slim_id);
5316 pinned_vertex_positions_2D.push_back(be->vert->uv[0]);
5317 pinned_vertex_positions_2D.push_back(be->vert->uv[1]);
5318 }
5319 be = p_boundary_edge_next(be);
5320 } while (be != outer);
5321
5322 PVert *v;
5323 for (v = chart->verts; v; v = v->nextlink) {
5324 if (!v->on_boundary_flag && (v->flag & PVERT_PIN)) {
5325 /* Reload `v`. */
5326 p_vert_load_pin_select_uvs(phandle, v);
5327
5328 if (v->flag & PVERT_SELECT) {
5329 selected_pins.push_back(v->slim_id);
5330 }
5331 pinned_vertex_indices.push_back(v->slim_id);
5332 pinned_vertex_positions_2D.push_back(v->uv[0]);
5333 pinned_vertex_positions_2D.push_back(v->uv[1]);
5334 }
5335 }
5336
5337 mt_chart.pinned_vertices_num = pinned_vertex_indices.size();
5338}
5339
5340#endif /* WITH_UV_SLIM */
5341
5343
5344/* -------------------------------------------------------------------- */
5347
5349 const ParamSlimOptions *slim_options,
5350 bool use_original_bounds,
5351 int *count_changed,
5352 int *count_failed)
5353{
5354#ifdef WITH_UV_SLIM
5355 slim_transfer_data_to_slim(phandle, slim_options, use_original_bounds);
5356 slim::MatrixTransfer *mt = phandle->slim_mt;
5357
5358 mt->parametrize();
5359
5360 slim_flush_uvs(phandle, mt, count_changed, count_failed);
5361 slim_free_matrix_transfer(phandle);
5362#else
5363 UNUSED_VARS(phandle, slim_options, use_original_bounds, count_changed, count_failed);
5364#endif /* !WITH_UV_SLIM */
5365}
5366
5368{
5369#ifdef WITH_UV_SLIM
5370 slim_transfer_data_to_slim(phandle, slim_options, false);
5371 slim::MatrixTransfer *mt = phandle->slim_mt;
5372
5373 for (int i = 0; i < phandle->ncharts; i++) {
5374 for (PFace *f = phandle->charts[i]->faces; f; f = f->nextlink) {
5376 }
5377 }
5378
5379 for (int i = 0; i < phandle->ncharts; i++) {
5380 PChart *chart = phandle->charts[i];
5381 slim::MatrixTransferChart &mt_chart = mt->charts[i];
5382
5383 bool select = false, deselect = false;
5384
5385 /* Give vertices matrix indices and count pins. */
5386 for (PVert *v = chart->verts; v; v = v->nextlink) {
5387 if (v->flag & PVERT_PIN) {
5388 if (v->flag & PVERT_SELECT) {
5389 select = true;
5390 }
5391 }
5392
5393 if (!(v->flag & PVERT_SELECT)) {
5394 deselect = true;
5395 }
5396 }
5397
5398 if (!select || !deselect) {
5399 chart->skip_flush = true;
5400 mt_chart.succeeded = false;
5401 continue;
5402 }
5403
5404 mt->setup_slim_data(mt_chart);
5405 }
5406#else
5407 UNUSED_VARS(phandle, slim_options);
5408#endif /* !WITH_UV_SLIM */
5409}
5410
5412{
5413#ifdef WITH_UV_SLIM
5414 slim::MatrixTransfer *mt = phandle->slim_mt;
5415
5416 /* Do one iteration and transfer UVs. */
5417 for (int i = 0; i < phandle->ncharts; i++) {
5418 mt->charts[i].parametrize_single_iteration();
5419 mt->charts[i].transfer_uvs_blended(blend);
5420 }
5421
5422 /* Assign new UVs back to each vertex. */
5423 slim_flush_uvs(phandle, mt, nullptr, nullptr);
5424#else
5425 UNUSED_VARS(phandle, blend);
5426#endif /* !WITH_UV_SLIM */
5427}
5428
5430{
5431#ifdef WITH_UV_SLIM
5432 slim::MatrixTransfer *mt = phandle->slim_mt;
5433
5434 /* Do one iteration and transfer UVs */
5435 for (int i = 0; i < phandle->ncharts; i++) {
5436 PChart *chart = phandle->charts[i];
5437 slim::MatrixTransferChart &mt_chart = mt->charts[i];
5438
5439 if (!mt_chart.data) {
5440 continue;
5441 }
5442
5443 slim_get_pinned_vertex_data(phandle, chart, mt_chart, mt->pinned_vertex_data);
5444
5445 mt->parametrize_live(mt_chart, mt->pinned_vertex_data);
5446 }
5447
5448 /* Assign new UVs back to each vertex. */
5449 const bool live = true;
5450 slim_flush_uvs(phandle, mt, nullptr, nullptr, live);
5451#else
5452 UNUSED_VARS(phandle);
5453#endif /* !WITH_UV_SLIM */
5454}
5455
5457{
5458#ifdef WITH_UV_SLIM
5459 slim::MatrixTransfer *mt = phandle->slim_mt;
5460
5461 for (int i = 0; i < phandle->ncharts; i++) {
5462 slim::MatrixTransferChart *mt_chart = &mt->charts[i];
5463 mt_chart->free_slim_data();
5464 }
5465
5466 slim_free_matrix_transfer(phandle);
5467#else
5468 UNUSED_VARS(phandle);
5469#endif /* WITH_UV_SLIM */
5470}
5471
5473{
5474#ifdef WITH_UV_SLIM
5475 return phandle->slim_mt != nullptr;
5476#else
5477 UNUSED_VARS(phandle);
5478 return false;
5479#endif
5480}
5481
5483
5484} // namespace blender::geometry
#define DEG2RAD(_deg)
#define DEG2RADF(_deg)
#define M_PI_2
#define M_PI
#define M_PI_4
#define BLI_MEMARENA_STD_BUFSIZE
#define BLI_POLYFILL_ALLOC_NGON_RESERVE
Random number functions.
#define PARAM_KEY_MAX
#define INIT_MINMAX2(min, max)
#define UNUSED_FUNCTION(x)
#define UNUSED_VARS(...)
#define POINTER_FROM_INT(i)
#define SHIFT3(type, a, b, c)
#define ELEM(...)
#define MEM_SIZE_OPTIMAL(size)
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
SIMD_FORCE_INLINE btScalar norm() const
Return the norm (length) of the vector.
Definition btVector3.h:263
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
int64_t size() const
Definition BLI_array.hh:267
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
const T * data() const
Definition BLI_array.hh:323
const T & first() const
Definition BLI_array.hh:292
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr void copy_from(Span< T > values) const
Definition BLI_span.hh:745
int64_t size() const
void append(const T &value)
void remove(const int64_t index)
IndexRange index_range() const
void append_unchecked(const T &value)
void reserve(const int64_t min_capacity)
bool can_scale_(const UVPackIsland_Params &params) const
Definition uv_pack.cc:2461
void build_transformation(float scale, double angle, float r_matrix[2][2]) const
Definition uv_pack.cc:2384
void add_triangle(float2 uv0, float2 uv1, float2 uv2)
Definition uv_pack.cc:140
eUVPackIsland_PinMethod pin_method
#define INT_MAX
#define sin
#define cos
float3x3 scale(float3x3 mat, float2 scale)
LinearSolver * EIG_linear_solver_new(int num_rows, int num_columns, int num_right_hand_sides)
void EIG_linear_solver_variable_set(LinearSolver *solver, int rhs, int index, double value)
void EIG_linear_solver_right_hand_side_add(LinearSolver *solver, int rhs, int index, double value)
LinearSolver * EIG_linear_least_squares_solver_new(int num_rows, int num_columns, int num_right_hand_sides)
void EIG_linear_solver_delete(LinearSolver *solver)
double EIG_linear_solver_variable_get(LinearSolver *solver, int rhs, int index)
void EIG_linear_solver_matrix_add(LinearSolver *solver, int row, int col, double value)
bool EIG_linear_solver_solve(LinearSolver *solver)
void EIG_linear_solver_variable_lock(LinearSolver *solver, int index)
ccl_device_inline float beta(const float x, const float y)
Definition math_base.h:708
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
ccl_device_inline void sincos(const float3 x, ccl_private float3 *sine, ccl_private float3 *cosine)
#define M
#define T
#define F
#define R
#define L
int size(const AssetLibraryReference *library_reference)
static void p_chart_rotate_minimum_area(PChart *chart)
bool uv_parametrizer_is_slim(const ParamHandle *phandle)
static PVert * p_vert_add(ParamHandle *handle, PHashKey key, const float co[3], const float weight, PEdge *e)
static PFace * p_face_add_construct(ParamHandle *handle, ParamKey key, const ParamKey *vkeys, const float **co, float **uv, const float *weight, int i1, int i2, int i3, const bool *pin, const bool *select)
void uv_parametrizer_construct_end(ParamHandle *phandle, bool fill_holes, bool topology_from_uvs, int *r_count_failed=nullptr)
static bool p_validate_corrected_coords(const PEdge *corr_e, const float corr_co[3], float min_area, float min_angle_cos)
static void p_chart_fill_boundaries(ParamHandle *handle, PChart *chart, const PEdge *outer)
static PFace * p_face_add_fill(ParamHandle *handle, PChart *chart, PVert *v1, PVert *v2, PVert *v3)
void uv_parametrizer_edge_set_seam(ParamHandle *phandle, const ParamKey *vkeys)
static void p_vert_load_pin_select_uvs(ParamHandle *handle, PVert *v)
static bool p_chart_lscm_solve(ParamHandle *handle, PChart *chart)
static void p_face_angles(PFace *f, double *r_a1, double *r_a2, double *r_a3)
static bool p_intersect_line_2d_dir(const float v1[2], const float dir1[2], const float v2[2], const float dir2[2], float r_isect[2])
void uv_parametrizer_average(ParamHandle *handle, bool ignore_pinned, bool scale_uv, bool shear)
static float p_chart_uv_area(PChart *chart)
void uv_parametrizer_flush(ParamHandle *handle)
static PHash * phash_new(PHashLink **list, int sizehint)
static bool UNUSED_FUNCTION_NO_SLIM p_chart_correct_degenerate_triangles(PChart *chart, const float min_area, const float min_angle)
void uv_parametrizer_lscm_begin(ParamHandle *handle, bool live, bool abf, bool use_original_bounds)
static void p_face_backup_uvs(PFace *f)
static void p_abf_adjust_alpha(PAbfSystem *sys, const int id, const float dlambda1, const float pre)
static void p_chart_rotate_fit_aabb(PChart *chart)
static void p_flush_uvs(ParamHandle *handle, PChart *chart)
void uv_parametrizer_slim_live_begin(ParamHandle *phandle, const ParamSlimOptions *slim_options)
static void p_collapse_cost_vertex(PVert *vert, float *r_mincost, PEdge **r_mine, const std::function< float(PEdge *, PEdge *)> &collapse_cost_fn, const std::function< float(PEdge *, PEdge *)> &collapse_allowed_fn)
static float p_rectangle_area(float *p1, float *dir, float *p2, float *p3, float *p4)
void uv_parametrizer_slim_stretch_iteration(ParamHandle *phandle, float blend)
static float p_collapse_doubles_cost(PEdge *edge, PEdge *pair)
static bool p_collapse_allowed_topologic(PEdge *edge, PEdge *pair)
static void phash_safe_delete(PHash **pph)
static bool p_chart_symmetry_pins(PChart *chart, PEdge *outer, PVert **pin1, PVert **pin2)
static bool p_chart_convex_hull(PChart *chart, PVert ***r_verts, int *r_nverts, int *r_right)
static float p_vec_cos(const float v1[3], const float v2[3], const float v3[3])
void uv_parametrizer_slim_live_solve_iteration(ParamHandle *phandle)
static void p_chart_stretch_minimize(PChart *chart, RNG *rng)
static PEdge * p_edge_lookup(ParamHandle *handle, const PHashKey *vkeys)
static float p_face_stretch(PFace *f)
ParamKey uv_find_pin_index(ParamHandle *handle, const int bmvertindex, const float uv[2])
static void p_split_vert(ParamHandle *handle, PChart *chart, PEdge *e)
static PEdge * p_wheel_edge_prev(PEdge *e)
static void p_collapsing_verts(PEdge *edge, PEdge *pair, PVert **r_newv, PVert **r_keepv)
static constexpr int P_NGON_STACK_NUM
static void p_stretch_pin_boundary(PChart *chart)
static float p_chart_minimum_area_angle(PChart *chart)
static bool p_abf_matrix_invert(PAbfSystem *sys, PChart *chart)
static int phash_size(PHash *ph)
static bool p_chart_correct_degenerate_triangle_point(PFace *f, float min_area, float min_angle_cos)
static float p_edge_length(PEdge *e)
void uv_prepare_pin_index(ParamHandle *handle, const int bmvertindex, const float uv[2])
static void p_face_restore_uvs(PFace *f)
static PEdge * p_wheel_edge_next(PEdge *e)
void uv_parametrizer_slim_live_end(ParamHandle *phandle)
static void p_chart_lscm_end(PChart *chart)
static void UNUSED_FUNCTION p_chart_collapse_doubles(PChart *chart, const float threshold)
static int PHashSizes[]
static void p_abf_setup_system(PAbfSystem *sys)
static const float CORR_ZERO_AREA_EPS
static void p_abf_compute_sines(PAbfSystem *sys)
static int p_compare_geometric_uv(const void *a, const void *b)
static void p_chart_pin_positions(PChart *chart, PVert **pin1, PVert **pin2)
static float p_edge_length_squared(PEdge *e)
void uv_parametrizer_stretch_blend(ParamHandle *handle, float blend)
static void p_chart_uv_bbox(PChart *chart, float minv[2], float maxv[2])
static bool p_edge_matrix(float R[3][3], const float edge_dir[3])
static bool p_edge_connect_pair(ParamHandle *handle, PEdge *e, bool topology_from_uvs, PEdge ***stack)
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 void p_chart_post_collapse_flush(PChart *chart, PEdge *collapsed)
static void p_collapse_edge(PEdge *edge, PEdge *pair)
static bool p_vert_interior(PVert *v)
static GeoUVPinIndex * new_geo_uv_pinindex(ParamHandle *handle, const float uv[2])
static float p_abf_compute_grad_alpha(PAbfSystem *sys, PFace *f, PEdge *e)
static float p_face_uv_area_signed(PFace *f)
static bool p_collapse_doubles_allowed(PEdge *edge, PEdge *pair, float threshold_squared)
static void p_chart_uv_to_array(PChart *chart, MutableSpan< float2 > points)
static void UNUSED_FUNCTION p_face_cos(PFace *f, float *r_cos1, float *r_cos2, float *r_cos3)
static void p_vert_fix_edge_pointer(PVert *v)
static void p_chart_uv_translate(PChart *chart, const float trans[2])
static bool p_edge_implicit_seam(PEdge *e, PEdge *ep)
static void p_chart_uv_scale(PChart *chart, const float scale)
void uv_parametrizer_lscm_end(ParamHandle *handle)
static bool p_edge_has_pair(ParamHandle *handle, PEdge *e, bool topology_from_uvs, PEdge **r_pair)
static float p_area_signed(const float v1[2], const float v2[2], const float v3[2])
void uv_parametrizer_aspect_ratio(ParamHandle *handle, float aspect_y)
static void p_chart_uv_transform(PChart *chart, const float mat[2][2])
static float p_abf_compute_gradient(PAbfSystem *sys, PChart *chart)
void uv_parametrizer_stretch_begin(ParamHandle *handle)
static PEdge * p_boundary_edge_next(PEdge *e)
static PHashLink * phash_lookup(PHash *ph, PHashKey key)
static void p_chart_uv_rotate(PChart *chart, float angle)
static void p_triangle_angles(const float v1[3], const float v2[3], const float v3[3], double *r_a1, double *r_a2, double *r_a3)
void uv_parametrizer_flush_restore(ParamHandle *handle)
static bool p_chart_abf_solve(PChart *chart)
static bool p_chart_correct_degenerate_triangles2(PChart *chart, float min_area, float min_angle)
static PVert * p_vert_copy(ParamHandle *handle, PVert *v)
void uv_parametrizer_pack(ParamHandle *handle, const UVPackIsland_Params &params)
static bool p_validate_corrected_coords_point(const PEdge *corr_e, const float corr_co1[3], const float corr_co2[3], const float min_area, const float min_angle_cos)
static PFace * p_face_add(ParamHandle *handle)
static void p_triangle_cos(const float v1[3], const float v2[3], const float v3[3], float *r_cos1, float *r_cos2, float *r_cos3)
static float p_stretch_compute_vertex(PVert *v)
static PChart ** p_split_charts(ParamHandle *handle, PChart *chart, int ncharts)
static void p_add_ngon(ParamHandle *handle, const ParamKey key, const int nverts, const ParamKey *vkeys, const float **co, float **uv, const float *weight, const bool *pin, const bool *select)
static float p_abf_compute_sin_product(PAbfSystem *sys, PVert *v, int aid)
static void p_chart_fill_boundary(ParamHandle *handle, PChart *chart, MutableSpan< PEdge * > border_edges, const float **co)
static void p_chart_extrema_verts(PChart *chart, PVert **pin1, PVert **pin2)
float pack_islands(Span< PackIsland * > islands, const UVPackIsland_Params &params)
void uv_parametrizer_lscm_solve(ParamHandle *handle, int *count_changed, int *count_failed)
static void fix_large_angle(const float v_fix[3], const float v1[3], const float v2[3], double *r_fix, double *r_a1, double *r_a2)
static void p_chart_lscm_begin(PChart *chart, bool live, bool abf, const bool use_original_bounds)
static void p_chart_simplify_compute(PChart *chart, std::function< float(PEdge *, PEdge *)> collapse_cost_fn, std::function< float(PEdge *, PEdge *)> collapse_allowed_fn)
void uv_parametrizer_stretch_iter(ParamHandle *handle)
static void uv_parametrizer_scale_x(ParamHandle *phandle, const float scale_x)
void uv_parametrizer_slim_solve(ParamHandle *phandle, const ParamSlimOptions *slim_options, bool use_original_bounds, int *count_changed, int *count_failed)
static int p_face_exists(ParamHandle *handle, const ParamKey *pvkeys, int i1, int i2, int i3)
static void p_face_flip(PFace *f)
static void phash_insert(PHash *ph, PHashLink *link)
static float p_face_area(PFace *f)
void uv_parametrizer_original_bounds(ParamHandle *phandle)
static PVert * p_vert_lookup(ParamHandle *handle, PHashKey key, const float co[3], const float weight, PEdge *e)
static void p_chart_flush_collapsed_uvs(PChart *chart)
static void p_chart_orig_bounds_init(PChart *chart)
void uv_parametrizer_stretch_end(ParamHandle *handle)
static PEdge * p_boundary_edge_prev(PEdge *e)
static PHashLink * phash_next(PHash *ph, PHashKey key, PHashLink *link)
static void p_polygon_calc_tris(ParamHandle *handle, const float **co, uint(**r_tris)[3], uint nverts)
static float p_edge_uv_length(PEdge *e)
static void p_chart_boundaries(PChart *chart, PEdge **r_outer)
static int p_connect_pairs(ParamHandle *handle, bool topology_from_uvs)
static void p_chart_lscm_transform_single_pin(PChart *chart)
static bool p_validate_triangle_angles(const PVert *vert1, const PVert *vert2, const PVert *vert3, const float min_angle_cos)
void uv_parametrizer_face_add(ParamHandle *handle, const ParamKey key, const int nverts, const ParamKey *vkeys, const float **co, float **uv, const float *weight, const bool *pin, const bool *select)
UserDef U
Definition blender.cc:58
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void mul_m3_v3(const float M[3][3], float r[3])
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:271
__int64 int64_t
Definition BKE_text.h:90
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:173
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
GHash * BLI_ghash_int_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
HeapNode * BLI_heap_top(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:281
MINLINE void copy_v3_v3(float r[3], const float a[3])
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
float angle_v2v2v2(const float a[2], const float b[2], const float c[2]) ATTR_WARN_UNUSED_RESULT
MINLINE void add_v2_v2v2(float r[2], const float a[2], const float b[2])
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
Definition BLI_heap.cc:309
float2 BLI_convexhull_aabb_fit_points_2d_as_sincos(Span< float2 > points)
void * BLI_ghash_lookup(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:735
MINLINE void copy_v2_v2(float r[2], const float a[2])
float angle_v3v3v3(const float a[3], const float b[3], const float c[3]) ATTR_WARN_UNUSED_RESULT
@ ED_UVPACK_PIN_NONE
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:193
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
void BLI_polyfill_calc_arena(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3], struct MemArena *arena)
ATTR_WARN_UNUSED_RESULT const BMVert * v
struct RNG * BLI_rng_new(unsigned int seed)
Definition rand.cc:41
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:293
MINLINE void mul_v3_fl(float r[3], float f)
void BLI_ghash_insert(GHash *gh, void *key, void *val)
Definition BLI_ghash.cc:711
MINLINE void sub_v3_v3(float r[3], const float a[3])
MINLINE bool equals_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
VecBase< float, 2 > float2
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition BLI_ghash.cc:866
void minmax_v2v2_v2(float min[2], float max[2], const float vec[2])
void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition BLI_heap.cc:236
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
MINLINE double max_dd(double a, double b)
void mul_m2_v2(const float mat[2][2], float vec[2])
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition rand.cc:55
MINLINE float len_v3(const float a[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void zero_v3(float r[3])
MINLINE bool equals_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
_W64 unsigned int uintptr_t
Definition BKE_text.h:120
float BLI_rng_get_float(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition rand.cc:90
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
MINLINE float normalize_v3(float n[3])
MINLINE void add_v3_v3(float r[3], const float a[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
MINLINE float len_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:104
void mid_v2_v2v2(float r[2], const float a[2], const float b[2])
Heap * BLI_heap_new() ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:188
float volume_tri_tetrahedron_signed_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:283
VecBase< float, 3 > float3
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float len_squared_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT
bool invert_m2_m2(float inverse[2][2], const float mat[2][2])
MINLINE float safe_divide(float a, float b)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void * BLI_memarena_calloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
float cos_v3v3v3(const float p1[3], const float p2[3], const float p3[3]) ATTR_WARN_UNUSED_RESULT
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void BLI_polyfill_beautify(const float(*coords)[2], unsigned int coords_num, unsigned int(*tris)[3], struct MemArena *arena, struct Heap *eheap)
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
MINLINE float clamp_f(float value, float min, float max)
#define hash
Definition noise_c.cc:156
const btScalar eps
Definition poly34.cpp:11
#define fabsf
#define sqrtf
#define sinf
#define cosf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
PChartOrigBounds * orig_bounds
union blender::geometry::PEdge::PEdgeUnion u
union blender::geometry::PFace::PFaceUnion u
union blender::geometry::PVert::PVertUnion u
std::vector< float > w_vectors
std::vector< double > el_vectors
std::vector< double > v_matrices
std::vector< double > uv_matrices
std::vector< double > pp_matrices
void setup_slim_data(MatrixTransferChart &chart) const
std::vector< MatrixTransferChart > charts
PinnedVertexData pinned_vertex_data
void parametrize_live(MatrixTransferChart &chart, const PinnedVertexData &pinned_vertex_data)
std::vector< int > selected_pins
std::vector< int > pinned_vertex_indices
std::vector< double > pinned_vertex_positions_2D
#define UNUSED_FUNCTION_NO_SLIM
#define PHASH_hash(ph, item)
#define PHASH_edge(v1, v2)
#define PEDGE_VERTEX_FLAGS
#define P_STRETCH_ITER
#define ABF_MAX_ITER
#define param_warning(message)