Metaballs without shaders + fluid physics

Once I had a dispute with the ZimM habrauser about a non-2D 2D engine: I argued that shaders are not necessary for simple 2D games, almost all the effects can be done with sprites, its position was the opposite. I repeatedly returned to this argument in my mind and invented tasks that could not be implemented at first glance without shaders, and it was the solution of one such task that led to the creation of a game where the player controls the fluid by tilting the phone.

Theory

As you can guess from the title, the task was to draw liquids using metaballs. The essence of this technology is in finding a set of points that are not further some distance from the center of any of the meta-balls - “drops” that make up the liquid (more precisely, look at the wiki ). There are many different options for rendering them, including on CSS . The simplest and most effective method is to draw circles with reverse quadratic transparency and in the resulting picture, drop zones with transparency less than 0.5, and paint the rest with one color.



In this screenshot from XScreenSaver MetaBalls, it can be seen that the intersecting circles form sufficiently high-quality “spikes” and look organically in places of multiple overlapping. This screensaver did not filter zones, but modern equipment can handle it.





')

First of all, I started thinking like making metaballs on shaders: first, we send four vertices for each Metaball to the vertex shader, create a square with texture coordinates from them, then in the pixel shader we draw either a ready-made texture or the result of an inverse-quadratic function:

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

The result of the work is written to the buffer and processed again with a pixel shader with discard if alpha is less than 0.5 and painting or texture for the other values. Of course, it will be necessary to pick up the coefficients and maybe a few “decorations” in the final shader.

Practice

But without shaders, the same approach, but on the CPU it looks doubtful: we create a buffer in memory, for example, 1024x1024xRGBA, pass through an array with liquid “drops” and arrange the coefficients using the inverse square of the distance for everyone in a square with R * 2 + 1 sides from the center. Well, then we run over the finished buffer and clean up the RGBA values, imitating the discard, paint over the solid zones, and then send this buffer to the video card. It turns out at a radius of R = 20 and 40 "drops" each frame must be done 67240 calculations + 1048576 iterations over an array of pixels with additional processing. This is not to mention the transfer of 4Mb textures to video memory and the hope of a 60fps frequency on mobile devices.



For the sake of experiment, I implemented such a scheme and got the brakes even on a desktop computer. Yes, and the result looked frankly weak: stepped edges, uniform fill color, too geometrically reliable "spikes". At the same time, I made a classic mistake of premature optimization - I tried to do all the operations with integer coordinates, which could have increased the speed, but it had a bad effect on quality and added “jerkiness” to the fluid movement.



It was thoughts about integer calculations that gave me the idea that I went the wrong way: I put too much on the CPU, although it was possible to transfer some of the work to the GPU. The right decision was ... reducing the texture several times! But now I decided to use the same effect that Valve uses for fonts and graffiti - Signed Distance Field Alpha Magnification . For those who have not encountered this technology, in a nutshell, the principle is this: increasing the picture does not degrade the quality of zones with gradients, i.e. if there is a smooth transition from a value of 0.0 to 1.0, then the gap inside it will retain its shape at any scale, as in this picture:





You can read more here .



In the case of liquids, I made a 256x256 buffer and left a gradient at the border of each “drop”, slightly scaling the alpha - simply, everything is dropped below the initial value of 0.4, above 0.6 it is filled with a solid color, and where there was a transition from 0.4 to 0.6, now the transition from 0.0 to 1.0 (in fact, a cubic function is used there, see the code below). I reduced the radius of each “drop” to 5 pixels, so for each frame there were 4840 calculations and 65536 pixels in a 256Kb buffer. Such a reduction in the load made it possible to switch to floating-point operations with fairly high accuracy - for each “drop” a region of 11x11 pixels is processed and for each pixel the distance to the exact coordinate of the “drop” is calculated, and not to the pixel in the center of the region. The result is sent to the video card via glTexSubImage2D with ALPHA_TEST at 0.5. The GPU cuts off the edge of the drop visually, quite neatly, even when scaling a texture with liquid 4-8 times.







Here is the processing code with which the picture was taken above:





