Tool to voxelize a Mesh Collider into multiple Box Colliders

.VoxelCollisionGenerator.cs.md

note: This is toy implementation, output is sub-optimal.

VoxelCollisionGenerator.cs

// src* https://gist.github.com/andrew-raphael-lukasik/7169fc088d0074762a166bcca84ec129
#if UNITY_EDITOR

using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;

using UnityEditor;

using UnityEngine;
using UnityEngine.UIElements;

public class VoxelCollisionGenerator : EditorWindow
{
    const string k_key_resolution_x = nameof(VoxelCollisionGenerator)+"."+nameof(_resolution)+".x";
    const string k_key_resolution_y = nameof(VoxelCollisionGenerator)+"."+nameof(_resolution)+".y";
    const string k_key_resolution_z = nameof(VoxelCollisionGenerator)+"."+nameof(_resolution)+".z";
    Vector3Int _resolution;
    const string k_key_boundsscale_x = nameof(VoxelCollisionGenerator)+"."+nameof(_boundsScale)+".x";
    const string k_key_boundsscale_y = nameof(VoxelCollisionGenerator)+"."+nameof(_boundsScale)+".y";
    const string k_key_boundsscale_z = nameof(VoxelCollisionGenerator)+"."+nameof(_boundsScale)+".z";
    Vector3 _boundsScale;

    void OnEnable ()
    {
        ReadResolution( out _resolution );
        ReadBoundsScale( out _boundsScale );
    }

    void OnDisable ()
    {
        EditorPrefs.SetInt( k_key_resolution_x , _resolution.x );
        EditorPrefs.SetInt( k_key_resolution_y , _resolution.y );
        EditorPrefs.SetInt( k_key_resolution_z , _resolution.z );
        EditorPrefs.SetFloat( k_key_boundsscale_x , _boundsScale.x );
        EditorPrefs.SetFloat( k_key_boundsscale_y , _boundsScale.y );
        EditorPrefs.SetFloat( k_key_boundsscale_z , _boundsScale.z );
    }

    void CreateGUI ()
    {
        Vector3IntField RESOLUTION = new ("Resolution");
        {
            RESOLUTION.value = _resolution;
            RESOLUTION.RegisterValueChangedCallback( (evt) => {
                Vector3Int newValue = evt.newValue;

                // limits resolution so it wont crash the editor
                if( newValue.magnitude>1000 )
                {
                    newValue = _resolution;
                    RESOLUTION.SetValueWithoutNotify( newValue );
                    Debug.LogWarning("Resolution limits reached. Limit is in place so number of potential Box Colliders wont crash the editor.");
                }

                _resolution = newValue;
                OnDisable();
            } );
        }

        Vector3Field BOUNDSSCALE = new ("Scale");
        {
            BOUNDSSCALE.value = _boundsScale;
            BOUNDSSCALE.RegisterValueChangedCallback( (etv) => {
                _boundsScale = etv.newValue;
                OnDisable();
            } );
        }

        Button BUTTON = new ( ReplaceWithBoxColliders );
        {
            BUTTON.text = "Replace selected Mesh Colliders with Box Colliders";
            BUTTON.style.flexGrow = 1;
        }

        rootVisualElement.Add( RESOLUTION );
        rootVisualElement.Add( BOUNDSSCALE );
        rootVisualElement.Add( BUTTON );
    }

    static void ReadResolution ( out Vector3Int result )
    {
        result = new Vector3Int{
            x = EditorPrefs.GetInt( k_key_resolution_x , 6 ) ,
            y = EditorPrefs.GetInt( k_key_resolution_y , 6 ) ,
            z = EditorPrefs.GetInt( k_key_resolution_z , 6 ) ,
        };
    }
    static void ReadBoundsScale ( out Vector3 result )
    {
        result = new Vector3{
            x = EditorPrefs.GetFloat( k_key_boundsscale_x , 1.001f ) ,
            y = EditorPrefs.GetFloat( k_key_boundsscale_y , 1.001f ) ,
            z = EditorPrefs.GetFloat( k_key_boundsscale_z , 1.001f ) ,
        };
    }

    void ReplaceWithBoxColliders ()
    {
        foreach( GameObject next in Selection.gameObjects )
        foreach( MeshCollider mc in next.GetComponentsInChildren<MeshCollider>() )
        {
            ReplaceWithBoxColliders( mc , _resolution , _boundsScale );
        }
    }

