stripifier.java

JAVA3D矩陈的相关类

/*
 * $RCSfile: Stripifier.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:20 $
 * $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 com.sun.j3d.utils.geometry.GeometryInfo;
import java.util.LinkedList;
import java.util.ArrayList;
import com.sun.j3d.internal.J3dUtilsI18N;

/**
 * The Stripifier utility will change the primitive of the GeometryInfo
 * object to Triangle Strips.  The strips are made by analyzing the
 * triangles in the original data and connecting them together.<p>
 * <p>
 * Normal Generation should be performed on the GeometryInfo object
 * <i>before</i> Stripification, for best results.  Example:<p>
 * <p>
 * <pre>
 *   GeometryInfo gi = new GeometryInfo(TRIANGLE_ARRAY);
 *   gi.setCoordinates(coordinateData);
 *
 *   NormalGenerator ng = new NormalGenerator();
 *   ng.generateNormals(gi);
 *
 *   Stripifier st = new Stripifier()
 *   st.stripify(gi);
 *
 *   Shape3D part = new Shape3D();
 *   part.setAppearance(appearance);
 *   part.setGeometry(gi.getGeometryArray());
 *   </pre>
 */
public class Stripifier {

    final boolean DEBUG = false;
    final boolean CHECK_ORIENT = false;

    static final int EMPTY = -1;

    boolean hasNormals = false;
    boolean hasTextures = false;
    int texSetCount = 0;
    boolean hasColors = false;
    boolean colorStrips = false;

    StripifierStats stats;

    int[] numNhbrs;

    /**
     * Indicates to the stripifier to collect statistics on the data
     */
    public static final int COLLECT_STATS = 0x01;

    /**
     * Creates the Stripifier object.
     */
    public Stripifier() {
    }

    /**
     * Creates the Stripifier object.
     * @param flags Flags
     * @since Java 3D 1.2.1
     */
    public Stripifier(int flags) {
	if ((flags & COLLECT_STATS) != 0) {
	    stats = new StripifierStats();
	}
    }

    /**
     * Converts the geometry contained in the GeometryInfo object into an
     * array of triangle strips.
     */
    public void stripify(GeometryInfo gi) {
	//    	System.out.println("stripify");
	long time = System.currentTimeMillis();
	// setup
	gi.convertToIndexedTriangles();
	gi.forgetOldPrim();

	// write out the gi object
	//  	System.out.println("write out the object");
	//     	gi.writeObj();

	Face[] faces = createFaceArray(gi);
	Edge[] edges = createEdgeArray(faces);
	buildAdjacencies(edges, faces);

	// print out the adjacency information
 	if (DEBUG) {
 	    for (int i = 0; i < faces.length; i++) {
 		faces[i].printVertices();
 	    }
 	    System.out.println("");
 	    for (int i = 0; i < faces.length; i++) {
 		faces[i].printAdjacency();
 	    }
 	    System.out.println("");
 	}

	Node[] faceNodes = new Node[faces.length];
	// 	Node[] queue = hybridSearch(faces, faceNodes);
	Node[] queue = dfSearch(faces, faceNodes);

	// print out the queue
 	if (DEBUG) {
 	    for (int i = 0; i < queue.length; i++) {
 		queue[i].print();
 	    }
 	    System.out.println("");
 	}

	// int "pointers" for the numbers of strips and patches from
	// hamiliton
	int[] ns = new int[1];
	int[] np = new int[1];
	ArrayList hamiltons = hamilton(queue, ns, np);
	int numStrips = ns[0];
	int numPatches = np[0];

	// print out the hamiltonians
 	if (DEBUG) {
 	    for (int i = 0; i < hamiltons.size(); i++) {
 		System.out.println("Hamiltonian: " + i);
 		ArrayList list = (ArrayList)hamiltons.get(i);
 		for (int j = 0; j < list.size(); j++) {
 		    Face face = (Face)list.get(j);
 		    face.printVertices();
 		}
 		System.out.println("");
 	    }
 	}

	// now make strips out of the hamiltonians
	ArrayList strips = stripe(hamiltons);

	// print out the strips
	if (DEBUG) {
	    for (int i = 0; i < strips.size(); i++) {
		System.out.println("Strip: " + i);
		Istream istream = (Istream)strips.get(i);
		for (int j = 0; j < istream.length; j++) {
		    System.out.println("vertex: " + istream.istream[j].index);
		}
		System.out.println("");
	    }
	}

	// concatenate the strips
     	concatenate(strips, faces);

	// print out the new strips
	if (DEBUG) {
	    System.out.println("");
	    System.out.println("concatenated strips: (" +
			       (strips.size()) + ")");
	    System.out.println("");
	    for (int i = 0; i < strips.size(); i++) {
		System.out.println("Strip: " + i);
		Istream istream = (Istream)strips.get(i);
		for (int j = 0; j < istream.length; j++) {
		    System.out.println("vertex: " + istream.istream[j].index);
		}
		System.out.println("");
	    }
	}

	// put the stripified data into the GeometryInfo object
	putBackData(gi, strips);

	// 	System.out.println("time: " + (System.currentTimeMillis()-time));
	// 	System.out.println("");

	// add to stats
	if (stats != null) {
	    stats.updateInfo(System.currentTimeMillis()-time, strips,
			     faces.length);
	}

	// 	Stat.printInfo();

	// print out strip count info
	// 	System.out.println("numStrips = " + strips.size());
	// 	System.out.println("stripCounts:");
	// 	int avg = 0;
	// 	for (int i = 0; i < strips.size(); i++) {
	// 	    System.out.print(((Istream)strips.get(i)).length + " ");
	// 	    avg += ((Istream)strips.get(i)).length;
	// 	}
	// 	System.out.println("Avg: " + ((double)avg/(double)strips.size()));
    }

