generalizedstrip.java

JAVA3D矩陈的相关类

/*
 * $RCSfile: GeneralizedStrip.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.3 $
 * $Date: 2007/02/09 17:20:22 $
 * $State: Exp $
 */

package com.sun.j3d.utils.geometry.compression;

import com.sun.j3d.internal.J3dUtilsI18N;


/**
 * This class provides static methods to support topological
 * transformations on generalized strips.  This is used by the
 * GeometryDecompressor.  These methods only need to look at the
 * vertex replacement flags to determine how the vertices in the strip
 * are connected.  The connections are rearranged in different ways to
 * transform generalized strips to GeometryArray representations.
 *
 * @see GeneralizedStripFlags
 * @see GeneralizedVertexList
 * @see GeometryDecompressor
 */
class GeneralizedStrip {
    private static final boolean debug = false ;

    // Private convenience copies of various constants.
    private static final int CW  =
	GeneralizedStripFlags.FRONTFACE_CW ;
    private static final int CCW =
	GeneralizedStripFlags.FRONTFACE_CCW ;
    private static final int RESTART_CW   =
	GeneralizedStripFlags.RESTART_CW ;
    private static final int RESTART_CCW  =
	GeneralizedStripFlags.RESTART_CCW ;
    private static final int REPLACE_MIDDLE =
	GeneralizedStripFlags.REPLACE_MIDDLE ;
    private static final int REPLACE_OLDEST =
	GeneralizedStripFlags.REPLACE_OLDEST ;

    /**
     * The IntList is like an ArrayList, but avoids the Integer
     * object wrapper and accessor overhead for simple lists of ints.
     */
    static class IntList {
	/**
	 * The array of ints.
	 */
	int ints[] ;

	/**
	 * The number of ints in this instance.
	 */
	int count ;

	/**
	 * Construct a new empty IntList of the given initial size.
	 * @param initialSize initial size of the backing array
	 */
	IntList(int initialSize) {
	    ints = new int[initialSize] ;
	    count = 0 ;
	}

	/**
	 * Constructs an IntList with the given contents.
	 * @param ints the array of ints to use as the contents
	 */
	IntList(int ints[]) {
	    this.ints = ints ;
	    this.count = ints.length ;
	}

	/**
	 * Add a new int to the end of this list.
	 * @param i the int to be appended to this list
	 */
	void add(int i) {
	    if (count == ints.length) {
		int newints[] = new int[2*count] ;
		System.arraycopy(ints, 0, newints, 0, count) ;
		ints = newints ;
		if (debug)
		    System.out.println
			("GeneralizedStrip.IntList: reallocated " +
			 (2*count) + " ints") ;
	    }
	    ints[count++] = i ;
	}

	/**
	 * Trim the backing array to the current count and return the
	 * resulting backing array.
	 */
	int[] trim() {
	    if (count != ints.length) {
		int newints[] = new int[count] ;
		System.arraycopy(ints, 0, newints, 0, count) ;
		ints = newints ;
	    }
	    return ints ;
	}

	/**
	 * Fill the list with consecutive integers starting from 0.
	 */
	void fillAscending() {
	    for (int i = 0 ; i < ints.length ; i++)
		ints[i] = i ;

	    count = ints.length ;
	}

	public String toString() {
	    String s = new String("[") ;
	    for (int i = 0 ; i < count-1 ; i++)
		s = s + Integer.toString(ints[i]) + ", " ;
	    return s + Integer.toString(ints[count-1]) + "]" ;
	}
    }

    /**
     * The StripArray class is used as the output of some conversion methods
     * in the GeneralizedStrip class.
     */
    static class StripArray {
	/**
	 * A list of indices into the vertices of the original generalized
	 * strip.  It specifies the order in which vertices in the original
	 * strip should be followed to build GeometryArray objects.  
	 */
	IntList vertices ;

	/**
	 * A list of strip counts.
	 */
	IntList stripCounts ;

	/**
	 * Creates a StripArray with the specified vertices and stripCounts.
	 * @param vertices IntList containing vertex indicies.
	 * @param stripCounts IntList containing strip lengths.
	 */
	StripArray(IntList vertices, IntList stripCounts) {
	    this.vertices = vertices ;
	    this.stripCounts = stripCounts ;
	}
    }

