Metaballs Without Shaders, Plus Liquid Physics

Theory

As you might guess from the title, the task was to draw liquids using metaballs. The essence of this technique is finding the set of points that lie no farther than some distance from the center of any of the metaballs — the “drops” that make up the liquid (see wiki for more detail). There are many different ways to render them, including CSS. The simplest and most effective method boils down to drawing circles with inverse-square opacity falloff, then, in the resulting image, discarding areas with opacity below 0.5 and filling the remaining ones with a solid color.

In this screenshot from XScreenSaver‘s MetaBalls, you can see that overlapping circles form fairly good-looking “spikes” and look organic wherever there’s a lot of overlap. This screensaver doesn’t filter the zones, but modern hardware can easily handle that.

The first thing I did was think about how I’d do metaballs with shaders: first, pass four vertices per metaball into the vertex shader, forming a quad out of them with texture coordinates, then in the pixel shader draw either a ready-made texture or the result of an inverse-square function:

vec2 pos = texCoord.xy - vec2(0.5,0.5);
color.a = 0.25/dot(pos,pos);

We write the result to a buffer and process it a second time with a pixel shader, doing a discard if alpha is below 0.5 and coloring or texturing the rest. Of course, you’d need to tune the coefficients and maybe add a bit of “polish” in the final shader.

Practice

But without shaders, the same approach done on the CPU looks questionable: create a buffer in memory, say 1024x1024xRGBA, iterate over the array of liquid “drops,” and for each one, in a square with sides R*2+1, set coefficients using the inverse-square-distance-from-center formula. Then run through the finished buffer, clearing out RGBA values to emulate a discard, filling solid zones, and finally sending that buffer off to the video card. At radius R = 20 and 40 “drops,” that works out to 67,240 calculations plus 1,048,576 iterations over the pixel array with extra processing, every single frame. Not to mention shipping a 4MB texture into video memory and hoping for 60fps on mobile devices.

Just as an experiment I implemented this scheme and got stuttering even on a desktop computer. And the result looked plain weak besides: jagged edges, uniform fill color, geometrically-too-precise “spikes.” Along the way I also made the classic premature-optimization mistake — I tried doing all the operations with integer coordinates, which may have given a speed boost, but hurt quality and added a “jittery” feel to the liquid’s motion.

It was actually thinking about integer calculations that pointed me toward the realization that I’d taken the wrong path: I’d loaded too much onto the CPU when part of the work could be handed off to the GPU. The right solution turned out to be… shrinking the texture several times over! But this time I decided to use the same effect Valve uses for fonts and graffiti — Signed Distance Field Alpha Magnification. For anyone unfamiliar with this technique, in a nutshell: magnifying the image doesn’t degrade quality in gradient zones, i.e. if there’s a smooth transition from 0.0 to 1.0, the segment inside it keeps its shape at any scale, as in this picture:

You can read more about it here.

For the liquid, I made a 256×256 buffer and left a gradient at the border of each “drop,” rescaling the alpha slightly — roughly speaking, everything below the original 0.4 value is discarded, everything above 0.6 is filled solid, and where there used to be a transition from 0.4 to 0.6, there’s now a transition from 0.0 to 1.0 (in practice a cubic function is used there, see the code below). I shrank the radius of each “drop” to 5 pixels, which brought the per-frame cost down to 4840 calculations and a 65536-pixel, 256KB buffer. That reduction in load let me switch to floating-point operations with fairly high precision — for each “drop” an 11×11-pixel region is processed, and for every pixel the distance is computed to the drop’s exact coordinate rather than to the pixel at the center of the region. The result is sent to the video card via glTexSubImage2D with ALPHA_TEST at 0.5. The GPU trims the drop’s edge visually cleanly enough, even when the liquid texture is scaled up 4-8 times.

Here’s the processing code that produced the image above:

for (int i = 0; i < m_metaballs.Length; i++)
{
    int minX = (int)Math.Floor(m_metaballs [i].Position.X - s_radius);
    int minY = (int)Math.Floor(m_metaballs [i].Position.Y - s_radius);
    int maxX = (int)Math.Ceiling(m_metaballs [i].Position.X + s_radius);
    int maxY = (int)Math.Ceiling(m_metaballs [i].Position.Y + s_radius);

    for (int y = minY; y < maxY; y++)
        for (int x = minX; x < maxX; x++)
        {
            float dist =
                        (x - m_metaballs[i].Position.X) * (x - m_metaballs[i].Position.X) +
                        (y - m_metaballs[i].Position.Y) * (y - m_metaballs[i].Position.Y);

            if (dist < s_radiusSqrd)
            {
                dist = 1.0f - (dist * s_iradiusSqrd);
                int value = (int)(dist * dist * 256.0f);

                int index = (x + y * s_fieldWidth) * 4;

                m_field[index + 3] = (byte)NormalizeInt(m_field[index + 3] + value, 0, 255);

                // shift from top left
                int v = (int)((Math.Abs(x - minX) + Math.Abs(y - minY)) * 32.0f);

                // middle value
                m_field[index + 1] = (byte)NormalizeInt((m_field[index + 0] + v) /2, 0, 255);
                // max value
                m_field[index + 0] = (byte)NormalizeInt(Math.Max(m_field[index + 0], v), 0, 255);
                // metaball index
                m_field[index + 2] = (byte)(i + 1);
            }
        }
}

