{"id":375,"date":"2021-05-22T20:08:20","date_gmt":"2021-05-22T20:08:20","guid":{"rendered":"https:\/\/bronsonzgeb.com\/?p=375"},"modified":"2021-05-22T20:08:21","modified_gmt":"2021-05-22T20:08:21","slug":"gpu-mesh-voxelizer-part-1","status":"publish","type":"post","link":"https:\/\/bronsonzgeb.com\/index.php\/2021\/05\/22\/gpu-mesh-voxelizer-part-1\/","title":{"rendered":"GPU Mesh Voxelizer Part 1"},"content":{"rendered":"\n

In this article, we’ll start porting my naive mesh voxelizer<\/a> to a multithreaded mesh voxelizer that runs on the GPU through Compute Shaders. First, we’ll set up the compute shader to position all the voxel grid points. Then, we’ll draw the grid points directly from the Compute Buffer on the GPU. From there, we’ll discuss how we can use the Separating Axis Theorem (SAT) to test for collisions between voxels and triangles.<\/p>\n\n\n\n

Setting up the Compute Shader<\/h2>\n\n\n\n

If you’re new to compute shaders, I recommend you start by reading my earlier tutorial<\/a> on the subject because I’m about to gloss over the basics. So what do we need to position the voxel grid? If you followed my previous Voxelization article, you might already know, but I’ll go over it anyway. First, we need the minimum point of the mesh’s bounds, which is the bottom-left-front point. It’s the minimum point because it’s the point where the X, Y and Z values are at their minimum. Given this point and our desired voxel size, we can lay down our voxel grid. We also need the Width, Height and Depth of the mesh’s bounds in voxel units. In other words, how many voxels can we fit in X, Y and Z dimensions? Let’s start writing the compute shader.<\/p>\n\n\n\n

#pragma kernel VoxelizeMesh\nRWStructuredBuffer<float4> _VoxelGridPoints;\n\nfloat4 _BoundsMin;\nfloat _CellHalfSize;\nint _GridWidth;\nint _GridHeight;\nint _GridDepth;\n\nnumthreads(1,1,1)]\nvoid VoxelizeMesh(uint3 id : SV_DispatchThreadID)\n{\n    float cellSize = _CellHalfSize * 2.0;\n\n    _VoxelGridPoints[id.x + _GridWidth * (id.y + _GridHeight * id.z)] = float4(\n        _BoundsMin.x + id.x * cellSize,\n        _BoundsMin.y + id.y * cellSize,\n        _BoundsMin.z + id.z * cellSize, 1.0);\n}<\/code><\/pre>\n\n\n\n
There’s not much going on here yet. We convert the thread id from three-dimensional to a one-dimensional index and then calculate the current voxel position. If you haven’t guessed already, we’ll run a single thread per voxel. This way, the thread id corresponds to the x,y,z position of a voxel in voxel-space, and we convert it to local-space. Then, we take the converted value and store it in our buffer of points. By the way, you may be wondering why we pass the cell half-size if we’re only using the full size. The half-size will come in handy later when we need to calculate the center of each voxel. Next, we’ll write a custom shader to draw directly from our buffer of points.<\/p>\n\n\n\n
Drawing from a Compute Buffer<\/h2>\n\n\n\n
To draw from the compute buffer, we first convert each point from local-space (its position relative to the mesh’s origin) to world-space (its position relative to the world’s origin) and then draw. We do this by multiplying the point’s position by the Local-to-World matrix of the mesh. Since we’re not drawing these points via the regular render pipeline, we’ll have to supply this matrix to the shader. We’ll also point the shader to the compute buffer that holds our array of points. Here’s what the vertex shader looks like:<\/p>\n\n\n\n
struct v2f\n{\n    float4 position : SV_POSITION;\n    float4 color : COLOR;\n    float size : PSIZE;\n};\n\nfloat4x4 _LocalToWorldMatrix;\nStructuredBuffer<float4> _VoxelGridPoints;\nfloat4 _Color;\n\nv2f vert(uint vertex_id : SV_VertexID, uint instance_id : SV_InstanceID)\n{\n    v2f o;\n    float4 localPos = _VoxelGridPoints[instance_id];\n    o.position = UnityWorldToClipPos(mul(_LocalToWorldMatrix, localPos));\n    o.size = 5;\n    o.color = _Color;\n    return o;\n}<\/code><\/pre>\n\n\n\n
And, as for the fragment shader, we have this:<\/p>\n\n\n\n
float4 frag(v2f i) : COLOR\n{\n    return i.color;\n}<\/code><\/pre>\n\n\n\n
By the way, I skipped the Shaderlab boilerplate, but I linked the finished project further down. You can see the complete file there.<\/p>\n\n\n\n
Next, we need to pass the data to the material and ask it to draw. For simplicity, I use DrawProceduralNow<\/code> in the OnRenderObject<\/code> callback. I’m not sure if this callback works in URP or HDRP, but we’ll switch to a more robust API that will work in the future. By the way, the OnRenderObject<\/code> method gets called on all MonoBehaviours just after they render. So we’ll add this to our VoxelizedMesh<\/code> component:<\/p>\n\n\n\n
void OnRenderObject()\n{\n    VoxelizeMeshWithGPU();\n\n    _gridPointMaterial.SetMatrix(\"_LocalToWorldMatrix\", transform.localToWorldMatrix);\n    _gridPointMaterial.SetVector(\"_BoundsMin\", new Vector4(_boundsMin.x, _boundsMin.y, _boundsMin.z, 0.0f));\n    _gridPointMaterial.SetBuffer(\"_VoxelGridPoints\", _voxelPointsBuffer);\n    _gridPointMaterial.SetPass(0);\n    Graphics.DrawProceduralNow(MeshTopology.Points, 1, _gridPointCount);\n}<\/code><\/pre>\n\n\n\n
In this case, the _gridPointMaterial<\/code> is a material that uses our custom Shader. We pass all the data to the material, set the pass to our first (and only) pass, and call DrawProceduralNow<\/code>. As for the DrawProceduralNow<\/code> arguments, we specify the mesh topology, number of vertices per mesh, and how many meshes to draw. In our case, we’re drawing points, each point has a single vertex, and finally, the number of points in the _voxelPointsBuffer<\/code>. To finish, we’ll look at the VoxelizeMeshWithGPU<\/code> function, which initializes the data.<\/p>\n\n\n\n
So let’s recap what we need. For the compute shader, we need the bounds’ min position in local-space, the half-size of a voxel cell and the grid’s width, height and depth. For the material, we need the local-to-world matrix and the bounds’ min position in local space. Of course, we also need to create a compute buffer that’ll hold the position of all the grid points. I’ll drop the entire function here. It’s primarily boilerplate. If any of it is unfamiliar, you may need to revisit this article<\/a> to learn about compute shaders or this other article<\/a> to understand the simple voxelizer that this code is based on.<\/p>\n\n\n\n
void VoxelizeMeshWithGPU()\n{\n    Bounds bounds = _meshCollider.bounds;\n    _boundsMin = transform.InverseTransformPoint(bounds.min);\n\n    Vector3 voxelCount = bounds.extents \/ _halfSize;\n    int xGridSize = Mathf.CeilToInt(voxelCount.x);\n    int yGridSize = Mathf.CeilToInt(voxelCount.y);\n    int zGridSize = Mathf.CeilToInt(voxelCount.z);\n\n    _voxelPointsBuffer?.Dispose();\n    _voxelPointsBuffer = new ComputeBuffer(xGridSize * yGridSize * zGridSize, 4 * sizeof(float));\n    if (_gridPoints == null || _gridPoints.Length != xGridSize * yGridSize * zGridSize)\n    {\n        _gridPoints = new Vector4[xGridSize * yGridSize * zGridSize];\n    }\n    _voxelPointsBuffer.SetData(_gridPoints);\n\n    var voxelizeKernel = _voxelizeComputeShader.FindKernel(\"VoxelizeMesh\");\n    _voxelizeComputeShader.SetInt(\"_GridWidth\", xGridSize);\n    _voxelizeComputeShader.SetInt(\"_GridHeight\", yGridSize);\n    _voxelizeComputeShader.SetInt(\"_GridDepth\", zGridSize);\n\n    _voxelizeComputeShader.SetFloat(\"_CellHalfSize\", _halfSize);\n\n    _voxelizeComputeShader.SetBuffer(voxelizeKernel, VoxelGridPoints, _voxelPointsBuffer);\n\n    _voxelizeComputeShader.SetVector(\"_BoundsMin\", _boundsMin);\n\n    _voxelizeComputeShader.GetKernelThreadGroupSizes(voxelizeKernel, \n\tout uint xGroupSize, \n\tout uint yGroupSize,\n        out uint zGroupSize);\n\n    _voxelizeComputeShader.Dispatch(voxelizeKernel,\n        Mathf.CeilToInt(xGridSize \/ (float) xGroupSize),\n        Mathf.CeilToInt(yGridSize \/ (float) yGroupSize),\n        Mathf.CeilToInt(zGridSize \/ (float) zGroupSize));\n    _gridPointCount = _voxelPointsBuffer.count;\n}<\/code><\/pre>\n\n\n\n
So at this point, we have a compute shader that runs on every voxel surrounding a mesh, and we’re able to draw the voxel grid, which will come in handy for debugging later. On my machine, I can draw around a million points before the framerate drops in the editor. <\/p>\n\n\n\n
\"\"
That’s a lot of voxels<\/figcaption><\/figure>\n\n\n\n
This is significantly better than our naive voxelizer, where drawing using OnSceneGUI<\/code> and the Handles<\/code> API had a notable impact on performance. Additionally, now that we wrote the boilerplate, we only have to implement voxel\/triangle collisions in the compute shader, and our voxelizer is nearly complete. We’ll do that using the Separating Axis Theorem.<\/p>\n\n\n\n
Separating Axis Theorem<\/h2>\n\n\n\n
I’ll briefly explain the separating axis theorem and provide links to some other resources later. The separating axis theorem is a technique for detecting collisions between two convex objects. The idea is that if we look at two convex objects from a handful of specific angles, if there’s an angle in which the two objects don’t overlap, then they aren’t colliding. In other words, imagine you couldn’t see depth. If you held two things, one in front of the other, it would appear as these two objects overlap from some angles. However, if you can find an angle where they aren’t, you know they aren’t colliding. That’s essentially how the SAT algorithm works.<\/p>\n\n\n\n
I won’t implement SAT yet because it would make this post too long, but I’ll share some resources where you can read more about it if you’d like to take a crack at it. Otherwise, stay tuned for part 2.<\/p>\n\n\n\n
Check out the <\/strong>project<\/strong><\/a> on Github to see it in action. If you’d like to learn more about SAT, I found <\/strong>this article<\/strong><\/a> very helpful. You can also read the wikipedia page <\/strong>here<\/strong><\/a>. If you appreciate this article, <\/strong>join my mailing list<\/strong><\/a>, and I’ll email you when part 2 is released.<\/strong><\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"
In this article, we’ll start porting my naive mesh voxelizer to a multithreaded mesh voxelizer that runs on the GPU through Compute Shaders. First, we’ll set up the compute shader to position all the voxel grid points. Then, we’ll draw the grid points directly from the Compute Buffer on the GPU. From there, we’ll discuss how we […]<\/p>\n","protected":false},"author":1,"featured_media":377,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[25,17,1],"tags":[26,8,5,34],"class_list":["post-375","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-compute-shaders","category-graphics","category-unity-programming","tag-compute-shaders","tag-game-development","tag-unity","tag-voxelization"],"_links":{"self":[{"href":"https:\/\/bronsonzgeb.com\/index.php\/wp-json\/wp\/v2\/posts\/375","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bronsonzgeb.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bronsonzgeb.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bronsonzgeb.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/bronsonzgeb.com\/index.php\/wp-json\/wp\/v2\/comments?post=375"}],"version-history":[{"count":2,"href":"https:\/\/bronsonzgeb.com\/index.php\/wp-json\/wp\/v2\/posts\/375\/revisions"}],"predecessor-version":[{"id":379,"href":"https:\/\/bronsonzgeb.com\/index.php\/wp-json\/wp\/v2\/posts\/375\/revisions\/379"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/bronsonzgeb.com\/index.php\/wp-json\/wp\/v2\/media\/377"}],"wp:attachment":[{"href":"https:\/\/bronsonzgeb.com\/index.php\/wp-json\/wp\/v2\/media?parent=375"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bronsonzgeb.com\/index.php\/wp-json\/wp\/v2\/categories?post=375"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bronsonzgeb.com\/index.php\/wp-json\/wp\/v2\/tags?post=375"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}