subdivisionbutterfly.java

java 3d game jme 工程开发源代码

/*
 * 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.
 */
/*
 * Created on 2006-okt-30
 */
package com.jmex.subdivision;

import java.nio.FloatBuffer;
import java.nio.IntBuffer;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.logging.Logger;

import com.jme.scene.TriMesh;
import com.jme.util.geom.BufferUtils;

/**
 * Subdivison according to the Butterfly scheme introduced by 
 * Dyn, Gregory and Levin in 
 * ['A butterfly subdivision scheme for surface interpolation with tension control', ACM Transactions on graphics 9, 2 (1990), pp. 160-169]
 * <br><br>
 * Other papers used during implementetion:<br>
 * 'SIGGRAPH 2000 Course Notes', Denis Zorin et al. (http://mrl.nyu.edu/~dzorin/sig00course/) mainly pp. 69-75 (Contains faulty coefficients on extraordinary crease rule)<br>
 * 'Interpolating Subdivision for Meshes with Arbitrary Topology', Denis Zorin, Peter Schr鰀er, Wim Sweldens. Computer Graphics, Ann. Conf. Series, vol. 30, pp. 189-192, 1996.<br>
 * 'Sharpen&Bend: Recovering curved sharp edges in triangle meshes produced by feature-insensitive sampling', M. Attene, B. Falcidieno, J. Rossignac and M. Spagnuolo. (contains the corrected coefficients, which I had to correct again to get it right. Where it says 'K=degree(V)+1' it should be 'K=degree(V)-1', I think... it works for me)<br>
 * <br>
 * The SIGGRAPH 2000 Course Notes contains detailed descriptions of other subdivison schemes if anyone feels the urge to implement another one,<em>hint, hint</em>. Be sure to contact me if that's the case.<br>
 * Among others: Catmull-Clark, Loop<br>
 * <br>
 *
 * Usage:<br>
 * <code>
 * TriMesh mesh = {some trimesh};<br>
 * Subdivision subdivision = new SubdivisionButterfly(mesh.getBatch(0)); // prepare for subdivision<br>
 * subdivision.subdivide(); // subdivide<br>
 * subdivision.apply(); // Applies the new subdivided buffers to the batch<br>
 * subdivision.computeNormals(); // calculate new normals <br>
 * </code><br>
 * <br>
 * Or you can use it without giving it a batch:<br>
 * <br>
 * <code>
 * Subdivision subdivision = new SubdivisionButterfly();<br>
 * subdivision.setVertexBuffer(batch.getVertexBuffer());<br>
 * subdivision.setIndexBuffer(batch.getIndexBuffer());<br>
 * subdivision.addToBufferList(batch.getTextureBuffer(0), Subdivision.BufferType.TEXTUREBUFFER);<br>
 * subdivision.addToBufferList(batch.getTextureBuffer(1), Subdivision.BufferType.TEXTUREBUFFER);<br>
 * subdivision.addToBufferList(batch.getColorBuffer(), Subdivision.BufferType.COLORBUFFER);<br>
 * subdivision.subdivide(); // subdivide<br>
 * subdivision.apply(mesh.getBatch(0)); // Applies the new subdivided buffers to the batch<br> 
 * subdivision.computeNormals(mesh.getBatch(0)); // calculate new normals<br> 
 * </code>
 * <br>
 * <br>
 * Handles triangular faces only 
 * <br>
 * 
 * @author Tobias Andersson (tobbe.a removethisoryourclientgoesape gmail.com)
 */
public class SubdivisionButterfly extends Subdivision {
    private static final Logger logger = Logger
            .getLogger(SubdivisionButterfly.class.getName());
	
	protected ArrayList<Edge> edges;
	protected ArrayList<Triangle> triangles;
	protected ArrayList<Edge>[] vertexEdgeMap;
	
	
	/**
	 * Constructor
	 */
	public SubdivisionButterfly() {
		super();
	}
	
