/** * 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: * * 1. Redistributions of source code must retain the above copyright notice, this list of * conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright notice, this list * of conditions and the following disclaimer in the documentation and/or other materials * provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY JogAmp Community ``AS IS'' AND ANY EXPRESS OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JogAmp Community OR * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * The views and conclusions contained in the software and documentation are those of the * authors and should not be interpreted as representing official policies, either expressed * or implied, of JogAmp Community. */ package jogamp.graph.curve.tess; import java.util.ArrayList; import java.util.List; import com.jogamp.graph.geom.Vertex; import com.jogamp.math.DoubleUtil; import com.jogamp.math.FloatUtil; 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 final AABBox box = new AABBox(); private final GraphOutline initialOutline; private final boolean isConvex; private HEdge root; private final List 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 createBoundary(final GraphOutline polyline, final boolean isConvex) { final Loop res = new Loop(polyline, HEdge.BOUNDARY, isConvex); if( null == res.root ) { return null; } return res; } public HEdge getHEdge(){ return root; } public boolean isSimplex(){ return (root.getNext().getNext().getNext() == root); } /** * Create a connected list of half edges (loop) * from the boundary profile * @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) { System.err.println( "Graph: Loop.initFromPolyline: GraphOutline's vertices < 3: " + vertices.size() ); if( GraphOutline.DEBUG ) { Thread.dumpStack(); } return null; } final Winding edgeWinding = HEdge.BOUNDARY == edgeType ? Winding.CCW : Winding.CW; final Winding winding = CDTriangulator2D.FixedWindingRule ? edgeWinding : outline.getOutline().getWinding(); 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; 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) { final GraphVertex v1 = vertices.get(index); box.resize(v1.x(), v1.y(), v1.z()); final HEdge edge = new HEdge(v1, edgeType); v1.addEdge(edge); if(lastEdge != null) { lastEdge.setNext(edge); edge.setPrev(lastEdge); } else { firstEdge = edge; } if(index == max ) { edge.setNext(firstEdge); firstEdge.setPrev(edge); } lastEdge = edge; } } else { // if( winding == 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()); final HEdge edge = new HEdge(v1, edgeType); v1.addEdge(edge); if(lastEdge != null) { lastEdge.setNext(edge); edge.setPrev(lastEdge); } else { firstEdge = edge; } if (index == 0) { edge.setNext(firstEdge); firstEdge.setPrev(edge); } lastEdge = edge; } } return firstEdge; } public void addConstraintCurveHole(final GraphOutline polyline) { // GraphOutline outline = new GraphOutline(polyline); /**needed to generate vertex references.*/ if( null == initFromPolyline(polyline, HEdge.HOLE) ) { return; } final GraphVertex v3 = locateClosestVertex(polyline); if( null == v3 ) { System.err.println( "Graph: Loop.locateClosestVertex returns null; root valid? "+(null!=root)); if( GraphOutline.DEBUG ) { Thread.dumpStack(); } return; } final HEdge v3Edge = v3.findBoundEdge(); final HEdge v3EdgeP = v3Edge.getPrev(); final HEdge crossEdge = new HEdge(root.getGraphPoint(), HEdge.INNER); HEdge.connect(root.getPrev(), crossEdge); HEdge.connect(crossEdge, v3Edge); HEdge crossEdgeSib = crossEdge.getSibling(); if(crossEdgeSib == null) { crossEdgeSib = new HEdge(crossEdge.getNext().getGraphPoint(), HEdge.INNER); HEdge.makeSiblings(crossEdge, crossEdgeSib); } HEdge.connect(v3EdgeP, crossEdgeSib); HEdge.connect(crossEdgeSib, 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 in CW * @return the vertex that is closest to the newly set root Hedge. */ private GraphVertex locateClosestVertex(final GraphOutline polyline) { 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; 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(); final int sz = vertices.size(); if( sz < 2 ) { return false; } 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, FloatUtil.EPSILON, false) ) { return true; } if( !( v0 == a2 || v1 == a2 ) && VectorUtil.testSeg2SegIntersection(a2, b, v0, v1, FloatUtil.EPSILON, false) ) { 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(); final int sz = vertices.size(); if( sz < 2 ) { return false; } 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, FloatUtil.EPSILON, false) ) { 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, FloatUtil.EPSILON, false) ) { 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(); 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; } HEdge e = candEdge.getNext(); while (e != candEdge){ final GraphVertex egp = e.getGraphPoint(); if(egp != root.getGraphPoint() && egp != next.getGraphPoint() && egp.getPoint() != candPoint ) { if( VectorUtil.isInCircle(rootPoint, nextPoint, candPoint, egp.getPoint()) ) { return null; } } e = e.getNext(); } return candEdge; } private HEdge isValidNeighborDbg(final HEdge candEdge, final boolean delaunay) { final HEdge next = root.getNext(); 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; } 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.inCircleVal(rootPoint, nextPoint, candPoint, egp.getPoint()); if( v > DoubleUtil.EPSILON ) { System.err.printf("Loop.isInCircle.1: %30.30f: %s, of%n- %s%n- %s%n- %s%n", 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", 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 * the triangle is valid. IE not outside region. * @param v1 vertex 1 * @param v2 vertex 2 * @param v3 vertex 3 * @param root and edge of this triangle * @return the triangle iff it satisfies, null otherwise */ private Triangle createTriangle(final Vertex v1, final Vertex v2, final Vertex v3, final HEdge rootT){ return new Triangle(v1, v2, v3, checkVerticesBoundary(rootT)); } private boolean[] checkVerticesBoundary(final HEdge rootT) { final boolean[] boundary = new boolean[3]; if(rootT.getGraphPoint().isBoundaryContained()){ boundary[0] = true; } if(rootT.getNext().getGraphPoint().isBoundaryContained()){ boundary[1] = true; } if(rootT.getNext().getNext().getGraphPoint().isBoundaryContained()){ boundary[2] = true; } return boundary; } public boolean checkInside(final Vertex v) { if(!box.contains(v.x(), v.y(), v.z())){ return false; } boolean inside = false; HEdge current = root; HEdge next = root.getNext(); do { final Vertex v2 = current.getGraphPoint().getPoint(); final Vertex v1 = next.getGraphPoint().getPoint(); if ( ((v1.y() > v.y()) != (v2.y() > v.y())) && (v.x() < (v2.x() - v1.x()) * (v.y() - v1.y()) / (v2.y() - v1.y()) + v1.x()) ){ inside = !inside; } current = next; next = current.getNext(); } while(current != root); return inside; } public int computeLoopSize(){ int size = 0; HEdge e = root; do{ size++; e = e.getNext(); }while(e != root); return size; } }