    /**
     * Prints out statistical information for the stripifier: the number of
     * original triangles, the number of original vertices, the number of
     * strips created, the number of vertices, the total number of triangles,
     * the minimum strip length (in # of tris) the maximum strip length
     * (in number of tris), the average strip length (in # of tris), the
     * average number of vertices per triangle, the total time it took to
     * stripify, and the strip length (how many strips of a given length.
     * The data is cumulative over all the times the stripifier is called
     * until the stats are printed, and then they are reset.
     */
    //     public static void printStats() {
    // // 	stats.toString();
    //     }

    /**
     * Returns the stripifier stats object.
     * @exception IllegalStateException if the Stripfier has not
     * been constructed
     * with the COLLECT_STATS flag
     * @since Java 3D 1.2.1
     */
    public StripifierStats getStripifierStats() {
	if (stats == null) {
	    throw new IllegalStateException(J3dUtilsI18N.getString("Stripifier0"));
	}
	return stats;
    }

    /**
     * Creates an array of faces from the geometry in the GeometryInfo object.
     */
    Face[] createFaceArray(GeometryInfo gi) {
	int[] vertices = gi.getCoordinateIndices();
	int[] normals = gi.getNormalIndices();

	int[][] textures = null;
	int[] t1 = null;
	int[] t2 = null;
	int[] t3 = null;
	texSetCount = gi.getTexCoordSetCount();
	if (texSetCount > 0) {
	    hasTextures = true;
	    textures = new int[texSetCount][];
	    for (int i = 0; i < texSetCount; i++) {
		textures[i] = gi.getTextureCoordinateIndices(i);
	    }
	    t1 = new int[texSetCount];
	    t2 = new int[texSetCount];
	    t3 = new int[texSetCount];
	} else hasTextures = false;

	int[] colors = gi.getColorIndices();
	Face[] faces = new Face[vertices.length/3];
	int n1, n2, n3, c1, c2, c3;
	Vertex v1, v2, v3;
	int count = 0;
	for (int i = 0; i < vertices.length;) {
	    if (normals != null) {
		// 		System.out.println("hasNormals");
		hasNormals = true;
		n1 = normals[i];
		n2 = normals[i+1];
		n3 = normals[i+2];
	    }
	    else {
		// 		System.out.println("doesn't have normals");
		hasNormals = false;
		n1 = EMPTY;
		n2 = EMPTY;
		n3 = EMPTY;
	    }
	    if (hasTextures) {
		for (int j = 0; j < texSetCount; j++) {
		    t1[j] = textures[j][i];
		    t2[j] = textures[j][(i+1)];
		    t3[j] = textures[j][(i+2)];
		}
	    }
	    if (colors != null) {
		hasColors = true;
		c1 = colors[i];
		c2 = colors[i+1];
		c3 = colors[i+2];
	    }
	    else {
		hasColors = false;
		c1 = EMPTY;
		c2 = EMPTY;
		c3 = EMPTY;
	    }
	    v1 = new Vertex(vertices[i], n1, texSetCount, t1, c1);
	    v2 = new Vertex(vertices[i+1], n2, texSetCount, t2, c2);
	    v3 = new Vertex(vertices[i+2], n3, texSetCount, t3, c3);
	    if (!v1.equals(v2) && !v2.equals(v3) && !v3.equals(v1)) {
		faces[count] = new Face(count, v1, v2, v3);
		count++;
	    }
	    i+=3;
	}

	if (faces.length > count) {
	    Face[] temp = faces;
	    faces = new Face[count];
	    System.arraycopy(temp, 0, faces, 0, count);
	}
	return faces;
    }

