Blender  V3.3
polyfill_2d.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
32 #include "BLI_math.h"
33 #include "BLI_utildefines.h"
34 
35 #include "BLI_alloca.h"
36 #include "BLI_memarena.h"
37 
38 #include "BLI_polyfill_2d.h" /* own include */
39 
40 #include "BLI_strict_flags.h"
41 
42 /* avoid fan-fill topology */
43 #define USE_CLIP_EVEN
44 #define USE_CONVEX_SKIP
45 /* sweep back-and-forth about convex ears (avoids lop-sided fans) */
46 #define USE_CLIP_SWEEP
47 // #define USE_CONVEX_SKIP_TEST
48 
49 #ifdef USE_CONVEX_SKIP
50 # define USE_KDTREE
51 #endif
52 
53 /* disable in production, it can fail on near zero area ngons */
54 // #define USE_STRICT_ASSERT
55 
56 // #define DEBUG_TIME
57 #ifdef DEBUG_TIME
58 # include "PIL_time_utildefines.h"
59 #endif
60 
61 typedef signed char eSign;
62 
63 #ifdef USE_KDTREE
83 typedef bool axis_t;
84 
85 /* use for sorting */
86 typedef struct KDTreeNode2D_head {
90 
91 typedef struct KDTreeNode2D {
94  axis_t axis; /* range is only (0-1) */
98 
99 struct KDTree2D {
101  const float (*coords)[2];
104  uint *nodes_map; /* index -> node lookup */
105 };
106 
107 struct KDRange2D {
108  float min, max;
109 };
110 #endif /* USE_KDTREE */
111 
112 enum {
113  CONCAVE = -1,
115  CONVEX = 1,
116 };
117 
118 typedef struct PolyFill {
119  struct PolyIndex *indices; /* vertex aligned */
120 
121  const float (*coords)[2];
123 #ifdef USE_CONVEX_SKIP
125 #endif
126 
127  /* A polygon with n vertices has a triangulation of n-2 triangles. */
128  uint (*tris)[3];
130 
131 #ifdef USE_KDTREE
132  struct KDTree2D kdtree;
133 #endif
135 
137 typedef struct PolyIndex {
138  struct PolyIndex *next, *prev;
142 
143 /* based on libgdx 2013-11-28, apache 2.0 licensed */
144 
145 static void pf_coord_sign_calc(PolyFill *pf, PolyIndex *pi);
146 
148 #ifdef USE_CLIP_EVEN
149  ,
150  PolyIndex *pi_ear_init
151 #endif
152 #ifdef USE_CLIP_SWEEP
153  ,
154  bool reverse
155 #endif
156 );
157 
158 static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip);
159 static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip);
160 
162 {
163  if (UNLIKELY(a == 0.0f)) {
164  return 0;
165  }
166  if (a > 0.0f) {
167  return 1;
168  }
169 
170  return -1;
171 }
172 
179 BLI_INLINE float area_tri_signed_v2_alt_2x(const float v1[2], const float v2[2], const float v3[2])
180 {
181  float d2[2], d3[2];
182  sub_v2_v2v2(d2, v2, v1);
183  sub_v2_v2v2(d3, v3, v1);
184  return (d2[0] * d3[1]) - (d3[0] * d2[1]);
185 }
186 
187 static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float v3[2])
188 {
190 }
191 
192 #ifdef USE_KDTREE
193 # define KDNODE_UNSET ((uint)-1)
194 
195 enum {
197 };
198 
199 static void kdtree2d_new(struct KDTree2D *tree, uint tot, const float (*coords)[2])
200 {
201  /* set by caller */
202  // tree->nodes = nodes;
203  tree->coords = coords;
204  tree->root = KDNODE_UNSET;
205  tree->node_num = tot;
206 }
207 
211 static void kdtree2d_init(struct KDTree2D *tree, const uint coords_num, const PolyIndex *indices)
212 {
214  uint i;
215 
216  for (i = 0, node = tree->nodes; i < coords_num; i++) {
217  if (indices[i].sign != CONVEX) {
218  node->neg = node->pos = KDNODE_UNSET;
219  node->index = indices[i].index;
220  node->axis = 0;
221  node->flag = 0;
222  node++;
223  }
224  }
225 
226  BLI_assert(tree->node_num == (uint)(node - tree->nodes));
227 }
228 
230  KDTreeNode2D *nodes, uint node_num, axis_t axis, const float (*coords)[2], const uint ofs)
231 {
233  uint neg, pos, median, i, j;
234 
235  if (node_num <= 0) {
236  return KDNODE_UNSET;
237  }
238  if (node_num == 1) {
239  return 0 + ofs;
240  }
241 
242  /* Quick-sort style sorting around median. */
243  neg = 0;
244  pos = node_num - 1;
245  median = node_num / 2;
246 
247  while (pos > neg) {
248  const float co = coords[nodes[pos].index][axis];
249  i = neg - 1;
250  j = pos;
251 
252  while (1) {
253  while (coords[nodes[++i].index][axis] < co) { /* pass */
254  }
255  while (coords[nodes[--j].index][axis] > co && j > neg) { /* pass */
256  }
257 
258  if (i >= j) {
259  break;
260  }
261  SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&nodes[i], *(KDTreeNode2D_head *)&nodes[j]);
262  }
263 
264  SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&nodes[i], *(KDTreeNode2D_head *)&nodes[pos]);
265  if (i >= median) {
266  pos = i - 1;
267  }
268  if (i <= median) {
269  neg = i + 1;
270  }
271  }
272 
273  /* Set node and sort sub-nodes. */
274  node = &nodes[median];
275  node->axis = axis;
276  axis = !axis;
277  node->neg = kdtree2d_balance_recursive(nodes, median, axis, coords, ofs);
279  &nodes[median + 1], (node_num - (median + 1)), axis, coords, (median + 1) + ofs);
280 
281  return median + ofs;
282 }
283 
284 static void kdtree2d_balance(struct KDTree2D *tree)
285 {
286  tree->root = kdtree2d_balance_recursive(tree->nodes, tree->node_num, 0, tree->coords, 0);
287 }
288 
289 static void kdtree2d_init_mapping(struct KDTree2D *tree)
290 {
291  uint i;
293 
294  for (i = 0, node = tree->nodes; i < tree->node_num; i++, node++) {
295  if (node->neg != KDNODE_UNSET) {
296  tree->nodes[node->neg].parent = i;
297  }
298  if (node->pos != KDNODE_UNSET) {
299  tree->nodes[node->pos].parent = i;
300  }
301 
302  /* build map */
303  BLI_assert(tree->nodes_map[node->index] == KDNODE_UNSET);
304  tree->nodes_map[node->index] = i;
305  }
306 
307  tree->nodes[tree->root].parent = KDNODE_UNSET;
308 }
309 
311 {
312  uint node_index = tree->nodes_map[index];
314 
315  if (node_index == KDNODE_UNSET) {
316  return;
317  }
318 
319  tree->nodes_map[index] = KDNODE_UNSET;
320 
321  node = &tree->nodes[node_index];
322  tree->node_num -= 1;
323 
324  BLI_assert((node->flag & KDNODE_FLAG_REMOVED) == 0);
325  node->flag |= KDNODE_FLAG_REMOVED;
326 
327  while ((node->neg == KDNODE_UNSET) && (node->pos == KDNODE_UNSET) &&
328  (node->parent != KDNODE_UNSET)) {
329  KDTreeNode2D *node_parent = &tree->nodes[node->parent];
330 
331  BLI_assert((uint)(node - tree->nodes) == node_index);
332  if (node_parent->neg == node_index) {
333  node_parent->neg = KDNODE_UNSET;
334  }
335  else {
336  BLI_assert(node_parent->pos == node_index);
337  node_parent->pos = KDNODE_UNSET;
338  }
339 
340  if (node_parent->flag & KDNODE_FLAG_REMOVED) {
341  node_index = node->parent;
342  node = node_parent;
343  }
344  else {
345  break;
346  }
347  }
348 }
349 
350 static bool kdtree2d_isect_tri_recursive(const struct KDTree2D *tree,
351  const uint tri_index[3],
352  const float *tri_coords[3],
353  const float tri_center[2],
354  const struct KDRange2D bounds[2],
355  const KDTreeNode2D *node)
356 {
357  const float *co = tree->coords[node->index];
358 
359  /* bounds then triangle intersect */
360  if ((node->flag & KDNODE_FLAG_REMOVED) == 0) {
361  /* bounding box test first */
362  if ((co[0] >= bounds[0].min) && (co[0] <= bounds[0].max) && (co[1] >= bounds[1].min) &&
363  (co[1] <= bounds[1].max)) {
364  if ((span_tri_v2_sign(tri_coords[0], tri_coords[1], co) != CONCAVE) &&
365  (span_tri_v2_sign(tri_coords[1], tri_coords[2], co) != CONCAVE) &&
366  (span_tri_v2_sign(tri_coords[2], tri_coords[0], co) != CONCAVE)) {
367  if (!ELEM(node->index, tri_index[0], tri_index[1], tri_index[2])) {
368  return true;
369  }
370  }
371  }
372  }
373 
374 # define KDTREE2D_ISECT_TRI_RECURSE_NEG \
375  (((node->neg != KDNODE_UNSET) && (co[node->axis] >= bounds[node->axis].min)) && \
376  (kdtree2d_isect_tri_recursive( \
377  tree, tri_index, tri_coords, tri_center, bounds, &tree->nodes[node->neg])))
378 # define KDTREE2D_ISECT_TRI_RECURSE_POS \
379  (((node->pos != KDNODE_UNSET) && (co[node->axis] <= bounds[node->axis].max)) && \
380  (kdtree2d_isect_tri_recursive( \
381  tree, tri_index, tri_coords, tri_center, bounds, &tree->nodes[node->pos])))
382 
383  if (tri_center[node->axis] > co[node->axis]) {
385  return true;
386  }
388  return true;
389  }
390  }
391  else {
393  return true;
394  }
396  return true;
397  }
398  }
399 
400 # undef KDTREE2D_ISECT_TRI_RECURSE_NEG
401 # undef KDTREE2D_ISECT_TRI_RECURSE_POS
402 
403  BLI_assert(node->index != KDNODE_UNSET);
404 
405  return false;
406 }
407 
408 static bool kdtree2d_isect_tri(struct KDTree2D *tree, const uint ind[3])
409 {
410  const float *vs[3];
411  uint i;
412  struct KDRange2D bounds[2] = {
413  {FLT_MAX, -FLT_MAX},
414  {FLT_MAX, -FLT_MAX},
415  };
416  float tri_center[2] = {0.0f, 0.0f};
417 
418  for (i = 0; i < 3; i++) {
419  vs[i] = tree->coords[ind[i]];
420 
421  add_v2_v2(tri_center, vs[i]);
422 
423  CLAMP_MAX(bounds[0].min, vs[i][0]);
424  CLAMP_MIN(bounds[0].max, vs[i][0]);
425  CLAMP_MAX(bounds[1].min, vs[i][1]);
426  CLAMP_MIN(bounds[1].max, vs[i][1]);
427  }
428 
429  mul_v2_fl(tri_center, 1.0f / 3.0f);
430 
431  return kdtree2d_isect_tri_recursive(tree, ind, vs, tri_center, bounds, &tree->nodes[tree->root]);
432 }
433 
434 #endif /* USE_KDTREE */
435 
437 {
438  return pf->tris[pf->tris_num++];
439 }
440 
442 {
443 #ifdef USE_KDTREE
444  /* avoid double lookups, since convex coords are ignored when testing intersections */
445  if (pf->kdtree.node_num) {
446  kdtree2d_node_remove(&pf->kdtree, pi->index);
447  }
448 #endif
449 
450  pi->next->prev = pi->prev;
451  pi->prev->next = pi->next;
452 
453  if (UNLIKELY(pf->indices == pi)) {
454  pf->indices = pi->next;
455  }
456 #ifdef DEBUG
457  pi->index = (uint)-1;
458  pi->next = pi->prev = NULL;
459 #endif
460 
461  pf->coords_num -= 1;
462 }
463 
465 {
466  /* localize */
467  PolyIndex *pi_ear;
468 
469 #ifdef USE_CLIP_EVEN
470  PolyIndex *pi_ear_init = pf->indices;
471 #endif
472 #ifdef USE_CLIP_SWEEP
473  bool reverse = false;
474 #endif
475 
476  while (pf->coords_num > 3) {
477  PolyIndex *pi_prev, *pi_next;
478  eSign sign_orig_prev, sign_orig_next;
479 
480  pi_ear = pf_ear_tip_find(pf
481 #ifdef USE_CLIP_EVEN
482  ,
483  pi_ear_init
484 #endif
485 #ifdef USE_CLIP_SWEEP
486  ,
487  reverse
488 #endif
489  );
490 
491 #ifdef USE_CONVEX_SKIP
492  if (pi_ear->sign != CONVEX) {
493  pf->coords_num_concave -= 1;
494  }
495 #endif
496 
497  pi_prev = pi_ear->prev;
498  pi_next = pi_ear->next;
499 
500  pf_ear_tip_cut(pf, pi_ear);
501 
502  /* The type of the two vertices adjacent to the clipped vertex may have changed. */
503  sign_orig_prev = pi_prev->sign;
504  sign_orig_next = pi_next->sign;
505 
506  /* check if any verts became convex the (else if)
507  * case is highly unlikely but may happen with degenerate polygons */
508  if (sign_orig_prev != CONVEX) {
509  pf_coord_sign_calc(pf, pi_prev);
510 #ifdef USE_CONVEX_SKIP
511  if (pi_prev->sign == CONVEX) {
512  pf->coords_num_concave -= 1;
513 # ifdef USE_KDTREE
514  kdtree2d_node_remove(&pf->kdtree, pi_prev->index);
515 # endif
516  }
517 #endif
518  }
519  if (sign_orig_next != CONVEX) {
520  pf_coord_sign_calc(pf, pi_next);
521 #ifdef USE_CONVEX_SKIP
522  if (pi_next->sign == CONVEX) {
523  pf->coords_num_concave -= 1;
524 # ifdef USE_KDTREE
525  kdtree2d_node_remove(&pf->kdtree, pi_next->index);
526 # endif
527  }
528 #endif
529  }
530 
531 #ifdef USE_CLIP_EVEN
532 # ifdef USE_CLIP_SWEEP
533  pi_ear_init = reverse ? pi_prev->prev : pi_next->next;
534 # else
535  pi_ear_init = pi_next->next;
536 # endif
537 #endif
538 
539 #ifdef USE_CLIP_EVEN
540 # ifdef USE_CLIP_SWEEP
541  if (pi_ear_init->sign != CONVEX) {
542  /* take the extra step since this ear isn't a good candidate */
543  pi_ear_init = reverse ? pi_ear_init->prev : pi_ear_init->next;
544  reverse = !reverse;
545  }
546 # endif
547 #else
548  if ((reverse ? pi_prev->prev : pi_next->next)->sign != CONVEX) {
549  reverse = !reverse;
550  }
551 #endif
552  }
553 
554  if (pf->coords_num == 3) {
555  uint *tri = pf_tri_add(pf);
556  pi_ear = pf->indices;
557  tri[0] = pi_ear->index;
558  pi_ear = pi_ear->next;
559  tri[1] = pi_ear->index;
560  pi_ear = pi_ear->next;
561  tri[2] = pi_ear->index;
562  }
563 }
564 
569 {
570  /* localize */
571  const float(*coords)[2] = pf->coords;
572 
573  pi->sign = span_tri_v2_sign(coords[pi->prev->index], coords[pi->index], coords[pi->next->index]);
574 }
575 
577 #ifdef USE_CLIP_EVEN
578  ,
579  PolyIndex *pi_ear_init
580 #endif
581 #ifdef USE_CLIP_SWEEP
582  ,
583  bool reverse
584 #endif
585 )
586 {
587  /* localize */
588  const uint coords_num = pf->coords_num;
589  PolyIndex *pi_ear;
590 
591  uint i;
592 
593 #ifdef USE_CLIP_EVEN
594  pi_ear = pi_ear_init;
595 #else
596  pi_ear = pf->indices;
597 #endif
598 
599  i = coords_num;
600  while (i--) {
601  if (pf_ear_tip_check(pf, pi_ear)) {
602  return pi_ear;
603  }
604 #ifdef USE_CLIP_SWEEP
605  pi_ear = reverse ? pi_ear->prev : pi_ear->next;
606 #else
607  pi_ear = pi_ear->next;
608 #endif
609  }
610 
611  /* Desperate mode: if no vertex is an ear tip,
612  * we are dealing with a degenerate polygon (e.g. nearly collinear).
613  * Note that the input was not necessarily degenerate,
614  * but we could have made it so by clipping some valid ears.
615  *
616  * Idea taken from Martin Held, "FIST: Fast industrial-strength triangulation of polygons",
617  * Algorithmica (1998),
618  * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291
619  *
620  * Return a convex or tangential vertex if one exists.
621  */
622 
623 #ifdef USE_CLIP_EVEN
624  pi_ear = pi_ear_init;
625 #else
626  pi_ear = pf->indices;
627 #endif
628 
629  i = coords_num;
630  while (i--) {
631  if (pi_ear->sign != CONCAVE) {
632  return pi_ear;
633  }
634  pi_ear = pi_ear->next;
635  }
636 
637  /* If all vertices are concave, just return the last one. */
638  return pi_ear;
639 }
640 
641 static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip)
642 {
643 #ifndef USE_KDTREE
644  /* localize */
645  const float(*coords)[2] = pf->coords;
646  PolyIndex *pi_curr;
647 
648  const float *v1, *v2, *v3;
649 #endif
650 
651 #if defined(USE_CONVEX_SKIP) && !defined(USE_KDTREE)
652  uint coords_num_concave_checked = 0;
653 #endif
654 
655 #ifdef USE_CONVEX_SKIP
656 
657 # ifdef USE_CONVEX_SKIP_TEST
658  /* check if counting is wrong */
659  {
660  uint coords_num_concave_test = 0;
661  PolyIndex *pi_iter = pi_ear_tip;
662  do {
663  if (pi_iter->sign != CONVEX) {
664  coords_num_concave_test += 1;
665  }
666  } while ((pi_iter = pi_iter->next) != pi_ear_tip);
667  BLI_assert(coords_num_concave_test == pf->coords_num_concave);
668  }
669 # endif
670 
671  /* fast-path for circles */
672  if (pf->coords_num_concave == 0) {
673  return true;
674  }
675 #endif
676 
677  if (UNLIKELY(pi_ear_tip->sign == CONCAVE)) {
678  return false;
679  }
680 
681 #ifdef USE_KDTREE
682  {
683  const uint ind[3] = {pi_ear_tip->index, pi_ear_tip->next->index, pi_ear_tip->prev->index};
684 
685  if (kdtree2d_isect_tri(&pf->kdtree, ind)) {
686  return false;
687  }
688  }
689 #else
690 
691  v1 = coords[pi_ear_tip->prev->index];
692  v2 = coords[pi_ear_tip->index];
693  v3 = coords[pi_ear_tip->next->index];
694 
695  /* Check if any point is inside the triangle formed by previous, current and next vertices.
696  * Only consider vertices that are not part of this triangle,
697  * or else we'll always find one inside. */
698 
699  for (pi_curr = pi_ear_tip->next->next; pi_curr != pi_ear_tip->prev; pi_curr = pi_curr->next) {
700  /* Concave vertices can obviously be inside the candidate ear,
701  * but so can tangential vertices if they coincide with one of the triangle's vertices. */
702  if (pi_curr->sign != CONVEX) {
703  const float *v = coords[pi_curr->index];
704  /* Because the polygon has clockwise winding order,
705  * the area sign will be positive if the point is strictly inside.
706  * It will be 0 on the edge, which we want to include as well. */
707 
708  /* NOTE: check (v3, v1) first since it fails _far_ more often than the other 2 checks
709  * (those fail equally).
710  * It's logical - the chance is low that points exist on the
711  * same side as the ear we're clipping off. */
712  if ((span_tri_v2_sign(v3, v1, v) != CONCAVE) && (span_tri_v2_sign(v1, v2, v) != CONCAVE) &&
713  (span_tri_v2_sign(v2, v3, v) != CONCAVE)) {
714  return false;
715  }
716 
717 # ifdef USE_CONVEX_SKIP
718  coords_num_concave_checked += 1;
719  if (coords_num_concave_checked == pf->coords_num_concave) {
720  break;
721  }
722 # endif
723  }
724  }
725 #endif /* USE_KDTREE */
726 
727  return true;
728 }
729 
730 static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip)
731 {
732  uint *tri = pf_tri_add(pf);
733 
734  tri[0] = pi_ear_tip->prev->index;
735  tri[1] = pi_ear_tip->index;
736  tri[2] = pi_ear_tip->next->index;
737 
738  pf_coord_remove(pf, pi_ear_tip);
739 }
740 
745  const float (*coords)[2],
746  const uint coords_num,
747  int coords_sign,
748  uint (*r_tris)[3],
749  PolyIndex *r_indices)
750 {
751  /* localize */
752  PolyIndex *indices = r_indices;
753 
754  uint i;
755 
756  /* assign all polyfill members here */
757  pf->indices = r_indices;
758  pf->coords = coords;
759  pf->coords_num = coords_num;
760 #ifdef USE_CONVEX_SKIP
761  pf->coords_num_concave = 0;
762 #endif
763  pf->tris = r_tris;
764  pf->tris_num = 0;
765 
766  if (coords_sign == 0) {
767  coords_sign = (cross_poly_v2(coords, coords_num) >= 0.0f) ? 1 : -1;
768  }
769  else {
770  /* check we're passing in correct args */
771 #ifdef USE_STRICT_ASSERT
772 # ifndef NDEBUG
773  if (coords_sign == 1) {
774  BLI_assert(cross_poly_v2(coords, coords_num) >= 0.0f);
775  }
776  else {
777  BLI_assert(cross_poly_v2(coords, coords_num) <= 0.0f);
778  }
779 # endif
780 #endif
781  }
782 
783  if (coords_sign == 1) {
784  for (i = 0; i < coords_num; i++) {
785  indices[i].next = &indices[i + 1];
786  indices[i].prev = &indices[i - 1];
787  indices[i].index = i;
788  }
789  }
790  else {
791  /* reversed */
792  uint n = coords_num - 1;
793  for (i = 0; i < coords_num; i++) {
794  indices[i].next = &indices[i + 1];
795  indices[i].prev = &indices[i - 1];
796  indices[i].index = (n - i);
797  }
798  }
799  indices[0].prev = &indices[coords_num - 1];
800  indices[coords_num - 1].next = &indices[0];
801 
802  for (i = 0; i < coords_num; i++) {
803  PolyIndex *pi = &indices[i];
804  pf_coord_sign_calc(pf, pi);
805 #ifdef USE_CONVEX_SKIP
806  if (pi->sign != CONVEX) {
807  pf->coords_num_concave += 1;
808  }
809 #endif
810  }
811 }
812 
813 static void polyfill_calc(PolyFill *pf)
814 {
815 #ifdef USE_KDTREE
816 # ifdef USE_CONVEX_SKIP
817  if (pf->coords_num_concave)
818 # endif
819  {
820  kdtree2d_new(&pf->kdtree, pf->coords_num_concave, pf->coords);
821  kdtree2d_init(&pf->kdtree, pf->coords_num, pf->indices);
822  kdtree2d_balance(&pf->kdtree);
823  kdtree2d_init_mapping(&pf->kdtree);
824  }
825 #endif
826 
828 }
829 
830 void BLI_polyfill_calc_arena(const float (*coords)[2],
831  const uint coords_num,
832  const int coords_sign,
833  uint (*r_tris)[3],
834 
835  struct MemArena *arena)
836 {
837  PolyFill pf;
838  PolyIndex *indices = BLI_memarena_alloc(arena, sizeof(*indices) * coords_num);
839 
840 #ifdef DEBUG_TIME
841  TIMEIT_START(polyfill2d);
842 #endif
843 
845  coords,
846  coords_num,
847  coords_sign,
848  r_tris,
849  /* cache */
850  indices);
851 
852 #ifdef USE_KDTREE
853  if (pf.coords_num_concave) {
854  pf.kdtree.nodes = BLI_memarena_alloc(arena, sizeof(*pf.kdtree.nodes) * pf.coords_num_concave);
855  pf.kdtree.nodes_map = memset(
856  BLI_memarena_alloc(arena, sizeof(*pf.kdtree.nodes_map) * coords_num),
857  0xff,
858  sizeof(*pf.kdtree.nodes_map) * coords_num);
859  }
860  else {
861  pf.kdtree.node_num = 0;
862  }
863 #endif
864 
865  polyfill_calc(&pf);
866 
867  /* indices are no longer needed,
868  * caller can clear arena */
869 
870 #ifdef DEBUG_TIME
871  TIMEIT_END(polyfill2d);
872 #endif
873 }
874 
875 void BLI_polyfill_calc(const float (*coords)[2],
876  const uint coords_num,
877  const int coords_sign,
878  uint (*r_tris)[3])
879 {
880  /* Fallback to heap memory for large allocations.
881  * Avoid running out of stack memory on systems with 512kb stack (macOS).
882  * This happens at around 13,000 points, use a much lower value to be safe. */
883  if (UNLIKELY(coords_num > 8192)) {
884  /* The buffer size only accounts for the index allocation,
885  * worst case we do two allocations when concave, while we should try to be efficient,
886  * any caller that relies on this frequently should use #BLI_polyfill_calc_arena directly. */
887  MemArena *arena = BLI_memarena_new(sizeof(PolyIndex) * coords_num, __func__);
888  BLI_polyfill_calc_arena(coords, coords_num, coords_sign, r_tris, arena);
889  BLI_memarena_free(arena);
890  return;
891  }
892 
893  PolyFill pf;
894  PolyIndex *indices = BLI_array_alloca(indices, coords_num);
895 
896 #ifdef DEBUG_TIME
897  TIMEIT_START(polyfill2d);
898 #endif
899 
901  coords,
902  coords_num,
903  coords_sign,
904  r_tris,
905  /* cache */
906  indices);
907 
908 #ifdef USE_KDTREE
909  if (pf.coords_num_concave) {
910  pf.kdtree.nodes = BLI_array_alloca(pf.kdtree.nodes, pf.coords_num_concave);
911  pf.kdtree.nodes_map = memset(BLI_array_alloca(pf.kdtree.nodes_map, coords_num),
912  0xff,
913  sizeof(*pf.kdtree.nodes_map) * coords_num);
914  }
915  else {
916  pf.kdtree.node_num = 0;
917  }
918 #endif
919 
920  polyfill_calc(&pf);
921 
922 #ifdef DEBUG_TIME
923  TIMEIT_END(polyfill2d);
924 #endif
925 }
typedef float(TangentPoint)[2]
#define BLI_array_alloca(arr, realsize)
Definition: BLI_alloca.h:22
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_INLINE
unsigned char axis_t
Definition: BLI_kdopbvh.c:61
float cross_poly_v2(const float verts[][2], unsigned int nr)
Definition: math_geom.c:141
MINLINE void mul_v2_fl(float r[2], float f)
MINLINE void add_v2_v2(float r[2], const float a[2])
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
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
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
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
unsigned short ushort
Definition: BLI_sys_types.h:68
#define CLAMP_MAX(a, c)
#define SWAP(type, a, b)
#define UNLIKELY(x)
#define ELEM(...)
#define CLAMP_MIN(a, b)
_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
Utility defines for timing/benchmarks.
#define TIMEIT_START(var)
#define TIMEIT_END(var)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert * v
static btDbvtVolume bounds(btDbvtNode **leaves, int count)
Definition: btDbvt.cpp:299
OperationNode * node
void * tree
#define pf(_x, _i)
Prefetch 64.
Definition: gim_memory.h:48
uint pos
ccl_gpu_kernel_postfix int ccl_global int * indices
static unsigned a[3]
Definition: RandGen.cpp:78
double sign(double arg)
Definition: utility.h:250
static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip)
Definition: polyfill_2d.c:641
static PolyIndex * pf_ear_tip_find(PolyFill *pf, PolyIndex *pi_ear_init, bool reverse)
Definition: polyfill_2d.c:576
static bool kdtree2d_isect_tri(struct KDTree2D *tree, const uint ind[3])
Definition: polyfill_2d.c:408
struct KDTreeNode2D KDTreeNode2D
static void kdtree2d_init_mapping(struct KDTree2D *tree)
Definition: polyfill_2d.c:289
signed char eSign
Definition: polyfill_2d.c:61
struct KDTreeNode2D_head KDTreeNode2D_head
@ TANGENTIAL
Definition: polyfill_2d.c:114
@ CONCAVE
Definition: polyfill_2d.c:113
@ CONVEX
Definition: polyfill_2d.c:115
BLI_INLINE eSign signum_enum(float a)
Definition: polyfill_2d.c:161
struct PolyIndex PolyIndex
static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip)
Definition: polyfill_2d.c:730
#define KDTREE2D_ISECT_TRI_RECURSE_NEG
static bool kdtree2d_isect_tri_recursive(const struct KDTree2D *tree, const uint tri_index[3], const float *tri_coords[3], const float tri_center[2], const struct KDRange2D bounds[2], const KDTreeNode2D *node)
Definition: polyfill_2d.c:350
BLI_INLINE float area_tri_signed_v2_alt_2x(const float v1[2], const float v2[2], const float v3[2])
Definition: polyfill_2d.c:179
struct PolyFill PolyFill
static void kdtree2d_node_remove(struct KDTree2D *tree, uint index)
Definition: polyfill_2d.c:310
@ KDNODE_FLAG_REMOVED
Definition: polyfill_2d.c:196
void BLI_polyfill_calc_arena(const float(*coords)[2], const uint coords_num, const int coords_sign, uint(*r_tris)[3], struct MemArena *arena)
Definition: polyfill_2d.c:830
static void pf_coord_sign_calc(PolyFill *pf, PolyIndex *pi)
Definition: polyfill_2d.c:568
#define USE_CLIP_EVEN
Definition: polyfill_2d.c:43
void BLI_polyfill_calc(const float(*coords)[2], const uint coords_num, const int coords_sign, uint(*r_tris)[3])
Definition: polyfill_2d.c:875
#define KDNODE_UNSET
Definition: polyfill_2d.c:193
static uint kdtree2d_balance_recursive(KDTreeNode2D *nodes, uint node_num, axis_t axis, const float(*coords)[2], const uint ofs)
Definition: polyfill_2d.c:229
#define USE_CLIP_SWEEP
Definition: polyfill_2d.c:46
static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float v3[2])
Definition: polyfill_2d.c:187
static void kdtree2d_balance(struct KDTree2D *tree)
Definition: polyfill_2d.c:284
static uint * pf_tri_add(PolyFill *pf)
Definition: polyfill_2d.c:436
bool axis_t
Definition: polyfill_2d.c:83
static void kdtree2d_init(struct KDTree2D *tree, const uint coords_num, const PolyIndex *indices)
Definition: polyfill_2d.c:211
static void polyfill_prepare(PolyFill *pf, const float(*coords)[2], const uint coords_num, int coords_sign, uint(*r_tris)[3], PolyIndex *r_indices)
Definition: polyfill_2d.c:744
#define KDTREE2D_ISECT_TRI_RECURSE_POS
static void kdtree2d_new(struct KDTree2D *tree, uint tot, const float(*coords)[2])
Definition: polyfill_2d.c:199
static void polyfill_calc(PolyFill *pf)
Definition: polyfill_2d.c:813
static void pf_coord_remove(PolyFill *pf, PolyIndex *pi)
Definition: polyfill_2d.c:441
static void pf_triangulate(PolyFill *pf)
Definition: polyfill_2d.c:464
#define min(a, b)
Definition: sort.c:35
float max
Definition: polyfill_2d.c:108
float min
Definition: polyfill_2d.c:108
KDTreeNode2D * nodes
Definition: polyfill_2d.c:100
uint root
Definition: polyfill_2d.c:102
uint node_num
Definition: polyfill_2d.c:103
uint * nodes_map
Definition: polyfill_2d.c:104
const float(* coords)[2]
Definition: polyfill_2d.c:101
ushort flag
Definition: polyfill_2d.c:95
axis_t axis
Definition: polyfill_2d.c:94
uint coords_num
Definition: polyfill_2d.c:122
struct PolyIndex * indices
Definition: polyfill_2d.c:119
uint(* tris)[3]
Definition: polyfill_2d.c:128
const float(* coords)[2]
Definition: polyfill_2d.c:121
uint coords_num_concave
Definition: polyfill_2d.c:124
uint tris_num
Definition: polyfill_2d.c:129
struct KDTree2D kdtree
Definition: polyfill_2d.c:132
eSign sign
Definition: polyfill_2d.c:140
struct PolyIndex * prev
Definition: polyfill_2d.c:138
struct PolyIndex * next
Definition: polyfill_2d.c:138
uint index
Definition: polyfill_2d.c:139
float max