polyhedralboundedsolid.java

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

//===========================================================================
//=-------------------------------------------------------------------------=
//= Module history:                                                         =
//= - November 18 2006 - Oscar Chavarro: Original base version              =
//= - January 3 2007 - Oscar Chavarro: First phase implementation           =
//= - April 21 2007 - Oscar Chavarro: First working version with basics     =
//=-------------------------------------------------------------------------=
//= References:                                                             =
//= [MANT1988] Mantyla Martti. "An Introduction To Solid Modeling",         =
//=     Computer Science Press, 1988.                                       =
//= [.wMANT2008] Mantyla Martti. "Personal Home Page", <<shar>> archive     =
//=     containing the C programs from [MANT1988]. Available at             =
//=     http://www.cs.hut.fi/~mam . Last visited April 12 / 2008.           =
//===========================================================================

package vsdk.toolkit.environment.geometry;

import java.util.ArrayList;

import java.text.DecimalFormat;
import java.text.FieldPosition;

import vsdk.toolkit.common.VSDK;
import vsdk.toolkit.common.Vector3D;
import vsdk.toolkit.common.Matrix4x4;
import vsdk.toolkit.common.CircularDoubleLinkedList;
import vsdk.toolkit.common.Ray;
import vsdk.toolkit.environment.geometry.polyhedralBoundedSolidNodes._PolyhedralBoundedSolidFace;
import vsdk.toolkit.environment.geometry.polyhedralBoundedSolidNodes._PolyhedralBoundedSolidLoop;
import vsdk.toolkit.environment.geometry.polyhedralBoundedSolidNodes._PolyhedralBoundedSolidHalfEdge;
import vsdk.toolkit.environment.geometry.polyhedralBoundedSolidNodes._PolyhedralBoundedSolidEdge;
import vsdk.toolkit.environment.geometry.polyhedralBoundedSolidNodes._PolyhedralBoundedSolidVertex;

/**
This class encapsulates a polyhedral boundary representation for 2-manifold
solids, as presented in [MANT1988]. As noted in [MANT1988].10.2.1:
The `PolyhedralBoundedSolid` class uses a five-level hierarchic data structure,
consisting of:
  - PolyhedralBoundedSolid
  - _PolyhedralBoundedSolidFace
  - _PolyhedralBoundedSolidLoop
  - _PolyhedralBoundedSolidHalfEdge (and _PolyhedralBoundedSolidEdge)
  - _PolyhedralBoundedSolidVertex
Current class forms the root element that gives access to faces, edges and
vertices of the model through agregations in CircularDoubleLinkedList's.
*/
public class PolyhedralBoundedSolid extends Solid {
    /// Check the general attribute description in superclass Entity.
    public static final long serialVersionUID = 20061118L;

    public static final int PLUS = 1;
    public static final int MINUS = 0;

    //= Main boundary representation solid data structure =============
    public CircularDoubleLinkedList<_PolyhedralBoundedSolidFace> polygonsList;
    public CircularDoubleLinkedList<_PolyhedralBoundedSolidEdge> edgesList;
    public CircularDoubleLinkedList<_PolyhedralBoundedSolidVertex> verticesList;
    // Auxiliary data structures for storage of parcial results and 
    // preprocessing
    private double[] minMax;
    public int maxVertexId;
    public int maxFaceId;
    private boolean modelIsValid;
    private GeometryIntersectionInformation lastInfo;

    //=================================================================
    public PolyhedralBoundedSolid()
    {
        polygonsList =
            new CircularDoubleLinkedList<_PolyhedralBoundedSolidFace>();
        edgesList =
            new CircularDoubleLinkedList<_PolyhedralBoundedSolidEdge>();
        verticesList =
            new CircularDoubleLinkedList<_PolyhedralBoundedSolidVertex>();
        minMax = null;
        maxVertexId = -1;
        maxFaceId = -1;
        modelIsValid = false;
        lastInfo = new GeometryIntersectionInformation();
    }

    //= SUPPORT MACROS FOR BASIC DATASTRUCTURE MANIPULATION ===========

    /**
    Find the face identified with `id`. Returns null if face not found,
    or current founded face otherwise.
    Build based over function `fface` in program [MANT1988].11.9.
    */
    public _PolyhedralBoundedSolidFace
    findFace(int id)
    {
        int i;
        _PolyhedralBoundedSolidFace facei;

        for ( i = 0; i < polygonsList.size(); i++ ) {
            facei = polygonsList.get(i);
            if ( facei.id == id ) {
                return facei;
            }
        }
        return null;
    }

    public _PolyhedralBoundedSolidVertex
    findVertex(int id)
    {
        int i;
        _PolyhedralBoundedSolidVertex v;

        for ( i = 0; i < verticesList.size(); i++ ) {
            v = verticesList.get(i);
            if ( v.id == id ) {
                return v;
            }
        }
        return null;
    }

