diff options
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<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); } } - } 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); } } } diff --git a/src/jogl/classes/jogamp/graph/curve/tess/Loop.java b/src/jogl/classes/jogamp/graph/curve/tess/Loop.java index 807a07b67..6f6b81a2f 100644 --- a/src/jogl/classes/jogamp/graph/curve/tess/Loop.java +++ b/src/jogl/classes/jogamp/graph/curve/tess/Loop.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: @@ -28,31 +28,31 @@ package jogamp.graph.curve.tess; import java.util.ArrayList; - +import java.util.List; import com.jogamp.graph.geom.Vertex; -import com.jogamp.math.Vec3f; import com.jogamp.math.VectorUtil; import com.jogamp.math.geom.AABBox; import com.jogamp.math.geom.plane.Winding; import com.jogamp.graph.geom.Triangle; public class Loop { - private HEdge root = null; private final AABBox box = new AABBox(); - private GraphOutline initialOutline = null; - - private Loop(final GraphOutline polyline, final int edgeType){ - initialOutline = polyline; + private final GraphOutline initialOutline; + private final boolean isConvex; + private HEdge root; + private final List<GraphOutline> outlines = new ArrayList<GraphOutline>(); + + 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<GraphVertex> 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<GraphVertex> initVertices = initialOutline.getGraphPoint(); + if( initVertices.size() < 2 ) { + return null; + } final ArrayList<GraphVertex> 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<vertices.size(); pos++) { final GraphVertex cand = vertices.get(pos); - final float distance = v.getCoord().dist( cand.getCoord() ); + final float distance = v0.getCoord().dist( cand.getCoord() ); if(distance < minDistance){ boolean inside = false; for (final GraphVertex vert:vertices){ - if(vert == v || vert == nextV || vert == cand) { - continue; - } - inside = VectorUtil.isInCircleVec2d(v.getPoint(), nextV.getPoint(), cand.getPoint(), vert.getPoint()); - if(inside){ - break; + if( !( vert == v0 || vert == v1 || vert == cand) ) { + inside = VectorUtil.isInCircle(v0.getPoint(), v1.getPoint(), cand.getPoint(), vert.getPoint()); + if(inside){ + break; + } } } if(!inside){ closestV = cand; minDistance = distance; - closestE = v.findBoundEdge(); + closestE = v0.findBoundEdge(); } } - } + v0 = v1; } - if(closestE != null){ root = closestE; } - return closestV; } + /** + public static void printPerf(final PrintStream out) { + out.printf("Graph.Intersection: cut[count %,d, td %,f ms], isect[count %,d, td %,f ms], isec/cut[count %f, td %f]%n", + perf_cut_count, perf_cut_td_ns/1000000.0, perf_isect_count, perf_isect_td_ns/1000000.0, + (double)perf_isect_count/(double)perf_cut_count, (double)perf_isect_td_ns/(double)perf_cut_td_ns); + } + private static long perf_isect_td_ns = 0; + private static long perf_isect_count = 0; + private static long perf_cut_td_ns = 0; + private static long perf_cut_count = 0; + */ + public final Triangle cut(final boolean delaunay){ + if( !CDTriangulator2D.DEBUG ) { + // final long t0 = Clock.currentNanos(); + return cut0(delaunay); + // perf_cut_td_ns += Clock.currentNanos() - t0; + // perf_cut_count++; + } else { + return cutDbg(delaunay); + } + } + private final Triangle cut0(final boolean delaunay){ + final HEdge next1 = root.getNext(); + if(isSimplex()){ + final Vertex rootPoint = root.getGraphPoint().getPoint(); + final Vertex nextPoint = next1.getGraphPoint().getPoint(); + final Vertex candPoint = next1.getNext().getGraphPoint().getPoint(); + if( !isConvex && intersectsOutline(rootPoint, nextPoint, candPoint) ) { + return null; + } + return new Triangle(rootPoint, nextPoint, candPoint, checkVerticesBoundary(root)); + } + final HEdge prev = root.getPrev(); + + final HEdge 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; + } + private final Triangle cutDbg(final boolean delaunay){ + final HEdge next1 = root.getNext(); + if(isSimplex()){ + final Vertex rootPoint = root.getGraphPoint().getPoint(); + final Vertex nextPoint = next1.getGraphPoint().getPoint(); + final Vertex candPoint = next1.getNext().getGraphPoint().getPoint(); + if( !isConvex && intersectsOutlineDbg(rootPoint, nextPoint, candPoint) ) { + System.err.printf("Loop.cut.X0: last-simplex intersects%n"); + return null; + } + final Triangle tri = new Triangle(rootPoint, nextPoint, candPoint, checkVerticesBoundary(root)); + System.err.printf("Loop.cut.X1: last-simplex %s%n", tri); + return tri; + } + final HEdge prev = root.getPrev(); + + final HEdge next2 = isValidNeighborDbg(next1.getNext(), delaunay); + if(next2 == null){ + root = root.getNext(); + System.err.printf("Loop.cut.0: null-cut %s%n", next1.getNext().getGraphPoint()); + 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; + System.err.printf("Loop.cut.1: new-cut %s -> %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<GraphVertex> 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<GraphVertex> 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", |