So if you've been following my twitter recently you would have noticed all the gifs I've been posting of things exploding.
A couple weeks ago I decided that I wanted to be able to simulate sand for use in partical effects. Now, after a ton of fiddling with openGL, I've got it working. I thought I'd write a summary of how it works, not just to help others who might be thinking of doing a similar thing, but also to clarify in my own head exactly what monstrosity I've created.
The majority of the logic runs entirely on the GPU, which is fantastic, because that thing is fast as hell, but there are some parts of any physics system that can't be run in parallel. To get around this, we perform five steps in sequence, each one a parallel computation.
All the forces on the pixels are processed here. This is things like adding speed for explosions and applying gravity. Each force is represented by a shader, and each force shader is applied to the speed map to update the speed of each pixel. How is the speed of each pixel represented you might ask? Well, the speed map is another image load of pixel data that overlays the image, and the speed of each pixel in the image is determined by the colour of that same pixel in the speed map.
The more red a pixel is, the more speed it has in the x axis, while green represents speed in the y axis.
There is an issue here already though, as a pixel only has 256 possible values for each of its r,g,b and a values. Because of this, we can't have negative colours, and we also lose some granularity in the speeds we can have. To get around this, each pixel on the speed map has a base red and green value of 0.5, or 128, and any value above that represents a positive speed, while any below represents a negative speed.
The speed is also represented as a fraction of the overall "max speed" defined in the pixel particle canvas. A low max speed restrains how fast the particles can move, obviously, but a really high max speed will create a cut off on how slow particles can move, as really low speeds will get rounded to 0.
Once the speeds have been updated, it's onto translating them into movements.
We can't just apply the speeds directly to the pixels of the image for a number of reasons. One of these reasons is that pixels in an image must be at an integer position, but we want our particles to move smoothly. To get around this, we have the move map, which essentially just records how much each pixel has been acted on by its speed in previous steps.
Just like the speed map, this is represented through the red and green values of its pixels. After we've got the move map updated, we can finally start getting some movement done.
We're not actually going to make any alterations to the image map right now though, because first we have to figure out exactly what movements are going to happen. Each pixel looks at its move map, and if it's got enough accumulated movement, it draws onto the force map exactly which direction it is moving in.
It's a little hard to see, but each of those purple/cyan pixels is a pixel recording that it will be making a movement in that step.
We could probably actually skip this step and have it be a part of the Move update, but its a little neater to have it like this, even if it does slow down the algorithm a little bit.
This is when it gets really interesting.
Getting the pixels to move might sound simple, but there are a couple things that make it hard.
Firstly, "moving" a pixel is impossible, we can only duplicate a pixel and delete the original.
Secondly, a pixel being processed can not edit the colour values of any other pixels in the image.
If that second point didnāt make a huge amount of sense, remember that we're doing each step completely in parallel, so if we were to edit the colour of another pixel other than the pixel we are currently processing, that would break the parallelism.
To get around this, we do something painful, but necessary. Every empty pixel does a scan of the immediately adjacent pixels, and if it finds a pixel that is signalling that it wants to move into its space, it copies the pixel into its space, making the same copies in the move map and speed map.
It is very important that only empty pixels are allowed to do this, as this is where our collision logic comes from. If a space is occupied, it is impossible for another pixel to enter that space in that step. Even if that pixel is itself moving, we still don't want to move another pixel into its space, as we don't know whether the movement is going to get blocked by another collision.
There is more to the collision system than just blocking movement however. Colliding particles transfer some of the speed to the particle they are colliding with, as can be seen in the gif below.
Without this logic, you can get some really weird behaviour with opposing particles forming solid walls in midair as they try to move past each other. We implement this simply by letting each filled pixel also do a scan of its surrounding area, but only move some of the speed across and leave the colour behind.
BUT WAIT, what if we move the speed across but then in the same step the pixel we're moving it across to itself moves? Remember that we're doing it all in parallel, so the speed we copy for each moving pixel is the speed that we started with at the beginning of the step.
We can fix that in the next, and final, step
All that's left to do is delete the original copies of each pixel that we duplicated, and handle that last speed moving case I just mentioned.
Deletion is also kind of painful, as it involves another scan. During the move step, we also leave a signal on the space the pixel moves into that records exactly which space that pixel came from. You can see these signals as little purple/cyan dots in the following gif.
Each filled space does a scan of the surrounding spaces, and if it finds a delete signal pointing to itself, it deletes. These signals also serve another purpose however in solving the problem we have with moving speeds over correctly for collided pixels. Each pixel that moved this step uses its delete signal to find out where it moved from, and updates its own speed to match the old tile. This catches all the changes that were made in the move step.
And all that goes on each step of the simulation, sometimes with multiple steps per frame. I skimped on some of the details, but hopefully the overall picture made sense. If you want to see exactly how I implemented it in the code, I've uploaded it all to github in the repository below.
https://github.com/Cowinatub/pixelparticles
If you are a Lƶve user yourself, feel free to use the code for whatever you want, including as an example of bad practices in lua, but be warned that my comments are sparse at best. I don't plan to stop working on this yet though, so I'll write more rigorous comments and documentation, if people are interested.