    /**
     * Creates an array of edges from the Face array.
     */
    Edge[] createEdgeArray(Face[] faces) {
	Edge[] edges = new Edge[faces.length*3];
	Face face;
	for (int i = 0; i < faces.length; i++) {
	    face = faces[i];
	    edges[i*3] = new Edge(face.verts[0], face.verts[1], face.key);
	    edges[i*3+1] = new Edge(face.verts[1], face.verts[2], face.key);
	    edges[i*3+2] = new Edge(face.verts[2], face.verts[0], face.key);
	}
	return edges;
    }

    /**
     * Builds the adjacency graph by finding the neighbors of the edges
     */
    void buildAdjacencies(Edge[] edges, Face[] faces) {
	// 	sortEdges(edges);
	quickSortEdges(edges, 0, edges.length-1);
	// 	int i = 1;

	// set up the edge list of each face
	Edge edge;
	Face face;
	Vertex[] verts;
	boolean flag;
	int k;
	for (int i = 0; i < edges.length; i++) {
	    // edges are kept in order s.t. the ith edge is the opposite
	    // edge of the ith vertex
	    edge = edges[i];
	    face = faces[edge.face];
	    verts = face.verts;

	    flag = true;
 	    if ((!verts[0].equals(edge.v1)) && (!verts[0].equals(edge.v2))) {
		face.edges[0] = edge;
		face.numNhbrs--;
		flag = false;
	    }
 	    else if ((!verts[1].equals(edge.v1)) &&
 		     (!verts[1].equals(edge.v2))) {
		face.edges[1] = edge;
		face.numNhbrs--;
		flag = false;
	    }
 	    else if ((!verts[2].equals(edge.v1)) &&
 		     (!verts[2].equals(edge.v2))) {
		face.edges[2] = edge;
		face.numNhbrs--;
		flag = false;
	    }
	    else {
		if (DEBUG) System.out.println("error!!!  Stripifier.buildAdj");
	    }

	    // handle degenerencies
	    if (flag) {
		Vertex i1;
		// triangle degenerated to a point
 		if ((edge.v1).equals(edge.v2)) {
		    face.edges[--face.numNhbrs] = edge;
		}
		// triangle degenerated to an edge
		else {
 		    if (verts[0].equals(verts[1])) {
			i1 = verts[1];
		    }
		    else {
			i1 = verts[2];
		    }
 		    if (verts[0].equals(i1) && face.edges[0] == null) {
			face.edges[0] = edge;
			face.numNhbrs--;
		    }
 		    else if (verts[1].equals(i1) && face.edges[1] == null) {
			face.edges[1] = edge;
			face.numNhbrs--;
		    }
		    else {
			face.edges[2] = edge;
			face.numNhbrs--;
		    }
		}
	    }
	}

	// build the adjacency information by pairing up every two triangles
	// that share the same edge
	int i = 0; int j = 0;
	int j1, j2;
	while (i < (edges.length-1)) {
	    j = i+1;
	    if (edges[i].equals(edges[j])) {
		// determine the orientations of the common edge in the two
		// adjacent triangles.  Only set them to be adjacent if they
		// are opposite
		j1 = edges[i].face;
		j2 = edges[j].face;
		if (j1 != j2) { // set up the two faces as neighbors
		    edge = edges[i];
		    face = faces[j1];
		    k = face.getEdgeIndex(edge);
		    if ((edge.v1.equals(face.verts[(k+1)%3])) &&
			(edge.v2.equals(face.verts[(k+2)%3]))) {
			flag = false;
		    }
		    else flag = true;

		    edge = edges[j];
		    face = faces[j2];
		    k = face.getEdgeIndex(edge);
		    if ((edge.v1.equals(face.verts[(k+1)%3])) &&
			(edge.v2.equals(face.verts[(k+2)%3]))) {
			flag = flag;
		    }
		    else flag = (!flag);

		    if (flag) {
			edges[i].face = j2;
			edges[j].face = j1;
			(faces[j1].numNhbrs)++;
			(faces[j2].numNhbrs)++;
			j++;
		    }
		    else edges[i].face = EMPTY;
		}
		else edges[i].face = EMPTY;
	    }
	    else edges[i].face = EMPTY;
	    i=j;