polyhedralboundedsolidsplitter.java

基于java的3d开发库。对坐java3d的朋友有很大的帮助。

//===========================================================================
//=-------------------------------------------------------------------------=
//= 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 classes
import java.util.ArrayList;
import java.util.Collections;

// VitralSDK classes
import 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 presented
in 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 decorator
design 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 boundary
representation split methods over winged-edge data structures, as presented
at chapter [MANT1988].14.

This class offers just one public method, which is supposed to be called
from 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(