From 949676fb8cac4d6aa626a375501e41a65a1a11fa Mon Sep 17 00:00:00 2001 From: Sven Göthel 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 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 --- .../jogamp/opengl/demos/graph/ui/FontView01.java | 20 +- .../com/jogamp/graph/curve/OutlineShape.java | 87 +++++- .../com/jogamp/graph/curve/tess/Triangulator.java | 3 + .../classes/com/jogamp/graph/geom/Outline.java | 59 +++- .../jogamp/graph/curve/tess/CDTriangulator2D.java | 27 +- src/jogl/classes/jogamp/graph/curve/tess/Loop.java | 322 +++++++++++++++------ 6 files changed, 384 insertions(+), 134 deletions(-) diff --git a/src/demos/com/jogamp/opengl/demos/graph/ui/FontView01.java b/src/demos/com/jogamp/opengl/demos/graph/ui/FontView01.java index 9a143a29d..2035c39cc 100644 --- a/src/demos/com/jogamp/opengl/demos/graph/ui/FontView01.java +++ b/src/demos/com/jogamp/opengl/demos/graph/ui/FontView01.java @@ -99,7 +99,8 @@ import com.jogamp.opengl.util.Animator; public class FontView01 { private static final float GlyphGridWidth = 3/4f; // FBO AA: 3/4f = 0.75f dropped fine grid lines @ 0.2f thickness; 0.70f OK private static final float GlyphGridBorderThickness = 0.02f; // thickness 0.2f dropping - private static final Vec4f GlyphGridBorderColor = new Vec4f(0.2f, 0.2f, 0.2f, 1); + private static final Vec4f GlyphGridBorderColorConvex = new Vec4f(0.2f, 0.2f, 0.7f, 1); + private static final Vec4f GlyphGridBorderColorComplex = new Vec4f(0.2f, 0.2f, 0.2f, 1); // static CommandlineOptions options = new CommandlineOptions(1280, 720, Region.MSAA_RENDERING_BIT, Region.DEFAULT_AA_QUALITY, 4); // static CommandlineOptions options = new CommandlineOptions(1280, 720, Region.VBAA_RENDERING_BIT); @@ -420,6 +421,7 @@ public class FontView01 { } printScreenOnGLThread(scene, window.getChosenGLCapabilities(), font, gridDim.contourChars.get(0)); // stay open .. + OutlineShape.printPerf(System.err); } static void printScreenOnGLThread(final Scene scene, final GLCapabilitiesImmutable caps, final Font font, final int codepoint) { @@ -435,6 +437,7 @@ public class FontView01 { final int rows; final int rowsPerPage; final int elemCount; + int convexGlyphCount; int maxNameLen; public GridDim(final Font font, final int columns, final int rowsPerPage, final int xReserved) { @@ -453,11 +456,15 @@ public class FontView01 { private int scanContourGlyphs(final Font font) { final long t0 = Clock.currentNanos(); contourChars.clear(); + convexGlyphCount = 0; maxNameLen = 1; final int[] max = { max_glyph_count }; font.forAllGlyphs((final Glyph fg) -> { if( !fg.isNonContour() && max[0]-- > 0 ) { contourChars.add( fg.getCodepoint() ); + if( null != fg.getShape() && fg.getShape().isConvex() ) { + ++convexGlyphCount; + } maxNameLen = Math.max(maxNameLen, fg.getName().length()); } }); @@ -468,7 +475,7 @@ public class FontView01 { return contourChars.size(); } @Override - public String toString() { return "GridDim[contours "+glyphCount+", "+columns+"x"+rows+"="+(columns*rows)+">="+elemCount+", rows/pg "+rowsPerPage+"]"; } + public String toString() { return "GridDim[contours "+glyphCount+", convex "+convexGlyphCount+" ("+((float)convexGlyphCount/(float)glyphCount)*100+"%), "+columns+"x"+rows+"="+(columns*rows)+">="+elemCount+", rows/pg "+rowsPerPage+"]"; } } static Group getGlyphShapeHolder(final Shape shape0) { @@ -498,6 +505,7 @@ public class FontView01 { for(int idx = 0; idx < gridDim.glyphCount; ++idx) { final char codepoint = gridDim.contourChars.get(idx); final Font.Glyph fg = font.getGlyph(codepoint); + final boolean isConvex = null != fg.getShape() ? fg.getShape().isConvex() : true; final GlyphShape g = new GlyphShape(options.renderModes, fg, 0, 0); g.setColor(0.1f, 0.1f, 0.1f, 1).setName("GlyphShape"); @@ -511,7 +519,8 @@ public class FontView01 { final AABBox gbox = fg.getBounds(tmpBox); // g.getBounds(glp); final boolean addUnderline = showUnderline && gbox.getMinY() < 0f; final Group c1 = new Group( new BoxLayout( 1f, 1f, addUnderline ? Alignment.None : Alignment.Center) ); - c1.setBorder(GlyphGridBorderThickness).setBorderColor(GlyphGridBorderColor).setInteractive(true).setDragAndResizable(false).setName("GlyphHolder2"); + c1.setBorder(GlyphGridBorderThickness).setBorderColor(isConvex ? GlyphGridBorderColorConvex : GlyphGridBorderColorComplex) + .setInteractive(true).setDragAndResizable(false).setName("GlyphHolder2"); if( addUnderline ) { final Shape underline = new Rectangle(options.renderModes, 1f, gbox.getMinY(), 0.01f).setInteractive(false).setColor(0f, 0f, 1f, 0.25f); c1.addShape(underline); @@ -565,11 +574,12 @@ public class FontView01 { static String getGlyphInfo(final Font.Glyph g) { final OutlineShape os = g.getShape(); + final boolean isConvex = null != os ? os.isConvex() : true; final int osVertices = null != os ? os.getVertexCount() : 0; final String name_s = null != g.getName() ? g.getName() : ""; final AABBox bounds = g.getBounds(); final String box_s = String.format("Box %+.3f/%+.3f%n %+.3f/%+.3f", bounds.getLow().x(), bounds.getLow().y(), bounds.getHigh().x(), bounds.getHigh().y()); - return String.format((Locale)null, "%s%nHeight: %1.3f%nLine Height: %1.3f%n%nSymbol: %04x, id %04x%nName: '%s'%nDim %1.3f x %1.3f%n%s%nAdvance %1.3f%nLS Bearings: %1.3f%nVertices: %03d", + return String.format((Locale)null, "%s%nHeight: %1.3f%nLine Height: %1.3f%n%nSymbol: %04x, id %04x%nName: '%s'%nDim %1.3f x %1.3f%n%s%nAdvance %1.3f%nLS Bearings: %1.3f%nVertices: %03d%n%s", g.getFont().getFullFamilyName(), g.getFont().getMetrics().getAscent() - g.getFont().getMetrics().getDescent(), // font hhea table g.getFont().getLineHeight(), // font hhea table @@ -577,6 +587,6 @@ public class FontView01 { bounds.getWidth(), bounds.getHeight(), box_s, g.getAdvanceWidth(), g.getLeftSideBearings(), - osVertices); + osVertices, isConvex?"Convex":"Non-Convex"); } } 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 { /** 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 { private final ArrayList triangles; private final ArrayList vertices; private int addedVerticeCount; + private boolean convexFlag; private VerticesState outlineState; @@ -181,6 +187,7 @@ public final class OutlineShape implements Comparable { this.triangles = new ArrayList(); this.vertices = new ArrayList(); this.addedVerticeCount = 0; + this.convexFlag = true; this.dirtyBits = 0; this.sharpness = DEFAULT_SHARPNESS; } @@ -214,6 +221,7 @@ public final class OutlineShape implements Comparable { vertices.clear(); triangles.clear(); addedVerticeCount = 0; + convexFlag = true; dirtyBits = 0; } @@ -221,7 +229,7 @@ public final class OutlineShape implements Comparable { 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. */ @@ -253,6 +261,50 @@ public final class OutlineShape implements Comparable { getLastOutline().setWinding(enforced); } + /** + * Returns cached or computed result whether all {@code polyline}s of {@link #getOutline(int)} are of convex shape, see {@link Outline#isConvex()}. + *

+ * 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. + *

+ *

+ * The result is cached. + *

+ * @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 { 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 { 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 { 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 { * @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 { 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 { 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 { */ 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 { 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 { triangles.clear(); final Triangulator triangulator2d = Triangulation.create(); + triangulator2d.setConvexShape( isConvex() ); for(int index = 0; index { } 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 { } } } - } 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 { 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 { bbox = new AABBox(); dirtyBBox = false; winding = Winding.CCW; - dirtyWinding = false; + convexFlag = false; + dirtyBits = 0; } /** @@ -79,7 +84,8 @@ public class Outline implements Comparable { final int count = src.vertices.size(); vertices = new ArrayList(count); winding = Winding.CCW; - dirtyWinding = true; + convexFlag = false; + dirtyBits = DIRTY_WINDING | DIRTY_CONVEX; for(int i=0; i { public Outline(final Outline src, final Winding enforce) { final int count = src.vertices.size(); vertices = new ArrayList(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 { } /** - * 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)}. + *

+ * The result is cached. + *

* @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 { } 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)}. + *

+ * 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. + *

+ *

+ * The result is cached. + *

+ */ + 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 { 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 { } 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 { */ 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 { out.printf("- OL[%d]: %s%n", vi, v); } } - } 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 loops = new ArrayList(); + private boolean convexFlag; private int addedVerticeCount; private int maxTriID; @@ -63,9 +64,15 @@ 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; @@ -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 sink) { final int loopsSize = loops.size(); + int size; for(int i=0;i outlines = new ArrayList(); + + private Loop(final GraphOutline polyline, final int edgeType, final boolean isConvex){ + this.initialOutline = polyline; + this.isConvex = isConvex; this.root = initFromPolyline(initialOutline, edgeType); } - public static Loop create(final GraphOutline polyline, final int edgeType) { - final Loop res = new Loop(polyline, edgeType); + public static Loop createBoundary(final GraphOutline polyline, final boolean isConvex) { + final Loop res = new Loop(polyline, HEdge.BOUNDARY, isConvex); if( null == res.root ) { return null; - } else if( HEdge.HOLE == edgeType ) { - res.addConstraintCurveImpl(polyline); } return res; } @@ -61,48 +61,6 @@ public class Loop { return root; } - public Triangle cut(final boolean delaunay){ - if(isSimplex()){ - return new Triangle(root.getGraphPoint().getPoint(), root.getNext().getGraphPoint().getPoint(), - root.getNext().getNext().getGraphPoint().getPoint(), checkVerticesBoundary(root)); - } - final HEdge prev = root.getPrev(); - final HEdge next1 = root.getNext(); - - final HEdge next2; - if( CDTriangulator2D.DEBUG ) { - next2 = isValidNeighborDbg(next1.getNext(), delaunay); - } else { - next2 = isValidNeighbor(next1.getNext(), delaunay); - } - if(next2 == null){ - root = root.getNext(); - return null; - } - - final GraphVertex v1 = root.getGraphPoint(); - final GraphVertex v2 = next1.getGraphPoint(); - final GraphVertex v3 = next2.getGraphPoint(); - - final HEdge v3Edge = new HEdge(v3, HEdge.INNER); - - HEdge.connect(v3Edge, root); - HEdge.connect(next1, v3Edge); - - HEdge v3EdgeSib = v3Edge.getSibling(); - if(v3EdgeSib == null){ - v3EdgeSib = new HEdge(v3Edge.getNext().getGraphPoint(), HEdge.INNER); - HEdge.makeSiblings(v3Edge, v3EdgeSib); - } - - HEdge.connect(prev, v3EdgeSib); - HEdge.connect(v3EdgeSib, next2); - - final Triangle t = createTriangle(v1.getPoint(), v2.getPoint(), v3.getPoint(), root); - this.root = next2; - return t; - } - public boolean isSimplex(){ return (root.getNext().getNext().getNext() == root); } @@ -113,6 +71,7 @@ public class Loop { * @param edgeType either {@link HEdge#BOUNDARY} requiring {@link Winding#CCW} or {@link HEdge#HOLE} using {@link Winding#CW} or even {@link Winding#CCW} */ private HEdge initFromPolyline(final GraphOutline outline, final int edgeType) { + outlines.add(outline); final ArrayList vertices = outline.getGraphPoint(); if(vertices.size()<3) { @@ -182,17 +141,12 @@ public class Loop { return firstEdge; } - public void addConstraintCurve(final GraphOutline polyline, final int edgeType) { + public void addConstraintCurveHole(final GraphOutline polyline) { // GraphOutline outline = new GraphOutline(polyline); /**needed to generate vertex references.*/ - if( null == initFromPolyline(polyline, edgeType) ) { // 'usually' HEdge.HOLE + if( null == initFromPolyline(polyline, HEdge.HOLE) ) { return; } - if( HEdge.HOLE == edgeType ) { - addConstraintCurveImpl(polyline); - } - } - private void addConstraintCurveImpl(final GraphOutline polyline) { final GraphVertex v3 = locateClosestVertex(polyline); if( null == v3 ) { System.err.println( "Graph: Loop.locateClosestVertex returns null; root valid? "+(null!=root)); @@ -225,60 +179,240 @@ public class Loop { * @return the vertex that is closest to the newly set root Hedge. */ private GraphVertex locateClosestVertex(final GraphOutline polyline) { - HEdge closestE = null; - GraphVertex closestV = null; - - // final Winding winding = polyline.getOutline().getWinding(); - // final Winding winding = getWinding( vertices ); // requires area-winding detection - float minDistance = Float.MAX_VALUE; final ArrayList initVertices = initialOutline.getGraphPoint(); + if( initVertices.size() < 2 ) { + return null; + } final ArrayList vertices = polyline.getGraphPoint(); + HEdge closestE = null; + GraphVertex closestV = null; - for(int i=0; i< initVertices.size()-1; i++){ - final GraphVertex v = initVertices.get(i); - final GraphVertex nextV = initVertices.get(i+1); + final int initSz = initVertices.size(); + GraphVertex v0 = initVertices.get(0); + for(int i=1; i< initSz; i++){ + final GraphVertex v1 = initVertices.get(i); for(int pos=0; pos %s%n", next2.getGraphPoint(), t); + return t; + } + + private boolean intersectsOutline(final Vertex a1, final Vertex a2, final Vertex b) { + // final long t0 = Clock.currentNanos(); + for(final GraphOutline outline : outlines) { + if( intersectsOutline(outline, a1, a2, b) ) { + // perf_isect_td_ns += Clock.currentNanos() - t0; + // perf_isect_count++; + return true; + } + } + // perf_isect_td_ns += Clock.currentNanos() - t0; + // perf_isect_count++; + return false; + } + private boolean intersectsOutline(final GraphOutline outline, final Vertex a1, final Vertex a2, final Vertex b) { + final ArrayList vertices = outline.getGraphPoint(); + if( vertices.size() < 2 ) { + return false; + } + final int sz = vertices.size(); + Vertex v0 = vertices.get(0).getPoint(); + for(int i=1; i< sz; i++){ + final Vertex v1 = vertices.get(i).getPoint(); + if( !( v0 == b || v1 == b ) ) { + if( !( v0 == a1 || v1 == a1 ) && + VectorUtil.testSeg2SegIntersection(a1, b, v0, v1) ) { + return true; + } + if( !( v0 == a2 || v1 == a2 ) && + VectorUtil.testSeg2SegIntersection(a2, b, v0, v1) ) { + return true; + } + } + v0 = v1; + } + return false; + } + private boolean intersectsOutlineDbg(final Vertex a1, final Vertex a2, final Vertex b) { + for(final GraphOutline outline : outlines) { + if( intersectsOutlineDbg(outline, a1, a2, b) ) { + return true; + } + } + return false; + } + private boolean intersectsOutlineDbg(final GraphOutline outline, final Vertex a1, final Vertex a2, final Vertex b) { + final ArrayList vertices = outline.getGraphPoint(); + if( vertices.size() < 2 ) { + return false; + } + final int sz = vertices.size(); + Vertex v0 = vertices.get(0).getPoint(); + for(int i=1; i< sz; i++){ + final Vertex v1 = vertices.get(i).getPoint(); + if( !( v0 == b || v1 == b ) ) { + if( !( v0 == a1 || v1 == a1 ) && + VectorUtil.testSeg2SegIntersection(a1, b, v0, v1) ) { + System.err.printf("Loop.intersection.b-a1.1: %d/%d %s to%n-a1 %s, with%n-v0 %s%n-v1 %s%n", i, sz-1, b, a1, v0, v1); + return true; + } + if( !( v0 == a2 || v1 == a2 ) && + VectorUtil.testSeg2SegIntersection(a2, b, v0, v1) ) { + System.err.printf("Loop.intersection.b-a2.1: %d/%d %s to%n-a2 %s, with%n-v0 %s%n-v1 %s%n", i, sz-1, b, a2, v0, v1); + return true; + } + } + v0 = v1; + } + return false; + } + private HEdge isValidNeighbor(final HEdge candEdge, final boolean delaunay) { final HEdge next = root.getNext(); - if( !VectorUtil.isCCW( root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(), - candEdge.getGraphPoint().getPoint()) ) { + final Vertex rootPoint = root.getGraphPoint().getPoint(); + final Vertex nextPoint = next.getGraphPoint().getPoint(); + final Vertex candPoint = candEdge.getGraphPoint().getPoint(); + if( !VectorUtil.isCCW( rootPoint, nextPoint, candPoint) ) { + return null; + } + if( !isConvex && intersectsOutline(rootPoint, nextPoint, candPoint) ) { return null; } if( !delaunay ) { return candEdge; } - final Vertex candPoint = candEdge.getGraphPoint().getPoint(); HEdge e = candEdge.getNext(); while (e != candEdge){ final GraphVertex egp = e.getGraphPoint(); @@ -286,8 +420,7 @@ public class Loop { egp != next.getGraphPoint() && egp.getPoint() != candPoint ) { - if( VectorUtil.isInCircleVec2d(root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(), - candPoint, egp.getPoint()) ) { + if( VectorUtil.isInCircle(rootPoint, nextPoint, candPoint, egp.getPoint()) ) { return null; } } @@ -297,14 +430,20 @@ public class Loop { } private HEdge isValidNeighborDbg(final HEdge candEdge, final boolean delaunay) { final HEdge next = root.getNext(); - if( !VectorUtil.isCCW( root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(), - candEdge.getGraphPoint().getPoint()) ) { + final Vertex rootPoint = root.getGraphPoint().getPoint(); + final Vertex nextPoint = next.getGraphPoint().getPoint(); + final Vertex candPoint = candEdge.getGraphPoint().getPoint(); + if( !VectorUtil.isCCW( rootPoint, nextPoint, candPoint) ) { + System.err.printf("Loop.isInCircle.X: !CCW %s, of%n- %s%n- %s%n- %s%n", + candPoint, rootPoint, nextPoint, candPoint); + return null; + } + if( !isConvex && intersectsOutlineDbg(rootPoint, nextPoint, candPoint) ) { return null; } if( !delaunay ) { return candEdge; } - final Vertex candPoint = candEdge.getGraphPoint().getPoint(); HEdge e = candEdge.getNext(); while (e != candEdge){ final GraphVertex egp = e.getGraphPoint(); @@ -312,11 +451,10 @@ public class Loop { egp != next.getGraphPoint() && egp.getPoint() != candPoint ) { - final double v = VectorUtil.inCircleVec2dVal(root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(), - candPoint, egp.getPoint()); + final double v = VectorUtil.inCircleVal(rootPoint, nextPoint, candPoint, egp.getPoint()); if( v > VectorUtil.InCircleDThreshold ) { System.err.printf("Loop.isInCircle.1: %30.30f: %s, of%n- %s%n- %s%n- %s%n", - v, candPoint, root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(), egp.getPoint()); + v, candPoint, rootPoint, nextPoint, egp.getPoint()); return null; } System.err.printf("Loop.isInCircle.0: %30.30f: %s, of%n- %s%n- %s%n- %s%n", -- cgit v1.2.3