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.

1 files changed, 44 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_polyfill2d.h b/source/blender/blenlib/BLI_polyfill2d.h
new file mode 100644
index 00000000000..40ac4cc0ad0
--- /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__ */