Code Cleanup: spelling
[blender.git] / source / blender / blenlib / intern / polyfill2d.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 /** \file blender/blenlib/intern/polyfill2d.c
22  *  \ingroup bli
23  *
24  * A simple implementation of the ear cutting algorithm
25  * to triangulate simple polygons without holes.
26  *
27  * \note
28  *
29  * Changes made for Blender.
30  *
31  * - loop the array to clip last verts first (less array resizing)
32  *
33  * - advance the ear to clip each iteration
34  *   to avoid fan-filling convex shapes (USE_CLIP_EVEN).
35  *
36  * - avoid intersection tests when there are no convex points (USE_CONVEX_SKIP).
37  *
38  * \note
39  *
40  * No globals - keep threadsafe.
41  */
42
43 #include "BLI_utildefines.h"
44 #include "BLI_math.h"
45
46 #include "BLI_memarena.h"
47 #include "BLI_alloca.h"
48
49 #include "BLI_polyfill2d.h"  /* own include */
50
51 #include "BLI_strict_flags.h"
52
53 /* avoid fan-fill topology */
54 #define USE_CLIP_EVEN
55 #define USE_CONVEX_SKIP
56 // #define USE_CONVEX_SKIP_TEST
57
58 typedef signed char eSign;
59 enum {
60         CONCAVE = -1,
61         TANGENTIAL = 0,
62         CONVEX = 1,
63 };
64
65 typedef struct PolyFill {
66         unsigned int *indices;  /* vertex aligned */
67
68         const float (*coords)[2];
69         unsigned int  coords_tot;
70         eSign        *coords_sign;
71 #ifdef USE_CONVEX_SKIP
72         unsigned int  coords_tot_concave;
73 #endif
74
75         /* A polygon with n vertices has a triangulation of n-2 triangles. */
76         unsigned int (*tris)[3];
77         unsigned int   tris_tot;
78 } PolyFill;
79
80
81 /* based on libgdx 2013-11-28, apache 2.0 licensed */
82
83 static eSign pf_coord_sign_calc(PolyFill *pf, unsigned int index);
84 static unsigned int pf_index_prev(const PolyFill *pf, const unsigned int index);
85 static unsigned int pf_index_next(const PolyFill *pf, unsigned index);
86
87 #ifdef USE_CLIP_EVEN
88 static unsigned int pf_ear_tip_find(PolyFill *pf, const unsigned int index_offset);
89 #else
90 static unsigned int pf_ear_tip_find(PolyFill *pf);
91 #endif
92 static bool         pf_ear_tip_check(PolyFill *pf, const unsigned int index_ear_tip);
93 static void         pf_ear_tip_cut(PolyFill *pf, unsigned int index_ear_tip);
94
95
96 BLI_INLINE eSign signum_i(float a)
97 {
98         if (UNLIKELY(a == 0.0f))
99                 return  0;
100         else if (a > 0.0f)
101                 return  1;
102         else
103                 return -1;
104 }
105
106 /**
107  * alternative version of #area_tri_signed_v2
108  * needed because of float precision issues
109  *
110  * \note removes / 2 since its not needed since we only need ths sign.
111  */
112 BLI_INLINE float area_tri_signed_v2_alt_2x(const float v1[2], const float v2[2], const float v3[2])
113 {
114         return ((v1[0] * (v2[1] - v3[1])) +
115                 (v2[0] * (v3[1] - v1[1])) +
116                 (v3[0] * (v1[1] - v2[1])));
117 }
118
119
120 static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float v3[2])
121 {
122         return signum_i(area_tri_signed_v2_alt_2x(v3, v2, v1));
123 }
124
125 static unsigned int *pf_tri_add(PolyFill *pf)
126 {
127         return pf->tris[pf->tris_tot++];
128 }
129
130 static void pf_coord_remove(PolyFill *pf, const unsigned int index)
131 {
132         ARRAY_DELETE(pf->indices,     index, 1, pf->coords_tot);
133         ARRAY_DELETE(pf->coords_sign, index, 1, pf->coords_tot);
134         pf->coords_tot -= 1;
135 }
136
137 static void pf_triangulate(PolyFill *pf)
138 {
139         /* localize */
140         eSign *coords_sign = pf->coords_sign;
141
142         unsigned int index_ear_tip = 0;
143
144
145         while (pf->coords_tot > 3) {
146                 unsigned int i_prev, i_next;
147
148 #ifdef USE_CONVEX_SKIP
149                 eSign sign_orig_prev, sign_orig_next;
150 #endif
151
152
153 #ifdef USE_CLIP_EVEN
154                 index_ear_tip = pf_ear_tip_find(pf, index_ear_tip);
155 #else
156                 index_ear_tip = pf_ear_tip_find(pf);
157 #endif
158
159 #ifdef USE_CONVEX_SKIP
160                 if (coords_sign[index_ear_tip] != CONVEX) {
161                         pf->coords_tot_concave -= 1;
162                 }
163 #endif
164
165                 pf_ear_tip_cut(pf, index_ear_tip);
166
167                 /* The type of the two vertices adjacent to the clipped vertex may have changed. */
168                 i_prev = pf_index_prev(pf, index_ear_tip);
169                 i_next = (index_ear_tip == pf->coords_tot) ? 0 : index_ear_tip;
170
171 #ifdef USE_CONVEX_SKIP
172                 sign_orig_prev = coords_sign[i_prev];
173                 sign_orig_next = coords_sign[i_next];
174 #endif
175
176                 coords_sign[i_prev] = pf_coord_sign_calc(pf, i_prev);
177                 coords_sign[i_next] = pf_coord_sign_calc(pf, i_next);
178
179 #ifdef USE_CONVEX_SKIP
180                 /* check if any verts became convex the (else if)
181                  * case is highly unlikely but may happen with degenerate polygons */
182                 if               ((sign_orig_prev != CONVEX) && (coords_sign[i_prev] == CONVEX))  pf->coords_tot_concave -= 1;
183                 else if (UNLIKELY((sign_orig_prev == CONVEX) && (coords_sign[i_prev] != CONVEX))) pf->coords_tot_concave += 1;
184
185                 if               ((sign_orig_next != CONVEX) && (coords_sign[i_next] == CONVEX))  pf->coords_tot_concave -= 1;
186                 else if (UNLIKELY((sign_orig_next == CONVEX) && (coords_sign[i_next] != CONVEX))) pf->coords_tot_concave += 1;
187 #endif
188
189 #ifdef USE_CLIP_EVEN
190                 index_ear_tip = i_prev;
191 #endif
192         }
193
194         if (pf->coords_tot == 3) {
195                 unsigned int *tri = pf_tri_add(pf);
196                 tri[0] = pf->indices[0];
197                 tri[1] = pf->indices[1];
198                 tri[2] = pf->indices[2];
199         }
200 }
201
202 /**
203  * \return CONCAVE, TANGENTIAL or CONVEX
204  */
205 static eSign pf_coord_sign_calc(PolyFill *pf, unsigned int index)
206 {
207         /* localize */
208         unsigned int *indices = pf->indices;
209         const float (*coords)[2] = pf->coords;
210
211         return span_tri_v2_sign(
212                 coords[indices[pf_index_prev(pf, index)]],
213                 coords[indices[index]],
214                 coords[indices[pf_index_next(pf, index)]]);
215 }
216
217 #ifdef USE_CLIP_EVEN
218 static unsigned int pf_ear_tip_find(PolyFill *pf, const unsigned int index_offset)
219 #else
220 static unsigned int pf_ear_tip_find(PolyFill *pf)
221 #endif
222 {
223         /* localize */
224         const eSign *coords_sign = pf->coords_sign;
225         const unsigned int coords_tot = pf->coords_tot;
226
227         unsigned int i;
228
229
230         i = coords_tot;
231         while (i--) {
232 #ifdef USE_CLIP_EVEN
233                 unsigned int j = (i + index_offset) % coords_tot;
234                 if (pf_ear_tip_check(pf, j)) {
235                         return j;
236                 }
237 #else
238                 if (pf_ear_tip_check(pf, i)) {
239                         return i;
240                 }
241 #endif
242         }
243
244         /* Desperate mode: if no vertex is an ear tip, we are dealing with a degenerate polygon (e.g. nearly collinear).
245          * Note that the input was not necessarily degenerate, but we could have made it so by clipping some valid ears.
246          *
247          * Idea taken from Martin Held, "FIST: Fast industrial-strength triangulation of polygons", Algorithmica (1998),
248          * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291
249          *
250          * Return a convex or tangential vertex if one exists.
251          */
252
253         i = coords_tot;
254         while (i--) {
255 #ifdef USE_CLIP_EVEN
256                 unsigned int j = (i + index_offset) % coords_tot;
257                 if (coords_sign[j] != CONCAVE) {
258                         return j;
259                 }
260 #else
261                 if (coords_sign[i] != CONCAVE) {
262                         return i;
263                 }
264 #endif
265         }
266
267         /* If all vertices are concave, just return the last one. */
268         return coords_tot - 1;
269 }
270
271 static bool pf_ear_tip_check(PolyFill *pf, const unsigned int index_ear_tip)
272 {
273         /* localize */
274         const unsigned int *indices = pf->indices;
275         const float (*coords)[2] = pf->coords;
276         const eSign *coords_sign = pf->coords_sign;
277
278         unsigned int i_prev, i_curr, i_next;
279
280         const float *v1, *v2, *v3;
281
282 #ifdef USE_CONVEX_SKIP
283         unsigned int coords_tot_concave_checked = 0;
284 #endif
285
286
287 #ifdef USE_CONVEX_SKIP
288
289 #ifdef USE_CONVEX_SKIP_TEST
290         /* check if counting is wrong */
291         {
292                 unsigned int coords_tot_concave_test = 0;
293                 unsigned int i = pf->coords_tot;
294                 while (i--) {
295                         if (coords_sign[i] != CONVEX) {
296                                 coords_tot_concave_test += 1;
297                         }
298                 }
299                 BLI_assert(coords_tot_concave_test == pf->coords_tot_concave);
300         }
301 #endif
302
303         /* fast-path for circles */
304         if (pf->coords_tot_concave == 0) {
305                 return true;
306         }
307 #endif
308
309         if (UNLIKELY(coords_sign[index_ear_tip] == CONCAVE)) {
310                 return false;
311         }
312
313         i_prev = pf_index_prev(pf, index_ear_tip);
314         i_next = pf_index_next(pf, index_ear_tip);
315
316         v1 = coords[indices[i_prev]];
317         v2 = coords[indices[index_ear_tip]];
318         v3 = coords[indices[i_next]];
319
320         /* Check if any point is inside the triangle formed by previous, current and next vertices.
321          * Only consider vertices that are not part of this triangle, or else we'll always find one inside. */
322
323         for (i_curr = pf_index_next(pf, i_next); i_curr != i_prev; i_curr = pf_index_next(pf, i_curr)) {
324                 /* Concave vertices can obviously be inside the candidate ear, but so can tangential vertices
325                  * if they coincide with one of the triangle's vertices. */
326                 if (coords_sign[i_curr] != CONVEX) {
327                         const float *v = coords[indices[i_curr]];
328                         /* Because the polygon has clockwise winding order,
329                          * the area sign will be positive if the point is strictly inside.
330                          * It will be 0 on the edge, which we want to include as well. */
331                         if ((span_tri_v2_sign(v1, v2, v) != CONCAVE) &&
332                             (span_tri_v2_sign(v2, v3, v) != CONCAVE) &&
333                             (span_tri_v2_sign(v3, v1, v) != CONCAVE))
334                         {
335                                 return false;
336                         }
337
338 #ifdef USE_CONVEX_SKIP
339                         coords_tot_concave_checked += 1;
340                         if (coords_tot_concave_checked == pf->coords_tot_concave) {
341                                 break;
342                         }
343 #endif
344                 }
345         }
346         return true;
347 }
348
349 static void pf_ear_tip_cut(PolyFill *pf, unsigned int index_ear_tip)
350 {
351         unsigned int *tri = pf_tri_add(pf);
352
353         tri[0] = pf->indices[pf_index_prev(pf, index_ear_tip)];
354         tri[1] = pf->indices[index_ear_tip];
355         tri[2] = pf->indices[pf_index_next(pf, index_ear_tip)];
356
357         pf_coord_remove(pf, index_ear_tip);
358 }
359
360 static unsigned int pf_index_prev(const PolyFill *pf, const unsigned int index)
361 {
362         return (index ? index : pf->coords_tot) - 1;
363 }
364
365 static unsigned int pf_index_next(const PolyFill *pf, unsigned index)
366 {
367         return (index + 1) % pf->coords_tot;
368 }
369
370 /**
371 * Triangulates the given (convex or concave) simple polygon to a list of triangle vertices.
372 * \param vertices pairs describing vertices of the polygon, in either clockwise or counterclockwise order.
373 * \return triples of triangle indices in clockwise order.
374 *         Note the returned array is reused for later calls to the same method.
375 */
376 void BLI_polyfill_calc_ex(
377         const float (*coords)[2],
378         const unsigned int coords_tot,
379         unsigned int (*r_tris)[3],
380
381         unsigned int *r_indices, eSign *r_coords_sign)
382 {
383         PolyFill pf;
384
385         /* localize */
386         unsigned int *indices = r_indices;
387         eSign *coords_sign = r_coords_sign;
388
389         unsigned int i;
390
391         /* assign all polyfill members here */
392         pf.indices = r_indices;
393         pf.coords = coords;
394         pf.coords_tot = coords_tot;
395         pf.coords_sign = r_coords_sign;
396 #ifdef USE_CONVEX_SKIP
397         pf.coords_tot_concave = 0;
398 #endif
399         pf.tris = r_tris;
400         pf.tris_tot = 0;
401
402         if ((coords_tot < 3) ||
403             cross_poly_v2((int)coords_tot, (float(*)[2])coords) > 0.0f)
404         {
405                 for (i = 0; i < coords_tot; i++) {
406                         indices[i] = i;
407                 }
408         }
409         else {
410                 /* reversed */
411                 unsigned int n = coords_tot - 1;
412                 for (i = 0; i < coords_tot; i++) {
413                         indices[i] = (n - i);
414                 }
415         }
416
417         for (i = 0; i < coords_tot; i++) {
418                 coords_sign[i] = pf_coord_sign_calc(&pf, i);
419 #ifdef USE_CONVEX_SKIP
420                 if (coords_sign[i] != CONVEX) {
421                         pf.coords_tot_concave += 1;
422                 }
423 #endif
424         }
425
426         pf_triangulate(&pf);
427 }
428
429 void BLI_polyfill_calc_arena(
430         const float (*coords)[2],
431         const unsigned int coords_tot,
432         unsigned int (*r_tris)[3],
433
434         struct MemArena *arena)
435 {
436         unsigned int *indices = BLI_memarena_alloc(arena, sizeof(*indices) * coords_tot);
437         eSign *coords_sign = BLI_memarena_alloc(arena, sizeof(*coords_sign) * coords_tot);
438
439         BLI_polyfill_calc_ex(
440                 coords, coords_tot,
441                 r_tris,
442                 /* cache */
443
444                 indices, coords_sign);
445
446         /* indices & coords_sign are no longer needed,
447          * caller can clear arena */
448 }
449
450 void BLI_polyfill_calc(
451         const float (*coords)[2],
452         const unsigned int coords_tot,
453         unsigned int (*r_tris)[3])
454 {
455         unsigned int *indices = BLI_array_alloca(indices, coords_tot);
456         eSign *coords_sign = BLI_array_alloca(coords_sign, coords_tot);
457
458         BLI_polyfill_calc_ex(
459                 coords, coords_tot,
460                 r_tris,
461                 /* cache */
462
463                 indices, coords_sign);
464 }