diff options
Diffstat (limited to 'src/jogl')
4 files changed, 197 insertions, 106 deletions
diff --git a/src/jogl/classes/com/jogamp/math/VectorUtil.java b/src/jogl/classes/com/jogamp/math/VectorUtil.java index 6cea0be0b..716b63e47 100644 --- a/src/jogl/classes/com/jogamp/math/VectorUtil.java +++ b/src/jogl/classes/com/jogamp/math/VectorUtil.java @@ -287,33 +287,75 @@ public final class VectorUtil { } /** - * Check if vertices in triangle circumcircle + * Check if vertices in triangle circumcircle given {@code d} vertex, from paper by Guibas and Stolfi (1985). * @param a triangle vertex 1 * @param b triangle vertex 2 * @param c triangle vertex 3 * @param d vertex in question - * @return true if the vertex d is inside the circle defined by the - * vertices a, b, c. from paper by Guibas and Stolfi (1985). - */ - public static boolean isInCircleVec2(final Vert2fImmutable a, final Vert2fImmutable b, final Vert2fImmutable c, final Vert2fImmutable d) { - return (a.x() * a.x() + a.y() * a.y()) * triAreaVec2(b, c, d) - - (b.x() * b.x() + b.y() * b.y()) * triAreaVec2(a, c, d) + - (c.x() * c.x() + c.y() * c.y()) * triAreaVec2(a, b, d) - - (d.x() * d.x() + d.y() * d.y()) * triAreaVec2(a, b, c) > 0; - } - - /** - * Computes oriented area of a triangle + * @return true if the vertex d is inside the circle defined by the vertices a, b, c. + */ + public static boolean isInCircleVec2f(final Vert2fImmutable a, final Vert2fImmutable b, final Vert2fImmutable c, final Vert2fImmutable d) { + // Operation costs: + // - 4x (triAreaVec2: 5+, 2*) -> 20+, 8* + // - plus 7+, 12* -> 27+, 20* + return (a.x() * a.x() + a.y() * a.y()) * triAreaVec2f(b, c, d) - + (b.x() * b.x() + b.y() * b.y()) * triAreaVec2f(a, c, d) + + (c.x() * c.x() + c.y() * c.y()) * triAreaVec2f(a, b, d) - + (d.x() * d.x() + d.y() * d.y()) * triAreaVec2f(a, b, c) > InCircleFThreshold; + } + public static final float InCircleFThreshold = FloatUtil.EPSILON; + public static float inCircleVec2fVal(final Vert2fImmutable a, final Vert2fImmutable b, final Vert2fImmutable c, final Vert2fImmutable d) { + // Operation costs: + // - 4x (triAreaVec2: 5+, 2*) -> 20+, 8* + // - plus 7+, 12* -> 27+, 20* + return (a.x() * a.x() + a.y() * a.y()) * triAreaVec2f(b, c, d) - + (b.x() * b.x() + b.y() * b.y()) * triAreaVec2f(a, c, d) + + (c.x() * c.x() + c.y() * c.y()) * triAreaVec2f(a, b, d) - + (d.x() * d.x() + d.y() * d.y()) * triAreaVec2f(a, b, c); + } + + public static final double InCircleDThreshold = DoubleUtil.EPSILON; + public static boolean isInCircleVec2d(final Vert2fImmutable a, final Vert2fImmutable b, final Vert2fImmutable c, final Vert2fImmutable d) { + return inCircleVec2dVal(a, b, c, d) > InCircleDThreshold; + } + public static double inCircleVec2dVal(final Vert2fImmutable a, final Vert2fImmutable b, final Vert2fImmutable c, final Vert2fImmutable d) { + // Operation costs: + // - 4x (triAreaVec2: 5+, 2*) -> 20+, 8* + // - plus 7+, 12* -> 27+, 20* + return sqlend(a) * triAreaVec2d(b, c, d) - + sqlend(b) * triAreaVec2d(a, c, d) + + sqlend(c) * triAreaVec2d(a, b, d) - + sqlend(d) * triAreaVec2d(a, b, c); + } + private static double sqlend(final Vert2fImmutable a) { + final double x = a.x(); + final double y = a.y(); + return x*x + y*y; + } + + /** + * Computes oriented double area of a triangle, + * i.e. the 2x2 determinant with b-a and c-a per column. + * <pre> + * | bx-ax, cx-ax | + * det = | by-ay, cy-ay | + * </pre> * @param a first vertex * @param b second vertex * @param c third vertex - * @return compute twice the area of the oriented triangle (a,b,c), the area - * is positive if the triangle is oriented counterclockwise. + * @return area > 0 CCW, .. */ - public static float triAreaVec2(final Vert2fImmutable a, final Vert2fImmutable b, final Vert2fImmutable c){ + public static float triAreaVec2f(final Vert2fImmutable a, final Vert2fImmutable b, final Vert2fImmutable c){ return (b.x() - a.x()) * (c.y() - a.y()) - (b.y() - a.y()) * (c.x() - a.x()); } + public static double triAreaVec2d(final Vert2fImmutable a, final Vert2fImmutable b, final Vert2fImmutable c){ + return triAreaVec2d(a.x(), a.y(), b.x(), b.y(), c.x(), c.y()); + } + private static double triAreaVec2d(final double ax, final double ay, final double bx, final double by, final double cx, final double cy){ + return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax); + } + /** * Check if a vertex is in triangle using barycentric coordinates computation. * @param a first triangle vertex @@ -494,13 +536,17 @@ public final class VectorUtil { /** * Check if points are in ccw order + * <p> + * Consider using {@link #getWinding(ArrayList)} using the {@link #area(ArrayList)} function over all points + * on complex shapes for a reliable result! + * </p> * @param a first vertex * @param b second vertex * @param c third vertex * @return true if the points a,b,c are in a ccw order */ public static boolean isCCW(final Vert2fImmutable a, final Vert2fImmutable b, final Vert2fImmutable c){ - return triAreaVec2(a,b,c) > 0; + return triAreaVec2d(a,b,c) > InCircleDThreshold; } /** @@ -516,7 +562,7 @@ public final class VectorUtil { * @see #getWinding(ArrayList) */ public static Winding getWinding(final Vert2fImmutable a, final Vert2fImmutable b, final Vert2fImmutable c) { - return triAreaVec2(a,b,c) > 0 ? Winding.CCW : Winding.CW ; + return triAreaVec2d(a,b,c) > InCircleDThreshold ? Winding.CCW : Winding.CW ; } /** @@ -767,4 +813,5 @@ public final class VectorUtil { testSeg2SegIntersection(b, c, d, e, epsilon) || testSeg2SegIntersection(a, c, d, e, epsilon) ; } + } 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<Triangle> 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<GraphVertex> 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<GraphVertex> 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<GraphVertex> 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<GraphVertex> initVertices = initialOutline.getGraphPoint(); final ArrayList<GraphVertex> 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 |