I’ve recently been getting into Unity to see if I could make a little basic game. My first idea has taken me down the road of procedurally generating meshes for objects in Unity . One method of doing this is creating an Isosurface using various algorithms. In my case I was trying to create Metaballs.
Metaballs are points in space, which exert a “force” which decreases the further you get away from it. Where this “force” hits 0 is where the surface is drawn.
When multiple metaballs are close to each other, the force they exert on a point will be greater than a single metaball alone. And so it appears the surface of the metaballs grow towards each other like in the demo above.
An algorithm used to draw the mesh is Marching cubes. After initially looking at the example script from Unity3d community I thought I was a bit out of my depth, but I soon got it working and was creating blobby objects.
There is plenty of material online regarding how marching cubes work and how you create a isosurface from a series of points within a 3D grid. Paul Bourke’s article helped immensely.
The performance impact increases vastly as the number of metaballs increase, as it requires traversing the full 3D grid each time to see if it was in range of the metaballs radius.
Reducing grid computation
One way to increase performance was to decrease the number of points that needed to be computed to find where the metaballs surface should be. A simple implementation will iterate through the full grid.
However, we compute which of the 8 vertices of the voxel the metaball surface should intersect as per Marching Cubes. Using some fancy lookup tables we can then choose a direction to compute next based on which vertices were intersected.
Effectively this allows us to only compute the voxels which contains the surface of the metaball. Rather than all of the other voxels which are empty 90% of the time!
In the past few months I tried to build in an alternative meshing method which uses Naive Surface Nets rather than the traditional meshing done by Marching Cubes. I managed to get it working, based on the work in Mikola Lysenko’s blog. This meant I could march across the same points, but generate fewer vertices and faces for the mesh, hopefully increasing performance.
I also encountered some weird bugs during my learning like the below.
Finally I have managed to optimise my metaballs algorithm to create a decent amount of metaballs and generate a mesh at a good resolution that it doesn’t look too blocky.
There are much faster ways to do what I have done using the GPU through a compute shader. However since I am targeting android with my little game, I need to do it on CPU until our mobile GPUs catch up with desktops.