aboutsummaryrefslogtreecommitdiffstats
path: root/src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java
diff options
context:
space:
mode:
authorSven Göthel <[email protected]>2024-02-13 23:03:01 +0100
committerSven Göthel <[email protected]>2024-02-13 23:03:01 +0100
commit949676fb8cac4d6aa626a375501e41a65a1a11fa (patch)
treed472a4bbc06e9f019db7d3e5964feb780426110f /src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java
parent08f0d34424aab6a496a71fa5d83af6c407c7c569 (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.java27
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);
}
}
}