vetmesh.java

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

		// Do a depth-first search of the mesh to find connected components.
		int iTSize = triangleMap.size();
		if (iTSize == 0) {
			raiConnect = null;
			return;
		}

		int iIQuantity = 3 * iTSize;
		int iIndex = 0;
		raiConnect = new int[iIQuantity];

		// for marking visited triangles during the traversal
		TreeMap<Triangle, Boolean> kVisitedMap = new TreeMap<Triangle, Boolean>(); 
		Iterator<Triangle> it = triangleMap.keySet().iterator();
		while (it.hasNext()) {
			kVisitedMap.put(it.next(), Boolean.FALSE);
		}

		while (iTSize > 0) {
			// find an unvisited triangle in the mesh
			Stack<Triangle> kStack = new Stack<Triangle>();
			Iterator<Triangle> visIt = kVisitedMap.keySet().iterator();
			while (visIt.hasNext()) {
				Triangle tri = visIt.next();
				if (Boolean.FALSE.equals(kVisitedMap.get(tri))) {
					// this triangle not yet visited
					kStack.push(tri);
					kVisitedMap.put(tri, Boolean.TRUE);
					iTSize--;
					break;
				}
			}

			// traverse the connected component of the starting triangle
			VETMesh pkComponent = create();
			Iterator triIt;
			while (!kStack.empty()) {
				// start at the current triangle
				Triangle kT = kStack.pop();
				pkComponent.insertTriangle(kT);

				for (int i = 0; i < 3; i++) {
					// get an edge of the current triangle
					Edge kE = new Edge(kT.vert[i], kT.vert[(i + 1) % 3]);
					EdgeAttribute pkE = edgeMap.get(kE);

					// visit each adjacent triangle
					ExVector rkTSet = (ExVector) pkE.triangleSet.clone(); // <Triangle>
					triIt = rkTSet.iterator();
					while (triIt.hasNext()) {
						Triangle rkTAdj = (Triangle) triIt.next();
						if (Boolean.FALSE.equals(kVisitedMap.get(rkTAdj))) {
							// this adjacent triangle not yet visited
							kStack.push(rkTAdj);
							kVisitedMap.put(rkTAdj, Boolean.TRUE);
							iTSize--;
						}
					}
				}
			}

			// store the connectivity information for this component
			TreeSet<Triangle> kTSet = new TreeSet<Triangle>();
			pkComponent.getTriangles(kTSet);
			pkComponent = null;

			rkIndex.add(new Integer(iIndex));
			Iterator<Triangle> tsetIter = kTSet.iterator();
			while (tsetIter.hasNext()) {
				Triangle rkT = tsetIter.next();
				raiConnect[iIndex++] = rkT.vert[0];
				raiConnect[iIndex++] = rkT.vert[1];
				raiConnect[iIndex++] = rkT.vert[2];
			}
		}

		rkIndex.add(new Integer(iIQuantity));
	}

	// Extract a connected component from the mesh and remove all the
	// triangles of the component from the mesh.  This is useful for computing
	// the components in a very large mesh that uses a lot of memory.  The
	// intention is that the function is called until all components are
	// found.  The typical code is
	//
	//     VETMesh kMesh = <some mesh>;
	//     int iITotalQuantity = 3*kMesh.GetTriangleQuantity();
	//     int* aiConnect = new int[iITotalQuantity];
	//     for (int iIQuantity = 0; iIQuantity < iITotalQuantity; /**/ )
	//     {
	//         int iCurrentIQuantity;
	//         int* aiCurrentConnect = aiConnect + iIQuantity;
	//         kMesh.RemoveComponent(iCurrentIQuantity,aiCurrentConnect);
	//         iIQuantity += iCurrentIQuantity;
	//     }

	public int removeComponent(int[] aiConnect) {
		// Do a depth-first search of the mesh to find connected components.  The
		// input array is assumed to be large enough to hold the component (see
		// the comments in WmlTriangleMesh.h for RemoveComponent).
		int riIQuantity = 0;

		int iTSize = triangleMap.size();
		if (iTSize == 0)
			return riIQuantity;

		// Find the connected component containing the first triangle in the mesh.
		// A set is used instead of a stack to avoid having a large-memory
		// 'visited' map.
		TreeSet<Triangle> kVisited = new TreeSet<Triangle>();
		kVisited.add((Triangle)triangleMap.keySet().toArray()[0]);

		// traverse the connected component
		Iterator triIt;
		while (!kVisited.isEmpty()) {
			// start at the current triangle
			Triangle kT = (Triangle) kVisited.toArray()[0];

			// add adjacent triangles to the set for recursive processing
			for (int i = 0; i < 3; i++) {
				// get an edge of the current triangle
				Edge kE = new Edge(kT.vert[i], kT.vert[(i + 1) % 3]);
				EdgeAttribute pkE = edgeMap.get(kE);

				// visit each adjacent triangle
				ExVector rkTSet = (ExVector) pkE.triangleSet.clone(); // <Triangle>
				triIt = rkTSet.iterator();
				while (triIt.hasNext()) {
					Triangle kTAdj = (Triangle) triIt.next();
					if (!kTAdj.equals(kT))
						kVisited.add(kTAdj);
				}
			}

			// add triangle to connectivity array
			aiConnect[riIQuantity++] = kT.vert[0];
			aiConnect[riIQuantity++] = kT.vert[1];
			aiConnect[riIQuantity++] = kT.vert[2];

			// remove the current triangle (visited, no longer needed)
			kVisited.remove(kT);
			removeTriangle(kT);
		}
		return riIQuantity;
	}

	// Extract the connected components from the mesh, but each component has
	// a consistent ordering across all triangles of that component.  The
	// mesh must be manifold.  The return value is 'true' if and only if the
	// mesh is manifold.  If the mesh has multiple components, each component
	// will have a consistent ordering.  However, the mesh knows nothing about
	// the mesh geometry, so it is possible that ordering across components is
	// not consistent.  For example, if the mesh has two disjoint closed
	// manifold components, one of them could have an ordering that implies
	// outward pointing normals and the other inward pointing normals.
	//
	// NOTE.  It is possible to create a nonorientable mesh such as a Moebius
	// strip.  In this case, GetConsistentComponents will return connected
	// components, but in fact the triangles will not (and can not) be
	// consistently ordered.
	public boolean getConsistentComponents(Vector<VETMesh> store) {
		if (!isManifold())
			return false;

		// Do a depth-first search of the mesh to find connected components.
		int iTSize = triangleMap.size();
		if (iTSize == 0)
			return true;

		// for marking visited triangles during the traversal
		TreeMap<Triangle, Boolean> kVisitedMap = new TreeMap<Triangle, Boolean>();
		Iterator<Triangle> it = triangleMap.keySet().iterator();
		while (it.hasNext()) {
			kVisitedMap.put(it.next(), Boolean.FALSE);
		}

		while (iTSize > 0) {
			// Find an unvisited triangle in the mesh.  Any triangle pushed onto
			// the stack is considered to have a consistent ordering.
			Stack<Triangle> kStack = new Stack<Triangle>();
			Iterator<Triangle> visIt = kVisitedMap.keySet().iterator();
			while (visIt.hasNext()) {
				Triangle tri = visIt.next();
				if (Boolean.FALSE.equals(kVisitedMap.get(tri))) {
					// this triangle not yet visited
					kStack.push(tri);
					kVisitedMap.put(tri, Boolean.TRUE);
					iTSize--;
					break;
				}
			}

			// traverse the connected component of the starting triangle
			VETMesh component = create();
			while (!kStack.empty()) {
				// start at the current triangle
				Triangle kT = kStack.pop();
				component.insertTriangle(kT);

				for (int i = 0; i < 3; i++) {
					// get an edge of the current triangle
					int iV0 = kT.vert[i], iV1 = kT.vert[(i + 1) % 3], iV2;
					Edge kE = new Edge(iV0, iV1);
					EdgeAttribute pkE = edgeMap.get(kE);

					int iSize = pkE.triangleSet.size();
					Triangle pkTAdj = (Triangle) pkE.triangleSet.toArray()[0];
					if (iSize == 2) {
						// get the adjacent triangle to the current one
						if (pkTAdj.equals(kT))
							pkTAdj = (Triangle) pkE.triangleSet.toArray()[1];

						if (Boolean.FALSE.equals(kVisitedMap.get(pkTAdj))) {
							// adjacent triangle not yet visited
							if ((pkTAdj.vert[0] == iV0 && pkTAdj.vert[1] == iV1)
									|| (pkTAdj.vert[1] == iV0 && pkTAdj.vert[2] == iV1)
									|| (pkTAdj.vert[2] == iV0 && pkTAdj.vert[0] == iV1)) {
								// adjacent triangle must be reordered
								iV0 = pkTAdj.vert[0];
								iV1 = pkTAdj.vert[1];
								iV2 = pkTAdj.vert[2];
								kVisitedMap.remove(pkTAdj);
								removeTriangle(iV0, iV1, iV2);
								insertTriangle(iV1, iV0, iV2);
								kVisitedMap.put(new Triangle(iV1, iV0, iV2),
										Boolean.FALSE);

								// refresh the iterators since maps changed
								pkE = edgeMap.get(kE);
								pkTAdj = (Triangle) pkE.triangleSet.toArray()[0];
								if (pkTAdj == kT)
									pkTAdj = (Triangle) pkE.triangleSet
											.toArray()[1];
							}

							kStack.push(pkTAdj);
							kVisitedMap.put(pkTAdj, Boolean.TRUE);
							iTSize--;
						}
					}
				}
			}
			store.add(component);
		}

		return true;
	}

	// Reverse the ordering of all triangles in the mesh.
	public VETMesh getReversedOrderMesh() {
		VETMesh reversed = create();

		Iterator<Triangle> it = triangleMap.keySet().iterator();
		while (it.hasNext()) {
			Triangle tri = it.next();
			reversed.insertTriangle(tri.vert[0], tri.vert[2], tri.vert[1]);
		}

		return reversed;
	}

	// statistics

	public void getVertices(Set<Integer> store) {
		store.clear();
		Iterator<Integer> it = vertexMap.keySet().iterator();
		while (it.hasNext())
			store.add(it.next());
	}

	public Object getData(int vert) {
		VertexAttribute pkV = vertexMap
				.get(new Integer(vert));
		return (pkV != null ? pkV.data : null);
	}

	public ExVector getEdges(int vert) {
		VertexAttribute pkV = vertexMap
				.get(new Integer(vert));
		return (pkV != null ? pkV.edgeSet : null);
	}

	public ExVector getTriangles(int vert) {
		VertexAttribute pkV = vertexMap
				.get(new Integer(vert));
		return (pkV != null ? pkV.triangleSet : null);
	}

	public void getEdges(Set<Edge> store) {
		store.clear();
		Iterator<Edge> it = edgeMap.keySet().iterator();
		while (it.hasNext()) {
			store.add(it.next());
		}
	}

	public Object getData(int vert0, int vert1) {
		EdgeAttribute pkE = edgeMap.get(new Edge(vert0, vert1));
		return (pkE != null ? pkE.data : null);
	}

	public Object getData(Edge edge) {
		return getData(edge.vert[0], edge.vert[1]);
	}

	public void getTriangles(Set<Triangle> store) {
		store.clear();
		Iterator<Triangle> it = triangleMap.keySet().iterator();
		while (it.hasNext()) {
			store.add(it.next());
		}
	}

	public Object getData(int vert0, int vert1, int vert2) {
		TriangleAttribute triAtt = triangleMap
				.get(new Triangle(vert0, vert1, vert2));
		return (triAtt != null ? triAtt.data : null);
	}

	public void setData(int vert0, int vert1, int vert2, Object data) {
		TriangleAttribute triAtt = triangleMap
				.get(new Triangle(vert0, vert1, vert2));
		if (triAtt != null)
			triAtt.data = data;
	}

	public Object getData(Triangle tri) {
		return getData(tri.vert[0], tri.vert[1], tri.vert[2]);
	}

	public void setData(Triangle tri, Object data) {
		setData(tri.vert[0], tri.vert[1], tri.vert[2], data);
	}

	// vertex is <v>
	// edge is <v0,v1> where v0 = min(v0,v1)
	// triangle is <v0,v1,v2> where v0 = min(v0,v1,v2)

	public class Edge implements Comparable {
		int vert[] = new int[2];

		public Edge(int iV0, int iV1) {
			if (iV0 < iV1) {
				// v0 is minimum
				vert[0] = iV0;
				vert[1] = iV1;
			} else {
				// v1 is minimum
				vert[0] = iV1;
				vert[1] = iV0;
			}
		}

		public boolean lessThan(Edge otherEdge) {
			if (vert[1] < otherEdge.vert[1])
				return true;

			if (vert[1] == otherEdge.vert[1])
				return vert[0] < otherEdge.vert[0];

			return false;
		}

		public boolean equals(Object obj) {
			Edge otherEdge = (Edge) obj;
			return (vert[0] == otherEdge.vert[0])
					&& (vert[1] == otherEdge.vert[1]);
		}

		public int compareTo(Object o) {
			Edge otherEdge = (Edge) o;
			if (lessThan(otherEdge))
				return -1;
			else if (equals(otherEdge))
				return 0;
			else
				return 1;
		}
	};

	public class Triangle implements Comparable {
		public int vert[] = new int[3];

		public Triangle(int vert0, int vert1, int vert2) {
			if (vert0 < vert1) {
				if (vert0 < vert2) {
					// vert0 is minimum
					vert[0] = vert0;
					vert[1] = vert1;
					vert[2] = vert2;
				} else {
					// vert2 is minimum
					vert[0] = vert2;
					vert[1] = vert0;
					vert[2] = vert1;
				}
			} else {
				if (vert1 < vert2) {
					// vert1 is minimum
					vert[0] = vert1;
					vert[1] = vert2;
					vert[2] = vert0;
				} else {
					// vert2 is minimum
					vert[0] = vert2;
					vert[1] = vert0;
					vert[2] = vert1;
				}
			}
		}

		public boolean lessThan(Triangle otherTri) {
			if (vert[2] < otherTri.vert[2])
				return true;

			if (vert[2] == otherTri.vert[2]) {
				if (vert[1] < otherTri.vert[1])
					return true;

				if (vert[1] == otherTri.vert[1])
					return vert[0] < otherTri.vert[0];
			}

			return false;
		}

		public boolean equals(Object obj) {
			Triangle otherTri = (Triangle) obj;
			return (vert[0] == otherTri.vert[0])
					&& ((vert[1] == otherTri.vert[1] && vert[2] == otherTri.vert[2]) || (vert[1] == otherTri.vert[2] && vert[2] == otherTri.vert[1]));
		}

		public int compareTo(Object o) {
			Triangle otherTri = (Triangle) o;
			if (lessThan(otherTri))
				return -1;
			else if (equals(otherTri))
				return 0;
			else
				return 1;
		}
	};

	public class VertexAttribute {
		public ExVector edgeSet; //<Edge>

		public ExVector triangleSet; //<Triangle>

		public Object data;

		public VertexAttribute() {
			edgeSet = new ExVector(8, 8);
			triangleSet = new ExVector(8, 8);
			data = null;
		}
	};

	public class EdgeAttribute {
		public ExVector triangleSet; //<Triangle>

		public Object data;

		public EdgeAttribute() {
			triangleSet = new ExVector(2, 2);
			data = null;
		}
	};

	public class TriangleAttribute {
		public Object data;

		public TriangleAttribute() {
			data = null;
		}
	};
}