Keeping on the trend on simulating interesting things in Unity, this time I'm trying to get Metaballs working in Unity using the Marching Squares Algoritthm, SPOILER ALERT: This is how the final result looks like.
This "lava-lamp" like effect can be a achieved by using the Marching Squares algorithm to procedurally generate a Mesh from a regular grid of sampled scalars, to put it in simpler terms, the algorithm takes as input, a uniform 2D grid of floats, and generates from that grid, smooth closed curves that "wrap around" regions where the values are above/below a certain threshold.
I also started off each GameObject with a random velocity, so we get a bunch of circles bouncing inside an invisible box.
This "lava-lamp" like effect can be a achieved by using the Marching Squares algorithm to procedurally generate a Mesh from a regular grid of sampled scalars, to put it in simpler terms, the algorithm takes as input, a uniform 2D grid of floats, and generates from that grid, smooth closed curves that "wrap around" regions where the values are above/below a certain threshold.
 |
| Marching squares result with the threshold value set to 6, image shows two possible variations of curves which enclose regions where value of sampled scalar is >= 6. |
Simulation and sampling
Doing this is fairly straightforward in Unity, I just set up a bunch of GameObjects with CircleCollider2D and RigidBody2D components set up as Triggers so that they pass through each other, and wrote some code inside FixedUpdate() so they bounced off some hard-coded world borders.
$$(x - a)^2 + (y - b)^2 \leq r^2$$
Rearranging a bit we get,
$$ \frac{r^2}{(x - a)^2 + (y - b)^2} \ge 1$$
We calculate the LHS of the above expression for each circle, and for each point in a grid inside our "invisible box".
To this I created a VoxelMapManager class, it stores the sampled values in a simple 2D array of floats, and is attached to an empty GameObject which is placed at the world origin.
I'll use the term "voxel" a lot in this project, its technically incorrect since a voxel is a cell in a 3D grid, but here we just have a 2D grid, but whatever.
I also added the function GetSampleAt(Vector2 pos) to the CircularSampleable class posted above to calculate samples for each circle. Its already attached to each circle for the physics sim.
Visual Debugging
This comes up super often when doing games/graphics related stuff, print's, logs and breakpoints help in very rare cases, it is always best to write a bunch of additional code to visualize the data you're debugging in the world, in this case we'll actually draw our voxels and their sample values at the positions their in the world, and we'll also color the voxels black if their sample value is above 1 (inside a circle)
OnDrawGizmos() and OnGUI() to the rescue!
Dump that code into VoxelMapManager with a DebugDraw flag you can set in the inspector. With a voxel size of 1, this is how the debug info should look.
Marching Squares
The high-level description of the Marching Squares Algorithm is pretty straightforward:
- Construct a square by connecting four adjacent vertices.
- Given the sample values at each vertex of the square, determine the mesh configuration from a lookup table (Picture below)
- Calculate the position of the edge vertices using linear interpolation, this means that the edge vertex would lie at the point on the edge where the sample value would be equal to the threshold, assuming the samples are transitioning linearly between the voxels.
Mathematically, given point $P_1$ with sample value $s_1$ and point $P_2$ with sample value $s_2$, point $P$ with a threshold value of $t$ would lie at:
$$P = P_1 + \frac{t - s_1}{s_2 - s_1} * (P_2 - P_1)$$
In our case $t=1$. - According to the configuration from the table, add the vertices and triangles to the mesh.
- March the square forward to the adjacent voxel and repeat the process.
 |
Lookup Table Generation
I created a SquareMeshConfig class, instances of which represent each of the possible configurations shown in the image above. Each vertex is represented as an enum value such as TopLeft, TopRight, BottomCenter, etc. , and each instance contains a List of these types to represent which vertices need to be added. It also maintains a list of triangles, with a scheme identical to Unity's system(an array of vertex indices in clockwise order)
I then used a static size 16 array for the lookup table and one-time initialized it with the instance at each index representing the configuration from the image above.
Mesh Generation
To start off with the mesh generation we need to map the set of four adjacent sample values to one of the configurations in the lookup table. Generating the index is actually fairly simple, you can generate a 4-bit number where each bit represents a sample corner in a square, its set to 1 if the sample value is above threshold, its 0 otherwise. The top left sample corresponds to the LSB and we go in a clockwise order with the bottom left corner corresponding to the MSB.
I've created a simple Square struct that stores the sample values for each corner, and provides properties to access the positions of each corner, it even calculates the LERP'ed positions for the edge vertices based on the sample values, and lastly, uses the bit mapping logic to create the lookup index.
I created a SquareMeshConfig class, instances of which represent each of the possible configurations shown in the image above. Each vertex is represented as an enum value such as TopLeft, TopRight, BottomCenter, etc. , and each instance contains a List of these types to represent which vertices need to be added. It also maintains a list of triangles, with a scheme identical to Unity's system(an array of vertex indices in clockwise order)
I then used a static size 16 array for the lookup table and one-time initialized it with the instance at each index representing the configuration from the image above.
Mesh Generation
To start off with the mesh generation we need to map the set of four adjacent sample values to one of the configurations in the lookup table. Generating the index is actually fairly simple, you can generate a 4-bit number where each bit represents a sample corner in a square, its set to 1 if the sample value is above threshold, its 0 otherwise. The top left sample corresponds to the LSB and we go in a clockwise order with the bottom left corner corresponding to the MSB.
I've created a simple Square struct that stores the sample values for each corner, and provides properties to access the positions of each corner, it even calculates the LERP'ed positions for the edge vertices based on the sample values, and lastly, uses the bit mapping logic to create the lookup index.
I implemented all of this inside a MarchingSquaresMeshGenerator class, it also provides a bunch of lifecycle methods that can clear the buffers at the start of each frame, generating the mesh data from Square instances and copy the buffers over to Unity's Mesh API for rendering once all the squares are added.
Using a MonoBehavior script as a controller for an instance of the above class and passing in the appropriate squares gives you this cool result.
Issues
While everything looks correct, a quick peak at the Stats panel shows us that our Vertex count hovers around 1.7k and peaking at about 2k vertices. Yikes!
This happens because we process each square independently and generate a completely new set of vertices, but in reality each Square shares vertices with adjacent squares
 |
| The same value for the central vertex in red gets added to the vertex buffer four times, the blue edge vertices which are shared between two squares get added twice. |
We can eliminate this by caching vertex indices from the adjacent squares during our generation loop.
There's also the fact that the sampling and generation loops are quite slow because of the sheer number of samples needed.
Since this is C# theres also a lot of GC being invoked as the Mesh data gets copied from my bufers to Unity's Mesh API buffers.
But these are issues I will (attempt) to deal with in Part II!
Is there a part 2?
ReplyDelete