Splitter.cs

using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public class MeshTreeNode
{
    public MeshTreeNode left;
    public MeshTreeNode right;
    public int[] triangles;
}

public class MeshBuilder
{
    public List<Vector3> vertices;
    public List<Vector3> normals;
    public List<Vector2> uv;

    public MeshBuilder(Mesh mesh)
    {
        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...");

        Mesh mesh = new Mesh
        {
            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];

        // Setup a ray along the edge
        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);
        this.normals.Add(normal.normalized);
        this.uv.Add(uv);

        return this.vertices.Count - 1;
    }

    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
{
    private MeshBuilder mesh;
    private MeshTreeNode root;
    private List<GraphEdge> graph;

    float time = 0;
    MeshTreeNode current;

    public int seed;

    void Start()
    {
        Mesh mesh = this.GetComponent<MeshFilter>().mesh;
        this.mesh = new MeshBuilder(mesh);

        Random.InitState(this.seed);

        this.BuildMeshTree();
        this.BuildConnectivityGraph();

        this.GetComponent<MeshFilter>().mesh = this.mesh.GetMesh();
        this.GetComponent<MeshFilter>().mesh.triangles = this.root.triangles;

        current = root;
    }

    void BuildMeshTree()
    {
        this.root = new MeshTreeNode
        {
            triangles = this.GetComponent<MeshFilter>().mesh.triangles
        };

        this.SplitNode(this.root);
    }

    // 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)))
        {
            time = 0;

            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)
    {
        if (depth <= 0)
        {
            return;
        }

        // 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)
        {
            // Get indices to triangle vertices
            int i1 = node.triangles[i + 0];
            int i2 = node.triangles[i + 1];
            int i3 = node.triangles[i + 2];

            // Get vertices themselves
            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;

            if (s1 && s2 && s3)
            {
                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);

                if (l)
                {
                    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()
        };

        // Split children
        SplitNode(node.left, depth - 1);
        SplitNode(node.right, depth - 1);
    }
}