//===========================================================================//=-------------------------------------------------------------------------=//= Module history:                                                         =//= - March 26 2008 - Oscar Chavarro: Original base version                 =//=-------------------------------------------------------------------------=//= References:                                                             =//= [MANT1988] Mantyla Martti. "An Introduction To Solid Modeling",         =//=     Computer Science Press, 1988.                                       =//===========================================================================package vsdk.toolkit.processing;// Java classesimport java.util.ArrayList;import java.util.Collections;// VitralSDK classesimport vsdk.toolkit.common.VSDK;import vsdk.toolkit.common.Vector3D;import vsdk.toolkit.common.CircularDoubleLinkedList;import vsdk.toolkit.environment.geometry.Geometry;import vsdk.toolkit.environment.geometry.InfinitePlane;import vsdk.toolkit.environment.geometry.PolyhedralBoundedSolid;import vsdk.toolkit.environment.geometry.polyhedralBoundedSolidNodes._PolyhedralBoundedSolidFace;import vsdk.toolkit.environment.geometry.polyhedralBoundedSolidNodes._PolyhedralBoundedSolidLoop;import vsdk.toolkit.environment.geometry.polyhedralBoundedSolidNodes._PolyhedralBoundedSolidEdge;import vsdk.toolkit.environment.geometry.polyhedralBoundedSolidNodes._PolyhedralBoundedSolidHalfEdge;import vsdk.toolkit.environment.geometry.polyhedralBoundedSolidNodes._PolyhedralBoundedSolidVertex;/**This class is used to store vertex / halfedge neigborhood information, as presentedin section [MANT1988].14.5, and program [MANT1988].14.3.*/class _PolyhedralBoundedSolidSplitterSectorClassification extends PolyhedralBoundedSolidOperator{    public static final int ABOVE = 1;    public static final int BELOW = -1;    public static final int ON = 0;    public static final int COPLANAR_FACE = 10;    public static final int INPLANE_EDGE = 20;    public static final int CROSSING_EDGE = 30;    public static final int UNDEFINED = 40;    public _PolyhedralBoundedSolidHalfEdge sector;    public int cl;    // Following attributes are not taken from [MANT1988], and all operations    // on them are fine tunning options aditional to original algorithm.    public boolean isWide = false;    public Vector3D position;    public int situation = UNDEFINED;    public String toString()    {        String msg = "{";        msg = msg + sector;        switch ( cl ) {          case ABOVE: msg = msg + " ABOVE"; break;          case BELOW: msg = msg + " BELOW"; break;          case ON: msg = msg + " ON"; break;          default: msg = msg + "<INVALID!>"; break;        }        if ( isWide ) {            msg = msg + " (W) ";        }        //msg = msg + ", pos: " + position;        switch ( situation ) {          case COPLANAR_FACE: msg = msg + "<COPLANAR_FACE>"; break;          case INPLANE_EDGE: msg = msg + "<INPLANE_EDGE>"; break;          case CROSSING_EDGE: msg = msg + "<CROSSING_EDGE>"; break;          default: msg = msg + "<UNDEFINED>"; break;        }        msg = msg + "}";        return msg;    }}/**Class `_PolyhedralBoundedSolidSplitterNullEdge` plays a role of a decoratordesign patern for class `_PolyhedralBoundedSolidEdge`, and adds sort-ability.*/class _PolyhedralBoundedSolidSplitterNullEdge extends PolyhedralBoundedSolidOperator implements Comparable <_PolyhedralBoundedSolidSplitterNullEdge>{    public _PolyhedralBoundedSolidEdge e;    public _PolyhedralBoundedSolidSplitterNullEdge(_PolyhedralBoundedSolidEdge e)    {        this.e = e;    }    public int compareTo(_PolyhedralBoundedSolidSplitterNullEdge other)    {        Vector3D a;        Vector3D b;        a = this.e.rightHalf.startingVertex.position;        b = other.e.rightHalf.startingVertex.position;        if ( PolyhedralBoundedSolid.compareValue(a.x, b.x, 10*VSDK.EPSILON) != 0 ) {            if ( a.x < b.x ) {                return -1;            }            return 1;        }        else {            if ( PolyhedralBoundedSolid.compareValue(a.y, b.y, 10*VSDK.EPSILON) != 0 ) {                if ( a.y < b.y ) {                    return -1;                }                return 1;            }            else {                if ( a.z < b.z ) {                    return -1;                }                return 1;            }        }    }}/**This is a utility class containing operations for implementing the boundaryrepresentation split methods over winged-edge data structures, as presentedat chapter [MANT1988].14.This class offers just one public method, which is supposed to be calledfrom GeometricModeler class.*/public class PolyhedralBoundedSolidSplitter extends PolyhedralBoundedSolidOperator{    /**    Following variable `soov` ("set of ON-vertices") from program [MANT1988].14.1.    */    private static ArrayList<_PolyhedralBoundedSolidVertex> soov;    /**    Following variable `sone` ("set of null edges") from program [MANT1988].14.1.    */    private static ArrayList<_PolyhedralBoundedSolidSplitterNullEdge> sone;    /**    Following variable `sonf` ("set of null faces") from program [MANT1988].14.1.    */    private static ArrayList<_PolyhedralBoundedSolidFace> sonf;    private static ArrayList<_PolyhedralBoundedSolidFace> facesToFixAbove;    private static ArrayList<_PolyhedralBoundedSolidFace> facesToFixBelow;    /**    Following variable `ends` from program [MANT1988].14.9.    */    private static ArrayList<_PolyhedralBoundedSolidHalfEdge> ends;    private static ArrayList<_PolyhedralBoundedSolidHalfEdge> tieds;    /**    Implements function `addsoov` from section [MANT1988].14.4. and program    [MANT1988].14.2.    */    private static void addsoov(_PolyhedralBoundedSolidVertex v)    {        int i;        for ( i = 0; i < soov.size(); i++ ) {            if ( soov.get(i) == v ) {                return;            }        }        soov.add(v);    }    /**    Implements solid splitting reduction step as indicated on sections    [MANT1988].14.2.1 and [MANT1988].14.4 and program [MANT1988].14.2.    This method is responsible for generating the set of coplanar    vertices of `inSolid` (with respect to `inSplittingPlane`) and store    them on `soov` for later usage.    This method subdivides all edges of `inSolid` that intersects    `inSplittingPlane` at their intersection points.    */    private static void splitGenerate(PolyhedralBoundedSolid inSolid,                                      InfinitePlane inSplittingPlane)    {        _PolyhedralBoundedSolidEdge e;        _PolyhedralBoundedSolidHalfEdge he;        _PolyhedralBoundedSolidVertex v1, v2;        Vector3D p;        double d1, d2, t;        int s1, s2;        int i;        soov = new ArrayList<_PolyhedralBoundedSolidVertex>();        for ( i = 0; i < inSolid.edgesList.size(); i++ ) {            e = inSolid.edgesList.get(i);            v1 = e.rightHalf.startingVertex;            v2 = e.leftHalf.startingVertex;            d1 = inSplittingPlane.pointDistance(v1.position);            d2 = inSplittingPlane.pointDistance(v2.position);            s1 = inSolid.compareValue(d1, 0.0, VSDK.EPSILON);            s2 = inSolid.compareValue(d2, 0.0, VSDK.EPSILON);            if ( (s1 == -1 && s2 == 1) || (s1 == 1 && s2 == -1) ) {                t = d1 / (d1 - d2);                p = v1.position.add((v2.position.substract(v1.position)).multiply(t));                he = e.leftHalf.next();                inSolid.lmev(e.rightHalf, he, inSolid.getMaxVertexId()+1, p);                addsoov(he.previous().startingVertex);            }            else {                if ( s1 == 0 ) {                    addsoov(v1);                }                if ( s2 == 0 ) {                    addsoov(v2);                }            }        }        /*        System.out.println("-----");        for ( i = 0; i < soov.size(); i++ ) {            System.out.println("  - Vertex [" + i + "]: " + soov.get(i));        }        System.out.println("-----");        */    }    /**    Current method is the first step for the initial classification of vertex    neighborhood for `vtx`, as indicated on section [MANT1988].14.5.2. and    program [MANT1988].14.4.    Vitral SDK's implementation of this procedure extends the original from    [MANT1988] by adding extra information flags to sector classifications    `.isWide`, `.position` and `.situation`. Those flags are an additional    aid for debugging purposes and specifically the `situation` flag will be    later used on `splitClassify` to correct the ordering of sectors in order    to keep consistency with Vitral SDK's interpretation of coordinate system.    */    private static ArrayList<_PolyhedralBoundedSolidSplitterSectorClassification> getNeighborhood(_PolyhedralBoundedSolidVertex vtx, InfinitePlane inSplittingPlane)    {        _PolyhedralBoundedSolidHalfEdge he;        Vector3D bisect;        double d;        _PolyhedralBoundedSolidSplitterSectorClassification c;        ArrayList<_PolyhedralBoundedSolidSplitterSectorClassification> neighborSectorsInfo;        neighborSectorsInfo = new ArrayList<_PolyhedralBoundedSolidSplitterSectorClassification>();        he = vtx.emanatingHalfEdge;        do {            c = new _PolyhedralBoundedSolidSplitterSectorClassification();            c.sector = he;            d = inSplittingPlane.pointDistance((he.next()).startingVertex.position);            c.cl = PolyhedralBoundedSolid.compareValue(d, 0.0, VSDK.EPSILON);            c.isWide = false;            c.position = new Vector3D((he.next()).startingVertex.position);            c.situation = c.UNDEFINED;            neighborSectorsInfo.add(c);            if ( checkWideness(he) ) {                bisect = bisector(he);                c.situation = c.CROSSING_EDGE;                c = new _PolyhedralBoundedSolidSplitterSectorClassification();                c.sector = he;                d = inSplittingPlane.pointDistance(bisect);                c.cl = PolyhedralBoundedSolid.compareValue(d, 0.0, VSDK.EPSILON);                c.isWide = true;                c.position = new Vector3D(bisect);                c.situation = c.CROSSING_EDGE;                neighborSectorsInfo.add(c);            }            he = (he.mirrorHalfEdge()).next();        } while ( he != vtx.emanatingHalfEdge );        //-----------------------------------------------------------------        // Extra pass, not from original [MANT1988] code        int i;        for ( i = 0; i < neighborSectorsInfo.size(); i++ ) {            c = neighborSectorsInfo.get(i);            if ( c.cl == c.ON && c.situation == c.UNDEFINED ) {                c.situation = c.INPLANE_EDGE;            }        }        return neighborSectorsInfo;    }    private static boolean inplaneEdgesOn(        ArrayList<_PolyhedralBoundedSolidSplitterSectorClassification> nbr)    {        int i;        for ( i = 0; i < nbr.size(); i++ ) {            if ( nbr.get(i).situation == nbr.get(i).INPLANE_EDGE ) return true;        }        return false;    }    /**    Current method applies the first reclassification rule presented at    sections [MANT1988].14.5.1 and [MANT1988].14.5.2:    For the given vertex neigborhood, classify each edge according to whether    its final vertex lies above, on or below the `inSplittingPlane`. Tag    the edge with the corresponding label ABOVE, ON or BELOW.    Following program [MANT1988].14.5.    */    private static void reclassifyOnSectors(        ArrayList<_PolyhedralBoundedSolidSplitterSectorClassification> nbr,        InfinitePlane inSplittingPlane)    {        _PolyhedralBoundedSolidFace f;        Vector3D c;        double d;        int i;        _PolyhedralBoundedSolidSplitterSectorClassification l;        for ( i = 0; i < nbr.size(); i++ ) {            l = nbr.get(i);            f = l.sector.parentLoop.parentFace;            c = f.containingPlane.getNormal().crossProduct(inSplittingPlane.getNormal());            d = c.dotProduct(c);            if ( PolyhedralBoundedSolid.compareValue(d, 0.0, VSDK.EPSILON) == 0 ) {                // Entering this means "faces are coplanar"                d = f.containingPlane.getNormal().dotProduct(inSplittingPlane.getNormal());                if ( PolyhedralBoundedSolid.compareValue(d, 0.0, VSDK.EPSILON) == 1 ) {                    l.cl = l.BELOW;                    l.situation = l.COPLANAR_FACE;                    nbr.get((i+1)%nbr.size()).cl = l.BELOW;                }                else {                    l.cl = l.ABOVE;                    l.situation = l.COPLANAR_FACE;                    nbr.get((i+1)%nbr.size()).cl = l.ABOVE;                }            }        }    }    /**    Current method applies the second reclassification rule presented at    sections [MANT1988].14.5.1 and [MANT1988].14.5.2:    After applying the first rule on method `reclassifyOnSectors`, ON edges    may appear in only four kinds of consecutive arrangements. For each    of the following arrangements, ON edge is reclassified as ABOVE or BELOW:      - Sequence ABOVE/ON/ABOVE -> reclassified as BELOW      - Sequence ABOVE/ON/BELOW -> reclassified as BELOW      - Sequence BELOW/ON/BELOW -> reclassified as ABOVE      - Sequence BELOW/ON/ABOVE -> reclassified as BELOW    Those 4 rules are designed so that nonmanifold results will be represented    as disconnected models.    Following program [MANT1988].14.6.    */    private static void reclassifyOnEdges(ArrayList<_PolyhedralBoundedSolidSplitterSectorClassification> nbr)    {        _PolyhedralBoundedSolidSplitterSectorClassification l;        int i;        for ( i = 0; i < nbr.size(); i++ ) {            l = nbr.get(i);            if ( l.cl == l.ON ) {                if ( nbr.get((nbr.size()+i-1) % nbr.size()).cl == l.BELOW ) {                    if ( nbr.get((i+1) % nbr.size()).cl == l.BELOW ) {                        nbr.get(i).cl = l.ABOVE;                    }                    else {                        nbr.get(i).cl = l.BELOW;                    }                }                else {                    nbr.get(i).cl = l.BELOW;                }            }        }    }    /**    Following section [MANT1988].14,6,2 and program [MANT1988].14.7.    Note, this code is horrible! YUCK! :P    With respect to the original algorithm from [MANT1988], current    implementation adds an extra check to ensure the orientation of the    edges from below to above.    */    private static void insertNullEdges(