    /**
     * Interprets the vertex flags associated with a class implementing
     * GeneralizedStripFlags, constructing and returning a 2-element array of
     * StripArray objects.  The first StripArray will contain triangle strips
     * and the second will contain triangle fans.
     *
     * @param vertices an object implementing GeneralizedStripFlags
     * @param frontFace a flag, either GeneralizedStripFlags.FRONTFACE_CW or
     * GeneralizedStripFlags.FRONTFACE_CCW, indicating front face winding
     * @return a 2-element array containing strips in 0 and fans in 1
     */
    static StripArray[] toStripsAndFans(GeneralizedStripFlags vertices,
					int frontFace) {

	int size = vertices.getFlagCount() ;

	// Initialize IntLists to worst-case sizes.
	IntList stripVerts  = new IntList(size*3) ;
	IntList fanVerts    = new IntList(size*3) ;
	IntList stripCounts = new IntList(size) ;
	IntList fanCounts   = new IntList(size) ;

	toStripsAndFans(vertices, frontFace,
			stripVerts, stripCounts, fanVerts, fanCounts) ;

	// Construct the StripArray output.
	StripArray sa[] = new StripArray[2] ;

	if (stripCounts.count > 0)
	    sa[0] = new StripArray(stripVerts, stripCounts) ;

	if (fanCounts.count > 0)
	    sa[1] = new StripArray(fanVerts, fanCounts) ;

	return sa ;
    }

    private static void toStripsAndFans(GeneralizedStripFlags vertices,
					int frontFace,
					IntList stripVerts,
					IntList stripCounts,
					IntList fanVerts,
					IntList fanCounts) {
	int newFlag, curFlag, winding ;
	int v, size, stripStart, stripLength ;
	boolean transition = false ;

	stripStart = 0 ;
	stripLength = 3 ;
	curFlag = vertices.getFlag(0) ;
	winding = (curFlag == RESTART_CW ? CW : CCW) ;
	size = vertices.getFlagCount() ;

	// Vertex replace flags for the first 3 vertices are irrelevant since
	// they can only define a single triangle.  The first meaningful
	// replace flag starts at the 4th vertex.
	v = 3 ;
	if (v < size)
	    curFlag = vertices.getFlag(v) ;

	while (v < size) {
	    newFlag = vertices.getFlag(v) ;

	    if ((newFlag == curFlag) &&
		(newFlag != RESTART_CW) && (newFlag != RESTART_CCW)) {
		// The last flag was the same as this one, and it wasn't a
		// restart: proceed to the next vertex.
		stripLength++ ;
		v++ ;

	    } else {
		// Either this vertex flag changed from the last one, or
		// the flag explicitly specifies a restart: process the
		// last strip and start up a new one.
		if (curFlag == REPLACE_MIDDLE)
		    addFan(fanVerts, fanCounts, stripStart, stripLength,
			   frontFace, winding, transition) ;
		else
		    addStrip(stripVerts, stripCounts, stripStart, stripLength,
			     frontFace, winding) ;

		// Restart: skip to the 4th vertex of the new strip.
		if ((newFlag == RESTART_CW) || (newFlag == RESTART_CCW)) {
		    winding = (newFlag == RESTART_CW ? CW : CCW) ;
		    stripStart = v ;
		    stripLength = 3 ;
		    v += 3 ;
		    transition = false ;
		    if (v < size)
			curFlag = vertices.getFlag(v) ;
		}
		// Strip/fan transition:  decrement start of strip.
		else {
		    if (newFlag == REPLACE_OLDEST) {
			// Flip winding order when transitioning from fans
			// to strips.
			winding = (winding == CW ? CCW : CW) ;
			stripStart = v-2 ;
			stripLength = 3 ;
		    } else {
			// Flip winding order when transitioning from
			// strips to fans only if the preceding strip has
			// an even number of vertices.
			if ((stripLength & 0x01) == 0)
			    winding = (winding == CW ? CCW : CW) ;
			stripStart = v-3 ;
			stripLength = 4 ;
		    }
		    v++ ;
		    transition = true ;
		    curFlag = newFlag ;
		}
	    }
	}
	    
	// Finish off the last strip or fan.
	// If v > size then the strip is degenerate.
	if (v == size)
	    if (curFlag == REPLACE_MIDDLE)
		addFan(fanVerts, fanCounts, stripStart, stripLength,
		       frontFace, winding, transition) ;
	    else
		addStrip(stripVerts, stripCounts, stripStart, stripLength,
			 frontFace, winding) ;
	else
	    throw new IllegalArgumentException
		(J3dUtilsI18N.getString("GeneralizedStrip0")) ;

	if (debug) {
	    System.out.println("GeneralizedStrip.toStripsAndFans") ;
	    if (v > size)
		System.out.println(" ended with a degenerate triangle:" +
				   " number of vertices: " + (v-size)) ;
	    
	    System.out.println("\n number of strips: " + stripCounts.count) ;
	    if (stripCounts.count > 0) {
		System.out.println(" number of vertices: " + stripVerts.count) ;
		System.out.println(" vertices/strip: " +
				   (float)stripVerts.count/stripCounts.count) ;
		System.out.println(" strip counts: " + stripCounts.toString()) ;
		// System.out.println(" indices: " + stripVerts.toString()) ;
	    }

	    System.out.println("\n number of fans: " + fanCounts.count) ;
	    if (fanCounts.count > 0) {
		System.out.println(" number of vertices: " + fanVerts.count) ;
		System.out.println(" vertices/strip: " +
				   (float)fanVerts.count/fanCounts.count) ;
		System.out.println(" fan counts: " + fanCounts.toString()) ;
		// System.out.println(" indices: " + fanVerts.toString()) ;
	    }
	    System.out.println("\n total vertices: " +
			       (stripVerts.count + fanVerts.count) + 
			       "\n original number of vertices: " + size +
			       "\n") ;
	}
    }

