Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / blenlib / intern / polyfill_2d.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file \ingroup bli
18  *
19  * An ear clipping algorithm to triangulate single boundary polygons.
20  *
21  * Details:
22  *
23  * - The algorithm guarantees all triangles are assigned (number of coords - 2)
24  *   and that triangles will have non-overlapping indices (even for degenerate geometry).
25  * - Self-intersections are considered degenerate (resulting triangles will overlap).
26  * - While multiple polygons aren't supported, holes can still be defined using *key-holes*
27  *   (where the polygon doubles back on its self with *exactly* matching coordinates).
28  *
29  * \note
30  *
31  * Changes made for Blender.
32  *
33  * - loop the array to clip last verts first (less array resizing)
34  *
35  * - advance the ear to clip each iteration
36  *   to avoid fan-filling convex shapes (USE_CLIP_EVEN).
37  *
38  * - avoid intersection tests when there are no convex points (USE_CONVEX_SKIP).
39  *
40  * \note
41  *
42  * No globals - keep threadsafe.
43  */
44
45 #include "BLI_utildefines.h"
46 #include "BLI_math.h"
47
48 #include "BLI_memarena.h"
49 #include "BLI_alloca.h"
50
51 #include "BLI_polyfill_2d.h"  /* own include */
52
53 #include "BLI_strict_flags.h"
54
55 /* avoid fan-fill topology */
56 #define USE_CLIP_EVEN
57 #define USE_CONVEX_SKIP
58 /* sweep back-and-forth about convex ears (avoids lop-sided fans) */
59 #define USE_CLIP_SWEEP
60 // #define USE_CONVEX_SKIP_TEST
61
62 #ifdef USE_CONVEX_SKIP
63 #  define USE_KDTREE
64 #endif
65
66 /* disable in production, it can fail on near zero area ngons */
67 // #define USE_STRICT_ASSERT
68
69 // #define DEBUG_TIME
70 #ifdef DEBUG_TIME
71 #  include "PIL_time_utildefines.h"
72 #endif
73
74
75 typedef signed char eSign;
76
77 #ifdef USE_KDTREE
78 /**
79  * Spatial optimization for point-in-triangle intersection checks.
80  * The simple version of this algorithm is ``O(n^2)`` complexity
81  * (every point needing to check the triangle defined by every other point),
82  * Using a binary-tree reduces the complexity to ``O(n log n)``
83  * plus some overhead of creating the tree.
84  *
85  * This is a single purpose KDTree based on BLI_kdtree with some modifications
86  * to better suit polyfill2d.
87  * - #KDTreeNode2D is kept small (only 16 bytes),
88  *   by not storing coords in the nodes and using index values rather then pointers
89  *   to reference neg/pos values.
90  *
91  * - #kdtree2d_isect_tri is the only function currently used.
92  *   This simply intersects a triangle with the kdtree points.
93  *
94  * - the KDTree is only built & used when the polygon is concave.
95  */
96
97 typedef bool axis_t;
98
99 /* use for sorting */
100 typedef struct KDTreeNode2D_head {
101         uint neg, pos;
102         uint index;
103 } KDTreeNode2D_head;
104
105 typedef struct KDTreeNode2D {
106         uint neg, pos;
107         uint index;
108         axis_t axis;  /* range is only (0-1) */
109         ushort flag;
110         uint parent;
111 } KDTreeNode2D;
112
113 struct KDTree2D {
114         KDTreeNode2D *nodes;
115         const float (*coords)[2];
116         uint root;
117         uint totnode;
118         uint *nodes_map;  /* index -> node lookup */
119 };
120
121 struct KDRange2D {
122         float min, max;
123 };
124 #endif  /* USE_KDTREE */
125
126 enum {
127         CONCAVE = -1,
128         TANGENTIAL = 0,
129         CONVEX = 1,
130 };
131
132 typedef struct PolyFill {
133         struct PolyIndex *indices;  /* vertex aligned */
134
135         const float (*coords)[2];
136         uint  coords_tot;
137 #ifdef USE_CONVEX_SKIP
138         uint  coords_tot_concave;
139 #endif
140
141         /* A polygon with n vertices has a triangulation of n-2 triangles. */
142         uint (*tris)[3];
143         uint   tris_tot;
144
145 #ifdef USE_KDTREE
146         struct KDTree2D kdtree;
147 #endif
148 } PolyFill;
149
150
151 /* circular linklist */
152 typedef struct PolyIndex {
153         struct PolyIndex *next, *prev;
154         uint index;
155         eSign sign;
156 } PolyIndex;
157
158
159 /* based on libgdx 2013-11-28, apache 2.0 licensed */
160
161 static void pf_coord_sign_calc(PolyFill *pf, PolyIndex *pi);
162
163 static PolyIndex *pf_ear_tip_find(
164         PolyFill *pf
165 #ifdef USE_CLIP_EVEN
166         , PolyIndex *pi_ear_init
167 #endif
168 #ifdef USE_CLIP_SWEEP
169         , bool reverse
170 #endif
171         );
172
173 static bool       pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip);
174 static void       pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip);
175
176
177 BLI_INLINE eSign signum_enum(float a)
178 {
179         if (UNLIKELY(a == 0.0f))
180                 return  0;
181         else if (a > 0.0f)
182                 return  1;
183         else
184                 return -1;
185 }
186
187 /**
188  * alternative version of #area_tri_signed_v2
189  * needed because of float precision issues
190  *
191  * \note removes / 2 since its not needed since we only need the sign.
192  */
193 BLI_INLINE float area_tri_signed_v2_alt_2x(const float v1[2], const float v2[2], const float v3[2])
194 {
195         return ((v1[0] * (v2[1] - v3[1])) +
196                 (v2[0] * (v3[1] - v1[1])) +
197                 (v3[0] * (v1[1] - v2[1])));
198 }
199
200
201 static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float v3[2])
202 {
203         return signum_enum(area_tri_signed_v2_alt_2x(v3, v2, v1));
204 }
205
206
207 #ifdef USE_KDTREE
208 #define KDNODE_UNSET ((uint)-1)
209
210 enum {
211         KDNODE_FLAG_REMOVED = (1 << 0),
212 };
213
214 static void kdtree2d_new(
215         struct KDTree2D *tree,
216         uint tot,
217         const float (*coords)[2])
218 {
219         /* set by caller */
220         // tree->nodes = nodes;
221         tree->coords = coords;
222         tree->root = KDNODE_UNSET;
223         tree->totnode = tot;
224 }
225
226 /**
227  * no need for kdtree2d_insert, since we know the coords array.
228  */
229 static void kdtree2d_init(
230         struct KDTree2D *tree,
231         const uint coords_tot,
232         const PolyIndex *indices)
233 {
234         KDTreeNode2D *node;
235         uint i;
236
237         for (i = 0, node = tree->nodes; i < coords_tot; i++) {
238                 if (indices[i].sign != CONVEX) {
239                         node->neg = node->pos = KDNODE_UNSET;
240                         node->index = indices[i].index;
241                         node->axis = 0;
242                         node->flag = 0;
243                         node++;
244                 }
245         }
246
247         BLI_assert(tree->totnode == (uint)(node - tree->nodes));
248 }
249
250 static uint kdtree2d_balance_recursive(
251         KDTreeNode2D *nodes, uint totnode, axis_t axis,
252         const float (*coords)[2], const uint ofs)
253 {
254         KDTreeNode2D *node;
255         uint neg, pos, median, i, j;
256
257         if (totnode <= 0) {
258                 return KDNODE_UNSET;
259         }
260         else if (totnode == 1) {
261                 return 0 + ofs;
262         }
263
264         /* quicksort style sorting around median */
265         neg = 0;
266         pos = totnode - 1;
267         median = totnode / 2;
268
269         while (pos > neg) {
270                 const float co = coords[nodes[pos].index][axis];
271                 i = neg - 1;
272                 j = pos;
273
274                 while (1) {
275                         while (coords[nodes[++i].index][axis] < co) ;
276                         while (coords[nodes[--j].index][axis] > co && j > neg) ;
277
278                         if (i >= j) {
279                                 break;
280                         }
281                         SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&nodes[i], *(KDTreeNode2D_head *)&nodes[j]);
282                 }
283
284                 SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&nodes[i], *(KDTreeNode2D_head *)&nodes[pos]);
285                 if (i >= median) {
286                         pos = i - 1;
287                 }
288                 if (i <= median) {
289                         neg = i + 1;
290                 }
291         }
292
293         /* set node and sort subnodes */
294         node = &nodes[median];
295         node->axis = axis;
296         axis = !axis;
297         node->neg = kdtree2d_balance_recursive(nodes, median, axis, coords, ofs);
298         node->pos = kdtree2d_balance_recursive(&nodes[median + 1], (totnode - (median + 1)), axis, coords, (median + 1) + ofs);
299
300         return median + ofs;
301 }
302
303 static void kdtree2d_balance(
304         struct KDTree2D *tree)
305 {
306         tree->root = kdtree2d_balance_recursive(tree->nodes, tree->totnode, 0, tree->coords, 0);
307 }
308
309
310 static void kdtree2d_init_mapping(
311         struct KDTree2D *tree)
312 {
313         uint i;
314         KDTreeNode2D *node;
315
316         for (i = 0, node = tree->nodes; i < tree->totnode; i++, node++) {
317                 if (node->neg != KDNODE_UNSET) {
318                         tree->nodes[node->neg].parent = i;
319                 }
320                 if (node->pos != KDNODE_UNSET) {
321                         tree->nodes[node->pos].parent = i;
322                 }
323
324                 /* build map */
325                 BLI_assert(tree->nodes_map[node->index] == KDNODE_UNSET);
326                 tree->nodes_map[node->index] = i;
327         }
328
329         tree->nodes[tree->root].parent = KDNODE_UNSET;
330 }
331
332 static void kdtree2d_node_remove(
333         struct KDTree2D *tree,
334         uint index)
335 {
336         uint node_index = tree->nodes_map[index];
337         KDTreeNode2D *node;
338
339         if (node_index == KDNODE_UNSET) {
340                 return;
341         }
342         else {
343                 tree->nodes_map[index] = KDNODE_UNSET;
344         }
345
346         node = &tree->nodes[node_index];
347         tree->totnode -= 1;
348
349         BLI_assert((node->flag & KDNODE_FLAG_REMOVED) == 0);
350         node->flag |= KDNODE_FLAG_REMOVED;
351
352         while ((node->neg == KDNODE_UNSET) &&
353                (node->pos == KDNODE_UNSET) &&
354                (node->parent != KDNODE_UNSET))
355         {
356                 KDTreeNode2D *node_parent = &tree->nodes[node->parent];
357
358                 BLI_assert((uint)(node - tree->nodes) == node_index);
359                 if (node_parent->neg == node_index) {
360                         node_parent->neg = KDNODE_UNSET;
361                 }
362                 else {
363                         BLI_assert(node_parent->pos == node_index);
364                         node_parent->pos = KDNODE_UNSET;
365                 }
366
367                 if (node_parent->flag & KDNODE_FLAG_REMOVED) {
368                         node_index = node->parent;
369                         node = node_parent;
370                 }
371                 else {
372                         break;
373                 }
374         }
375 }
376
377 static bool kdtree2d_isect_tri_recursive(
378         const struct KDTree2D *tree,
379         const uint         tri_index[3],
380         const float       *tri_coords[3],
381         const float        tri_center[2],
382         const struct KDRange2D bounds[2],
383         const KDTreeNode2D *node)
384 {
385         const float *co = tree->coords[node->index];
386
387         /* bounds then triangle intersect */
388         if ((node->flag & KDNODE_FLAG_REMOVED) == 0) {
389                 /* bounding box test first */
390                 if ((co[0] >= bounds[0].min) &&
391                     (co[0] <= bounds[0].max) &&
392                     (co[1] >= bounds[1].min) &&
393                     (co[1] <= bounds[1].max))
394                 {
395                         if ((span_tri_v2_sign(tri_coords[0], tri_coords[1], co) != CONCAVE) &&
396                             (span_tri_v2_sign(tri_coords[1], tri_coords[2], co) != CONCAVE) &&
397                             (span_tri_v2_sign(tri_coords[2], tri_coords[0], co) != CONCAVE))
398                         {
399                                 if (!ELEM(node->index, tri_index[0], tri_index[1], tri_index[2])) {
400                                         return true;
401                                 }
402                         }
403                 }
404         }
405
406 #define KDTREE2D_ISECT_TRI_RECURSE_NEG \
407         (((node->neg != KDNODE_UNSET) && (co[node->axis] >= bounds[node->axis].min)) &&  \
408           (kdtree2d_isect_tri_recursive(tree, tri_index, tri_coords, tri_center, bounds, \
409                                         &tree->nodes[node->neg])))
410 #define KDTREE2D_ISECT_TRI_RECURSE_POS \
411         (((node->pos != KDNODE_UNSET) && (co[node->axis] <= bounds[node->axis].max)) &&  \
412           (kdtree2d_isect_tri_recursive(tree, tri_index, tri_coords, tri_center, bounds, \
413                                         &tree->nodes[node->pos])))
414
415         if (tri_center[node->axis] > co[node->axis]) {
416                 if (KDTREE2D_ISECT_TRI_RECURSE_POS) {
417                         return true;
418                 }
419                 if (KDTREE2D_ISECT_TRI_RECURSE_NEG) {
420                         return true;
421                 }
422         }
423         else {
424                 if (KDTREE2D_ISECT_TRI_RECURSE_NEG) {
425                         return true;
426                 }
427                 if (KDTREE2D_ISECT_TRI_RECURSE_POS) {
428                         return true;
429                 }
430         }
431
432 #undef KDTREE2D_ISECT_TRI_RECURSE_NEG
433 #undef KDTREE2D_ISECT_TRI_RECURSE_POS
434
435         BLI_assert(node->index != KDNODE_UNSET);
436
437         return false;
438 }
439
440 static bool kdtree2d_isect_tri(
441         struct KDTree2D *tree,
442         const uint ind[3])
443 {
444         const float *vs[3];
445         uint i;
446         struct KDRange2D bounds[2] = {
447             {FLT_MAX, -FLT_MAX},
448             {FLT_MAX, -FLT_MAX},
449         };
450         float tri_center[2] = {0.0f, 0.0f};
451
452         for (i = 0; i < 3; i++) {
453                 vs[i] = tree->coords[ind[i]];
454
455                 add_v2_v2(tri_center, vs[i]);
456
457                 CLAMP_MAX(bounds[0].min, vs[i][0]);
458                 CLAMP_MIN(bounds[0].max, vs[i][0]);
459                 CLAMP_MAX(bounds[1].min, vs[i][1]);
460                 CLAMP_MIN(bounds[1].max, vs[i][1]);
461         }
462
463         mul_v2_fl(tri_center, 1.0f / 3.0f);
464
465         return kdtree2d_isect_tri_recursive(tree, ind, vs, tri_center, bounds, &tree->nodes[tree->root]);
466 }
467
468 #endif  /* USE_KDTREE */
469
470
471 static uint *pf_tri_add(PolyFill *pf)
472 {
473         return pf->tris[pf->tris_tot++];
474 }
475
476 static void pf_coord_remove(PolyFill *pf, PolyIndex *pi)
477 {
478 #ifdef USE_KDTREE
479         /* avoid double lookups, since convex coords are ignored when testing intersections */
480         if (pf->kdtree.totnode) {
481                 kdtree2d_node_remove(&pf->kdtree, pi->index);
482         }
483 #endif
484
485         pi->next->prev = pi->prev;
486         pi->prev->next = pi->next;
487
488         if (UNLIKELY(pf->indices == pi)) {
489                 pf->indices = pi->next;
490         }
491 #ifdef DEBUG
492         pi->index = (uint)-1;
493         pi->next = pi->prev = NULL;
494 #endif
495
496         pf->coords_tot -= 1;
497 }
498
499 static void pf_triangulate(PolyFill *pf)
500 {
501         /* localize */
502         PolyIndex *pi_ear;
503
504 #ifdef USE_CLIP_EVEN
505         PolyIndex *pi_ear_init = pf->indices;
506 #endif
507 #ifdef USE_CLIP_SWEEP
508         bool reverse = false;
509 #endif
510
511         while (pf->coords_tot > 3) {
512                 PolyIndex *pi_prev, *pi_next;
513                 eSign sign_orig_prev, sign_orig_next;
514
515                 pi_ear = pf_ear_tip_find(
516                         pf
517 #ifdef USE_CLIP_EVEN
518                         , pi_ear_init
519 #endif
520 #ifdef USE_CLIP_SWEEP
521                         , reverse
522 #endif
523                         );
524
525 #ifdef USE_CONVEX_SKIP
526                 if (pi_ear->sign != CONVEX) {
527                         pf->coords_tot_concave -= 1;
528                 }
529 #endif
530
531                 pi_prev = pi_ear->prev;
532                 pi_next = pi_ear->next;
533
534                 pf_ear_tip_cut(pf, pi_ear);
535
536                 /* The type of the two vertices adjacent to the clipped vertex may have changed. */
537                 sign_orig_prev = pi_prev->sign;
538                 sign_orig_next = pi_next->sign;
539
540                 /* check if any verts became convex the (else if)
541                  * case is highly unlikely but may happen with degenerate polygons */
542                 if (sign_orig_prev != CONVEX) {
543                         pf_coord_sign_calc(pf, pi_prev);
544 #ifdef USE_CONVEX_SKIP
545                         if (pi_prev->sign == CONVEX) {
546                                 pf->coords_tot_concave -= 1;
547 #ifdef USE_KDTREE
548                                 kdtree2d_node_remove(&pf->kdtree, pi_prev->index);
549 #endif
550                         }
551 #endif
552                 }
553                 if (sign_orig_next != CONVEX) {
554                         pf_coord_sign_calc(pf, pi_next);
555 #ifdef USE_CONVEX_SKIP
556                         if (pi_next->sign == CONVEX) {
557                                 pf->coords_tot_concave -= 1;
558 #ifdef USE_KDTREE
559                                 kdtree2d_node_remove(&pf->kdtree, pi_next->index);
560 #endif
561                         }
562 #endif
563                 }
564
565 #ifdef USE_CLIP_EVEN
566 #ifdef USE_CLIP_SWEEP
567                 pi_ear_init = reverse ? pi_prev->prev : pi_next->next;
568 #else
569                 pi_ear_init = pi_next->next;
570 #endif
571 #endif
572
573 #ifdef USE_CLIP_EVEN
574 #ifdef USE_CLIP_SWEEP
575                 if (pi_ear_init->sign != CONVEX) {
576                         /* take the extra step since this ear isn't a good candidate */
577                         pi_ear_init = reverse ? pi_ear_init->prev : pi_ear_init->next;
578                         reverse = !reverse;
579                 }
580 #endif
581 #else
582                 if ((reverse ? pi_prev->prev : pi_next->next)->sign != CONVEX) {
583                         reverse = !reverse;
584                 }
585 #endif
586
587         }
588
589         if (pf->coords_tot == 3) {
590                 uint *tri = pf_tri_add(pf);
591                 pi_ear = pf->indices;
592                 tri[0] = pi_ear->index; pi_ear = pi_ear->next;
593                 tri[1] = pi_ear->index; pi_ear = pi_ear->next;
594                 tri[2] = pi_ear->index;
595         }
596 }
597
598 /**
599  * \return CONCAVE, TANGENTIAL or CONVEX
600  */
601 static void pf_coord_sign_calc(PolyFill *pf, PolyIndex *pi)
602 {
603         /* localize */
604         const float (*coords)[2] = pf->coords;
605
606         pi->sign = span_tri_v2_sign(
607                 coords[pi->prev->index],
608                 coords[pi->index],
609                 coords[pi->next->index]);
610 }
611
612 static PolyIndex *pf_ear_tip_find(
613         PolyFill *pf
614 #ifdef USE_CLIP_EVEN
615         , PolyIndex *pi_ear_init
616 #endif
617 #ifdef USE_CLIP_SWEEP
618         , bool reverse
619 #endif
620         )
621 {
622         /* localize */
623         const uint coords_tot = pf->coords_tot;
624         PolyIndex *pi_ear;
625
626         uint i;
627
628 #ifdef USE_CLIP_EVEN
629         pi_ear = pi_ear_init;
630 #else
631         pi_ear = pf->indices;
632 #endif
633
634         i = coords_tot;
635         while (i--) {
636                 if (pf_ear_tip_check(pf, pi_ear)) {
637                         return pi_ear;
638                 }
639 #ifdef USE_CLIP_SWEEP
640                 pi_ear = reverse ? pi_ear->prev : pi_ear->next;
641 #else
642                 pi_ear = pi_ear->next;
643 #endif
644         }
645
646         /* Desperate mode: if no vertex is an ear tip,
647          * we are dealing with a degenerate polygon (e.g. nearly collinear).
648          * Note that the input was not necessarily degenerate,
649          * but we could have made it so by clipping some valid ears.
650          *
651          * Idea taken from Martin Held, "FIST: Fast industrial-strength triangulation of polygons",
652          * Algorithmica (1998),
653          * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291
654          *
655          * Return a convex or tangential vertex if one exists.
656          */
657
658 #ifdef USE_CLIP_EVEN
659         pi_ear = pi_ear_init;
660 #else
661         pi_ear = pf->indices;
662 #endif
663
664         i = coords_tot;
665         while (i--) {
666                 if (pi_ear->sign != CONCAVE) {
667                         return pi_ear;
668                 }
669                 pi_ear = pi_ear->next;
670         }
671
672         /* If all vertices are concave, just return the last one. */
673         return pi_ear;
674 }
675
676 static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip)
677 {
678 #ifndef USE_KDTREE
679         /* localize */
680         const float (*coords)[2] = pf->coords;
681         PolyIndex *pi_curr;
682
683         const float *v1, *v2, *v3;
684 #endif
685
686 #if defined(USE_CONVEX_SKIP) && !defined(USE_KDTREE)
687         uint coords_tot_concave_checked = 0;
688 #endif
689
690
691 #ifdef USE_CONVEX_SKIP
692
693 #ifdef USE_CONVEX_SKIP_TEST
694         /* check if counting is wrong */
695         {
696                 uint coords_tot_concave_test = 0;
697                 PolyIndex *pi_iter = pi_ear_tip;
698                 do {
699                         if (pi_iter->sign != CONVEX) {
700                                 coords_tot_concave_test += 1;
701                         }
702                 } while ((pi_iter = pi_iter->next) != pi_ear_tip);
703                 BLI_assert(coords_tot_concave_test == pf->coords_tot_concave);
704         }
705 #endif
706
707         /* fast-path for circles */
708         if (pf->coords_tot_concave == 0) {
709                 return true;
710         }
711 #endif
712
713         if (UNLIKELY(pi_ear_tip->sign == CONCAVE)) {
714                 return false;
715         }
716
717 #ifdef USE_KDTREE
718         {
719                 const uint ind[3] = {
720                     pi_ear_tip->index,
721                     pi_ear_tip->next->index,
722                     pi_ear_tip->prev->index};
723
724                 if (kdtree2d_isect_tri(&pf->kdtree, ind)) {
725                         return false;
726                 }
727         }
728 #else
729
730         v1 = coords[pi_ear_tip->prev->index];
731         v2 = coords[pi_ear_tip->index];
732         v3 = coords[pi_ear_tip->next->index];
733
734         /* Check if any point is inside the triangle formed by previous, current and next vertices.
735          * Only consider vertices that are not part of this triangle,
736          * or else we'll always find one inside. */
737
738         for (pi_curr = pi_ear_tip->next->next; pi_curr != pi_ear_tip->prev; pi_curr = pi_curr->next) {
739                 /* Concave vertices can obviously be inside the candidate ear,
740                  * but so can tangential vertices if they coincide with one of the triangle's vertices. */
741                 if (pi_curr->sign != CONVEX) {
742                         const float *v = coords[pi_curr->index];
743                         /* Because the polygon has clockwise winding order,
744                          * the area sign will be positive if the point is strictly inside.
745                          * It will be 0 on the edge, which we want to include as well. */
746
747                         /* note: check (v3, v1) first since it fails _far_ more often then the other 2 checks
748                          * (those fail equally).
749                          * It's logical - the chance is low that points exist on the
750                          * same side as the ear we're clipping off. */
751                         if ((span_tri_v2_sign(v3, v1, v) != CONCAVE) &&
752                             (span_tri_v2_sign(v1, v2, v) != CONCAVE) &&
753                             (span_tri_v2_sign(v2, v3, v) != CONCAVE))
754                         {
755                                 return false;
756                         }
757
758 #ifdef USE_CONVEX_SKIP
759                         coords_tot_concave_checked += 1;
760                         if (coords_tot_concave_checked == pf->coords_tot_concave) {
761                                 break;
762                         }
763 #endif
764                 }
765         }
766 #endif  /* USE_KDTREE */
767
768         return true;
769 }
770
771 static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip)
772 {
773         uint *tri = pf_tri_add(pf);
774
775         tri[0] = pi_ear_tip->prev->index;
776         tri[1] = pi_ear_tip->index;
777         tri[2] = pi_ear_tip->next->index;
778
779         pf_coord_remove(pf, pi_ear_tip);
780 }
781
782 /**
783  * Initializes the #PolyFill structure before tessellating with #polyfill_calc.
784  */
785 static void polyfill_prepare(
786         PolyFill *pf,
787         const float (*coords)[2],
788         const uint coords_tot,
789         int coords_sign,
790         uint (*r_tris)[3],
791         PolyIndex *r_indices)
792 {
793         /* localize */
794         PolyIndex *indices = r_indices;
795
796         uint i;
797
798         /* assign all polyfill members here */
799         pf->indices = r_indices;
800         pf->coords = coords;
801         pf->coords_tot = coords_tot;
802 #ifdef USE_CONVEX_SKIP
803         pf->coords_tot_concave = 0;
804 #endif
805         pf->tris = r_tris;
806         pf->tris_tot = 0;
807
808         if (coords_sign == 0) {
809                 coords_sign = (cross_poly_v2(coords, coords_tot) >= 0.0f) ? 1 : -1;
810         }
811         else {
812                 /* check we're passing in correcty args */
813 #ifdef USE_STRICT_ASSERT
814 #ifndef NDEBUG
815                 if (coords_sign == 1) {
816                         BLI_assert(cross_poly_v2(coords, coords_tot) >= 0.0f);
817                 }
818                 else {
819                         BLI_assert(cross_poly_v2(coords, coords_tot) <= 0.0f);
820                 }
821 #endif
822 #endif
823         }
824
825         if (coords_sign == 1) {
826                 for (i = 0; i < coords_tot; i++) {
827                         indices[i].next = &indices[i + 1];
828                         indices[i].prev = &indices[i - 1];
829                         indices[i].index = i;
830                 }
831         }
832         else {
833                 /* reversed */
834                 uint n = coords_tot - 1;
835                 for (i = 0; i < coords_tot; i++) {
836                         indices[i].next = &indices[i + 1];
837                         indices[i].prev = &indices[i - 1];
838                         indices[i].index = (n - i);
839                 }
840         }
841         indices[0].prev = &indices[coords_tot - 1];
842         indices[coords_tot - 1].next = &indices[0];
843
844         for (i = 0; i < coords_tot; i++) {
845                 PolyIndex *pi = &indices[i];
846                 pf_coord_sign_calc(pf, pi);
847 #ifdef USE_CONVEX_SKIP
848                 if (pi->sign != CONVEX) {
849                         pf->coords_tot_concave += 1;
850                 }
851 #endif
852         }
853 }
854
855 static void polyfill_calc(
856         PolyFill *pf)
857 {
858 #ifdef USE_KDTREE
859 #ifdef USE_CONVEX_SKIP
860         if (pf->coords_tot_concave)
861 #endif
862         {
863                 kdtree2d_new(&pf->kdtree, pf->coords_tot_concave, pf->coords);
864                 kdtree2d_init(&pf->kdtree, pf->coords_tot, pf->indices);
865                 kdtree2d_balance(&pf->kdtree);
866                 kdtree2d_init_mapping(&pf->kdtree);
867         }
868 #endif
869
870         pf_triangulate(pf);
871 }
872
873 /**
874  * A version of #BLI_polyfill_calc that uses a memory arena to avoid re-allocations.
875  */
876 void BLI_polyfill_calc_arena(
877         const float (*coords)[2],
878         const uint coords_tot,
879         const int coords_sign,
880         uint (*r_tris)[3],
881
882         struct MemArena *arena)
883 {
884         PolyFill pf;
885         PolyIndex *indices = BLI_memarena_alloc(arena, sizeof(*indices) * coords_tot);
886
887 #ifdef DEBUG_TIME
888         TIMEIT_START(polyfill2d);
889 #endif
890
891         polyfill_prepare(
892                 &pf,
893                 coords, coords_tot, coords_sign,
894                 r_tris,
895                 /* cache */
896                 indices);
897
898 #ifdef USE_KDTREE
899         if (pf.coords_tot_concave) {
900                 pf.kdtree.nodes = BLI_memarena_alloc(arena, sizeof(*pf.kdtree.nodes) * pf.coords_tot_concave);
901                 pf.kdtree.nodes_map = memset(BLI_memarena_alloc(arena, sizeof(*pf.kdtree.nodes_map) * coords_tot),
902                                              0xff, sizeof(*pf.kdtree.nodes_map) * coords_tot);
903         }
904         else {
905                 pf.kdtree.totnode = 0;
906         }
907 #endif
908
909         polyfill_calc(&pf);
910
911         /* indices are no longer needed,
912          * caller can clear arena */
913
914 #ifdef DEBUG_TIME
915         TIMEIT_END(polyfill2d);
916 #endif
917 }
918
919 /**
920  * Triangulates the given (convex or concave) simple polygon to a list of triangle vertices.
921  *
922  * \param coords: 2D coordinates describing vertices of the polygon,
923  * in either clockwise or counterclockwise order.
924  * \param coords_tot: Total points in the array.
925  * \param coords_sign: Pass this when we know the sign in advance to avoid extra calculations.
926  *
927  * \param r_tris: This array is filled in with triangle indices in clockwise order.
928  * The length of the array must be ``coords_tot - 2``.
929  * Indices are guaranteed to be assigned to unique triangles, with valid indices,
930  * even in the case of degenerate input (self intersecting polygons, zero area ears... etc).
931  */
932 void BLI_polyfill_calc(
933         const float (*coords)[2],
934         const uint coords_tot,
935         const int coords_sign,
936         uint (*r_tris)[3])
937 {
938         PolyFill pf;
939         PolyIndex *indices = BLI_array_alloca(indices, coords_tot);
940
941 #ifdef DEBUG_TIME
942         TIMEIT_START(polyfill2d);
943 #endif
944
945         polyfill_prepare(
946                 &pf,
947                 coords, coords_tot, coords_sign,
948                 r_tris,
949                 /* cache */
950                 indices);
951
952 #ifdef USE_KDTREE
953         if (pf.coords_tot_concave) {
954                 pf.kdtree.nodes = BLI_array_alloca(pf.kdtree.nodes, pf.coords_tot_concave);
955                 pf.kdtree.nodes_map = memset(BLI_array_alloca(pf.kdtree.nodes_map, coords_tot),
956                                              0xff, sizeof(*pf.kdtree.nodes_map) * coords_tot);
957         }
958         else {
959                 pf.kdtree.totnode = 0;
960         }
961 #endif
962
963         polyfill_calc(&pf);
964
965 #ifdef DEBUG_TIME
966         TIMEIT_END(polyfill2d);
967 #endif
968 }