	/**
	 * @param vertexBuffer
	 * @param indexBuffer
	 */
	public SubdivisionButterfly(FloatBuffer vertexBuffer, IntBuffer indexBuffer) {
		super(vertexBuffer, indexBuffer);
	}
	
	/**
	 * @param mesh The TriMesh that is to be subdivided
	 */
	public SubdivisionButterfly(TriMesh mesh) {
		super(mesh);
	}
	
	/* (non-Javadoc)
	 * @see com.tobbes.subdivision.Subdivision#prepare()
	 */
	/**
	 * Prepare the structures needed for subdividing
	 * 
	 * @return <code>true</code> always :)
	 */
	@Override
	public boolean prepare() {
		findEdgesAndTriangles();
		constructVertexEdgeMap();
		return true;
	}
	
	/* (non-Javadoc)
	 * @see com.tobbes.subdivision.Subdivision#doSubdivide()
	 */
	/**
	 * Do the actual subdivision.<br>
	 * 1. Set up the new buffers<br>
	 * 2. Split all edges and interpolate all buffers according to the Butterfly scheme
	 * 3. Construct new triangles
	 * 
	 * @return <code>true</code> always :)
	 */
	@Override
	protected boolean doSubdivide() {
		
		// **** Set up the new buffers ****
		newVertexBuffer = BufferUtils.createVector3Buffer(getVertexCount() + edges.size()); // every edge makes a new vertex
		getVertexBuffer().rewind();
		newVertexBuffer.put(getVertexBuffer()); // put the old vertex buffer in the beginning of the new. Butterfly is an interpolating scheme and all vertices remain.
		
		newIndexBuffer = BufferUtils.createIntBuffer(getTriangleCount() * 4 * 3); // Every old triangle makes four new
		
		newBuffers = new ArrayList<SubdivisionBuffer>();
		
		SubdivisionBuffer oldBuf;
		FloatBuffer newBuf;
		for (Iterator<SubdivisionBuffer> it = buffers.iterator(); it.hasNext(); ) {
			oldBuf = it.next();
			if (oldBuf != null) {
				oldBuf.buf.rewind();
				newBuf = BufferUtils.createFloatBuffer(oldBuf.buf.capacity() + (edges.size()*oldBuf.elemSize));
				newBuf.put(oldBuf.buf); // put the old buffer in the beginning of the new. Butterfly is an interpolating scheme and all vertices from earlier levels remain the same.
				newBuffers.add(new SubdivisionBuffer(newBuf, oldBuf.type));
			}
		}
		
		// **** Subdivide ****
		Edge edge;
		Vector newVector;
		Rule rule;
		SubdivisionBuffer curOldBuffer;
		SubdivisionBuffer curNewBuffer;
		int bufferNumber = 0;
		
		// For every edge in edgeList, make new vertex
		for (Iterator<Edge> it = edges.iterator() ; it.hasNext(); ) {
			edge = it.next();
			
			// determine which rule to use
			rule = VertexType.getRule(vertexValence[edge.vertexIndex[0]], vertexLocation[edge.vertexIndex[0]], vertexValence[edge.vertexIndex[1]], vertexLocation[edge.vertexIndex[1]]);
			
			// and split the edge according to that rule, once for every buffer
			// First: the vertex buffer
			newVector = rule.split(edge, vertexBuffer, 3, vertexEdgeMap, triangles, vertexValence, vertexLocation);
			edge.newVertexIndex = newVertexBuffer.position() / 3; // Store the index of the new vertex in the split edge
			newVertexBuffer.put(newVector.elem,0,3); // store the new vertex in the new vertex buffer
			
			// Second: the other buffers
			Iterator<SubdivisionBuffer> newBufIt = newBuffers.iterator();
			bufferNumber = 0;
			for (Iterator<SubdivisionBuffer> oldBufIt = buffers.iterator(); oldBufIt.hasNext(); bufferNumber++) {
				curNewBuffer = newBufIt.next();
				curOldBuffer = oldBufIt.next();
				
				if (curOldBuffer.linear) {
					// Those buffers marked as linear should be linearly interpolated, generally they are texture buffers
					newVector = new Vector(curOldBuffer.elemSize);
					newVector.interpolate(
							new Vector(curOldBuffer.elemSize).populateFromBuffer(curOldBuffer.buf, edge.vertexIndex[0]),
							new Vector(curOldBuffer.elemSize).populateFromBuffer(curOldBuffer.buf, edge.vertexIndex[1])
					);
				} else {
					// Otherwise we interpolate according to the Butterfly Scheme
					newVector = rule.split(edge, curOldBuffer.buf, curOldBuffer.elemSize, vertexEdgeMap, triangles, vertexValence, vertexLocation);
				}
				curNewBuffer.buf.put(newVector.elem,0,curNewBuffer.elemSize); // Put the new vector into the buffer
			}
		}
		// Flip all new buffers
		for (Iterator<SubdivisionBuffer> it=newBuffers.iterator(); it.hasNext();) {
			it.next().buf.flip();
		}
		
		
		// **** construct new triangles ***
		Triangle triangle;
		int[] vertices = new int[6];
		int i = 0;
		
		// For every triangle who's edges has a new vertex each, make four new triangles
		for (Iterator<Triangle> it = triangles.iterator() ; it.hasNext() ; ) {
			triangle = it.next();
			vertices[0] = triangle.vertexIndex[0];
			vertices[1] = triangle.vertexIndex[1];
			vertices[2] = triangle.vertexIndex[2];
			vertices[3] = triangle.findEdge(triangle.vertexIndex[0], triangle.vertexIndex[1]).newVertexIndex;
			vertices[4] = triangle.findEdge(triangle.vertexIndex[1], triangle.vertexIndex[2]).newVertexIndex;
			vertices[5] = triangle.findEdge(triangle.vertexIndex[2], triangle.vertexIndex[0]).newVertexIndex;
			
			newIndexBuffer.put(vertices[0]).put(vertices[3]).put(vertices[5]);
			newIndexBuffer.put(vertices[1]).put(vertices[4]).put(vertices[3]);
			newIndexBuffer.put(vertices[2]).put(vertices[5]).put(vertices[4]);
			newIndexBuffer.put(vertices[3]).put(vertices[4]).put(vertices[5]);
			
			i++;
		}
		newIndexBuffer.flip();
		return true;
	}
	
