triangulator.java

JAVA3D矩陈的相关类

/*
 * $RCSfile: Triangulator.java,v $
 *
 * Copyright (c) 2007 Sun Microsystems, Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistribution of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * - Redistribution in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in
 *   the documentation and/or other materials provided with the
 *   distribution.
 *
 * Neither the name of Sun Microsystems, Inc. or the names of
 * contributors may be used to endorse or promote products derived
 * from this software without specific prior written permission.
 *
 * This software is provided "AS IS," without a warranty of any
 * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
 * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
 * EXCLUDED. SUN MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL
 * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF
 * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
 * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR
 * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL,
 * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND
 * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR
 * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGES.
 *
 * You acknowledge that this software is not designed, licensed or
 * intended for use in the design, construction, operation or
 * maintenance of any nuclear facility.
 *
 * $Revision: 1.4 $
 * $Date: 2007/02/09 17:20:21 $
 * $State: Exp $
 */

// ----------------------------------------------------------------------
//
// The reference to Fast Industrial Strength Triangulation (FIST) code
// in this release by Sun Microsystems is related to Sun's rewrite of
// an early version of FIST. FIST was originally created by Martin
// Held and Joseph Mitchell at Stony Brook University and is
// incorporated by Sun under an agreement with The Research Foundation
// of SUNY (RFSUNY). The current version of FIST is available for
// commercial use under a license agreement with RFSUNY on behalf of
// the authors and Stony Brook University.  Please contact the Office
// of Technology Licensing at Stony Brook, phone [phone], for
// licensing information.
//
// ----------------------------------------------------------------------

package com.sun.j3d.utils.geometry;

import javax.vecmath.*;
import java.util.*;
import com.sun.j3d.utils.geometry.GeometryInfo;
import com.sun.j3d.internal.J3dUtilsI18N;

/**
 * Triangulator is a utility for turning arbitrary polygons into triangles
 * so they can be rendered by Java 3D.
 * Polygons can be concave, nonplanar, and can contain holes.
 * @see GeometryInfo
 */
public class Triangulator extends Object {

    GeometryInfo gInfo = null;

    int faces[] = null;
    int loops[] = null;
    int chains[] = null;
    Point2f points[] = null;
    Triangle triangles[] = null;
    ListNode list[] = null;

    Random randomGen = null;

    int numPoints = 0;
    int maxNumPoints = 0;
    int numList = 0;
    int maxNumList = 0;
    int numLoops = 0;
    int maxNumLoops = 0;
    int numTriangles = 0;
    int maxNumTriangles = 0;

    int numFaces = 0;
    int numTexSets = 0;
    //  int maxNumFaces = 0;

    int firstNode = 0;

    int numChains = 0;
    int maxNumChains = 0;

    // For Clean class.
    Point2f[] pUnsorted = null;
    int maxNumPUnsorted = 0;

    // For NoHash class.
    boolean noHashingEdges = false;
    boolean noHashingPnts = false;
    int loopMin, loopMax;
    PntNode vtxList[] = null;
    int numVtxList = 0;
    int numReflex = 0;
    int reflexVertices;

    // For Bridge class.
    Distance distances[] = null;
    int maxNumDist = 0;
    Left leftMost[] = null;
    int maxNumLeftMost = 0;

    // For Heap class.
    HeapNode heap[] = null;
    int numHeap = 0;
    int maxNumHeap = 0;
    int numZero = 0;

    // For Orientation class.
    int maxNumPolyArea = 0;
    double polyArea[] = null;

    int stripCounts[] = null;
    int vertexIndices[] = null;
    Point3f vertices[] = null;
    Object colors[] = null;
    Vector3f normals[] = null;

    boolean ccwLoop = true;

    boolean earsRandom = true;
    boolean earsSorted = true;

    int identCntr;  // Not sure what is this for. (Ask Martin)

    //  double epsilon = 1.0e-12;
    double epsilon = 1.0e-12;

    static final double ZERO = 1.0e-8;
    static final int EARS_SEQUENCE = 0;
    static final int EARS_RANDOM = 1;
    static final int EARS_SORTED = 2;


    static final int INC_LIST_BK = 100;
    static final int INC_LOOP_BK = 20;
    static final int INC_TRI_BK = 50;
    static final int INC_POINT_BK = 100;
    static final int INC_DIST_BK = 50;

    private static final int DEBUG = 0;

    /**
     * Creates a new instance of the Triangulator.
     * @deprecated This class is created automatically when needed in
     * GeometryInfo and never needs to be used directly.  Putting data
     * into a GeometryInfo with primitive POLYGON_ARRAY automatically
     * causes the triangulator to be created and used.
     */
    public Triangulator() {
	earsRandom = false;
	earsSorted = false;
    }

