| /* | |
| * 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); | |
| } | |
| } |