    static void ReplaceWithBoxColliders
    (
        MeshCollider meshCollider ,
        Vector3Int resolution ,
        Vector3 boundsScale
    )
    {
        if( meshCollider==null )
        {
            Debug.LogError("Target is null");
            return;
        }
        
        Mesh mesh = meshCollider.sharedMesh;
        if( mesh==null )
        {
            Debug.LogError("meshCollider.sharedMesh is null");
            return;
        }

        int rx = resolution.x;
        int ry = resolution.y;
        int rz = resolution.z;
        Bounds totalBounds = mesh.bounds;
        totalBounds.size = Vector3.Scale( totalBounds.size , boundsScale );
        float3 cellSize = (float3)totalBounds.size / new float3(rx,ry,rz);
        float3 totalMin = totalBounds.min;
        float3 cellSizeHalf = cellSize * 0.5f;
        int numCells = rx * ry * rz;
        NativeArray<float3> aabbCenters = new ( numCells , Allocator.TempJob );
        NativeArray<byte> hits = new ( numCells , Allocator.TempJob );
        NativeArray<int> indices = new ( mesh.triangles , Allocator.TempJob );
        NativeArray<float3> vertices = new NativeArray<Vector3>( mesh.vertices , Allocator.TempJob ).Reinterpret<float3>();
        {
            int i = 0;
            for( int x=0 ; x<rx ; x++ )
            for( int y=0 ; y<ry ; y++ )
            for( int z=0 ; z<rz ; z++ )
            {
                aabbCenters[i++] = totalMin + cellSizeHalf + new float3(x,y,z) * cellSize;
            }
        }
        NativeList<AABB> bounds = new ( initialCapacity:numCells , Allocator.TempJob );
        int indicesPerJobCount = math.max( numCells/(SystemInfo.processorCount*3) , 16 );
        //Debug.Log($"numCells:{numCells}, indicesPerJobCount:{indicesPerJobCount}");
        
        JobHandle dependency = new AabbMeshIntersectionTestJob{
            CellExtents = cellSizeHalf ,
            Indices = indices ,
            Vertices = vertices ,
            AabbCenters = aabbCenters ,
            Hits = hits ,
        }
        .Schedule( numCells , indicesPerJobCount );
        indices.Dispose( dependency );
        vertices.Dispose( dependency );
        
        dependency = new CreateBoundsJob{
            CellExtents = cellSizeHalf ,
            AabbCenters = aabbCenters ,
            Hits = hits ,
            Bounds = bounds.AsParallelWriter() ,
        }.Schedule( arrayLength:numCells , innerloopBatchCount:indicesPerJobCount , dependency );
        aabbCenters.Dispose( dependency );
        hits.Dispose( dependency );

        dependency = new OptimizeAabbJob{
            Resolution = resolution ,
            Bounds = bounds ,
        }.Schedule( dependency );

        var stopwatch = System.Diagnostics.Stopwatch.StartNew();
        dependency.Complete();
        Debug.Log($"jobs took {stopwatch.ElapsedMilliseconds} ms");
        //Debug.Log($"numCells:{numCells}, bounds.len:{bounds.Length}");

        stopwatch.Restart();
        #if ENABLE_MONO
        foreach( AABB aabb in bounds.AsArray().ToArray() )
        #else
        foreach( AABB aabb in bounds.AsArray() )
        #endif
        {
            var boxCollider = Undo.AddComponent<BoxCollider>( meshCollider.gameObject );
            boxCollider.center = aabb.Center;
            boxCollider.size = aabb.Size;
        }
        bounds.Dispose();
        Debug.Log($"AddComponent took {stopwatch.ElapsedMilliseconds} ms");

        Undo.RegisterCompleteObjectUndo( meshCollider.gameObject , k_window_label );
        DestroyImmediate( meshCollider );
    }