	/**
	 * Get the triangle count of the set index buffer (capacity / 3)
	 * 
	 * @return The triangle count
	 */
	private int getTriangleCount() {
		if (getIndexBuffer() == null) {
			logger.warning("No index buffer set, aborting.");
			return 0;
		}
		return indexBuffer.capacity() / 3;
	}
	
	/**
	 * Finds all edges and triangles in indexBuffer.
	 * 
	 * @see SubdivisionButterfly.Edge
	 * @see SubdivisionButterfly.Triangle
	 */
	private void findEdgesAndTriangles() {
		edges = new ArrayList<Edge>(); // only an approximation
		triangles = new ArrayList<Triangle>(this.getTriangleCount());
		IntBuffer ib = this.getIndexBuffer();
		Edge edge;
		Triangle triangle;
		int i1,i2,i3;		
		
		// go through all the triangles in the indexBuffer and 
		// add to edges and triangles
		ib.rewind();
		while (ib.remaining() >= 3) {
			i1 = ib.get();
			i2 = ib.get();
			i3 = ib.get();
			triangle = new Triangle(i1,i2,i3);
			
			edge = inList(edges, i1, i2);
			if (edge == null) {
				edge = new Edge(i1, i2);
				edges.add(edge);
				edge.triangles[0] = triangle;
			} else {
				edge.triangles[1] = triangle;
			}
			triangle.edges[0] = edge;
			
			edge = inList(edges, i2, i3);
			if (edge == null) {
				edge = new Edge(i2, i3);
				edges.add(edge);
				edge.triangles[0] = triangle;
			} else {
				edge.triangles[1] = triangle;
			}
			triangle.edges[1] = edge;
			
			edge = inList(edges, i3, i1);
			if (edge == null) {
				edge = new Edge(i3, i1);
				edges.add(edge);
				edge.triangles[0] = triangle;
			} else {
				edge.triangles[1] = triangle;
			}
			triangle.edges[2] = edge;
			
			triangles.add(triangle);
		}
	}
	
	
	private Edge inList(ArrayList<Edge> list, int i1, int i2) {
		Edge edge;
		for (int i = 0; i < list.size(); i++) {
			edge = list.get(i);
			if (edge.equals(i1, i2))
				return edge;
		}
		return null;
	}
	
