Blender  V3.3
uv_parametrizer.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
7 #include "GEO_uv_parametrizer.h"
8 
9 #include "MEM_guardedalloc.h"
10 
11 #include "BLI_boxpack_2d.h"
12 #include "BLI_convexhull_2d.h"
13 #include "BLI_ghash.h"
14 #include "BLI_heap.h"
15 #include "BLI_memarena.h"
16 #include "BLI_polyfill_2d.h"
18 #include "BLI_rand.h"
19 
20 #include "eigen_capi.h"
21 
22 /* Utils */
23 
24 #define param_assert(condition) \
25  if (!(condition)) { /*printf("Assertion %s:%d\n", __FILE__, __LINE__); abort();*/ \
26  } \
27  (void)0
28 #define param_warning(message) \
29  {/*printf("Warning %s:%d: %s\n", __FILE__, __LINE__, message);*/}(void)0
30 
31 /* Special Purpose Hash */
32 
34 
35 typedef struct PHashLink {
36  struct PHashLink *next;
39 
40 typedef struct PHash {
45 
46 /* Simplices */
47 
48 typedef struct PVert {
49  struct PVert *nextlink;
50 
51  union PVertUnion {
52  PHashKey key; /* Construct. */
53  int id; /* ABF/LSCM matrix index. */
54  float distortion; /* Area smoothing. */
55  HeapNode *heaplink; /* Edge collapsing. */
56  } u;
57 
58  struct PEdge *edge;
59  float co[3];
60  float uv[2];
62 
64 
65 typedef struct PEdge {
66  struct PEdge *nextlink;
67 
68  union PEdgeUnion {
69  PHashKey key; /* Construct. */
70  int id; /* ABF matrix index. */
71  HeapNode *heaplink; /* Fill holes. */
72  struct PEdge *nextcollapse; /* Simplification. */
73  } u;
74 
75  struct PVert *vert;
76  struct PEdge *pair;
77  struct PEdge *next;
78  struct PFace *face;
79  float *orig_uv, old_uv[2];
81 
83 
84 typedef struct PFace {
85  struct PFace *nextlink;
86 
87  union PFaceUnion {
88  PHashKey key; /* Construct. */
89  int chart; /* Construct splitting. */
90  float area3d; /* Stretch. */
91  int id; /* ABF matrix index. */
92  } u;
93 
94  struct PEdge *edge;
97 
98 enum PVertFlag {
99  PVERT_PIN = 1,
104 };
105 
106 enum PEdgeFlag {
116 };
117 
118 /* for flipping faces */
119 #define PEDGE_VERTEX_FLAGS (PEDGE_PIN)
120 
121 enum PFaceFlag {
125 };
126 
127 /* Chart */
128 
129 typedef struct PChart {
135 
139 
140  union PChartUnion {
141  struct PChartLscm {
143  float *abf_alpha;
147  float single_pin_uv[2];
148  } lscm;
149  struct PChartPack {
150  float rescale, area;
151  float size[2];
152  float origin[2];
153  } pack;
154  } u;
155 
159 
162 };
163 
169 };
170 
171 typedef struct ParamHandle {
172  enum PHandleState state;
176 
181 
182  struct GHash *pin_hash;
184 
186  int ncharts;
187 
188  float aspx, aspy;
189 
191  float blend;
193 
194 /* PHash
195  * - special purpose hash that keeps all its elements in a single linked list.
196  * - after construction, this hash is thrown away, and the list remains.
197  * - removing elements is not possible efficiently.
198  */
199 
200 static int PHashSizes[] = {
201  1, 3, 5, 11, 17, 37, 67, 131, 257, 521,
202  1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309,
203  1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459,
204 };
205 
206 #define PHASH_hash(ph, item) (((uintptr_t)(item)) % ((uint)(ph)->cursize))
207 #define PHASH_edge(v1, v2) (((v1) < (v2)) ? ((v1)*39) ^ ((v2)*31) : ((v1)*31) ^ ((v2)*39))
208 
209 static PHash *phash_new(PHashLink **list, int sizehint)
210 {
211  PHash *ph = (PHash *)MEM_callocN(sizeof(PHash), "PHash");
212  ph->size = 0;
213  ph->cursize_id = 0;
214  ph->list = list;
215 
216  while (PHashSizes[ph->cursize_id] < sizehint) {
217  ph->cursize_id++;
218  }
219 
220  ph->cursize = PHashSizes[ph->cursize_id];
221  ph->buckets = (PHashLink **)MEM_callocN(ph->cursize * sizeof(*ph->buckets), "PHashBuckets");
222 
223  return ph;
224 }
225 
226 static void phash_delete(PHash *ph)
227 {
228  MEM_freeN(ph->buckets);
229  MEM_freeN(ph);
230 }
231 
232 static int phash_size(PHash *ph)
233 {
234  return ph->size;
235 }
236 
237 static void phash_insert(PHash *ph, PHashLink *link)
238 {
239  int size = ph->cursize;
240  uintptr_t hash = PHASH_hash(ph, link->key);
241  PHashLink *lookup = ph->buckets[hash];
242 
243  if (lookup == NULL) {
244  /* insert in front of the list */
245  ph->buckets[hash] = link;
246  link->next = *(ph->list);
247  *(ph->list) = link;
248  }
249  else {
250  /* insert after existing element */
251  link->next = lookup->next;
252  lookup->next = link;
253  }
254 
255  ph->size++;
256 
257  if (ph->size > (size * 3)) {
258  PHashLink *next = NULL, *first = *(ph->list);
259 
260  ph->cursize = PHashSizes[++ph->cursize_id];
261  MEM_freeN(ph->buckets);
262  ph->buckets = (PHashLink **)MEM_callocN(ph->cursize * sizeof(*ph->buckets), "PHashBuckets");
263  ph->size = 0;
264  *(ph->list) = NULL;
265 
266  for (link = first; link; link = next) {
267  next = link->next;
268  phash_insert(ph, link);
269  }
270  }
271 }
272 
274 {
275  PHashLink *link;
276  uintptr_t hash = PHASH_hash(ph, key);
277 
278  for (link = ph->buckets[hash]; link; link = link->next) {
279  if (link->key == key) {
280  return link;
281  }
282  if (PHASH_hash(ph, link->key) != hash) {
283  return NULL;
284  }
285  }
286 
287  return link;
288 }
289 
290 static PHashLink *phash_next(PHash *ph, PHashKey key, PHashLink *link)
291 {
292  uintptr_t hash = PHASH_hash(ph, key);
293 
294  for (link = link->next; link; link = link->next) {
295  if (link->key == key) {
296  return link;
297  }
298  if (PHASH_hash(ph, link->key) != hash) {
299  return NULL;
300  }
301  }
302 
303  return link;
304 }
305 
306 /* Geometry */
307 
308 static float p_vec_angle(const float v1[3], const float v2[3], const float v3[3])
309 {
310  return angle_v3v3v3(v1, v2, v3);
311 }
312 static float p_vec2_angle(const float v1[2], const float v2[2], const float v3[2])
313 {
314  return angle_v2v2v2(v1, v2, v3);
315 }
316 static void p_triangle_angles(
317  const float v1[3], const float v2[3], const float v3[3], float *r_a1, float *r_a2, float *r_a3)
318 {
319  *r_a1 = p_vec_angle(v3, v1, v2);
320  *r_a2 = p_vec_angle(v1, v2, v3);
321  *r_a3 = (float)M_PI - *r_a2 - *r_a1;
322 }
323 
324 static void p_face_angles(PFace *f, float *r_a1, float *r_a2, float *r_a3)
325 {
326  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
327  PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
328 
329  p_triangle_angles(v1->co, v2->co, v3->co, r_a1, r_a2, r_a3);
330 }
331 
332 static float p_face_area(PFace *f)
333 {
334  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
335  PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
336 
337  return area_tri_v3(v1->co, v2->co, v3->co);
338 }
339 
340 static float p_area_signed(const float v1[2], const float v2[2], const float v3[2])
341 {
342  return 0.5f * (((v2[0] - v1[0]) * (v3[1] - v1[1])) - ((v3[0] - v1[0]) * (v2[1] - v1[1])));
343 }
344 
345 static float p_face_uv_area_signed(PFace *f)
346 {
347  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
348  PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
349 
350  return 0.5f * (((v2->uv[0] - v1->uv[0]) * (v3->uv[1] - v1->uv[1])) -
351  ((v3->uv[0] - v1->uv[0]) * (v2->uv[1] - v1->uv[1])));
352 }
353 
354 static float p_edge_length(PEdge *e)
355 {
356  return len_v3v3(e->vert->co, e->next->vert->co);
357 }
358 
359 static float p_edge_uv_length(PEdge *e)
360 {
361  return len_v2v2(e->vert->uv, e->next->vert->uv);
362 }
363 
364 static void p_chart_uv_bbox(PChart *chart, float minv[2], float maxv[2])
365 {
366  PVert *v;
367 
368  INIT_MINMAX2(minv, maxv);
369 
370  for (v = chart->verts; v; v = v->nextlink) {
371  minmax_v2v2_v2(minv, maxv, v->uv);
372  }
373 }
374 
375 static float p_chart_uv_area(PChart *chart)
376 {
377  float area = 0.0f;
378 
379  for (PFace *f = chart->faces; f; f = f->nextlink) {
381  }
382 
383  return area;
384 }
385 
386 static void p_chart_uv_scale(PChart *chart, float scale)
387 {
388  PVert *v;
389 
390  for (v = chart->verts; v; v = v->nextlink) {
391  v->uv[0] *= scale;
392  v->uv[1] *= scale;
393  }
394 }
395 
396 static void p_chart_uv_scale_xy(PChart *chart, float x, float y)
397 {
398  PVert *v;
399 
400  for (v = chart->verts; v; v = v->nextlink) {
401  v->uv[0] *= x;
402  v->uv[1] *= y;
403  }
404 }
405 
406 static void p_chart_uv_translate(PChart *chart, const float trans[2])
407 {
408  PVert *v;
409 
410  for (v = chart->verts; v; v = v->nextlink) {
411  v->uv[0] += trans[0];
412  v->uv[1] += trans[1];
413  }
414 }
415 
416 static void p_chart_uv_transform(PChart *chart, const float mat[2][2])
417 {
418  PVert *v;
419 
420  for (v = chart->verts; v; v = v->nextlink) {
421  mul_m2_v2(mat, v->uv);
422  }
423 }
424 
425 static void p_chart_uv_to_array(PChart *chart, float (*points)[2])
426 {
427  PVert *v;
428  uint i = 0;
429 
430  for (v = chart->verts; v; v = v->nextlink) {
431  copy_v2_v2(points[i++], v->uv);
432  }
433 }
434 
435 static bool p_intersect_line_2d_dir(const float v1[2],
436  const float dir1[2],
437  const float v2[2],
438  const float dir2[2],
439  float r_isect[2])
440 {
441  float lmbda, div;
442 
443  div = dir2[0] * dir1[1] - dir2[1] * dir1[0];
444 
445  if (div == 0.0f) {
446  return false;
447  }
448 
449  lmbda = ((v1[1] - v2[1]) * dir1[0] - (v1[0] - v2[0]) * dir1[1]) / div;
450  r_isect[0] = v1[0] + lmbda * dir2[0];
451  r_isect[1] = v1[1] + lmbda * dir2[1];
452 
453  return true;
454 }
455 
456 /* Topological Utilities */
457 
459 {
460  return e->next->next->pair;
461 }
462 
464 {
465  return (e->pair) ? e->pair->next : NULL;
466 }
467 
469 {
470  return e->next->vert->edge;
471 }
472 
474 {
475  PEdge *we = e, *last;
476 
477  do {
478  last = we;
479  we = p_wheel_edge_next(we);
480  } while (we && (we != e));
481 
482  return last->next->next;
483 }
484 
485 static bool p_vert_interior(PVert *v)
486 {
487  return v->edge->pair;
488 }
489 
490 static void p_face_flip(PFace *f)
491 {
492  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
493  PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
494  int f1 = e1->flag, f2 = e2->flag, f3 = e3->flag;
495  float *orig_uv1 = e1->orig_uv, *orig_uv2 = e2->orig_uv, *orig_uv3 = e3->orig_uv;
496 
497  e1->vert = v2;
498  e1->next = e3;
499  e1->orig_uv = orig_uv2;
500  e1->flag = (f1 & ~PEDGE_VERTEX_FLAGS) | (f2 & PEDGE_VERTEX_FLAGS);
501 
502  e2->vert = v3;
503  e2->next = e1;
504  e2->orig_uv = orig_uv3;
505  e2->flag = (f2 & ~PEDGE_VERTEX_FLAGS) | (f3 & PEDGE_VERTEX_FLAGS);
506 
507  e3->vert = v1;
508  e3->next = e2;
509  e3->orig_uv = orig_uv1;
510  e3->flag = (f3 & ~PEDGE_VERTEX_FLAGS) | (f1 & PEDGE_VERTEX_FLAGS);
511 }
512 
513 #if 0
514 static void p_chart_topological_sanity_check(PChart *chart)
515 {
516  PVert *v;
517  PEdge *e;
518 
519  for (v = chart->verts; v; v = v->nextlink) {
520  GEO_uv_parametrizer_test_equals_ptr("v->edge->vert", v, v->edge->vert);
521  }
522 
523  for (e = chart->edges; e; e = e->nextlink) {
524  if (e->pair) {
525  GEO_uv_parametrizer_test_equals_ptr("e->pair->pair", e, e->pair->pair);
526  GEO_uv_parametrizer_test_equals_ptr("pair->vert", e->vert, e->pair->next->vert);
527  GEO_uv_parametrizer_test_equals_ptr("pair->next->vert", e->next->vert, e->pair->vert);
528  }
529  }
530 }
531 #endif
532 
533 /* Loading / Flushing */
534 
536 {
537  PEdge *e;
538  int nedges = 0, npins = 0;
539  float pinuv[2];
540 
541  v->uv[0] = v->uv[1] = 0.0f;
542  pinuv[0] = pinuv[1] = 0.0f;
543  e = v->edge;
544  do {
545  if (e->orig_uv) {
546  if (e->flag & PEDGE_SELECT) {
547  v->flag |= PVERT_SELECT;
548  }
549 
550  if (e->flag & PEDGE_PIN) {
551  pinuv[0] += e->orig_uv[0] * handle->aspx;
552  pinuv[1] += e->orig_uv[1] * handle->aspy;
553  npins++;
554  }
555  else {
556  v->uv[0] += e->orig_uv[0] * handle->aspx;
557  v->uv[1] += e->orig_uv[1] * handle->aspy;
558  }
559 
560  nedges++;
561  }
562 
563  e = p_wheel_edge_next(e);
564  } while (e && e != (v->edge));
565 
566  if (npins > 0) {
567  v->uv[0] = pinuv[0] / npins;
568  v->uv[1] = pinuv[1] / npins;
569  v->flag |= PVERT_PIN;
570  }
571  else if (nedges > 0) {
572  v->uv[0] /= nedges;
573  v->uv[1] /= nedges;
574  }
575 }
576 
577 static void p_flush_uvs(ParamHandle *handle, PChart *chart)
578 {
579  PEdge *e;
580 
581  for (e = chart->edges; e; e = e->nextlink) {
582  if (e->orig_uv) {
583  e->orig_uv[0] = e->vert->uv[0] / handle->aspx;
584  e->orig_uv[1] = e->vert->uv[1] / handle->aspy;
585  }
586  }
587 }
588 
589 static void p_flush_uvs_blend(ParamHandle *handle, PChart *chart, float blend)
590 {
591  PEdge *e;
592  float invblend = 1.0f - blend;
593 
594  for (e = chart->edges; e; e = e->nextlink) {
595  if (e->orig_uv) {
596  e->orig_uv[0] = blend * e->old_uv[0] + invblend * e->vert->uv[0] / handle->aspx;
597  e->orig_uv[1] = blend * e->old_uv[1] + invblend * e->vert->uv[1] / handle->aspy;
598  }
599  }
600 }
601 
602 static void p_face_backup_uvs(PFace *f)
603 {
604  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
605 
606  if (e1->orig_uv) {
607  e1->old_uv[0] = e1->orig_uv[0];
608  e1->old_uv[1] = e1->orig_uv[1];
609  }
610  if (e2->orig_uv) {
611  e2->old_uv[0] = e2->orig_uv[0];
612  e2->old_uv[1] = e2->orig_uv[1];
613  }
614  if (e3->orig_uv) {
615  e3->old_uv[0] = e3->orig_uv[0];
616  e3->old_uv[1] = e3->orig_uv[1];
617  }
618 }
619 
620 static void p_face_restore_uvs(PFace *f)
621 {
622  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
623 
624  if (e1->orig_uv) {
625  e1->orig_uv[0] = e1->old_uv[0];
626  e1->orig_uv[1] = e1->old_uv[1];
627  }
628  if (e2->orig_uv) {
629  e2->orig_uv[0] = e2->old_uv[0];
630  e2->orig_uv[1] = e2->old_uv[1];
631  }
632  if (e3->orig_uv) {
633  e3->orig_uv[0] = e3->old_uv[0];
634  e3->orig_uv[1] = e3->old_uv[1];
635  }
636 }
637 
638 /* Construction (use only during construction, relies on u.key being set */
639 
640 static PVert *p_vert_add(ParamHandle *handle, PHashKey key, const float co[3], PEdge *e)
641 {
642  PVert *v = (PVert *)BLI_memarena_alloc(handle->arena, sizeof(*v));
643  copy_v3_v3(v->co, co);
644 
645  /* Sanity check, a single nan/inf point causes the entire result to be invalid.
646  * Note that values within the calculation may _become_ non-finite,
647  * so the rest of the code still needs to take this possibility into account. */
648  for (int i = 0; i < 3; i++) {
649  if (UNLIKELY(!isfinite(v->co[i]))) {
650  v->co[i] = 0.0f;
651  }
652  }
653 
654  v->u.key = key;
655  v->edge = e;
656  v->flag = 0;
657 
658  phash_insert(handle->hash_verts, (PHashLink *)v);
659 
660  return v;
661 }
662 
663 static PVert *p_vert_lookup(ParamHandle *handle, PHashKey key, const float co[3], PEdge *e)
664 {
665  PVert *v = (PVert *)phash_lookup(handle->hash_verts, key);
666 
667  if (v) {
668  return v;
669  }
670  return p_vert_add(handle, key, co, e);
671 }
672 
673 static PVert *p_vert_copy(PChart *chart, PVert *v)
674 {
675  PVert *nv = (PVert *)BLI_memarena_alloc(chart->handle->arena, sizeof(*nv));
676 
677  copy_v3_v3(nv->co, v->co);
678  nv->uv[0] = v->uv[0];
679  nv->uv[1] = v->uv[1];
680  nv->u.key = v->u.key;
681  nv->edge = v->edge;
682  nv->flag = v->flag;
683 
684  return nv;
685 }
686 
687 static PEdge *p_edge_lookup(ParamHandle *handle, const PHashKey *vkeys)
688 {
689  PHashKey key = PHASH_edge(vkeys[0], vkeys[1]);
690  PEdge *e = (PEdge *)phash_lookup(handle->hash_edges, key);
691 
692  while (e) {
693  if ((e->vert->u.key == vkeys[0]) && (e->next->vert->u.key == vkeys[1])) {
694  return e;
695  }
696  if ((e->vert->u.key == vkeys[1]) && (e->next->vert->u.key == vkeys[0])) {
697  return e;
698  }
699 
700  e = (PEdge *)phash_next(handle->hash_edges, key, (PHashLink *)e);
701  }
702 
703  return NULL;
704 }
705 
706 static int p_face_exists(ParamHandle *handle, const ParamKey *pvkeys, int i1, int i2, int i3)
707 {
708  PHashKey *vkeys = (PHashKey *)pvkeys;
709  PHashKey key = PHASH_edge(vkeys[i1], vkeys[i2]);
710  PEdge *e = (PEdge *)phash_lookup(handle->hash_edges, key);
711 
712  while (e) {
713  if ((e->vert->u.key == vkeys[i1]) && (e->next->vert->u.key == vkeys[i2])) {
714  if (e->next->next->vert->u.key == vkeys[i3]) {
715  return true;
716  }
717  }
718  else if ((e->vert->u.key == vkeys[i2]) && (e->next->vert->u.key == vkeys[i1])) {
719  if (e->next->next->vert->u.key == vkeys[i3]) {
720  return true;
721  }
722  }
723 
724  e = (PEdge *)phash_next(handle->hash_edges, key, (PHashLink *)e);
725  }
726 
727  return false;
728 }
729 
731 {
732  PChart *chart = (PChart *)MEM_callocN(sizeof(*chart), "PChart");
733  chart->handle = handle;
734 
735  return chart;
736 }
737 
738 static void p_chart_delete(PChart *chart)
739 {
740  /* the actual links are free by memarena */
741  MEM_freeN(chart);
742 }
743 
744 static bool p_edge_implicit_seam(PEdge *e, PEdge *ep)
745 {
746  float *uv1, *uv2, *uvp1, *uvp2;
747  float limit[2];
748 
749  limit[0] = 0.00001;
750  limit[1] = 0.00001;
751 
752  uv1 = e->orig_uv;
753  uv2 = e->next->orig_uv;
754 
755  if (e->vert->u.key == ep->vert->u.key) {
756  uvp1 = ep->orig_uv;
757  uvp2 = ep->next->orig_uv;
758  }
759  else {
760  uvp1 = ep->next->orig_uv;
761  uvp2 = ep->orig_uv;
762  }
763 
764  if ((fabsf(uv1[0] - uvp1[0]) > limit[0]) || (fabsf(uv1[1] - uvp1[1]) > limit[1])) {
765  e->flag |= PEDGE_SEAM;
766  ep->flag |= PEDGE_SEAM;
767  return true;
768  }
769  if ((fabsf(uv2[0] - uvp2[0]) > limit[0]) || (fabsf(uv2[1] - uvp2[1]) > limit[1])) {
770  e->flag |= PEDGE_SEAM;
771  ep->flag |= PEDGE_SEAM;
772  return true;
773  }
774 
775  return false;
776 }
777 
778 static bool p_edge_has_pair(ParamHandle *handle, PEdge *e, bool topology_from_uvs, PEdge **r_pair)
779 {
780  PHashKey key;
781  PEdge *pe;
782  PVert *v1, *v2;
783  PHashKey key1 = e->vert->u.key;
784  PHashKey key2 = e->next->vert->u.key;
785 
786  if (e->flag & PEDGE_SEAM) {
787  return false;
788  }
789 
790  key = PHASH_edge(key1, key2);
791  pe = (PEdge *)phash_lookup(handle->hash_edges, key);
792  *r_pair = NULL;
793 
794  while (pe) {
795  if (pe != e) {
796  v1 = pe->vert;
797  v2 = pe->next->vert;
798 
799  if (((v1->u.key == key1) && (v2->u.key == key2)) ||
800  ((v1->u.key == key2) && (v2->u.key == key1))) {
801 
802  /* don't connect seams and t-junctions */
803  if ((pe->flag & PEDGE_SEAM) || *r_pair ||
804  (topology_from_uvs && p_edge_implicit_seam(e, pe))) {
805  *r_pair = NULL;
806  return false;
807  }
808 
809  *r_pair = pe;
810  }
811  }
812 
813  pe = (PEdge *)phash_next(handle->hash_edges, key, (PHashLink *)pe);
814  }
815 
816  if (*r_pair && (e->vert == (*r_pair)->vert)) {
817  if ((*r_pair)->next->pair || (*r_pair)->next->next->pair) {
818  /* non unfoldable, maybe mobius ring or klein bottle */
819  *r_pair = NULL;
820  return false;
821  }
822  }
823 
824  return (*r_pair != NULL);
825 }
826 
827 static bool p_edge_connect_pair(ParamHandle *handle,
828  PEdge *e,
829  bool topology_from_uvs,
830  PEdge ***stack)
831 {
832  PEdge *pair = NULL;
833 
834  if (!e->pair && p_edge_has_pair(handle, e, topology_from_uvs, &pair)) {
835  if (e->vert == pair->vert) {
836  p_face_flip(pair->face);
837  }
838 
839  e->pair = pair;
840  pair->pair = e;
841 
842  if (!(pair->face->flag & PFACE_CONNECTED)) {
843  **stack = pair;
844  (*stack)++;
845  }
846  }
847 
848  return (e->pair != NULL);
849 }
850 
851 static int p_connect_pairs(ParamHandle *handle, bool topology_from_uvs)
852 {
853  PEdge **stackbase = MEM_mallocN(sizeof(*stackbase) * phash_size(handle->hash_faces),
854  "Pstackbase");
855  PEdge **stack = stackbase;
856  PFace *f, *first;
857  PEdge *e, *e1, *e2;
858  PChart *chart = handle->construction_chart;
859  int ncharts = 0;
860 
861  /* Connect pairs, count edges, set vertex-edge pointer to a pair-less edge. */
862  for (first = chart->faces; first; first = first->nextlink) {
863  if (first->flag & PFACE_CONNECTED) {
864  continue;
865  }
866 
867  *stack = first->edge;
868  stack++;
869 
870  while (stack != stackbase) {
871  stack--;
872  e = *stack;
873  e1 = e->next;
874  e2 = e1->next;
875 
876  f = e->face;
877  f->flag |= PFACE_CONNECTED;
878 
879  /* assign verts to charts so we can sort them later */
880  f->u.chart = ncharts;
881 
882  if (!p_edge_connect_pair(handle, e, topology_from_uvs, &stack)) {
883  e->vert->edge = e;
884  }
885  if (!p_edge_connect_pair(handle, e1, topology_from_uvs, &stack)) {
886  e1->vert->edge = e1;
887  }
888  if (!p_edge_connect_pair(handle, e2, topology_from_uvs, &stack)) {
889  e2->vert->edge = e2;
890  }
891  }
892 
893  ncharts++;
894  }
895 
896  MEM_freeN(stackbase);
897 
898  return ncharts;
899 }
900 
901 static void p_split_vert(PChart *chart, PEdge *e)
902 {
903  PEdge *we, *lastwe = NULL;
904  PVert *v = e->vert;
905  bool copy = true;
906 
907  if (e->flag & PEDGE_PIN) {
908  chart->flag |= PCHART_HAS_PINS;
909  }
910 
911  if (e->flag & PEDGE_VERTEX_SPLIT) {
912  return;
913  }
914 
915  /* rewind to start */
916  lastwe = e;
917  for (we = p_wheel_edge_prev(e); we && (we != e); we = p_wheel_edge_prev(we)) {
918  lastwe = we;
919  }
920 
921  /* go over all edges in wheel */
922  for (we = lastwe; we; we = p_wheel_edge_next(we)) {
923  if (we->flag & PEDGE_VERTEX_SPLIT) {
924  break;
925  }
926 
927  we->flag |= PEDGE_VERTEX_SPLIT;
928 
929  if (we == v->edge) {
930  /* found it, no need to copy */
931  copy = false;
932  v->nextlink = chart->verts;
933  chart->verts = v;
934  chart->nverts++;
935  }
936  }
937 
938  if (copy) {
939  /* not found, copying */
940  v->flag |= PVERT_SPLIT;
941  v = p_vert_copy(chart, v);
942  v->flag |= PVERT_SPLIT;
943 
944  v->nextlink = chart->verts;
945  chart->verts = v;
946  chart->nverts++;
947 
948  v->edge = lastwe;
949 
950  we = lastwe;
951  do {
952  we->vert = v;
953  we = p_wheel_edge_next(we);
954  } while (we && (we != lastwe));
955  }
956 }
957 
958 static PChart **p_split_charts(ParamHandle *handle, PChart *chart, int ncharts)
959 {
960  PChart **charts = MEM_mallocN(sizeof(*charts) * ncharts, "PCharts"), *nchart;
961  PFace *f, *nextf;
962  int i;
963 
964  for (i = 0; i < ncharts; i++) {
965  charts[i] = p_chart_new(handle);
966  }
967 
968  f = chart->faces;
969  while (f) {
970  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
971  nextf = f->nextlink;
972 
973  nchart = charts[f->u.chart];
974 
975  f->nextlink = nchart->faces;
976  nchart->faces = f;
977  e1->nextlink = nchart->edges;
978  nchart->edges = e1;
979  e2->nextlink = nchart->edges;
980  nchart->edges = e2;
981  e3->nextlink = nchart->edges;
982  nchart->edges = e3;
983 
984  nchart->nfaces++;
985  nchart->nedges += 3;
986 
987  p_split_vert(nchart, e1);
988  p_split_vert(nchart, e2);
989  p_split_vert(nchart, e3);
990 
991  f = nextf;
992  }
993 
994  return charts;
995 }
996 
997 static PFace *p_face_add(ParamHandle *handle)
998 {
999  PFace *f;
1000  PEdge *e1, *e2, *e3;
1001 
1002  /* allocate */
1003  f = (PFace *)BLI_memarena_alloc(handle->arena, sizeof(*f));
1004  f->flag = 0; /* init ! */
1005 
1006  e1 = (PEdge *)BLI_memarena_alloc(handle->arena, sizeof(*e1));
1007  e2 = (PEdge *)BLI_memarena_alloc(handle->arena, sizeof(*e2));
1008  e3 = (PEdge *)BLI_memarena_alloc(handle->arena, sizeof(*e3));
1009 
1010  /* set up edges */
1011  f->edge = e1;
1012  e1->face = e2->face = e3->face = f;
1013 
1014  e1->next = e2;
1015  e2->next = e3;
1016  e3->next = e1;
1017 
1018  e1->pair = NULL;
1019  e2->pair = NULL;
1020  e3->pair = NULL;
1021 
1022  e1->flag = 0;
1023  e2->flag = 0;
1024  e3->flag = 0;
1025 
1026  return f;
1027 }
1028 
1030  ParamKey key,
1031  const ParamKey *vkeys,
1032  const float **co,
1033  float **uv,
1034  int i1,
1035  int i2,
1036  int i3,
1037  const bool *pin,
1038  const bool *select)
1039 {
1040  PFace *f = p_face_add(handle);
1041  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
1042 
1043  e1->vert = p_vert_lookup(handle, vkeys[i1], co[i1], e1);
1044  e2->vert = p_vert_lookup(handle, vkeys[i2], co[i2], e2);
1045  e3->vert = p_vert_lookup(handle, vkeys[i3], co[i3], e3);
1046 
1047  e1->orig_uv = uv[i1];
1048  e2->orig_uv = uv[i2];
1049  e3->orig_uv = uv[i3];
1050 
1051  if (pin) {
1052  if (pin[i1]) {
1053  e1->flag |= PEDGE_PIN;
1054  }
1055  if (pin[i2]) {
1056  e2->flag |= PEDGE_PIN;
1057  }
1058  if (pin[i3]) {
1059  e3->flag |= PEDGE_PIN;
1060  }
1061  }
1062 
1063  if (select) {
1064  if (select[i1]) {
1065  e1->flag |= PEDGE_SELECT;
1066  }
1067  if (select[i2]) {
1068  e2->flag |= PEDGE_SELECT;
1069  }
1070  if (select[i3]) {
1071  e3->flag |= PEDGE_SELECT;
1072  }
1073  }
1074 
1075  f->u.key = key;
1076  phash_insert(handle->hash_faces, (PHashLink *)f);
1077 
1078  e1->u.key = PHASH_edge(vkeys[i1], vkeys[i2]);
1079  e2->u.key = PHASH_edge(vkeys[i2], vkeys[i3]);
1080  e3->u.key = PHASH_edge(vkeys[i3], vkeys[i1]);
1081 
1082  phash_insert(handle->hash_edges, (PHashLink *)e1);
1083  phash_insert(handle->hash_edges, (PHashLink *)e2);
1084  phash_insert(handle->hash_edges, (PHashLink *)e3);
1085 
1086  return f;
1087 }
1088 
1089 static PFace *p_face_add_fill(PChart *chart, PVert *v1, PVert *v2, PVert *v3)
1090 {
1091  PFace *f = p_face_add(chart->handle);
1092  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
1093 
1094  e1->vert = v1;
1095  e2->vert = v2;
1096  e3->vert = v3;
1097 
1098  e1->orig_uv = e2->orig_uv = e3->orig_uv = NULL;
1099 
1100  f->nextlink = chart->faces;
1101  chart->faces = f;
1102  e1->nextlink = chart->edges;
1103  chart->edges = e1;
1104  e2->nextlink = chart->edges;
1105  chart->edges = e2;
1106  e3->nextlink = chart->edges;
1107  chart->edges = e3;
1108 
1109  chart->nfaces++;
1110  chart->nedges += 3;
1111 
1112  return f;
1113 }
1114 
1115 static bool p_quad_split_direction(ParamHandle *handle, const float **co, const ParamKey *vkeys)
1116 {
1117  /* Slight bias to prefer one edge over the other in case they are equal, so
1118  * that in symmetric models we choose the same split direction instead of
1119  * depending on floating point errors to decide. */
1120  float bias = 1.0f + 1e-6f;
1121  float fac = len_v3v3(co[0], co[2]) * bias - len_v3v3(co[1], co[3]);
1122  bool dir = (fac <= 0.0f);
1123 
1124  /* The face exists check is there because of a special case:
1125  * when two quads share three vertices, they can each be split into two triangles,
1126  * resulting in two identical triangles. For example in Suzanne's nose. */
1127  if (dir) {
1128  if (p_face_exists(handle, vkeys, 0, 1, 2) || p_face_exists(handle, vkeys, 0, 2, 3)) {
1129  return !dir;
1130  }
1131  }
1132  else {
1133  if (p_face_exists(handle, vkeys, 0, 1, 3) || p_face_exists(handle, vkeys, 1, 2, 3)) {
1134  return !dir;
1135  }
1136  }
1137 
1138  return dir;
1139 }
1140 
1141 /* Construction: boundary filling */
1142 
1143 static void p_chart_boundaries(PChart *chart, PEdge **r_outer)
1144 {
1145  PEdge *e, *be;
1146  float len, maxlen = -1.0;
1147 
1148  chart->nboundaries = 0;
1149  if (r_outer) {
1150  *r_outer = NULL;
1151  }
1152 
1153  for (e = chart->edges; e; e = e->nextlink) {
1154  if (e->pair || (e->flag & PEDGE_DONE)) {
1155  continue;
1156  }
1157 
1158  chart->nboundaries++;
1159 
1160  len = 0.0f;
1161 
1162  be = e;
1163  do {
1164  be->flag |= PEDGE_DONE;
1165  len += p_edge_length(be);
1166  be = be->next->vert->edge;
1167  } while (be != e);
1168 
1169  if (r_outer && (len > maxlen)) {
1170  *r_outer = e;
1171  maxlen = len;
1172  }
1173  }
1174 
1175  for (e = chart->edges; e; e = e->nextlink) {
1176  e->flag &= ~PEDGE_DONE;
1177  }
1178 }
1179 
1181 {
1182  PEdge *we;
1183  PVert *v, *v1, *v2;
1184  float angle;
1185  int n = 0;
1186 
1187  v = e->vert;
1188 
1189  /* concave angle check -- could be better */
1190  angle = M_PI;
1191 
1192  we = v->edge;
1193  do {
1194  v1 = we->next->vert;
1195  v2 = we->next->next->vert;
1196  angle -= p_vec_angle(v1->co, v->co, v2->co);
1197 
1198  we = we->next->next->pair;
1199  n++;
1200  } while (we && (we != v->edge));
1201 
1202  return angle;
1203 }
1204 
1205 static void p_chart_fill_boundary(PChart *chart, PEdge *be, int nedges)
1206 {
1207  PEdge *e, *e1, *e2;
1208 
1209  PFace *f;
1210  struct Heap *heap = BLI_heap_new();
1211  float angle;
1212 
1213  e = be;
1214  do {
1216  e->u.heaplink = BLI_heap_insert(heap, angle, e);
1217 
1219  } while (e != be);
1220 
1221  if (nedges == 2) {
1222  /* no real boundary, but an isolated seam */
1223  e = be->next->vert->edge;
1224  e->pair = be;
1225  be->pair = e;
1226 
1227  BLI_heap_remove(heap, e->u.heaplink);
1228  BLI_heap_remove(heap, be->u.heaplink);
1229  }
1230  else {
1231  while (nedges > 2) {
1232  PEdge *ne, *ne1, *ne2;
1233 
1234  e = (PEdge *)BLI_heap_pop_min(heap);
1235 
1236  e1 = p_boundary_edge_prev(e);
1237  e2 = p_boundary_edge_next(e);
1238 
1239  BLI_heap_remove(heap, e1->u.heaplink);
1240  BLI_heap_remove(heap, e2->u.heaplink);
1241  e->u.heaplink = e1->u.heaplink = e2->u.heaplink = NULL;
1242 
1243  e->flag |= PEDGE_FILLED;
1244  e1->flag |= PEDGE_FILLED;
1245 
1246  f = p_face_add_fill(chart, e->vert, e1->vert, e2->vert);
1247  f->flag |= PFACE_FILLED;
1248 
1249  ne = f->edge->next->next;
1250  ne1 = f->edge;
1251  ne2 = f->edge->next;
1252 
1253  ne->flag = ne1->flag = ne2->flag = PEDGE_FILLED;
1254 
1255  e->pair = ne;
1256  ne->pair = e;
1257  e1->pair = ne1;
1258  ne1->pair = e1;
1259 
1260  ne->vert = e2->vert;
1261  ne1->vert = e->vert;
1262  ne2->vert = e1->vert;
1263 
1264  if (nedges == 3) {
1265  e2->pair = ne2;
1266  ne2->pair = e2;
1267  }
1268  else {
1269  ne2->vert->edge = ne2;
1270 
1271  ne2->u.heaplink = BLI_heap_insert(heap, p_edge_boundary_angle(ne2), ne2);
1272  e2->u.heaplink = BLI_heap_insert(heap, p_edge_boundary_angle(e2), e2);
1273  }
1274 
1275  nedges--;
1276  }
1277  }
1278 
1279  BLI_heap_free(heap, NULL);
1280 }
1281 
1282 static void p_chart_fill_boundaries(PChart *chart, PEdge *outer)
1283 {
1284  PEdge *e, *be; /* *enext - as yet unused */
1285  int nedges;
1286 
1287  for (e = chart->edges; e; e = e->nextlink) {
1288  /* enext = e->nextlink; - as yet unused */
1289 
1290  if (e->pair || (e->flag & PEDGE_FILLED)) {
1291  continue;
1292  }
1293 
1294  nedges = 0;
1295  be = e;
1296  do {
1297  be->flag |= PEDGE_FILLED;
1298  be = be->next->vert->edge;
1299  nedges++;
1300  } while (be != e);
1301 
1302  if (e != outer) {
1303  p_chart_fill_boundary(chart, e, nedges);
1304  }
1305  }
1306 }
1307 
1308 #if 0
1309 /* Polygon kernel for inserting uv's non overlapping */
1310 
1311 static int p_polygon_point_in(const float cp1[2], const float cp2[2], const float p[2])
1312 {
1313  if ((cp1[0] == p[0]) && (cp1[1] == p[1])) {
1314  return 2;
1315  }
1316  else if ((cp2[0] == p[0]) && (cp2[1] == p[1])) {
1317  return 3;
1318  }
1319  else {
1320  return (p_area_signed(cp1, cp2, p) >= 0.0f);
1321  }
1322 }
1323 
1324 static void p_polygon_kernel_clip(float (*oldpoints)[2],
1325  int noldpoints,
1326  float (*newpoints)[2],
1327  int *r_nnewpoints,
1328  const float cp1[2],
1329  const float cp2[2])
1330 {
1331  float *p2, *p1, isect[2];
1332  int i, p2in, p1in;
1333 
1334  p1 = oldpoints[noldpoints - 1];
1335  p1in = p_polygon_point_in(cp1, cp2, p1);
1336  *r_nnewpoints = 0;
1337 
1338  for (i = 0; i < noldpoints; i++) {
1339  p2 = oldpoints[i];
1340  p2in = p_polygon_point_in(cp1, cp2, p2);
1341 
1342  if ((p2in >= 2) || (p1in && p2in)) {
1343  newpoints[*r_nnewpoints][0] = p2[0];
1344  newpoints[*r_nnewpoints][1] = p2[1];
1345  (*r_nnewpoints)++;
1346  }
1347  else if (p1in && !p2in) {
1348  if (p1in != 3) {
1349  p_intersect_line_2d(p1, p2, cp1, cp2, isect);
1350  newpoints[*r_nnewpoints][0] = isect[0];
1351  newpoints[*r_nnewpoints][1] = isect[1];
1352  (*r_nnewpoints)++;
1353  }
1354  }
1355  else if (!p1in && p2in) {
1356  p_intersect_line_2d(p1, p2, cp1, cp2, isect);
1357  newpoints[*r_nnewpoints][0] = isect[0];
1358  newpoints[*r_nnewpoints][1] = isect[1];
1359  (*r_nnewpoints)++;
1360 
1361  newpoints[*r_nnewpoints][0] = p2[0];
1362  newpoints[*r_nnewpoints][1] = p2[1];
1363  (*r_nnewpoints)++;
1364  }
1365 
1366  p1in = p2in;
1367  p1 = p2;
1368  }
1369 }
1370 
1371 static void p_polygon_kernel_center(float (*points)[2], int npoints, float *center)
1372 {
1373  int i, size, nnewpoints = npoints;
1374  float(*oldpoints)[2], (*newpoints)[2], *p1, *p2;
1375 
1376  size = npoints * 3;
1377  oldpoints = MEM_mallocN(sizeof(float[2]) * size, "PPolygonOldPoints");
1378  newpoints = MEM_mallocN(sizeof(float[2]) * size, "PPolygonNewPoints");
1379 
1380  memcpy(oldpoints, points, sizeof(float[2]) * npoints);
1381 
1382  for (i = 0; i < npoints; i++) {
1383  p1 = points[i];
1384  p2 = points[(i + 1) % npoints];
1385  p_polygon_kernel_clip(oldpoints, nnewpoints, newpoints, &nnewpoints, p1, p2);
1386 
1387  if (nnewpoints == 0) {
1388  /* degenerate case, use center of original polygon */
1389  memcpy(oldpoints, points, sizeof(float[2]) * npoints);
1390  nnewpoints = npoints;
1391  break;
1392  }
1393  else if (nnewpoints == 1) {
1394  /* degenerate case, use remaining point */
1395  center[0] = newpoints[0][0];
1396  center[1] = newpoints[0][1];
1397 
1398  MEM_freeN(oldpoints);
1399  MEM_freeN(newpoints);
1400 
1401  return;
1402  }
1403 
1404  if (nnewpoints * 2 > size) {
1405  size *= 2;
1406  MEM_freeN(oldpoints);
1407  oldpoints = MEM_mallocN(sizeof(float[2]) * size, "oldpoints");
1408  memcpy(oldpoints, newpoints, sizeof(float[2]) * nnewpoints);
1409  MEM_freeN(newpoints);
1410  newpoints = MEM_mallocN(sizeof(float[2]) * size, "newpoints");
1411  }
1412  else {
1413  float(*sw_points)[2] = oldpoints;
1414  oldpoints = newpoints;
1415  newpoints = sw_points;
1416  }
1417  }
1418 
1419  center[0] = center[1] = 0.0f;
1420 
1421  for (i = 0; i < nnewpoints; i++) {
1422  center[0] += oldpoints[i][0];
1423  center[1] += oldpoints[i][1];
1424  }
1425 
1426  center[0] /= nnewpoints;
1427  center[1] /= nnewpoints;
1428 
1429  MEM_freeN(oldpoints);
1430  MEM_freeN(newpoints);
1431 }
1432 #endif
1433 
1434 #if 0
1435 /* Edge Collapser */
1436 
1437 int NCOLLAPSE = 1;
1438 int NCOLLAPSEX = 0;
1439 
1440 static float p_vert_cotan(const float v1[3], const float v2[3], const float v3[3])
1441 {
1442  float a[3], b[3], c[3], clen;
1443 
1444  sub_v3_v3v3(a, v2, v1);
1445  sub_v3_v3v3(b, v3, v1);
1446  cross_v3_v3v3(c, a, b);
1447 
1448  clen = len_v3(c);
1449 
1450  if (clen == 0.0f) {
1451  return 0.0f;
1452  }
1453 
1454  return dot_v3v3(a, b) / clen;
1455 }
1456 
1457 static bool p_vert_flipped_wheel_triangle(PVert *v)
1458 {
1459  PEdge *e = v->edge;
1460 
1461  do {
1462  if (p_face_uv_area_signed(e->face) < 0.0f) {
1463  return true;
1464  }
1465 
1466  e = p_wheel_edge_next(e);
1467  } while (e && (e != v->edge));
1468 
1469  return false;
1470 }
1471 
1472 static bool p_vert_map_harmonic_weights(PVert *v)
1473 {
1474  float weightsum, positionsum[2], olduv[2];
1475 
1476  weightsum = 0.0f;
1477  positionsum[0] = positionsum[1] = 0.0f;
1478 
1479  if (p_vert_interior(v)) {
1480  PEdge *e = v->edge;
1481 
1482  do {
1483  float t1, t2, weight;
1484  PVert *v1, *v2;
1485 
1486  v1 = e->next->vert;
1487  v2 = e->next->next->vert;
1488  t1 = p_vert_cotan(v2->co, e->vert->co, v1->co);
1489 
1490  v1 = e->pair->next->vert;
1491  v2 = e->pair->next->next->vert;
1492  t2 = p_vert_cotan(v2->co, e->pair->vert->co, v1->co);
1493 
1494  weight = 0.5f * (t1 + t2);
1495  weightsum += weight;
1496  positionsum[0] += weight * e->pair->vert->uv[0];
1497  positionsum[1] += weight * e->pair->vert->uv[1];
1498 
1499  e = p_wheel_edge_next(e);
1500  } while (e && (e != v->edge));
1501  }
1502  else {
1503  PEdge *e = v->edge;
1504 
1505  do {
1506  float t1, t2;
1507  PVert *v1, *v2;
1508 
1509  v2 = e->next->vert;
1510  v1 = e->next->next->vert;
1511 
1512  t1 = p_vert_cotan(v1->co, v->co, v2->co);
1513  t2 = p_vert_cotan(v2->co, v->co, v1->co);
1514 
1515  weightsum += t1 + t2;
1516  positionsum[0] += (v2->uv[1] - v1->uv[1]) + (t1 * v2->uv[0] + t2 * v1->uv[0]);
1517  positionsum[1] += (v1->uv[0] - v2->uv[0]) + (t1 * v2->uv[1] + t2 * v1->uv[1]);
1518 
1519  e = p_wheel_edge_next(e);
1520  } while (e && (e != v->edge));
1521  }
1522 
1523  if (weightsum != 0.0f) {
1524  weightsum = 1.0f / weightsum;
1525  positionsum[0] *= weightsum;
1526  positionsum[1] *= weightsum;
1527  }
1528 
1529  olduv[0] = v->uv[0];
1530  olduv[1] = v->uv[1];
1531  v->uv[0] = positionsum[0];
1532  v->uv[1] = positionsum[1];
1533 
1534  if (p_vert_flipped_wheel_triangle(v)) {
1535  v->uv[0] = olduv[0];
1536  v->uv[1] = olduv[1];
1537 
1538  return false;
1539  }
1540 
1541  return true;
1542 }
1543 
1544 static void p_vert_harmonic_insert(PVert *v)
1545 {
1546  PEdge *e;
1547 
1548  if (!p_vert_map_harmonic_weights(v)) {
1549  /* do polygon kernel center insertion: this is quite slow, but should
1550  * only be needed for 0.01 % of verts or so, when insert with harmonic
1551  * weights fails */
1552 
1553  int npoints = 0, i;
1554  float(*points)[2];
1555 
1556  e = v->edge;
1557  do {
1558  npoints++;
1559  e = p_wheel_edge_next(e);
1560  } while (e && (e != v->edge));
1561 
1562  if (e == NULL) {
1563  npoints++;
1564  }
1565 
1566  points = MEM_mallocN(sizeof(float[2]) * npoints, "PHarmonicPoints");
1567 
1568  e = v->edge;
1569  i = 0;
1570  do {
1571  PEdge *nexte = p_wheel_edge_next(e);
1572 
1573  points[i][0] = e->next->vert->uv[0];
1574  points[i][1] = e->next->vert->uv[1];
1575 
1576  if (nexte == NULL) {
1577  i++;
1578  points[i][0] = e->next->next->vert->uv[0];
1579  points[i][1] = e->next->next->vert->uv[1];
1580  break;
1581  }
1582 
1583  e = nexte;
1584  i++;
1585  } while (e != v->edge);
1586 
1587  p_polygon_kernel_center(points, npoints, v->uv);
1588 
1589  MEM_freeN(points);
1590  }
1591 
1592  e = v->edge;
1593  do {
1594  if (!(e->next->vert->flag & PVERT_PIN)) {
1595  p_vert_map_harmonic_weights(e->next->vert);
1596  }
1597  e = p_wheel_edge_next(e);
1598  } while (e && (e != v->edge));
1599 
1600  p_vert_map_harmonic_weights(v);
1601 }
1602 
1603 static void p_vert_fix_edge_pointer(PVert *v)
1604 {
1605  PEdge *start = v->edge;
1606 
1607  /* set v->edge pointer to the edge with no pair, if there is one */
1608  while (v->edge->pair) {
1609  v->edge = p_wheel_edge_prev(v->edge);
1610 
1611  if (v->edge == start) {
1612  break;
1613  }
1614  }
1615 }
1616 
1617 static void p_collapsing_verts(PEdge *edge, PEdge *pair, PVert **r_newv, PVert **r_keepv)
1618 {
1619  /* the two vertices that are involved in the collapse */
1620  if (edge) {
1621  *r_newv = edge->vert;
1622  *r_keepv = edge->next->vert;
1623  }
1624  else {
1625  *r_newv = pair->next->vert;
1626  *r_keepv = pair->vert;
1627  }
1628 }
1629 
1630 static void p_collapse_edge(PEdge *edge, PEdge *pair)
1631 {
1632  PVert *oldv, *keepv;
1633  PEdge *e;
1634 
1635  p_collapsing_verts(edge, pair, &oldv, &keepv);
1636 
1637  /* change e->vert pointers from old vertex to the target vertex */
1638  e = oldv->edge;
1639  do {
1640  if ((e != edge) && !(pair && pair->next == e)) {
1641  e->vert = keepv;
1642  }
1643 
1644  e = p_wheel_edge_next(e);
1645  } while (e && (e != oldv->edge));
1646 
1647  /* set keepv->edge pointer */
1648  if ((edge && (keepv->edge == edge->next)) || (keepv->edge == pair)) {
1649  if (edge && edge->next->pair) {
1650  keepv->edge = edge->next->pair->next;
1651  }
1652  else if (pair && pair->next->next->pair) {
1653  keepv->edge = pair->next->next->pair;
1654  }
1655  else if (edge && edge->next->next->pair) {
1656  keepv->edge = edge->next->next->pair;
1657  }
1658  else {
1659  keepv->edge = pair->next->pair->next;
1660  }
1661  }
1662 
1663  /* update pairs and v->edge pointers */
1664  if (edge) {
1665  PEdge *e1 = edge->next, *e2 = e1->next;
1666 
1667  if (e1->pair) {
1668  e1->pair->pair = e2->pair;
1669  }
1670 
1671  if (e2->pair) {
1672  e2->pair->pair = e1->pair;
1673  e2->vert->edge = p_wheel_edge_prev(e2);
1674  }
1675  else {
1676  e2->vert->edge = p_wheel_edge_next(e2);
1677  }
1678 
1679  p_vert_fix_edge_pointer(e2->vert);
1680  }
1681 
1682  if (pair) {
1683  PEdge *e1 = pair->next, *e2 = e1->next;
1684 
1685  if (e1->pair) {
1686  e1->pair->pair = e2->pair;
1687  }
1688 
1689  if (e2->pair) {
1690  e2->pair->pair = e1->pair;
1691  e2->vert->edge = p_wheel_edge_prev(e2);
1692  }
1693  else {
1694  e2->vert->edge = p_wheel_edge_next(e2);
1695  }
1696 
1697  p_vert_fix_edge_pointer(e2->vert);
1698  }
1699 
1700  p_vert_fix_edge_pointer(keepv);
1701 
1702  /* mark for move to collapsed list later */
1703  oldv->flag |= PVERT_COLLAPSE;
1704 
1705  if (edge) {
1706  PFace *f = edge->face;
1707  PEdge *e1 = edge->next, *e2 = e1->next;
1708 
1709  f->flag |= PFACE_COLLAPSE;
1710  edge->flag |= PEDGE_COLLAPSE;
1711  e1->flag |= PEDGE_COLLAPSE;
1712  e2->flag |= PEDGE_COLLAPSE;
1713  }
1714 
1715  if (pair) {
1716  PFace *f = pair->face;
1717  PEdge *e1 = pair->next, *e2 = e1->next;
1718 
1719  f->flag |= PFACE_COLLAPSE;
1720  pair->flag |= PEDGE_COLLAPSE;
1721  e1->flag |= PEDGE_COLLAPSE;
1722  e2->flag |= PEDGE_COLLAPSE;
1723  }
1724 }
1725 
1726 static void p_split_vertex(PEdge *edge, PEdge *pair)
1727 {
1728  PVert *newv, *keepv;
1729  PEdge *e;
1730 
1731  p_collapsing_verts(edge, pair, &newv, &keepv);
1732 
1733  /* update edge pairs */
1734  if (edge) {
1735  PEdge *e1 = edge->next, *e2 = e1->next;
1736 
1737  if (e1->pair) {
1738  e1->pair->pair = e1;
1739  }
1740  if (e2->pair) {
1741  e2->pair->pair = e2;
1742  }
1743 
1744  e2->vert->edge = e2;
1745  p_vert_fix_edge_pointer(e2->vert);
1746  keepv->edge = e1;
1747  }
1748 
1749  if (pair) {
1750  PEdge *e1 = pair->next, *e2 = e1->next;
1751 
1752  if (e1->pair) {
1753  e1->pair->pair = e1;
1754  }
1755  if (e2->pair) {
1756  e2->pair->pair = e2;
1757  }
1758 
1759  e2->vert->edge = e2;
1760  p_vert_fix_edge_pointer(e2->vert);
1761  keepv->edge = pair;
1762  }
1763 
1764  p_vert_fix_edge_pointer(keepv);
1765 
1766  /* set e->vert pointers to restored vertex */
1767  e = newv->edge;
1768  do {
1769  e->vert = newv;
1770  e = p_wheel_edge_next(e);
1771  } while (e && (e != newv->edge));
1772 }
1773 
1774 static bool p_collapse_allowed_topologic(PEdge *edge, PEdge *pair)
1775 {
1776  PVert *oldv, *keepv;
1777 
1778  p_collapsing_verts(edge, pair, &oldv, &keepv);
1779 
1780  /* boundary edges */
1781  if (!edge || !pair) {
1782  /* avoid collapsing chart into an edge */
1783  if (edge && !edge->next->pair && !edge->next->next->pair) {
1784  return false;
1785  }
1786  else if (pair && !pair->next->pair && !pair->next->next->pair) {
1787  return false;
1788  }
1789  }
1790  /* avoid merging two boundaries (oldv and keepv are on the 'other side' of
1791  * the chart) */
1792  else if (!p_vert_interior(oldv) && !p_vert_interior(keepv)) {
1793  return false;
1794  }
1795 
1796  return true;
1797 }
1798 
1799 static bool p_collapse_normal_flipped(float *v1, float *v2, float *vold, float *vnew)
1800 {
1801  float nold[3], nnew[3], sub1[3], sub2[3];
1802 
1803  sub_v3_v3v3(sub1, vold, v1);
1804  sub_v3_v3v3(sub2, vold, v2);
1805  cross_v3_v3v3(nold, sub1, sub2);
1806 
1807  sub_v3_v3v3(sub1, vnew, v1);
1808  sub_v3_v3v3(sub2, vnew, v2);
1809  cross_v3_v3v3(nnew, sub1, sub2);
1810 
1811  return (dot_v3v3(nold, nnew) <= 0.0f);
1812 }
1813 
1814 static bool p_collapse_allowed_geometric(PEdge *edge, PEdge *pair)
1815 {
1816  PVert *oldv, *keepv;
1817  PEdge *e;
1818  float angulardefect, angle;
1819 
1820  p_collapsing_verts(edge, pair, &oldv, &keepv);
1821 
1822  angulardefect = 2 * M_PI;
1823 
1824  e = oldv->edge;
1825  do {
1826  float a[3], b[3], minangle, maxangle;
1827  PEdge *e1 = e->next, *e2 = e1->next;
1828  PVert *v1 = e1->vert, *v2 = e2->vert;
1829  int i;
1830 
1831  angle = p_vec_angle(v1->co, oldv->co, v2->co);
1832  angulardefect -= angle;
1833 
1834  /* skip collapsing faces */
1835  if (v1 == keepv || v2 == keepv) {
1836  e = p_wheel_edge_next(e);
1837  continue;
1838  }
1839 
1840  if (p_collapse_normal_flipped(v1->co, v2->co, oldv->co, keepv->co)) {
1841  return false;
1842  }
1843 
1844  a[0] = angle;
1845  a[1] = p_vec_angle(v2->co, v1->co, oldv->co);
1846  a[2] = M_PI - a[0] - a[1];
1847 
1848  b[0] = p_vec_angle(v1->co, keepv->co, v2->co);
1849  b[1] = p_vec_angle(v2->co, v1->co, keepv->co);
1850  b[2] = M_PI - b[0] - b[1];
1851 
1852  /* ABF criterion 1: avoid sharp and obtuse angles. */
1853  minangle = 15.0f * M_PI / 180.0f;
1854  maxangle = M_PI - minangle;
1855 
1856  for (i = 0; i < 3; i++) {
1857  if ((b[i] < a[i]) && (b[i] < minangle)) {
1858  return false;
1859  }
1860  else if ((b[i] > a[i]) && (b[i] > maxangle)) {
1861  return false;
1862  }
1863  }
1864 
1865  e = p_wheel_edge_next(e);
1866  } while (e && (e != oldv->edge));
1867 
1868  if (p_vert_interior(oldv)) {
1869  /* HLSCM criterion: angular defect smaller than threshold. */
1870  if (fabsf(angulardefect) > (float)(M_PI * 30.0 / 180.0)) {
1871  return false;
1872  }
1873  }
1874  else {
1875  PVert *v1 = p_boundary_edge_next(oldv->edge)->vert;
1876  PVert *v2 = p_boundary_edge_prev(oldv->edge)->vert;
1877 
1878  /* ABF++ criterion 2: avoid collapsing verts inwards. */
1879  if (p_vert_interior(keepv)) {
1880  return false;
1881  }
1882 
1883  /* Don't collapse significant boundary changes. */
1884  angle = p_vec_angle(v1->co, oldv->co, v2->co);
1885  if (angle < (M_PI * 160.0 / 180.0)) {
1886  return false;
1887  }
1888  }
1889 
1890  return true;
1891 }
1892 
1893 static bool p_collapse_allowed(PEdge *edge, PEdge *pair)
1894 {
1895  PVert *oldv, *keepv;
1896 
1897  p_collapsing_verts(edge, pair, &oldv, &keepv);
1898 
1899  if (oldv->flag & PVERT_PIN) {
1900  return false;
1901  }
1902 
1903  return (p_collapse_allowed_topologic(edge, pair) && p_collapse_allowed_geometric(edge, pair));
1904 }
1905 
1906 static float p_collapse_cost(PEdge *edge, PEdge *pair)
1907 {
1908  /* based on volume and boundary optimization from:
1909  * "Fast and Memory Efficient Polygonal Simplification" P. Lindstrom, G. Turk */
1910 
1911  PVert *oldv, *keepv;
1912  PEdge *e;
1913  PFace *oldf1, *oldf2;
1914  float volumecost = 0.0f, areacost = 0.0f, edgevec[3], cost, weight, elen;
1915  float shapecost = 0.0f;
1916  float shapeold = 0.0f, shapenew = 0.0f;
1917  int nshapeold = 0, nshapenew = 0;
1918 
1919  p_collapsing_verts(edge, pair, &oldv, &keepv);
1920  oldf1 = (edge) ? edge->face : NULL;
1921  oldf2 = (pair) ? pair->face : NULL;
1922 
1923  sub_v3_v3v3(edgevec, keepv->co, oldv->co);
1924 
1925  e = oldv->edge;
1926  do {
1927  float a1, a2, a3;
1928  float *co1 = e->next->vert->co;
1929  float *co2 = e->next->next->vert->co;
1930 
1931  if (!ELEM(e->face, oldf1, oldf2)) {
1932  float tetrav2[3], tetrav3[3];
1933 
1934  /* tetrahedron volume = (1/3!)*|a.(b x c)| */
1935  sub_v3_v3v3(tetrav2, co1, oldv->co);
1936  sub_v3_v3v3(tetrav3, co2, oldv->co);
1937  volumecost += fabsf(volume_tri_tetrahedron_signed_v3(tetrav2, tetrav3, edgevec));
1938 
1939 # if 0
1940  shapecost += dot_v3v3(co1, keepv->co);
1941 
1942  if (p_wheel_edge_next(e) == NULL) {
1943  shapecost += dot_v3v3(co2, keepv->co);
1944  }
1945 # endif
1946 
1947  p_triangle_angles(oldv->co, co1, co2, &a1, &a2, &a3);
1948  a1 = a1 - M_PI / 3.0;
1949  a2 = a2 - M_PI / 3.0;
1950  a3 = a3 - M_PI / 3.0;
1951  shapeold = (a1 * a1 + a2 * a2 + a3 * a3) / (M_PI_2 * M_PI_2);
1952 
1953  nshapeold++;
1954  }
1955  else {
1956  p_triangle_angles(keepv->co, co1, co2, &a1, &a2, &a3);
1957  a1 = a1 - M_PI / 3.0;
1958  a2 = a2 - M_PI / 3.0;
1959  a3 = a3 - M_PI / 3.0;
1960  shapenew = (a1 * a1 + a2 * a2 + a3 * a3) / (M_PI_2 * M_PI_2);
1961 
1962  nshapenew++;
1963  }
1964 
1965  e = p_wheel_edge_next(e);
1966  } while (e && (e != oldv->edge));
1967 
1968  if (!p_vert_interior(oldv)) {
1969  PVert *v1 = p_boundary_edge_prev(oldv->edge)->vert;
1970  PVert *v2 = p_boundary_edge_next(oldv->edge)->vert;
1971 
1972  areacost = area_tri_v3(oldv->co, v1->co, v2->co);
1973  }
1974 
1975  elen = len_v3(edgevec);
1976  weight = 1.0f; /* 0.2f */
1977  cost = weight * volumecost * volumecost + elen * elen * areacost * areacost;
1978 # if 0
1979  cost += shapecost;
1980 # else
1981  shapeold /= nshapeold;
1982  shapenew /= nshapenew;
1983  shapecost = (shapeold + 0.00001) / (shapenew + 0.00001);
1984 
1985  cost *= shapecost;
1986 # endif
1987 
1988  return cost;
1989 }
1990 
1991 static void p_collapse_cost_vertex(PVert *vert, float *r_mincost, PEdge **r_mine)
1992 {
1993  PEdge *e, *enext, *pair;
1994 
1995  *r_mine = NULL;
1996  *r_mincost = 0.0f;
1997  e = vert->edge;
1998  do {
1999  if (p_collapse_allowed(e, e->pair)) {
2000  float cost = p_collapse_cost(e, e->pair);
2001 
2002  if ((*r_mine == NULL) || (cost < *r_mincost)) {
2003  *r_mincost = cost;
2004  *r_mine = e;
2005  }
2006  }
2007 
2008  enext = p_wheel_edge_next(e);
2009 
2010  if (enext == NULL) {
2011  /* The other boundary edge, where we only have the pair half-edge. */
2012  pair = e->next->next;
2013 
2014  if (p_collapse_allowed(NULL, pair)) {
2015  float cost = p_collapse_cost(NULL, pair);
2016 
2017  if ((*r_mine == NULL) || (cost < *r_mincost)) {
2018  *r_mincost = cost;
2019  *r_mine = pair;
2020  }
2021  }
2022 
2023  break;
2024  }
2025 
2026  e = enext;
2027  } while (e != vert->edge);
2028 }
2029 
2030 static void p_chart_post_collapse_flush(PChart *chart, PEdge *collapsed)
2031 {
2032  /* Move to `collapsed_*`. */
2033 
2034  PVert *v, *nextv = NULL, *verts = chart->verts;
2035  PEdge *e, *nexte = NULL, *edges = chart->edges, *laste = NULL;
2036  PFace *f, *nextf = NULL, *faces = chart->faces;
2037 
2038  chart->verts = chart->collapsed_verts = NULL;
2039  chart->edges = chart->collapsed_edges = NULL;
2040  chart->faces = chart->collapsed_faces = NULL;
2041 
2042  chart->nverts = chart->nedges = chart->nfaces = 0;
2043 
2044  for (v = verts; v; v = nextv) {
2045  nextv = v->nextlink;
2046 
2047  if (v->flag & PVERT_COLLAPSE) {
2048  v->nextlink = chart->collapsed_verts;
2049  chart->collapsed_verts = v;
2050  }
2051  else {
2052  v->nextlink = chart->verts;
2053  chart->verts = v;
2054  chart->nverts++;
2055  }
2056  }
2057 
2058  for (e = edges; e; e = nexte) {
2059  nexte = e->nextlink;
2060 
2061  if (!collapsed || !(e->flag & PEDGE_COLLAPSE_EDGE)) {
2062  if (e->flag & PEDGE_COLLAPSE) {
2063  e->nextlink = chart->collapsed_edges;
2064  chart->collapsed_edges = e;
2065  }
2066  else {
2067  e->nextlink = chart->edges;
2068  chart->edges = e;
2069  chart->nedges++;
2070  }
2071  }
2072  }
2073 
2074  /* these are added last so they can be popped of in the right order
2075  * for splitting */
2076  for (e = collapsed; e; e = e->nextlink) {
2077  e->nextlink = e->u.nextcollapse;
2078  laste = e;
2079  }
2080  if (laste) {
2081  laste->nextlink = chart->collapsed_edges;
2082  chart->collapsed_edges = collapsed;
2083  }
2084 
2085  for (f = faces; f; f = nextf) {
2086  nextf = f->nextlink;
2087 
2088  if (f->flag & PFACE_COLLAPSE) {
2089  f->nextlink = chart->collapsed_faces;
2090  chart->collapsed_faces = f;
2091  }
2092  else {
2093  f->nextlink = chart->faces;
2094  chart->faces = f;
2095  chart->nfaces++;
2096  }
2097  }
2098 }
2099 
2100 static void p_chart_post_split_flush(PChart *chart)
2101 {
2102  /* Move from `collapsed_*`. */
2103 
2104  PVert *v, *nextv = NULL;
2105  PEdge *e, *nexte = NULL;
2106  PFace *f, *nextf = NULL;
2107 
2108  for (v = chart->collapsed_verts; v; v = nextv) {
2109  nextv = v->nextlink;
2110  v->nextlink = chart->verts;
2111  chart->verts = v;
2112  chart->nverts++;
2113  }
2114 
2115  for (e = chart->collapsed_edges; e; e = nexte) {
2116  nexte = e->nextlink;
2117  e->nextlink = chart->edges;
2118  chart->edges = e;
2119  chart->nedges++;
2120  }
2121 
2122  for (f = chart->collapsed_faces; f; f = nextf) {
2123  nextf = f->nextlink;
2124  f->nextlink = chart->faces;
2125  chart->faces = f;
2126  chart->nfaces++;
2127  }
2128 
2129  chart->collapsed_verts = NULL;
2130  chart->collapsed_edges = NULL;
2131  chart->collapsed_faces = NULL;
2132 }
2133 
2134 static void p_chart_simplify_compute(PChart *chart)
2135 {
2136  /* Computes a list of edge collapses / vertex splits. The collapsed
2137  * simplices go in the `chart->collapsed_*` lists, The original and
2138  * collapsed may then be view as stacks, where the next collapse/split
2139  * is at the top of the respective lists. */
2140 
2141  Heap *heap = BLI_heap_new();
2142  PVert *v, **wheelverts;
2143  PEdge *collapsededges = NULL, *e;
2144  int nwheelverts, i, ncollapsed = 0;
2145 
2146  wheelverts = MEM_mallocN(sizeof(PVert *) * chart->nverts, "PChartWheelVerts");
2147 
2148  /* insert all potential collapses into heap */
2149  for (v = chart->verts; v; v = v->nextlink) {
2150  float cost;
2151  PEdge *e = NULL;
2152 
2153  p_collapse_cost_vertex(v, &cost, &e);
2154 
2155  if (e) {
2156  v->u.heaplink = BLI_heap_insert(heap, cost, e);
2157  }
2158  else {
2159  v->u.heaplink = NULL;
2160  }
2161  }
2162 
2163  for (e = chart->edges; e; e = e->nextlink) {
2164  e->u.nextcollapse = NULL;
2165  }
2166 
2167  /* pop edge collapse out of heap one by one */
2168  while (!BLI_heap_is_empty(heap)) {
2169  if (ncollapsed == NCOLLAPSE) {
2170  break;
2171  }
2172 
2173  HeapNode *link = BLI_heap_top(heap);
2174  PEdge *edge = (PEdge *)BLI_heap_pop_min(heap), *pair = edge->pair;
2175  PVert *oldv, *keepv;
2176  PEdge *wheele, *nexte;
2177 
2178  /* remember the edges we collapsed */
2179  edge->u.nextcollapse = collapsededges;
2180  collapsededges = edge;
2181 
2182  if (edge->vert->u.heaplink != link) {
2184  edge->next->vert->u.heaplink = NULL;
2185  SWAP(PEdge *, edge, pair);
2186  }
2187  else {
2188  edge->flag |= PEDGE_COLLAPSE_EDGE;
2189  edge->vert->u.heaplink = NULL;
2190  }
2191 
2192  p_collapsing_verts(edge, pair, &oldv, &keepv);
2193 
2194  /* gather all wheel verts and remember them before collapse */
2195  nwheelverts = 0;
2196  wheele = oldv->edge;
2197 
2198  do {
2199  wheelverts[nwheelverts++] = wheele->next->vert;
2200  nexte = p_wheel_edge_next(wheele);
2201 
2202  if (nexte == NULL) {
2203  wheelverts[nwheelverts++] = wheele->next->next->vert;
2204  }
2205 
2206  wheele = nexte;
2207  } while (wheele && (wheele != oldv->edge));
2208 
2209  /* collapse */
2210  p_collapse_edge(edge, pair);
2211 
2212  for (i = 0; i < nwheelverts; i++) {
2213  float cost;
2214  PEdge *collapse = NULL;
2215 
2216  v = wheelverts[i];
2217 
2218  if (v->u.heaplink) {
2219  BLI_heap_remove(heap, v->u.heaplink);
2220  v->u.heaplink = NULL;
2221  }
2222 
2223  p_collapse_cost_vertex(v, &cost, &collapse);
2224 
2225  if (collapse) {
2226  v->u.heaplink = BLI_heap_insert(heap, cost, collapse);
2227  }
2228  }
2229 
2230  ncollapsed++;
2231  }
2232 
2233  MEM_freeN(wheelverts);
2234  BLI_heap_free(heap, NULL);
2235 
2236  p_chart_post_collapse_flush(chart, collapsededges);
2237 }
2238 
2239 static void p_chart_complexify(PChart *chart)
2240 {
2241  PEdge *e, *pair, *edge;
2242  PVert *newv, *keepv;
2243  int x = 0;
2244 
2245  for (e = chart->collapsed_edges; e; e = e->nextlink) {
2246  if (!(e->flag & PEDGE_COLLAPSE_EDGE)) {
2247  break;
2248  }
2249 
2250  edge = e;
2251  pair = e->pair;
2252 
2253  if (edge->flag & PEDGE_COLLAPSE_PAIR) {
2254  SWAP(PEdge *, edge, pair);
2255  }
2256 
2257  p_split_vertex(edge, pair);
2258  p_collapsing_verts(edge, pair, &newv, &keepv);
2259 
2260  if (x >= NCOLLAPSEX) {
2261  newv->uv[0] = keepv->uv[0];
2262  newv->uv[1] = keepv->uv[1];
2263  }
2264  else {
2265  p_vert_harmonic_insert(newv);
2266  x++;
2267  }
2268  }
2269 
2270  p_chart_post_split_flush(chart);
2271 }
2272 
2273 # if 0
2274 static void p_chart_simplify(PChart *chart)
2275 {
2276  /* Not implemented, needs proper reordering in split_flush. */
2277 }
2278 # endif
2279 #endif
2280 
2281 /* ABF */
2282 
2283 #define ABF_MAX_ITER 20
2284 
2285 typedef struct PAbfSystem {
2287  float *alpha, *beta, *sine, *cosine, *weight;
2290  float (*J2dt)[3], *bstar, *dstar;
2293 
2295 {
2296  int i;
2297 
2298  sys->alpha = (float *)MEM_mallocN(sizeof(float) * sys->nangles, "ABFalpha");
2299  sys->beta = (float *)MEM_mallocN(sizeof(float) * sys->nangles, "ABFbeta");
2300  sys->sine = (float *)MEM_mallocN(sizeof(float) * sys->nangles, "ABFsine");
2301  sys->cosine = (float *)MEM_mallocN(sizeof(float) * sys->nangles, "ABFcosine");
2302  sys->weight = (float *)MEM_mallocN(sizeof(float) * sys->nangles, "ABFweight");
2303 
2304  sys->bAlpha = (float *)MEM_mallocN(sizeof(float) * sys->nangles, "ABFbalpha");
2305  sys->bTriangle = (float *)MEM_mallocN(sizeof(float) * sys->nfaces, "ABFbtriangle");
2306  sys->bInterior = (float *)MEM_mallocN(sizeof(float[2]) * sys->ninterior, "ABFbinterior");
2307 
2308  sys->lambdaTriangle = (float *)MEM_callocN(sizeof(float) * sys->nfaces, "ABFlambdatri");
2309  sys->lambdaPlanar = (float *)MEM_callocN(sizeof(float) * sys->ninterior, "ABFlamdaplane");
2310  sys->lambdaLength = (float *)MEM_mallocN(sizeof(float) * sys->ninterior, "ABFlambdalen");
2311 
2312  sys->J2dt = MEM_mallocN(sizeof(float) * sys->nangles * 3, "ABFj2dt");
2313  sys->bstar = (float *)MEM_mallocN(sizeof(float) * sys->nfaces, "ABFbstar");
2314  sys->dstar = (float *)MEM_mallocN(sizeof(float) * sys->nfaces, "ABFdstar");
2315 
2316  for (i = 0; i < sys->ninterior; i++) {
2317  sys->lambdaLength[i] = 1.0;
2318  }
2319 
2320  sys->minangle = 1.0 * M_PI / 180.0;
2321  sys->maxangle = (float)M_PI - sys->minangle;
2322 }
2323 
2325 {
2326  MEM_freeN(sys->alpha);
2327  MEM_freeN(sys->beta);
2328  MEM_freeN(sys->sine);
2329  MEM_freeN(sys->cosine);
2330  MEM_freeN(sys->weight);
2331  MEM_freeN(sys->bAlpha);
2332  MEM_freeN(sys->bTriangle);
2333  MEM_freeN(sys->bInterior);
2334  MEM_freeN(sys->lambdaTriangle);
2335  MEM_freeN(sys->lambdaPlanar);
2336  MEM_freeN(sys->lambdaLength);
2337  MEM_freeN(sys->J2dt);
2338  MEM_freeN(sys->bstar);
2339  MEM_freeN(sys->dstar);
2340 }
2341 
2343 {
2344  int i;
2345  float *sine = sys->sine, *cosine = sys->cosine, *alpha = sys->alpha;
2346 
2347  for (i = 0; i < sys->nangles; i++, sine++, cosine++, alpha++) {
2348  *sine = sinf(*alpha);
2349  *cosine = cosf(*alpha);
2350  }
2351 }
2352 
2353 static float p_abf_compute_sin_product(PAbfSystem *sys, PVert *v, int aid)
2354 {
2355  PEdge *e, *e1, *e2;
2356  float sin1, sin2;
2357 
2358  sin1 = sin2 = 1.0;
2359 
2360  e = v->edge;
2361  do {
2362  e1 = e->next;
2363  e2 = e->next->next;
2364 
2365  if (aid == e1->u.id) {
2366  /* we are computing a derivative for this angle,
2367  * so we use cos and drop the other part */
2368  sin1 *= sys->cosine[e1->u.id];
2369  sin2 = 0.0;
2370  }
2371  else {
2372  sin1 *= sys->sine[e1->u.id];
2373  }
2374 
2375  if (aid == e2->u.id) {
2376  /* see above */
2377  sin1 = 0.0;
2378  sin2 *= sys->cosine[e2->u.id];
2379  }
2380  else {
2381  sin2 *= sys->sine[e2->u.id];
2382  }
2383 
2384  e = e->next->next->pair;
2385  } while (e && (e != v->edge));
2386 
2387  return (sin1 - sin2);
2388 }
2389 
2391 {
2392  PVert *v = e->vert, *v1 = e->next->vert, *v2 = e->next->next->vert;
2393  float deriv;
2394 
2395  deriv = (sys->alpha[e->u.id] - sys->beta[e->u.id]) * sys->weight[e->u.id];
2396  deriv += sys->lambdaTriangle[f->u.id];
2397 
2398  if (v->flag & PVERT_INTERIOR) {
2399  deriv += sys->lambdaPlanar[v->u.id];
2400  }
2401 
2402  if (v1->flag & PVERT_INTERIOR) {
2403  float product = p_abf_compute_sin_product(sys, v1, e->u.id);
2404  deriv += sys->lambdaLength[v1->u.id] * product;
2405  }
2406 
2407  if (v2->flag & PVERT_INTERIOR) {
2408  float product = p_abf_compute_sin_product(sys, v2, e->u.id);
2409  deriv += sys->lambdaLength[v2->u.id] * product;
2410  }
2411 
2412  return deriv;
2413 }
2414 
2415 static float p_abf_compute_gradient(PAbfSystem *sys, PChart *chart)
2416 {
2417  PFace *f;
2418  PEdge *e;
2419  PVert *v;
2420  float norm = 0.0;
2421 
2422  for (f = chart->faces; f; f = f->nextlink) {
2423  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
2424  float gtriangle, galpha1, galpha2, galpha3;
2425 
2426  galpha1 = p_abf_compute_grad_alpha(sys, f, e1);
2427  galpha2 = p_abf_compute_grad_alpha(sys, f, e2);
2428  galpha3 = p_abf_compute_grad_alpha(sys, f, e3);
2429 
2430  sys->bAlpha[e1->u.id] = -galpha1;
2431  sys->bAlpha[e2->u.id] = -galpha2;
2432  sys->bAlpha[e3->u.id] = -galpha3;
2433 
2434  norm += galpha1 * galpha1 + galpha2 * galpha2 + galpha3 * galpha3;
2435 
2436  gtriangle = sys->alpha[e1->u.id] + sys->alpha[e2->u.id] + sys->alpha[e3->u.id] - (float)M_PI;
2437  sys->bTriangle[f->u.id] = -gtriangle;
2438  norm += gtriangle * gtriangle;
2439  }
2440 
2441  for (v = chart->verts; v; v = v->nextlink) {
2442  if (v->flag & PVERT_INTERIOR) {
2443  float gplanar = -2 * M_PI, glength;
2444 
2445  e = v->edge;
2446  do {
2447  gplanar += sys->alpha[e->u.id];
2448  e = e->next->next->pair;
2449  } while (e && (e != v->edge));
2450 
2451  sys->bInterior[v->u.id] = -gplanar;
2452  norm += gplanar * gplanar;
2453 
2454  glength = p_abf_compute_sin_product(sys, v, -1);
2455  sys->bInterior[sys->ninterior + v->u.id] = -glength;
2456  norm += glength * glength;
2457  }
2458  }
2459 
2460  return norm;
2461 }
2462 
2463 static bool p_abf_matrix_invert(PAbfSystem *sys, PChart *chart)
2464 {
2465  int ninterior = sys->ninterior;
2466  int nvar = 2 * ninterior;
2468 
2469  for (int i = 0; i < nvar; i++) {
2471  }
2472 
2473  for (PFace *f = chart->faces; f; f = f->nextlink) {
2474  float wi1, wi2, wi3, b, si, beta[3], j2[3][3], W[3][3];
2475  float row1[6], row2[6], row3[6];
2476  int vid[6];
2477  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
2478  PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
2479 
2480  wi1 = 1.0f / sys->weight[e1->u.id];
2481  wi2 = 1.0f / sys->weight[e2->u.id];
2482  wi3 = 1.0f / sys->weight[e3->u.id];
2483 
2484  /* bstar1 = (J1*dInv*bAlpha - bTriangle) */
2485  b = sys->bAlpha[e1->u.id] * wi1;
2486  b += sys->bAlpha[e2->u.id] * wi2;
2487  b += sys->bAlpha[e3->u.id] * wi3;
2488  b -= sys->bTriangle[f->u.id];
2489 
2490  /* si = J1*d*J1t */
2491  si = 1.0f / (wi1 + wi2 + wi3);
2492 
2493  /* J1t*si*bstar1 - bAlpha */
2494  beta[0] = b * si - sys->bAlpha[e1->u.id];
2495  beta[1] = b * si - sys->bAlpha[e2->u.id];
2496  beta[2] = b * si - sys->bAlpha[e3->u.id];
2497 
2498  /* use this later for computing other lambda's */
2499  sys->bstar[f->u.id] = b;
2500  sys->dstar[f->u.id] = si;
2501 
2502  /* set matrix */
2503  W[0][0] = si - sys->weight[e1->u.id];
2504  W[0][1] = si;
2505  W[0][2] = si;
2506  W[1][0] = si;
2507  W[1][1] = si - sys->weight[e2->u.id];
2508  W[1][2] = si;
2509  W[2][0] = si;
2510  W[2][1] = si;
2511  W[2][2] = si - sys->weight[e3->u.id];
2512 
2513  vid[0] = vid[1] = vid[2] = vid[3] = vid[4] = vid[5] = -1;
2514 
2515  if (v1->flag & PVERT_INTERIOR) {
2516  vid[0] = v1->u.id;
2517  vid[3] = ninterior + v1->u.id;
2518 
2519  sys->J2dt[e1->u.id][0] = j2[0][0] = 1.0f * wi1;
2520  sys->J2dt[e2->u.id][0] = j2[1][0] = p_abf_compute_sin_product(sys, v1, e2->u.id) * wi2;
2521  sys->J2dt[e3->u.id][0] = j2[2][0] = p_abf_compute_sin_product(sys, v1, e3->u.id) * wi3;
2522 
2523  EIG_linear_solver_right_hand_side_add(context, 0, v1->u.id, j2[0][0] * beta[0]);
2525  context, 0, ninterior + v1->u.id, j2[1][0] * beta[1] + j2[2][0] * beta[2]);
2526 
2527  row1[0] = j2[0][0] * W[0][0];
2528  row2[0] = j2[0][0] * W[1][0];
2529  row3[0] = j2[0][0] * W[2][0];
2530 
2531  row1[3] = j2[1][0] * W[0][1] + j2[2][0] * W[0][2];
2532  row2[3] = j2[1][0] * W[1][1] + j2[2][0] * W[1][2];
2533  row3[3] = j2[1][0] * W[2][1] + j2[2][0] * W[2][2];
2534  }
2535 
2536  if (v2->flag & PVERT_INTERIOR) {
2537  vid[1] = v2->u.id;
2538  vid[4] = ninterior + v2->u.id;
2539 
2540  sys->J2dt[e1->u.id][1] = j2[0][1] = p_abf_compute_sin_product(sys, v2, e1->u.id) * wi1;
2541  sys->J2dt[e2->u.id][1] = j2[1][1] = 1.0f * wi2;
2542  sys->J2dt[e3->u.id][1] = j2[2][1] = p_abf_compute_sin_product(sys, v2, e3->u.id) * wi3;
2543 
2544  EIG_linear_solver_right_hand_side_add(context, 0, v2->u.id, j2[1][1] * beta[1]);
2546  context, 0, ninterior + v2->u.id, j2[0][1] * beta[0] + j2[2][1] * beta[2]);
2547 
2548  row1[1] = j2[1][1] * W[0][1];
2549  row2[1] = j2[1][1] * W[1][1];
2550  row3[1] = j2[1][1] * W[2][1];
2551 
2552  row1[4] = j2[0][1] * W[0][0] + j2[2][1] * W[0][2];
2553  row2[4] = j2[0][1] * W[1][0] + j2[2][1] * W[1][2];
2554  row3[4] = j2[0][1] * W[2][0] + j2[2][1] * W[2][2];
2555  }
2556 
2557  if (v3->flag & PVERT_INTERIOR) {
2558  vid[2] = v3->u.id;
2559  vid[5] = ninterior + v3->u.id;
2560 
2561  sys->J2dt[e1->u.id][2] = j2[0][2] = p_abf_compute_sin_product(sys, v3, e1->u.id) * wi1;
2562  sys->J2dt[e2->u.id][2] = j2[1][2] = p_abf_compute_sin_product(sys, v3, e2->u.id) * wi2;
2563  sys->J2dt[e3->u.id][2] = j2[2][2] = 1.0f * wi3;
2564 
2565  EIG_linear_solver_right_hand_side_add(context, 0, v3->u.id, j2[2][2] * beta[2]);
2567  context, 0, ninterior + v3->u.id, j2[0][2] * beta[0] + j2[1][2] * beta[1]);
2568 
2569  row1[2] = j2[2][2] * W[0][2];
2570  row2[2] = j2[2][2] * W[1][2];
2571  row3[2] = j2[2][2] * W[2][2];
2572 
2573  row1[5] = j2[0][2] * W[0][0] + j2[1][2] * W[0][1];
2574  row2[5] = j2[0][2] * W[1][0] + j2[1][2] * W[1][1];
2575  row3[5] = j2[0][2] * W[2][0] + j2[1][2] * W[2][1];
2576  }
2577 
2578  for (int i = 0; i < 3; i++) {
2579  int r = vid[i];
2580 
2581  if (r == -1) {
2582  continue;
2583  }
2584 
2585  for (int j = 0; j < 6; j++) {
2586  int c = vid[j];
2587 
2588  if (c == -1) {
2589  continue;
2590  }
2591 
2592  if (i == 0) {
2593  EIG_linear_solver_matrix_add(context, r, c, j2[0][i] * row1[j]);
2594  }
2595  else {
2596  EIG_linear_solver_matrix_add(context, r + ninterior, c, j2[0][i] * row1[j]);
2597  }
2598 
2599  if (i == 1) {
2600  EIG_linear_solver_matrix_add(context, r, c, j2[1][i] * row2[j]);
2601  }
2602  else {
2603  EIG_linear_solver_matrix_add(context, r + ninterior, c, j2[1][i] * row2[j]);
2604  }
2605 
2606  if (i == 2) {
2607  EIG_linear_solver_matrix_add(context, r, c, j2[2][i] * row3[j]);
2608  }
2609  else {
2610  EIG_linear_solver_matrix_add(context, r + ninterior, c, j2[2][i] * row3[j]);
2611  }
2612  }
2613  }
2614  }
2615 
2616  bool success = EIG_linear_solver_solve(context);
2617 
2618  if (success) {
2619  for (PFace *f = chart->faces; f; f = f->nextlink) {
2620  float dlambda1, pre[3], dalpha;
2621  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
2622  PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
2623 
2624  pre[0] = pre[1] = pre[2] = 0.0;
2625 
2626  if (v1->flag & PVERT_INTERIOR) {
2627  float x = EIG_linear_solver_variable_get(context, 0, v1->u.id);
2628  float x2 = EIG_linear_solver_variable_get(context, 0, ninterior + v1->u.id);
2629  pre[0] += sys->J2dt[e1->u.id][0] * x;
2630  pre[1] += sys->J2dt[e2->u.id][0] * x2;
2631  pre[2] += sys->J2dt[e3->u.id][0] * x2;
2632  }
2633 
2634  if (v2->flag & PVERT_INTERIOR) {
2635  float x = EIG_linear_solver_variable_get(context, 0, v2->u.id);
2636  float x2 = EIG_linear_solver_variable_get(context, 0, ninterior + v2->u.id);
2637  pre[0] += sys->J2dt[e1->u.id][1] * x2;
2638  pre[1] += sys->J2dt[e2->u.id][1] * x;
2639  pre[2] += sys->J2dt[e3->u.id][1] * x2;
2640  }
2641 
2642  if (v3->flag & PVERT_INTERIOR) {
2643  float x = EIG_linear_solver_variable_get(context, 0, v3->u.id);
2644  float x2 = EIG_linear_solver_variable_get(context, 0, ninterior + v3->u.id);
2645  pre[0] += sys->J2dt[e1->u.id][2] * x2;
2646  pre[1] += sys->J2dt[e2->u.id][2] * x2;
2647  pre[2] += sys->J2dt[e3->u.id][2] * x;
2648  }
2649 
2650  dlambda1 = pre[0] + pre[1] + pre[2];
2651  dlambda1 = sys->dstar[f->u.id] * (sys->bstar[f->u.id] - dlambda1);
2652 
2653  sys->lambdaTriangle[f->u.id] += dlambda1;
2654 
2655  dalpha = (sys->bAlpha[e1->u.id] - dlambda1);
2656  sys->alpha[e1->u.id] += dalpha / sys->weight[e1->u.id] - pre[0];
2657 
2658  dalpha = (sys->bAlpha[e2->u.id] - dlambda1);
2659  sys->alpha[e2->u.id] += dalpha / sys->weight[e2->u.id] - pre[1];
2660 
2661  dalpha = (sys->bAlpha[e3->u.id] - dlambda1);
2662  sys->alpha[e3->u.id] += dalpha / sys->weight[e3->u.id] - pre[2];
2663 
2664  /* clamp */
2665  PEdge *e = f->edge;
2666  do {
2667  if (sys->alpha[e->u.id] > (float)M_PI) {
2668  sys->alpha[e->u.id] = (float)M_PI;
2669  }
2670  else if (sys->alpha[e->u.id] < 0.0f) {
2671  sys->alpha[e->u.id] = 0.0f;
2672  }
2673  } while (e != f->edge);
2674  }
2675 
2676  for (int i = 0; i < ninterior; i++) {
2678  sys->lambdaLength[i] += (float)EIG_linear_solver_variable_get(context, 0, ninterior + i);
2679  }
2680  }
2681 
2683 
2684  return success;
2685 }
2686 
2687 static bool p_chart_abf_solve(PChart *chart)
2688 {
2689  PVert *v;
2690  PFace *f;
2691  PEdge *e, *e1, *e2, *e3;
2692  PAbfSystem sys;
2693  int i;
2694  float /* lastnorm, */ /* UNUSED */ limit = (chart->nfaces > 100) ? 1.0f : 0.001f;
2695 
2696  /* setup id's */
2697  sys.ninterior = sys.nfaces = sys.nangles = 0;
2698 
2699  for (v = chart->verts; v; v = v->nextlink) {
2700  if (p_vert_interior(v)) {
2701  v->flag |= PVERT_INTERIOR;
2702  v->u.id = sys.ninterior++;
2703  }
2704  else {
2705  v->flag &= ~PVERT_INTERIOR;
2706  }
2707  }
2708 
2709  for (f = chart->faces; f; f = f->nextlink) {
2710  e1 = f->edge;
2711  e2 = e1->next;
2712  e3 = e2->next;
2713  f->u.id = sys.nfaces++;
2714 
2715  /* angle id's are conveniently stored in half edges */
2716  e1->u.id = sys.nangles++;
2717  e2->u.id = sys.nangles++;
2718  e3->u.id = sys.nangles++;
2719  }
2720 
2721  p_abf_setup_system(&sys);
2722 
2723  /* compute initial angles */
2724  for (f = chart->faces; f; f = f->nextlink) {
2725  float a1, a2, a3;
2726 
2727  e1 = f->edge;
2728  e2 = e1->next;
2729  e3 = e2->next;
2730  p_face_angles(f, &a1, &a2, &a3);
2731 
2732  if (a1 < sys.minangle) {
2733  a1 = sys.minangle;
2734  }
2735  else if (a1 > sys.maxangle) {
2736  a1 = sys.maxangle;
2737  }
2738  if (a2 < sys.minangle) {
2739  a2 = sys.minangle;
2740  }
2741  else if (a2 > sys.maxangle) {
2742  a2 = sys.maxangle;
2743  }
2744  if (a3 < sys.minangle) {
2745  a3 = sys.minangle;
2746  }
2747  else if (a3 > sys.maxangle) {
2748  a3 = sys.maxangle;
2749  }
2750 
2751  sys.alpha[e1->u.id] = sys.beta[e1->u.id] = a1;
2752  sys.alpha[e2->u.id] = sys.beta[e2->u.id] = a2;
2753  sys.alpha[e3->u.id] = sys.beta[e3->u.id] = a3;
2754 
2755  sys.weight[e1->u.id] = 2.0f / (a1 * a1);
2756  sys.weight[e2->u.id] = 2.0f / (a2 * a2);
2757  sys.weight[e3->u.id] = 2.0f / (a3 * a3);
2758  }
2759 
2760  for (v = chart->verts; v; v = v->nextlink) {
2761  if (v->flag & PVERT_INTERIOR) {
2762  float anglesum = 0.0, scale;
2763 
2764  e = v->edge;
2765  do {
2766  anglesum += sys.beta[e->u.id];
2767  e = e->next->next->pair;
2768  } while (e && (e != v->edge));
2769 
2770  scale = (anglesum == 0.0f) ? 0.0f : 2.0f * (float)M_PI / anglesum;
2771 
2772  e = v->edge;
2773  do {
2774  sys.beta[e->u.id] = sys.alpha[e->u.id] = sys.beta[e->u.id] * scale;
2775  e = e->next->next->pair;
2776  } while (e && (e != v->edge));
2777  }
2778  }
2779 
2780  if (sys.ninterior > 0) {
2781  p_abf_compute_sines(&sys);
2782 
2783  /* iteration */
2784  /* lastnorm = 1e10; */ /* UNUSED */
2785 
2786  for (i = 0; i < ABF_MAX_ITER; i++) {
2787  float norm = p_abf_compute_gradient(&sys, chart);
2788 
2789  /* lastnorm = norm; */ /* UNUSED */
2790 
2791  if (norm < limit) {
2792  break;
2793  }
2794 
2795  if (!p_abf_matrix_invert(&sys, chart)) {
2796  param_warning("ABF failed to invert matrix");
2797  p_abf_free_system(&sys);
2798  return false;
2799  }
2800 
2801  p_abf_compute_sines(&sys);
2802  }
2803 
2804  if (i == ABF_MAX_ITER) {
2805  param_warning("ABF maximum iterations reached");
2806  p_abf_free_system(&sys);
2807  return false;
2808  }
2809  }
2810 
2811  chart->u.lscm.abf_alpha = MEM_dupallocN(sys.alpha);
2812  p_abf_free_system(&sys);
2813 
2814  return true;
2815 }
2816 
2817 /* Least Squares Conformal Maps */
2818 
2819 static void p_chart_pin_positions(PChart *chart, PVert **pin1, PVert **pin2)
2820 {
2821  if (!*pin1 || !*pin2 || *pin1 == *pin2) {
2822  /* degenerate case */
2823  PFace *f = chart->faces;
2824  *pin1 = f->edge->vert;
2825  *pin2 = f->edge->next->vert;
2826 
2827  (*pin1)->uv[0] = 0.0f;
2828  (*pin1)->uv[1] = 0.5f;
2829  (*pin2)->uv[0] = 1.0f;
2830  (*pin2)->uv[1] = 0.5f;
2831  }
2832  else {
2833  int diru, dirv, dirx, diry;
2834  float sub[3];
2835 
2836  sub_v3_v3v3(sub, (*pin1)->co, (*pin2)->co);
2837  sub[0] = fabsf(sub[0]);
2838  sub[1] = fabsf(sub[1]);
2839  sub[2] = fabsf(sub[2]);
2840 
2841  if ((sub[0] > sub[1]) && (sub[0] > sub[2])) {
2842  dirx = 0;
2843  diry = (sub[1] > sub[2]) ? 1 : 2;
2844  }
2845  else if ((sub[1] > sub[0]) && (sub[1] > sub[2])) {
2846  dirx = 1;
2847  diry = (sub[0] > sub[2]) ? 0 : 2;
2848  }
2849  else {
2850  dirx = 2;
2851  diry = (sub[0] > sub[1]) ? 0 : 1;
2852  }
2853 
2854  if (dirx == 2) {
2855  diru = 1;
2856  dirv = 0;
2857  }
2858  else {
2859  diru = 0;
2860  dirv = 1;
2861  }
2862 
2863  (*pin1)->uv[diru] = (*pin1)->co[dirx];
2864  (*pin1)->uv[dirv] = (*pin1)->co[diry];
2865  (*pin2)->uv[diru] = (*pin2)->co[dirx];
2866  (*pin2)->uv[dirv] = (*pin2)->co[diry];
2867  }
2868 }
2869 
2870 static bool p_chart_symmetry_pins(PChart *chart, PEdge *outer, PVert **pin1, PVert **pin2)
2871 {
2872  PEdge *be, *lastbe = NULL, *maxe1 = NULL, *maxe2 = NULL, *be1, *be2;
2873  PEdge *cure = NULL, *firste1 = NULL, *firste2 = NULL, *nextbe;
2874  float maxlen = 0.0f, curlen = 0.0f, totlen = 0.0f, firstlen = 0.0f;
2875  float len1, len2;
2876 
2877  /* find longest series of verts split in the chart itself, these are
2878  * marked during construction */
2879  be = outer;
2880  lastbe = p_boundary_edge_prev(be);
2881  do {
2882  float len = p_edge_length(be);
2883  totlen += len;
2884 
2885  nextbe = p_boundary_edge_next(be);
2886 
2887  if ((be->vert->flag & PVERT_SPLIT) ||
2888  (lastbe->vert->flag & nextbe->vert->flag & PVERT_SPLIT)) {
2889  if (!cure) {
2890  if (be == outer) {
2891  firste1 = be;
2892  }
2893  cure = be;
2894  }
2895  else {
2896  curlen += p_edge_length(lastbe);
2897  }
2898  }
2899  else if (cure) {
2900  if (curlen > maxlen) {
2901  maxlen = curlen;
2902  maxe1 = cure;
2903  maxe2 = lastbe;
2904  }
2905 
2906  if (firste1 == cure) {
2907  firstlen = curlen;
2908  firste2 = lastbe;
2909  }
2910 
2911  curlen = 0.0f;
2912  cure = NULL;
2913  }
2914 
2915  lastbe = be;
2916  be = nextbe;
2917  } while (be != outer);
2918 
2919  /* make sure we also count a series of splits over the starting point */
2920  if (cure && (cure != outer)) {
2921  firstlen += curlen + p_edge_length(be);
2922 
2923  if (firstlen > maxlen) {
2924  maxlen = firstlen;
2925  maxe1 = cure;
2926  maxe2 = firste2;
2927  }
2928  }
2929 
2930  if (!maxe1 || !maxe2 || (maxlen < 0.5f * totlen)) {
2931  return false;
2932  }
2933 
2934  /* find pin1 in the split vertices */
2935  be1 = maxe1;
2936  be2 = maxe2;
2937  len1 = 0.0f;
2938  len2 = 0.0f;
2939 
2940  do {
2941  if (len1 < len2) {
2942  len1 += p_edge_length(be1);
2943  be1 = p_boundary_edge_next(be1);
2944  }
2945  else {
2946  be2 = p_boundary_edge_prev(be2);
2947  len2 += p_edge_length(be2);
2948  }
2949  } while (be1 != be2);
2950 
2951  *pin1 = be1->vert;
2952 
2953  /* find pin2 outside the split vertices */
2954  be1 = maxe1;
2955  be2 = maxe2;
2956  len1 = 0.0f;
2957  len2 = 0.0f;
2958 
2959  do {
2960  if (len1 < len2) {
2961  be1 = p_boundary_edge_prev(be1);
2962  len1 += p_edge_length(be1);
2963  }
2964  else {
2965  len2 += p_edge_length(be2);
2966  be2 = p_boundary_edge_next(be2);
2967  }
2968  } while (be1 != be2);
2969 
2970  *pin2 = be1->vert;
2971 
2972  p_chart_pin_positions(chart, pin1, pin2);
2973 
2974  return !equals_v3v3((*pin1)->co, (*pin2)->co);
2975 }
2976 
2977 static void p_chart_extrema_verts(PChart *chart, PVert **pin1, PVert **pin2)
2978 {
2979  float minv[3], maxv[3], dirlen;
2980  PVert *v, *minvert[3], *maxvert[3];
2981  int i, dir;
2982 
2983  /* find minimum and maximum verts over x/y/z axes */
2984  minv[0] = minv[1] = minv[2] = 1e20;
2985  maxv[0] = maxv[1] = maxv[2] = -1e20;
2986 
2987  minvert[0] = minvert[1] = minvert[2] = NULL;
2988  maxvert[0] = maxvert[1] = maxvert[2] = NULL;
2989 
2990  for (v = chart->verts; v; v = v->nextlink) {
2991  for (i = 0; i < 3; i++) {
2992  if (v->co[i] < minv[i]) {
2993  minv[i] = v->co[i];
2994  minvert[i] = v;
2995  }
2996  if (v->co[i] > maxv[i]) {
2997  maxv[i] = v->co[i];
2998  maxvert[i] = v;
2999  }
3000  }
3001  }
3002 
3003  /* find axes with longest distance */
3004  dir = 0;
3005  dirlen = -1.0;
3006 
3007  for (i = 0; i < 3; i++) {
3008  if (maxv[i] - minv[i] > dirlen) {
3009  dir = i;
3010  dirlen = maxv[i] - minv[i];
3011  }
3012  }
3013 
3014  *pin1 = minvert[dir];
3015  *pin2 = maxvert[dir];
3016 
3017  p_chart_pin_positions(chart, pin1, pin2);
3018 }
3019 
3021 {
3022  LinearSolver *context = chart->u.lscm.context;
3023  PVert *v;
3024 
3025  for (v = chart->verts; v; v = v->nextlink) {
3026  v->uv[0] = EIG_linear_solver_variable_get(context, 0, 2 * v->u.id);
3027  v->uv[1] = EIG_linear_solver_variable_get(context, 0, 2 * v->u.id + 1);
3028  }
3029 }
3030 
3031 static void p_chart_lscm_begin(PChart *chart, bool live, bool abf)
3032 {
3033  PVert *v, *pin1, *pin2;
3034  bool select = false, deselect = false;
3035  int npins = 0, id = 0;
3036 
3037  /* give vertices matrix indices and count pins */
3038  for (v = chart->verts; v; v = v->nextlink) {
3039  if (v->flag & PVERT_PIN) {
3040  npins++;
3041  if (v->flag & PVERT_SELECT) {
3042  select = true;
3043  }
3044  }
3045 
3046  if (!(v->flag & PVERT_SELECT)) {
3047  deselect = true;
3048  }
3049  }
3050 
3051  if ((live && (!select || !deselect))) {
3052  chart->u.lscm.context = NULL;
3053  }
3054  else {
3055 #if 0
3056  p_chart_simplify_compute(chart);
3057  p_chart_topological_sanity_check(chart);
3058 #endif
3059 
3060  if (npins == 1) {
3061  chart->u.lscm.single_pin_area = p_chart_uv_area(chart);
3062  for (v = chart->verts; v; v = v->nextlink) {
3063  if (v->flag & PVERT_PIN) {
3064  chart->u.lscm.single_pin = v;
3065  break;
3066  }
3067  }
3068  }
3069 
3070  if (abf) {
3071  if (!p_chart_abf_solve(chart)) {
3072  param_warning("ABF solving failed: falling back to LSCM.\n");
3073  }
3074  }
3075 
3076  if (npins <= 1) {
3077  /* No pins, let's find some ourself. */
3078  PEdge *outer;
3079 
3080  p_chart_boundaries(chart, &outer);
3081 
3082  /* Outer can be NULL with non-finite coords. */
3083  if (!(outer && p_chart_symmetry_pins(chart, outer, &pin1, &pin2))) {
3084  p_chart_extrema_verts(chart, &pin1, &pin2);
3085  }
3086 
3087  chart->u.lscm.pin1 = pin1;
3088  chart->u.lscm.pin2 = pin2;
3089  }
3090 
3091  for (v = chart->verts; v; v = v->nextlink) {
3092  v->u.id = id++;
3093  }
3094 
3096  2 * chart->nfaces, 2 * chart->nverts, 1);
3097  }
3098 }
3099 
3100 static bool p_chart_lscm_solve(ParamHandle *handle, PChart *chart)
3101 {
3102  LinearSolver *context = chart->u.lscm.context;
3103  PVert *v, *pin1 = chart->u.lscm.pin1, *pin2 = chart->u.lscm.pin2;
3104  PFace *f;
3105  const float *alpha = chart->u.lscm.abf_alpha;
3106  float area_pinned_up, area_pinned_down;
3107  bool flip_faces;
3108  int row;
3109 
3110 #if 0
3111  /* TODO: make loading pins work for simplify/complexify. */
3112 #endif
3113 
3114  for (v = chart->verts; v; v = v->nextlink) {
3115  if (v->flag & PVERT_PIN) {
3116  p_vert_load_pin_select_uvs(handle, v); /* reload for live */
3117  }
3118  }
3119 
3120  if (chart->u.lscm.single_pin) {
3121  /* If only one pin, save area and pin for transform later. */
3122  copy_v2_v2(chart->u.lscm.single_pin_uv, chart->u.lscm.single_pin->uv);
3123  }
3124 
3125  if (chart->u.lscm.pin1) {
3127  EIG_linear_solver_variable_lock(context, 2 * pin1->u.id + 1);
3128  EIG_linear_solver_variable_lock(context, 2 * pin2->u.id);
3129  EIG_linear_solver_variable_lock(context, 2 * pin2->u.id + 1);
3130 
3131  EIG_linear_solver_variable_set(context, 0, 2 * pin1->u.id, pin1->uv[0]);
3132  EIG_linear_solver_variable_set(context, 0, 2 * pin1->u.id + 1, pin1->uv[1]);
3133  EIG_linear_solver_variable_set(context, 0, 2 * pin2->u.id, pin2->uv[0]);
3134  EIG_linear_solver_variable_set(context, 0, 2 * pin2->u.id + 1, pin2->uv[1]);
3135  }
3136  else {
3137  /* set and lock the pins */
3138  for (v = chart->verts; v; v = v->nextlink) {
3139  if (v->flag & PVERT_PIN) {
3141  EIG_linear_solver_variable_lock(context, 2 * v->u.id + 1);
3142 
3143  EIG_linear_solver_variable_set(context, 0, 2 * v->u.id, v->uv[0]);
3144  EIG_linear_solver_variable_set(context, 0, 2 * v->u.id + 1, v->uv[1]);
3145  }
3146  }
3147  }
3148 
3149  /* detect up direction based on pinned vertices */
3150  area_pinned_up = 0.0f;
3151  area_pinned_down = 0.0f;
3152 
3153  for (f = chart->faces; f; f = f->nextlink) {
3154  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
3155  PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
3156 
3157  if ((v1->flag & PVERT_PIN) && (v2->flag & PVERT_PIN) && (v3->flag & PVERT_PIN)) {
3158  float area = p_face_uv_area_signed(f);
3159 
3160  if (area > 0.0f) {
3161  area_pinned_up += area;
3162  }
3163  else {
3164  area_pinned_down -= area;
3165  }
3166  }
3167  }
3168 
3169  flip_faces = (area_pinned_down > area_pinned_up);
3170 
3171  /* construct matrix */
3172 
3173  row = 0;
3174  for (f = chart->faces; f; f = f->nextlink) {
3175  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
3176  PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
3177  float a1, a2, a3, ratio, cosine, sine;
3178  float sina1, sina2, sina3, sinmax;
3179 
3180  if (alpha) {
3181  /* use abf angles if passed on */
3182  a1 = *(alpha++);
3183  a2 = *(alpha++);
3184  a3 = *(alpha++);
3185  }
3186  else {
3187  p_face_angles(f, &a1, &a2, &a3);
3188  }
3189 
3190  if (flip_faces) {
3191  SWAP(float, a2, a3);
3192  SWAP(PEdge *, e2, e3);
3193  SWAP(PVert *, v2, v3);
3194  }
3195 
3196  sina1 = sinf(a1);
3197  sina2 = sinf(a2);
3198  sina3 = sinf(a3);
3199 
3200  sinmax = max_fff(sina1, sina2, sina3);
3201 
3202  /* shift vertices to find most stable order */
3203  if (sina3 != sinmax) {
3204  SHIFT3(PVert *, v1, v2, v3);
3205  SHIFT3(float, a1, a2, a3);
3206  SHIFT3(float, sina1, sina2, sina3);
3207 
3208  if (sina2 == sinmax) {
3209  SHIFT3(PVert *, v1, v2, v3);
3210  SHIFT3(float, a1, a2, a3);
3211  SHIFT3(float, sina1, sina2, sina3);
3212  }
3213  }
3214 
3215  /* angle based lscm formulation */
3216  ratio = (sina3 == 0.0f) ? 1.0f : sina2 / sina3;
3217  cosine = cosf(a1) * ratio;
3218  sine = sina1 * ratio;
3219 
3220  EIG_linear_solver_matrix_add(context, row, 2 * v1->u.id, cosine - 1.0f);
3221  EIG_linear_solver_matrix_add(context, row, 2 * v1->u.id + 1, -sine);
3222  EIG_linear_solver_matrix_add(context, row, 2 * v2->u.id, -cosine);
3223  EIG_linear_solver_matrix_add(context, row, 2 * v2->u.id + 1, sine);
3224  EIG_linear_solver_matrix_add(context, row, 2 * v3->u.id, 1.0);
3225  row++;
3226 
3227  EIG_linear_solver_matrix_add(context, row, 2 * v1->u.id, sine);
3228  EIG_linear_solver_matrix_add(context, row, 2 * v1->u.id + 1, cosine - 1.0f);
3229  EIG_linear_solver_matrix_add(context, row, 2 * v2->u.id, -sine);
3230  EIG_linear_solver_matrix_add(context, row, 2 * v2->u.id + 1, -cosine);
3231  EIG_linear_solver_matrix_add(context, row, 2 * v3->u.id + 1, 1.0);
3232  row++;
3233  }
3234 
3237  return true;
3238  }
3239 
3240  for (v = chart->verts; v; v = v->nextlink) {
3241  v->uv[0] = 0.0f;
3242  v->uv[1] = 0.0f;
3243  }
3244 
3245  return false;
3246 }
3247 
3249 {
3250  PVert *pin = chart->u.lscm.single_pin;
3251 
3252  /* If only one pin, keep UV area the same. */
3253  const float new_area = p_chart_uv_area(chart);
3254  if (new_area > 0.0f) {
3255  const float scale = chart->u.lscm.single_pin_area / new_area;
3256  if (scale > 0.0f) {
3257  p_chart_uv_scale(chart, sqrtf(scale));
3258  }
3259  }
3260 
3261  /* Translate to keep the pinned vertex in place. */
3262  float offset[2];
3263  sub_v2_v2v2(offset, chart->u.lscm.single_pin_uv, pin->uv);
3264  p_chart_uv_translate(chart, offset);
3265 }
3266 
3267 static void p_chart_lscm_end(PChart *chart)
3268 {
3269  if (chart->u.lscm.context) {
3271  }
3272 
3273  MEM_SAFE_FREE(chart->u.lscm.abf_alpha);
3274 
3275  chart->u.lscm.context = NULL;
3276  chart->u.lscm.pin1 = NULL;
3277  chart->u.lscm.pin2 = NULL;
3278  chart->u.lscm.single_pin = NULL;
3279  chart->u.lscm.single_pin_area = 0.0f;
3280 }
3281 
3282 /* Stretch */
3283 
3284 #define P_STRETCH_ITER 20
3285 
3286 static void p_stretch_pin_boundary(PChart *chart)
3287 {
3288  PVert *v;
3289 
3290  for (v = chart->verts; v; v = v->nextlink) {
3291  if (v->edge->pair == NULL) {
3292  v->flag |= PVERT_PIN;
3293  }
3294  else {
3295  v->flag &= ~PVERT_PIN;
3296  }
3297  }
3298 }
3299 
3300 static float p_face_stretch(PFace *f)
3301 {
3302  float T, w, tmp[3];
3303  float Ps[3], Pt[3];
3304  float a, c, area;
3305  PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
3306  PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
3307 
3309 
3310  if (area <= 0.0f) {
3311  /* When a face is flipped, provide a large penalty.
3312  * Add on a slight gradient to unflip the face, see also: T99781. */
3313  return 1e8f * (1.0f + p_edge_uv_length(e1) + p_edge_uv_length(e2) + p_edge_uv_length(e3));
3314  }
3315 
3316  w = 1.0f / (2.0f * area);
3317 
3318  /* compute derivatives */
3319  copy_v3_v3(Ps, v1->co);
3320  mul_v3_fl(Ps, (v2->uv[1] - v3->uv[1]));
3321 
3322  copy_v3_v3(tmp, v2->co);
3323  mul_v3_fl(tmp, (v3->uv[1] - v1->uv[1]));
3324  add_v3_v3(Ps, tmp);
3325 
3326  copy_v3_v3(tmp, v3->co);
3327  mul_v3_fl(tmp, (v1->uv[1] - v2->uv[1]));
3328  add_v3_v3(Ps, tmp);
3329 
3330  mul_v3_fl(Ps, w);
3331 
3332  copy_v3_v3(Pt, v1->co);
3333  mul_v3_fl(Pt, (v3->uv[0] - v2->uv[0]));
3334 
3335  copy_v3_v3(tmp, v2->co);
3336  mul_v3_fl(tmp, (v1->uv[0] - v3->uv[0]));
3337  add_v3_v3(Pt, tmp);
3338 
3339  copy_v3_v3(tmp, v3->co);
3340  mul_v3_fl(tmp, (v2->uv[0] - v1->uv[0]));
3341  add_v3_v3(Pt, tmp);
3342 
3343  mul_v3_fl(Pt, w);
3344 
3345  /* Sander Tensor */
3346  a = dot_v3v3(Ps, Ps);
3347  c = dot_v3v3(Pt, Pt);
3348 
3349  T = sqrtf(0.5f * (a + c));
3350  if (f->flag & PFACE_FILLED) {
3351  T *= 0.2f;
3352  }
3353 
3354  return T;
3355 }
3356 
3358 {
3359  PEdge *e = v->edge;
3360  float sum = 0.0f;
3361 
3362  do {
3363  sum += p_face_stretch(e->face);
3364  e = p_wheel_edge_next(e);
3365  } while (e && e != (v->edge));
3366 
3367  return sum;
3368 }
3369 
3370 static void p_chart_stretch_minimize(PChart *chart, RNG *rng)
3371 {
3372  PVert *v;
3373  PEdge *e;
3374  int j, nedges;
3375  float orig_stretch, low, stretch_low, high, stretch_high, mid, stretch;
3376  float orig_uv[2], dir[2], random_angle, trusted_radius;
3377 
3378  for (v = chart->verts; v; v = v->nextlink) {
3379  if ((v->flag & PVERT_PIN) || !(v->flag & PVERT_SELECT)) {
3380  continue;
3381  }
3382 
3383  orig_stretch = p_stretch_compute_vertex(v);
3384  orig_uv[0] = v->uv[0];
3385  orig_uv[1] = v->uv[1];
3386 
3387  /* move vertex in a random direction */
3388  trusted_radius = 0.0f;
3389  nedges = 0;
3390  e = v->edge;
3391 
3392  do {
3393  trusted_radius += p_edge_uv_length(e);
3394  nedges++;
3395 
3396  e = p_wheel_edge_next(e);
3397  } while (e && e != (v->edge));
3398 
3399  trusted_radius /= 2 * nedges;
3400 
3401  random_angle = BLI_rng_get_float(rng) * 2.0f * (float)M_PI;
3402  dir[0] = trusted_radius * cosf(random_angle);
3403  dir[1] = trusted_radius * sinf(random_angle);
3404 
3405  /* calculate old and new stretch */
3406  low = 0;
3407  stretch_low = orig_stretch;
3408 
3409  add_v2_v2v2(v->uv, orig_uv, dir);
3410  high = 1;
3411  stretch = stretch_high = p_stretch_compute_vertex(v);
3412 
3413  /* binary search for lowest stretch position */
3414  for (j = 0; j < P_STRETCH_ITER; j++) {
3415  mid = 0.5f * (low + high);
3416  v->uv[0] = orig_uv[0] + mid * dir[0];
3417  v->uv[1] = orig_uv[1] + mid * dir[1];
3418  stretch = p_stretch_compute_vertex(v);
3419 
3420  if (stretch_low < stretch_high) {
3421  high = mid;
3422  stretch_high = stretch;
3423  }
3424  else {
3425  low = mid;
3426  stretch_low = stretch;
3427  }
3428  }
3429 
3430  /* no luck, stretch has increased, reset to old values */
3431  if (stretch >= orig_stretch) {
3432  copy_v2_v2(v->uv, orig_uv);
3433  }
3434  }
3435 }
3436 
3437 /* Minimum area enclosing rectangle for packing */
3438 
3439 static int p_compare_geometric_uv(const void *a, const void *b)
3440 {
3441  const PVert *v1 = *(const PVert *const *)a;
3442  const PVert *v2 = *(const PVert *const *)b;
3443 
3444  if (v1->uv[0] < v2->uv[0]) {
3445  return -1;
3446  }
3447  if (v1->uv[0] == v2->uv[0]) {
3448  if (v1->uv[1] < v2->uv[1]) {
3449  return -1;
3450  }
3451  if (v1->uv[1] == v2->uv[1]) {
3452  return 0;
3453  }
3454  return 1;
3455  }
3456  return 1;
3457 }
3458 
3459 static bool p_chart_convex_hull(PChart *chart, PVert ***r_verts, int *r_nverts, int *r_right)
3460 {
3461  /* Graham algorithm, taken from:
3462  * http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117225 */
3463 
3464  PEdge *be, *e;
3465  int npoints = 0, i, ulen, llen;
3466  PVert **U, **L, **points, **p;
3467 
3468  p_chart_boundaries(chart, &be);
3469 
3470  if (!be) {
3471  return false;
3472  }
3473 
3474  e = be;
3475  do {
3476  npoints++;
3478  } while (e != be);
3479 
3480  p = points = (PVert **)MEM_mallocN(sizeof(PVert *) * npoints * 2, "PCHullpoints");
3481  U = (PVert **)MEM_mallocN(sizeof(PVert *) * npoints, "PCHullU");
3482  L = (PVert **)MEM_mallocN(sizeof(PVert *) * npoints, "PCHullL");
3483 
3484  e = be;
3485  do {
3486  *p = e->vert;
3487  p++;
3489  } while (e != be);
3490 
3491  qsort(points, npoints, sizeof(PVert *), p_compare_geometric_uv);
3492 
3493  ulen = llen = 0;
3494  for (p = points, i = 0; i < npoints; i++, p++) {
3495  while ((ulen > 1) && (p_area_signed(U[ulen - 2]->uv, (*p)->uv, U[ulen - 1]->uv) <= 0)) {
3496  ulen--;
3497  }
3498  while ((llen > 1) && (p_area_signed(L[llen - 2]->uv, (*p)->uv, L[llen - 1]->uv) >= 0)) {
3499  llen--;
3500  }
3501 
3502  U[ulen] = *p;
3503  ulen++;
3504  L[llen] = *p;
3505  llen++;
3506  }
3507 
3508  npoints = 0;
3509  for (p = points, i = 0; i < ulen; i++, p++, npoints++) {
3510  *p = U[i];
3511  }
3512 
3513  /* the first and last point in L are left out, since they are also in U */
3514  for (i = llen - 2; i > 0; i--, p++, npoints++) {
3515  *p = L[i];
3516  }
3517 
3518  *r_verts = points;
3519  *r_nverts = npoints;
3520  *r_right = ulen - 1;
3521 
3522  MEM_freeN(U);
3523  MEM_freeN(L);
3524 
3525  return true;
3526 }
3527 
3528 static float p_rectangle_area(float *p1, float *dir, float *p2, float *p3, float *p4)
3529 {
3530  /* given 4 points on the rectangle edges and the direction of on edge,
3531  * compute the area of the rectangle */
3532 
3533  float orthodir[2], corner1[2], corner2[2], corner3[2];
3534 
3535  orthodir[0] = dir[1];
3536  orthodir[1] = -dir[0];
3537 
3538  if (!p_intersect_line_2d_dir(p1, dir, p2, orthodir, corner1)) {
3539  return 1e10;
3540  }
3541 
3542  if (!p_intersect_line_2d_dir(p1, dir, p4, orthodir, corner2)) {
3543  return 1e10;
3544  }
3545 
3546  if (!p_intersect_line_2d_dir(p3, dir, p4, orthodir, corner3)) {
3547  return 1e10;
3548  }
3549 
3550  return len_v2v2(corner1, corner2) * len_v2v2(corner2, corner3);
3551 }
3552 
3554 {
3555  /* minimum area enclosing rectangle with rotating calipers, info:
3556  * http://cgm.cs.mcgill.ca/~orm/maer.html */
3557 
3558  float rotated, minarea, minangle, area, len;
3559  float *angles, miny, maxy, v[2], a[4], mina;
3560  int npoints, right, i_min, i_max, i, idx[4], nextidx;
3561  PVert **points, *p1, *p2, *p3, *p4, *p1n;
3562 
3563  /* compute convex hull */
3564  if (!p_chart_convex_hull(chart, &points, &npoints, &right)) {
3565  return 0.0;
3566  }
3567 
3568  /* find left/top/right/bottom points, and compute angle for each point */
3569  angles = MEM_mallocN(sizeof(float) * npoints, "PMinAreaAngles");
3570 
3571  i_min = i_max = 0;
3572  miny = 1e10;
3573  maxy = -1e10;
3574 
3575  for (i = 0; i < npoints; i++) {
3576  p1 = (i == 0) ? points[npoints - 1] : points[i - 1];
3577  p2 = points[i];
3578  p3 = (i == npoints - 1) ? points[0] : points[i + 1];
3579 
3580  angles[i] = (float)M_PI - p_vec2_angle(p1->uv, p2->uv, p3->uv);
3581 
3582  if (points[i]->uv[1] < miny) {
3583  miny = points[i]->uv[1];
3584  i_min = i;
3585  }
3586  if (points[i]->uv[1] > maxy) {
3587  maxy = points[i]->uv[1];
3588  i_max = i;
3589  }
3590  }
3591 
3592  /* left, top, right, bottom */
3593  idx[0] = 0;
3594  idx[1] = i_max;
3595  idx[2] = right;
3596  idx[3] = i_min;
3597 
3598  v[0] = points[idx[0]]->uv[0];
3599  v[1] = points[idx[0]]->uv[1] + 1.0f;
3600  a[0] = p_vec2_angle(points[(idx[0] + 1) % npoints]->uv, points[idx[0]]->uv, v);
3601 
3602  v[0] = points[idx[1]]->uv[0] + 1.0f;
3603  v[1] = points[idx[1]]->uv[1];
3604  a[1] = p_vec2_angle(points[(idx[1] + 1) % npoints]->uv, points[idx[1]]->uv, v);
3605 
3606  v[0] = points[idx[2]]->uv[0];
3607  v[1] = points[idx[2]]->uv[1] - 1.0f;
3608  a[2] = p_vec2_angle(points[(idx[2] + 1) % npoints]->uv, points[idx[2]]->uv, v);
3609 
3610  v[0] = points[idx[3]]->uv[0] - 1.0f;
3611  v[1] = points[idx[3]]->uv[1];
3612  a[3] = p_vec2_angle(points[(idx[3] + 1) % npoints]->uv, points[idx[3]]->uv, v);
3613 
3614  /* 4 rotating calipers */
3615 
3616  rotated = 0.0;
3617  minarea = 1e10;
3618  minangle = 0.0;
3619 
3620  while (rotated <= (float)M_PI_2) { /* INVESTIGATE: how far to rotate? */
3621  /* rotate with the smallest angle */
3622  i_min = 0;
3623  mina = 1e10;
3624 
3625  for (i = 0; i < 4; i++) {
3626  if (a[i] < mina) {
3627  mina = a[i];
3628  i_min = i;
3629  }
3630  }
3631 
3632  rotated += mina;
3633  nextidx = (idx[i_min] + 1) % npoints;
3634 
3635  a[i_min] = angles[nextidx];
3636  a[(i_min + 1) % 4] = a[(i_min + 1) % 4] - mina;
3637  a[(i_min + 2) % 4] = a[(i_min + 2) % 4] - mina;
3638  a[(i_min + 3) % 4] = a[(i_min + 3) % 4] - mina;
3639 
3640  /* compute area */
3641  p1 = points[idx[i_min]];
3642  p1n = points[nextidx];
3643  p2 = points[idx[(i_min + 1) % 4]];
3644  p3 = points[idx[(i_min + 2) % 4]];
3645  p4 = points[idx[(i_min + 3) % 4]];
3646 
3647  len = len_v2v2(p1->uv, p1n->uv);
3648 
3649  if (len > 0.0f) {
3650  len = 1.0f / len;
3651  v[0] = (p1n->uv[0] - p1->uv[0]) * len;
3652  v[1] = (p1n->uv[1] - p1->uv[1]) * len;
3653 
3654  area = p_rectangle_area(p1->uv, v, p2->uv, p3->uv, p4->uv);
3655 
3656  /* remember smallest area */
3657  if (area < minarea) {
3658  minarea = area;
3659  minangle = rotated;
3660  }
3661  }
3662 
3663  idx[i_min] = nextidx;
3664  }
3665 
3666  /* try keeping rotation as small as possible */
3667  if (minangle > (float)M_PI_4) {
3668  minangle -= (float)M_PI_2;
3669  }
3670 
3671  MEM_freeN(angles);
3672  MEM_freeN(points);
3673 
3674  return minangle;
3675 }
3676 
3678 {
3679  float angle = p_chart_minimum_area_angle(chart);
3680  float sine = sinf(angle);
3681  float cosine = cosf(angle);
3682  PVert *v;
3683 
3684  for (v = chart->verts; v; v = v->nextlink) {
3685  float oldu = v->uv[0], oldv = v->uv[1];
3686  v->uv[0] = cosine * oldu - sine * oldv;
3687  v->uv[1] = sine * oldu + cosine * oldv;
3688  }
3689 }
3690 
3691 static void p_chart_rotate_fit_aabb(PChart *chart)
3692 {
3693  float(*points)[2] = MEM_mallocN(sizeof(*points) * chart->nverts, __func__);
3694 
3695  p_chart_uv_to_array(chart, points);
3696 
3697  float angle = BLI_convexhull_aabb_fit_points_2d(points, chart->nverts);
3698 
3699  MEM_freeN(points);
3700 
3701  if (angle != 0.0f) {
3702  float mat[2][2];
3703  angle_to_mat2(mat, angle);
3704  p_chart_uv_transform(chart, mat);
3705  }
3706 }
3707 
3708 /* Exported */
3709 
3711 {
3712  ParamHandle *handle = MEM_callocN(sizeof(*handle), "ParamHandle");
3713  handle->construction_chart = p_chart_new(handle);
3714  handle->state = PHANDLE_STATE_ALLOCATED;
3715  handle->arena = BLI_memarena_new(MEM_SIZE_OPTIMAL(1 << 16), "param construct arena");
3716  handle->polyfill_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "param polyfill arena");
3718  handle->aspx = 1.0f;
3719  handle->aspy = 1.0f;
3720 
3721  handle->hash_verts = phash_new((PHashLink **)&handle->construction_chart->verts, 1);
3722  handle->hash_edges = phash_new((PHashLink **)&handle->construction_chart->edges, 1);
3723  handle->hash_faces = phash_new((PHashLink **)&handle->construction_chart->faces, 1);
3724 
3725  return handle;
3726 }
3727 
3728 void GEO_uv_parametrizer_aspect_ratio(ParamHandle *phandle, float aspx, float aspy)
3729 {
3730  phandle->aspx = aspx;
3731  phandle->aspy = aspy;
3732 }
3733 
3735 {
3736  int i;
3737 
3739 
3740  for (i = 0; i < phandle->ncharts; i++) {
3741  p_chart_delete(phandle->charts[i]);
3742  }
3743 
3744  MEM_SAFE_FREE(phandle->charts);
3745 
3746  if (phandle->pin_hash) {
3747  BLI_ghash_free(phandle->pin_hash, NULL, NULL);
3748  phandle->pin_hash = NULL;
3749  }
3750 
3751  if (phandle->construction_chart) {
3753 
3754  phash_delete(phandle->hash_verts);
3755  phash_delete(phandle->hash_edges);
3756  phash_delete(phandle->hash_faces);
3757  }
3758 
3759  BLI_memarena_free(phandle->arena);
3761  BLI_heap_free(phandle->polyfill_heap, NULL);
3762  MEM_freeN(phandle);
3763 }
3764 
3765 typedef struct GeoUVPinIndex {
3767  float uv[2];
3770 
3771 /* Find a (mostly) unique ParamKey given a BMVert index and UV co-ordinates.
3772  * For each unique pinned UVs, return a unique ParamKey, starting with
3773  * a very large number, and decreasing steadily from there.
3774  * For non-pinned UVs which share a BMVert with a pinned UV,
3775  * return the index corresponding to the closest pinned UV.
3776  * For everything else, just return the BMVert index.
3777  * Note that ParamKeys will eventually be hashed, so they don't need to be contiguous.
3778  */
3779 ParamKey GEO_uv_find_pin_index(ParamHandle *handle, const int bmvertindex, const float uv[2])
3780 {
3781  if (!handle->pin_hash) {
3782  return bmvertindex; /* No verts pinned. */
3783  }
3784 
3785  GeoUVPinIndex *pinuvlist = BLI_ghash_lookup(handle->pin_hash, POINTER_FROM_INT(bmvertindex));
3786  if (!pinuvlist) {
3787  return bmvertindex; /* Vert not pinned. */
3788  }
3789 
3790  /* At least one of the UVs associated with bmvertindex is pinned. Find the best one. */
3791  float bestdistsquared = len_squared_v2v2(pinuvlist->uv, uv);
3792  ParamKey bestkey = pinuvlist->reindex;
3793  pinuvlist = pinuvlist->next;
3794  while (pinuvlist) {
3795  const float distsquared = len_squared_v2v2(pinuvlist->uv, uv);
3796  if (bestdistsquared > distsquared) {
3797  bestdistsquared = distsquared;
3798  bestkey = pinuvlist->reindex;
3799  }
3800  pinuvlist = pinuvlist->next;
3801  }
3802  return bestkey;
3803 }
3804 
3805 static GeoUVPinIndex *new_geo_uv_pinindex(ParamHandle *handle, const float uv[2])
3806 {
3807  GeoUVPinIndex *pinuv = BLI_memarena_alloc(handle->arena, sizeof(*pinuv));
3808  pinuv->next = NULL;
3809  copy_v2_v2(pinuv->uv, uv);
3810  pinuv->reindex = PARAM_KEY_MAX - (handle->unique_pin_count++);
3811  return pinuv;
3812 }
3813 
3814 void GEO_uv_prepare_pin_index(ParamHandle *handle, const int bmvertindex, const float uv[2])
3815 {
3816  if (!handle->pin_hash) {
3817  handle->pin_hash = BLI_ghash_int_new("uv pin reindex");
3818  }
3819 
3820  GeoUVPinIndex *pinuvlist = BLI_ghash_lookup(handle->pin_hash, POINTER_FROM_INT(bmvertindex));
3821  if (!pinuvlist) {
3823  handle->pin_hash, POINTER_FROM_INT(bmvertindex), new_geo_uv_pinindex(handle, uv));
3824  return;
3825  }
3826 
3827  while (true) {
3828  if (equals_v2v2(pinuvlist->uv, uv)) {
3829  return;
3830  }
3831  if (!pinuvlist->next) {
3832  pinuvlist->next = new_geo_uv_pinindex(handle, uv);
3833  return;
3834  }
3835  pinuvlist = pinuvlist->next;
3836  }
3837 }
3838 
3839 static void p_add_ngon(ParamHandle *handle,
3840  const ParamKey key,
3841  const int nverts,
3842  const ParamKey *vkeys,
3843  const float **co,
3844  float **uv, /* Output will eventually be written to `uv`. */
3845  const bool *pin,
3846  const bool *select)
3847 {
3848  /* Allocate memory for polyfill. */
3849  MemArena *arena = handle->polyfill_arena;
3850  Heap *heap = handle->polyfill_heap;
3851  uint nfilltri = nverts - 2;
3852  uint(*tris)[3] = BLI_memarena_alloc(arena, sizeof(*tris) * (size_t)nfilltri);
3853  float(*projverts)[2] = BLI_memarena_alloc(arena, sizeof(*projverts) * (size_t)nverts);
3854 
3855  /* Calc normal, flipped: to get a positive 2d cross product. */
3856  float normal[3];
3857  zero_v3(normal);
3858 
3859  const float *co_curr, *co_prev = co[nverts - 1];
3860  for (int j = 0; j < nverts; j++) {
3861  co_curr = co[j];
3862  add_newell_cross_v3_v3v3(normal, co_prev, co_curr);
3863  co_prev = co_curr;
3864  }
3865  if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
3866  normal[2] = 1.0f;
3867  }
3868 
3869  /* Project verts to 2d. */
3870  float axis_mat[3][3];
3872  for (int j = 0; j < nverts; j++) {
3873  mul_v2_m3v3(projverts[j], axis_mat, co[j]);
3874  }
3875 
3876  BLI_polyfill_calc_arena(projverts, nverts, 1, tris, arena);
3877 
3878  /* Beautify helps avoid thin triangles that give numerical problems. */
3879  BLI_polyfill_beautify(projverts, nverts, tris, arena, heap);
3880 
3881  /* Add triangles. */
3882  for (int j = 0; j < nfilltri; j++) {
3883  uint *tri = tris[j];
3884  uint v0 = tri[0];
3885  uint v1 = tri[1];
3886  uint v2 = tri[2];
3887 
3888  const ParamKey tri_vkeys[3] = {vkeys[v0], vkeys[v1], vkeys[v2]};
3889  const float *tri_co[3] = {co[v0], co[v1], co[v2]};
3890  float *tri_uv[3] = {uv[v0], uv[v1], uv[v2]};
3891  bool tri_pin[3] = {pin[v0], pin[v1], pin[v2]};
3892  bool tri_select[3] = {select[v0], select[v1], select[v2]};
3893 
3894  GEO_uv_parametrizer_face_add(handle, key, 3, tri_vkeys, tri_co, tri_uv, tri_pin, tri_select);
3895  }
3896 
3897  BLI_memarena_clear(arena);
3898 }
3899 
3901  const ParamKey key,
3902  const int nverts,
3903  const ParamKey *vkeys,
3904  const float **co,
3905  float **uv,
3906  const bool *pin,
3907  const bool *select)
3908 {
3909  param_assert(phash_lookup(phandle->hash_faces, key) == NULL);
3911  param_assert(ELEM(nverts, 3, 4));
3912 
3913  if (nverts > 4) {
3914  /* ngon */
3915  p_add_ngon(phandle, key, nverts, vkeys, co, uv, pin, select);
3916  }
3917  else if (nverts == 4) {
3918  /* quad */
3919  if (p_quad_split_direction(phandle, co, vkeys)) {
3920  p_face_add_construct(phandle, key, vkeys, co, uv, 0, 1, 2, pin, select);
3921  p_face_add_construct(phandle, key, vkeys, co, uv, 0, 2, 3, pin, select);
3922  }
3923  else {
3924  p_face_add_construct(phandle, key, vkeys, co, uv, 0, 1, 3, pin, select);
3925  p_face_add_construct(phandle, key, vkeys, co, uv, 1, 2, 3, pin, select);
3926  }
3927  }
3928  else if (!p_face_exists(phandle, vkeys, 0, 1, 2)) {
3929  /* triangle */
3930  p_face_add_construct(phandle, key, vkeys, co, uv, 0, 1, 2, pin, select);
3931  }
3932 }
3933 
3935 {
3936  PEdge *e;
3937 
3939 
3940  e = p_edge_lookup(phandle, vkeys);
3941  if (e) {
3942  e->flag |= PEDGE_SEAM;
3943  }
3944 }
3945 
3947  bool fill,
3948  bool topology_from_uvs,
3949  int *count_fail)
3950 {
3951  PChart *chart = phandle->construction_chart;
3952  int i, j;
3953  PEdge *outer;
3954 
3956 
3957  phandle->ncharts = p_connect_pairs(phandle, topology_from_uvs);
3958  phandle->charts = p_split_charts(phandle, chart, phandle->ncharts);
3959 
3961  phandle->construction_chart = NULL;
3962 
3963  phash_delete(phandle->hash_verts);
3964  phash_delete(phandle->hash_edges);
3965  phash_delete(phandle->hash_faces);
3966  phandle->hash_verts = phandle->hash_edges = phandle->hash_faces = NULL;
3967 
3968  for (i = j = 0; i < phandle->ncharts; i++) {
3969  PVert *v;
3970  chart = phandle->charts[i];
3971 
3972  p_chart_boundaries(chart, &outer);
3973 
3974  if (!topology_from_uvs && chart->nboundaries == 0) {
3975  p_chart_delete(chart);
3976  if (count_fail != NULL) {
3977  *count_fail += 1;
3978  }
3979  continue;
3980  }
3981 
3982  phandle->charts[j] = chart;
3983  j++;
3984 
3985  if (fill && (chart->nboundaries > 1)) {
3986  p_chart_fill_boundaries(chart, outer);
3987  }
3988 
3989  for (v = chart->verts; v; v = v->nextlink) {
3990  p_vert_load_pin_select_uvs(phandle, v);
3991  }
3992  }
3993 
3994  phandle->ncharts = j;
3995 
3996  phandle->state = PHANDLE_STATE_CONSTRUCTED;
3997 }
3998 
3999 void GEO_uv_parametrizer_lscm_begin(ParamHandle *phandle, bool live, bool abf)
4000 {
4001  PFace *f;
4002  int i;
4003 
4005  phandle->state = PHANDLE_STATE_LSCM;
4006 
4007  for (i = 0; i < phandle->ncharts; i++) {
4008  for (f = phandle->charts[i]->faces; f; f = f->nextlink) {
4009  p_face_backup_uvs(f);
4010  }
4011  p_chart_lscm_begin(phandle->charts[i], live, abf);
4012  }
4013 }
4014 
4015 void GEO_uv_parametrizer_lscm_solve(ParamHandle *phandle, int *count_changed, int *count_failed)
4016 {
4017  PChart *chart;
4018  int i;
4019 
4020  param_assert(phandle->state == PHANDLE_STATE_LSCM);
4021 
4022  for (i = 0; i < phandle->ncharts; i++) {
4023  chart = phandle->charts[i];
4024 
4025  if (chart->u.lscm.context) {
4026  const bool result = p_chart_lscm_solve(phandle, chart);
4027 
4028  if (result && !(chart->flag & PCHART_HAS_PINS)) {
4030  }
4031  else if (result && chart->u.lscm.single_pin) {
4032  p_chart_rotate_fit_aabb(chart);
4034  }
4035 
4036  if (!result || !(chart->flag & PCHART_HAS_PINS)) {
4037  p_chart_lscm_end(chart);
4038  }
4039 
4040  if (result) {
4041  if (count_changed != NULL) {
4042  *count_changed += 1;
4043  }
4044  }
4045  else {
4046  if (count_failed != NULL) {
4047  *count_failed += 1;
4048  }
4049  }
4050  }
4051  }
4052 }
4053 
4055 {
4056  int i;
4057 
4058  param_assert(phandle->state == PHANDLE_STATE_LSCM);
4059 
4060  for (i = 0; i < phandle->ncharts; i++) {
4061  p_chart_lscm_end(phandle->charts[i]);
4062 #if 0
4063  p_chart_complexify(phandle->charts[i]);
4064 #endif
4065  }
4066 
4067  phandle->state = PHANDLE_STATE_CONSTRUCTED;
4068 }
4069 
4071 {
4072  PChart *chart;
4073  PVert *v;
4074  PFace *f;
4075  int i;
4076 
4078  phandle->state = PHANDLE_STATE_STRETCH;
4079 
4080  phandle->rng = BLI_rng_new(31415926);
4081  phandle->blend = 0.0f;
4082 
4083  for (i = 0; i < phandle->ncharts; i++) {
4084  chart = phandle->charts[i];
4085 
4086  for (v = chart->verts; v; v = v->nextlink) {
4087  v->flag &= ~PVERT_PIN; /* don't use user-defined pins */
4088  }
4089 
4090  p_stretch_pin_boundary(chart);
4091 
4092  for (f = chart->faces; f; f = f->nextlink) {
4093  p_face_backup_uvs(f);
4094  f->u.area3d = p_face_area(f);
4095  }
4096  }
4097 }
4098 
4100 {
4102  phandle->blend = blend;
4103 }
4104 
4106 {
4107  PChart *chart;
4108  int i;
4109 
4111 
4112  for (i = 0; i < phandle->ncharts; i++) {
4113  chart = phandle->charts[i];
4114  p_chart_stretch_minimize(chart, phandle->rng);
4115  }
4116 }
4117 
4119 {
4121  phandle->state = PHANDLE_STATE_CONSTRUCTED;
4122 
4123  BLI_rng_free(phandle->rng);
4124  phandle->rng = NULL;
4125 }
4126 
4127 /* don't pack, just rotate (used for better packing) */
4128 static void GEO_uv_parametrizer_pack_rotate(ParamHandle *phandle, bool ignore_pinned)
4129 {
4130  PChart *chart;
4131  int i;
4132 
4133  for (i = 0; i < phandle->ncharts; i++) {
4134  chart = phandle->charts[i];
4135 
4136  if (ignore_pinned && (chart->flag & PCHART_HAS_PINS)) {
4137  continue;
4138  }
4139 
4140  p_chart_rotate_fit_aabb(chart);
4141  }
4142 }
4143 
4145  float margin,
4146  bool do_rotate,
4147  bool ignore_pinned)
4148 {
4149  /* box packing variables */
4150  BoxPack *boxarray, *box;
4151  float tot_width, tot_height, scale;
4152 
4153  PChart *chart;
4154  int i, unpacked = 0;
4155  float trans[2];
4156  double area = 0.0;
4157 
4158  if (handle->ncharts == 0) {
4159  return;
4160  }
4161 
4162  /* this could be its own function */
4163  if (do_rotate) {
4164  GEO_uv_parametrizer_pack_rotate(handle, ignore_pinned);
4165  }
4166 
4167  if (handle->aspx != handle->aspy) {
4168  GEO_uv_parametrizer_scale(handle, 1.0f / handle->aspx, 1.0f / handle->aspy);
4169  }
4170 
4171  /* we may not use all these boxes */
4172  boxarray = MEM_mallocN(handle->ncharts * sizeof(BoxPack), "BoxPack box");
4173 
4174  for (i = 0; i < handle->ncharts; i++) {
4175  chart = handle->charts[i];
4176 
4177  if (ignore_pinned && (chart->flag & PCHART_HAS_PINS)) {
4178  unpacked++;
4179  continue;
4180  }
4181 
4182  box = boxarray + (i - unpacked);
4183 
4184  p_chart_uv_bbox(chart, trans, chart->u.pack.size);
4185 
4186  trans[0] = -trans[0];
4187  trans[1] = -trans[1];
4188 
4189  p_chart_uv_translate(chart, trans);
4190 
4191  box->w = chart->u.pack.size[0] + trans[0];
4192  box->h = chart->u.pack.size[1] + trans[1];
4193  box->index = i; /* warning this index skips PCHART_HAS_PINS boxes */
4194 
4195  if (margin > 0.0f) {
4196  area += (double)sqrtf(box->w * box->h);
4197  }
4198  }
4199 
4200  if (margin > 0.0f) {
4201  /* multiply the margin by the area to give predictable results not dependent on UV scale,
4202  * ...Without using the area running pack multiple times also gives a bad feedback loop.
4203  * multiply by 0.1 so the margin value from the UI can be from
4204  * 0.0 to 1.0 but not give a massive margin */
4205  margin = (margin * (float)area) * 0.1f;
4206  unpacked = 0;
4207  for (i = 0; i < handle->ncharts; i++) {
4208  chart = handle->charts[i];
4209 
4210  if (ignore_pinned && (chart->flag & PCHART_HAS_PINS)) {
4211  unpacked++;
4212  continue;
4213  }
4214 
4215  box = boxarray + (i - unpacked);
4216  trans[0] = margin;
4217  trans[1] = margin;
4218  p_chart_uv_translate(chart, trans);
4219  box->w += margin * 2;
4220  box->h += margin * 2;
4221  }
4222  }
4223 
4224  BLI_box_pack_2d(boxarray, handle->ncharts - unpacked, &tot_width, &tot_height);
4225 
4226  if (tot_height > tot_width) {
4227  scale = tot_height != 0.0f ? (1.0f / tot_height) : 1.0f;
4228  }
4229  else {
4230  scale = tot_width != 0.0f ? (1.0f / tot_width) : 1.0f;
4231  }
4232 
4233  for (i = 0; i < handle->ncharts - unpacked; i++) {
4234  box = boxarray + i;
4235  trans[0] = box->x;
4236  trans[1] = box->y;
4237 
4238  chart = handle->charts[box->index];
4239  p_chart_uv_translate(chart, trans);
4240  p_chart_uv_scale(chart, scale);
4241  }
4242  MEM_freeN(boxarray);
4243 
4244  if (handle->aspx != handle->aspy) {
4245  GEO_uv_parametrizer_scale(handle, handle->aspx, handle->aspy);
4246  }
4247 }
4248 
4250  bool ignore_pinned,
4251  bool scale_uv,
4252  bool shear)
4253 {
4254  PChart *chart;
4255  int i;
4256  float tot_uvarea = 0.0f, tot_facearea = 0.0f;
4257  float tot_fac, fac;
4258  float minv[2], maxv[2], trans[2];
4259 
4260  if (phandle->ncharts == 0) {
4261  return;
4262  }
4263 
4264  for (i = 0; i < phandle->ncharts; i++) {
4265  chart = phandle->charts[i];
4266 
4267  if (ignore_pinned && (chart->flag & PCHART_HAS_PINS)) {
4268  continue;
4269  }
4270 
4271  p_chart_uv_bbox(chart, minv, maxv);
4272  mid_v2_v2v2(chart->u.pack.origin, minv, maxv);
4273 
4274  if (scale_uv || shear) {
4275  /* It's possible that for some "bad" inputs, the following iteration will converge slowly or
4276  * perhaps even diverge. Rather than infinite loop, we only iterate a maximum of `max_iter`
4277  * times. (Also useful when making changes to the calculation.) */
4278  int max_iter = 10;
4279  for (int j = 0; j < max_iter; j++) {
4280  /* An island could contain millions of polygons. When summing many small values, we need to
4281  * use double precision in the accumulator to maintain accuracy. Note that the individual
4282  * calculations only need to be at single precision.*/
4283  double scale_cou = 0;
4284  double scale_cov = 0;
4285  double scale_cross = 0;
4286  double weight_sum = 0;
4287  for (PFace *f = chart->faces; f; f = f->nextlink) {
4288  float m[2][2], s[2][2];
4289  PVert *va = f->edge->vert;
4290  PVert *vb = f->edge->next->vert;
4291  PVert *vc = f->edge->next->next->vert;
4292  s[0][0] = va->uv[0] - vc->uv[0];
4293  s[0][1] = va->uv[1] - vc->uv[1];
4294  s[1][0] = vb->uv[0] - vc->uv[0];
4295  s[1][1] = vb->uv[1] - vc->uv[1];
4296  /* Find the "U" axis and "V" axis in triangle co-ordinates. Normally this would require
4297  * SVD, but in 2D we can use a cheaper matrix inversion instead.*/
4298  if (!invert_m2_m2(m, s)) {
4299  continue;
4300  }
4301  float cou[3], cov[3]; /* i.e. Texture "U" and texture "V" in 3D co-ordinates.*/
4302  for (int k = 0; k < 3; k++) {
4303  cou[k] = m[0][0] * (va->co[k] - vc->co[k]) + m[0][1] * (vb->co[k] - vc->co[k]);
4304  cov[k] = m[1][0] * (va->co[k] - vc->co[k]) + m[1][1] * (vb->co[k] - vc->co[k]);
4305  }
4306  const float weight = p_face_area(f);
4307  scale_cou += len_v3(cou) * weight;
4308  scale_cov += len_v3(cov) * weight;
4309  if (shear) {
4310  normalize_v3(cov);
4311  normalize_v3(cou);
4312 
4313  /* Why is scale_cross called `cross` when we call `dot`? The next line calculates:
4314  * `scale_cross += length(cross(cross(cou, face_normal), cov))`
4315  * By construction, both `cou` and `cov` are orthogonal to the face normal.
4316  * By definition, the normal vector has unit length. */
4317  scale_cross += dot_v3v3(cou, cov) * weight;
4318  }
4319  weight_sum += weight;
4320  }
4321  if (scale_cou * scale_cov < 1e-10f) {
4322  break;
4323  }
4324  const float scale_factor_u = scale_uv ? sqrtf(scale_cou / scale_cov) : 1.0f;
4325 
4326  /* Compute correction transform. */
4327  float t[2][2];
4328  t[0][0] = scale_factor_u;
4329  t[1][0] = clamp_f((float)(scale_cross / weight_sum), -0.5f, 0.5f);
4330  t[0][1] = 0;
4331  t[1][1] = 1.0f / scale_factor_u;
4332 
4333  /* Apply the correction. */
4334  p_chart_uv_transform(chart, t);
4335 
4336  /* How far from the identity transform are we? [[1,0],[0,1]] */
4337  const float err = fabsf(t[0][0] - 1.0f) + fabsf(t[1][0]) + fabsf(t[0][1]) +
4338  fabsf(t[1][1] - 1.0f);
4339 
4340  const float tolerance = 1e-6f; /* Trade accuracy for performance. */
4341  if (err < tolerance) {
4342  /* Too slow? Use Richardson Extrapolation to accelerate the convergence.*/
4343  break;
4344  }
4345  }
4346  }
4347 
4348  chart->u.pack.area = 0.0f; /* 3d area */
4349  chart->u.pack.rescale = 0.0f; /* UV area, abusing rescale for tmp storage, oh well :/ */
4350 
4351  for (PFace *f = chart->faces; f; f = f->nextlink) {
4352  chart->u.pack.area += p_face_area(f);
4353  chart->u.pack.rescale += fabsf(p_face_uv_area_signed(f));
4354  }
4355 
4356  tot_facearea += chart->u.pack.area;
4357  tot_uvarea += chart->u.pack.rescale;
4358  }
4359 
4360  if (tot_facearea == tot_uvarea || tot_facearea == 0.0f || tot_uvarea == 0.0f) {
4361  /* nothing to do */
4362  return;
4363  }
4364 
4365  tot_fac = tot_facearea / tot_uvarea;
4366 
4367  for (i = 0; i < phandle->ncharts; i++) {
4368  chart = phandle->charts[i];
4369 
4370  if (ignore_pinned && (chart->flag & PCHART_HAS_PINS)) {
4371  continue;
4372  }
4373 
4374  if (chart->u.pack.area != 0.0f && chart->u.pack.rescale != 0.0f) {
4375  fac = chart->u.pack.area / chart->u.pack.rescale;
4376 
4377  /* Average scale. */
4378  p_chart_uv_scale(chart, sqrtf(fac / tot_fac));
4379 
4380  /* Get the current island center. */
4381  p_chart_uv_bbox(chart, minv, maxv);
4382 
4383  /* Move to original center. */
4384  mid_v2_v2v2(trans, minv, maxv);
4385  negate_v2(trans);
4386  add_v2_v2(trans, chart->u.pack.origin);
4387  p_chart_uv_translate(chart, trans);
4388  }
4389  }
4390 }
4391 
4392 void GEO_uv_parametrizer_scale(ParamHandle *phandle, float x, float y)
4393 {
4394  PChart *chart;
4395  int i;
4396 
4397  for (i = 0; i < phandle->ncharts; i++) {
4398  chart = phandle->charts[i];
4399  p_chart_uv_scale_xy(chart, x, y);
4400  }
4401 }
4402 
4404 {
4405  PChart *chart;
4406  int i;
4407 
4408  for (i = 0; i < phandle->ncharts; i++) {
4409  chart = phandle->charts[i];
4410 
4411  if ((phandle->state == PHANDLE_STATE_LSCM) && !chart->u.lscm.context) {
4412  continue;
4413  }
4414 
4415  if (phandle->blend == 0.0f) {
4416  p_flush_uvs(phandle, chart);
4417  }
4418  else {
4419  p_flush_uvs_blend(phandle, chart, phandle->blend);
4420  }
4421  }
4422 }
4423 
4425 {
4426  PChart *chart;
4427  PFace *f;
4428  int i;
4429 
4430  for (i = 0; i < phandle->ncharts; i++) {
4431  chart = phandle->charts[i];
4432 
4433  for (f = chart->faces; f; f = f->nextlink) {
4434  p_face_restore_uvs(f);
4435  }
4436  }
4437 }
typedef float(TangentPoint)[2]
void BLI_box_pack_2d(BoxPack *boxarray, unsigned int len, float *r_tot_x, float *r_tot_y)
Definition: boxpack_2d.c:269
float BLI_convexhull_aabb_fit_points_2d(const float(*points)[2], unsigned int n)
GHash * BLI_ghash_int_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
void * BLI_ghash_lookup(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:734
void BLI_ghash_insert(GHash *gh, void *key, void *val)
Definition: BLI_ghash.c:710
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition: BLI_ghash.c:863
A min-heap / priority queue ADT.
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition: BLI_heap.c:202
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Definition: BLI_heap.c:279
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition: BLI_heap.c:301
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition: BLI_heap.c:182
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition: BLI_heap.c:245
HeapNode * BLI_heap_top(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: BLI_heap.c:289
Heap * BLI_heap_new(void) ATTR_WARN_UNUSED_RESULT
Definition: BLI_heap.c:197
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
MINLINE float max_fff(float a, float b, float c)
MINLINE float clamp_f(float value, float min, float max)
#define M_PI_2
Definition: BLI_math_base.h:23
#define M_PI
Definition: BLI_math_base.h:20
#define M_PI_4
Definition: BLI_math_base.h:26
float volume_tri_tetrahedron_signed_v3(const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:263
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
Definition: math_geom.c:3544
float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:92
bool invert_m2_m2(float R[2][2], const float A[2][2])
Definition: math_matrix.c:1119
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
Definition: math_matrix.c:917
void mul_m2_v2(const float M[2][2], float v[2])
Definition: math_matrix.c:785
void angle_to_mat2(float R[2][2], float angle)
float angle_v2v2v2(const float a[2], const float b[2], const float c[2]) ATTR_WARN_UNUSED_RESULT
Definition: math_vector.c:395
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
MINLINE float normalize_v3(float r[3])
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void copy_v2_v2(float r[2], const float a[2])
MINLINE void mul_v3_fl(float r[3], float f)
MINLINE void negate_v2(float r[2])
MINLINE void copy_v3_v3(float r[3], const float a[3])
void minmax_v2v2_v2(float min[2], float max[2], const float vec[2])
Definition: math_vector.c:890
MINLINE void add_v2_v2(float r[2], const float a[2])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE bool equals_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
void mid_v2_v2v2(float r[2], const float a[2], const float b[2])
Definition: math_vector.c:244
MINLINE void add_v2_v2v2(float r[2], const float a[2], const float b[2])
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
MINLINE bool equals_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float len_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT
MINLINE void zero_v3(float r[3])
float angle_v3v3v3(const float a[3], const float b[3], const float c[3]) ATTR_WARN_UNUSED_RESULT
Definition: math_vector.c:361
MINLINE void add_v3_v3(float r[3], const float a[3])
MINLINE float len_v3(const float a[3]) ATTR_WARN_UNUSED_RESULT
void BLI_memarena_free(struct MemArena *ma) ATTR_NONNULL(1)
Definition: BLI_memarena.c:94
struct MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
Definition: BLI_memarena.c:64
#define BLI_MEMARENA_STD_BUFSIZE
Definition: BLI_memarena.h:20
void * BLI_memarena_alloc(struct MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
Definition: BLI_memarena.c:116
void void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
Definition: BLI_memarena.c:208
void BLI_polyfill_calc_arena(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3], struct MemArena *arena)
Definition: polyfill_2d.c:830
#define BLI_POLYFILL_ALLOC_NGON_RESERVE
void BLI_polyfill_beautify(const float(*coords)[2], unsigned int coords_num, unsigned int(*tris)[3], struct MemArena *arena, struct Heap *eheap)
Random number functions.
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition: rand.cc:58
struct RNG * BLI_rng_new(unsigned int seed)
Definition: rand.cc:39
float BLI_rng_get_float(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: rand.cc:93
unsigned char uchar
Definition: BLI_sys_types.h:70
unsigned int uint
Definition: BLI_sys_types.h:67
unsigned short ushort
Definition: BLI_sys_types.h:68
#define INIT_MINMAX2(min, max)
#define SWAP(type, a, b)
#define POINTER_FROM_INT(i)
#define SHIFT3(type, a, b, c)
#define UNLIKELY(x)
#define ELEM(...)
typedef double(DMatrix)[4][4]
intptr_t ParamKey
#define PARAM_KEY_MAX
NSNotificationCenter * center
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble GLdouble r _GL_VOID_RET _GL_VOID GLfloat GLfloat r _GL_VOID_RET _GL_VOID GLint GLint r _GL_VOID_RET _GL_VOID GLshort GLshort r _GL_VOID_RET _GL_VOID GLdouble GLdouble r
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint y
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble x2
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble right
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint i1
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble t
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
#define MEM_SAFE_FREE(v)
#define MEM_SIZE_OPTIMAL(size)
__forceinline const avxb select(const avxb &m, const avxb &t, const avxb &f)
Definition: avxb.h:154
__forceinline ssef low(const avxf &a)
Definition: avxf.h:264
__forceinline ssef high(const avxf &a)
Definition: avxf.h:268
#define U
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
unsigned int U
Definition: btGjkEpa3.h:78
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition: btQuadWord.h:119
static T sum(const btAlignedObjectArray< T > &items)
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
#define sinf(x)
Definition: cuda/compat.h:102
#define cosf(x)
Definition: cuda/compat.h:101
int len
Definition: draw_manager.c:108
static float verts[][3]
IconTextureDrawCall normal
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
void EIG_linear_solver_variable_set(LinearSolver *solver, int rhs, int index, double value)
LinearSolver * EIG_linear_solver_new(int num_rows, int num_columns, int num_rhs)
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_rhs)
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)
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_dupallocN)(const void *vmemh)
Definition: mallocn.c:28
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static ulong * next
static int corner1[12]
#define T
#define L
static char faces[256]
static int corner2[12]
#define fabsf(x)
Definition: metal/compat.h:219
#define sqrtf(x)
Definition: metal/compat.h:243
bool isfinite(uchar)
Definition: scene/image.cpp:31
static unsigned c
Definition: RandGen.cpp:83
static unsigned a[3]
Definition: RandGen.cpp:78
GAttributeReader lookup(const void *owner, const AttributeIDRef &attribute_id)
static void area(int d1, int d2, int e1, int e2, float weights[2])
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
static void copy(bNodeTree *dest_ntree, bNode *dest_node, const bNode *src_node)
#define hash
Definition: noise.c:153
_W64 unsigned int uintptr_t
Definition: stdint.h:119
_W64 int intptr_t
Definition: stdint.h:118
float co[3]
Definition: bmesh_class.h:87
struct GeoUVPinIndex * next
Definition: BLI_heap.c:43
float * lambdaPlanar
float * lambdaLength
float * bTriangle
float * bInterior
float * lambdaTriangle
float(* J2dt)[3]
PEdge * edges
int nboundaries
PFace * faces
PFace * collapsed_faces
uchar flag
PVert * verts
PVert * collapsed_verts
PEdge * collapsed_edges
union PChart::PChartUnion u
ParamHandle * handle
struct PFace * face
float old_uv[2]
ushort flag
struct PEdge * nextlink
struct PEdge * next
float * orig_uv
struct PEdge * pair
struct PVert * vert
union PEdge::PEdgeUnion u
struct PFace * nextlink
uchar flag
struct PEdge * edge
union PFace::PFaceUnion u
int cursize
PHashLink ** buckets
int cursize_id
PHashLink ** list
uchar flag
union PVert::PVertUnion u
struct PVert * nextlink
float uv[2]
struct PEdge * edge
float co[3]
PHash * hash_edges
PChart ** charts
PHash * hash_verts
MemArena * polyfill_arena
PHash * hash_faces
Heap * polyfill_heap
struct GHash * pin_hash
PChart * construction_chart
MemArena * arena
enum PHandleState state
Definition: rand.cc:33
static int blend(const Tex *tex, const float texvec[3], TexResult *texres)
struct PChart::PChartUnion::PChartLscm lscm
struct PChart::PChartUnion::PChartPack pack
struct PEdge * nextcollapse
ccl_device_inline float beta(float x, float y)
Definition: util/math.h:775
static void phash_insert(PHash *ph, PHashLink *link)
static float p_face_stretch(PFace *f)
struct PChart PChart
static void p_triangle_angles(const float v1[3], const float v2[3], const float v3[3], float *r_a1, float *r_a2, float *r_a3)
void GEO_uv_parametrizer_flush_restore(ParamHandle *phandle)
PChartFlag
@ PCHART_HAS_PINS
static PChart * p_chart_new(ParamHandle *handle)
void GEO_uv_parametrizer_construct_end(ParamHandle *phandle, bool fill, bool topology_from_uvs, int *count_fail)
static PEdge * p_edge_lookup(ParamHandle *handle, const PHashKey *vkeys)
static float p_abf_compute_grad_alpha(PAbfSystem *sys, PFace *f, PEdge *e)
static bool p_chart_symmetry_pins(PChart *chart, PEdge *outer, PVert **pin1, PVert **pin2)
static GeoUVPinIndex * new_geo_uv_pinindex(ParamHandle *handle, const float uv[2])
struct PVert PVert
static void p_split_vert(PChart *chart, PEdge *e)
void GEO_uv_parametrizer_lscm_end(ParamHandle *phandle)
#define PHASH_hash(ph, item)
static float p_edge_boundary_angle(PEdge *e)
static bool p_abf_matrix_invert(PAbfSystem *sys, PChart *chart)
static void p_chart_lscm_load_solution(PChart *chart)
static void p_chart_fill_boundaries(PChart *chart, PEdge *outer)
static void p_add_ngon(ParamHandle *handle, const ParamKey key, const int nverts, const ParamKey *vkeys, const float **co, float **uv, const bool *pin, const bool *select)
static void p_chart_uv_to_array(PChart *chart, float(*points)[2])
static void p_abf_setup_system(PAbfSystem *sys)
static PFace * p_face_add(ParamHandle *handle)
static float p_abf_compute_sin_product(PAbfSystem *sys, PVert *v, int aid)
static float p_edge_length(PEdge *e)
static PEdge * p_wheel_edge_next(PEdge *e)
static bool p_chart_abf_solve(PChart *chart)
struct PHash PHash
static void p_chart_rotate_fit_aabb(PChart *chart)
struct PFace PFace
static void p_stretch_pin_boundary(PChart *chart)
static bool p_edge_implicit_seam(PEdge *e, PEdge *ep)
ParamHandle * GEO_uv_parametrizer_construct_begin(void)
void GEO_uv_prepare_pin_index(ParamHandle *handle, const int bmvertindex, const float uv[2])
static float p_area_signed(const float v1[2], const float v2[2], const float v3[2])
static PHash * phash_new(PHashLink **list, int sizehint)
static bool p_edge_has_pair(ParamHandle *handle, PEdge *e, bool topology_from_uvs, PEdge **r_pair)
static void GEO_uv_parametrizer_pack_rotate(ParamHandle *phandle, bool ignore_pinned)
void GEO_uv_parametrizer_edge_set_seam(ParamHandle *phandle, ParamKey *vkeys)
static bool p_chart_convex_hull(PChart *chart, PVert ***r_verts, int *r_nverts, int *r_right)
void GEO_uv_parametrizer_lscm_begin(ParamHandle *phandle, bool live, bool abf)
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 GEO_uv_parametrizer_flush(ParamHandle *phandle)
#define param_assert(condition)
static void p_chart_boundaries(PChart *chart, PEdge **r_outer)
#define PHASH_edge(v1, v2)
struct PAbfSystem PAbfSystem
static void p_chart_lscm_end(PChart *chart)
static void p_chart_extrema_verts(PChart *chart, PVert **pin1, PVert **pin2)
static float p_face_uv_area_signed(PFace *f)
static void p_chart_uv_translate(PChart *chart, const float trans[2])
void GEO_uv_parametrizer_stretch_iter(ParamHandle *phandle)
#define PEDGE_VERTEX_FLAGS
#define P_STRETCH_ITER
void GEO_uv_parametrizer_pack(ParamHandle *handle, float margin, bool do_rotate, bool ignore_pinned)
static void p_abf_compute_sines(PAbfSystem *sys)
struct ParamHandle ParamHandle
static void p_flush_uvs_blend(ParamHandle *handle, PChart *chart, float blend)
static void p_chart_pin_positions(PChart *chart, PVert **pin1, PVert **pin2)
static void phash_delete(PHash *ph)
static float p_chart_uv_area(PChart *chart)
static PVert * p_vert_copy(PChart *chart, PVert *v)
void GEO_uv_parametrizer_face_add(ParamHandle *phandle, const ParamKey key, const int nverts, const ParamKey *vkeys, const float **co, float **uv, const bool *pin, const bool *select)
static float p_vec2_angle(const float v1[2], const float v2[2], const float v3[2])
static int p_connect_pairs(ParamHandle *handle, bool topology_from_uvs)
static PHashLink * phash_next(PHash *ph, PHashKey key, PHashLink *link)
static PEdge * p_boundary_edge_prev(PEdge *e)
static void p_chart_lscm_begin(PChart *chart, bool live, bool abf)
static bool p_vert_interior(PVert *v)
static PVert * p_vert_lookup(ParamHandle *handle, PHashKey key, const float co[3], PEdge *e)
static int PHashSizes[]
static void p_chart_uv_transform(PChart *chart, const float mat[2][2])
void GEO_uv_parametrizer_stretch_end(ParamHandle *phandle)
void GEO_uv_parametrizer_stretch_begin(ParamHandle *phandle)
static PFace * p_face_add_fill(PChart *chart, PVert *v1, PVert *v2, PVert *v3)
static void p_abf_free_system(PAbfSystem *sys)
static void p_chart_rotate_minimum_area(PChart *chart)
static float p_rectangle_area(float *p1, float *dir, float *p2, float *p3, float *p4)
static PEdge * p_boundary_edge_next(PEdge *e)
PEdgeFlag
@ PEDGE_DONE
@ PEDGE_SEAM
@ PEDGE_COLLAPSE_PAIR
@ PEDGE_FILLED
@ PEDGE_COLLAPSE_EDGE
@ PEDGE_COLLAPSE
@ PEDGE_VERTEX_SPLIT
@ PEDGE_SELECT
@ PEDGE_PIN
static void p_chart_stretch_minimize(PChart *chart, RNG *rng)
static void p_chart_uv_scale(PChart *chart, float scale)
PFaceFlag
@ PFACE_CONNECTED
@ PFACE_COLLAPSE
@ PFACE_FILLED
static void p_chart_delete(PChart *chart)
static void p_face_backup_uvs(PFace *f)
static int p_compare_geometric_uv(const void *a, const void *b)
#define ABF_MAX_ITER
static void p_chart_uv_bbox(PChart *chart, float minv[2], float maxv[2])
void GEO_uv_parametrizer_scale(ParamHandle *phandle, float x, float y)
PVertFlag
@ PVERT_INTERIOR
@ PVERT_COLLAPSE
@ PVERT_PIN
@ PVERT_SPLIT
@ PVERT_SELECT
void GEO_uv_parametrizer_lscm_solve(ParamHandle *phandle, int *count_changed, int *count_failed)
static void p_face_flip(PFace *f)
struct PHashLink PHashLink
static float p_stretch_compute_vertex(PVert *v)
static float p_chart_minimum_area_angle(PChart *chart)
void GEO_uv_parametrizer_average(ParamHandle *phandle, bool ignore_pinned, bool scale_uv, bool shear)
static bool p_edge_connect_pair(ParamHandle *handle, PEdge *e, bool topology_from_uvs, PEdge ***stack)
static int p_face_exists(ParamHandle *handle, const ParamKey *pvkeys, int i1, int i2, int i3)
ParamKey GEO_uv_find_pin_index(ParamHandle *handle, const int bmvertindex, const float uv[2])
static PEdge * p_wheel_edge_prev(PEdge *e)
void GEO_uv_parametrizer_delete(ParamHandle *phandle)
#define param_warning(message)
void GEO_uv_parametrizer_aspect_ratio(ParamHandle *phandle, float aspx, float aspy)
intptr_t PHashKey
static void p_flush_uvs(ParamHandle *handle, PChart *chart)
static float p_edge_uv_length(PEdge *e)
static int phash_size(PHash *ph)
static void p_vert_load_pin_select_uvs(ParamHandle *handle, PVert *v)
static float p_face_area(PFace *f)
static void p_chart_fill_boundary(PChart *chart, PEdge *be, int nedges)
static PHashLink * phash_lookup(PHash *ph, PHashKey key)
static void p_chart_uv_scale_xy(PChart *chart, float x, float y)
static bool p_chart_lscm_solve(ParamHandle *handle, PChart *chart)
static void p_face_restore_uvs(PFace *f)
PHandleState
@ PHANDLE_STATE_LSCM
@ PHANDLE_STATE_ALLOCATED
@ PHANDLE_STATE_CONSTRUCTED
@ PHANDLE_STATE_STRETCH
static void p_face_angles(PFace *f, float *r_a1, float *r_a2, float *r_a3)
struct PEdge PEdge
struct GeoUVPinIndex GeoUVPinIndex
static float p_vec_angle(const float v1[3], const float v2[3], const float v3[3])
void GEO_uv_parametrizer_stretch_blend(ParamHandle *phandle, float blend)
static PVert * p_vert_add(ParamHandle *handle, PHashKey key, const float co[3], PEdge *e)
static bool p_quad_split_direction(ParamHandle *handle, const float **co, const ParamKey *vkeys)
static PFace * p_face_add_construct(ParamHandle *handle, ParamKey key, const ParamKey *vkeys, const float **co, float **uv, int i1, int i2, int i3, const bool *pin, const bool *select)
static float p_abf_compute_gradient(PAbfSystem *sys, PChart *chart)
static void p_chart_lscm_transform_single_pin(PChart *chart)
static PChart ** p_split_charts(ParamHandle *handle, PChart *chart, int ncharts)
static FT_Error err