    [BurstCompile]
    partial struct AabbMeshIntersectionTestJob : IJobParallelForBatch
    {
        public float3 CellExtents;
        [ReadOnly] public NativeArray<int> Indices;
        [ReadOnly] public NativeArray<float3> Vertices;
        [ReadOnly] public NativeArray<float3> AabbCenters;
        [WriteOnly] public NativeArray<byte> Hits;
        void IJobParallelForBatch.Execute ( int startIndex , int count )
        {
            NativeArray<float3> tempBufferAllocation = new ( 3+3+8 , Allocator.Temp , NativeArrayOptions.UninitializedMemory );
            int numTriangles = Indices.Length / 3;
            int endIndex = startIndex + count;
            for( int index=startIndex ; index<endIndex ; index++ )
            {
                bool hit = false;
                AABB b = new AABB{
                    Center = AabbCenters[index] ,
                    Extents = CellExtents ,
                };
                for( int t=0 ; t<numTriangles ; t++ )
                {
                    int t0 = t * 3;
                    int i0 = Indices[t0+0];
                    int i1 = Indices[t0+1];
                    int i2 = Indices[t0+2];
                    float3x3 triangle = new float3x3( Vertices[i0] , Vertices[i1] , Vertices[i2] );
                    if( IsIntersecting(b,triangle,tempBufferAllocation) )
                    {
                        hit = true;
                        break;
                    }
                }
                Hits[index] = (byte)( hit ? 1 : 0 );
            }
        }
    }

    [BurstCompile]
    partial struct CreateBoundsJob : IJobParallelFor
    {
        public float3 CellExtents;
        [ReadOnly] public NativeArray<float3> AabbCenters;
        [ReadOnly] public NativeArray<byte> Hits;
        [WriteOnly] public NativeList<AABB>.ParallelWriter Bounds;
        void IJobParallelFor.Execute ( int index )
        {
            if( Hits[index]==1 )
            {
                var aabb = new AABB{
                    Center = AabbCenters[index] ,
                    Extents = CellExtents ,
                };
                Bounds.AddNoResize( aabb );
            }
        }
    }


    [BurstCompile]
    partial struct OptimizeAabbJob : IJob
    {
        public Vector3Int Resolution;
        public NativeList<AABB> Bounds;
        void IJob.Execute ()
        {
            if( Bounds.Length<2 ) return;
            
            pass_start:
            bool repeat = false;
            for( int ia=0 ; ia<Bounds.Length ; ia++ )
            {
                AABB a = Bounds[ia];
                for( int ib=0 ; ib<Bounds.Length ; ib++ )
                {
                    AABB b = Bounds[ib];
                    AABB c = Combine( a , b );
                    float av = a.Size.x * a.Size.y * a.Size.z;
                    float bv = b.Size.x * b.Size.y * b.Size.z;
                    float cv = c.Size.x * c.Size.y * c.Size.z;
                    if( AreApproxEqual(cv,(av+bv)) )
                    if( ia!=ib )// not comparing with itself
                    {
                        Bounds.RemoveAt( ib );

                        if( ia>ib )
                        {
                            ia--;
                        }
                        Bounds[ia] = c;

                        ia++;
                        if( ia==Bounds.Length )
                        {
                            ia = 0;
                        }
                        a = Bounds[ia];

                        ib = 0;

                        repeat = true;
                    }
                }
            }
            if( repeat ) goto pass_start;
        }
        bool AreApproxEqual ( float a , float b , float tolerance=0.01f )
        {
            float max = math.max( math.abs(a) , math.abs(b) );
            if( max!=0 )// check to prevent division by zero
            {
                float diff = math.abs(a-b);
                return (diff/max) <= tolerance;
            }
            else return true;// both are 0
        }
        AABB Combine ( AABB a , AABB b )
        {
            Encapsulate( ref a , b.Center - b.Extents );
            Encapsulate( ref a , b.Center + b.Extents );
            return a;
        }
        void Encapsulate ( ref AABB aabb , float3 point ) => SetMinMax( ref aabb , math.min(aabb.Min,point) , math.max(aabb.Max,point) );
        void SetMinMax ( ref AABB aabb , float3 min , float3 max )
        {
            aabb.Extents = (max - min) * 0.5f;
            aabb.Center = min + aabb.Extents;
        }

        // signed distance between bounds
        float SignedDistance ( AABB a , AABB b )
        {
            var amin = a.Min; var amax = a.Max;
            var bmin = b.Min; var bmax = b.Max;
            return math.min(
                sd( amin.x , amax.x , bmin.x , bmax.x ) ,
                sd( amin.y , amax.y , bmin.y , bmax.y )
            );
        }

