From 949676fb8cac4d6aa626a375501e41a65a1a11fa Mon Sep 17 00:00:00 2001
From: Sven Göthel <sgothel@jausoft.com>
Date: Tue, 13 Feb 2024 23:03:01 +0100
Subject: 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
---
.../classes/com/jogamp/graph/geom/Outline.java | 59 +++++++++++++++++-----
1 file changed, 46 insertions(+), 13 deletions(-)
(limited to 'src/jogl/classes/com/jogamp/graph/geom/Outline.java')
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);
}
}
-
}
--
cgit v1.2.3