    /**
    addhe: addHalfEdge.
    As described in section [MANT1988].11.2.2 and following the structure
    of sample program [MANT1988].11.3, there exist the need for a halfedge
    procedure creation where some special cases should be considered.
    */
    private _PolyhedralBoundedSolidHalfEdge addhe(
        _PolyhedralBoundedSolidEdge e,
        _PolyhedralBoundedSolidVertex v,
        _PolyhedralBoundedSolidHalfEdge where,
        int sign
    )
    {
        _PolyhedralBoundedSolidHalfEdge he;

        if ( where == null ) {
            VSDK.reportMessage(this, VSDK.FATAL_ERROR, "addhe",
            "Trying to build a halfedge from another, non-existing halfedge!");
        }
        if ( e == null ) {
            VSDK.reportMessage(this, VSDK.FATAL_ERROR, "addhe",
            "Trying to associate a halfedge to a non-existing edge!");
        }

        if ( where.parentEdge == null ) {
            he = where;
          }
          else {
            he =
                new _PolyhedralBoundedSolidHalfEdge(v, where.parentLoop, this);
            where.parentLoop.halfEdgesList.insertBefore(he, where);
            he.startingVertex = v;
        }
        he.parentEdge = e;
        he.parentLoop = where.parentLoop;

        if ( sign == PolyhedralBoundedSolid.PLUS ) {
            e.leftHalf = he;
          }
          else {
            e.rightHalf = he;
        }

        return he;
    }

    //= LOW LEVEL EULER OPERATIONS ====================================

    /**
    mvfs: MakeVertexFaceSolid.
    Operator mvfs creates a new solid representation that consist of
    one face and one vertex with coordinates specified in `p`. This
    operator has one single level of implementation (no "low level"
    or "high level versions") as other operator has.

    As described in sections [MANT1988].9.2.2, [MANT1988].11.3.1 and
    [MANT1988].11.5.1; and following the structure of sample program
    [MANT1988].11.5, this method should be used as part of every
    PolyhedralBoundedSolid constructor process, to yield to an empty
    skeletal boundary representation solid.

    Note that all correctly builded solids are the result of a series of
    Euler operations over this generated skeleton, the "single skeletal
    plane model" ([MANT1988].9.2.2). The "solid" created here may not
    satisfy the intuitive notion of a solid object. Nevertheless, it is
    useful as the initial state of creating a boundary model with a sequence
    of Euler operations.
    */
    public void mvfs(Vector3D p, int vertexId, int faceId)
    {
        _PolyhedralBoundedSolidFace newFace;
        _PolyhedralBoundedSolidLoop newLoop;
        _PolyhedralBoundedSolidHalfEdge newHalfEdge;
        _PolyhedralBoundedSolidVertex newVertex;

        if ( vertexId > maxVertexId ) maxVertexId = vertexId;
        if ( faceId > maxFaceId ) maxFaceId = faceId;

        minMax = null;
        newFace = new _PolyhedralBoundedSolidFace(this, faceId);
        newLoop = new _PolyhedralBoundedSolidLoop(newFace);
        newVertex = new _PolyhedralBoundedSolidVertex(this, p, vertexId);
        newHalfEdge =
            new _PolyhedralBoundedSolidHalfEdge(newVertex, newLoop, this);
        newLoop.halfEdgesList.add(newHalfEdge);
        newLoop.boundaryStartHalfEdge = newHalfEdge;
    }

    /**
    kvfs: KillVertexFaceSolid.
    Operator kvfs is the inverse of mvfs, and removes the contents of
    current solid, given that it is the skeletal solid. The solid must
    consist of a single face and vertex only.

    As described in sections [MANT1988].9.2.2 and [MANT1988].11.5.1 method
    can be used as part of final PolyhedralBoundedSolid destructor process,
    starting from an empty skeletal boundary representation solid.

    Note that all correctly builded solids can be destroyed with a series of
    Euler operations over yielding to the "single skeletal plane model" 
    [MANT1988].9.2.2.
    */
    public void kvfs()
    {
        if ( polygonsList.size() != 1 ) {
            VSDK.reportMessage(this, VSDK.FATAL_ERROR, "kvfs",
            "Not skeletal solid, not having exactly one loop!");
            return;
        }
        if ( edgesList.size() != 0 ) {
            VSDK.reportMessage(this, VSDK.FATAL_ERROR, "kvfs",
            "Not skeletal solid, having some edges!");
            return;
        }
        if ( verticesList.size() != 1 ) {
            VSDK.reportMessage(this, VSDK.FATAL_ERROR, "kvfs",
            "Not skeletal solid, not having exactly one vertex !");
            return;
        }
        polygonsList.remove(0);
        verticesList.remove(0);
    }

