Blender V5.3
polyfill_2d.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
33
34#include "BLI_utildefines.hh"
35
36#include <algorithm>
37#include <cstdlib>
38
39#include "MEM_guardedalloc.h"
40
41#include "BLI_alloca.hh"
42#include "BLI_enum_flags.hh"
43#include "BLI_math_geom_c.hh"
44#include "BLI_math_vector_c.hh"
45#include "BLI_memarena.hh"
46
47#include "BLI_polyfill_2d.hh" /* own include */
48
49#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
50
51namespace blender {
52
53/* avoid fan-fill topology */
54#define USE_CLIP_EVEN
55#define USE_CONVEX_SKIP
56/* sweep back-and-forth about convex ears (avoids lop-sided fans) */
57#define USE_CLIP_SWEEP
58// #define USE_CONVEX_SKIP_TEST
59
60#ifdef USE_CONVEX_SKIP
61# define USE_KDTREE
62#endif
63
64#ifdef USE_KDTREE
66# define USE_KDTREE_INDEX_CACHE
67# ifdef USE_KDTREE_INDEX_CACHE
68# define KDTREE_INDEX_CACHE_UNSET uint32_t(-1)
69# endif
71# define USE_PRECOMPUTED_ISECT
72#endif
73
74/* disable in production, it can fail on near zero area ngons */
75// #define USE_STRICT_ASSERT
76
77// #define DEBUG_TIME
78#ifdef DEBUG_TIME
80#endif
81
82namespace {
83
84using eSign = int8_t;
85
86#ifdef USE_KDTREE
105
106using axis_t = uint8_t;
107
108/* use for sorting */
109struct KDTreeNode2D_head {
110 uint32_t neg, pos;
112};
113
114struct KDTreeNode2D {
115 uint32_t neg, pos;
117 axis_t axis; /* range is only (0-1) */
118 uint16_t flag;
119 uint32_t parent;
120};
121
122struct KDTree2D {
123 KDTreeNode2D *nodes;
124 const float (*coords)[2];
125 uint32_t root;
126 uint32_t node_num;
127 uint32_t *nodes_map; /* index -> node lookup */
128};
129
130struct KDRange2D {
131 float min, max;
132};
133#endif /* USE_KDTREE */
134
135enum {
136 CONCAVE = -1,
137 TANGENTIAL = 0,
138 CONVEX = 1,
139};
140
141#ifdef USE_KDTREE_INDEX_CACHE
142enum class PolyIndexFlag : uint8_t {
147 IndexCacheDirty = 1 << 0,
148};
149ENUM_OPERATORS(PolyIndexFlag);
150#endif
151
153struct PolyIndex {
154 PolyIndex *next, *prev;
156 eSign sign;
157#ifdef USE_KDTREE_INDEX_CACHE
158 PolyIndexFlag flag;
160 uint32_t index_last_hit;
161#endif
162};
163
164struct PolyFill {
165 PolyIndex *indices; /* vertex aligned */
166
167 const float (*coords)[2];
168 uint32_t coords_num;
169#ifdef USE_CONVEX_SKIP
170 uint32_t coords_num_concave;
171#endif
172
173 /* A polygon with n vertices has a triangulation of n-2 triangles. */
174 uint32_t (*tris)[3];
175 uint32_t tris_num;
176
177#ifdef USE_KDTREE
178 KDTree2D kdtree;
179#endif
180};
181
182} // namespace
183
184#ifdef USE_PRECOMPUTED_ISECT
190 float edge[3][2];
192 float c[3];
193};
194
199static void tri_isect_precomputed_init(TriIsectPrecomputed *t, const float *const vs[3])
200{
201 sub_v2_v2v2(t->edge[0], vs[1], vs[0]);
202 sub_v2_v2v2(t->edge[1], vs[2], vs[1]);
203 sub_v2_v2v2(t->edge[2], vs[0], vs[2]);
204 t->c[0] = (t->edge[0][0] * vs[0][1]) - (vs[0][0] * t->edge[0][1]);
205 t->c[1] = (t->edge[1][0] * vs[1][1]) - (vs[1][0] * t->edge[1][1]);
206 t->c[2] = (t->edge[2][0] * vs[2][1]) - (vs[2][0] * t->edge[2][1]);
207}
208
215static bool tri_isect_precomputed_test(const TriIsectPrecomputed *t, const float co[2])
216{
217 return ((t->edge[1][1] * co[0]) - (t->edge[1][0] * co[1]) + t->c[1] >= 0.0f) &&
218 ((t->edge[2][1] * co[0]) - (t->edge[2][0] * co[1]) + t->c[2] >= 0.0f) &&
219 ((t->edge[0][1] * co[0]) - (t->edge[0][0] * co[1]) + t->c[0] >= 0.0f);
220}
221#endif /* USE_PRECOMPUTED_ISECT */
222
223/* Based on LIBGDX 2013-11-28, APACHE 2.0 licensed. */
224
225static void pf_coord_sign_calc(const PolyFill *pf, PolyIndex *pi);
226
227static PolyIndex *pf_ear_tip_find(PolyFill *pf
228#ifdef USE_CLIP_EVEN
229 ,
230 PolyIndex *pi_ear_init
231#endif
232#ifdef USE_CLIP_SWEEP
233 ,
234 bool reverse
235#endif
236);
237
238static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip, const eSign sign_accept);
239static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip);
240
242{
243 if (a > 0.0f) {
244 return CONVEX;
245 }
246 if (a == 0.0f) [[unlikely]] {
247 return TANGENTIAL;
248 }
249 return CONCAVE;
250}
251
258BLI_INLINE float area_tri_signed_v2_alt_2x(const float v1[2], const float v2[2], const float v3[2])
259{
260 float d2[2], d3[2];
261 sub_v2_v2v2(d2, v2, v1);
262 sub_v2_v2v2(d3, v3, v1);
263 return (d2[0] * d3[1]) - (d3[0] * d2[1]);
264}
265
266static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float v3[2])
267{
269}
270
271#ifdef USE_KDTREE
272# define KDNODE_UNSET (uint32_t(-1))
273
274enum {
276};
277
278static void kdtree2d_new(KDTree2D *tree, uint32_t tot, const float (*coords)[2])
279{
280 /* set by caller */
281 // tree->nodes = nodes;
282 tree->coords = coords;
283 tree->root = KDNODE_UNSET;
284 tree->node_num = tot;
285}
286
290static void kdtree2d_init(KDTree2D *tree, const uint32_t coords_num, const PolyIndex *indices)
291{
292 KDTreeNode2D *node;
293 uint32_t i;
294
295 for (i = 0, node = tree->nodes; i < coords_num; i++) {
296 if (indices[i].sign != CONVEX) {
297 node->neg = node->pos = KDNODE_UNSET;
298 node->index = indices[i].index;
299 node->axis = 0;
300 node->flag = 0;
301 node++;
302 }
303 }
304
305 BLI_assert(tree->node_num == uint32_t(node - tree->nodes));
306}
307
309 uint32_t node_num,
310 axis_t axis,
311 const float (*coords)[2],
312 const uint32_t ofs)
313{
314 KDTreeNode2D *node;
315 uint32_t neg, pos, median, i, j;
316
317 if (node_num <= 0) {
318 return KDNODE_UNSET;
319 }
320 if (node_num == 1) {
321 return 0 + ofs;
322 }
323
324 /* Quick-sort style sorting around median. */
325 neg = 0;
326 pos = node_num - 1;
327 median = node_num / 2;
328
329 while (pos > neg) {
330 const float co = coords[nodes[pos].index][axis];
331 i = neg - 1;
332 j = pos;
333
334 while (true) {
335 while (coords[nodes[++i].index][axis] < co) { /* pass */
336 }
337 while (coords[nodes[--j].index][axis] > co && j > neg) { /* pass */
338 }
339
340 if (i >= j) {
341 break;
342 }
343 SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&nodes[i], *(KDTreeNode2D_head *)&nodes[j]);
344 }
345
346 SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&nodes[i], *(KDTreeNode2D_head *)&nodes[pos]);
347 if (i >= median) {
348 pos = i - 1;
349 }
350 if (i <= median) {
351 neg = i + 1;
352 }
353 }
354
355 /* Set node and sort sub-nodes. */
356 node = &nodes[median];
357 node->axis = axis;
358 axis = !axis;
359 node->neg = kdtree2d_balance_recursive(nodes, median, axis, coords, ofs);
361 &nodes[median + 1], (node_num - (median + 1)), axis, coords, (median + 1) + ofs);
362
363 return median + ofs;
364}
365
366static void kdtree2d_balance(KDTree2D *tree)
367{
368 tree->root = kdtree2d_balance_recursive(tree->nodes, tree->node_num, 0, tree->coords, 0);
369}
370
371static void kdtree2d_init_mapping(KDTree2D *tree)
372{
373 uint32_t i;
374 KDTreeNode2D *node;
375
376 for (i = 0, node = tree->nodes; i < tree->node_num; i++, node++) {
377 if (node->neg != KDNODE_UNSET) {
378 tree->nodes[node->neg].parent = i;
379 }
380 if (node->pos != KDNODE_UNSET) {
381 tree->nodes[node->pos].parent = i;
382 }
383
384 /* build map */
385 BLI_assert(tree->nodes_map[node->index] == KDNODE_UNSET);
386 tree->nodes_map[node->index] = i;
387 }
388
389 tree->nodes[tree->root].parent = KDNODE_UNSET;
390}
391
392static void kdtree2d_node_remove(KDTree2D *tree, uint32_t index)
393{
394 uint32_t node_index = tree->nodes_map[index];
395 KDTreeNode2D *node;
396
397 if (node_index == KDNODE_UNSET) {
398 return;
399 }
400
401 tree->nodes_map[index] = KDNODE_UNSET;
402
403 node = &tree->nodes[node_index];
404 tree->node_num -= 1;
405
406 BLI_assert((node->flag & KDNODE_FLAG_REMOVED) == 0);
407 node->flag |= KDNODE_FLAG_REMOVED;
408
409 /* Walk up the tree, performing two operations to keep the tree compact:
410 * - Disconnect: Remove childless nodes from their parent.
411 * - Collapse: When a node has exactly one child, connect that child
412 * directly to the grandparent, bypassing this removed node.
413 *
414 * Note that while this isn't a replacement for re-balancing,
415 * given the nature of polygon filling and it's use of the KD-tree
416 * the overhead of the rebalancing can't be justified.
417 * Only perform KD-tree manipulations that can be done efficiently as part of removal. */
418 while (node->parent != KDNODE_UNSET) {
419 uint32_t node_child;
420 if (node->neg == KDNODE_UNSET) {
421 node_child = node->pos;
422 }
423 else if (node->pos == KDNODE_UNSET) {
424 node_child = node->neg;
425 }
426 else {
427 /* Both children set, nothing to collapse. */
428 break;
429 }
430
431 /* Update parent's reference to this node:
432 * - If one child exists: collapse by connecting child directly to grandparent,
433 * bypassing this removed node and shortening the tree path.
434 * - If no children: disconnect entirely (set parent's reference to #KDNODE_UNSET). */
435 BLI_assert(uint32_t(node - tree->nodes) == node_index);
436 KDTreeNode2D *node_parent = &tree->nodes[node->parent];
437 if (node_parent->neg == node_index) {
438 node_parent->neg = node_child;
439 }
440 else {
441 BLI_assert(node_parent->pos == node_index);
442 node_parent->pos = node_child;
443 }
444
445 if (node_child != KDNODE_UNSET) {
446 tree->nodes[node_child].parent = node->parent;
447 }
448
449 if ((node_parent->flag & KDNODE_FLAG_REMOVED) == 0) {
450 break;
451 }
452 node_index = node->parent;
453 node = node_parent;
454 }
455}
456
460static uint32_t kdtree2d_isect_tri_recursive(const KDTree2D *tree,
461 const uint32_t tri_index[3],
463 const TriIsectPrecomputed *tri_isect,
464# else
465 const float *tri_coords[3],
466# endif
467 const float tri_center[2],
468 const KDRange2D bounds[2],
469 const KDTreeNode2D *node)
470{
471 const float *co = tree->coords[node->index];
472
473 if ((node->flag & KDNODE_FLAG_REMOVED) == 0) {
474# ifdef USE_PRECOMPUTED_ISECT
475 if (tri_isect_precomputed_test(tri_isect, co))
476# else
477 /* Check `tri_coords[1], tri_coords[2]` first as it's the "opposite edge"
478 * (`next` and `prev` in triangle terms) which fails most often for random points. */
479 if ((span_tri_v2_sign(tri_coords[1], tri_coords[2], co) != CONCAVE) &&
480 (span_tri_v2_sign(tri_coords[2], tri_coords[0], co) != CONCAVE) &&
481 (span_tri_v2_sign(tri_coords[0], tri_coords[1], co) != CONCAVE))
482# endif
483 {
484 if (!ELEM(node->index, tri_index[0], tri_index[1], tri_index[2])) {
485 return node->index;
486 }
487 }
488 }
489
490# ifdef USE_PRECOMPUTED_ISECT
491# define KDTREE2D_ISECT_ARGS tree, tri_index, tri_isect, tri_center, bounds
492# else
493# define KDTREE2D_ISECT_ARGS tree, tri_index, tri_coords, tri_center, bounds
494# endif
495
496# define KDTREE2D_ISECT_TRI_RECURSE_NEG \
497 (((node->neg != KDNODE_UNSET) && (co[node->axis] >= bounds[node->axis].min)) ? \
498 kdtree2d_isect_tri_recursive(KDTREE2D_ISECT_ARGS, &tree->nodes[node->neg]) : \
499 KDNODE_UNSET)
500# define KDTREE2D_ISECT_TRI_RECURSE_POS \
501 (((node->pos != KDNODE_UNSET) && (co[node->axis] <= bounds[node->axis].max)) ? \
502 kdtree2d_isect_tri_recursive(KDTREE2D_ISECT_ARGS, &tree->nodes[node->pos]) : \
503 KDNODE_UNSET)
504
506 if (tri_center[node->axis] > co[node->axis]) {
508 if (result == KDNODE_UNSET) {
510 }
511 }
512 else {
514 if (result == KDNODE_UNSET) {
516 }
517 }
518
519# undef KDTREE2D_ISECT_TRI_RECURSE_NEG
520# undef KDTREE2D_ISECT_TRI_RECURSE_POS
521# undef KDTREE2D_ISECT_ARGS
522
523 BLI_assert(node->index != KDNODE_UNSET);
524
525 return result;
526}
527
528# ifdef USE_KDTREE_INDEX_CACHE
533static bool kdtree2d_isect_tri_single(const KDTree2D *tree,
534 const uint32_t tri_index[3],
535 const uint32_t test_index)
536{
537 /* Check if the vertex is still in the tree and not one of the triangle vertices. */
538 if ((tree->nodes_map[test_index] != KDNODE_UNSET) &&
539 !ELEM(test_index, tri_index[0], tri_index[1], tri_index[2]))
540 {
541 const float *v1 = tree->coords[tri_index[0]];
542 const float *v2 = tree->coords[tri_index[1]];
543 const float *v3 = tree->coords[tri_index[2]];
544 const float *co = tree->coords[test_index];
545
546# ifdef USE_PRECOMPUTED_ISECT
547 const float *vs[3] = {v1, v2, v3};
548 TriIsectPrecomputed tri_isect;
549 tri_isect_precomputed_init(&tri_isect, vs);
550 if (tri_isect_precomputed_test(&tri_isect, co))
551# else
552 /* Check (v2, v3) first - the "opposite edge" (`next` and `prev`) fails most often. */
553 if ((span_tri_v2_sign(v2, v3, co) != CONCAVE) && (span_tri_v2_sign(v3, v1, co) != CONCAVE) &&
554 (span_tri_v2_sign(v1, v2, co) != CONCAVE))
555# endif
556 {
557 return true;
558 }
559 }
560
561 return false;
562}
563# endif /* USE_KDTREE_INDEX_CACHE */
564
568static uint32_t kdtree2d_isect_tri(KDTree2D *tree, const uint32_t ind[3])
569{
570 const float *vs[3] = {
571 tree->coords[ind[0]],
572 tree->coords[ind[1]],
573 tree->coords[ind[2]],
574 };
575
576 const KDRange2D bounds[2] = {
577 {std::min({vs[0][0], vs[1][0], vs[2][0]}), std::max({vs[0][0], vs[1][0], vs[2][0]})},
578 {std::min({vs[0][1], vs[1][1], vs[2][1]}), std::max({vs[0][1], vs[1][1], vs[2][1]})},
579 };
580
581 const float tri_center[2] = {
582 (vs[0][0] + vs[1][0] + vs[2][0]) * (1.0f / 3.0f),
583 (vs[0][1] + vs[1][1] + vs[2][1]) * (1.0f / 3.0f),
584 };
585
586# ifdef USE_PRECOMPUTED_ISECT
587 TriIsectPrecomputed tri_isect;
588 tri_isect_precomputed_init(&tri_isect, vs);
589# endif
590
592 ind,
594 &tri_isect,
595# else
596 vs,
597# endif
598 tri_center,
599 bounds,
600 &tree->nodes[tree->root]);
601}
602
603#endif /* USE_KDTREE */
604
605static uint32_t *pf_tri_add(PolyFill *pf)
606{
607 return pf->tris[pf->tris_num++];
608}
609
610static void pf_coord_remove(PolyFill *pf, PolyIndex *pi)
611{
612#ifdef USE_KDTREE
613 /* avoid double lookups, since convex coords are ignored when testing intersections */
614 if (pf->kdtree.node_num) {
615 kdtree2d_node_remove(&pf->kdtree, pi->index);
616 }
617#endif /* USE_KDTREE */
618
619 pi->next->prev = pi->prev;
620 pi->prev->next = pi->next;
621
622 if (pf->indices == pi) [[unlikely]] {
623 pf->indices = pi->next;
624 }
625#ifndef NDEBUG
626 pi->index = uint32_t(-1);
627 pi->next = pi->prev = nullptr;
628#endif /* !NDEBUG */
629
630 pf->coords_num -= 1;
631}
632
633static void pf_triangulate(PolyFill *pf)
634{
635 /* localize */
636 PolyIndex *pi_ear;
637
638#ifdef USE_CLIP_EVEN
639 PolyIndex *pi_ear_init = pf->indices;
640#endif
641#ifdef USE_CLIP_SWEEP
642 bool reverse = false;
643#endif
644
645 while (pf->coords_num > 3) {
646 PolyIndex *pi_prev, *pi_next;
647 eSign sign_orig_prev, sign_orig_next;
648
649 pi_ear = pf_ear_tip_find(pf
650#ifdef USE_CLIP_EVEN
651 ,
652 pi_ear_init
653#endif
654#ifdef USE_CLIP_SWEEP
655 ,
656 reverse
657#endif
658 );
659
660#ifdef USE_CONVEX_SKIP
661 if (pi_ear->sign != CONVEX) {
662 pf->coords_num_concave -= 1;
663 }
664#endif
665
666 pi_prev = pi_ear->prev;
667 pi_next = pi_ear->next;
668
669 pf_ear_tip_cut(pf, pi_ear);
670
671#ifdef USE_KDTREE_INDEX_CACHE
672 /* Tag neighbors to indicate their triangles changed, cached index needs verification. */
673 pi_prev->flag |= PolyIndexFlag::IndexCacheDirty;
674 pi_next->flag |= PolyIndexFlag::IndexCacheDirty;
675#endif
676
677 /* The type of the two vertices adjacent to the clipped vertex may have changed. */
678 sign_orig_prev = pi_prev->sign;
679 sign_orig_next = pi_next->sign;
680
681 /* check if any verts became convex the (else if)
682 * case is highly unlikely but may happen with degenerate polygons */
683 if (sign_orig_prev != CONVEX) {
684 pf_coord_sign_calc(pf, pi_prev);
685#ifdef USE_CONVEX_SKIP
686 if (pi_prev->sign == CONVEX) {
687 pf->coords_num_concave -= 1;
688# ifdef USE_KDTREE
689 kdtree2d_node_remove(&pf->kdtree, pi_prev->index);
690# endif
691 }
692#endif
693 }
694 if (sign_orig_next != CONVEX) {
695 pf_coord_sign_calc(pf, pi_next);
696#ifdef USE_CONVEX_SKIP
697 if (pi_next->sign == CONVEX) {
698 pf->coords_num_concave -= 1;
699# ifdef USE_KDTREE
700 kdtree2d_node_remove(&pf->kdtree, pi_next->index);
701# endif
702 }
703#endif
704 }
705
706#ifdef USE_CLIP_EVEN
707# ifdef USE_CLIP_SWEEP
708 pi_ear_init = reverse ? pi_prev->prev : pi_next->next;
709# else
710 pi_ear_init = pi_next->next;
711# endif
712#endif
713
714#ifdef USE_CLIP_EVEN
715# ifdef USE_CLIP_SWEEP
716 if (pi_ear_init->sign != CONVEX) {
717 /* take the extra step since this ear isn't a good candidate */
718 pi_ear_init = reverse ? pi_ear_init->prev : pi_ear_init->next;
719 reverse = !reverse;
720 }
721# endif
722#else
723# ifdef USE_CLIP_SWEEP
724 if ((reverse ? pi_prev->prev : pi_next->next)->sign != CONVEX) {
725 reverse = !reverse;
726 }
727# endif
728#endif
729 }
730
731 if (pf->coords_num == 3) {
732 uint32_t *tri = pf_tri_add(pf);
733 pi_ear = pf->indices;
734 tri[0] = pi_ear->index;
735 pi_ear = pi_ear->next;
736 tri[1] = pi_ear->index;
737 pi_ear = pi_ear->next;
738 tri[2] = pi_ear->index;
739 }
740}
741
745static void pf_coord_sign_calc(const PolyFill *pf, PolyIndex *pi)
746{
747 /* localize */
748 const float (*coords)[2] = pf->coords;
749
750 pi->sign = span_tri_v2_sign(coords[pi->prev->index], coords[pi->index], coords[pi->next->index]);
751}
752
753static PolyIndex *pf_ear_tip_find(PolyFill *pf
754#ifdef USE_CLIP_EVEN
755 ,
756 PolyIndex *pi_ear_init
757#endif
758#ifdef USE_CLIP_SWEEP
759 ,
760 bool reverse
761#endif
762)
763{
764 /* localize */
765 const uint32_t coords_num = pf->coords_num;
766 PolyIndex *pi_ear;
767
768 uint32_t i;
769
770 /* Use two passes when looking for an ear.
771 *
772 * - The first pass only picks *good* (concave) choices.
773 * For polygons which aren't degenerate this works well
774 * since it avoids creating any zero area faces.
775 *
776 * - The second pass is only met if no concave choices are possible,
777 * so the cost of a second pass is only incurred for degenerate polygons.
778 * In this case accept zero area faces as better alternatives aren't available.
779 *
780 * See: #103913 for reference.
781 *
782 * NOTE: these passes draw a distinction between zero area faces and concave
783 * which is susceptible minor differences in float precision
784 * (since #TANGENTIAL compares with 0.0f).
785 *
786 * While it's possible to compute an error threshold and run a pass that picks
787 * ears which are more likely not to appear as zero area from a users perspective,
788 * this API prioritizes performance (for real-time updates).
789 * Higher quality tessellation can always be achieved using #BLI_polyfill_beautify.
790 */
791 for (eSign sign_accept = CONVEX; sign_accept >= TANGENTIAL; sign_accept--) {
792#ifdef USE_CLIP_EVEN
793 pi_ear = pi_ear_init;
794#else
795 pi_ear = pf->indices;
796#endif
797 i = coords_num;
798 while (i--) {
799 if (pf_ear_tip_check(pf, pi_ear, sign_accept)) {
800 return pi_ear;
801 }
802#ifdef USE_CLIP_SWEEP
803 pi_ear = reverse ? pi_ear->prev : pi_ear->next;
804#else
805 pi_ear = pi_ear->next;
806#endif
807 }
808 }
809
810 /* Desperate mode: if no vertex is an ear tip,
811 * we are dealing with a degenerate polygon (e.g. nearly collinear).
812 * Note that the input was not necessarily degenerate,
813 * but we could have made it so by clipping some valid ears.
814 *
815 * Idea taken from Martin Held, "FIST: Fast industrial-strength triangulation of polygons",
816 * Algorithmica (1998),
817 * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291
818 *
819 * Return a convex or tangential vertex if one exists.
820 */
821
822#ifdef USE_CLIP_EVEN
823 pi_ear = pi_ear_init;
824#else
825 pi_ear = pf->indices;
826#endif
827
828 i = coords_num;
829 while (i--) {
830 if (pi_ear->sign != CONCAVE) {
831 return pi_ear;
832 }
833 pi_ear = pi_ear->next;
834 }
835
836 /* If all vertices are concave, just return the last one. */
837 return pi_ear;
838}
839
840static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip, const eSign sign_accept)
841{
842#ifndef USE_KDTREE
843 /* localize */
844 const float (*coords)[2] = pf->coords;
845 PolyIndex *pi_curr;
846
847 const float *v1, *v2, *v3;
848#endif
849
850#if defined(USE_CONVEX_SKIP) && !defined(USE_KDTREE)
851 uint32_t coords_num_concave_checked = 0;
852#endif
853
854#ifdef USE_CONVEX_SKIP
855
856# ifdef USE_CONVEX_SKIP_TEST
857 /* check if counting is wrong */
858 {
859 uint32_t coords_num_concave_test = 0;
860 PolyIndex *pi_iter = pi_ear_tip;
861 do {
862 if (pi_iter->sign != CONVEX) {
863 coords_num_concave_test += 1;
864 }
865 } while ((pi_iter = pi_iter->next) != pi_ear_tip);
866 BLI_assert(coords_num_concave_test == pf->coords_num_concave);
867 }
868# endif
869
870 /* fast-path for circles */
871 if (pf->coords_num_concave == 0) {
872 return true;
873 }
874#endif
875
876 if (pi_ear_tip->sign != sign_accept) [[unlikely]] {
877 return false;
878 }
879
880#ifdef USE_KDTREE
881 {
882 const uint32_t ind[3] = {pi_ear_tip->index, pi_ear_tip->next->index, pi_ear_tip->prev->index};
883
884# ifdef USE_KDTREE_INDEX_CACHE
885 const uint32_t cached_hit = pi_ear_tip->index_last_hit;
886 if (cached_hit != KDTREE_INDEX_CACHE_UNSET) {
887 if ((pi_ear_tip->flag & PolyIndexFlag::IndexCacheDirty) == PolyIndexFlag(0)) {
888 /* Triangle unchanged since caching - the last hit is guaranteed to remain intersecting,
889 * provided it's still in the tree and therefor concave.
890 * Note that technically the removed point still intersects,
891 * it's just that in the case it's removed this code should match the behavior
892 * of the un-cached #KDTree lookup.
893 * In practice this should only occur with polygons that overlap themselves. */
894 if (pf->kdtree.nodes_map[cached_hit] != KDNODE_UNSET) {
895 return false;
896 }
897 }
898 else {
899 /* Triangle changed (flagged dirty). Verify cached vertex still blocks. */
900 if (kdtree2d_isect_tri_single(&pf->kdtree, ind, cached_hit)) {
901 /* Still blocks, clear dirty flag. */
902 pi_ear_tip->flag &= ~PolyIndexFlag::IndexCacheDirty;
903 return false;
904 }
905 /* Cache miss: fall through to full search. */
906 }
907 }
908# endif /* USE_KDTREE_INDEX_CACHE */
909
910 const uint32_t hit = kdtree2d_isect_tri(&pf->kdtree, ind);
911 if (hit != KDNODE_UNSET) {
912# ifdef USE_KDTREE_INDEX_CACHE
913 pi_ear_tip->index_last_hit = hit;
914 pi_ear_tip->flag &= ~PolyIndexFlag::IndexCacheDirty;
915# endif
916 return false;
917 }
918 }
919#else
920
921 v1 = coords[pi_ear_tip->prev->index];
922 v2 = coords[pi_ear_tip->index];
923 v3 = coords[pi_ear_tip->next->index];
924
925 /* Check if any point is inside the triangle formed by previous, current and next vertices.
926 * Only consider vertices that are not part of this triangle,
927 * or else we'll always find one inside. */
928
929 for (pi_curr = pi_ear_tip->next->next; pi_curr != pi_ear_tip->prev; pi_curr = pi_curr->next) {
930 /* Concave vertices can obviously be inside the candidate ear,
931 * but so can tangential vertices if they coincide with one of the triangle's vertices. */
932 if (pi_curr->sign != CONVEX) {
933 const float *v = coords[pi_curr->index];
934 /* Because the polygon has clockwise winding order,
935 * the area sign will be positive if the point is strictly inside.
936 * It will be 0 on the edge, which we want to include as well. */
937
938 /* NOTE: check (v3, v1) first since it fails _far_ more often than the other 2 checks
939 * (those fail equally).
940 * It's logical - the chance is low that points exist on the
941 * same side as the ear we're clipping off. */
942 if ((span_tri_v2_sign(v3, v1, v) != CONCAVE) && (span_tri_v2_sign(v1, v2, v) != CONCAVE) &&
943 (span_tri_v2_sign(v2, v3, v) != CONCAVE))
944 {
945 return false;
946 }
947
948# ifdef USE_CONVEX_SKIP
949 coords_num_concave_checked += 1;
950 if (coords_num_concave_checked == pf->coords_num_concave) {
951 break;
952 }
953# endif
954 }
955 }
956#endif /* USE_KDTREE */
957
958 return true;
959}
960
961static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip)
962{
963 uint32_t *tri = pf_tri_add(pf);
964
965 tri[0] = pi_ear_tip->prev->index;
966 tri[1] = pi_ear_tip->index;
967 tri[2] = pi_ear_tip->next->index;
968
969 pf_coord_remove(pf, pi_ear_tip);
970}
971
975static void polyfill_prepare(PolyFill *pf,
976 const float (*coords)[2],
977 const uint32_t coords_num,
978 int coords_sign,
979 uint32_t (*r_tris)[3],
980 PolyIndex *r_indices)
981{
982 /* localize */
983 PolyIndex *indices = r_indices;
984
985 uint32_t i;
986
987 /* assign all polyfill members here */
988 pf->indices = r_indices;
989 pf->coords = coords;
990 pf->coords_num = coords_num;
991#ifdef USE_CONVEX_SKIP
992 pf->coords_num_concave = 0;
993#endif
994 pf->tris = r_tris;
995 pf->tris_num = 0;
996
997 if (coords_sign == 0) {
998 coords_sign = (cross_poly_v2(coords, coords_num) <= 0.0f) ? 1 : -1;
999 }
1000 else {
1001 /* check we're passing in correct args */
1002#ifdef USE_STRICT_ASSERT
1003# ifndef NDEBUG
1004 if (coords_sign == 1) {
1005 BLI_assert(cross_poly_v2(coords, coords_num) <= 0.0f);
1006 }
1007 else {
1008 BLI_assert(cross_poly_v2(coords, coords_num) >= 0.0f);
1009 }
1010# endif
1011#endif
1012 }
1013
1014 if (coords_sign == 1) {
1015 for (i = 0; i < coords_num; i++) {
1016 indices[i].next = &indices[i + 1];
1017 indices[i].prev = &indices[i - 1];
1018 indices[i].index = i;
1019 }
1020 }
1021 else {
1022 /* reversed */
1023 uint32_t n = coords_num - 1;
1024 for (i = 0; i < coords_num; i++) {
1025 indices[i].next = &indices[i + 1];
1026 indices[i].prev = &indices[i - 1];
1027 indices[i].index = (n - i);
1028 }
1029 }
1030 indices[0].prev = &indices[coords_num - 1];
1031 indices[coords_num - 1].next = &indices[0];
1032
1033 for (i = 0; i < coords_num; i++) {
1034 PolyIndex *pi = &indices[i];
1036#ifdef USE_CONVEX_SKIP
1037 if (pi->sign != CONVEX) {
1038 pf->coords_num_concave += 1;
1039 }
1040#endif
1041#ifdef USE_KDTREE_INDEX_CACHE
1042 pi->flag = PolyIndexFlag(0);
1043 pi->index_last_hit = KDTREE_INDEX_CACHE_UNSET;
1044#endif
1045 }
1046}
1047
1048static void polyfill_calc(PolyFill *pf)
1049{
1050#ifdef USE_KDTREE
1051# ifdef USE_CONVEX_SKIP
1052 if (pf->coords_num_concave)
1053# endif
1054 {
1055 kdtree2d_new(&pf->kdtree, pf->coords_num_concave, pf->coords);
1056 kdtree2d_init(&pf->kdtree, pf->coords_num, pf->indices);
1057 kdtree2d_balance(&pf->kdtree);
1058 kdtree2d_init_mapping(&pf->kdtree);
1059 }
1060#endif
1061
1063}
1064
1065void BLI_polyfill_calc_arena(const float (*coords)[2],
1066 const uint32_t coords_num,
1067 const int coords_sign,
1068 uint32_t (*r_tris)[3],
1069
1070 MemArena *arena)
1071{
1072 PolyFill pf;
1073 PolyIndex *indices = static_cast<PolyIndex *>(
1074 BLI_memarena_alloc(arena, sizeof(*indices) * coords_num));
1075
1076#ifdef DEBUG_TIME
1077 TIMEIT_START(polyfill2d);
1078#endif
1079
1081 coords,
1082 coords_num,
1083 coords_sign,
1084 r_tris,
1085 /* cache */
1086 indices);
1087
1088#ifdef USE_KDTREE
1089 if (pf.coords_num_concave) {
1090 pf.kdtree.nodes = static_cast<KDTreeNode2D *>(
1091 BLI_memarena_alloc(arena, sizeof(*pf.kdtree.nodes) * pf.coords_num_concave));
1092 pf.kdtree.nodes_map = static_cast<uint32_t *>(
1093 memset(BLI_memarena_alloc(arena, sizeof(*pf.kdtree.nodes_map) * coords_num),
1094 0xff,
1095 sizeof(*pf.kdtree.nodes_map) * coords_num));
1096 }
1097 else {
1098 pf.kdtree.node_num = 0;
1099 }
1100#endif
1101
1102 polyfill_calc(&pf);
1103
1104 /* indices are no longer needed,
1105 * caller can clear arena */
1106
1107#ifdef DEBUG_TIME
1108 TIMEIT_END(polyfill2d);
1109#endif
1110}
1111
1112void BLI_polyfill_calc(const float (*coords)[2],
1113 const uint32_t coords_num,
1114 const int coords_sign,
1115 uint32_t (*r_tris)[3])
1116{
1117 /* Fall back to heap memory for large allocations.
1118 * Avoid running out of stack memory on systems with 512kb stack (macOS).
1119 * This happens at around 13,000 points, use a much lower value to be safe. */
1120 if (coords_num > 8192) [[unlikely]] {
1121 /* The buffer size only accounts for the index allocation,
1122 * worst case we do two allocations when concave, while we should try to be efficient,
1123 * any caller that relies on this frequently should use #BLI_polyfill_calc_arena directly. */
1124 MemArena *arena = BLI_memarena_new(sizeof(PolyIndex) * coords_num, __func__);
1125 BLI_polyfill_calc_arena(coords, coords_num, coords_sign, r_tris, arena);
1126 BLI_memarena_free(arena);
1127 return;
1128 }
1129
1130 PolyFill pf;
1131 PolyIndex *indices = static_cast<PolyIndex *>(BLI_array_alloca(indices, coords_num));
1132
1133#ifdef DEBUG_TIME
1134 TIMEIT_START(polyfill2d);
1135#endif
1136
1138 coords,
1139 coords_num,
1140 coords_sign,
1141 r_tris,
1142 /* cache */
1143 indices);
1144
1145#ifdef USE_KDTREE
1146 if (pf.coords_num_concave) {
1147 pf.kdtree.nodes = static_cast<KDTreeNode2D *>(
1148 BLI_array_alloca(pf.kdtree.nodes, pf.coords_num_concave));
1149 pf.kdtree.nodes_map = static_cast<uint32_t *>(
1150 memset(BLI_array_alloca(pf.kdtree.nodes_map, coords_num),
1151 0xff,
1152 sizeof(*pf.kdtree.nodes_map) * coords_num));
1153 }
1154 else {
1155 pf.kdtree.node_num = 0;
1156 }
1157#endif
1158
1159 polyfill_calc(&pf);
1160
1161#ifdef DEBUG_TIME
1162 TIMEIT_END(polyfill2d);
1163#endif
1164}
1165
1166} // namespace blender
#define BLI_array_alloca(arr, realsize)
Definition BLI_alloca.hh:18
#define ENUM_OPERATORS(_enum_type)
Utility defines for timing/benchmarks.
#define TIMEIT_START(var)
#define TIMEIT_END(var)
Read Blender memory allocation and freeing.
#define SWAP(type, a, b)
#define BLI_INLINE
#define ELEM(...)
btScalar max
#define pf(_x, _i)
Prefetch 64.
Definition gim_memory.h:48
#define index(i)
constexpr T sign(T) RET
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static void kdtree2d_node_remove(KDTree2D *tree, uint32_t index)
static void pf_coord_remove(PolyFill *pf, PolyIndex *pi)
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
uchar axis_t
static PolyIndex * pf_ear_tip_find(PolyFill *pf, PolyIndex *pi_ear_init, bool reverse)
static bool kdtree2d_isect_tri_single(const KDTree2D *tree, const uint32_t tri_index[3], const uint32_t test_index)
float cross_poly_v2(const float verts[][2], unsigned int nr)
Definition math_geom.cc:153
void BLI_polyfill_calc(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3])
BLI_INLINE eSign signum_enum(float a)
static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip)
static void pf_triangulate(PolyFill *pf)
static void kdtree2d_balance(KDTree2D *tree)
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
void BLI_polyfill_calc_arena(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3], struct MemArena *arena)
static uint32_t kdtree2d_balance_recursive(KDTreeNode2D *nodes, uint32_t node_num, axis_t axis, const float(*coords)[2], const uint32_t ofs)
ATTR_WARN_UNUSED_RESULT const BMVert * v
static void kdtree2d_init(KDTree2D *tree, const uint32_t coords_num, const PolyIndex *indices)
@ KDNODE_FLAG_REMOVED
unsigned short uint16_t
Definition BKE_text.h:80
unsigned int uint32_t
Definition BKE_text.h:81
static void polyfill_calc(PolyFill *pf)
static void kdtree2d_init_mapping(KDTree2D *tree)
unsigned char uint8_t
Definition BKE_text.h:79
static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float v3[2])
BLI_INLINE float area_tri_signed_v2_alt_2x(const float v1[2], const float v2[2], const float v3[2])
static void pf_coord_sign_calc(const PolyFill *pf, PolyIndex *pi)
static bool tri_isect_precomputed_test(const TriIsectPrecomputed *t, const float co[2])
static void tri_isect_precomputed_init(TriIsectPrecomputed *t, const float *const vs[3])
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
static void polyfill_prepare(PolyFill *pf, const float(*coords)[2], const uint32_t coords_num, int coords_sign, uint32_t(*r_tris)[3], PolyIndex *r_indices)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip, const eSign sign_accept)
static uint32_t kdtree2d_isect_tri(KDTree2D *tree, const uint32_t ind[3])
static uint32_t kdtree2d_isect_tri_recursive(const KDTree2D *tree, const uint32_t tri_index[3], const TriIsectPrecomputed *tri_isect, const float tri_center[2], const KDRange2D bounds[2], const KDTreeNode2D *node)
static void kdtree2d_new(KDTree2D *tree, uint32_t tot, const float(*coords)[2])
static uint32_t * pf_tri_add(PolyFill *pf)
signed char int8_t
Definition BKE_text.h:76
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
#define USE_PRECOMPUTED_ISECT
#define KDTREE2D_ISECT_TRI_RECURSE_NEG
#define KDTREE_INDEX_CACHE_UNSET
#define USE_CLIP_EVEN
#define KDNODE_UNSET
#define USE_CLIP_SWEEP
#define KDTREE2D_ISECT_TRI_RECURSE_POS
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
#define min(a, b)
Definition sort.cc:38