/*
* Copyright (c) 2009-2010 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.HashSet;
import java.util.logging.Logger;
/**
*
*/
class Stripifier {
private static final Logger logger = Logger.getLogger(Stripifier.class
.getName());
public static int CACHE_INEFFICIENCY = 6;
IntVec indices = new IntVec();
int cacheSize;
int minStripLength;
float meshJump;
boolean bFirstTimeResetPoint;
Stripifier() {
super();
}
///////////////////////////////////////////////////////////////////////////////////////////
// FindEdgeInfo()
//
// find the edge info for these two indices
//
static EdgeInfo findEdgeInfo(EdgeInfoVec edgeInfos, int v0, int v1) {
// we can get to it through either array
// because the edge infos have a v0 and v1
// and there is no order except how it was
// first created.
EdgeInfo infoIter = edgeInfos.at(v0);
while (infoIter != null) {
if (infoIter.m_v0 == v0) {
if (infoIter.m_v1 == v1)
return infoIter;
infoIter = infoIter.m_nextV0;
} else {
if (infoIter.m_v0 == v1)
return infoIter;
infoIter = infoIter.m_nextV1;
}
}
return null;
}
///////////////////////////////////////////////////////////////////////////////////////////
// FindOtherFace
//
// find the other face sharing these vertices
// exactly like the edge info above
//
static FaceInfo findOtherFace(EdgeInfoVec edgeInfos, int v0, int v1,
FaceInfo faceInfo) {
EdgeInfo edgeInfo = findEdgeInfo(edgeInfos, v0, v1);
if ((edgeInfo == null) || (v0 == v1)) {
//we've hit a degenerate
return null;
}
return (edgeInfo.m_face0 == faceInfo ? edgeInfo.m_face1
: edgeInfo.m_face0);
}
static boolean alreadyExists(FaceInfo faceInfo, FaceInfoVec faceInfos) {
for (int i = 0; i < faceInfos.size(); ++i) {
FaceInfo o = faceInfos.at(i);
if ((o.m_v0 == faceInfo.m_v0) && (o.m_v1 == faceInfo.m_v1)
&& (o.m_v2 == faceInfo.m_v2))
return true;
}
return false;
}
///////////////////////////////////////////////////////////////////////////////////////////
// BuildStripifyInfo()
//
// Builds the list of all face and edge infos
//
void buildStripifyInfo(FaceInfoVec faceInfos, EdgeInfoVec edgeInfos,
int maxIndex) {
// reserve space for the face infos, but do not resize them.
int numIndices = indices.size();
faceInfos.reserve(numIndices / 3);
// we actually resize the edge infos, so we must initialize to null
for (int i = 0; i < maxIndex + 1; i++)
edgeInfos.add(null);
// iterate through the triangles of the triangle list
int numTriangles = numIndices / 3;
int index = 0;
boolean[] bFaceUpdated = new boolean[3];
for (int i = 0; i < numTriangles; i++) {
boolean bMightAlreadyExist = true;
bFaceUpdated[0] = false;
bFaceUpdated[1] = false;
bFaceUpdated[2] = false;
// grab the indices
int v0 = indices.get(index++);
int v1 = indices.get(index++);
int v2 = indices.get(index++);
//we disregard degenerates
if (isDegenerate(v0, v1, v2))
continue;
// create the face info and add it to the list of faces, but only
// if this exact face doesn't already
// exist in the list
FaceInfo faceInfo = new FaceInfo(v0, v1, v2);
// grab the edge infos, creating them if they do not already exist
EdgeInfo edgeInfo01 = findEdgeInfo(edgeInfos, v0, v1);
if (edgeInfo01 == null) {
//since one of it's edges isn't in the edge data structure, it
// can't already exist in the face structure
bMightAlreadyExist = false;
// create the info
edgeInfo01 = new EdgeInfo(v0, v1);
// update the linked list on both
edgeInfo01.m_nextV0 = edgeInfos.at(v0);
edgeInfo01.m_nextV1 = edgeInfos.at(v1);
edgeInfos.set(v0, edgeInfo01);
edgeInfos.set(v1, edgeInfo01);
// set face 0
edgeInfo01.m_face0 = faceInfo;
} else {
if (edgeInfo01.m_face1 != null) {
logger.info("BuildStripifyInfo: > 2 triangles on an edge"
+ v0 + "," + v1 + "... uncertain consequences\n");
} else {
edgeInfo01.m_face1 = faceInfo;
bFaceUpdated[0] = true;
}
}
// grab the edge infos, creating them if they do not already exist
EdgeInfo edgeInfo12 = findEdgeInfo(edgeInfos, v1, v2);
if (edgeInfo12 == null) {
bMightAlreadyExist = false;
// create the info
edgeInfo12 = new EdgeInfo(v1, v2);
// update the linked list on both
edgeInfo12.m_nextV0 = edgeInfos.at(v1);
edgeInfo12.m_nextV1 = edgeInfos.at(v2);
edgeInfos.set(v1, edgeInfo12);
edgeInfos.set(v2, edgeInfo12);
// set face 0
edgeInfo12.m_face0 = faceInfo;
} else {
if (edgeInfo12.m_face1 != null) {
logger.info("BuildStripifyInfo: > 2 triangles on an edge"
+ v1
+ ","
+ v2
+ "... uncertain consequences\n");
} else {
edgeInfo12.m_face1 = faceInfo;
bFaceUpdated[1] = true;
}
}
// grab the edge infos, creating them if they do not already exist
EdgeInfo edgeInfo20 = findEdgeInfo(edgeInfos, v2, v0);
if (edgeInfo20 == null) {
bMightAlreadyExist = false;
// create the info
edgeInfo20 = new EdgeInfo(v2, v0);
// update the linked list on both
edgeInfo20.m_nextV0 = edgeInfos.at(v2);
edgeInfo20.m_nextV1 = edgeInfos.at(v0);
edgeInfos.set(v2, edgeInfo20);
edgeInfos.set(v0, edgeInfo20);
// set face 0
edgeInfo20.m_face0 = faceInfo;
} else {
if (edgeInfo20.m_face1 != null) {
logger.info("BuildStripifyInfo: > 2 triangles on an edge"
+ v2
+ ","
+ v0
+ "... uncertain consequences\n");
} else {
edgeInfo20.m_face1 = faceInfo;
bFaceUpdated[2] = true;
}
}
if (bMightAlreadyExist) {
if (!alreadyExists(faceInfo, faceInfos))
faceInfos.add(faceInfo);
else {
//cleanup pointers that point to this deleted face
if (bFaceUpdated[0])
edgeInfo01.m_face1 = null;
if (bFaceUpdated[1])
edgeInfo12.m_face1 = null;
if (bFaceUpdated[2])
edgeInfo20.m_face1 = null;
}
} else {
faceInfos.add(faceInfo);
}
}
}
static boolean isDegenerate(FaceInfo face) {
if (face.m_v0 == face.m_v1)
return true;
else if (face.m_v0 == face.m_v2)
return true;
else if (face.m_v1 == face.m_v2)
return true;
else
return false;
}
static boolean isDegenerate(int v0, int v1, int v2) {
if (v0 == v1)
return true;
else if (v0 == v2)
return true;
else if (v1 == v2)
return true;
else
return false;
}
///////////////////////////////////////////////////////////////////////////////////////////
// GetNextIndex()
//
// Returns vertex of the input face which is "next" in the input index list
//
static int getNextIndex(IntVec indices, FaceInfo face) {
int numIndices = indices.size();
int v0 = indices.get(numIndices - 2);
int v1 = indices.get(numIndices - 1);
int fv0 = face.m_v0;
int fv1 = face.m_v1;
int fv2 = face.m_v2;
if (fv0 != v0 && fv0 != v1) {
if ((fv1 != v0 && fv1 != v1) || (fv2 != v0 && fv2 != v1)) {
logger.info("GetNextIndex: Triangle doesn't have all of its vertices\n");
logger.info("GetNextIndex: Duplicate triangle probably got us derailed\n");
}
return fv0;
}
if (fv1 != v0 && fv1 != v1) {
if ((fv0 != v0 && fv0 != v1) || (fv2 != v0 && fv2 != v1)) {
logger.info("GetNextIndex: Triangle doesn't have all of its vertices\n");
logger.info("GetNextIndex: Duplicate triangle probably got us derailed\n");
}
return fv1;
}
if (fv2 != v0 && fv2 != v1) {
if ((fv0 != v0 && fv0 != v1) || (fv1 != v0 && fv1 != v1)) {
logger.info("GetNextIndex: Triangle doesn't have all of its vertices\n");
logger.info("GetNextIndex: Duplicate triangle probably got us derailed\n");
}
return fv2;
}
// shouldn't get here, but let's try and fail gracefully
if ((fv0 == fv1) || (fv0 == fv2))
return fv0;
else if ((fv1 == fv0) || (fv1 == fv2))
return fv1;
else if ((fv2 == fv0) || (fv2 == fv1))
return fv2;
else
return -1;
}
///////////////////////////////////////////////////////////////////////////////////////////
// FindStartPoint()
//
// Finds a good starting point, namely one which has only one neighbor
//
static int findStartPoint(FaceInfoVec faceInfos, EdgeInfoVec edgeInfos) {
int bestCtr = -1;
int bestIndex = -1;
for (int i = 0; i < faceInfos.size(); i++) {
int ctr = 0;
if (findOtherFace(edgeInfos, faceInfos.at(i).m_v0,
faceInfos.at(i).m_v1, faceInfos.at(i)) == null)
ctr++;
if (findOtherFace(edgeInfos, faceInfos.at(i).m_v1,
faceInfos.at(i).m_v2, faceInfos.at(i)) == null)
ctr++;
if (findOtherFace(edgeInfos, faceInfos.at(i).m_v2,
faceInfos.at(i).m_v0, faceInfos.at(i)) == null)
ctr++;
if (ctr > bestCtr) {
bestCtr = ctr;
bestIndex = i;
//return i;
}
}
//return -1;
if (bestCtr == 0)
return -1;
return bestIndex;
}
///////////////////////////////////////////////////////////////////////////////////////////
// FindGoodResetPoint()
//
// A good reset point is one near other commited areas so that
// we know that when we've made the longest strips its because
// we're stripifying in the same general orientation.
//
FaceInfo findGoodResetPoint(FaceInfoVec faceInfos, EdgeInfoVec edgeInfos) {
// we hop into different areas of the mesh to try to get
// other large open spans done. Areas of small strips can
// just be left to triangle lists added at the end.
FaceInfo result = null;
if (result == null) {
int numFaces = faceInfos.size();
int startPoint;
if (bFirstTimeResetPoint) {
//first time, find a face with few neighbors (look for an edge
// of the mesh)
startPoint = findStartPoint(faceInfos, edgeInfos);
bFirstTimeResetPoint = false;
} else
startPoint = (int) (((float) numFaces - 1) * meshJump);
if (startPoint == -1) {
startPoint = (int) (((float) numFaces - 1) * meshJump);
//meshJump += 0.1f;
//if (meshJump > 1.0f)
// meshJump = .05f;
}
int i = startPoint;
do {
// if this guy isn't visited, try him
if (faceInfos.at(i).m_stripId < 0) {
result = faceInfos.at(i);
break;
}
// update the index and clamp to 0-(numFaces-1)
if (++i >= numFaces)
i = 0;
} while (i != startPoint);
// update the meshJump
meshJump += 0.1f;
if (meshJump > 1.0f)
meshJump = .05f;
}
// return the best face we found
return result;
}
///////////////////////////////////////////////////////////////////////////////////////////
// GetUniqueVertexInB()
//
// Returns the vertex unique to faceB
//
static int getUniqueVertexInB(FaceInfo faceA, FaceInfo faceB) {
int facev0 = faceB.m_v0;
if (facev0 != faceA.m_v0 && facev0 != faceA.m_v1
&& facev0 != faceA.m_v2)
return facev0;
int facev1 = faceB.m_v1;
if (facev1 != faceA.m_v0 && facev1 != faceA.m_v1
&& facev1 != faceA.m_v2)
return facev1;
int facev2 = faceB.m_v2;
if (facev2 != faceA.m_v0 && facev2 != faceA.m_v1
&& facev2 != faceA.m_v2)
return facev2;
// nothing is different
return -1;
}
///////////////////////////////////////////////////////////////////////////////////////////
// GetSharedVertices()
//
// Returns the (at most) two vertices shared between the two faces
//
static void getSharedVertices(FaceInfo faceA, FaceInfo faceB, int[] vertex) {
vertex[0] = -1;
vertex[1] = -1;
int facev0 = faceB.m_v0;
if (facev0 == faceA.m_v0 || facev0 == faceA.m_v1
|| facev0 == faceA.m_v2) {
if (vertex[0] == -1)
vertex[0] = facev0;
else {
vertex[1] = facev0;
return;
}
}
int facev1 = faceB.m_v1;
if (facev1 == faceA.m_v0 || facev1 == faceA.m_v1
|| facev1 == faceA.m_v2) {
if (vertex[0] == -1)
vertex[0] = facev1;
else {
vertex[1] = facev1;
return;
}
}
int facev2 = faceB.m_v2;
if (facev2 == faceA.m_v0 || facev2 == faceA.m_v1
|| facev2 == faceA.m_v2) {
if (vertex[0] == -1)
vertex[0] = facev2;
else {
vertex[1] = facev2;
return;
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////
// CommitStrips()
//
// "Commits" the input strips by setting their m_experimentId to -1 and
// adding to the allStrips
// vector
//
static void commitStrips(StripInfoVec allStrips, StripInfoVec strips) {
// Iterate through strips
int numStrips = strips.size();
for (int i = 0; i < numStrips; i++) {
// Tell the strip that it is now real
StripInfo strip = strips.at(i);
strip.m_experimentId = -1;
// add to the list of real strips
allStrips.add(strip);
// Iterate through the faces of the strip
// Tell the faces of the strip that they belong to a real strip now
FaceInfoVec faces = strips.at(i).m_faces;
int numFaces = faces.size();
for (int j = 0; j < numFaces; j++) {
strip.markTriangle(faces.at(j));
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////
// NextIsCW()
//
// Returns true if the next face should be ordered in CW fashion
//
static boolean nextIsCW(int numIndices) {
return ((numIndices % 2) == 0);
}
///////////////////////////////////////////////////////////////////////////////////////////
// UpdateCacheFace()
//
// Updates the input vertex cache with this face's vertices
//
static void updateCacheFace(VertexCache vcache, FaceInfo face) {
if (!vcache.inCache(face.m_v0))
vcache.addEntry(face.m_v0);
if (!vcache.inCache(face.m_v1))
vcache.addEntry(face.m_v1);
if (!vcache.inCache(face.m_v2))
vcache.addEntry(face.m_v2);
}
///////////////////////////////////////////////////////////////////////////////////////////
// UpdateCacheStrip()
//
// Updates the input vertex cache with this strip's vertices
//
static void updateCacheStrip(VertexCache vcache, StripInfo strip) {
for (int i = 0; i < strip.m_faces.size(); ++i) {
if (!vcache.inCache(strip.m_faces.at(i).m_v0))
vcache.addEntry(strip.m_faces.at(i).m_v0);
if (!vcache.inCache(strip.m_faces.at(i).m_v1))
vcache.addEntry(strip.m_faces.at(i).m_v1);
if (!vcache.inCache(strip.m_faces.at(i).m_v2))
vcache.addEntry(strip.m_faces.at(i).m_v2);
}
}
///////////////////////////////////////////////////////////////////////////////////////////
// CalcNumHitsStrip()
//
// returns the number of cache hits per face in the strip
//
static float calcNumHitsStrip(VertexCache vcache, StripInfo strip) {
int numHits = 0;
int numFaces = 0;
for (int i = 0; i < strip.m_faces.size(); i++) {
if (vcache.inCache(strip.m_faces.at(i).m_v0))
++numHits;
if (vcache.inCache(strip.m_faces.at(i).m_v1))
++numHits;
if (vcache.inCache(strip.m_faces.at(i).m_v2))
++numHits;
numFaces++;
}
return ((float) numHits / (float) numFaces);
}
///////////////////////////////////////////////////////////////////////////////////////////
// AvgStripSize()
//
// Finds the average strip size of the input vector of strips
//
static float avgStripSize(StripInfoVec strips) {
int sizeAccum = 0;
int numStrips = strips.size();
for (int i = 0; i < numStrips; i++) {
StripInfo strip = strips.at(i);
sizeAccum += strip.m_faces.size();
sizeAccum -= strip.m_numDegenerates;
}
return ((float) sizeAccum) / ((float) numStrips);
}
///////////////////////////////////////////////////////////////////////////////////////////
// CalcNumHitsFace()
//
// returns the number of cache hits in the face
//
static int calcNumHitsFace(VertexCache vcache, FaceInfo face) {
int numHits = 0;
if (vcache.inCache(face.m_v0))
numHits++;
if (vcache.inCache(face.m_v1))
numHits++;
if (vcache.inCache(face.m_v2))
numHits++;
return numHits;
}
///////////////////////////////////////////////////////////////////////////////////////////
// NumNeighbors()
//
// Returns the number of neighbors that this face has
//
static int numNeighbors(FaceInfo face, EdgeInfoVec edgeInfoVec) {
int numNeighbors = 0;
if (findOtherFace(edgeInfoVec, face.m_v0, face.m_v1, face) != null) {
numNeighbors++;
}
if (findOtherFace(edgeInfoVec, face.m_v1, face.m_v2, face) != null) {
numNeighbors++;
}
if (findOtherFace(edgeInfoVec, face.m_v2, face.m_v0, face) != null) {
numNeighbors++;
}
return numNeighbors;
}
///////////////////////////////////////////////////////////////////////////////////////////
// IsCW()
//
// Returns true if the face is ordered in CW fashion
//
static boolean isCW(FaceInfo faceInfo, int v0, int v1) {
if (faceInfo.m_v0 == v0)
return (faceInfo.m_v1 == v1);
else if (faceInfo.m_v1 == v0)
return (faceInfo.m_v2 == v1);
else
return (faceInfo.m_v0 == v1);
}
static boolean faceContainsIndex(FaceInfo face, int index) {
return ((face.m_v0 == index) || (face.m_v1 == index) || (face.m_v2 == index));
}
///////////////////////////////////////////////////////////////////////////////////////////
// FindTraversal()
//
// Finds the next face to start the next strip on.
//
static boolean findTraversal(FaceInfoVec faceInfos, EdgeInfoVec edgeInfos,
StripInfo strip, StripStartInfo startInfo) {
// if the strip was v0.v1 on the edge, then v1 will be a vertex in the
// next edge.
int v = (strip.m_startInfo.m_toV1 ? strip.m_startInfo.m_startEdge.m_v1
: strip.m_startInfo.m_startEdge.m_v0);
FaceInfo untouchedFace = null;
EdgeInfo edgeIter = edgeInfos.at(v);
while (edgeIter != null) {
FaceInfo face0 = edgeIter.m_face0;
FaceInfo face1 = edgeIter.m_face1;
if ((face0 != null && !strip.isInStrip(face0)) && face1 != null
&& !strip.isMarked(face1)) {
untouchedFace = face1;
break;
}
if ((face1 != null && !strip.isInStrip(face1)) && face0 != null
&& !strip.isMarked(face0)) {
untouchedFace = face0;
break;
}
// find the next edgeIter
edgeIter = (edgeIter.m_v0 == v ? edgeIter.m_nextV0
: edgeIter.m_nextV1);
}
startInfo.m_startFace = untouchedFace;
startInfo.m_startEdge = edgeIter;
if (edgeIter != null) {
if (strip.sharesEdge(startInfo.m_startFace, edgeInfos))
startInfo.m_toV1 = (edgeIter.m_v0 == v); //note! used to be
// m_v1
else
startInfo.m_toV1 = (edgeIter.m_v1 == v);
}
return (startInfo.m_startFace != null);
}
////////////////////////////////////////////////////////////////////////////////////////
// RemoveSmallStrips()
//
// allStrips is the whole strip vector...all small strips will be deleted
// from this list, to avoid leaking mem
// allBigStrips is an out parameter which will contain all strips above
// minStripLength
// faceList is an out parameter which will contain all faces which were
// removed from the striplist
//
void removeSmallStrips(StripInfoVec allStrips, StripInfoVec allBigStrips,
FaceInfoVec faceList) {
faceList.clear();
allBigStrips.clear(); //make sure these are empty
FaceInfoVec tempFaceList = new FaceInfoVec();
for (int i = 0; i < allStrips.size(); i++) {
if (allStrips.at(i).m_faces.size() < minStripLength) {
//strip is too small, add faces to faceList
for (int j = 0; j < allStrips.at(i).m_faces.size(); j++)
tempFaceList.add(allStrips.at(i).m_faces.at(j));
} else {
allBigStrips.add(allStrips.at(i));
}
}
boolean[] bVisitedList = new boolean[tempFaceList.size()];
VertexCache vcache = new VertexCache(cacheSize);
int bestNumHits = -1;
int numHits;
int bestIndex = -9999;
while (true) {
bestNumHits = -1;
//find best face to add next, given the current cache
for (int i = 0; i < tempFaceList.size(); i++) {
if (bVisitedList[i])
continue;
numHits = calcNumHitsFace(vcache, tempFaceList.at(i));
if (numHits > bestNumHits) {
bestNumHits = numHits;
bestIndex = i;
}
}
if (bestNumHits == -1.0f)
break;
bVisitedList[bestIndex] = true;
updateCacheFace(vcache, tempFaceList.at(bestIndex));
faceList.add(tempFaceList.at(bestIndex));
}
}
////////////////////////////////////////////////////////////////////////////////////////
// CreateStrips()
//
// Generates actual strips from the list-in-strip-order.
//
int createStrips(StripInfoVec allStrips, IntVec stripIndices,
boolean bStitchStrips) {
int numSeparateStrips = 0;
FaceInfo tLastFace = new FaceInfo(0, 0, 0);
int nStripCount = allStrips.size();
//we infer the cw/ccw ordering depending on the number of indices
//this is screwed up by the fact that we insert -1s to denote changing
// strips
//this is to account for that
int accountForNegatives = 0;
for (int i = 0; i < nStripCount; i++) {
StripInfo strip = allStrips.at(i);
int nStripFaceCount = strip.m_faces.size();
// Handle the first face in the strip
{
FaceInfo tFirstFace = new FaceInfo(strip.m_faces.at(0).m_v0,
strip.m_faces.at(0).m_v1, strip.m_faces.at(0).m_v2);
// If there is a second face, reorder vertices such that the
// unique vertex is first
if (nStripFaceCount > 1) {
int nUnique = getUniqueVertexInB(strip.m_faces.at(1),
tFirstFace);
if (nUnique == tFirstFace.m_v1) {
int tmp = tFirstFace.m_v0;
tFirstFace.m_v0 = tFirstFace.m_v1;
tFirstFace.m_v1 = tmp;
} else if (nUnique == tFirstFace.m_v2) {
int tmp = tFirstFace.m_v0;
tFirstFace.m_v0 = tFirstFace.m_v2;
tFirstFace.m_v2 = tmp;
}
// If there is a third face, reorder vertices such that the
// shared vertex is last
if (nStripFaceCount > 2) {
if (isDegenerate(strip.m_faces.at(1))) {
int pivot = strip.m_faces.at(1).m_v1;
if (tFirstFace.m_v1 == pivot) {
int tmp = tFirstFace.m_v1;
tFirstFace.m_v1 = tFirstFace.m_v2;
tFirstFace.m_v2 = tmp;
}
} else {
int[] nShared = new int[2];
getSharedVertices(strip.m_faces.at(2), tFirstFace,
nShared);
if ((nShared[0] == tFirstFace.m_v1)
&& (nShared[1] == -1)) {
int tmp = tFirstFace.m_v1;
tFirstFace.m_v1 = tFirstFace.m_v2;
tFirstFace.m_v2 = tmp;
}
}
}
}
if ((i == 0) || !bStitchStrips) {
if (!isCW(strip.m_faces.at(0), tFirstFace.m_v0,
tFirstFace.m_v1))
stripIndices.add(tFirstFace.m_v0);
} else {
// Double tap the first in the new strip
stripIndices.add(tFirstFace.m_v0);
// Check CW/CCW ordering
if (nextIsCW(stripIndices.size() - accountForNegatives) != isCW(
strip.m_faces.at(0), tFirstFace.m_v0,
tFirstFace.m_v1)) {
stripIndices.add(tFirstFace.m_v0);
}
}
stripIndices.add(tFirstFace.m_v0);
stripIndices.add(tFirstFace.m_v1);
stripIndices.add(tFirstFace.m_v2);
// Update last face info
tLastFace.set(tFirstFace);
}
for (int j = 1; j < nStripFaceCount; j++) {
int nUnique = getUniqueVertexInB(tLastFace, strip.m_faces.at(j));
if (nUnique != -1) {
stripIndices.add(nUnique);
// Update last face info
tLastFace.m_v0 = tLastFace.m_v1;
tLastFace.m_v1 = tLastFace.m_v2;
tLastFace.m_v2 = nUnique;
} else {
//we've hit a degenerate
stripIndices.add(strip.m_faces.at(j).m_v2);
tLastFace.m_v0 = strip.m_faces.at(j).m_v0; //tLastFace.m_v1;
tLastFace.m_v1 = strip.m_faces.at(j).m_v1; //tLastFace.m_v2;
tLastFace.m_v2 = strip.m_faces.at(j).m_v2; //tLastFace.m_v1;
}
}
// Double tap between strips.
if (bStitchStrips) {
if (i != nStripCount - 1)
stripIndices.add(tLastFace.m_v2);
} else {
//-1 index indicates next strip
stripIndices.add(-1);
accountForNegatives++;
numSeparateStrips++;
}
// Update last face info
tLastFace.m_v0 = tLastFace.m_v1;
tLastFace.m_v1 = tLastFace.m_v2;
tLastFace.m_v2 = tLastFace.m_v2;
}
if (bStitchStrips)
numSeparateStrips = 1;
return numSeparateStrips;
}
///////////////////////////////////////////////////////////////////////////////////////////
// FindAllStrips()
//
// Does the stripification, puts output strips into vector allStrips
//
// Works by setting runnning a number of experiments in different areas of
// the mesh, and
// accepting the one which results in the longest strips. It then accepts
// this, and moves
// on to a different area of the mesh. We try to jump around the mesh some,
// to ensure that
// large open spans of strips get generated.
//
void findAllStrips(StripInfoVec allStrips, FaceInfoVec allFaceInfos,
EdgeInfoVec allEdgeInfos, int numSamples) {
// the experiments
int experimentId = 0;
int stripId = 0;
boolean done = false;
int loopCtr = 0;
while (!done) {
loopCtr++;
//
// PHASE 1: Set up numSamples * numEdges experiments
//
StripInfoVec[] experiments = new StripInfoVec[numSamples * 6];
for (int i = 0; i < experiments.length; i++)
experiments[i] = new StripInfoVec();
int experimentIndex = 0;
HashSet<FaceInfo> resetPoints = new HashSet<FaceInfo>(); /* NvFaceInfo */
for (int i = 0; i < numSamples; i++) {
// Try to find another good reset point.
// If there are none to be found, we are done
FaceInfo nextFace = findGoodResetPoint(allFaceInfos,
allEdgeInfos);
if (nextFace == null) {
done = true;
break;
}
// If we have already evaluated starting at this face in this
// slew of experiments, then skip going any further
else if (resetPoints.contains(nextFace)) {
continue;
}
// trying it now...
resetPoints.add(nextFace);
// otherwise, we shall now try experiments for starting on the
// 01,12, and 20 edges
// build the strip off of this face's 0-1 edge
EdgeInfo edge01 = findEdgeInfo(allEdgeInfos, nextFace.m_v0,
nextFace.m_v1);
StripInfo strip01 = new StripInfo(new StripStartInfo(nextFace,
edge01, true), stripId++, experimentId++);
experiments[experimentIndex++].add(strip01);
// build the strip off of this face's 1-0 edge
EdgeInfo edge10 = findEdgeInfo(allEdgeInfos, nextFace.m_v0,
nextFace.m_v1);
StripInfo strip10 = new StripInfo(new StripStartInfo(nextFace,
edge10, false), stripId++, experimentId++);
experiments[experimentIndex++].add(strip10);
// build the strip off of this face's 1-2 edge
EdgeInfo edge12 = findEdgeInfo(allEdgeInfos, nextFace.m_v1,
nextFace.m_v2);
StripInfo strip12 = new StripInfo(new StripStartInfo(nextFace,
edge12, true), stripId++, experimentId++);
experiments[experimentIndex++].add(strip12);
// build the strip off of this face's 2-1 edge
EdgeInfo edge21 = findEdgeInfo(allEdgeInfos, nextFace.m_v1,
nextFace.m_v2);
StripInfo strip21 = new StripInfo(new StripStartInfo(nextFace,
edge21, false), stripId++, experimentId++);
experiments[experimentIndex++].add(strip21);
// build the strip off of this face's 2-0 edge
EdgeInfo edge20 = findEdgeInfo(allEdgeInfos, nextFace.m_v2,
nextFace.m_v0);
StripInfo strip20 = new StripInfo(new StripStartInfo(nextFace,
edge20, true), stripId++, experimentId++);
experiments[experimentIndex++].add(strip20);
// build the strip off of this face's 0-2 edge
EdgeInfo edge02 = findEdgeInfo(allEdgeInfos, nextFace.m_v2,
nextFace.m_v0);
StripInfo strip02 = new StripInfo(new StripStartInfo(nextFace,
edge02, false), stripId++, experimentId++);
experiments[experimentIndex++].add(strip02);
}
//
// PHASE 2: Iterate through that we setup in the last phase
// and really build each of the strips and strips that follow to
// see how
// far we get
//
int numExperiments = experimentIndex;
for (int i = 0; i < numExperiments; i++) {
// get the strip set
// build the first strip of the list
experiments[i].at(0).build(allEdgeInfos, allFaceInfos);
int experimentId2 = experiments[i].at(0).m_experimentId;
StripInfo stripIter = experiments[i].at(0);
StripStartInfo startInfo = new StripStartInfo(null, null, false);
while (findTraversal(allFaceInfos, allEdgeInfos, stripIter,
startInfo)) {
// create the new strip info
//TODO startInfo clone ?
stripIter = new StripInfo(startInfo, stripId++,
experimentId2);
// build the next strip
stripIter.build(allEdgeInfos, allFaceInfos);
// add it to the list
experiments[i].add(stripIter);
}
}
//
// Phase 3: Find the experiment that has the most promise
//
int bestIndex = 0;
double bestValue = 0;
for (int i = 0; i < numExperiments; i++) {
float avgStripSizeWeight = 1.0f;
//float numTrisWeight = 0.0f;
float numStripsWeight = 0.0f;
float avgStripSize = avgStripSize(experiments[i]);
float numStrips = experiments[i].size();
float value = avgStripSize * avgStripSizeWeight
+ (numStrips * numStripsWeight);
//float value = 1.f / numStrips;
//float value = numStrips * avgStripSize;
if (value > bestValue) {
bestValue = value;
bestIndex = i;
}
}
//
// Phase 4: commit the best experiment of the bunch
//
commitStrips(allStrips, experiments[bestIndex]);
}
}
///////////////////////////////////////////////////////////////////////////////////////////
// SplitUpStripsAndOptimize()
//
// Splits the input vector of strips (allBigStrips) into smaller, cache
// friendly pieces, then
// reorders these pieces to maximize cache hits
// The final strips are output through outStrips
//
void splitUpStripsAndOptimize(StripInfoVec allStrips,
StripInfoVec outStrips, EdgeInfoVec edgeInfos,
FaceInfoVec outFaceList) {
int threshold = cacheSize;
StripInfoVec tempStrips = new StripInfoVec();
int j;
//split up strips into threshold-sized pieces
for (int i = 0; i < allStrips.size(); i++) {
StripInfo currentStrip;
StripStartInfo startInfo = new StripStartInfo(null, null, false);
int actualStripSize = 0;
for (j = 0; j < allStrips.at(i).m_faces.size(); ++j) {
if (!isDegenerate(allStrips.at(i).m_faces.at(j)))
actualStripSize++;
}
if (actualStripSize /* allStrips.at(i).m_faces.size() */
> threshold) {
int numTimes = actualStripSize /* allStrips.at(i).m_faces.size() */
/ threshold;
int numLeftover = actualStripSize /* allStrips.at(i).m_faces.size() */
% threshold;
int degenerateCount = 0;
for (j = 0; j < numTimes; j++) {
currentStrip = new StripInfo(startInfo, 0, -1);
int faceCtr = j * threshold + degenerateCount;
boolean bFirstTime = true;
while (faceCtr < threshold + (j * threshold)
+ degenerateCount) {
if (isDegenerate(allStrips.at(i).m_faces.at(faceCtr))) {
degenerateCount++;
//last time or first time through, no need for a
// degenerate
if ((((faceCtr + 1) != threshold + (j * threshold)
+ degenerateCount) || ((j == numTimes - 1)
&& (numLeftover < 4) && (numLeftover > 0)))
&& !bFirstTime) {
currentStrip.m_faces
.add(allStrips.at(i).m_faces
.at(faceCtr++));
} else
++faceCtr;
} else {
currentStrip.m_faces.add(allStrips.at(i).m_faces
.at(faceCtr++));
bFirstTime = false;
}
}
/*
* threshold; faceCtr < threshold+(j*threshold); faceCtr++) {
* currentStrip.m_faces.add(allStrips.at(i).m_faces.at(faceCtr]); }
*/
///*
if (j == numTimes - 1) //last time through
{
if ((numLeftover < 4) && (numLeftover > 0)) //way too
// small
{
//just add to last strip
int ctr = 0;
while (ctr < numLeftover) {
if (!isDegenerate(allStrips.at(i).m_faces
.at(faceCtr))) {
currentStrip.m_faces
.add(allStrips.at(i).m_faces
.at(faceCtr++));
++ctr;
} else {
currentStrip.m_faces
.add(allStrips.at(i).m_faces
.at(faceCtr++));
++degenerateCount;
}
}
numLeftover = 0;
}
}
//*/
tempStrips.add(currentStrip);
}
int leftOff = j * threshold + degenerateCount;
if (numLeftover != 0) {
currentStrip = new StripInfo(startInfo, 0, -1);
int ctr = 0;
boolean bFirstTime = true;
while (ctr < numLeftover) {
if (!isDegenerate(allStrips.at(i).m_faces.at(leftOff))) {
ctr++;
bFirstTime = false;
currentStrip.m_faces.add(allStrips.at(i).m_faces
.at(leftOff++));
} else if (!bFirstTime)
currentStrip.m_faces.add(allStrips.at(i).m_faces
.at(leftOff++));
else
leftOff++;
}
/*
* for(int k = 0; k < numLeftover; k++) {
* currentStrip.m_faces.add(allStrips.at(i).m_faces[leftOff++]); }
*/
tempStrips.add(currentStrip);
}
} else {
//we're not just doing a tempStrips.add(allBigStrips[i])
// because
// this way we can delete allBigStrips later to free the memory
currentStrip = new StripInfo(startInfo, 0, -1);
for (j = 0; j < allStrips.at(i).m_faces.size(); j++)
currentStrip.m_faces.add(allStrips.at(i).m_faces.at(j));
tempStrips.add(currentStrip);
}
}
//add small strips to face list
StripInfoVec tempStrips2 = new StripInfoVec();
removeSmallStrips(tempStrips, tempStrips2, outFaceList);
outStrips.clear();
//screw optimization for now
// for(i = 0; i < tempStrips.size(); ++i)
// outStrips.add(tempStrips[i]);
if (tempStrips2.size() != 0) {
//Optimize for the vertex cache
VertexCache vcache = new VertexCache(cacheSize);
float bestNumHits = -1.0f;
float numHits;
int bestIndex = -99999;
int firstIndex = 0;
float minCost = 10000.0f;
for (int i = 0; i < tempStrips2.size(); i++) {
int numNeighbors = 0;
//find strip with least number of neighbors per face
for (j = 0; j < tempStrips2.at(i).m_faces.size(); j++) {
numNeighbors += numNeighbors(tempStrips2.at(i).m_faces
.at(j), edgeInfos);
}
float currCost = (float) numNeighbors
/ (float) tempStrips2.at(i).m_faces.size();
if (currCost < minCost) {
minCost = currCost;
firstIndex = i;
}
}
updateCacheStrip(vcache, tempStrips2.at(firstIndex));
outStrips.add(tempStrips2.at(firstIndex));
tempStrips2.at(firstIndex).visited = true;
boolean bWantsCW = (tempStrips2.at(firstIndex).m_faces.size() % 2) == 0;
//this n^2 algo is what slows down stripification so much....
// needs to be improved
while (true) {
bestNumHits = -1.0f;
//find best strip to add next, given the current cache
for (int i = 0; i < tempStrips2.size(); i++) {
if (tempStrips2.at(i).visited)
continue;
numHits = calcNumHitsStrip(vcache, tempStrips2.at(i));
if (numHits > bestNumHits) {
bestNumHits = numHits;
bestIndex = i;
} else if (numHits >= bestNumHits) {
//check previous strip to see if this one requires it
// to switch polarity
StripInfo strip = tempStrips2.at(i);
int nStripFaceCount = strip.m_faces.size();
FaceInfo tFirstFace = new FaceInfo(
strip.m_faces.at(0).m_v0,
strip.m_faces.at(0).m_v1,
strip.m_faces.at(0).m_v2);
// If there is a second face, reorder vertices such
// that the
// unique vertex is first
if (nStripFaceCount > 1) {
int nUnique = getUniqueVertexInB(strip.m_faces
.at(1), tFirstFace);
if (nUnique == tFirstFace.m_v1) {
int tmp = tFirstFace.m_v0;
tFirstFace.m_v0 = tFirstFace.m_v1;
tFirstFace.m_v1 = tmp;
} else if (nUnique == tFirstFace.m_v2) {
int tmp = tFirstFace.m_v0;
tFirstFace.m_v0 = tFirstFace.m_v2;
tFirstFace.m_v2 = tmp;
}
// If there is a third face, reorder vertices such
// that the
// shared vertex is last
if (nStripFaceCount > 2) {
int[] nShared = new int[2];
getSharedVertices(strip.m_faces.at(2),
tFirstFace, nShared);
if ((nShared[0] == tFirstFace.m_v1)
&& (nShared[1] == -1)) {
int tmp = tFirstFace.m_v2;
tFirstFace.m_v2 = tFirstFace.m_v1;
tFirstFace.m_v1 = tmp;
}
}
}
// Check CW/CCW ordering
if (bWantsCW == isCW(strip.m_faces.at(0),
tFirstFace.m_v0, tFirstFace.m_v1)) {
//I like this one!
bestIndex = i;
}
}
}
if (bestNumHits == -1.0f)
break;
tempStrips2.at(bestIndex).visited = true;
updateCacheStrip(vcache, tempStrips2.at(bestIndex));
outStrips.add(tempStrips2.at(bestIndex));
bWantsCW = (tempStrips2.at(bestIndex).m_faces.size() % 2 == 0) ? bWantsCW
: !bWantsCW;
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////
// Stripify()
//
//
// in_indices are the input indices of the mesh to stripify
// in_cacheSize is the target cache size
//
void stripify(IntVec in_indices, int in_cacheSize, int in_minStripLength,
int maxIndex, StripInfoVec outStrips, FaceInfoVec outFaceList) {
meshJump = 0.0f;
bFirstTimeResetPoint = true; //used in FindGoodResetPoint()
//the number of times to run the experiments
int numSamples = 10;
//the cache size, clamped to one
cacheSize = Math.max(1, in_cacheSize - CACHE_INEFFICIENCY);
minStripLength = in_minStripLength;
//this is the strip size threshold below which we dump the strip into
// a list
indices = in_indices;
// build the stripification info
FaceInfoVec allFaceInfos = new FaceInfoVec();
EdgeInfoVec allEdgeInfos = new EdgeInfoVec();
buildStripifyInfo(allFaceInfos, allEdgeInfos, maxIndex);
StripInfoVec allStrips = new StripInfoVec();
// stripify
findAllStrips(allStrips, allFaceInfos, allEdgeInfos, numSamples);
//split up the strips into cache friendly pieces, optimize them, then
// dump these into outStrips
splitUpStripsAndOptimize(allStrips, outStrips, allEdgeInfos,
outFaceList);
}
}