A little more shamanism was needed to give the fluid a more “volumetric” look with darkening in the upper left corner and to draw the outline. This is what the final version looks like with GL_ONE / GL_ONE_MINUS_SRC_ALPHA blending:







If you take a closer look, then not perfect shading quality is seen closer to the edge due to the low resolution of the texture. This could be corrected by making all the liquid monochrome, but I decided to leave this effect to get a more dynamic picture.

Physics

In general, the fluids turned out visually more or less normal and then I wanted to make a puzzle out of the game, similar to Teeter. I sometimes use the Farseer engine (Box2D port in C #) in games, because when I found the blog comrade. QuantumYeti was very happy and after some time was able to run its code. Everything would be fine, but liquids seeped through the smallest gaps between objects and flowed behind the screen. As a quick fix, I sketched a patch to the engine, which at each vertex of the convex polygon adds a small offset along the normal vector. This solved most of the problems, because I gave the prototype to the designer and waited for the result. After a few weeks, the level designer began to complain that simple elements are processed relatively normally, but on complex curves and sharp corners, the liquid can get stuck forever.



This did not seem like a big problem and just looked like a temporary bug. I dug a little into the code Comrade. QuantumYeti realized that everything was pretty bad there, because it was more of a proof of concept and not a working engine for liquids: dubious execution logic, constants in the code, storage of temporary variables in a class with public fields and other jambs. But most importantly, the logic of collisions with objects was very conditional and not suitable for our task - when liquid particles got inside the object, their speed was reset and they teleported in the direction of the normal vector to the surface. If at the same time the particle fell into another object, then the external forces and the viscosity of the fluid hung forever and no longer acted on it. Particles were also considered to be point bodies and the TestPoint method was used for collisions, so they could leak into the slots. Simple patches did not help here, and my hack with the increase in objects aggravated the situation, so I decided to switch to another physics engine.



The choice fell on liquidfun , or rather, on its full C # port, sharpbox2d . This engine is made by guys from Google, is good enough inside, gives a pleasant speed and dynamics of the movement of liquids. The port on C # turned out to be a bit worse and, on the whole, not finished - it compiled, but did not work, since The Java approach was often used when a function changes an instance of a class, but it is not marked with the words ref or out, and if it turned into a struct during porting, the operation logic is violated. I took up the correction of these problems and in a day I had a working version of the engine (ps I can put in git if someone needs it), and then adapted the whole game to work with it. Everything would be fine, but the level designer described the behavior of the fluid in the new engine as “a piece of dough creeping along the oiled walls”. For a while I was playing with the parameters, until I realized that there would be no sense from this - physically accurate and high-quality this engine did not allow me to get the necessary viscosity and density parameters, which in the prototype from QuantumYeti were set "by eye", stitched constants and approximate formulas.



At this point, I had already pretty well figured out the physics of liquids and could conditionally understand how collisions should work and why the previous version did not work. The basis was the ray casting method while the particle is moving. It took several days to rework one small method, but on the whole, the final version suited me — liquids no longer leak, do not stick to the walls, and do not stop internal movements when they come into contact with 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 - vX; float ay = moveVector.Y - vY; float fdn = ax * nX + ay * nY; antiGravity -= n * fdn; } 

During the iteration of all the figures with which there are (or will be in the next frame) intersections, I form an antiGravity vector, directed opposite to the motion vector.



My FluidSystem.cs code with some sweep, but with the namespace, logic, and comments of the first author is available here: runserver.net/temp/FluidSystem.cs



Perhaps someone wants to use it in their projects, or just bring to mind and add to any engine.



The final stroke in physics was the addition of moving objects - they can begin to intersect with the fluid themselves, and not as a result of particle motion, because ray casting does not quite fit here and had to use the author’s original approach with the TestPoint method and spot checks. Then there were some bugs, but for this project they were no longer significant.



In general, it can be said that the whole project is born from crutches and it also keeps on them - shader graphics without shaders, fluid physics without a fluid engine, patches and patches instead of refactoring. But on the other hand, if something good came out of a funny dispute and the desire to do something that is not feasible by ordinary methods - pourquoi pas?