aboutsummaryrefslogtreecommitdiffstats
path: root/src/jogl/classes/com
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/com
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/com')
-rw-r--r--src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java87
-rw-r--r--src/jogl/classes/com/jogamp/graph/curve/tess/Triangulator.java3
-rw-r--r--src/jogl/classes/com/jogamp/graph/geom/Outline.java59
3 files changed, 123 insertions, 26 deletions
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);
}
}
-
}