stripifier.java

来自「java 3d game jme 工程开发源代码」· Java 代码 · 共 1,365 行 · 第 1/3 页

/*
 * 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 com.jme.util.geom.nvtristrip;

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()
	//