for (int i = 0; i < m_field.Length; i += 4)
{
    int a = m_field [i + 3];
    if (a > 40)
    {
        float na = a / 255.0f + 0.4f;
        na = (na * na * na);

        if (na > 0.8f)
            na = 0.8f;
        float nx = m_field [i + 0] / 32.0f;
        if (nx > 4)
            nx = 4;
        float ny = m_field [i + 1] / 32.0f;
        if (ny > 4)
            ny = 4;

        m_field [i + 0] = (byte)(25 * na + 30 * nx + 5 * ny);
        m_field [i + 1] = (byte)(100 * na + 30 * nx + 10 * ny);
        m_field [i + 2] = (byte)(150 * na + 30 * nx + 5 * ny);
        m_field [i + 3] = (byte)(255 * na);
    }
}

A bit more wizardry was needed to give the liquid a more “voluminous” look with darkening in the top-left corner, and to draw an outline. Here’s what the final version looks like, with GL_ONE/GL_ONE_MINUS_SRC_ALPHA blending:

If you look closely, near the edge you can see the shading isn’t quite perfect, due to the texture’s low resolution. That could be fixed by making the whole liquid a single flat color, but I decided to keep this effect to get a more dynamic-looking picture.

Physics

Overall the liquids came out looking more or less decent, and at that point I wanted to turn the game into an actual puzzle game, something like Teeter. I sometimes use the Farseer engine (a C# port of Box2D) in games, so when I found the blog of a certain QuantumYeti I was quite pleased, and after a while managed to get his code running. Everything would have been fine, except the liquid leaked through the tiniest gaps between objects and ran off the edge of the screen. As a quick fix I hacked together a patch to the engine that adds a small offset along the normal vector to every vertex of a convex polygon. That solved most of the problems, so I handed the prototype to the level designer and waited for the results. A few weeks later the level designer started complaining that simple elements were handled reasonably well, but on complex curves and sharp corners the liquid could get stuck forever.

This didn’t seem like a big problem and looked like just a temporary bug. I dug a bit into QuantumYeti’s code and realized things were pretty rough in there, since it was more of a proof of concept than a working fluid engine: shaky control flow logic, constants hardcoded in the code, temporary variables stored in a class with public fields, and other such issues. But the main thing was that the collision logic with objects was very crude and didn’t suit our task at all — when a liquid particle hit the inside of an object, its velocity got zeroed out and it was teleported along the surface’s normal vector. If the particle then ended up inside another object, it would freeze there forever, with external forces and the liquid’s viscosity no longer affecting it. Particles were also treated as point bodies, and collisions used the TestPoint method, so they could leak through gaps. Simple patches didn’t help here, and my hack of enlarging the objects only made the situation worse, so I decided to switch to a different physics engine.

The choice fell on liquidfun, or more precisely on its full C# port, sharpbox2d. This engine was built by folks at Google, is quite solid on the inside, and gives nice speed and dynamics to liquid motion. The C# port turned out to be a bit worse and generally unfinished — it compiled but didn’t work, because it often used the Java approach where a function mutates a class instance without the instance being marked with ref or out, and if that got turned into a struct during porting, the logic breaks. I took on fixing these problems and within a day had a working version of the engine (p.s. I can post it on git if anyone needs it), then adapted the whole game to work with it. Everything would have been fine, except the level designer described the liquid’s behavior in the new engine as “a lump of dough crawling along oiled walls.” I spent some time fiddling with the parameters until I realized it was pointless — this physically accurate, high-quality engine simply wouldn’t let me get the viscosity and density parameters I needed, the ones that in QuantumYeti’s prototype had been eyeballed, baked in as constants, and approximated with formulas.

By this point I understood liquid physics well enough to have a rough sense of how the collisions should work and why the previous version didn’t. The solution was built around ray casting during particle movement. It took a few days to rework one small method, but overall I was happy with the final result — the liquid no longer leaks through, doesn’t stick to walls, and doesn’t stop its internal motion when it touches objects.

            RayCastInput input = new RayCastInput();
            input.Point1 = particle.oldPosition;
            input.Point2 = newPosition;
            input.MaxFraction = 1.0f;
            RayCastOutput output = new RayCastOutput();
/// ... skipped ...
            if (fixture.RayCast(out output, ref input, c))
            {
                Vector2 n = output.Normal;
                Vector2 p = (1 - output.Fraction) * input.Point1 + output.Fraction * input.Point2 + PUSHBACK * n;
                Vector2 v = (p - particle.position);
                        
                float ax = moveVector.X - v.X;
                float ay = moveVector.Y - v.Y;
                float fdn = ax * n.X + ay * n.Y;
                        
                antiGravity -= n * fdn;
            }

While iterating over all the shapes that intersect (or will intersect in the next frame), I build an antiGravity vector pointing opposite to the direction of motion.

My FluidSystem.cs code, cleaned up a bit but keeping the original author’s namespace, logic, and comments, is available here: runserver.net/temp/FluidSystem.cs

Maybe someone will want to use it in their own projects, or just polish it further and bolt it onto some engine.

The final touch to the physics was adding moving objects — they can start intersecting with the liquid on their own, not as a result of particle movement, so ray casting doesn’t quite fit there, and I had to fall back on the original author’s approach with the TestPoint method and point-based checks. That introduced a few bugs, but for this project they turned out not to matter much.

Overall, you could say the whole project was born from workarounds and still stands on them — shader graphics without shaders, liquid physics without a liquid engine, patches and band-aids instead of proper refactoring. But then again, if something decent came out of a fun argument and a desire to do something that couldn’t be done by ordinary means — pourquoi pas?