Bug 1501: Apply intersection tests for non-convex shapes to reject new CCW and non-circulcircle triangulation candidates in our Delaunay tessellator

<https://jogamp.org/bugzilla//show_bug.cgi?id=1501#c6>

The used Delaunay tessellation works well with (almost) convex shapes.
In case e.g. a glyph gets to the extremes like 'M' in FreeMono
or any other complex Chinese symbol - it may just simply happen
that the new non-circumcircle triangle point crosses the inner (hope)
or outer boundaries of the given polygon.

Applying further constraint at Loop.cut() resolves most cases
by rejecting the proposed CCW and non-circumcircle triangle candidate
if its new two line-segments intersects with the original polygon.

This results in mostly proper rendered Chinese fonts and also
FreeMono is now readable - overal remaining bugs in Glyphs is low.

+++

Of course, this intersection test is costly around >= O(log(n)*n) costs,
practically adding a measured ~65% processing time.
E.g. for FontView01 using FreeSerif.ttf
- orig total took 1430.817638ms, per-glyph 0.2236ms, glyphs 6399
- fix  total took 2377.337359ms, per-glyph 0.371517ms, glyphs 6399

Pure Glyph/Shape instantiation shows > 2x costs:
 750 ms 100% convex (fake)
1875 ms   0% convex (fake)
1870 ms  13% convex 824/6399

+++

Hence it is desired to either
(1) Manually mark a polygon non-convex to add described intersection test for accuracy.
    Also may be used to just drop the additional costs despite the lack of correctness.

PROVIDED

(2) Determine non-convex nature of a polygon with a and overall less expensive algorithm.
    If considerably cheaper, this could reduce O(log(n) * n) -> O(n) or even O(log n).

Added convex/non-convex classification while ignoring off-curve points,
but only ~13% of FreeSerif is pure convex,
hence there is no benefit with this classification type.

It might be desired to attempt other classes, i.e.
being rendered in non-convex mode w/o intersection tests.
See
- GENERALIZED DELAUNAY TRIANGULATIONS OF NON-CONVEX DOMAINS
  https://deepblue.lib.umich.edu/bitstream/handle/2027.42/28782/0000614.pdf;sequence=1

- https://en.wikipedia.org/wiki/List_of_self-intersecting_polygons
- https://en.wikipedia.org/wiki/Complex_polygon

6 files changed, 384 insertions, 134 deletions

