_polyhedralboundedsolidface.java

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

//===========================================================================
//=-------------------------------------------------------------------------=
//= Module history:                                                         =
//= - November 18 2006 - Oscar Chavarro: Original base version              =
//= - January 3 2007 - Oscar Chavarro: First phase implementation           =
//=-------------------------------------------------------------------------=
//= References:                                                             =
//= [GLAS1989] Glassner, Andrew. "An introduction to ray tracing",          =
//=     Academic Press, 1989.                                               =
//= [MANT1988] Mantyla Martti. "An Introduction To Solid Modeling",         =
//=     Computer Science Press, 1988.                                       =
//===========================================================================

package vsdk.toolkit.environment.geometry.polyhedralBoundedSolidNodes;

import java.util.ArrayList;

import vsdk.toolkit.common.CircularDoubleLinkedList;
import vsdk.toolkit.common.FundamentalEntity;
import vsdk.toolkit.common.Vector3D;
import vsdk.toolkit.common.VSDK;
import vsdk.toolkit.common.ArrayListOfDoubles;
import vsdk.toolkit.environment.geometry.Geometry;
import vsdk.toolkit.environment.geometry.PolyhedralBoundedSolid;
import vsdk.toolkit.environment.geometry.InfinitePlane;
import vsdk.toolkit.environment.Camera;
import vsdk.toolkit.processing.ComputationalGeometry;

/**
As noted in [MANT1988].10.2.1, class `_PolyhedralBoundedSolidFace` represents
one planar face of the polyhedron represented by the half-edge data
structure in a `PolyhedralBoundedSolid`. A face is defined as a planar
polygon whose interior is connected, considering that could be convex or
concave, with or without holes (but without "islands", in which case there
are more than one polygon), and based in this, a polygon can have more than
one polygonal boundary.

Note that in current implementation, the first loop in the list of boundaries
is the outer boundary, and the others are "rings" or hole loops.

Note that in the sake of simplify and eficiency current programming 
implementation of this class exhibit public access attributes. It is important
to note that those attributes will only be accessed directly from related 
classes in the same package
(vsdk.toolkit.environment.geometry.polyhedralBoundedSolidNodes) and
from methods in the `PolyhedralBoundedSolid` class, and that they should
not be used from outer classes.
*/
public class _PolyhedralBoundedSolidFace extends FundamentalEntity {
    /// Check the general attribute description in superclass Entity.
    public static final long serialVersionUID = 20061118L;

    /// Defined as presented in [MANT1988].10.2.1
    public int id;

    /// Defined as presented in [MANT1988].10.2.1
    public PolyhedralBoundedSolid parentSolid;

    /// Each face should have at least one loop, corresponding to the
    /// external boundary. Each subsequent loop will be interpreted as a ring.
    /// Defined as presented in [MANT1988].10.2.1
    public CircularDoubleLinkedList<_PolyhedralBoundedSolidLoop> boundariesList;
    /// Defined as presented in [MANT1988].10.2.1
    public InfinitePlane containingPlane;

    /// Used by method testPointInside. Normally null, not null value when
    /// a point intersected an edge. Following problem [MANT1988].13.3. and
    /// variable `hitthe`  from program [MANT1988].15.3.
    public _PolyhedralBoundedSolidHalfEdge lastIntersectedHalfedge;

    /// Used by method testPointInside. Normally null, not null value when
    /// a point intersected a vertex.  Following problem [MANT1988].13.3. and
    /// variable `hitvertex`  from program [MANT1988].15.3.
    public _PolyhedralBoundedSolidVertex lastIntersectedVertex;

    //=================================================================

    public _PolyhedralBoundedSolidFace(PolyhedralBoundedSolid parent, int id)
    {
        this.id = id;
        parentSolid = parent;
        parentSolid.polygonsList.add(this);
        boundariesList =
            new CircularDoubleLinkedList<_PolyhedralBoundedSolidLoop>();
        lastIntersectedHalfedge = null;
    }

    /**
    Find the halfedge from vertex `vn1` to vertex `vn2`. 
    Returns null if halfedge not found, or current founded halfedge otherwise.
    Build based over function `fhe` in program [MANT1988].11.9.
    */
    public _PolyhedralBoundedSolidHalfEdge findHalfEdge(int vn1, int vn2)
    {
        _PolyhedralBoundedSolidLoop loop;
        _PolyhedralBoundedSolidHalfEdge he;
        int i;

        for ( i = 0; i < boundariesList.size(); i++ ) {
            loop = boundariesList.get(i);
            he = loop.halfEdgeVertices(vn1, vn2);
            if ( he != null ) {
                return he;
            }
        }
        return null;
    }

