stripifier.java

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

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

	}

}