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

1 files changed, 16 insertions, 11 deletions

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);
                 }
             }
         }