From 277ad1ba1453b7e2e0164f1a609482a36469b2ea Mon Sep 17 00:00:00 2001 From: Sven Göthel Date: Mon, 12 Feb 2024 02:31:13 +0100 Subject: Bug 1501: Graph Delaunay: Add double triAreaVec2() and isInCircleVec2() version, overcome float precision; Loop: Pass edgeType not Winding, simplify findClosestValidNeighbor() -> isValidNeighbor(); CDTriangulator2D.addCurve() enforces Winding.CCW on BOUNDARY null == loop case Add double version of triAreaVec2() and isInCircleVec2() in VectorUtil, overcoming float precision limits - Analysis exposed float precision limits within isInCircleVec2() Loop: Pass edgeType not Winding, simplify findClosestValidNeighbor() -> isValidNeighbor() - Enhance code clarity CDTriangulator2D.addCurve() enforces Winding.CCW on BOUNDARY null == loop case --- .../jogamp/graph/curve/opengl/VBORegionSPES2.java | 4 +- .../jogamp/graph/curve/tess/CDTriangulator2D.java | 45 ++++-- src/jogl/classes/jogamp/graph/curve/tess/Loop.java | 171 ++++++++++++--------- 3 files changed, 132 insertions(+), 88 deletions(-) (limited to 'src/jogl/classes/jogamp/graph') diff --git a/src/jogl/classes/jogamp/graph/curve/opengl/VBORegionSPES2.java b/src/jogl/classes/jogamp/graph/curve/opengl/VBORegionSPES2.java index a406bfb82..478931531 100644 --- a/src/jogl/classes/jogamp/graph/curve/opengl/VBORegionSPES2.java +++ b/src/jogl/classes/jogamp/graph/curve/opengl/VBORegionSPES2.java @@ -202,11 +202,11 @@ public final class VBORegionSPES2 extends GLRegion { gl.glUniform(gcu_ColorTexBBox); // Always update, since program maybe used by multiple regions gl.glUniform(gcu_ColorTexClearCol); // Always update, since program maybe used by multiple regions gl.glDrawElements(GL.GL_TRIANGLES, indicesBuffer.getElemCount() * indicesBuffer.getCompsPerElem(), glIdxType(), 0); - // gl.glDrawElements(GL.GL_LINE_STRIP, indicesBuffer.getElementCount() * indicesBuffer.getComponentCount(), gl_idx_type, 0); + // gl.glDrawElements(GL.GL_LINE_STRIP, indicesBuffer.getElemCount() * indicesBuffer.getCompsPerElem(), glIdxType(), 0); tex.disable(gl); // nop on core } else { gl.glDrawElements(GL.GL_TRIANGLES, indicesBuffer.getElemCount() * indicesBuffer.getCompsPerElem(), glIdxType(), 0); - // gl.glDrawElements(GL.GL_LINE_STRIP, indicesBuffer.getElementCount() * indicesBuffer.getComponentCount(), gl_idx_type, 0); + // gl.glDrawElements(GL.GL_LINE_STRIP, indicesBuffer.getElemCount() * indicesBuffer.getCompsPerElem(), glIdxType(), 0); } indicesBuffer.bindBuffer(gl, false); diff --git a/src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java b/src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java index fe1aad169..d27b7a584 100644 --- a/src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java +++ b/src/jogl/classes/jogamp/graph/curve/tess/CDTriangulator2D.java @@ -83,14 +83,32 @@ public class CDTriangulator2D implements Triangulator { public final void addCurve(final List sink, final Outline polyline, final float sharpness) { Loop loop = getContainerLoop(polyline); + final Winding winding = polyline.getWinding(); if( null == loop ) { - final Winding winding = Winding.CCW; // -> HEdge.BOUNDARY + // HEdge.BOUNDARY -> Winding.CCW + int edgeType; + boolean hole; + if( Winding.CCW != winding ) { + System.err.println("CDT2.add.xx.BOUNDARY: !CCW but "+winding); + // polyline.print(System.err); + if( false ) { + edgeType = HEdge.HOLE; + hole = true; + } else { + edgeType = HEdge.BOUNDARY; + hole = false; + polyline.setWinding(Winding.CCW); + } + } else { + edgeType = HEdge.BOUNDARY; + hole = false; + } // Too late: polyline.setWinding(winding); - final GraphOutline outline = new GraphOutline(polyline); // , winding); - final GraphOutline innerPoly = extractBoundaryTriangles(sink, outline, false, sharpness); + final GraphOutline outline = new GraphOutline(polyline); + final GraphOutline innerPoly = extractBoundaryTriangles(sink, outline, hole, sharpness); // vertices.addAll(polyline.getVertices()); if( innerPoly.getGraphPoint().size() >= 3 ) { - loop = Loop.create(innerPoly, winding); + loop = Loop.create(innerPoly, edgeType); if( null != loop ) { loops.add(loop); } @@ -122,9 +140,9 @@ public class CDTriangulator2D implements Triangulator { Thread.dumpStack(); } } else { - // final Winding winding = Winding.CW; // -> HEdge.HOLE - // Not required, handled in Loop.initFromPolyline(): polyline.setWinding(winding); - final GraphOutline outline = new GraphOutline(polyline); // , winding); + // 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, true, sharpness); // vertices.addAll(innerPoly.getVertices()); loop.addConstraintCurve(innerPoly); @@ -140,14 +158,13 @@ public class CDTriangulator2D implements Triangulator { int size = loop.computeLoopSize(); while(!loop.isSimplex()){ final Triangle tri; - final boolean delauny; - if(numTries > size){ + final boolean delaunay; + if(numTries > size) { tri = loop.cut(false); - delauny = false; - } - else{ + delaunay = false; + } else { tri = loop.cut(true); - delauny = true; + delaunay = true; } numTries++; @@ -155,7 +172,7 @@ public class CDTriangulator2D implements Triangulator { tri.setId(maxTriID++); sink.add(tri); if(DEBUG){ - System.err.println("CDTri.gen["+i+"].0: delauny "+delauny+", tries "+numTries+", size "+size+", "+tri); + System.err.println("CDTri.gen["+i+"].0: delaunay "+delaunay+", tries "+numTries+", size "+size+", "+tri); } numTries = 0; size--; diff --git a/src/jogl/classes/jogamp/graph/curve/tess/Loop.java b/src/jogl/classes/jogamp/graph/curve/tess/Loop.java index a27540878..d94ab775d 100644 --- a/src/jogl/classes/jogamp/graph/curve/tess/Loop.java +++ b/src/jogl/classes/jogamp/graph/curve/tess/Loop.java @@ -42,14 +42,19 @@ public class Loop { private final AABBox box = new AABBox(); private GraphOutline initialOutline = null; - private Loop(final GraphOutline polyline, final Winding winding){ + private Loop(final GraphOutline polyline, final int edgeType){ initialOutline = polyline; - this.root = initFromPolyline(initialOutline, winding); + this.root = initFromPolyline(initialOutline, edgeType); } - public static Loop create(final GraphOutline polyline, final Winding winding) { - final Loop res = new Loop(polyline, winding); - return null != res.root ? res : null; + public static Loop create(final GraphOutline polyline, final int edgeType) { + final Loop res = new Loop(polyline, edgeType); + if( null == res.root ) { + return null; + } else if( HEdge.HOLE == edgeType ) { + res.addConstraintCurveImpl(polyline); + } + return res; } public HEdge getHEdge(){ @@ -64,7 +69,12 @@ public class Loop { final HEdge prev = root.getPrev(); final HEdge next1 = root.getNext(); - final HEdge next2 = findClosestValidNeighbor(next1.getNext(), delaunay); + 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; @@ -97,26 +107,12 @@ public class Loop { return (root.getNext().getNext().getNext() == root); } - private static float area(final ArrayList vertices) { - final int n = vertices.size(); - float area = 0.0f; - for (int p = n - 1, q = 0; q < n; p = q++) { - final Vec3f pCoord = vertices.get(p).getCoord(); - final Vec3f qCoord = vertices.get(q).getCoord(); - area += pCoord.x() * qCoord.y() - qCoord.x() * pCoord.y(); - } - return area; - } - private static Winding getWinding(final ArrayList vertices) { - return area(vertices) >= 0 ? Winding.CCW : Winding.CW ; - } - /** * Create a connected list of half edges (loop) * from the boundary profile - * @param reqWinding requested winding of edges, either {@link Winding#CCW} for {@link HEdge#BOUNDARY} or {@link Winding#CW} for {@link HEdge#HOLE} + * @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 Winding reqWinding){ + private HEdge initFromPolyline(final GraphOutline outline, final int edgeType) { final ArrayList vertices = outline.getGraphPoint(); if(vertices.size()<3) { @@ -126,21 +122,19 @@ public class Loop { } return null; } - final Winding hasWinding = getWinding( vertices ); // requires area-winding detection - - final int edgeType = reqWinding == Winding.CCW ? HEdge.BOUNDARY : HEdge.HOLE ; + final Winding winding = outline.getOutline().getWinding(); + final Winding edgeWinding = HEdge.BOUNDARY == edgeType ? Winding.CCW : Winding.CW; + + if( HEdge.BOUNDARY == edgeType && Winding.CCW != winding ) { + // XXXX + System.err.println("Loop.init.xx.01: BOUNDARY req CCW but has "+winding); + // outline.getOutline().print(System.err); + Thread.dumpStack(); + } HEdge firstEdge = null; HEdge lastEdge = null; - /** - * The winding conversion CW -> CCW can't be resolved here (-> Rami?) - * Therefore we require outline boundaries to be in CCW, see API-doc comment in OutlineShape. - * - * Original comment: - * FIXME: handle case when vertices come inverted - Rami - * Skips inversion CW -> CCW - */ - if( hasWinding == reqWinding || reqWinding == Winding.CCW ) { + if( winding == edgeWinding || HEdge.BOUNDARY == edgeType ) { // Correct Winding or skipped CW -> CCW (no inversion possible here, too late ??) final int max = vertices.size() - 1; for(int index = 0; index <= max; ++index) { @@ -162,8 +156,8 @@ public class Loop { } lastEdge = edge; } - } else { // if( reqWinding == Winding.CW ) { - // CCW -> CW + } else { // if( hasWinding == Winding.CW ) { + // CCW <-> CW for(int index = vertices.size() - 1; index >= 0; --index) { final GraphVertex v1 = vertices.get(index); box.resize(v1.x(), v1.y(), v1.z()); @@ -191,10 +185,12 @@ public class Loop { public void addConstraintCurve(final GraphOutline polyline) { // GraphOutline outline = new GraphOutline(polyline); /**needed to generate vertex references.*/ - if( null == initFromPolyline(polyline, Winding.CW) ) { // -> HEdge.HOLE + if( null == initFromPolyline(polyline, HEdge.HOLE) ) { return; } - + 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)); @@ -220,18 +216,20 @@ public class Loop { HEdge.connect(crossEdgeSib, root); } - /** Locates the vertex and update the loops root + /** + * Locates the vertex and update the loops root * to have (root + vertex) as closest pair - * @param polyline the control polyline - * to search for closestvertices + * @param polyline the control polyline to search for closestvertices in CW * @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; - boolean inValid = false; final ArrayList initVertices = initialOutline.getGraphPoint(); final ArrayList vertices = polyline.getGraphPoint(); @@ -242,16 +240,17 @@ public class Loop { final GraphVertex cand = vertices.get(pos); final float distance = v.getCoord().dist( cand.getCoord() ); if(distance < minDistance){ + boolean inside = false; for (final GraphVertex vert:vertices){ - if(vert == v || vert == nextV || vert == cand) + if(vert == v || vert == nextV || vert == cand) { continue; - inValid = VectorUtil.isInCircleVec2(v.getPoint(), nextV.getPoint(), - cand.getPoint(), vert.getPoint()); - if(inValid){ + } + inside = VectorUtil.isInCircleVec2d(v.getPoint(), nextV.getPoint(), cand.getPoint(), vert.getPoint()); + if(inside){ break; } } - if(!inValid){ + if(!inside){ closestV = cand; minDistance = distance; closestE = v.findBoundEdge(); @@ -268,39 +267,67 @@ public class Loop { return closestV; } - private HEdge findClosestValidNeighbor(final HEdge edge, final boolean delaunay) { + private HEdge isValidNeighbor(final HEdge candEdge, final boolean delaunay) { final HEdge next = root.getNext(); - - if(!VectorUtil.isCCW(root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(), - edge.getGraphPoint().getPoint())){ + if( !VectorUtil.isCCW( root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(), + candEdge.getGraphPoint().getPoint()) ) { return null; } - - final HEdge candEdge = edge; - boolean inValid = false; - - if(delaunay){ - final Vertex cand = candEdge.getGraphPoint().getPoint(); - HEdge e = candEdge.getNext(); - while (e != candEdge){ - if(e.getGraphPoint() == root.getGraphPoint() - || e.getGraphPoint() == next.getGraphPoint() - || e.getGraphPoint().getPoint() == cand){ - e = e.getNext(); - continue; - } - inValid = VectorUtil.isInCircleVec2(root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(), - cand, e.getGraphPoint().getPoint()); - if(inValid){ - break; + if( !delaunay ) { + return candEdge; + } + final Vertex candPoint = candEdge.getGraphPoint().getPoint(); + HEdge e = candEdge.getNext(); + while (e != candEdge){ + final GraphVertex egp = e.getGraphPoint(); + if(egp != root.getGraphPoint() && + egp != next.getGraphPoint() && + egp.getPoint() != candPoint ) + { + if( VectorUtil.isInCircleVec2d(root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(), + candPoint, egp.getPoint()) ) { + return null; } - e = e.getNext(); } + e = e.getNext(); } - if(!inValid){ + return candEdge; + } + 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()) ) { + return null; + } + if( !delaunay ) { return candEdge; } - return null; + final Vertex candPoint = candEdge.getGraphPoint().getPoint(); + HEdge e = candEdge.getNext(); + while (e != candEdge){ + final GraphVertex egp = e.getGraphPoint(); + if(egp != root.getGraphPoint() && + egp != next.getGraphPoint() && + egp.getPoint() != candPoint ) + { + final double v = VectorUtil.inCircleVec2dVal(root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(), + candPoint, egp.getPoint()); + if( v > VectorUtil.InCircleDThreshold ) { + if( CDTriangulator2D.DEBUG ) { + 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()); + } + return null; + } + if( CDTriangulator2D.DEBUG ) { + System.err.printf("Loop.isInCircle.0: %30.30f: %s, of%n- %s%n- %s%n- %s%n", + v, candPoint, root.getGraphPoint().getPoint(), next.getGraphPoint().getPoint(), egp.getPoint()); + } + } + e = e.getNext(); + } + System.err.printf("Loop.isInCircle.0: %s%n", candPoint); + return candEdge; } /** Create a triangle from the param vertices only if -- cgit v1.2.3