Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Mesh voxelization

Discussion in 'Scripting' started by slowpuke666, Jan 23, 2020.

  1. slowpuke666

    slowpuke666

    Joined:
    May 4, 2018
    Posts:
    7
    Hello guys.
    I found a Mesh voxelization script, but after voxelization there are no voxels inside object. How is possible to add voxels inside?

    Code (CSharp):
    1. using UnityEngine;
    2. using System.Collections;
    3. using System.Collections.Generic;
    4.  
    5. #if UNITY_EDITOR
    6. using UnityEditor;
    7. #endif
    8.  
    9. using BoundHierarchy = TriAABBOverlap.BoundHierarchy;
    10. using Triangle = TriAABBOverlap.Triangle;
    11.  
    12. public class Voxeliser
    13. {
    14.     private bool[][][] _voxelMap;
    15.     private int _xDensity = 8;
    16.     private int _yDensity = 8;
    17.     private int _zDensity = 8;
    18.     private Bounds _bounds;
    19.  
    20.     public bool[][][] VoxelMap
    21.     {
    22.         get { return _voxelMap; }
    23.     }
    24.  
    25.     public Voxeliser (Bounds bounds, int xDensity, int yDensity, int zDensity)
    26.     {
    27.         _bounds = bounds;
    28.         _xDensity = xDensity;
    29.         _yDensity = yDensity;
    30.         _zDensity = zDensity;
    31.     }
    32.  
    33.     public void Voxelize (Transform root)
    34.     {
    35.         var meshFilters = root.GetComponentsInChildren<MeshFilter>();
    36.      
    37.         var objectBounds = new List<BoundHierarchy>();
    38.         foreach (var filter in meshFilters)
    39.         {
    40.             var mesh = filter.sharedMesh;
    41.             var vertices = mesh.vertices;
    42.             var tris = mesh.triangles;
    43.             var triangleBounds = new List<BoundHierarchy>();
    44.             for(int i = 0; i < tris.Length; i += 3)
    45.             {
    46.                 var vert1 = vertices[tris[i + 0]];
    47.                 var vert2 = vertices[tris[i + 1]];
    48.                 var vert3 = vertices[tris[i + 2]];
    49.                 vert1 = filter.transform.TransformPoint(vert1);
    50.                 vert2 = filter.transform.TransformPoint(vert2);
    51.                 vert3 = filter.transform.TransformPoint(vert3);
    52.              
    53.                 var u = vert2 - vert3;
    54.                 var v = vert3 - vert1;
    55.                 var triNormal = Vector3.Cross(u, v);
    56.                 triNormal = triNormal.normalized;
    57.              
    58.                 var triBounds = new Bounds(vert1, Vector3.zero);
    59.                 triBounds.Encapsulate(vert2);
    60.                 triBounds.Encapsulate(vert3);
    61.              
    62.                 var tri = new Triangle {
    63.                     vertA = vert1,
    64.                     vertB = vert2,
    65.                     vertC = vert3,
    66.                     normal = triNormal,
    67.                     bound = triBounds,
    68.                 };
    69.              
    70.                 triangleBounds.Add(new BoundHierarchy() {
    71.                     bound = triBounds,
    72.                     subBounds = null,
    73.                     triList = tri
    74.                 });
    75.             }
    76.          
    77.             objectBounds.Add(new BoundHierarchy() {
    78.                 bound = filter.GetComponent<Renderer>().bounds,
    79.                 subBounds = triangleBounds.ToArray()
    80.             });
    81.         }
    82.      
    83.         var rootNode = new BoundHierarchy() {
    84.             bound = _bounds,
    85.             subBounds = objectBounds.ToArray()
    86.         };
    87.      
    88.         GenerateBlockArray ();
    89.         GenerateVoxelData (rootNode);
    90.     }
    91.  
    92.     private void GenerateVoxelData(BoundHierarchy rootNode)
    93.     {
    94.         var gridCubeSize = new Vector3(
    95.             _bounds.size.x / _xDensity,
    96.             _bounds.size.y / _yDensity,
    97.             _bounds.size.z / _zDensity);
    98.         var worldCentre = _bounds.min + gridCubeSize / 2;
    99.         var objectLevelBounds = rootNode.subBounds;
    100.         var cachedGridBounds = new Bounds(Vector3.zero, gridCubeSize);
    101.         var cachedVec = Vector3.zero;
    102.      
    103.         #if UNITY_EDITOR
    104.         EditorUtility.ClearProgressBar();
    105.         var pointsProcessed = 0;
    106.         var totalPoints = (float)(_xDensity * _yDensity * _zDensity);
    107.         #endif
    108.      
    109.         for(int x = 0; x < _xDensity; x++)
    110.         {
    111.             for(int y = 0; y < _yDensity; y++)
    112.             {
    113.                 for(int z = 0; z < _zDensity; z++)
    114.                 {
    115.                     #if UNITY_EDITOR
    116.                     pointsProcessed++;
    117.                     if (Application.isEditor && !Application.isPlaying)
    118.                     {
    119.                         if (pointsProcessed % 2000 == 0)
    120.                         {
    121.                             if(EditorUtility.DisplayCancelableProgressBar("Voxelising", "Voxelising", (float)pointsProcessed / totalPoints))
    122.                             {
    123.                                 EditorUtility.ClearProgressBar();
    124.                                 return;
    125.                             }
    126.                         }
    127.                     }
    128.                     #endif
    129.                  
    130.                     var didFind = false;
    131.                     for(int objectCnt = 0; objectCnt < objectLevelBounds.Length; objectCnt++)
    132.                     {
    133.                         cachedVec.x = x * gridCubeSize.x + worldCentre.x;
    134.                         cachedVec.y = y * gridCubeSize.y + worldCentre.y;
    135.                         cachedVec.z = z * gridCubeSize.z + worldCentre.z;
    136.                         cachedGridBounds.center = cachedVec;
    137.                      
    138.                         if(cachedGridBounds.Intersects(objectLevelBounds[objectCnt].bound))
    139.                         {
    140.                             var triBounds = objectLevelBounds[objectCnt].subBounds;
    141.                             for(int triCnt = 0; triCnt < triBounds.Length; triCnt++)
    142.                             {
    143.                                 var triangle = triBounds[triCnt].triList;
    144.                                 if(TriAABBOverlap.Check(cachedGridBounds, triangle))
    145.                                 {
    146.                                  
    147.                                     _voxelMap[x][y][z] = true;
    148.                                     didFind = true;
    149.                                     break;
    150.                                 }
    151.                             }
    152.                             if(didFind)
    153.                             {
    154.                                 break;
    155.                             }
    156.                         }
    157.                         if(didFind)
    158.                         {
    159.                             break;
    160.                         }
    161.                     }
    162.                 }
    163.             }
    164.         }
    165.      
    166.         #if UNITY_EDITOR
    167.         EditorUtility.ClearProgressBar();
    168.         #endif
    169.     }
    170.  
    171.     /// <summary>
    172.     /// Faster indexing than a [,,] array
    173.     /// </summary>
    174.     private void GenerateBlockArray ()
    175.     {
    176.         _voxelMap = new bool[_xDensity][][];
    177.         for (var x = 0; x < _xDensity; x++)
    178.         {
    179.             _voxelMap[x] = new bool[_yDensity][];
    180.             for (var y = 0; y < _yDensity; y++)
    181.             {
    182.                 _voxelMap[x][y] = new bool[_zDensity];
    183.             }
    184.         }
    185.     }
    186. }
    187.  
    Code (CSharp):
    1. using UnityEngine;
    2. #if UNITY_EDITOR
    3. using UnityEditor;
    4. #endif
    5. using System.Collections;
    6. using System.Collections.Generic;
    7. using System;
    8.  
    9.  
    10. public class VoxeliseScene : MonoBehaviour
    11. {
    12.     [Header("Click the settings icon for more options")]
    13.     [Header("Version 1.0 Brian Su")]
    14.     [SerializeField]
    15.     public GameObject _voxelModel;
    16.     [SerializeField]
    17.     [Header("Keep this value low 8 = 8^3 = 512, 16^3 = 4096 voxels")]
    18.     private int _xDensity = 8;
    19.     [SerializeField]
    20.     private int _yDensity = 8;
    21.     [SerializeField]
    22.     private int _zDensity = 8;
    23.     [Header("Area where to voxelise")]
    24.     [SerializeField]
    25.     private Bounds _bounds = new Bounds(Vector3.zero, Vector3.one);
    26.     [Header("Meshrenderers under this will be processed.")]
    27.     [SerializeField]
    28.     public Transform root;
    29.  
    30.     private Voxeliser _voxeliser;
    31.  
    32.     [ContextMenu("Run and create voxels")]
    33.  
    34.  
    35.     private void Start()
    36.     {
    37.         RunAndCreate();
    38.     }
    39.  
    40.     private void RunAndCreate ()
    41.     {
    42.         Run();
    43.  
    44.         var gridCubeSize = new Vector3(
    45.             _bounds.size.x / _xDensity,
    46.             _bounds.size.y / _yDensity,
    47.             _bounds.size.z / _zDensity);
    48.         var worldCentre = _bounds.min + gridCubeSize / 2;
    49.         var voxelRoot = new GameObject("Voxel Root");
    50.         var rootTransform = voxelRoot.transform;
    51.  
    52.         for(int x = 0; x < _xDensity; x++)
    53.         {
    54.             for(int y = 0; y < _yDensity; y++)
    55.             {
    56.                 for(int z = 0; z < _zDensity; z++)
    57.                 {
    58.                     if (_voxeliser.VoxelMap[x][y][z])
    59.                     {
    60.                         var go = Instantiate(_voxelModel, new Vector3(
    61.                             x * gridCubeSize.x,
    62.                             y * gridCubeSize.y,
    63.                             z * gridCubeSize.z) + worldCentre, Quaternion.identity) as GameObject;
    64.                         go.transform.localScale = gridCubeSize;
    65.                         go.gameObject.tag = "Enemy";
    66.                         go.transform.SetParent(rootTransform, true);
    67.                     }
    68.                 }
    69.             }
    70.         }
    71.     }
    72.  
    73.  
    74.     [ContextMenu("Debug run")]
    75.     private void Run()
    76.     {
    77.         _voxeliser = new Voxeliser(_bounds, _xDensity, _yDensity, _zDensity);
    78.         _voxeliser.Voxelize(root);
    79.     }
    80.  
    81.     private void OnDrawGizmosSelected()
    82.     {
    83.         Gizmos.DrawWireCube(transform.position + _bounds.center, _bounds.size);
    84.         if (_voxeliser != null)
    85.         {
    86.             var gridCubeSize = new Vector3(
    87.                 _bounds.size.x / _xDensity,
    88.                 _bounds.size.y / _yDensity,
    89.                 _bounds.size.z / _zDensity);
    90.             var worldCentre = _bounds.min + gridCubeSize / 2;
    91.  
    92.             var voxelMap = _voxeliser.VoxelMap;
    93.  
    94.             if (
    95.                 _xDensity != voxelMap.Length ||
    96.                 _yDensity != voxelMap[0].Length ||
    97.                 _zDensity != voxelMap[0][0].Length)
    98.             {
    99.                 voxelMap = null;
    100.                 return;
    101.             }
    102.          
    103.             for(int x = 0; x < _xDensity; x++)
    104.             {
    105.                 for(int y = 0; y < _yDensity; y++)
    106.                 {
    107.                     for(int z = 0; z < _zDensity; z++)
    108.                     {
    109.                         if (voxelMap[x][y][z])
    110.                         {
    111.                             Gizmos.DrawWireCube(new Vector3(
    112.                                 x * gridCubeSize.x,
    113.                                 y * gridCubeSize.y,
    114.                                 z * gridCubeSize.z) + worldCentre, gridCubeSize);
    115.                         }
    116.                     }
    117.                 }
    118.             }
    119.         }
    120.     }
    121. }
    122.            
    Code (CSharp):
    1. using UnityEngine;
    2. using System.Collections;
    3.  
    4. public static class TriAABBOverlap
    5. {
    6.     public struct Triangle
    7.     {
    8.         public Vector3 vertA;
    9.         public Vector3 vertB;
    10.         public Vector3 vertC;
    11.         public Vector3 normal;
    12.         public Bounds bound;
    13.         public bool didHit;
    14.     }
    15.    
    16.     public struct BoundHierarchy
    17.     {
    18.         public Bounds bound;
    19.         public BoundHierarchy[] subBounds;
    20.         public Triangle triList;
    21.     }
    22.  
    23.     // cache everything
    24.     private static Vector3 vmin = Vector3.zero;
    25.     private static Vector3 vmax = Vector3.zero;
    26.     private static Vector3 vertA = Vector3.zero;
    27.     private static Vector3 vertB = Vector3.zero;
    28.     private static Vector3 vertC = Vector3.zero;
    29.     private static Vector3 edgeA = Vector3.zero;
    30.     private static Vector3 edgeB = Vector3.zero;
    31.     private static Vector3 edgeC = Vector3.zero;
    32.    
    33.     private static bool PlaneBoxOverlap(Vector3 normal, Vector3 vert, Vector3 maxbox)
    34.     {
    35.         vmin.x = vmin.y = vmin.z = 0;
    36.         vmax.x = vmax.y = vmax.z = 0;
    37.  
    38.         // unroll loop
    39.         var vX = vert.x;
    40.         var vY = vert.y;
    41.         var vZ = vert.z;
    42.         var maxX = maxbox.x;
    43.         var maxY = maxbox.y;
    44.         var maxZ = maxbox.z;
    45.  
    46.         if(normal.x > 0.0f)
    47.         {
    48.             vmin.x = -maxX - vX;
    49.             vmax.x =  maxX - vX;
    50.         }
    51.         else
    52.         {
    53.             vmin.x =  maxX - vX;
    54.             vmax.x = -maxX - vX;
    55.         }
    56.    
    57.         if(normal.y > 0.0f)
    58.         {
    59.             vmin.y = -maxY - vY;
    60.             vmax.y =  maxY - vY;
    61.         }
    62.         else
    63.         {
    64.             vmin.y =  maxY - vY;
    65.             vmax.y = -maxY - vY;
    66.         }
    67.  
    68.         if(normal.z > 0.0f)
    69.         {
    70.             vmin.z = -maxZ - vZ;
    71.             vmax.z =  maxZ - vZ;
    72.         }
    73.         else
    74.         {
    75.             vmin.z =  maxZ - vZ;
    76.             vmax.z = -maxZ - vZ;
    77.         }
    78.        
    79.         if(Vector3.Dot(normal, vmin) > 0.0f)
    80.         {
    81.             return false;
    82.         }  
    83.        
    84.         if(Vector3.Dot(normal, vmax) >= 0.0f)
    85.         {
    86.             return true;
    87.         }
    88.        
    89.         return false;
    90.     }
    91.    
    92.     private static void FindMinMax(float x0, float x1, float x2, out float min, out float max)
    93.     {
    94.         min = (x0 < x1) ? ((x0 < x2) ? x0 : x2) : ((x1 < x2) ? x1 : x2);
    95.         max = (x0 > x1) ? ((x0 > x2) ? x0 : x2) : ((x1 > x2) ? x1 : x2);
    96.     }
    97.  
    98.     public static bool Project(
    99.         float ea1, float ea2,
    100.         float v1a1, float v1a2,
    101.         float v2a1, float v2a2, float rad)
    102.     {
    103.         var p0 = ea1 * v1a2 - ea2 * v1a1;                
    104.         var p2 = ea1 * v2a2 - ea2 * v2a1;  
    105.         var min = p0 < p2 ? p0 : p2;
    106.         var max = p0 > p2 ? p0 : p2;
    107.         if(min > rad || max < -rad)
    108.         {
    109.             return true;
    110.         }
    111.         return false;
    112.     }
    113.  
    114.     public static bool Project(Vector3 vert1, Vector3 vert2, Vector3 edge, int axis1, int axis2, float rad)
    115.     {
    116.         var p0 = edge[axis1] * vert1[axis2] - edge[axis2] * vert1[axis1];                
    117.         var p2 = edge[axis1] * vert2[axis2] - edge[axis2] * vert2[axis1];  
    118.         var min = p0 < p2 ? p0 : p2;
    119.         var max = p0 > p2 ? p0 : p2;
    120.         if(min > rad || max < -rad)
    121.         {
    122.             return true;
    123.         }
    124.         return false;
    125.     }
    126.  
    127.     // faster than Mathf.Abs
    128.     public static float Abs (float val)
    129.     {
    130.         return val < 0 ? -val : val;
    131.     }
    132.  
    133.     public static bool Check(Bounds bounds, Triangle triangle)
    134.     {
    135.         var boundsCentre = bounds.center;
    136.         var boundsExtents = bounds.extents;
    137.  
    138.         vertA.x = triangle.vertA.x - boundsCentre.x;
    139.         vertA.y = triangle.vertA.y - boundsCentre.y;
    140.         vertA.z = triangle.vertA.z - boundsCentre.z;
    141.  
    142.         vertB.x = triangle.vertB.x - boundsCentre.x;
    143.         vertB.y = triangle.vertB.y - boundsCentre.y;
    144.         vertB.z = triangle.vertB.z - boundsCentre.z;
    145.  
    146.         vertC.x = triangle.vertC.x - boundsCentre.x;
    147.         vertC.y = triangle.vertC.y - boundsCentre.y;
    148.         vertC.z = triangle.vertC.z - boundsCentre.z;
    149.  
    150.         // overlap in the {x,y,z}-directions
    151.         // find min, max of the triangle each direction, and test for overlap in
    152.         // that direction -- this is equivalent to testing a minimal AABB around
    153.         // the triangle against the AABB
    154.         float min, max;
    155.         // test in X-direction
    156.         FindMinMax(vertA.x, vertB.x, vertC.x, out min, out max);
    157.         if(min > boundsExtents.x || max < -boundsExtents.x)
    158.         {
    159.             return false;
    160.         }
    161.         // test in Y-direction
    162.         FindMinMax(vertA.y, vertB.y, vertC.y, out min, out max);
    163.         if(min > boundsExtents.y || max < -boundsExtents.y)
    164.         {
    165.             return false;
    166.         }
    167.         // test in Z-direction
    168.         FindMinMax(vertA.z, vertB.z, vertC.z, out min, out max);
    169.         if(min > boundsExtents.z || max < -boundsExtents.z)
    170.         {
    171.             return false;
    172.         }
    173.  
    174.         edgeA.x = vertB.x - vertA.x;
    175.         edgeA.y = vertB.y - vertA.y;
    176.         edgeA.z = vertB.z - vertA.z;
    177.  
    178.         edgeB.x = vertC.x - vertB.x;
    179.         edgeB.y = vertC.y - vertB.y;
    180.         edgeB.z = vertC.z - vertB.z;
    181.  
    182.         edgeC.x = vertA.x - vertC.x;
    183.         edgeC.y = vertA.y - vertC.y;
    184.         edgeC.z = vertA.z - vertC.z;
    185.  
    186.         // Project the points on to the planes formed by the aabb normals
    187.         var fex = Abs(edgeA.x);
    188.         var fey = Abs(edgeA.y);
    189.         var fez = Abs(edgeA.z);
    190.         if(Project(
    191.             edgeA.z, edgeA.y,
    192.             vertA.z, vertA.y,
    193.             vertC.z, vertC.y,
    194.             fez * boundsExtents.y + fey * boundsExtents.z))
    195.         {
    196.             return false;
    197.         }
    198.         if(Project(
    199.             -edgeA.z, -edgeA.x,
    200.             vertA.z, vertA.x,
    201.             vertC.z, vertC.x,
    202.             fez * boundsExtents.x + fex * boundsExtents.z))
    203.         {
    204.             return false;
    205.         }
    206.         if(Project(
    207.             edgeA.y, edgeA.x,
    208.             vertB.y, vertB.x,
    209.             vertC.y, vertC.x,
    210.             fey * boundsExtents.x + fex * boundsExtents.y))
    211.         {
    212.             return false;
    213.         }
    214.        
    215.         fex = Abs(edgeB.x);
    216.         fey = Abs(edgeB.y);
    217.         fez = Abs(edgeB.z);
    218.         if(Project(
    219.             edgeB.z, edgeB.y,
    220.             vertA.z, vertA.y,
    221.             vertC.z, vertC.y,
    222.             fez * boundsExtents.y + fey * boundsExtents.z))
    223.         {
    224.             return false;
    225.         }
    226.         if(Project(
    227.             -edgeB.z, -edgeB.x,
    228.             vertA.z, vertA.x,
    229.             vertC.z, vertC.x,
    230.             fez * boundsExtents.x + fex * boundsExtents.z))
    231.         {
    232.             return false;
    233.         }
    234.         if(Project(
    235.             edgeB.y, edgeB.x,
    236.             vertA.y, vertA.x,
    237.             vertB.y, vertB.x,
    238.             fey * boundsExtents.x + fex * boundsExtents.y))
    239.         {
    240.             return false;
    241.         }
    242.        
    243.         fex = Abs(edgeC.x);
    244.         fey = Abs(edgeC.y);
    245.         fez = Abs(edgeC.z);
    246.  
    247.         if(Project(
    248.             edgeC.z, edgeC.y,
    249.             vertA.z, vertA.y,
    250.             vertB.z, vertB.y,
    251.             fez * boundsExtents.y + fey * boundsExtents.z))
    252.         {
    253.             return false;
    254.         }
    255.  
    256.         if(Project(
    257.             -edgeC.z, -edgeC.x,
    258.             vertA.z, vertA.x,
    259.             vertB.z, vertB.x,
    260.             fez * boundsExtents.x + fex * boundsExtents.z))
    261.         {
    262.             return false;
    263.         }
    264.  
    265.         if(Project(
    266.             edgeC.y, edgeC.x,
    267.             vertB.y, vertB.x,
    268.             vertC.y, vertC.x,
    269.             fey * boundsExtents.x + fex * boundsExtents.y))
    270.         {
    271.             return false;
    272.         }
    273.  
    274.         // if the box intersects the plane of the triangle  compute plane equation of triangle: normal * x + d = 0
    275.         if(!PlaneBoxOverlap(triangle.normal, vertA, boundsExtents))
    276.         {
    277.             return false;
    278.         }
    279.         return true;
    280.     }
    281. }
    282.  
     
    Last edited: Jan 23, 2020
  2. csofranz

    csofranz

    Joined:
    Apr 29, 2017
    Posts:
    1,556
    What is a voxel in this context? Brian Su's code (which you copied with insufficient attribution here) clearly states that the voxel data is a 3D Array of booleans with the meaning true = solid, false = empty. It's up to you to define what a voxel is in your game context, and transform the bool Array into something usable in your game.

    As a first Approximation, run a script over the Array, and place a cube at (x, y, z) if map[x,y,z] is true, then expand from there.
     
    slowpuke666 and Yoreki like this.
  3. Yoreki

    Yoreki

    Joined:
    Apr 10, 2019
    Posts:
    2,605
    What do you mean with 'there are no voxels inside object'? When you want a world based on voxels, then the entire point of doing it efficiently is that voxels are not their own objects. This would be way too performance heavy. Instead, a voxel worls basically renders the outside layer that is visible and, until edited if possible, acts as if the entire thing is one object (or in most cases 'chunk').

    If it does not work at all for you, then you probably missed some components.
    At line 35 it expects to find a Meshfilter. Did you add one to your object? Renderer?

    Edit: It also expects you to add a voxelModel. Seems like this 'Voxelizer' is effectively just spawning a cube in a 3D array at every location where the bool is true? Going with this approach, even one 'Minecraft chunk' would lag out the best of hardware.
     
    Last edited: Jan 23, 2020
  4. slowpuke666

    slowpuke666

    Joined:
    May 4, 2018
    Posts:
    7
    It works fine, but as i said when i use script on a sphere, after voxelization i have a new sphere created from lots of cubes, but it's empty inside.
     
  5. Yoreki

    Yoreki

    Joined:
    Apr 10, 2019
    Posts:
    2,605
    In the third script you just posted he implements an AABB check. He just renders the triangles that are on the outside (even tho, i believe he is rather just spawning cubes on the outside? Would be at least some optimization but far from optimal).

    As i said in my first post, for performance reasons going in this direction is the desired behavior. If you actually want a huge lump of cube-gameobjects, the implementation for this is extremely simple. Just iterate a 3D array with some data in it and instantiate a cube object at each location where it belongs (depending on your definition for where cubes belong. On a bool array they would belong at true, at a float array they would belong at each location with a value over some treshhold). Done. Extremely imperformant due to tons of drawcalls and unnecessary mesh sides tho.
    Is this the desires behavior? What do you need it for?