Delaunay add support for detecting and removing holes from output.

Adds two new output modes to the CDT api which detect and remove
holes. A hole is a face from which a ray shot to the outside
intersects an even number of constraint edges, except we don't
count constraint edges in the same connected region of faces,
where a region is connected via non-constraint edges.

These modes are useful for filling in outlines meant to represent
text characters and the like.

Original patch was from Erik Abrahamsson, modified by me to work
with the "valid Bmesh" output type too. I also added tests
for the new modes.

1 files changed, 5 insertions, 1 deletions

diff --git a/source/blender/blenlib/BLI_delaunay_2d.h b/source/blender/blenlib/BLI_delaunay_2d.h
index e91726991ca..d42bd6af637 100644
--- a/source/blender/blenlib/BLI_delaunay_2d.h
+++ b/source/blender/blenlib/BLI_delaunay_2d.h
@@ -178,6 +178,8 @@ typedef enum CDT_output_type {
   CDT_FULL,
   /** All triangles fully enclosed by constraint edges or faces. */
   CDT_INSIDE,
+  /** Like previous, but detect holes and omit those from output. */
+  CDT_INSIDE_WITH_HOLES,
   /** Only point, edge, and face constraints, and their intersections. */
   CDT_CONSTRAINTS,
   /**
@@ -186,7 +188,9 @@ typedef enum CDT_output_type {
    * #BMesh faces in Blender: that is,
    * no vertex appears more than once and no isolated holes in faces.
    */
-  CDT_CONSTRAINTS_VALID_BMESH
+  CDT_CONSTRAINTS_VALID_BMESH,
+  /** Like previous, but detect holes and omit those from output. */
+  CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES,
 } CDT_output_type;
 
 /**