Newer
Older
using UnityEngine;
public class MeshTreeNode
{
public MeshTreeNode left;
public MeshTreeNode right;
public List<Vector3> vertices;
public List<Vector3> normals;
public List<Vector2> uv;
this.vertices = new List<Vector3>(mesh.vertices);
this.normals = new List<Vector3>(mesh.normals);
this.uv = new List<Vector2>(mesh.uv);
}
public Mesh GetMesh()
{
Debug.Log($"Building mesh containing {this.vertices.Count} vertices...");
indexFormat = UnityEngine.Rendering.IndexFormat.UInt32,
vertices = this.vertices.ToArray(),
normals = this.normals.ToArray(),
uv = this.uv.ToArray()
};
return mesh;
}
public int SplitEdge(int index1, int index2, Vector3 p, Vector3 n)
{
Vector3 v1 = this.vertices[index1];
Vector3 v2 = this.vertices[index2];
Vector3 origin = v1;
Vector3 direction = v2 - v1;
// Calculate intersection
float t = Vector3.Dot(p - origin, n) / Vector3.Dot(direction, n);
// Interpolate vertex, normal and uv
Vector3 vertex = origin + direction * t;
Vector3 normal = t * this.normals[index1] + (1 - t) * this.normals[index2];
Vector2 uv = t * this.uv[index1] + (1 - t) * this.uv[index2];
this.vertices.Add(vertex);
public int PushVertex(Vector3 position, Vector3 normal, Vector2 uv)
{
this.vertices.Add(position);
this.normals.Add(normal);
this.uv.Add(uv);
return this.vertices.Count - 1;
}
public Vector3 GetCenter(IEnumerable<int> triangles)
{
// Get unique indices
HashSet<int> indices = new HashSet<int>(triangles);
// Accumalate all vertex positions of mesh
Vector3 accumalator = new Vector3();
foreach (int idx in indices)
{
accumalator += this.vertices[idx];
}
// Return average of positions (i.e. center)
return accumalator * (1.0f / indices.Count);
public class Splitter : MonoBehaviour
{
Mesh mesh = this.GetComponent<MeshFilter>().mesh;
this.mesh = new MeshBuilder(mesh);
Random.InitState(this.seed);
this.GetComponent<MeshFilter>().mesh = this.mesh.GetMesh();
this.GetComponent<MeshFilter>().mesh.triangles = this.root.triangles;
this.root = new MeshTreeNode
{
triangles = this.GetComponent<MeshFilter>().mesh.triangles
};
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
// Compare fragment bounding boxes to create a connectivity graph
void BuildConnectivityGraph() {
this.graph = new List<GraphEdge>();
// Collect all fragments in a list
List<MeshTreeNode> leaves = new List<MeshTreeNode>();
GetLeaves(this.root, ref leaves);
// Iterate over all leaves/fragments, building a connectivity graph
for (int i = 0; i < leaves.Count; i++) {
Mesh A = new Mesh { triangles = leaves[i].triangles };
for (int j = i + 1; j < leaves.Count; j++) {
Mesh B = new Mesh { triangles = leaves[j].triangles };
// Check if the two AABBs intersect
if (A.bounds.Intersects(B.bounds))
this.graph.Add(new GraphEdge { A = leaves[i], B = leaves[j] });
}
}
}
// Gather all leaves from a given MeshTree recursively
void GetLeaves(MeshTreeNode node, ref List<MeshTreeNode> leaves) {
if (node.left != null)
GetLeaves(node.left, ref leaves);
if (node.right != null)
GetLeaves(node.right, ref leaves);
if (node.left == null && node.right == null)
leaves.Add(node);
}
private void Update()
{
time += Time.deltaTime;
if (time > 0.3 && (Input.GetKey(KeyCode.N) || Input.GetKey(KeyCode.M)))
if (Input.GetKey(KeyCode.N))
current = current.left;
else
current = current.right;
if (current == null)
{
current = root;
}
this.GetComponent<MeshFilter>().mesh.triangles = current.triangles;
}
}
void SplitNode(MeshTreeNode node, int depth = 6)
// We split the vertices in the node based on which
// side of the plane they are. This plane has a random
// normal and goes through the center of the mesh.
Vector3 n = Random.onUnitSphere; // normal of plane
Vector3 p = this.mesh.GetCenter(node.triangles); // point on plane
float d = -n.x * p.x - n.y * p.y - n.z * p.z;
// Indices for left and right triangles
List<int> left = new List<int>();
List<int> right = new List<int>();
List<int> splits = new List<int>();
for (int i = 0; i < node.triangles.Length; i += 3)
int i1 = node.triangles[i + 0];
int i2 = node.triangles[i + 1];
int i3 = node.triangles[i + 2];
Vector3 v1 = this.mesh.vertices[i1];
Vector3 v2 = this.mesh.vertices[i2];
Vector3 v3 = this.mesh.vertices[i3];
// Test for each vertex whether they lie on the same side of the plane
bool s1 = v1.x * n.x + v1.y * n.y + v1.z * n.z + d > 0;
bool s2 = v2.x * n.x + v2.y * n.y + v2.z * n.z + d > 0;
bool s3 = v3.x * n.x + v3.y * n.y + v3.z * n.z + d > 0;
left.AddRange(new[] { i1, i2, i3 });
}
else if (!s1 && !s2 && !s3)
{
right.AddRange(new[] { i1, i2, i3 });
}
else
{
// The difficult cases where one vertex is on one side, and the other
// two vertices are on the other side of the plane.
int s = -1, p1 = -1, p2 = -1;
bool l = false;
if (s1 && !s2 && !s3) { s = i1; p1 = i2; p2 = i3; l = true; }
if (!s1 && s2 && !s3) { s = i2; p1 = i3; p2 = i1; l = true; }
if (!s1 && !s2 && s3) { s = i3; p1 = i1; p2 = i2; l = true; }
if (!s1 && s2 && s3) { s = i1; p1 = i2; p2 = i3; l = false; }
if (s1 && !s2 && s3) { s = i2; p1 = i3; p2 = i1; l = false; }
if (s1 && s2 && !s3) { s = i3; p1 = i1; p2 = i2; l = false; }
int x1 = mesh.SplitEdge(p1, s, p, n);
int x2 = mesh.SplitEdge(p2, s, p, n);
{
left.AddRange(new[] { x1, x2, s });
right.AddRange(new[] { x1, p1, p2, p2, x2, x1 });
}
else
{
left.AddRange(new[] { x1, p1, p2, p2, x2, x1 });
right.AddRange(new[] { x1, x2, s });
splits.Add(this.mesh.PushVertex(this.mesh.vertices[x1], n, this.mesh.uv[x1]));
splits.Add(this.mesh.PushVertex(this.mesh.vertices[x2], n, this.mesh.uv[x2]));
// New vertex at center of splitting plane
int a = this.mesh.PushVertex(p, n, Vector2.zero);
// Triangulate the new vertices from center of splitting plane (only works for convex shapes)
for (int i = 0; i < splits.Count; i += 2)
{
int b = splits[i];
int c = splits[i + 1];
left.AddRange(new[] { a, b, c, c, b, a });
right.AddRange(new[] { a, b, c, c, b, a });
}
// Create children
node.left = new MeshTreeNode()
{
triangles = left.ToArray()
};
node.right = new MeshTreeNode()
{
triangles = right.ToArray()
};
SplitNode(node.left, depth - 1);
SplitNode(node.right, depth - 1);