diff options
author | Sven Göthel <[email protected]> | 2024-02-13 23:03:01 +0100 |
---|---|---|
committer | Sven Göthel <[email protected]> | 2024-02-13 23:03:01 +0100 |
commit | 949676fb8cac4d6aa626a375501e41a65a1a11fa (patch) | |
tree | d472a4bbc06e9f019db7d3e5964feb780426110f /src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java | |
parent | 08f0d34424aab6a496a71fa5d83af6c407c7c569 (diff) |
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
Diffstat (limited to 'src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java')
-rw-r--r-- | src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java | 27 |
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); } } } |