subdivisionbutterfly.java

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

	 * @param edge
	 * 			The edge whos triangles we are examining
	 * @param vertexIndex
	 * 			The vertex of the edge that we are looking down the edge from
	 * @return The counter-clockwise Triangle of the edge, or null if none found
	 */
	private Triangle findCCWTriangle(Edge edge, int vertexIndex) {
		Triangle result = null;
		Triangle[] triangles = edge.triangles;
		if (triangles[0] != null) {
			if (triangles[0].isCCW(edge, vertexIndex)) return triangles[0];
		}
		if (triangles[1] != null) {
			if (triangles[1].isCCW(edge, vertexIndex)) return triangles[1];
		}
		return result;
	}
	
	/**
	 * One or two Triangles share an Edge, find the Triangle that is on the clockwise
	 * side of the Edge when looking down the Edge from its vertex vertexIndex
	 *
	 * @see SubdivisionButterfly#findCCWTriangle(SubdivisionButterfly.Edge, int)
	 * @param edge
	 * 			The edge whos triangles we are examining
	 * @param vertexIndex
	 * 			The vertex of the edge that we are looking down the edge from
	 * @return The clockwise Triangle of the edge, or null if none found
	 */
	private Triangle findCWTriangle(Edge edge, int vertexIndex) {
		Triangle result = null;
		Triangle[] triangles = edge.triangles;
		if (triangles[0] != null) {
			if (!triangles[0].isCCW(edge, vertexIndex)) return triangles[0];
		}
		if (triangles[1] != null) {
			if (!triangles[1].isCCW(edge, vertexIndex)) return triangles[1];
		}
		return result;
	}
	
	/**
	 * Find the next counter-clockwise Edge of the vertex, using this method we can
	 * circle around the vertex and find all its Edges in a CCW order (if it's not a 
	 * boundary vertex)
	 * 
	 * @param edge The current edge
	 * @param vertexIndex The vertex who's edge we want to find
	 * @return The next Edge of the vertex, circling counter-clockwise around the vertex
	 */		
	private Edge findNextCCWEdge(Edge edge, int vertexIndex) {
		Triangle triangle = findCCWTriangle(edge, vertexIndex);
		if (triangle == null) return null;
		return triangle.findOtherSharedEdge(vertexIndex, edge);
	}
	
	/**
	 * Find the next clockwise Edge of the vertex, using this method we can
	 * circle around the vertex and find all its Edges in a CW order (if it's not a 
	 * boundary vertex)
	 * 
	 * @param edge The current edge
	 * @param vertexIndex The vertex who's edge we want to find
	 * @return The next Edge of the vertex, circling clockwise around the vertex
	 */		
	private Edge findNextCWEdge(Edge edge, int vertexIndex) {
		Triangle triangle = findCWTriangle(edge, vertexIndex);
		if (triangle == null) return null;
		return triangle.findOtherSharedEdge(vertexIndex, edge);
	}
	
	/**
	 * Inner helper class for SubdivisonBatch to keep track of the edges
	 * 
	 * @see SubdivisionButterfly#findEdgesAndTriangles()
	 * @author Tobias
	 */
		public class Edge {
		/** The two vertex indices of this Edge */
		public int[] vertexIndex;
		/** The two new Edges that were created when splitting this Edge */ 
		public Edge[] newEdges;
		/** The one or two triangle(s) sharing this edge */ 
		public Triangle[] triangles;
		/** The new vertex that was created when splitting this Edge */
		public int newVertexIndex = -1;
		
		/** Constructor */
		public Edge() {
			vertexIndex = new int[2];
			newEdges = new Edge[2];
			triangles = new Triangle[2];
		}
		
		/**
		 * Constructor
		 * 
		 * @param i1 One vertex index of this Edge
		 * @param i2 The other vertex index of this Edge
		 */
		public Edge(int i1, int i2) {
			this();
			if (i1 < i2) {
				vertexIndex[0] = i1;
				vertexIndex[1] = i2;
			} else {
				vertexIndex[0] = i2;
				vertexIndex[1] = i1;
			}
		}
		
		/**
		 * Does this Edge have the same vertex indices as the provided Edge. 
		 * The order of the vertex indices does not matter.
		 * 
		 * @param edge The Edge to compare this Edge to
		 * @return <code>true</code> if they are the same
		 */
		public boolean equals(Edge edge) {
			if (edge == null) return false;
			return (this.vertexIndex[0] == edge.vertexIndex[0] && this.vertexIndex[1] == edge.vertexIndex[1]) || (this.vertexIndex[1] == edge.vertexIndex[0] && this.vertexIndex[0] == edge.vertexIndex[1]);
		}
		
		/**
		 * Does this Edge have the same vertex indices as those provided. 
		 * The order of the vertex indices does not matter.
		 *
		 * @param i1 One vertex index
		 * @param i2 Another vertex index
		 * @return <code>true</code> if the vertex indices in this Edge are the same as those provided
		 */
		public boolean equals(int i1, int i2) {
			return (this.vertexIndex[0] == i1 && this.vertexIndex[1] == i2) || (this.vertexIndex[1] == i1 && this.vertexIndex[0] == i2);
		}
		
		/** 
		 * @param vertexIndex The index to look for
		 * @return <code>true</code> if this Edge contains the provided vertexIndex
		 */
		public boolean hasVertex(int vertexIndex) {
			if (this.vertexIndex[0] == vertexIndex) return true;
			if (this.vertexIndex[1] == vertexIndex) return true;
			return false;
		}
		
		/**
		 * @param vertexIndex The index that we already know of of this Edge
		 * @return The other vertex index of this Edge
		 */
		public int otherVertex(int vertexIndex) {
			if (this.vertexIndex[0] == vertexIndex) return this.vertexIndex[1];
			if (this.vertexIndex[1] == vertexIndex) return this.vertexIndex[0];
			return -1;
		}
		
		/**
		 * @return a String representing this Edge
		 */
		public String toString() {
			return "{" + vertexIndex[0] + "," + vertexIndex[1] + "}";
		}
	}
	
	
	/**
	 * Inner helper class for SubdivisonBatch to keep track of the triangles
	 * 
	 * @see SubdivisionButterfly#findEdgesAndTriangles()
	 * @author Tobias
	 */
	public class Triangle {
		/** The three vertex indices of this Triangle */
		public int[] vertexIndex;
		/** The three Edges of this Triangle */
		public Edge[] edges;
		
		/** Constructor */
		public Triangle() {
			vertexIndex = new int[3];
			edges = new Edge[3];
		}
		
		/**
		 * Constructor
		 * 
		 * @param i1 
		 * @param i2
		 * @param i3 The three vertex indices of this Triangle
		 */
		public Triangle(int i1, int i2, int i3) {
			this();
			vertexIndex[0] = i1;
			vertexIndex[1] = i2;
			vertexIndex[2] = i3;
		}
		
		/** 
		 * Does this Triangle contain the given Edge?
		 * 
		 * @param edge The edge to look for
		 * @return <code>true</code> if the edge is found
		 */
		public boolean hasEdge(Edge edge) {
			boolean result = false;
			for (int i=0 ; i < 3 ; i++) {
				if (edge.equals(edges[i])) result = true;
			}
			return result;
		}
		
		/**
		 * Returns true if the triangle is counter-clockwise from the edges point of view,
		 * looking down the edge starting at vertex vertexIndex
		 * 
		 * @param edge
		 * @param vertexIndex
		 * @return Whether the triangle is counter-clockwise from the edges point of view
		 */
		public boolean isCCW(Edge edge, int vertexIndex) {
			if (this.vertexIndex[0] == vertexIndex) {
				if (this.vertexIndex[1] == edge.otherVertex(vertexIndex)) {
					return true;
				}
			}
			if (this.vertexIndex[1] == vertexIndex) {
				if (this.vertexIndex[2] == edge.otherVertex(vertexIndex)) {
					return true;
				}
			}
			if (this.vertexIndex[2] == vertexIndex) {
				if (this.vertexIndex[0] == edge.otherVertex(vertexIndex)) {
					return true;
				}
			}
			return false;
		}
		
		/**
		 * Find the Edge of this Triangle with the provided vertex indices
		 * 
		 * @param vertexIndex1
		 * @param vertexIndex2
		 * @return The found Edge, or null if none was found in this Triangle
		 */
		public Edge findEdge(int vertexIndex1, int vertexIndex2) {
			Edge result = null;
			if (edges[0].equals(vertexIndex1, vertexIndex2)) result = edges[0];
			if (edges[1].equals(vertexIndex1, vertexIndex2)) result = edges[1];
			if (edges[2].equals(vertexIndex1, vertexIndex2)) result = edges[2];
			return result;
		}
		
		/**
		 * Given two vertex indices of this Triangle, find the third vertex index 
		 * 
		 * @param edge The edge that defines the other two vertex indices
		 * @return The third vertex index
		 */
		public int findThirdVertex(Edge edge) {
			int result = -1;
			if (edge.equals(vertexIndex[0], vertexIndex[1])) result = vertexIndex[2];
			if (edge.equals(vertexIndex[1], vertexIndex[2])) result = vertexIndex[0];
			if (edge.equals(vertexIndex[0], vertexIndex[2])) result = vertexIndex[1];
			return result;
		}
		
		/**
		 * Given two vertex indices of this Triangle, find the third vertex index 
		 * 
		 * @param vertexIndex1
		 * @param vertexIndex2
		 * @return The third vertex index
		 */
		public int findThirdVertex(int vertexIndex1, int vertexIndex2) {
			return findThirdVertex(new Edge(vertexIndex1, vertexIndex2));
		}
		
		/**
		 *  Finds the other edge in this triangle which has the vertex
		 *  i.e. if edge=a,b and vertex=a then otherEdge=a,c is returned 
		 *  
		 *  @param vertexIndex The vertex index who's other Edge we want to find
		 *  @param edge The edge we already know of
		 *  @return The other edge, or null if vertex index or Edge provided are not in the triangle
		 */
		public Edge findOtherSharedEdge(int vertexIndex, Edge edge) {
			if (edges[0].hasVertex(vertexIndex) && (!edges[0].equals(edge))) return edges[0];
			if (edges[1].hasVertex(vertexIndex) && (!edges[1].equals(edge))) return edges[1];
			if (edges[2].hasVertex(vertexIndex) && (!edges[2].equals(edge))) return edges[2];
			return null; // should never happen
		}
		
		/**
		 * @return A String representing this Triangle
		 */
		public String toString() {
			String ret = "{" + vertexIndex[0] + "," + vertexIndex[1] + "," + vertexIndex[2] + "}";
			return ret;
		}
	}
	/**
	 * Maps vertex indices to the enum <code>Location</code>
	 */
	Location[] vertexLocation;
	
	/**
	 * Maps vertex indices to the enum <code>Valence</code>
	 */
	Valence[] vertexValence;
	
	/**
	 * Which rule to use when splitting a certain <code>Edge</code><br>
	 * See Page 73-75 in SIGGRAPH 2000 Course Notes, Denis Zorin, et al.
	 * 
	 * @author Tobias
	 */
	public enum Rule {
		STANDARD { 
			Vector split(Edge edge, FloatBuffer vb, int bufferElementSize, ArrayList<Edge>[] vertexEdgeMap, ArrayList<Triangle> triangles, Valence[] vertexValence, Location[] vertexLocation) {
				Rule.standard++;
				newVector = regularButterfly(edge, edge.vertexIndex[0], vb, bufferElementSize, vertexEdgeMap[edge.vertexIndex[0]])
				.addLocal(regularButterfly(edge, edge.vertexIndex[1], vb, bufferElementSize, vertexEdgeMap[edge.vertexIndex[1]]));
				return newVector;
			} 
		}, 				
		REGULAR_INTERIOR_CREASE { 
			Vector split(Edge edge, FloatBuffer vb, int bufferElementSize, ArrayList<Edge>[] vertexEdgeMap, ArrayList<Triangle> triangles, Valence[] vertexValence, Location[] vertexLocation) {
				Rule.regularInteriorCrease++;
				int interiorVertex;
				if (vertexLocation[edge.vertexIndex[0]] == Location.INTERIOR)
					interiorVertex = 0;
				else
					interiorVertex = 1;
				newVector = regularInteriorCrease(edge, edge.vertexIndex[interiorVertex], vb, bufferElementSize, vertexEdgeMap[edge.vertexIndex[interiorVertex]], vertexEdgeMap[edge.vertexIndex[interiorVertex==0?1:0]]);
				return newVector;
			} 
		}, 
		REGULAR_CREASE_CREASE { 
			Vector split(Edge edge, FloatBuffer vb, int bufferElementSize, ArrayList<Edge>[] vertexEdgeMap, ArrayList<Triangle> triangles, Valence[] vertexValence, Location[] vertexLocation) {
				Rule.regularCreaseCrease++;
				newVector = regularCreaseCrease(edge, vb, bufferElementSize, vertexEdgeMap);
				return newVector;
			} 
		},
		EXTRAORDINARY_AVERAGE { 
			Vector split(Edge edge, FloatBuffer vb, int bufferElementSize, ArrayList<Edge>[] vertexEdgeMap, ArrayList<Triangle> triangles, Valence[] vertexValence, Location[] vertexLocation) {
				Rule.extraordinaryAverage++;
				newVector = extraordinaryInterior(edge, edge.vertexIndex[0], vb, bufferElementSize, vertexEdgeMap[edge.vertexIndex[0]], triangles)
				.addLocal(extraordinaryInterior(edge, edge.vertexIndex[1], vb, bufferElementSize, vertexEdgeMap[edge.vertexIndex[1]], triangles));
				newVector.multLocal(1f/2f);
				return newVector;
			} 
		}, 	
		EXTRAORDINARY_INTERIOR { 
			Vector split(Edge edge, FloatBuffer vb, int bufferElementSize, ArrayList<Edge>[] vertexEdgeMap, ArrayList<Triangle> triangles, Valence[] vertexValence, Location[] vertexLocation) {
				Rule.extraordinaryInterior++;
				int extraordinaryVertex;
				if (vertexValence[edge.vertexIndex[0]] == Valence.EXTRAORDINARY)
					extraordinaryVertex = 0;
				else
					extraordinaryVertex = 1;
				newVector = extraordinaryInterior(edge, edge.vertexIndex[extraordinaryVertex], vb, bufferElementSize, vertexEdgeMap[edge.vertexIndex[extraordinaryVertex]], triangles);
				return newVector;
			} 
		}, 	
		EXTRAORDINARY_CREASE { 
			Vector split(Edge edge, FloatBuffer vb, int bufferElementSize, ArrayList<Edge>[] vertexEdgeMap, ArrayList<Triangle> triangles, Valence[] vertexValence, Location[] vertexLocation) {
				Rule.extraordinaryCrease++;
				int extraordinaryVertex;
				if (vertexValence[edge.vertexIndex[0]] == Valence.EXTRAORDINARY)
					extraordinaryVertex = 0;
				else
					extraordinaryVertex = 1;
				newVector = extraordinaryCrease(edge, edge.vertexIndex[extraordinaryVertex], vb, bufferElementSize, vertexEdgeMap[edge.vertexIndex[extraordinaryVertex]]);
				return newVector;
//				return null;//newVertex;
			} 
		}; 
		
		private final static float WEIGHT = 0f;
		
		Vector newVector = null;
		
		abstract Vector split(Edge edge, FloatBuffer vb, int bufferElementSize, ArrayList<Edge>[] vertexEdgeMap, ArrayList<Triangle> triangles, Valence[] vertexValence, Location[] vertexLocation);
		
		private static Vector extraordinaryCrease(Edge edge, int vertexIndex, FloatBuffer vb, int bufferElementSize, ArrayList<Edge> edges) {
			Vector result = new Vector(bufferElementSize);
			int valence = edges.size();
			int k = valence - 1;// - 1;
			int v[] = new int[valence];
			int i=-1;
			double theta = Math.PI / (double)k; // (k-1)
			double c = 0f;
			
			Edge tempEdge;
			
			int j = valence-1;
			for (Iterator<Edge> it = edges.iterator() ; it.hasNext() ; ) {
				tempEdge = it.next();
				v[j] = tempEdge.otherVertex(vertexIndex);
				if (tempEdge.equals(edge)) i = j;
				j--;
			}