polyhedralboundedsolidsplitter.java

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

        ArrayList<_PolyhedralBoundedSolidSplitterSectorClassification> nbr,
        PolyhedralBoundedSolid inSolid, InfinitePlane inSplittingPlane)
    {
        int start, i;
        _PolyhedralBoundedSolidHalfEdge head, tail;
        _PolyhedralBoundedSolidSplitterSectorClassification n;
        int nnbr = nbr.size();

        if ( nnbr <= 0 ) return;
        n = nbr.get(0);

        //- Locate the head of an ABOVE-sequence --------------------------
        i = 0;
        while ( !( nbr.get(i).cl == n.BELOW &&
                   nbr.get( (i+1)%nnbr ).cl == n.ABOVE )  ) {
            i++;
            if ( i >= nnbr ) {
                return;
            }
        }
        start = i;
        head = nbr.get(i).sector;

        //-----------------------------------------------------------------
        while ( true ) {
            //- Locate the final sector of the sequence ------------------
            while ( !( nbr.get(i).cl == n.ABOVE &&
                       nbr.get( (i+1)%nnbr ).cl == n.BELOW ) ) {
                i = (i+1) % nnbr;
            }
            tail = nbr.get(i).sector;

            //- Insert null edge -----------------------------------------
            int d1;
            d1 = inSplittingPlane.doContainmentTestHalfSpace(head.next().startingVertex.position, VSDK.EPSILON);

            //System.out.println("LMEV:");
            if ( d1 != inSplittingPlane.OUTSIDE ) {
                //System.out.println("  - H1: " + tail);
                //System.out.println("  - H2: " + head);
                inSolid.lmev(tail, head, inSolid.getMaxVertexId()+1, head.startingVertex.position);
                sone.add(new _PolyhedralBoundedSolidSplitterNullEdge(tail.previous().parentEdge));
            }
            else {
                //System.out.println("  - H1: " + head);
                //System.out.println("  - H2: " + tail);
                inSolid.lmev(head, tail, inSolid.getMaxVertexId()+1, head.startingVertex.position);
                sone.add(new _PolyhedralBoundedSolidSplitterNullEdge(head.previous().parentEdge));
            }

            //- Locate the start of the next sequence --------------------
            while ( !( nbr.get(i).cl == n.BELOW &&
                       nbr.get( (i+1) % nnbr ).cl == n.ABOVE ) ) {
                i = (i+1) % nnbr;
                if ( i == start ) {
                    return;
                }
            }
        }
    }

    /**
    Vertex neighborhood classifier, as presented in section [MANT1988].14.5,
    and program 14.3.

    It appears that original algorithm from [MANT1988] assumes a left handed
    geometry or orientation or other difference to current Vitral SDK
    implementation of the boundary representation. That difference implies
    a reverse order in some cases, so `inplaneEdgesOn` check is added here
    to keep current implementation's consistency.
    */
    private static void splitClassify(PolyhedralBoundedSolid inSolid, InfinitePlane inSplittingPlane)
    {
        int i;

        sone = new ArrayList<_PolyhedralBoundedSolidSplitterNullEdge>();

        /// Following variable `nbr` from program [MANT1988].14.3.
        ArrayList<_PolyhedralBoundedSolidSplitterSectorClassification> nbr;

        for ( i = 0; i < soov.size(); i++ ) {
            nbr = getNeighborhood(soov.get(i), inSplittingPlane);
            if ( inplaneEdgesOn(nbr) ) {
                Collections.reverse(nbr);
            }
            reclassifyOnSectors(nbr, inSplittingPlane);
            reclassifyOnEdges(nbr);
            insertNullEdges(nbr, inSolid, inSplittingPlane);
        }
    }

    /**
    Following section [MANT1988].14.7.2. and program [MANT1988].14.9.
    */
    private static _PolyhedralBoundedSolidHalfEdge
    canJoin(_PolyhedralBoundedSolidHalfEdge he)
    {
        _PolyhedralBoundedSolidHalfEdge ret;
        int i;

        for ( i = 0; i < ends.size(); i++ ) {
            if ( neighbor(he, ends.get(i)) ) {
                ret = ends.get(i);
                ends.remove(i);
                tieds.add(ret);
                return ret;
            }
        }
        ends.add(he);
        return null;
    }

    private static void printNbr(ArrayList<_PolyhedralBoundedSolidSplitterSectorClassification> neighborSectorsInfo)
    {
        int i;

        for ( i = 0; i < neighborSectorsInfo.size(); i++ ) {
            System.out.println("  - " + neighborSectorsInfo.get(i));
        }
    }

    private static void printEnds()
    {
        int i;

        for ( i = 0; i < ends.size(); i++ ) {
            System.out.println("  - ends[" + i + "]: " + ends.get(i));
        }
    }

    /**
    Following section [MANT1988].14.7.2. and program [MANT1988].14.10.
    */
    private static void cut(_PolyhedralBoundedSolidHalfEdge he)
    {
        PolyhedralBoundedSolid s;

        s = he.parentLoop.parentFace.parentSolid;

        if ( he.parentEdge.rightHalf.parentLoop ==
             he.parentEdge.leftHalf.parentLoop ) {
            sonf.add(he.parentLoop.parentFace);
            s.lkemr(he.parentEdge.rightHalf, he.parentEdge.leftHalf);
        }
        else {
            s.lkef(he.parentEdge.rightHalf, he.parentEdge.leftHalf);
        }
    }

    /**
    */
    private static boolean isLoose(_PolyhedralBoundedSolidHalfEdge he)
    {
        int i;

        for ( i = 0; i < tieds.size(); i++ ) {
            if ( he == tieds.get(i) ) return false;
        }

        return true;
    }

    /**
    Following section [MANT1988].14.7.2. and program [MANT1988].14.9.
    */
    private static void splitConnect()
    {        
        int i;

        ends = new ArrayList<_PolyhedralBoundedSolidHalfEdge>();
        tieds = new ArrayList<_PolyhedralBoundedSolidHalfEdge>();

        //-----------------------------------------------------------------
        _PolyhedralBoundedSolidEdge nextedge;
        _PolyhedralBoundedSolidHalfEdge h1, h2;

        sonf = new ArrayList<_PolyhedralBoundedSolidFace>();

        Collections.sort(sone);

        //System.out.println(sone.get(0).e.rightHalf.parentLoop.parentFace.parentSolid);

        for ( i = 0; i < sone.size(); i++ ) {
            //System.out.println("- " + i + " ---------------------------------------------------------------------");
            //System.out.println(" - " + sone.get(i).e + " / " + sone.get(i).e.rightHalf.startingVertex.position);

            nextedge = sone.get(i).e;
            //System.out.println("    . edge.rightHalf: " + nextedge.rightHalf);
            h1 = canJoin(nextedge.rightHalf);

            //System.out.println("    . h1: " + h1);

            if ( h1 != null ) {
                //System.out.println("    . -> JOIN H1");
                join(h1, nextedge.rightHalf, false);
                tieds.add(nextedge.rightHalf);
                if ( !isLoose(h1.mirrorHalfEdge()) ) {
                    //System.out.println("    . -> CUT H1");
                    cut(h1);
                }
            }
            //System.out.println("    . edge.leftHalf: " + nextedge.leftHalf);
            h2 = canJoin(nextedge.leftHalf);

            //System.out.println("    . h2: " + h2);

            if ( h2 != null ) {
                //System.out.println("    . -> JOIN H2");
                join(h2, nextedge.leftHalf, false);
                tieds.add(nextedge.leftHalf);
                if ( !isLoose(h2.mirrorHalfEdge()) ) {
                    //System.out.println("    . -> CUT H2");
                    cut(h2);
                }
            }
            if ( h1 != null && h2 != null ) {
                //System.out.println("    . -> CUT DUAL");
                cut(nextedge.rightHalf);
            }

            //printEnds();
        }
    }

    /**
    Following section [MANT1988].14.8. and program [MANT1988].14.12.
    */
    private static void classify(PolyhedralBoundedSolid S,
                                 PolyhedralBoundedSolid Above,
                                 PolyhedralBoundedSolid Below)
    {
        int i;
        facesToFixAbove = new ArrayList<_PolyhedralBoundedSolidFace>();
        facesToFixBelow = new ArrayList<_PolyhedralBoundedSolidFace>();

        for ( i = 0; i < sonf.size()/2; i++ ) {
            movefac(sonf.get(i), Above);
            facesToFixAbove.add(sonf.get(i));
            movefac(sonf.get(i+sonf.size()/2), Below);
            facesToFixBelow.add(sonf.get(i+sonf.size()/2));
        }
    }

    private static boolean isNullFace(_PolyhedralBoundedSolidFace f)
    {
        int i;

        for ( i = 0; i < sonf.size(); i++ ) {
            if ( sonf.get(i) == f ) return true;
        }
        return false;
    }

    /**
    */
    private static void destroy(PolyhedralBoundedSolid inSolid)
    {
        inSolid.polygonsList =
            new CircularDoubleLinkedList<_PolyhedralBoundedSolidFace>();
        inSolid.edgesList =
            new CircularDoubleLinkedList<_PolyhedralBoundedSolidEdge>();
        inSolid.verticesList =
            new CircularDoubleLinkedList<_PolyhedralBoundedSolidVertex>();
    }

    /**
    A face `a` is "inside" other `b` (and should be an internal loop) if
    all vertices from `b` are inside the polygon of `a`.

    PRE: given faces are coplanar.
    */
    private static boolean faceInsideFace(
        _PolyhedralBoundedSolidFace a, _PolyhedralBoundedSolidFace b)
    {
        int i;
        _PolyhedralBoundedSolidLoop l;
        _PolyhedralBoundedSolidHalfEdge he, heStart;

        a.calculatePlane();
        for ( i = 0; i < b.boundariesList.size(); i++ ) {
            heStart = b.boundariesList.get(i).boundaryStartHalfEdge;
            he = heStart;
            do {
                if ( a.testPointInside(he.startingVertex.position, VSDK.EPSILON) == Geometry.OUTSIDE ) {
                    return false;
                }
                he = he.next();
            } while ( he != heStart );
        }
        return true;
    }

    /**
    */
    private static void fixNullFaces(ArrayList<_PolyhedralBoundedSolidFace> l)
    {
        if ( l.size() == 1 ) {
            l.remove(0);
            return;
        }

        int i, j;

        for ( i = 0; i < l.size(); i++ ) {
            for ( j = 0; j < l.size(); j++ ) {
                if ( i == j ) continue;
                if ( faceInsideFace(l.get(j), l.get(i) ) ) {
                    l.get(i).parentSolid.lkfmrh(l.get(i), l.get(j));
                    l.remove(j);
                    // Repeat he process with remaining list
                    fixNullFaces(l);
                    return;
                }
            }
        }
    }

    /**
    Following section [MANT1988].14.8. and program [MANT1988].14.11.
    */
    private static void splitFinish(PolyhedralBoundedSolid inSolid,
                             ArrayList<PolyhedralBoundedSolid> outSolidsAbove,
                             ArrayList<PolyhedralBoundedSolid> outSolidsBelow)
    {
        int i;
        int firstHalfSize;
        _PolyhedralBoundedSolidFace newface;
        PolyhedralBoundedSolid newAbove, newBelow;

        firstHalfSize = sonf.size();
        for ( i = 0; i < firstHalfSize; i++ ) {
            newface = inSolid.lmfkrh(sonf.get(i).boundariesList.get(1), inSolid.getMaxFaceId()+1);
            sonf.add(newface);
        }
        newAbove = new PolyhedralBoundedSolid();
        newBelow = new PolyhedralBoundedSolid();
        classify(inSolid, newAbove, newBelow);
        fixNullFaces(facesToFixAbove);
        fixNullFaces(facesToFixBelow);
        cleanup(newAbove);
        newAbove.validateModel();
        cleanup(newBelow);
        newBelow.validateModel();
        outSolidsAbove.add(newAbove);
        outSolidsBelow.add(newBelow);
        destroy(inSolid);
    }

    /**
    Given the input `inSolid` and the cutting plane `inSplittingPlane`,
    this method appends to the `outSolidsAbove` list the solids resulting
    from cutting the solid with the plane and resulting above the plane,
    similarly, `outSolidsBelow` will be appended with solid pieces
    resulting below the plane.

    Current macro-algorithm follows the strategy outlined on sections
    [MANT1988].14.1, [MANT1988].14.2 and [MANT1988].14.3 and program
    [MANT1988].14.1.
    */
    public static void split(
                      PolyhedralBoundedSolid inSolid,
                      InfinitePlane inSplittingPlane,
                      ArrayList<PolyhedralBoundedSolid> outSolidsAbove,
                      ArrayList<PolyhedralBoundedSolid> outSolidsBelow)
    {
        //-----------------------------------------------------------------
        inSolid.validateModel();
        splitGenerate(inSolid, inSplittingPlane);
        splitClassify(inSolid, inSplittingPlane);

        if ( sone.size() <= 0 ) {
            // Plane should be tested here before asuming this order!
            outSolidsAbove.add(inSolid);
            outSolidsBelow.add(new PolyhedralBoundedSolid());
            return;
        }

        splitConnect();
        splitFinish(inSolid, outSolidsAbove, outSolidsBelow);

        //-----------------------------------------------------------------
        soov = null;
        sone = null;
        sonf = null;
    }
}

//===========================================================================
//= EOF                                                                     =
//===========================================================================