/*
* Copyright (c) 2003-2009 jMonkeyEngine
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* * Redistributions 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 'jMonkeyEngine' nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
package jme3tools.converters.model.strip;
import java.util.Arrays;
/**
* To use, call generateStrips method, passing your triangle index list and
* then construct geometry/render resulting PrimitiveGroup objects.
* Features:
* <ul>
* <li>generates strips from arbitrary geometry.
* <li>flexibly optimizes for post TnL vertex caches (16 on GeForce1/2, 24 on GeForce3).
* <li>can stitch together strips using degenerate triangles, or not.
* <li>can output lists instead of strips.
* <li>can optionally throw excessively small strips into a list instead.
* <li>can remap indices to improve spatial locality in your vertex buffers.
* </ul>
* On cache sizes: Note that it's better to UNDERESTIMATE the cache size
* instead of OVERESTIMATING. So, if you're targetting GeForce1, 2, and 3, be
* conservative and use the GeForce1_2 cache size, NOT the GeForce3 cache size.
* This will make sure you don't "blow" the cache of the GeForce1 and 2. Also
* note that the cache size you specify is the "actual" cache size, not the
* "effective" cache size you may have heard about. This is 16 for GeForce1 and 2,
* and 24 for GeForce3.
*
* Credit goes to Curtis Beeson and Joe Demers for the basis for this
* stripifier and to Jason Regier and Jon Stone at Blizzard for providing a
* much cleaner version of CreateStrips().
*
* Ported to java by Artur Biesiadowski <abies@pg.gda.pl>
*/
public class TriStrip {
public static final int CACHESIZE_GEFORCE1_2 = 16;
public static final int CACHESIZE_GEFORCE3 = 24;
int cacheSize = CACHESIZE_GEFORCE1_2;
boolean bStitchStrips = true;
int minStripSize = 0;
boolean bListsOnly = false;
/**
*
*/
public TriStrip() {
super();
}
/**
* If set to true, will return an optimized list, with no strips at all.
* Default value: false
*/
public void setListsOnly(boolean _bListsOnly) {
bListsOnly = _bListsOnly;
}
/**
* Sets the cache size which the stripfier uses to optimize the data.
* Controls the length of the generated individual strips. This is the
* "actual" cache size, so 24 for GeForce3 and 16 for GeForce1/2 You may
* want to play around with this number to tweak performance. Default
* value: 16
*/
public void setCacheSize(int _cacheSize) {
cacheSize = _cacheSize;
}
/**
* bool to indicate whether to stitch together strips into one huge strip
* or not. If set to true, you'll get back one huge strip stitched together
* using degenerate triangles. If set to false, you'll get back a large
* number of separate strips. Default value: true
*/
public void setStitchStrips(boolean _bStitchStrips) {
bStitchStrips = _bStitchStrips;
}
/**
* Sets the minimum acceptable size for a strip, in triangles. All strips
* generated which are shorter than this will be thrown into one big,
* separate list. Default value: 0
*/
public void setMinStripSize(int _minStripSize) {
minStripSize = _minStripSize;
}
/**
* @param in_indices
* input index list, the indices you would use to render
* @return array of optimized/stripified PrimitiveGroups
*/
public PrimitiveGroup[] generateStrips(int[] in_indices) {
int numGroups = 0;
PrimitiveGroup[] primGroups;
//put data in format that the stripifier likes
IntVec tempIndices = new IntVec();
int maxIndex = 0;
for (int i = 0; i < in_indices.length; i++) {
tempIndices.add(in_indices[i]);
if (in_indices[i] > maxIndex)
maxIndex = in_indices[i];
}
StripInfoVec tempStrips = new StripInfoVec();
FaceInfoVec tempFaces = new FaceInfoVec();
Stripifier stripifier = new Stripifier();
//do actual stripification
stripifier.stripify(tempIndices, cacheSize, minStripSize, maxIndex, tempStrips, tempFaces);
//stitch strips together
IntVec stripIndices = new IntVec();
int numSeparateStrips = 0;
if (bListsOnly) {
//if we're outputting only lists, we're done
numGroups = 1;
primGroups = new PrimitiveGroup[numGroups];
primGroups[0] = new PrimitiveGroup();
PrimitiveGroup[] primGroupArray = primGroups;
//count the total number of indices
int numIndices = 0;
for (int i = 0; i < tempStrips.size(); i++) {
numIndices += tempStrips.at(i).m_faces.size() * 3;
}
//add in the list
numIndices += tempFaces.size() * 3;
primGroupArray[0].type = PrimitiveGroup.PT_LIST;
primGroupArray[0].indices = new int[numIndices];
primGroupArray[0].numIndices = numIndices;
//do strips
int indexCtr = 0;
for (int i = 0; i < tempStrips.size(); i++) {
for (int j = 0; j < tempStrips.at(i).m_faces.size(); j++) {
//degenerates are of no use with lists
if (!Stripifier.isDegenerate(tempStrips.at(i).m_faces.at(j))) {
primGroupArray[0].indices[indexCtr++] = tempStrips.at(i).m_faces.at(j).m_v0;
primGroupArray[0].indices[indexCtr++] = tempStrips.at(i).m_faces.at(j).m_v1;
primGroupArray[0].indices[indexCtr++] = tempStrips.at(i).m_faces.at(j).m_v2;
} else {
//we've removed a tri, reduce the number of indices
primGroupArray[0].numIndices -= 3;
}
}
}
//do lists
for (int i = 0; i < tempFaces.size(); i++) {
primGroupArray[0].indices[indexCtr++] = tempFaces.at(i).m_v0;
primGroupArray[0].indices[indexCtr++] = tempFaces.at(i).m_v1;
primGroupArray[0].indices[indexCtr++] = tempFaces.at(i).m_v2;
}
} else {
numSeparateStrips = stripifier.createStrips(tempStrips, stripIndices, bStitchStrips);
//if we're stitching strips together, we better get back only one
// strip from CreateStrips()
//convert to output format
numGroups = numSeparateStrips; //for the strips
if (tempFaces.size() != 0)
numGroups++; //we've got a list as well, increment
primGroups = new PrimitiveGroup[numGroups];
for (int i = 0; i < primGroups.length; i++) {
primGroups[i] = new PrimitiveGroup();
}
PrimitiveGroup[] primGroupArray = primGroups;
//first, the strips
int startingLoc = 0;
for (int stripCtr = 0; stripCtr < numSeparateStrips; stripCtr++) {
int stripLength = 0;
if (!bStitchStrips) {
int i;
//if we've got multiple strips, we need to figure out the
// correct length
for (i = startingLoc; i < stripIndices.size(); i++) {
if (stripIndices.get(i) == -1)
break;
}
stripLength = i - startingLoc;
} else
stripLength = stripIndices.size();
primGroupArray[stripCtr].type = PrimitiveGroup.PT_STRIP;
primGroupArray[stripCtr].indices = new int[stripLength];
primGroupArray[stripCtr].numIndices = stripLength;
int indexCtr = 0;
for (int i = startingLoc; i < stripLength + startingLoc; i++)
primGroupArray[stripCtr].indices[indexCtr++] = stripIndices.get(i);
//we add 1 to account for the -1 separating strips
//this doesn't break the stitched case since we'll exit the
// loop
startingLoc += stripLength + 1;
}
//next, the list
if (tempFaces.size() != 0) {
int faceGroupLoc = numGroups - 1; //the face group is the last
// one
primGroupArray[faceGroupLoc].type = PrimitiveGroup.PT_LIST;
primGroupArray[faceGroupLoc].indices = new int[tempFaces.size() * 3];
primGroupArray[faceGroupLoc].numIndices = tempFaces.size() * 3;
int indexCtr = 0;
for (int i = 0; i < tempFaces.size(); i++) {
primGroupArray[faceGroupLoc].indices[indexCtr++] = tempFaces.at(i).m_v0;
primGroupArray[faceGroupLoc].indices[indexCtr++] = tempFaces.at(i).m_v1;
primGroupArray[faceGroupLoc].indices[indexCtr++] = tempFaces.at(i).m_v2;
}
}
}
return primGroups;
}
/**
* Function to remap your indices to improve spatial locality in your
* vertex buffer.
*
* in_primGroups: array of PrimitiveGroups you want remapped numGroups:
* number of entries in in_primGroups numVerts: number of vertices in your
* vertex buffer, also can be thought of as the range of acceptable values
* for indices in your primitive groups. remappedGroups: array of remapped
* PrimitiveGroups
*
* Note that, according to the remapping handed back to you, you must
* reorder your vertex buffer.
*
*/
public static int[] remapIndices(int[] indices, int numVerts) {
int[] indexCache = new int[numVerts];
Arrays.fill(indexCache, -1);
int numIndices = indices.length;
int[] remappedIndices = new int[numIndices];
int indexCtr = 0;
for (int j = 0; j < numIndices; j++) {
int cachedIndex = indexCache[indices[j]];
if (cachedIndex == -1) //we haven't seen this index before
{
//point to "last" vertex in VB
remappedIndices[j] = indexCtr;
//add to index cache, increment
indexCache[indices[j]] = indexCtr++;
} else {
//we've seen this index before
remappedIndices[j] = cachedIndex;
}
}
return remappedIndices;
}
public static void remapArrays(float[] vertexBuffer, int vertexSize, int[] indices) {
int[] remapped = remapIndices(indices, vertexBuffer.length / vertexSize);
float[] bufferCopy = vertexBuffer.clone();
for (int i = 0; i < remapped.length; i++) {
int from = indices[i] * vertexSize;
int to = remapped[i] * vertexSize;
for (int j = 0; j < vertexSize; j++) {
vertexBuffer[to + j] = bufferCopy[from + j];
}
}
System.arraycopy(remapped, 0, indices, 0, indices.length);
}
}