[Bf-blender-cvs] [b944510] master: Geometry API: polyfill2d, ear clipping polygon filling functions.
Campbell Barton
noreply at git.blender.org
Sat Nov 30 12:01:03 CET 2013
Commit: b9445106b23b0da0436bcca7be0131b577980a5a
Author: Campbell Barton
Date: Sat Nov 30 21:55:50 2013 +1100
http://developer.blender.org/rBb9445106b23b0da0436bcca7be0131b577980a5a
Geometry API: polyfill2d, ear clipping polygon filling functions.
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.
===================================================================
A source/blender/blenlib/BLI_polyfill2d.h
M source/blender/blenlib/CMakeLists.txt
A source/blender/blenlib/intern/polyfill2d.c
===================================================================
diff --git a/source/blender/blenlib/BLI_polyfill2d.h b/source/blender/blenlib/BLI_polyfill2d.h
new file mode 100644
index 0000000..40ac4cc
--- /dev/null
+++ b/source/blender/blenlib/BLI_polyfill2d.h
@@ -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__ */
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index d855d45..00adb37 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -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
index 0000000..8e77166
--- /dev/null
+++ b/source/blender/blenlib/intern/polyfill2d.c
@@ -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)
+{
+ r
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list