clodcreator.java

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

/*
 * 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.scene.lod;

import java.nio.FloatBuffer;
import java.nio.IntBuffer;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeSet;
import java.util.Map.Entry;

import com.jme.math.Vector3f;
import com.jme.util.geom.BufferUtils;

/**
 * <code>ClodCreator</code> originally ported from David Eberly's c++,
 * modifications and enhancements made from there.<br>
 * <br>
 * This class is used by ClodMesh to create automatically generated records. The
 * reason for lack of documentation is that it should have little use to someone
 * outside the API, unless they already know how to use it.
 * 
 * @author Joshua Slack
 * @version $Id: ClodCreator.java,v 1.21 2007/08/20 10:28:23 rherlitz Exp $
 */

public class ClodCreator extends VETMesh {
	private FloatBuffer vertices;

	private FloatBuffer normals;

	private FloatBuffer colors;

	private FloatBuffer textures;

	private IntBuffer indices;

	private int currentVertex, currentTriangle, numbTriangles, vertQuantity;

	private int[] orderedVertices;

	private int[] permuteVertices;

	private int[] newIndices;

	int heapSize;

	HeapRecord[] heapArray;

	boolean collapsing;

	// for reordering vertices and triangles
	TreeSet<Integer> deletedVertices;

	ArrayList<CollapseRecord> deletedEdges;

	CollapseRecord[] records;

	private static final Vector3f tempVa = new Vector3f();

	private static final Vector3f tempVb = new Vector3f();

	private static final Vector3f tempVc = new Vector3f();

	private static final Vector3f tempVd = new Vector3f();

	protected class HeapRecord {
		public HeapRecord() {
			m_kEdge = new Edge(-1, -1);
			m_iHIndex = -1;
			m_fMetric = -1.0f;
		}

		public Edge m_kEdge;

		public int m_iHIndex;

		public float m_fMetric;

		public boolean equals(Object obj) {
			HeapRecord rkH = (HeapRecord) obj;
			return m_kEdge.equals(rkH.m_kEdge);
		}
	};

	public ClodCreator(FloatBuffer vertexArray, FloatBuffer normalArray,
			FloatBuffer colorArray, FloatBuffer textureArray,
			IntBuffer indiceArray) {
		// Hang onto these to avoid having to pass them through member function
		// calls.
		this.vertices = vertexArray;
		this.normals = normalArray;
		this.colors = colorArray;
		this.textures = textureArray;
		this.indices = indiceArray;
		vertQuantity = vertexArray.capacity() / 3;
		numbTriangles = indiceArray.capacity() / 3;

		// for reordering vertices and triangles
		currentVertex = vertQuantity - 1;
		currentTriangle = numbTriangles - 1;
		orderedVertices = new int[vertQuantity];
		permuteVertices = new int[vertQuantity];
		newIndices = new int[indices.capacity()];

		deletedEdges = new ArrayList<CollapseRecord>();
		deletedVertices = new TreeSet<Integer>();

		// Insert the triangles into the mesh.  The triangle indices are attached
		// as extra data.
		collapsing = false;
		for (int i = 0; i < numbTriangles; i++) {
			//      int iV0 = m_aiConnect[3 * i];
			//      int iV1 = m_aiConnect[3 * i + 1];
			//      int iV2 = m_aiConnect[3 * i + 2];
			//      if (!(iV0 != iV1 && iV0 != iV2 && iV1 != iV2)) throw new AssertionError();
			Triangle tri = new Triangle(indices.get(3 * i), indices
					.get(3 * i + 1), indices.get(3 * i + 2));
			insertTriangle(tri);
			setData(tri, new Integer(i));
		}

		if (triangleMap.size() != numbTriangles) {
			// We must have duplicates...  lets weed them out and make a new Clod.
			IntBuffer redoneIndices = BufferUtils.createIntBuffer(triangleMap
					.size() * 3);
			Iterator<Triangle> it = triangleMap.keySet().iterator();
			while (it.hasNext()) {
				Triangle t = it.next();
				redoneIndices.put(t.vert[0]);
				redoneIndices.put(t.vert[1]);
				redoneIndices.put(t.vert[2]);
			}
			ClodCreator creator = new ClodCreator(vertexArray, normalArray,
					colorArray, textureArray, redoneIndices);
			records = creator.getRecords();
			creator = null;
			// Copy the reduced indices back to the original indice array.  There will
			// be some bogus ones on the end, but thats ok because they will never be shown thanks to
			// the number of triangles field.
			indices.rewind();
			indices.put(redoneIndices);

			// clear the triangle map so a call to remove triangles doesn't bomb.
			triangleMap.clear();
			return;
		}

		//    if (m_kVMap.size() != m_akVertex.length)throw new AssertionError();
		//    if (m_kTMap.size() != m_iTQuantity)throw new AssertionError(
		//        "triangle map size: " + m_kTMap.size() + " != m_iTQuantity: " +
		//        m_iTQuantity);

		initializeHeap();

		collapsing = true;
		while (heapSize > 0) {
			if (heapArray[0].m_fMetric == Float.MAX_VALUE) {
				// all remaining heap elements have infinite weight
				flushVertices();
				flushTriangles();
				break;
			}

			doCollapse();

			//      if (! ( (m_kVMap.size()) == m_iVCurrent + 1))throw new AssertionError();
			//      if (! ( (m_kTMap.size()) == m_iTCurrent + 1))throw new AssertionError(
			//          "triangle map size: " + m_kTMap.size() + " != m_iTCurrent+1: " +
			//          (m_iTCurrent + 1));
		}

		collapsing = false;

		// Permute the vertices and triangle connectivity so that the last
		// vertex/triangle in the array is the first vertex/triangle to be
		// removed.
		reorder();

		// The collapse records store the incremental changes that are used for
		// dynamic LOD changes in the caller of this constructor.
		records = computeRecords();
	}