diff --git a/src/demos/com/jogamp/opengl/demos/graph/ui/FontView01.java b/src/demos/com/jogamp/opengl/demos/graph/ui/FontView01.java
index 9a143a29d..2035c39cc 100644
--- a/src/demos/com/jogamp/opengl/demos/graph/ui/FontView01.java
+++ b/src/demos/com/jogamp/opengl/demos/graph/ui/FontView01.java
@@ -99,7 +99,8 @@ import com.jogamp.opengl.util.Animator;
 public class FontView01 {
     private static final float GlyphGridWidth = 3/4f; // FBO AA: 3/4f = 0.75f dropped fine grid lines @ 0.2f thickness; 0.70f OK
     private static final float GlyphGridBorderThickness = 0.02f; // thickness 0.2f dropping
-    private static final Vec4f GlyphGridBorderColor = new Vec4f(0.2f, 0.2f, 0.2f, 1);
+    private static final Vec4f GlyphGridBorderColorConvex = new Vec4f(0.2f, 0.2f, 0.7f, 1);
+    private static final Vec4f GlyphGridBorderColorComplex = new Vec4f(0.2f, 0.2f, 0.2f, 1);
 
     // static CommandlineOptions options = new CommandlineOptions(1280, 720, Region.MSAA_RENDERING_BIT, Region.DEFAULT_AA_QUALITY, 4);
     // static CommandlineOptions options = new CommandlineOptions(1280, 720, Region.VBAA_RENDERING_BIT);
@@ -420,6 +421,7 @@ public class FontView01 {
         }
         printScreenOnGLThread(scene, window.getChosenGLCapabilities(), font, gridDim.contourChars.get(0));
         // stay open ..
+        OutlineShape.printPerf(System.err);
     }
 
     static void printScreenOnGLThread(final Scene scene, final GLCapabilitiesImmutable caps, final Font font, final int codepoint) {
@@ -435,6 +437,7 @@ public class FontView01 {
         final int rows;
         final int rowsPerPage;
         final int elemCount;
+        int convexGlyphCount;
         int maxNameLen;
 
         public GridDim(final Font font, final int columns, final int rowsPerPage, final int xReserved) {
@@ -453,11 +456,15 @@ public class FontView01 {
         private int scanContourGlyphs(final Font font) {
             final long t0 = Clock.currentNanos();
             contourChars.clear();
+            convexGlyphCount = 0;
             maxNameLen = 1;
             final int[] max = { max_glyph_count };
             font.forAllGlyphs((final Glyph fg) -> {
                 if( !fg.isNonContour() && max[0]-- > 0 ) {
                     contourChars.add( fg.getCodepoint() );
+                    if( null != fg.getShape() && fg.getShape().isConvex() ) {
+                        ++convexGlyphCount;
+                    }
                     maxNameLen = Math.max(maxNameLen, fg.getName().length());
                 }
             });
@@ -468,7 +475,7 @@ public class FontView01 {
             return contourChars.size();
         }
         @Override
-        public String toString() { return "GridDim[contours "+glyphCount+", "+columns+"x"+rows+"="+(columns*rows)+">="+elemCount+", rows/pg "+rowsPerPage+"]"; }
+        public String toString() { return "GridDim[contours "+glyphCount+", convex "+convexGlyphCount+" ("+((float)convexGlyphCount/(float)glyphCount)*100+"%), "+columns+"x"+rows+"="+(columns*rows)+">="+elemCount+", rows/pg "+rowsPerPage+"]"; }
     }
 
     static Group getGlyphShapeHolder(final Shape shape0) {
@@ -498,6 +505,7 @@ public class FontView01 {
         for(int idx = 0; idx < gridDim.glyphCount; ++idx) {
             final char codepoint = gridDim.contourChars.get(idx);
             final Font.Glyph fg = font.getGlyph(codepoint);
+            final boolean isConvex = null != fg.getShape() ? fg.getShape().isConvex() : true;
 
             final GlyphShape g = new GlyphShape(options.renderModes, fg, 0, 0);
             g.setColor(0.1f, 0.1f, 0.1f, 1).setName("GlyphShape");
@@ -511,7 +519,8 @@ public class FontView01 {
             final AABBox gbox = fg.getBounds(tmpBox); // g.getBounds(glp);
             final boolean addUnderline = showUnderline && gbox.getMinY() < 0f;
             final Group c1 = new Group( new BoxLayout( 1f, 1f, addUnderline ? Alignment.None : Alignment.Center) );
-            c1.setBorder(GlyphGridBorderThickness).setBorderColor(GlyphGridBorderColor).setInteractive(true).setDragAndResizable(false).setName("GlyphHolder2");
+            c1.setBorder(GlyphGridBorderThickness).setBorderColor(isConvex ? GlyphGridBorderColorConvex : GlyphGridBorderColorComplex)
+              .setInteractive(true).setDragAndResizable(false).setName("GlyphHolder2");
             if( addUnderline ) {
                 final Shape underline = new Rectangle(options.renderModes, 1f, gbox.getMinY(), 0.01f).setInteractive(false).setColor(0f, 0f, 1f, 0.25f);
                 c1.addShape(underline);
@@ -565,11 +574,12 @@ public class FontView01 {
 
     static String getGlyphInfo(final Font.Glyph g) {
         final OutlineShape os = g.getShape();
+        final boolean isConvex = null != os ? os.isConvex() : true;
         final int osVertices = null != os ? os.getVertexCount() : 0;
         final String name_s = null != g.getName() ? g.getName() : "";
         final AABBox bounds = g.getBounds();
         final String box_s = String.format("Box %+.3f/%+.3f%n    %+.3f/%+.3f", bounds.getLow().x(), bounds.getLow().y(), bounds.getHigh().x(), bounds.getHigh().y());
-        return String.format((Locale)null, "%s%nHeight: %1.3f%nLine Height: %1.3f%n%nSymbol: %04x, id %04x%nName: '%s'%nDim %1.3f x %1.3f%n%s%nAdvance %1.3f%nLS Bearings: %1.3f%nVertices: %03d",
+        return String.format((Locale)null, "%s%nHeight: %1.3f%nLine Height: %1.3f%n%nSymbol: %04x, id %04x%nName: '%s'%nDim %1.3f x %1.3f%n%s%nAdvance %1.3f%nLS Bearings: %1.3f%nVertices: %03d%n%s",
                 g.getFont().getFullFamilyName(),
                 g.getFont().getMetrics().getAscent() - g.getFont().getMetrics().getDescent(), // font hhea table
                 g.getFont().getLineHeight(), // font hhea table
@@ -577,6 +587,6 @@ public class FontView01 {
                 bounds.getWidth(), bounds.getHeight(), box_s,
                 g.getAdvanceWidth(),
                 g.getLeftSideBearings(),
-                osVertices);
+                osVertices, isConvex?"Convex":"Non-Convex");
     }
 }
diff --git a/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java b/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java
index d481af24c..18e7328ce 100644
--- a/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java
+++ b/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java
@@ -1,5 +1,5 @@
 /**
- * Copyright 2010-2023 JogAmp Community. All rights reserved.
+ * Copyright 2010-2024 JogAmp Community. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without modification, are
  * permitted provided that the following conditions are met:
@@ -135,15 +135,20 @@ public final class OutlineShape implements Comparable<OutlineShape> {
     /** Initial {@link #getSharpness()} value, which can be modified via {@link #setSharpness(float)}. */
     public static final float DEFAULT_SHARPNESS = 0.5f;
 
-    public static final int DIRTY_BOUNDS = 1 << 0;
+    private static final int DIRTY_BOUNDS = 1 << 0;
     /**
      * Modified shape, requires to update the vertices and triangles, here: vertices.
      */
-    public static final int DIRTY_VERTICES  = 1 << 1;
+    private static final int DIRTY_VERTICES  = 1 << 1;
     /**
      * Modified shape, requires to update the vertices and triangles, here: triangulation.
      */
-    public static final int DIRTY_TRIANGLES  = 1 << 2;
+    private static final int DIRTY_TRIANGLES  = 1 << 2;
+    /**
+     * Modified shape, requires to update the convex determination
+     */
+    private static final int DIRTY_CONVEX  = 1 << 3;
+    private static final int OVERRIDE_CONVEX  = 1 << 4;
 
     /** The list of {@link Outline}s that are part of this
      *  outline shape.
@@ -154,6 +159,7 @@ public final class OutlineShape implements Comparable<OutlineShape> {
     private final ArrayList<Triangle> triangles;
     private final ArrayList<Vertex> vertices;
     private int addedVerticeCount;
+    private boolean convexFlag;
 
     private VerticesState outlineState;
 
@@ -181,6 +187,7 @@ public final class OutlineShape implements Comparable<OutlineShape> {
         this.triangles = new ArrayList<Triangle>();
         this.vertices = new ArrayList<Vertex>();
         this.addedVerticeCount = 0;
+        this.convexFlag = true;
         this.dirtyBits = 0;
         this.sharpness = DEFAULT_SHARPNESS;
     }
@@ -214,6 +221,7 @@ public final class OutlineShape implements Comparable<OutlineShape> {
         vertices.clear();
         triangles.clear();
         addedVerticeCount = 0;
+        convexFlag = true;
         dirtyBits = 0;
     }
 
@@ -221,7 +229,7 @@ public final class OutlineShape implements Comparable<OutlineShape> {
     public final void clearCache() {
         vertices.clear();
         triangles.clear();
-        dirtyBits |= DIRTY_TRIANGLES | DIRTY_VERTICES;
+        dirtyBits |= DIRTY_TRIANGLES | DIRTY_VERTICES | DIRTY_CONVEX;
     }
 
     /** Returns the number of {@link Outline}s. */
@@ -254,6 +262,50 @@ public final class OutlineShape implements Comparable<OutlineShape> {
     }
 
     /**
+     * Returns cached or computed result whether all {@code polyline}s of {@link #getOutline(int)} are of convex shape, see {@link Outline#isConvex()}.
+     * <p>
+     * A polyline with less than 3 elements is marked convex for simplicity,
+     * since a non-convex complex shape may need to pass intersection testing within triangulation.
+     * </p>
+     * <p>
+     * The result is cached.
+     * </p>
+     * @see #setOverrideConvex(boolean)
+     * @see #clearOverrideConvex()
+     */
+    public boolean isConvex() {
+        if( 0 == ( OVERRIDE_CONVEX & dirtyBits ) ) {
+            if( 0 != ( DIRTY_CONVEX & dirtyBits ) ) {
+                convexFlag = true;
+                final int sz = this.getOutlineCount();
+                for(int i=0; i<sz && convexFlag; ++i) {
+                    convexFlag = getOutline(i).isConvex();
+                }
+                dirtyBits &= ~DIRTY_CONVEX;
+            }
+        }
+        return convexFlag;
+    }
+    /**
+     * Overrides {@link #isConvex()} using the given value instead of computing via {@link Outline#isConvex()}.
+     * @see #clearOverrideConvex()
+     * @see #isConvex()
+     */
+    public void setOverrideConvex(final boolean convex) {
+        dirtyBits |= OVERRIDE_CONVEX;
+        convexFlag = convex;
+    }
+    /**
+     * Clears the {@link #isConvex()} override done by {@link #setOverrideConvex(boolean)}
+     * @see #setOverrideConvex(boolean)
+     * @see #isConvex()
+     */
+    public void clearOverrideConvex() {
+        dirtyBits &= ~OVERRIDE_CONVEX;
+        dirtyBits |= DIRTY_CONVEX;
+    }
+
+    /**
      * Add a new empty {@link Outline}
      * to the end of this shape's outline list.
      * <p>If the {@link #getLastOutline()} is empty already, no new one will be added.</p>
@@ -308,7 +360,7 @@ public final class OutlineShape implements Comparable<OutlineShape> {
                     bbox.resize(outline.getBounds());
                 }
                 // vertices.addAll(outline.getVertices()); // FIXME: can do and remove DIRTY_VERTICES ?
-                dirtyBits |= DIRTY_TRIANGLES | DIRTY_VERTICES;
+                dirtyBits |= DIRTY_TRIANGLES | DIRTY_VERTICES | DIRTY_CONVEX;
                 return;
             }
         }
@@ -316,7 +368,7 @@ public final class OutlineShape implements Comparable<OutlineShape> {
         if( 0 == ( dirtyBits & DIRTY_BOUNDS ) ) {
             bbox.resize(outline.getBounds());
         }
-        dirtyBits |= DIRTY_TRIANGLES | DIRTY_VERTICES;
+        dirtyBits |= DIRTY_TRIANGLES | DIRTY_VERTICES | DIRTY_CONVEX;
     }
 
     /**
@@ -351,7 +403,7 @@ public final class OutlineShape implements Comparable<OutlineShape> {
             throw new NullPointerException("outline is null");
         }
         outlines.set(position, outline);
-        dirtyBits |= DIRTY_BOUNDS | DIRTY_TRIANGLES | DIRTY_VERTICES;
+        dirtyBits |= DIRTY_BOUNDS | DIRTY_TRIANGLES | DIRTY_VERTICES | DIRTY_CONVEX;
     }
 
     /**
@@ -362,7 +414,7 @@ public final class OutlineShape implements Comparable<OutlineShape> {
      * @throws IndexOutOfBoundsException if position is out of range (position < 0 || position >= getOutlineNumber())
      */
     public final Outline removeOutline(final int position) throws IndexOutOfBoundsException {
-        dirtyBits |= DIRTY_BOUNDS | DIRTY_TRIANGLES | DIRTY_VERTICES;
+        dirtyBits |= DIRTY_BOUNDS | DIRTY_TRIANGLES | DIRTY_VERTICES | DIRTY_CONVEX;
         return outlines.remove(position);
     }
 
@@ -396,7 +448,7 @@ public final class OutlineShape implements Comparable<OutlineShape> {
             bbox.resize(v.getCoord());
         }
         // vertices.add(v); // FIXME: can do and remove DIRTY_VERTICES ?
-        dirtyBits |= DIRTY_TRIANGLES | DIRTY_VERTICES;
+        dirtyBits |= DIRTY_TRIANGLES | DIRTY_VERTICES | DIRTY_CONVEX;
     }
 
     /**
@@ -412,7 +464,7 @@ public final class OutlineShape implements Comparable<OutlineShape> {
         if( 0 == ( dirtyBits & DIRTY_BOUNDS ) ) {
             bbox.resize(v.getCoord());
         }
-        dirtyBits |= DIRTY_TRIANGLES | DIRTY_VERTICES;
+        dirtyBits |= DIRTY_TRIANGLES | DIRTY_VERTICES | DIRTY_CONVEX;
     }
 
     /**
@@ -516,7 +568,7 @@ public final class OutlineShape implements Comparable<OutlineShape> {
      */
     public final void closeLastOutline(final boolean closeTail) {
         if( getLastOutline().setClosed( closeTail ) ) {
-            dirtyBits |= DIRTY_TRIANGLES | DIRTY_VERTICES;
+            dirtyBits |= DIRTY_TRIANGLES | DIRTY_VERTICES | DIRTY_CONVEX;
         }
     }
 
@@ -956,6 +1008,9 @@ public final class OutlineShape implements Comparable<OutlineShape> {
         return vertices;
     }
 
+    public static void printPerf(final PrintStream out) {
+        // jogamp.graph.curve.tess.Loop.printPerf(out);
+    }
     private void triangulateImpl() {
         if( 0 < outlines.size() ) {
             sortOutlines();
@@ -963,6 +1018,7 @@ public final class OutlineShape implements Comparable<OutlineShape> {
 
             triangles.clear();
             final Triangulator triangulator2d = Triangulation.create();
+            triangulator2d.setConvexShape( isConvex() );
             for(int index = 0; index<outlines.size(); index++) {
                 triangulator2d.addCurve(triangles, outlines.get(index), sharpness);
             }
@@ -997,6 +1053,12 @@ public final class OutlineShape implements Comparable<OutlineShape> {
         }
         if(Region.DEBUG_INSTANCE) {
             System.err.println("OutlineShape.getTriangles().X: "+triangles.size()+", updated "+updated);
+            if( updated ) {
+                int i=0;
+                for(final Triangle t : triangles) {
+                    System.err.printf("- [%d]: %s%n", i++, t);
+                }
+            }
         }
         return triangles;
     }
@@ -1117,5 +1179,4 @@ public final class OutlineShape implements Comparable<OutlineShape> {
             }
         }
     }
-
 }
diff --git a/src/jogl/classes/com/jogamp/graph/curve/tess/Triangulator.java b/src/jogl/classes/com/jogamp/graph/curve/tess/Triangulator.java
index 20fe9bfd9..eaebde076 100644
--- a/src/jogl/classes/com/jogamp/graph/curve/tess/Triangulator.java
+++ b/src/jogl/classes/com/jogamp/graph/curve/tess/Triangulator.java
@@ -49,6 +49,9 @@ import com.jogamp.graph.geom.Triangle;
  */
 public interface Triangulator {
 
+    /** Mark the to be triangulated shape convex or non-convex, causing further processing costs if non-convex like intersection tests. Default is assuming a convex shape. */
+    public void setConvexShape(boolean convex);
+
     /**
      * Add a curve to the list of Outlines
      * describing the shape
diff --git a/src/jogl/classes/com/jogamp/graph/geom/Outline.java b/src/jogl/classes/com/jogamp/graph/geom/Outline.java
index 1b36bfc24..8c39004a0 100644
--- a/src/jogl/classes/com/jogamp/graph/geom/Outline.java
+++ b/src/jogl/classes/com/jogamp/graph/geom/Outline.java
@@ -1,5 +1,5 @@
 /**
- * Copyright 2010-2023 JogAmp Community. All rights reserved.
+ * Copyright 2010-2024 JogAmp Community. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without modification, are
  * permitted provided that the following conditions are met:
@@ -57,7 +57,11 @@ public class Outline implements Comparable<Outline> {
     private final AABBox bbox;
     private boolean dirtyBBox;
     private Winding winding;
-    private boolean dirtyWinding;
+    private boolean convexFlag;
+    private int dirtyBits;
+
+    private static final int DIRTY_WINDING = 1 << 0;
+    private static final int DIRTY_CONVEX  = 1 << 0;
 
     /**Create an outline defined by control vertices.
      * An outline can contain off Curve vertices which define curved
@@ -69,7 +73,8 @@ public class Outline implements Comparable<Outline> {
         bbox = new AABBox();
         dirtyBBox = false;
         winding = Winding.CCW;
-        dirtyWinding = false;
+        convexFlag = false;
+        dirtyBits = 0;
     }
 
     /**
@@ -79,7 +84,8 @@ public class Outline implements Comparable<Outline> {
         final int count = src.vertices.size();
         vertices = new ArrayList<Vertex>(count);
         winding = Winding.CCW;
-        dirtyWinding = true;
+        convexFlag = false;
+        dirtyBits = DIRTY_WINDING | DIRTY_CONVEX;
         for(int i=0; i<count; i++) {
             vertices.add( src.vertices.get(i).copy() );
         }
@@ -99,9 +105,15 @@ public class Outline implements Comparable<Outline> {
     public Outline(final Outline src, final Winding enforce) {
         final int count = src.vertices.size();
         vertices = new ArrayList<Vertex>(count);
-        final Winding had_winding = src.getWinding();;
+        final Winding had_winding = src.getWinding();
         winding = had_winding;
-        dirtyWinding = false;
+        if( 0 == ( src.dirtyBits & DIRTY_CONVEX ) ) {
+            convexFlag = src.convexFlag;
+            dirtyBits = 0;
+        } else {
+            convexFlag = false;
+            dirtyBits = DIRTY_CONVEX;
+        }
         if( enforce != had_winding ) {
             for(int i=count-1; i>=0; --i) {
                 vertices.add( src.vertices.get(i).copy() );
@@ -138,11 +150,14 @@ public class Outline implements Comparable<Outline> {
     }
 
     /**
-     * Compute the winding of the {@link #getLastOutline()} using the {@link VectorUtil#area2d(ArrayList)} function over all of its vertices.
+     * Returns the cached or computed winding of this {@link Outline}s {@code polyline} using {@link VectorUtil#area(ArrayList)}.
+     * <p>
+     * The result is cached.
+     * </p>
      * @return {@link Winding#CCW} or {@link Winding#CW}
      */
     public final Winding getWinding() {
-        if( !dirtyWinding ) {
+        if( 0 == ( dirtyBits & DIRTY_WINDING ) ) {
             return winding;
         }
         final int count = getVertexCount();
@@ -151,10 +166,29 @@ public class Outline implements Comparable<Outline> {
         } else {
             winding = VectorUtil.getWinding( getVertices() );
         }
-        dirtyWinding = false;
+        dirtyBits &= ~DIRTY_WINDING;
         return winding;
     }
 
+    /**
+     * Returns the cached or computed result whether this {@link Outline}s {@code polyline} has a convex shape using {@link VectorUtil#isConvex(ArrayList, boolean)}.
+     * <p>
+     * A polyline with less than 3 elements is marked convex for simplicity,
+     * since a non-convex complex shape may need to pass intersection testing within triangulation.
+     * </p>
+     * <p>
+     * The result is cached.
+     * </p>
+     */
+    public boolean isConvex() {
+        if( 0 == ( dirtyBits & DIRTY_CONVEX ) ) {
+            return convexFlag;
+        }
+        convexFlag = VectorUtil.isConvex1( getVertices(), true );
+        dirtyBits &= ~DIRTY_CONVEX;
+        return convexFlag;
+    }
+
     public final int getVertexCount() {
         return vertices.size();
     }
@@ -183,7 +217,7 @@ public class Outline implements Comparable<Outline> {
         if(!dirtyBBox) {
             bbox.resize(vertex.getCoord());
         }
-        dirtyWinding = true;
+        dirtyBits |= DIRTY_WINDING | DIRTY_CONVEX;
     }
 
     /** Replaces the {@link Vertex} element at the given {@code position}.
@@ -200,7 +234,7 @@ public class Outline implements Comparable<Outline> {
         }
         vertices.set(position, vertex);
         dirtyBBox = true;
-        dirtyWinding = true;
+        dirtyBits |= DIRTY_WINDING | DIRTY_CONVEX;
     }
 
     public final Vertex getVertex(final int index){
@@ -219,7 +253,7 @@ public class Outline implements Comparable<Outline> {
      */
     public final Vertex removeVertex(final int position) throws IndexOutOfBoundsException {
         dirtyBBox = true;
-        dirtyWinding = true;
+        dirtyBits |= DIRTY_WINDING | DIRTY_CONVEX;
         return vertices.remove(position);
     }
 
@@ -372,5 +406,4 @@ public class Outline implements Comparable<Outline> {
             out.printf("- OL[%d]: %s%n", vi, v);
         }
     }
-
 }
diff --git a/src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java b/src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java
index 1c2f0b323..d0e0fecf6 100644
--- a/src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java
+++ b/src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java
@@ -1,5 +1,5 @@
 /**
- * Copyright 2010-2023 JogAmp Community. All rights reserved.
+ * Copyright 2010-2024 JogAmp Community. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without modification, are
  * permitted provided that the following conditions are met:
@@ -56,6 +56,7 @@ public class CDTriangulator2D implements Triangulator {
 
     private final ArrayList<Loop> loops = new ArrayList<Loop>();
 
+    private boolean convexFlag;
     private int addedVerticeCount;
     private int maxTriID;
 
@@ -63,10 +64,16 @@ public class CDTriangulator2D implements Triangulator {
     /** Constructor for a new Delaunay triangulator
      */
     public CDTriangulator2D() {
+        convexFlag = true;
         reset();
     }
 
     @Override
+    public void setConvexShape(final boolean convex) {
+        convexFlag = convex;
+    }
+
+    @Override
     public final void reset() {
         maxTriID = 0;
         addedVerticeCount = 0;
@@ -87,8 +94,6 @@ public class CDTriangulator2D implements Triangulator {
 
         if( null == loop ) {
             // HEdge.BOUNDARY -> Winding.CCW
-            final int edgeType = HEdge.BOUNDARY;
-            final boolean hole = false;
             if( !FixedWindingRule ) {
                 final Winding winding = polyline.getWinding();
                 if( Winding.CCW != winding ) {
@@ -98,10 +103,10 @@ public class CDTriangulator2D implements Triangulator {
                 }
             }
             final GraphOutline outline = new GraphOutline(polyline);
-            final GraphOutline innerPoly = extractBoundaryTriangles(sink, outline, hole, sharpness);
+            final GraphOutline innerPoly = extractBoundaryTriangles(sink, outline, false /* hole */, sharpness);
             // vertices.addAll(polyline.getVertices());
             if( innerPoly.getGraphPoint().size() >= 3 ) {
-                loop = Loop.create(innerPoly, edgeType);
+                loop = Loop.createBoundary(innerPoly, convexFlag);
                 if( null != loop ) {
                     loops.add(loop);
                 }
@@ -133,24 +138,23 @@ public class CDTriangulator2D implements Triangulator {
                 Thread.dumpStack();
             }
         } else {
-            final int edgeType = HEdge.HOLE;
-            final boolean hole = true;
             // HEdge.HOLE -> Winding.CW, but Winding.CCW is also accepted!
             // Winding.CW not required, handled in Loop.initFromPolyline(): polyline.setWinding(winding);
             final GraphOutline outline = new GraphOutline(polyline);
-            final GraphOutline innerPoly = extractBoundaryTriangles(sink, outline, hole, sharpness);
+            final GraphOutline innerPoly = extractBoundaryTriangles(sink, outline, true /* hole */, sharpness);
             // vertices.addAll(innerPoly.getVertices());
-            loop.addConstraintCurve(innerPoly, edgeType);
+            loop.addConstraintCurveHole(innerPoly);
         }
     }
 
     @Override
     public final void generate(final List<Triangle> sink) {
         final int loopsSize = loops.size();
+        int size;
         for(int i=0;i<loopsSize;i++) {
             final Loop loop = loops.get(i);
             int numTries = 0;
-            int size = loop.computeLoopSize();
+            size = loop.computeLoopSize();
             while(!loop.isSimplex()){
                 final Triangle tri;
                 final boolean delaunay;
@@ -181,9 +185,10 @@ public class CDTriangulator2D implements Triangulator {
             }
             final Triangle tri = loop.cut(true);
             if(tri != null) {
+                tri.setId(maxTriID++);
                 sink.add(tri);
                 if(DEBUG){
-                    System.err.println("CDTri.gen["+i+"].1: "+tri);
+                    System.err.println("CDTri.gen["+i+"].1: size "+size+"/"+loopsSize+", "+tri);
                 }
             }
         }
diff --git a/src/jogl/classes/jogamp/graph/curve/tess/Loop.java b/src/jogl/classes/jogamp/graph/curve/tess/Loop.java
index 807a07b67..6f6b81a2f 100644
--- a/src/jogl/classes/jogamp/graph/curve/tess/Loop.java
+++ b/src/jogl/classes/jogamp/graph/curve/tess/Loop.java
@@ -1,5 +1,5 @@
 /**
- * Copyright 2010-2023 JogAmp Community. All rights reserved.
+ * Copyright 2010-2024 JogAmp Community. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without modification, are
  * permitted provided that the following conditions are met:
@@ -28,31 +28,31 @@
 package jogamp.graph.curve.tess;
 
 import java.util.ArrayList;
-
+import java.util.List;
 
 import com.jogamp.graph.geom.Vertex;
-import com.jogamp.math.Vec3f;
 import com.jogamp.math.VectorUtil;
 import com.jogamp.math.geom.AABBox;
 import com.jogamp.math.geom.plane.Winding;
 import com.jogamp.graph.geom.Triangle;
 
 public class Loop {
-    private HEdge root = null;
     private final AABBox box = new AABBox();
-    private GraphOutline initialOutline = null;
-
-    private Loop(final GraphOutline polyline, final int edgeType){
-        initialOutline = polyline;
+    private final GraphOutline initialOutline;
+    private final boolean isConvex;
+    private HEdge root;
+    private final List<GraphOutline> outlines = new ArrayList<GraphOutline>();
+
+    private Loop(final GraphOutline polyline, final int edgeType, final boolean isConvex){
+        this.initialOutline = polyline;
+        this.isConvex = isConvex;
         this.root = initFromPolyline(initialOutline, edgeType);
     }
 
-    public static Loop create(final GraphOutline polyline, final int edgeType) {
-        final Loop res = new Loop(polyline, edgeType);
+    public static Loop createBoundary(final GraphOutline polyline, final boolean isConvex) {
+        final Loop res = new Loop(polyline, HEdge.BOUNDARY, isConvex);
         if( null == res.root ) {
             return null;
-        } else if( HEdge.HOLE == edgeType ) {
-            res.addConstraintCurveImpl(polyline);
         }
         return res;
     }
@@ -61,48 +61,6 @@ public class Loop {
         return root;
     }
 
-    public Triangle cut(final boolean delaunay){
-        if(isSimplex()){
-            return new Triangle(root.getGraphPoint().getPoint(), root.getNext().getGraphPoint().getPoint(),
-                                root.getNext().getNext().getGraphPoint().getPoint(), checkVerticesBoundary(root));
-        }
-        final HEdge prev = root.getPrev();
-        final HEdge next1 = root.getNext();
-
-        final HEdge next2;
-        if( CDTriangulator2D.DEBUG ) {
-            next2 = isValidNeighborDbg(next1.getNext(), delaunay);
-        } else {
-            next2 = isValidNeighbor(next1.getNext(), delaunay);
-        }
-        if(next2 == null){
-            root = root.getNext();
-            return null;
-        }
-
-        final GraphVertex v1 = root.getGraphPoint();
-        final GraphVertex v2 = next1.getGraphPoint();
-        final GraphVertex v3 = next2.getGraphPoint();
-
-        final HEdge v3Edge = new HEdge(v3, HEdge.INNER);
-
-        HEdge.connect(v3Edge, root);
-        HEdge.connect(next1, v3Edge);
-
-        HEdge v3EdgeSib = v3Edge.getSibling();
-        if(v3EdgeSib == null){
-            v3EdgeSib = new HEdge(v3Edge.getNext().getGraphPoint(), HEdge.INNER);
-            HEdge.makeSiblings(v3Edge, v3EdgeSib);
-        }
-
-        HEdge.connect(prev, v3EdgeSib);
-        HEdge.connect(v3EdgeSib, next2);
-
-        final Triangle t = createTriangle(v1.getPoint(), v2.getPoint(), v3.getPoint(), root);
-        this.root = next2;
-        return t;
-    }
-
     public boolean isSimplex(){
         return (root.getNext().getNext().getNext() == root);
     }
@@ -113,6 +71,7 @@ public class Loop {
      * @param edgeType either {@link HEdge#BOUNDARY} requiring {@link Winding#CCW} or {@link HEdge#HOLE} using {@link Winding#CW} or even {@link Winding#CCW}
      */
     private HEdge initFromPolyline(final GraphOutline outline, final int edgeType) {
+        outlines.add(outline);
         final ArrayList<GraphVertex> vertices = outline.getGraphPoint();
 
         if(vertices.size()<3) {
@@ -182,17 +141,12 @@ public class Loop {
         return firstEdge;
     }
 
-    public void addConstraintCurve(final GraphOutline polyline, final int edgeType) {
+    public void addConstraintCurveHole(final GraphOutline polyline) {
         //        GraphOutline outline = new GraphOutline(polyline);
         /**needed to generate vertex references.*/
-        if( null == initFromPolyline(polyline, edgeType) ) { // 'usually' HEdge.HOLE
+        if( null == initFromPolyline(polyline, HEdge.HOLE) ) {
             return;
         }
-        if( HEdge.HOLE == edgeType ) {
-            addConstraintCurveImpl(polyline);
-        }
-    }
-    private void addConstraintCurveImpl(final GraphOutline polyline) {
         final GraphVertex v3 = locateClosestVertex(polyline);
         if( null == v3 ) {
             System.err.println( "Graph: Loop.locateClosestVertex returns null; root valid? "+(null!=root));
@@ -225,60 +179,240 @@ public class Loop {
      * @return the vertex that is closest to the newly set root Hedge.
      */
     private GraphVertex locateClosestVertex(final GraphOutline polyline) {
-        HEdge closestE = null;
-        GraphVertex closestV = null;
-
-        // final Winding winding = polyline.getOutline().getWinding();
-        // final Winding winding = getWinding( vertices ); // requires area-winding detection
-
         float minDistance = Float.MAX_VALUE;
         final ArrayList<GraphVertex> initVertices = initialOutline.getGraphPoint();
+        if( initVertices.size() < 2 ) {
+            return null;
+        }
         final ArrayList<GraphVertex> vertices = polyline.getGraphPoint();
+        HEdge closestE = null;
+        GraphVertex closestV = null;
 
-        for(int i=0; i< initVertices.size()-1; i++){
-            final GraphVertex v = initVertices.get(i);
-            final GraphVertex nextV = initVertices.get(i+1);
+        final int initSz = initVertices.size();
+        GraphVertex v0 = initVertices.get(0);
+        for(int i=1; i< initSz; i++){
+            final GraphVertex v1 = initVertices.get(i);
             for(int pos=0; pos<vertices.size(); pos++) {
                 final GraphVertex cand = vertices.get(pos);
-                final float distance = v.getCoord().dist( cand.getCoord() );
+                final float distance = v0.getCoord().dist( cand.getCoord() );
                 if(distance < minDistance){
                     boolean inside = false;
                     for (final GraphVertex vert:vertices){
-                        if(vert == v || vert == nextV || vert == cand) {
-                            continue;
-                        }
-                        inside = VectorUtil.isInCircleVec2d(v.getPoint(), nextV.getPoint(), cand.getPoint(), vert.getPoint());
-                        if(inside){
-                            break;
+                        if( !( vert == v0 || vert == v1 || vert == cand) ) {
+                            inside = VectorUtil.isInCircle(v0.getPoint(), v1.getPoint(), cand.getPoint(), vert.getPoint());
+                            if(inside){
+                                break;
+                            }
                         }
                     }
                     if(!inside){
                         closestV = cand;
                         minDistance = distance;
-                        closestE = v.findBoundEdge();
+                        closestE = v0.findBoundEdge();
                     }
                 }
-
             }
+            v0 = v1;
         }
-
         if(closestE != null){
             root = closestE;
         }
-
         return closestV;
     }
 
+    /**
+    public static void printPerf(final PrintStream out) {
+        out.printf("Graph.Intersection: cut[count %,d, td %,f ms], isect[count %,d, td %,f ms], isec/cut[count %f, td %f]%n",
+                   perf_cut_count, perf_cut_td_ns/1000000.0, perf_isect_count, perf_isect_td_ns/1000000.0,
+                   (double)perf_isect_count/(double)perf_cut_count, (double)perf_isect_td_ns/(double)perf_cut_td_ns);
+    }
+    private static long perf_isect_td_ns = 0;
+    private static long perf_isect_count = 0;
+    private static long perf_cut_td_ns = 0;
+    private static long perf_cut_count = 0;
+    */
+    public final Triangle cut(final boolean delaunay){
+        if( !CDTriangulator2D.DEBUG ) {
+            // final long t0 = Clock.currentNanos();
+            return cut0(delaunay);
+            // perf_cut_td_ns += Clock.currentNanos() - t0;
+            // perf_cut_count++;
+        } else {
+            return cutDbg(delaunay);
+        }
+    }
+    private final Triangle cut0(final boolean delaunay){
+        final HEdge next1 = root.getNext();
+        if(isSimplex()){
+            final Vertex rootPoint = root.getGraphPoint().getPoint();
+            final Vertex nextPoint = next1.getGraphPoint().getPoint();
+            final Vertex candPoint = next1.getNext().getGraphPoint().getPoint();
+            if( !isConvex && intersectsOutline(rootPoint, nextPoint, candPoint) ) {
+                return null;
+            }
+            return new Triangle(rootPoint, nextPoint, candPoint, checkVerticesBoundary(root));
+        }
+        final HEdge prev = root.getPrev();
+
+        final HEdge next2 = isValidNeighbor(next1.getNext(), delaunay);
+        if(next2 == null){
+            root = root.getNext();
+            return null;
+        }
+
+        final GraphVertex v1 = root.getGraphPoint();
+        final GraphVertex v2 = next1.getGraphPoint();
+        final GraphVertex v3 = next2.getGraphPoint();
+
+        final HEdge v3Edge = new HEdge(v3, HEdge.INNER);
+
+        HEdge.connect(v3Edge, root);
+        HEdge.connect(next1, v3Edge);
+
+        HEdge v3EdgeSib = v3Edge.getSibling();
+        if(v3EdgeSib == null){
+            v3EdgeSib = new HEdge(v3Edge.getNext().getGraphPoint(), HEdge.INNER);
+            HEdge.makeSiblings(v3Edge, v3EdgeSib);
+        }
+
+        HEdge.connect(prev, v3EdgeSib);
+        HEdge.connect(v3EdgeSib, next2);
+
+        final Triangle t = createTriangle(v1.getPoint(), v2.getPoint(), v3.getPoint(), root);
+        this.root = next2;
+        return t;
+    }
+    private final Triangle cutDbg(final boolean delaunay){
+        final HEdge next1 = root.getNext();
+        if(isSimplex()){
+            final Vertex rootPoint = root.getGraphPoint().getPoint();
+            final Vertex nextPoint = next1.getGraphPoint().getPoint();
+            final Vertex candPoint = next1.getNext().getGraphPoint().getPoint();
+            if( !isConvex && intersectsOutlineDbg(rootPoint, nextPoint, candPoint) ) {
+                System.err.printf("Loop.cut.X0: last-simplex intersects%n");
+                return null;
+            }
+            final Triangle tri = new Triangle(rootPoint, nextPoint, candPoint, checkVerticesBoundary(root));
+            System.err.printf("Loop.cut.X1: last-simplex %s%n", tri);
+            return tri;
+        }
+        final HEdge prev = root.getPrev();
+
+        final HEdge next2 = isValidNeighborDbg(next1.getNext(), delaunay);
+        if(next2 == null){
+            root = root.getNext();
+            System.err.printf("Loop.cut.0: null-cut %s%n", next1.getNext().getGraphPoint());
+            return null;
+        }
+
+        final GraphVertex v1 = root.getGraphPoint();
+        final GraphVertex v2 = next1.getGraphPoint();
+        final GraphVertex v3 = next2.getGraphPoint();
+
+        final HEdge v3Edge = new HEdge(v3, HEdge.INNER);
+
+        HEdge.connect(v3Edge, root);
+        HEdge.connect(next1, v3Edge);
+
+        HEdge v3EdgeSib = v3Edge.getSibling();
+        if(v3EdgeSib == null){
+            v3EdgeSib = new HEdge(v3Edge.getNext().getGraphPoint(), HEdge.INNER);
+            HEdge.makeSiblings(v3Edge, v3EdgeSib);
+        }
+
+        HEdge.connect(prev, v3EdgeSib);
+        HEdge.connect(v3EdgeSib, next2);
+
+        final Triangle t = createTriangle(v1.getPoint(), v2.getPoint(), v3.getPoint(), root);
+        this.root = next2;
+        System.err.printf("Loop.cut.1: new-cut %s -> %s%n", next2.getGraphPoint(), t);
+        return t;
+    }
+
+    private boolean intersectsOutline(final Vertex a1, final Vertex a2, final Vertex b) {
+        // final long t0 = Clock.currentNanos();
+        for(final GraphOutline outline : outlines) {
+            if( intersectsOutline(outline, a1, a2, b) ) {
+                // perf_isect_td_ns += Clock.currentNanos() - t0;
+                // perf_isect_count++;
+                return true;
+            }
+        }
+        // perf_isect_td_ns += Clock.currentNanos() - t0;
+        // perf_isect_count++;
+        return false;
+    }
+    private boolean intersectsOutline(final GraphOutline outline, final Vertex a1, final Vertex a2, final Vertex b) {
+        final ArrayList<GraphVertex> vertices = outline.getGraphPoint();
+        if( vertices.size() < 2 ) {
+            return false;
+        }
+        final int sz = vertices.size();
+        Vertex v0 = vertices.get(0).getPoint();
+        for(int i=1; i< sz; i++){
+            final Vertex v1 = vertices.get(i).getPoint();
+            if( !( v0 == b || v1 == b ) ) {
+                if( !( v0 == a1 || v1 == a1 ) &&
+                    VectorUtil.testSeg2SegIntersection(a1, b, v0, v1) ) {
+                    return true;
+                }
+                if( !( v0 == a2 || v1 == a2 ) &&
+                    VectorUtil.testSeg2SegIntersection(a2, b, v0, v1) ) {
+                    return true;
+                }
+            }
+            v0 = v1;
+        }
+        return false;
+    }
+    private boolean intersectsOutlineDbg(final Vertex a1, final Vertex a2, final Vertex b) {
+        for(final GraphOutline outline : outlines) {
+            if( intersectsOutlineDbg(outline, a1, a2, b) ) {
+                return true;
+            }
+        }
+        return false;
+    }
+    private boolean intersectsOutlineDbg(final GraphOutline outline, final Vertex a1, final Vertex a2, final Vertex b) {
+        final ArrayList<GraphVertex> vertices = outline.getGraphPoint();
+        if( vertices.size() < 2 ) {
+            return false;
+        }
+        final int sz = vertices.size();
+        Vertex v0 = vertices.get(0).getPoint();
+        for(int i=1; i< sz; i++){
+            final Vertex v1 = vertices.get(i).getPoint();
+            if( !( v0 == b || v1 == b ) ) {
+                if( !( v0 == a1 || v1 == a1 ) &&
+                    VectorUtil.testSeg2SegIntersection(a1, b, v0, v1) ) {
+                    System.err.printf("Loop.intersection.b-a1.1: %d/%d %s to%n-a1 %s, with%n-v0 %s%n-v1 %s%n", i, sz-1, b, a1, v0, v1);
+                    return true;
+                }
+                if( !( v0 == a2 || v1 == a2 ) &&
+                    VectorUtil.testSeg2SegIntersection(a2, b, v0, v1) ) {
+                    System.err.printf("Loop.intersection.b-a2.1: %d/%d %s to%n-a2 %s, with%n-v0 %s%n-v1 %s%n", i, sz-1, b, a2, v0, v1);
+                    return true;
+                }
+            }
+            v0 = v1;
+        }
+        return false;
+    }
+
     private HEdge isValidNeighbor(final HEdge candEdge, final boolean delaunay) {
         final HEdge next = root.getNext();
-        if( !VectorUtil.isCCW( root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(),
-                               candEdge.getGraphPoint().getPoint()) ) {
+        final Vertex rootPoint = root.getGraphPoint().getPoint();
+        final Vertex nextPoint = next.getGraphPoint().getPoint();
+        final Vertex candPoint = candEdge.getGraphPoint().getPoint();
+        if( !VectorUtil.isCCW( rootPoint, nextPoint, candPoint) ) {
+            return null;
+        }
+        if( !isConvex && intersectsOutline(rootPoint, nextPoint, candPoint) ) {
             return null;
         }
         if( !delaunay ) {
             return candEdge;
         }
-        final Vertex candPoint = candEdge.getGraphPoint().getPoint();
         HEdge e = candEdge.getNext();
         while (e != candEdge){
             final GraphVertex egp = e.getGraphPoint();
@@ -286,8 +420,7 @@ public class Loop {
                egp != next.getGraphPoint() &&
                egp.getPoint() != candPoint )
             {
-                if( VectorUtil.isInCircleVec2d(root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(),
-                                               candPoint, egp.getPoint()) ) {
+                if( VectorUtil.isInCircle(rootPoint, nextPoint, candPoint, egp.getPoint()) ) {
                     return null;
                 }
             }
@@ -297,14 +430,20 @@ public class Loop {
     }
     private HEdge isValidNeighborDbg(final HEdge candEdge, final boolean delaunay) {
         final HEdge next = root.getNext();
-        if( !VectorUtil.isCCW( root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(),
-                               candEdge.getGraphPoint().getPoint()) ) {
+        final Vertex rootPoint = root.getGraphPoint().getPoint();
+        final Vertex nextPoint = next.getGraphPoint().getPoint();
+        final Vertex candPoint = candEdge.getGraphPoint().getPoint();
+        if( !VectorUtil.isCCW( rootPoint, nextPoint, candPoint) ) {
+            System.err.printf("Loop.isInCircle.X: !CCW %s, of%n- %s%n- %s%n- %s%n",
+                    candPoint, rootPoint, nextPoint, candPoint);
+            return null;
+        }
+        if( !isConvex && intersectsOutlineDbg(rootPoint, nextPoint, candPoint) ) {
             return null;
         }
         if( !delaunay ) {
             return candEdge;
         }
-        final Vertex candPoint = candEdge.getGraphPoint().getPoint();
         HEdge e = candEdge.getNext();
         while (e != candEdge){
             final GraphVertex egp = e.getGraphPoint();
@@ -312,11 +451,10 @@ public class Loop {
                egp != next.getGraphPoint() &&
                egp.getPoint() != candPoint )
             {
-                final double v = VectorUtil.inCircleVec2dVal(root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(),
-                                                             candPoint, egp.getPoint());
+                final double v = VectorUtil.inCircleVal(rootPoint, nextPoint, candPoint, egp.getPoint());
                 if( v > VectorUtil.InCircleDThreshold ) {
                     System.err.printf("Loop.isInCircle.1: %30.30f: %s, of%n- %s%n- %s%n- %s%n",
-                            v, candPoint, root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(), egp.getPoint());
+                            v, candPoint, rootPoint, nextPoint, egp.getPoint());
                     return null;
                 }
                 System.err.printf("Loop.isInCircle.0: %30.30f: %s, of%n- %s%n- %s%n- %s%n",