Geometry API: polyfill2d, ear clipping polygon filling functions.
authorCampbell Barton <ideasman42@gmail.com>
Sat, 30 Nov 2013 10:55:50 +0000 (21:55 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Sat, 30 Nov 2013 11:00:01 +0000 (22:00 +1100)
Simple/predictable polygon filling functions (no hole support)
originally from libgdx which have some advantages over scanfill.

- always creates the same number of triangles (never any missing faces).
- gives same results for any affine transformation.
- doesn't give so many skinny faces by default.

made some changes for Blender.
- remove last ears first (less to memmove)
- step over the ears while clipping to avoid some verts becoming fans to most of the other.

source/blender/blenlib/BLI_polyfill2d.h [new file with mode: 0644]
source/blender/blenlib/CMakeLists.txt
source/blender/blenlib/intern/polyfill2d.c [new file with mode: 0644]

diff --git a/source/blender/blenlib/BLI_polyfill2d.h b/source/blender/blenlib/BLI_polyfill2d.h
new file mode 100644 (file)
index 0000000..40ac4cc
--- /dev/null
@@ -0,0 +1,44 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BLI_POLYFILL2D_H__
+#define __BLI_POLYFILL2D_H__
+
+void BLI_polyfill_calc_ex(
+        const float (*coords)[2],
+        const unsigned int count,
+        unsigned int (*r_tris)[3],
+
+        /* avoid allocating each time */
+        unsigned int *r_indices, signed char *r_coords_sign);
+
+void BLI_polyfill_calc_arena(
+        const float (*coords)[2],
+        const unsigned int coords_tot,
+        unsigned int (*r_tris)[3],
+
+        struct MemArena *arena);
+
+void BLI_polyfill_calc(
+        const float (*coords)[2],
+        const unsigned int coords_tot,
+        unsigned int (*r_tris)[3]);
+
+#endif  /* __BLI_POLYFILL2D_H__ */
index d855d45760a14b235b9b74a4a907eb997f2a94fc..00adb375c417ee5d5df811a1973fe1fadb2c00cd 100644 (file)
@@ -82,6 +82,7 @@ set(SRC
        intern/md5.c
        intern/noise.c
        intern/path_util.c
+       intern/polyfill2d.c
        intern/quadric.c
        intern/rand.c
        intern/rct.c
@@ -148,6 +149,7 @@ set(SRC
        BLI_mempool.h
        BLI_noise.h
        BLI_path_util.h
+       BLI_polyfill2d.h
        BLI_quadric.h
        BLI_rand.h
        BLI_rect.h
diff --git a/source/blender/blenlib/intern/polyfill2d.c b/source/blender/blenlib/intern/polyfill2d.c
new file mode 100644 (file)
index 0000000..8e77166
--- /dev/null
@@ -0,0 +1,375 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/blenlib/intern/polyfill2d.c
+ *  \ingroup bli
+ *
+ * A simple implementation of the ear cutting algorithm
+ * to triangulate simple polygons without holes.
+ *
+ * \note
+ *
+ * Changes made for Blender.
+ *
+ * - loop the array to clip last verts first (less array resizing)
+ *
+ * - advance the ear to clip each iteration
+ *   to avoid fan-filling convex shapes (USE_CLIP_EVEN).
+ *
+ * \note
+ *
+ * No globals - keep threadsafe.
+ */
+
+#include "BLI_utildefines.h"
+#include "BLI_math.h"
+
+#include "BLI_memarena.h"
+#include "BLI_alloca.h"
+
+#include "BLI_polyfill2d.h"  /* own include */
+
+#include "BLI_strict_flags.h"
+
+#define SIGN_EPS 0.000001f
+
+/* avoid fan-fill topology */
+#define USE_CLIP_EVEN
+
+typedef signed char eSign;
+enum {
+       CONCAVE = -1,
+       TANGENTIAL = 0,
+       CONVEX = 1,
+};
+
+typedef struct PolyFill {
+       unsigned int *indices;  /* vertex aligned */
+
+       const float (*coords)[2];
+       unsigned int  coords_tot;
+       eSign        *coords_sign;
+
+       /* A polygon with n vertices has a triangulation of n-2 triangles. */
+       unsigned int (*tris)[3];
+       unsigned int   tris_tot;
+} PolyFill;
+
+
+/* based on libgdx 2013-11-28, apache 2.0 licensed */
+
+static eSign pf_coord_sign_calc(PolyFill *pf, unsigned int index);
+static unsigned int pf_index_prev(const PolyFill *pf, const unsigned int index);
+static unsigned int pf_index_next(const PolyFill *pf, unsigned index);
+
+#ifdef USE_CLIP_EVEN
+static unsigned int pf_ear_tip_find(PolyFill *pf, const unsigned int index_offset);
+#else
+static unsigned int pf_ear_tip_find(PolyFill *pf);
+#endif
+static bool         pf_ear_tip_check(PolyFill *pf, const unsigned int index_ear_tip);
+static void         pf_ear_tip_cut(PolyFill *pf, unsigned int index_ear_tip);
+
+
+BLI_INLINE eSign signum_i(float a)
+{
+       if (UNLIKELY(fabsf(a) < SIGN_EPS))
+               return  0;
+       else if (a > 0.0f)
+               return  1;
+       else
+               return -1;
+}
+
+static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float v3[2])
+{
+       return signum_i(area_tri_signed_v2(v3, v2, v1));
+}
+
+static unsigned int *pf_tri_add(PolyFill *pf)
+{
+       return pf->tris[pf->tris_tot++];
+}
+
+static void pf_coord_remove(PolyFill *pf, const unsigned int index)
+{
+       ARRAY_DELETE(pf->indices,     index, 1, pf->coords_tot);
+       ARRAY_DELETE(pf->coords_sign, index, 1, pf->coords_tot);
+       pf->coords_tot -= 1;
+}
+
+static void pf_triangulate(PolyFill *pf)
+{
+       /* localize */
+       eSign *coords_sign = pf->coords_sign;
+
+       unsigned int index_ear_tip = 0;
+
+
+       while (pf->coords_tot > 3) {
+               unsigned int i_prev, i_next;
+
+#ifdef USE_CLIP_EVEN
+               index_ear_tip = pf_ear_tip_find(pf, index_ear_tip);
+#else
+               index_ear_tip = pf_ear_tip_find(pf);
+#endif
+               pf_ear_tip_cut(pf, index_ear_tip);
+
+               /* The type of the two vertices adjacent to the clipped vertex may have changed. */
+               i_prev = pf_index_prev(pf, index_ear_tip);
+               i_next = (index_ear_tip == pf->coords_tot) ? 0 : index_ear_tip;
+               coords_sign[i_prev] = pf_coord_sign_calc(pf, i_prev);
+               coords_sign[i_next] = pf_coord_sign_calc(pf, i_next);
+
+#ifdef USE_CLIP_EVEN
+               index_ear_tip = i_prev;
+#endif
+       }
+
+       if (pf->coords_tot == 3) {
+               unsigned int *tri = pf_tri_add(pf);
+               tri[0] = pf->indices[0];
+               tri[1] = pf->indices[1];
+               tri[2] = pf->indices[2];
+       }
+}
+
+/**
+ * \return CONCAVE, TANGENTIAL or CONVEX
+ */
+static eSign pf_coord_sign_calc(PolyFill *pf, unsigned int index)
+{
+       /* localize */
+       unsigned int *indices = pf->indices;
+       const float (*coords)[2] = pf->coords;
+
+       return span_tri_v2_sign(
+               coords[indices[pf_index_prev(pf, index)]],
+               coords[indices[index]],
+               coords[indices[pf_index_next(pf, index)]]);
+}
+
+#ifdef USE_CLIP_EVEN
+static unsigned int pf_ear_tip_find(PolyFill *pf, const unsigned int index_offset)
+#else
+static unsigned int pf_ear_tip_find(PolyFill *pf)
+#endif
+{
+       /* localize */
+       const eSign *coords_sign = pf->coords_sign;
+       const unsigned int coords_tot = pf->coords_tot;
+
+       unsigned int i;
+
+
+       i = coords_tot;
+       while (i--) {
+#ifdef USE_CLIP_EVEN
+               unsigned int j = (i + index_offset) % coords_tot;
+               if (pf_ear_tip_check(pf, j)) {
+                       return j;
+               }
+#else
+               if (pf_ear_tip_check(pf, i)) {
+                       return i;
+               }
+#endif
+       }
+
+       /* Desperate mode: if no vertex is an ear tip, we are dealing with a degenerate polygon (e.g. nearly collinear).
+        * Note that the input was not necessarily degenerate, but we could have made it so by clipping some valid ears.
+        *
+        * Idea taken from Martin Held, "FIST: Fast industrial-strength triangulation of polygons", Algorithmica (1998),
+        * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291
+        *
+        * Return a convex or tangential vertex if one exists.
+        */
+
+       i = coords_tot;
+       while (i--) {
+#ifdef USE_CLIP_EVEN
+               unsigned int j = (i + index_offset) % coords_tot;
+               if (coords_sign[j] != CONCAVE) {
+                       return j;
+               }
+#else
+               if (coords_sign[i] != CONCAVE) {
+                       return i;
+               }
+#endif
+       }
+
+       /* If all vertices are concave, just return the last one. */
+       return coords_tot - 1;
+}
+
+static bool pf_ear_tip_check(PolyFill *pf, const unsigned int index_ear_tip)
+{
+       /* localize */
+       const unsigned int *indices = pf->indices;
+       const float (*coords)[2] = pf->coords;
+       const eSign *coords_sign = pf->coords_sign;
+
+       unsigned int i_prev, i_curr, i_next;
+
+       const float *v1, *v2, *v3;
+
+       if (UNLIKELY(coords_sign[index_ear_tip] == CONCAVE)) {
+               return false;
+       }
+
+       i_prev = pf_index_prev(pf, index_ear_tip);
+       i_next = pf_index_next(pf, index_ear_tip);
+
+       v1 = coords[indices[i_prev]];
+       v2 = coords[indices[index_ear_tip]];
+       v3 = coords[indices[i_next]];
+
+       /* Check if any point is inside the triangle formed by previous, current and next vertices.
+        * Only consider vertices that are not part of this triangle, or else we'll always find one inside. */
+
+       for (i_curr = pf_index_next(pf, i_next); i_curr != i_prev; i_curr = pf_index_next(pf, i_curr)) {
+               /* Concave vertices can obviously be inside the candidate ear, but so can tangential vertices
+                * if they coincide with one of the triangle's vertices. */
+               if (coords_sign[i_curr] != CONVEX) {
+                       const float *v = coords[indices[i_curr]];
+                       /* Because the polygon has clockwise winding order,
+                        * the area sign will be positive if the point is strictly inside.
+                        * It will be 0 on the edge, which we want to include as well. */
+                       if ((span_tri_v2_sign(v1, v2, v) == CONVEX) &&
+                           (span_tri_v2_sign(v2, v3, v) == CONVEX) &&
+                           (span_tri_v2_sign(v3, v1, v) == CONVEX))
+                       {
+                               return false;
+                       }
+               }
+       }
+       return true;
+}
+
+static void pf_ear_tip_cut(PolyFill *pf, unsigned int index_ear_tip)
+{
+       unsigned int *tri = pf_tri_add(pf);
+
+       tri[0] = pf->indices[pf_index_prev(pf, index_ear_tip)];
+       tri[1] = pf->indices[index_ear_tip];
+       tri[2] = pf->indices[pf_index_next(pf, index_ear_tip)];
+
+       pf_coord_remove(pf, index_ear_tip);
+}
+
+static unsigned int pf_index_prev(const PolyFill *pf, const unsigned int index)
+{
+       return (index ? index : pf->coords_tot) - 1;
+}
+
+static unsigned int pf_index_next(const PolyFill *pf, unsigned index)
+{
+       return (index + 1) % pf->coords_tot;
+}
+
+/**
+* Triangulates the given (convex or concave) simple polygon to a list of triangle vertices.
+* \param vertices pairs describing vertices of the polygon, in either clockwise or counterclockwise order.
+* \return triples of triangle indices in clockwise order.
+*         Note the returned array is reused for later calls to the same method.
+*/
+void BLI_polyfill_calc_ex(
+        const float (*coords)[2],
+        const unsigned int coords_tot,
+        unsigned int (*r_tris)[3],
+
+        unsigned int *r_indices, eSign *r_coords_sign)
+{
+       PolyFill pf;
+
+       /* localize */
+       unsigned int *indices = r_indices;
+       eSign *coords_sign = r_coords_sign;
+
+       unsigned int i;
+
+       /* assign all polyfill members here */
+       pf.indices = r_indices;
+       pf.coords = coords;
+       pf.coords_tot = coords_tot;
+       pf.coords_sign = r_coords_sign;
+       pf.tris = r_tris;
+       pf.tris_tot = 0;
+
+       if ((coords_tot < 3) ||
+           cross_poly_v2((int)coords_tot, (float(*)[2])coords) > 0.0f)
+       {
+               for (i = 0; i < coords_tot; i++) {
+                       indices[i] = i;
+               }
+       }
+       else {
+               /* reversed */
+               unsigned int n = coords_tot - 1;
+               for (i = 0; i < coords_tot; i++) {
+                       indices[i] = (n - i);
+               }
+       }
+
+       for (i = 0; i < coords_tot; i++) {
+               coords_sign[i] = pf_coord_sign_calc(&pf, i);
+       }
+
+       pf_triangulate(&pf);
+}
+
+void BLI_polyfill_calc_arena(
+        const float (*coords)[2],
+        const unsigned int coords_tot,
+        unsigned int (*r_tris)[3],
+
+        struct MemArena *arena)
+{
+       unsigned int *indicies = BLI_memarena_alloc(arena, (int)(sizeof(*indicies) * coords_tot));
+       eSign *coords_sign = BLI_memarena_alloc(arena, (int)(sizeof(*coords_sign) * coords_tot));
+
+       BLI_polyfill_calc_ex(
+               coords, coords_tot,
+               r_tris,
+               /* cache */
+
+               indicies, coords_sign);
+
+       /* indicies & coords_sign are no longer needed,
+        * caller can clear arena */
+}
+
+void BLI_polyfill_calc(
+        const float (*coords)[2],
+        const unsigned int coords_tot,
+        unsigned int (*r_tris)[3])
+{
+       unsigned int *indicies = BLI_array_alloca(indicies, coords_tot);
+       eSign *coords_sign = BLI_array_alloca(coords_sign, coords_tot);
+
+       BLI_polyfill_calc_ex(
+               coords, coords_tot,
+               r_tris,
+               /* cache */
+
+               indicies, coords_sign);
+}