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, 15 insertions, 5 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");
     }
 }