stripifier.java

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

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