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/com | |
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/com')
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); } } - } |