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();
        mesh.vertices = this.vertices.ToArray();
        mesh.normals = this.normals.ToArray();
        mesh.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 = origin - this.vertices[index2];

        // Calculate intersection
        float t = Vector3.Dot(p - origin, n) / Vector3.Dot(direction, n);

        // Interpolate vertex, normal and uv
        Vector3 vertex = t * this.vertices[index1] + (1 - t) * this.vertices[index2];
        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);
        this.uv.Add(uv);

        return this.vertices.Count;
    }

    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;

    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.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 < 10)
        {
            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;

        // For containing the triangles of the left and right children.
        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 case where one vertex is on one side, and the other
                // two vertices are on the other side of the plane.
            }
        }

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

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

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