Splitter.cs

using System.Collections.Generic;
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()
    {
        Mesh mesh = new Mesh
        {
            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)
    {
        // Setup a ray along the edge
        Vector3 origin = this.vertices[index1];
        Vector3 direction = this.vertices[index2] - origin;

        // 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 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;

    float total = 0.3f;
    bool swtch;

    public int seed;

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

        this.BuildMeshTree();

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

        Random.InitState(this.seed);
    }

    private void Update()
    {
        this.total += Time.deltaTime;

        if (this.total > 0.4)
        {
            this.total = 0;
            this.swtch = !this.swtch;

            if (this.swtch)
            {
                this.GetComponent<MeshFilter>().mesh.triangles = this.root.right.triangles;
            }
            else
            {
                this.GetComponent<MeshFilter>().mesh.triangles = this.root.left.triangles;
            }
        }
    }

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

        this.SplitNode(this.root);
    }

    void SplitNode(MeshTreeNode node)
    {
        // Too small for splitting (TODO: make configurable?)
        if (node.triangles.Length < 100)
        {
            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>();

        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 });
                }
            }
        }

        // Create children
        node.left = new MeshTreeNode()
        {
            triangles = left.ToArray()
        };

        node.right = new MeshTreeNode()
        {
            triangles = right.ToArray()
        };

        // Split children
        //SplitNode(node.left);
        //SplitNode(node.right);
    }
}