        // signed distance between segments
        float sd ( float a0 , float a1 , float b0 , float b1 )
        {
            float lengthA = a1 - a0;
            float lengthB = b1 - b0;
            float lengthAB = math.max(a1,b1) - math.min(a0,b0);
            float lengthOverlap = lengthA + lengthB - lengthAB;
            float sign = math.sign(a0-b0);
            return sign * math.min(math.abs(a0-b0), lengthOverlap);
        }

    }

    // based on https://stackoverflow.com/a/17503268/2528943
    static bool IsIntersecting ( AABB bounds , float3x3 triangle , NativeSlice<float3> tempBuffer )
    {
        float triangleMin, triangleMax, boxMin, boxMax;
        
        // Test the box normals (x-, y- and z-axes)
        NativeSlice<float3> boxNormals = tempBuffer.Slice( 0 , 3 );
        {
            boxNormals[0] = new float3(1,0,0);
            boxNormals[1] = new float3(0,1,0);
            boxNormals[2] = new float3(0,0,1);
        }
        for( int i=0 ; i<3 ; i++ )
        {
            Project( triangle , boxNormals[i] , out triangleMin , out triangleMax );
            if( triangleMax<bounds.Min[i] || triangleMin>bounds.Max[i] )
                return false;// No intersection possible.
        }

        NativeSlice<float3> boundsVertices = tempBuffer.Slice( 3+3 , 8 );
        {
            float3 min = bounds.Min;
            float3 size = bounds.Size;
            boundsVertices[0] = min;
            boundsVertices[1] = min + new float3( size.x , 0 , 0 );
            boundsVertices[2] = min + new float3( 0 , 0 , size.z );
            boundsVertices[3] = min + new float3( size.x , 0 , size.z );
            boundsVertices[4] = min + new float3( 0 , size.y , 0 );
            boundsVertices[5] = min + new float3( size.x , size.y , 0 );
            boundsVertices[6] = min + new float3( 0 , size.y , size.z );
            boundsVertices[7] = min + size;
        }
        float3 triangleNormal = math.cross( triangle.c1-triangle.c0 , triangle.c2-triangle.c0 );

        // Test the triangle normal
        float triangleOffset = math.dot( triangleNormal , triangle[0] );
        Project( boundsVertices , triangleNormal , out boxMin , out boxMax );
        if( boxMax<triangleOffset || boxMin>triangleOffset )
            return false;// No intersection possible.

        // Test the nine edge cross-products
        NativeSlice<float3> triangleEdges = tempBuffer.Slice( 3 , 3 );
        {
            triangleEdges[0] = triangle.c0 - triangle.c1;
            triangleEdges[1] = triangle.c1 - triangle.c2;
            triangleEdges[2] = triangle.c2 - triangle.c0;
        }
        for( int i=0 ; i<3 ; i++ )
        for( int j=0 ; j<3 ; j++ )
        {
            // The box normals are the same as it's edge tangents
            float3 axis = math.cross( triangleEdges[i] , boxNormals[j] );
            Project( boundsVertices , axis , out boxMin , out boxMax );
            Project( triangle , axis , out triangleMin , out triangleMax );
            if( boxMax<triangleMin || boxMin>triangleMax )
                return false;// no intersection possible
        }

        // no separating axis found.
        return true;
    }

    // based on https://stackoverflow.com/a/17503268/2528943
    static void Project ( NativeSlice<float3> points , float3 axis , out float min , out float max )
    {
        min = float.PositiveInfinity;
        max = float.NegativeInfinity;
        foreach( float3 p in points )
        {
            float val = math.dot( axis , p );
            if( val<min ) min = val;
            if( val>max ) max = val;
        }
    }
    static void Project ( float3x3 triangle , float3 axis , out float min , out float max )
    {
        float a = math.dot( axis , triangle.c0 );
        float b = math.dot( axis , triangle.c1 );
        float c = math.dot( axis , triangle.c2 );
        min = math.cmin( new float4(a,b,c,float.PositiveInfinity) );
        max = math.cmax( new float4(a,b,c,float.NegativeInfinity) );
    }

    const string k_window_label = "Voxel Collision Generator";
    [MenuItem( "Window/"+k_window_label )]
    static void ShowWindow ()
    {
        var window = EditorWindow.GetWindow<VoxelCollisionGenerator>();
        window.titleContent = new GUIContent( k_window_label );
        window.Show();
    }

}

#endif