    /**
    lmev: LowlevelMakeEdgeVertex (vertex splitting operation).
    Operator lmev "splits" the vertex pointed at by `he1` and `he2`,
    and adds a new vertex and new edge between the resulting two vertices.
    The coordinates specified by `p` are assigned to the new vertex position.
    If `he1` and `he2` are the same halfedge, the new vertex and edge are
    added into the face of `he1`. The new edge is oriented from the new
    vertex to the old one.

    As described in sections [MANT1988].9.2.3, [MANT1988].11.3.2 and
    [MANT1988].11.5.1; and following the structure of sample program
    [MANT1988].11.6, this method has the effect of adding one new vertex
    and one new edge to the solid model.
    */
    public void lmev(_PolyhedralBoundedSolidHalfEdge he1,
                     _PolyhedralBoundedSolidHalfEdge he2,
                     int vertexID, Vector3D p)
    {
        //-----------------------------------------------------------------
        _PolyhedralBoundedSolidHalfEdge he;
        _PolyhedralBoundedSolidVertex newVertex;
        _PolyhedralBoundedSolidEdge newEdge;
        boolean strutCase = false;

        if ( he1 == he2 ) {
            strutCase = true;
        }

        if ( he1 == null && he2 == null ) {
            VSDK.reportMessage(this, VSDK.WARNING, "lmev",
            "Calling with (both) empty halfedges!");
            return;
        }

        if ( he1 == null ) {
            VSDK.reportMessage(this, VSDK.WARNING, "lmev",
            "Calling with (first) empty halfedge!");
            return;
        }

        if ( he2 == null ) {
            VSDK.reportMessage(this, VSDK.WARNING, "lmev",
            "Calling with (second) empty halfedge!");
            return;
        }

        if ( he1.startingVertex != he2.startingVertex ) {
            VSDK.reportMessage(this, VSDK.FATAL_ERROR, "lmev",
            "Halfedges not starting at the same vertex. Not supported case!");
            return;
        }

        if ( vertexID > maxVertexId ) maxVertexId = vertexID;

        newEdge = new _PolyhedralBoundedSolidEdge(he1.parentLoop.parentFace.parentSolid);
        newVertex = new _PolyhedralBoundedSolidVertex(he1.parentLoop.parentFace.parentSolid, p, vertexID);
        minMax = null;

        //-----------------------------------------------------------------
        he = he1;
        while ( he != he2 ) {
            he.startingVertex = newVertex;
            he = (he.mirrorHalfEdge()).next();
        }

        //-----------------------------------------------------------------
        // Original [MANT1988] code...
        //addhe(newEdge, newVertex, he2, PLUS);
        //addhe(newEdge, he2.startingVertex, he1, MINUS);

        // Modified code...
        _PolyhedralBoundedSolidVertex oldVertex = he2.startingVertex;
        if ( strutCase ) {
            addhe(newEdge, oldVertex, he2, PLUS);
            addhe(newEdge, newVertex, he1, MINUS);
        }
        else {
            addhe(newEdge, newVertex, he2, PLUS);
            addhe(newEdge, he2.startingVertex, he1, MINUS);
        }

        //-----------------------------------------------------------------
        newVertex.emanatingHalfEdge = he2.previous();
        he2.startingVertex.emanatingHalfEdge = he2;
    }

    /**
    lkev: LowlevelKillEdgeVertex (vertex joining operation).
    Operator lkev is the inverse of lmev. It removes the edge pointed at
    by `he1` and `he2`, and "joins" the two vertices `he1.startingVertex`
    and `he2.startingVertex` which must be distinct (but can, of course,
    correspond with geometrically identical points). Vertex
    `he1->startingVertex` is removed.

    As described in sections [MANT1988].9.2.3, [MANT1988].11.3.4 and
    [MANT1988].11.5.1 this method has the effect of removing one vertex
    and one edge from the solid model.

    Current implementation is not explained on [MANT1988], but leaved as
    problem [MANT1988].11.3.
    */
    public void lkev(_PolyhedralBoundedSolidHalfEdge he1,
                     _PolyhedralBoundedSolidHalfEdge he2)
    {
        //-----------------------------------------------------------------
        if ( he1 == null || he2 == null ) {
            VSDK.reportMessage(this, VSDK.WARNING, "lkev",
            "Two halfedges are needed for this Euler operator two work!");
            return;
        }

        if ( he1.parentEdge != he2.parentEdge ) {
            VSDK.reportMessage(this, VSDK.WARNING, "lkev",
            "Given halfedges must lie over the same edge!");
            return;
        }        

        if ( he1 == he2 ) {