	public CollapseRecord[] getRecords() {
		return records;
	}

	public void doCollapse() {
		// Define a 2-edge to be an edge that has exactly two triangles sharing
		// it.  An edge is collapsible if it is a 2-edge and has at least one end
		// point whose sharing edges are all 2-edges.  In this case, such an end
		// point will be the 'throw' vertex.  This keeps the boundary and junction
		// edges from changing geometry and helps preserve the shape of the mesh.
		// The topology is always guaranteed not to change.

		// When this function is called, the metric has already been calculated
		// and is finite (so exactly two triangles must be sharing this edge).
		//    if (!(m_apkHeap[0].m_fMetric < Float.MAX_VALUE)) throw new AssertionError();
		Edge kEdge = heapArray[0].m_kEdge;

		// test end points to see if either has only 2-edges sharing it
		int i;
		for (i = 0; i < 2; i++) {
			ExVector pkESet = (ExVector) getEdges(kEdge.vert[i]).clone();
			int j;
			for (j = 0; j < pkESet.size(); j++) {
				EdgeAttribute pkEM = edgeMap.get(pkESet
						.toArray()[j]);
				//        if (!(pkEM != null)) throw new AssertionError();
				if (pkEM.triangleSet.size() != 2)
					break;
			}

			if (j == pkESet.size()) {
				// all edges sharing this end point are 2-edges
				break;
			}
		}

		if (i < 2) {
			int iVThrow = kEdge.vert[i];
			int iVKeep = kEdge.vert[1 - i];
			if (!collapseCausesFolding(iVKeep, iVThrow)) {
				remove();
				collapseEdge(iVKeep, iVThrow);
				return;
			}
		}

		// edge not collapsible, assign it infinite weight and update the heap
		update(0, Float.MAX_VALUE);
	}

	public boolean collapseCausesFolding(int iVKeep, int iVThrow) {
		VertexAttribute pkVT = vertexMap.get(new Integer(
				iVThrow));
		//    if (!(pkVT != null)) throw new AssertionError();

		Edge kCollapse = new Edge(iVKeep, iVThrow);
		for (int j = 0; j < pkVT.triangleSet.size(); j++) {
			Triangle kT = (Triangle) pkVT.triangleSet.toArray()[j];
			if (kCollapse.equals(new Edge(kT.vert[0], kT.vert[1]))
					|| kCollapse.equals(new Edge(kT.vert[1], kT.vert[2]))
					|| kCollapse.equals(new Edge(kT.vert[2], kT.vert[0]))) {
				// This triangle would be removed in a collapse, so it does not
				// contribute to any folding.
				continue;
			}

			for (int i = 0; i < 3; i++) {
				if (kT.vert[i] == iVThrow) {
					// Test if potential replacement triangle (either ordering)
					// is in the mesh.
					int iV0 = iVKeep;
					int iV1 = kT.vert[(i + 1) % 3];
					int iV2 = kT.vert[(i + 2) % 3];

					if (triangleMap.get(new Triangle(iV0, iV1, iV2)) != null
							|| triangleMap.get(new Triangle(iV0, iV2, iV1)) != null) {
						return true;
					}
				}
			}
		}

		return false;
	}

	public float getMetric(Edge pkE, EdgeAttribute pkEA) {
		float fLengthWeight = 10.0f;
		float fAngleWeight = 1.0f;

		// Compute the metric for the edge.  Only manifold edges (exactly two
		// triangles sharing the edge) are allowed to collapse.
		if (pkEA.triangleSet.size() == 2) {
			// length contribution
			BufferUtils.populateFromBuffer(tempVa, vertices, pkE.vert[0]);
			BufferUtils.populateFromBuffer(tempVb, vertices, pkE.vert[1]);
			Vector3f kDiff = tempVa.subtractLocal(tempVb);
			float fMetric = fLengthWeight * kDiff.length();

			// angle/area contribution
			Triangle kT = (Triangle) pkEA.triangleSet.toArray()[0];
			BufferUtils.populateFromBuffer(tempVc, vertices, kT.vert[0]);
			BufferUtils.populateFromBuffer(tempVa, vertices, kT.vert[1]);
			BufferUtils.populateFromBuffer(tempVb, vertices, kT.vert[2]);
			Vector3f kE0 = tempVa.subtractLocal(tempVc);
			Vector3f kE1 = tempVb.subtractLocal(tempVc);
			Vector3f kN0 = kE0.cross(kE1, tempVc);

			kT = (Triangle) pkEA.triangleSet.toArray()[1];
			BufferUtils.populateFromBuffer(tempVd, vertices, kT.vert[0]);
			BufferUtils.populateFromBuffer(tempVa, vertices, kT.vert[1]);
			BufferUtils.populateFromBuffer(tempVb, vertices, kT.vert[2]);
			kE0 = tempVa.subtractLocal(tempVd);
			kE1 = tempVb.subtractLocal(tempVd);
			Vector3f kN1 = kE0.crossLocal(kE1);

			Vector3f kCross = kN0.cross(kN1, tempVa);
			fMetric += fAngleWeight * kCross.length();

			return fMetric;
		}

		// Boundary edges (one triangle containing edge) and junction edges
		// (3 or more triangles sharing edge) are not allowed to collapse.
		return Float.MAX_VALUE;
	}