    /**
    Find the first halfedge originating from vertex `vn1`.
    Returns null if halfedge not found, or current founded halfedge otherwise.
    */
    public _PolyhedralBoundedSolidHalfEdge findHalfEdge(int vn1)
    {
        _PolyhedralBoundedSolidLoop loop;
        _PolyhedralBoundedSolidHalfEdge he;
        int i;

        for ( i = 0; i < boundariesList.size(); i++ ) {
            loop = boundariesList.get(i);
            he = loop.firstHalfEdgeAtVertex(vn1);
            if ( he != null ) {
                return he;
            }
        }
        return null;
    }

    /**
    PRE: current face points must be all co-planar. Previous solid validation
    should be made!
    POST: current face contains a plane containing the face.

    Current implementation takes in to account only the first loop.
    */
    public void
    calculatePlane()
    {
        if ( boundariesList.size() < 1 ) {
            return;
        }

        _PolyhedralBoundedSolidLoop loop;
        _PolyhedralBoundedSolidHalfEdge he, heStart;

        loop = boundariesList.get(0);

        he = loop.boundaryStartHalfEdge;
        if ( he == null ) {
            // Loop without starting halfedge
            return;
        }
        heStart = he;

        boolean colinearPoints = true;

        do {
            // This is only considering the first three vertices, and not taking
            // in to account the possible case of too close vertices. Should be
            // replaced to consider the full vertices set.

            //- Do normal estimation on a three set of points -----------------
            Vector3D p0 = null, p1 = null;
            Vector3D p2 = null;
            Vector3D a, b;
            Vector3D n;

            p0 = he.startingVertex.position;
            p1 = he.next().startingVertex.position;
            p2 = he.next().next().startingVertex.position;

            a = p1.substract(p0);    a.normalize();
            b = p2.substract(p0);    b.normalize();
            n = a.crossProduct(b);

            if ( n.length() < VSDK.EPSILON ||
                 a.length() < VSDK.EPSILON ||
                 b.length() < VSDK.EPSILON ) {
                he = he.next();
                continue;
            }
            else {
                colinearPoints = false;
            }

            n.normalize();
            containingPlane = new InfinitePlane(n, p0);

            //- Determine if p1 region is convex or concave -------------------
            Vector3D middle = a.add(b);
            Vector3D testPoint;
            middle.normalize();
            middle = middle.multiply(10.0*VSDK.EPSILON);

            testPoint = p0.add(middle);

            //- If concave, swap normal direction -----------------------------
            if ( testPointInside(testPoint, VSDK.EPSILON) == Geometry.OUTSIDE ) {
                n = n.multiply(-1.0);
            }
            containingPlane = new InfinitePlane(n, p0);

            he = he.next();

        } while ( he != heStart && colinearPoints );

        /*
        do {
            he = he.next();
            if ( he == null ) {
                // Loop is not closed!
                break;
            }
            // ?
        } while( he != heStart );
        */

    }

    /**
    @coord: 1 means drop x, 2 means drop y and 3 means drop z
    */
    private void dropCoordinate(Vector3D in, Vector3D out, int coord)
    {
        out.z = 0;

        switch ( coord ) {
          case 1:
            // Drop X
            out.x = in.y;
            out.y = in.z;
            break;
          case 2:
            // Drop Y
            out.x = in.x;
            out.y = in.z;
            break;
          case 3: default:
            // Drop Z
            out.x = in.x;
            out.y = in.y;
            break;
        }
    }

    /**
    Given a point p in the containing plane of this face, the method returns:
    @return Geometry.OUTSIDE if point is outside polygon, Geometry.LIMIT if
    its in the polygon border, Geometry.INSIDE if point is inside border.
    PRE:
    - Polygon is planar
    - Point p is in the containing plane
    The structure of this algorithm follows the one outlined in
    [GLAS1989].2.3.2. with a little variation in the handlig of `sh`
    which allows this code to manage internal loops.

    Functionally, this is equivalent to procedure `contfv` proposed at
    problem [MANT1988].13.3. For [MANT1988] based algorithms compatibility
    this method supports the generation oof extra information, and
    stores .

    When point is outside the border of the polygon, this method writes