Skip to content

Instantly share code, notes, and snippets.

@kwalkerxxi

kwalkerxxi/.VoxelCollisionGenerator.cs.md

Forked from andrew-raphael-lukasik/.VoxelCollisionGenerator.cs.md
Created February 6, 2025 12:30
Show Gist options
  • Save kwalkerxxi/3d9b35d463c4052d5cbfda7f11c55dfe to your computer and use it in GitHub Desktop.
Save kwalkerxxi/3d9b35d463c4052d5cbfda7f11c55dfe to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @andrew-raphael-lukasik andrew-raphael-lukasik revised this gist Jan 31, 2024. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions .VoxelCollisionGenerator.cs.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +1,3 @@
    ![GIF 21 01 2024 01-20-34](https://gist.github.com/assets/3066539/0b413327-0f4e-48a5-a459-bd1416e0fadb)

    note: This is toy implementation, output is sub-optimal.
  2. @andrew-raphael-lukasik andrew-raphael-lukasik revised this gist Jan 21, 2024. 2 changed files with 2 additions and 1 deletion.
    2 changes: 1 addition & 1 deletion .VoxelCollisionGenerator.cs.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +1 @@
    readme
    ![GIF 21 01 2024 01-20-34](https://gist.github.com/assets/3066539/0b413327-0f4e-48a5-a459-bd1416e0fadb)
    1 change: 1 addition & 0 deletions VoxelCollisionGenerator.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,4 @@
    // src* https://gist.github.com/andrew-raphael-lukasik/7169fc088d0074762a166bcca84ec129
    #if UNITY_EDITOR

    using Unity.Burst;
  3. @andrew-raphael-lukasik andrew-raphael-lukasik created this gist Jan 21, 2024.
    1 change: 1 addition & 0 deletions .VoxelCollisionGenerator.cs.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1 @@
    readme
    448 changes: 448 additions & 0 deletions VoxelCollisionGenerator.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,448 @@
    #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