	private int valence(int vertexIndex) {
		return vertexEdgeMap[vertexIndex].size();
	}
	
	/**
	 * Constructs the vertexEdgeMap which, for every vertex, stores that
	 * vertex's edges in a counter-clockwise order. Also, it calculates
	 * <code>Location</code> and <code>Valence</code> of each vertex
	 *
	 * @see SubdivisionButterfly.Location
	 * @see SubdivisionButterfly.Valence
	 */
	@SuppressWarnings ("unchecked")
	private void constructVertexEdgeMap() {
		Edge firstEdge, nextEdge, edge;
		vertexEdgeMap = new ArrayList[this.getVertexCount()];
		vertexLocation = new Location[this.getVertexCount()];
		vertexValence = new Valence[this.getVertexCount()];
		for (int i=0; i < this.getVertexCount() ; i++) {
			// Set the Location of this vertex to INTERIOR, will be changed if appropriate
			vertexLocation[i] = Location.INTERIOR;
			nextEdge = null;
			firstEdge = findOneEdge(i, edges);
			edge = firstEdge;
			vertexEdgeMap[i] = new ArrayList<Edge>();
			while ((!firstEdge.equals(nextEdge)) && edge != null) {
				vertexEdgeMap[i].add(edge);
				nextEdge = findNextCCWEdge(edge, i);
				edge = nextEdge;
			}
			if (edge == null) {
				// As we hit a boundary, we know that the vertex is a boundary vertex
				if (edge == null) vertexLocation[i] = Location.CREASE;
				// We are at a boundary vertex, and we might have missed 
				// some of its edges since we can't circle all around it.
				// TODO: Better solution
				// Temporary solution for now: rewind ClockWise until boundary 
				// is hit on the other side, then redo it CounterClockWise as usual
				edge = firstEdge;
				while (edge != null) {
					nextEdge = edge;
					edge = findNextCWEdge(edge, i);
				}
				firstEdge = nextEdge;
				
				// redo it from the start (the most clockwise edge)
				nextEdge = null;
				edge = firstEdge;
				vertexEdgeMap[i].clear();
				while ((!firstEdge.equals(nextEdge)) && edge != null) {
					vertexEdgeMap[i].add(edge);
					nextEdge = findNextCCWEdge(edge, i);
					edge = nextEdge;
				}
			}
			// Calculate Valence of the vertex
			vertexValence[i] = Valence.getValence(vertexLocation[i], valence(i));
		}
	}
	
	/**
	 * Finds any Edge that contains the vertex index
	 * 
	 *  @return the Edge
	 */
	private Edge findOneEdge(int vertexIndex, ArrayList<Edge> edges) {
		Edge result = null;
		boolean found = false;
		for (Iterator<Edge> it = edges.iterator() ; it.hasNext() && (!found) ; ) {
			result = it.next();
			if (result.hasVertex(vertexIndex)) found = true;			
		}
		return result;
	}
	
	/**
	 * One or two Triangles share an Edge, find the Triangle that is on the counter-clockwise
	 * side of the Edge when looking down the Edge from its vertex vertexIndex
	 *
	 * @see SubdivisionButterfly#findCWTriangle(SubdivisionButterfly.Edge, int)