    //
    // Java 3D specifies that the vertices of front-facing polygons
    // have counter-clockwise (CCW) winding order when projected to
    // the view surface. Polygons with clockwise (CW) vertex winding
    // will be culled as back-facing by default.
    // 
    // Generalized triangle strips can flip the orientation of their
    // triangles with the RESTART_CW and RESTART_CCW vertex flags.
    // Strips flagged with an orientation opposite to what has been
    // specified as front-facing must have their windings reversed in
    // order to have the correct face orientation when represented as
    // GeometryArray objects.
    //
    private static void addStrip(IntList stripVerts,
				 IntList stripCounts,
				 int start, int length,
				 int frontFace, int winding) {
	int vindex = start ;

	if (winding == frontFace) {
	    // Maintain original order.
	    stripCounts.add(length) ;
	    while (vindex < start + length) {
		stripVerts.add(vindex++) ;
	    }
	} else if ((length & 0x1) == 1) {
	    // Reverse winding order if number of vertices is odd.
	    stripCounts.add(length) ;
	    vindex += length-1 ;
	    while (vindex >= start) {
		stripVerts.add(vindex--) ;
	    }
	} else if (length == 4) {
	    // Swap middle vertices.
	    stripCounts.add(4) ;
	    stripVerts.add(vindex) ;
	    stripVerts.add(vindex+2) ;
	    stripVerts.add(vindex+1) ;
	    stripVerts.add(vindex+3) ;
	} else {
	    // Make the 1st triangle a singleton with reverse winding.
	    stripCounts.add(3) ;
	    stripVerts.add(vindex) ;
	    stripVerts.add(vindex+2) ;
	    stripVerts.add(vindex+1) ;
	    if (length > 3) {
		// Copy the rest of the vertices in original order.
		vindex++ ;
		stripCounts.add(length-1) ;
		while (vindex < start + length) {
		    stripVerts.add(vindex++) ;
		}
	    }
	}
    }
	
    private static void addFan(IntList fanVerts,
			       IntList fanCounts,
			       int start, int length,
			       int frontFace, int winding,
			       boolean transition) {
	int vindex = start ;
	fanVerts.add(vindex++) ;

	if (winding == frontFace) {
	    if (transition) {
		// Skip 1st triangle if this is the result of a transition.
		fanCounts.add(length-1) ;
		vindex++ ;
	    } else {
		fanCounts.add(length) ;
		fanVerts.add(vindex++) ;
	    }
	    while (vindex < start + length) {
		fanVerts.add(vindex++) ;
	    }
	} else {
	    // Reverse winding order.
	    vindex += length-2 ;
	    while (vindex > start+1) {
		fanVerts.add(vindex--) ;
	    }
	    if (transition) {
		// Skip 1st triangle if this is the result of a transition.
		fanCounts.add(length-1) ;
	    } else {
		fanCounts.add(length) ;
		fanVerts.add(vindex) ;
	    }
	}
    }

    /**
     * Interprets the vertex flags associated with a class implementing
     * GeneralizedStripFlags, constructing and returning a StripArray containing
     * exclusively strips.
     *
     * @param vertices an object implementing GeneralizedStripFlags
     * @param frontFace a flag, either GeneralizedStripFlags.FRONTFACE_CW or
     * GeneralizedStripFlags.FRONTFACE_CCW, indicating front face winding
     * @return a StripArray containing the converted strips
     */
    static StripArray toTriangleStrips(GeneralizedStripFlags vertices,
				       int frontFace) {

	int size = vertices.getFlagCount() ;

	// initialize lists to worst-case sizes.
	IntList stripVerts  = new IntList(size*3) ;
	IntList fanVerts    = new IntList(size*3) ;