Pixel Hacking

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.

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.

I also started off each GameObject with a random velocity, so we get a bunch of circles bouncing inside an invisible box.

Now we need to get on with sampling a uniform grid of scalar values from these circles, for any circle with radius $r$ and center $(a,b)$, a point $(x,y)$ is inside the circle if:
$$(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.

Now all thats left is wiring the two classes together by looking up the appropriate SquareMeshConfig for a specific Square and parsing it to add the appropriate data to to Unity's vertex and triangle buffers.
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!

When we last left off, we had a result that looked like this.

While this does look like a blob, it has some artifacts ( you can see slivers of "spokes along the edges of the triangles), and the blob can only be a solid color, which is fairly limiting, unless your game has super minimalistic art-style.

Today I'll be tackling these issues by, first, fixing the buggy rendering and then adding the ability to texture map the blob.

Fixing the rendering issues

The solution I used for this was to take a completely manifold mesh and just mask of the pixels that fall outside the bezier loop.

To start off, we don't need a triangles that filled up the center anymore, so we remove the code that generated that, this should leave you with triangles that look like this, pretty much like how our initial triangle generation looked.

Reverted Triangulation

Now, just flip the discard condition in the bezier shader to render the pixeld outside and discard the pixels inside( Now we discard if y*y - x < 0). Result should look like this.

The Mask

Now, instead of rendering these pixels to the framebuffer ( the display) we want to render it into an buffer in GPU VRAM called the "stencil buffer". Its not rendered to the display, it just store an 8-bit integer for each pixel/fragment, and you can use in your shader to reject or accept pixels.

OpenGL Pipeline

It is in the last "Per-Sample Operations" stage that you can have some Stencil Buffer write or Stencil Buffer read and reject/accept operations for the fragment.

In our case we want to write 1 into the Stencil Buffer for each of the red pixels in the mask. In Unity ShaderLab allows us to specify the stencil logic at the top of our Subshader pass block.

But wait, we can't stop there, we also do not want the mask to render to framebuffer, we can specify just a couple of lines at the top of the Subshader block to do this.

For the mask we need the following code at the top of the shader

Step 2

Now, that we have our mask ready, we want to render the mesh that gets masked. The triangle generation for this pretty trivial, we add outer ring of rigidbodies and the central rigidbody as vertices and make, and have the triangles ordered clockwise, with two outer loop vertices and the third vertex of the triangle being the center.

If that was too confusing, the image below illustrates how you do it. The blue numbers represent the indices of the respective vertices and the orange arrow shows in which order you're sup[posed to add the triangles.

Mesh Triangulation illustration

Now, we need a new shader and associated material for this mesh. Start off by creating a new Standard -> Unlit shader, this will already have all the code needed for being able to add texture maps as well, we just need to a some code at the top telling this object to render in a pass after mask, and to not render the pixels which have a corresponding value of 1 in the pixel shader.

Setting the UV Co-ordinates of the mesh

We also need to assign UV co-ordinates to our mesh vertices, I decided to set the central vertex with a (u,v) of (0.5, 0.5) making it correspond to the center of the texture, for the loop vertices i set them up as follows :

u = - 0.5f * cos(theta) + 0.5f

v = 0.5f * sin(theta) + 0.5f;

Angles

Now, initially I hardcoded the phi 2*PI/NumTris, giving each triangle a fixed UV, this worked OK for most situations but as the blob would simulate the value of phi would change and this would cause the texture maps to stretch/ compress.

Switching it to actually measure the value of phi every frame inside Update() and updating the UV's accordingly resulted in a much better looking blob.

Here's the function that does that

Results

And, thus we have a nice texture mapped blob!

At the last Global Game Jam (2016) I worked on a 2D physics puzzle game , and we wanted to have monsters which were like jello-o blobs of lava which you could interact with physically, and since we had some really good artists with us, we decided to implement them as spritesheet animations with some animation state-machine controlling code.

This didn't work out too well and we constantly ended up with situations that looked a bit like this.

Whats happening here is the state-machine script keeps switching the animation state between the falling and the resting animation as the collider bounces of the wall on the left and the platform on the right, and no amount of tweaking and rewriting the controller script with more conditions seemed to make a difference.

The correct way to go about it would be would be to physically simulate the blob, but Unity really doesn't provide a way to do this in a way that doesn't look terrible and allows the artist to add some character to the blob ( can you spot the facial expressions in the gif above? ), I have some solutions in my head to tackle this and this blog post is the first in a series in which I try an find a one.

Step I : Setup the joints for the blob physics simulation

This is fairly straightforward in Unity, you basically want to set up a bunch of Rigibody2D's and SpringJoint2D's that look a bit like this,

Each of the green lines is one SpringJoint2D and each square is a Rigidbody2D with a BoxCollider2D. ( Make sure all of the physics objects are in the same level and do NOT child them among each other )

Step II : Rendering the Blob

If we were to simply build up triangles along the spring joints and fill up the inside, you get something that looks like this,

That behavior is pretty blobby, but its too jagged because we don't have enough triangles. Well, the easy solution to this is to just add a bunch more points on the outer loop, but this will slow down performance a lot, especially on mobile, especially if you have a lot of them simulating at the same time, we can do better.

We effectively want to round the corners on the blob above, and we want to let the GPU do this work for us, because CPU bound curve smoothing code in C# would put us squarely back into to same problem of slowdown on mobile as we would have to compute a LOT of intermediary points to make it look smooth.

So, we want to apply a curve smoothing algorithm (Bezier Curves/B-Splines/ Catmull-Rom) on the GPU, while pretty much any smoothing algorithm can be implemented on the GPU using Geometry Shaders ,with that we would only be able to support OpenGL4+ or DX11+ devices, not ideal since a large portion of current mobile devices( and even WebGL) are stuck on OpenGL ES 2.1 and only support Vertex and Fragment Shaders. However, Loop & Blinn at Microsoft Research figured out how to do bezier curve rendering on fragment shaders at the per pixel level, and used it for creating resolution-independent texture maps of text on 3D surfaces, here's a really cool result from their paper.

The Math

I'll skip over the really Math-y bits in the paper, and get right to the final result that's useful for us, for the triangle given below,

with [u, v] co-ordinates of the vertices as shown, a point( x,y) is inside the curve (colored red) if ( y * y - x ) < 0.

This gives us a simple condition that we can evaluate at the per-pixel level of our fragment shader, if you want to see why you can go read the paper for their derivation or refer this GPU Gems article by Nvidia.

However, since we are restricted to quadratic Bezier Curves, we are going to have to change our triangulation scheme significantly to support this shader for the result we need.

Triangulation Scheme

We basically want our triangles to look like this,

What we're doing here is between each of the outer rigidbodies, we add TWO vertices at the mid-point, this is because,

Two separate bezier curves are not guaranteed to be continuous at their end points, but a bezier curve is tangential at its end points, by putting the end points along a straight line, we guarantee that they have the same tangent and create a smooth curve.
We're adding two vertices because, that same vertex needs to be (u,v) = (1,1) for the previous triangle and (u,v) = (0,0) for the next one.

The code below does all this work, I've tweaked it a bit and added some additions like offsetting the vertices outwards from the rigibodies.

The Shader

Since I've already described the core logic of the shader earlier, for those that arent familiar, this is a overview of the OpenGL2 and DX9 rendering pipelines

An, important detail missed out in this image is that the Rasterizer( the GPU hardware) automagically interpolates color,uv and vertex-normal values within the pixels of the triangle, it is this interpolated data that you get at the fragment shader.

The final shader code is below.

Results

Now all you need to do is create the material, apply the shader and BOOM, the blob is transformed:

Up Next

Well, our mesh isn't manifold and has double vertices, plus we haven't allowed custom texture mapping of the blob yet, I have some ideas on how to achieve those goals using maybe some stencil buffering and masking.

Subscribe to: Posts ( Atom )

Pixel Hacking

Metaballs using Marching Squares in Unity (Part I)

Simulation and sampling

Marching Squares

Issues

Blobby things, bezier curves and shaders (Part II)

Fixing the rendering issues

Results

Blobby things, Bezier Curves and Shaders(Part I)

Step I : Setup the joints for the blob physics simulation

Step II : Rendering the Blob

The Math

Triangulation Scheme

The Shader

Results

Up Next