	public void removeTriangle(Triangle rkT) {
		// If the triangle is an original one, reorder the connectivity array so
		// that the triangle occurs at the end.
		int iTIndex = ((Integer) getData(rkT)).intValue();
		if (iTIndex >= 0) {
			//      if (!(m_iTCurrent >= 0)) throw new AssertionError();
			newIndices[3 * currentTriangle] = indices.get(3 * iTIndex);
			newIndices[3 * currentTriangle + 1] = indices.get(3 * iTIndex + 1);
			newIndices[3 * currentTriangle + 2] = indices.get(3 * iTIndex + 2);
			currentTriangle--;
		}

		super.removeTriangle(rkT);
	}

	public void modifyTriangle(Triangle rkT, int iVKeep, int iVThrow) {
		// Get the index of the pre-modified triangle, then remove the triangle
		// from the mesh.
		int iTIndex = ((Integer) getData(rkT)).intValue();
		super.removeTriangle(rkT);

		// replace 'throw' by 'keep'
		for (int i = 0; i < 3; i++) {
			if (rkT.vert[i] == iVThrow) {
				rkT.vert[i] = iVKeep;
				break;
			}
		}

		// Indices on modified triangles are the same as the indices on the
		// pre-modified triangles.
		insertTriangle(rkT);
		setData(rkT, new Integer(iTIndex));
	}

	public void collapseEdge(int iVKeep, int iVThrow) {
		// find the edge to collapse
		Edge kCollapse = new Edge(iVKeep, iVThrow);
		EdgeAttribute pkEM = edgeMap.get(kCollapse);
		//    if (pkEM == null) throw new AssertionError("Edge unexpectedly missing from EdgeMap!");

		// keep track of vertices that are deleted in the collapse
		deletedVertices.clear();

		// Remove the collapse-edge-shared triangles.  Using a copy of the
		// triangle set from the collapse edge is required since removal of the
		// last triangle sharing the collapse edge will remove that edge from
		// the edge map, thereby invalidating any iterator that points to data
		// in the collapse edge.
		ExVector kTSet = (ExVector) pkEM.triangleSet.clone(); // <Triangle>
		int iTDeletions = kTSet.size();
		//    if (!(iTDeletions > 0)) throw new AssertionError();
		for (int j = 0; j < kTSet.size(); j++)
			removeTriangle((Triangle) kTSet.toArray()[j]);

		// Replace 'throw' vertices by 'keep' vertices in the remaining triangles
		// at the 'throw' vertex.  The old triangles are removed and the modified
		// triangles are inserted.
		Triangle kT;
		VertexAttribute pkVM = vertexMap.get(new Integer(
				iVThrow));
		if (pkVM != null) {
			kTSet = (ExVector) pkVM.triangleSet.clone();
			for (int j = 0; j < kTSet.size(); j++) {
				kT = (Triangle) kTSet.toArray()[j];
				modifyTriangle(kT, iVKeep, iVThrow);
			}
		}

		// The set of potentially modified edges consists of all those edges that
		// are shared by the triangles containing the 'keep' vertex.  Modify these
		// metrics and update the heap.
		TreeSet<Edge> kModified = new TreeSet<Edge>();
		ExVector pkTSet = (ExVector) getTriangles(iVKeep).clone(); // <Triangle>
		if (pkTSet != null) {
			kTSet = (ExVector) pkTSet.clone();
			for (int j = 0; j < kTSet.size(); j++) {
				kT = (Triangle) kTSet.toArray()[j];
				kModified.add(new Edge(kT.vert[0], kT.vert[1]));
				kModified.add(new Edge(kT.vert[1], kT.vert[2]));
				kModified.add(new Edge(kT.vert[2], kT.vert[0]));
			}

			Iterator<Edge> it = kModified.iterator();
			while (it.hasNext()) {
				Edge pkES = it.next();
				pkEM = edgeMap.get(pkES);
				HeapRecord pkRecord = (HeapRecord) pkEM.data;
				float fMetric = getMetric(pkES, pkEM);
				if (pkRecord.m_iHIndex >= 0)
					update(pkRecord.m_iHIndex, fMetric);
			}
		}

		// save vertex reordering information
		Iterator it = deletedVertices.iterator();
		int iV;
		while (it.hasNext()) {