    /**
     * Creates a new instance of a Triangulator.
     * @deprecated This class is created automatically when needed in
     * GeometryInfo and never needs to be used directly.  Putting data
     * into a GeometryInfo with primitive POLYGON_ARRAY automatically
     * causes the triangulator to be created and used.
     */
    public Triangulator(int earOrder) {
	switch(earOrder) {
	case EARS_SEQUENCE:
	    earsRandom = false;
	    earsSorted = false;
	    break;
	case EARS_RANDOM:
	    randomGen = new Random();
	    earsRandom = true;
	    earsSorted = false;
	    break;
	case EARS_SORTED:
	    earsRandom = false;
	    earsSorted = true;
	    break;
	default:
	    earsRandom = false;
	    earsSorted = false;
	}

    }

    /**
     * This routine converts the GeometryInfo object from primitive type
     * POLYGON_ARRAY to primitive type TRIANGLE_ARRAY using polygon
     * decomposition techniques.
     * <p>
     * <pre>
     * Example of usage:
     *   Triangulator tr = new Triangulator();
     *   tr.triangulate(ginfo); // ginfo contains the geometry.
     *   shape.setGeometry(ginfo.getGeometryArray()); // shape is a Shape3D.
     *<p></pre>
     * @param gi Geometry to be triangulated
     **/
    public void triangulate(GeometryInfo gi) {
	int i, j, k;
	int sIndex = 0, index, currLoop, lastInd, ind;
	boolean proceed;
	boolean reset = false, troubles = false;

	boolean done[] = new boolean[1];
	boolean gotIt[] = new boolean[1];

	if (gi.getPrimitive() != GeometryInfo.POLYGON_ARRAY){
	    throw new IllegalArgumentException(J3dUtilsI18N.getString("Triangulator0"));
	}

	gi.indexify();

	vertices = gi.getCoordinates();
	if(vertices != null)
	    vertexIndices = gi.getCoordinateIndices();
	else
	    vertexIndices = null;

	colors = gi.getColors();
	normals = gi.getNormals();
	this.gInfo= gi;


	stripCounts = gi.getStripCounts();

	faces = gi.getContourCounts();
	if(faces == null) {
	    if(stripCounts == null)
		System.out.println("StripCounts is null! Don't know what to do.");

	    faces = new int[stripCounts.length];
	    for(i=0; i<stripCounts.length; i++)
		faces[i] = 1;
	}

	numFaces = faces.length;
	numTexSets = gInfo.getTexCoordSetCount();


	// For debugging ...
	/*
	  System.out.println("Faces (number " + faces.length + ") : ");
	  for(i=0; i<faces.length; i++) {
	  System.out.println(faces[i]  + ", ");
	  }

	  System.out.println("StripCounts (number " + stripCounts.length + ") : ");
	  for(i=0; i<stripCounts.length; i++) {
	  System.out.println(stripCounts[i]  + ", ");
	  }

	  System.out.println("Vertices (number " + vertices.length + ") : ");
	  for(i=0; i<vertices.length; i++) {
	  System.out.println(i + " x " + vertices[i].x  + " y " + vertices[i].y +
	  " z " + vertices[i].z);
	  }


	  System.out.println("VertexIndices (number " + vertexIndices.length + ") : ");

	  for(i=0; i<vertexIndices.length; i++) {
	  System.out.print(vertexIndices[i]  + ", ");
	  }
	*/

	maxNumLoops = 0;
	maxNumList = 0;
	maxNumPoints = 0;
	maxNumDist = 0;
	maxNumLeftMost = 0;
	maxNumPUnsorted = 0;

	// Compute the length of loops and list.
	for(i=0; i<faces.length; i++) {
	    maxNumLoops += faces[i];
	    for(j=0; j<faces[i]; j++, sIndex++) {
		maxNumList += (stripCounts[sIndex]+1);
	    }
	}

	// Add some incase of bridges.
	maxNumList += 20;

	loops = new int[maxNumLoops];
	list = new ListNode[maxNumList];
	// maxNumPoints = vertices.length;
	//points = new Point2f[maxNumPoints];


	// Construct data for use in triangulation.
	numVtxList = 0;
	numReflex = 0;

	numTriangles = 0;
	numChains = 0;
	numPoints = 0;
	numLoops = 0;
	numList = 0;
	sIndex = 0;
	index = 0;

	for(i=0; i<faces.length; i++) {
	    for(j=0; j<faces[i]; j++, sIndex++) {

		currLoop = makeLoopHeader();
		lastInd = loops[currLoop];

		for(k=0; k<stripCounts[sIndex]; k++) {
		    list[numList] = new ListNode(vertexIndices[index]);
		    ind = numList++;

		    insertAfter(lastInd, ind);
		    list[ind].setCommonIndex(index);

		    lastInd = ind;
		    index++;

		} // index k.

		deleteHook(currLoop);

	    } // index j.
	} // index i.


	// Done with constructing data. We can start to triangulate now.

	maxNumTriangles = maxNumList/2;
	triangles = new Triangle[maxNumTriangles];

	// set the numerical precision threshold
	setEpsilon(ZERO);

	// process the polygonal faces of the polyhedron. for every face, we
	// check whether it is a triangle or a quadrangle in order to weed out
	// simple cases which do not require the full triangulation algorithm

	/*
	  for(i=0; i<numLoops; i++)
	  System.out.println("loops[" + i + "] " + loops[i]);
	  printListData();
	*/

	int i1 = 0;
	int i2 = 0;
	for( j = 0;  j < numFaces;  ++j) {
	    ccwLoop = true;
	    done[0] = false;
	    i2 = i1 + faces[j];

	    if (faces[j] > 1) {
		proceed = true;
	    }
	    else if(Simple.simpleFace(this, loops[i1]))
		proceed = false;
	    else
		proceed = true;

	    if (proceed) {


		// Do some preprocessing here.

		// System.out.println("faces["+j+"] "+faces[j]);
		for(int lpIndex = 0; lpIndex<faces[j]; lpIndex++)
		    preProcessList(i1 + lpIndex);

		// project the polygonal face onto a plane
		Project.projectFace(this, i1, i2);

		// sort the points of this face in lexicographic order and  discard
		// duplicates

		// System.out.println("Before cleaning ...");
		// printListData();


		int removed = Clean.cleanPolyhedralFace(this, i1, i2);

		// For debugging.
		/*
		  System.out.println("After cleaning ...");
		  printListData();

		  System.out.println("\n***** " + removed +
		  " duplicate points removed for face " +
		  i1 + " *****\n");
		*/

		// determine the orientation of the polygon; the default
		// orientation is CCW for the outer polygon
		if (faces[j] == 1) {
		    // System.out.println("determineOrientation");
		    Orientation.determineOrientation(this, loops[i1]);
		}
		else {
		    // System.out.println("adjustOrientation");
		    Orientation.adjustOrientation(this, i1, i2);
		}

		// CE2 only
		if (faces[j] > 1) {
		    NoHash.prepareNoHashEdges(this, i1, i2);
		}
		else {
		    noHashingEdges = false;
		    noHashingPnts  = false;
		}


		// mark those vertices whose interior angle is convex
		for (i = i1;  i < i2;  ++i) {
		    EarClip.classifyAngles(this, loops[i]);
		}

		/*
		  System.out.println("After classifyAngles ...");
		  printListData();
		*/


		// link the holes with the outer boundary by means of "bridges"
		if (faces[j] > 1)  Bridge.constructBridges(this, i1, i2);

		// put all ears into a circular linked list
		resetPolyList(loops[i1]);
		NoHash.prepareNoHashPnts(this, i1);
		EarClip.classifyEars(this, loops[i1]);
		done[0]  = false;

		/*
		  System.out.println("Before clipEar (List)...");
		  printListData();
		  System.out.println("Before clipEar (vtxList)...");
		  printVtxList();

		  int counter = 0;
		*/

		// triangulate the polygon
		while (!done[0]) {
		    if (!EarClip.clipEar(this, done)) {
			/*
			  System.out.println(" (False case) clipEar (vtxList)...");
			  printListData();
			  printVtxList();
			*/

			if (reset) {
			    // For debugging.

			    // System.out.println("***** no further ear to clip! ***** \n");
			    // System.out.println("***** not a simple polygon, isn't it? *****\n");


			    ind = getNode();
			    resetPolyList(ind);

			    loops[i1] = ind;
			    if (Desperate.desperate(this, ind, i1, done)) {
				//  System.out.println("***** let's hope for the best *****\n");
				if (!Desperate.letsHope(this, ind)) {
				    /*
				      System.out.println("***** sorry, I can't do it! ***** \n");
				      System.out.println("***** ask a triangulation wizard, or ");
				      System.out.println("clean-up your polyhedron! ***** \n");
				    */
				    return;
				}
			    }
			    else {
				reset = false;
			    }
			}
			else {
			    // try again from scratch
			    troubles = true;
			    // System.out.println("\n***** re-classifying the ears! ***** \n");
			    ind = getNode();
			    resetPolyList(ind);

			    //	System.out.println("Before classifyEars(" + ind + ")");
			    //	printListData();

			    EarClip.classifyEars(this, ind);
			    reset = true;
			}
		    }
		    else {
			reset = false;
			/*
			  System.out.println(" (True case) clipEar (vtxList)...");

			  printVtxList();
			*/

		    }

		    if (done[0]) {
			// System.out.println("In done[0] is true");
			ind = getNextChain(gotIt);
			if (gotIt[0]) {
			    // at some point of the triangulation, we could not find
			    // any ear and the polygon was split into two parts. now
			    // we have to handle (one of) the remaining parts.
			    resetPolyList(ind);