[In this reprinted #altdevblogaday in-depth piece, BitSquid co-founder Niklas Frykholm discusses his team's recent hack day, and his project in which he rewrote the collision algorithm for the studio's particle systems.] Last Friday, we had our second hack day (a.k.a. do-what-you-want day, a.k.a. Google day) at the office. Different companies seem to take different approaches to hack days. At some places it just means that you can spend a certain percentage of your working week on your own projects. We wanted something that was a bit more focused and felt more like a special event, so we used the following approach:
People were encouraged to pick tasks that could be completed, or taken to a "proof-of-concept" level in a single day. The goal was that at the end of the day you should have something interesting to show/tell your colleagues.
It is ok to fail of course. Failure is often interesting. Trying crazy ideas with a significant risk of spectacular failure is part of the charm of a hack day.
A couple of days before the event, everybody presented their projects. The idea was to get everybody to start thinking about the topics, so that we could help each other with ideas and suggestions.
We ate breakfast together in the morning to start the discussions and get everybody in the spirit of the event. At the end of the day, we rounded off with a couple of beers.
We avoided Skype, email and meetings during the day, so that we could focus 100 percent on the projects.
A couple of days after the events, we had a small show and tell, where everybody could present what they had learned.
Results
A number of interesting projects came out of this hack day:
Tobias and Mats created an improved highlighting system for indicating selected objects in the level editor. (Highlighting the OOBB works well for small objects, but for big things like landscapes and sub-levels, it is just confusing.)
Jim looked into a cross-platform solution for capturing screen shots and videos on target machines and transmitting them over the network.
Andreas created a Lua profiling tool, that can dynamically enable and disable profiling for any Lua function by hot-patching the code with profiler calls.
Finally, I rewrote the collision algorithm for our particle systems.
Being an egotistical bastard, I will focus on my own project. Particle collision is one of those annoying things that it is difficult to find a good general solution to, for two reasons:
It ties together two completely different systems (particles and physics), creating an ugly coupling between them. Since the solution must have decent performance, the coupling must be done at a fairly low-level, which makes it even worse.
Particles can have very different collision requirements. Some effects need a massive amount of particles (e. g., sparks), but don't care that much about collision quality. As long as most of them bounce somewhat accurately, it is OK. Other effects may have just a single particle (e. g., a bullet casing). Performance doesn't matter at all, but if it doesn't bounce right you will surely notice. Handling both effects in the same system is a challenge. Having different systems for different effects is another kind of challenge.
My previous attempts at implementing particle collision have all been based on first cutting out a slice of the physics world around the particle effect and then trying to find a fast representation of the collision shapes in that world slice. The problem with this approach is that there are a lot of variables to tweak and tune:
How big should the world slice be?
How much detail should there be in the simplified representation? More detail is slower, but gives better collision results.
What kind of representation should we use?
How should we handle dynamic/moving objects? How often should the world slice be updated?
I've tried a lot of different representations: a triangle soup, a collection of half-spheres, a height field, but none of them has given completely satisfactory results. Often, parameters that work for one effect at one location fail for a different effect at a different location. Both performance and behavior are hard to predict. The main idea for the new approach came from a Naughty Dog presentation at GDC. Instead of trying to create a shared collision model for all particles, we give each particle its own collision model, and we store it inside the particle itself, together with the other particle data. Of course, it would be expensive to store a complicated collision model inside every particle, so we use the simplest model possible: a plane. We can represent that by a normal and an offset from origin. So with this approach, the data for a particle might look something like this:
struct Particle {
Vector3 position;
Vector3 velocity;
Color8 color;
Vector3 collision_plane_normal;
float collision_plane_offset;
};(Side note: Our particle data doesn't actually look like this, we use a "structure-of-arrays" approach rather than an "array-of-structures" and we don't have a fixed set of fields, each effect has its own set.) Note that we don't bother with any flag for indicating whether there is plane or not. If there is no collision, we just put the collision plane far enough below the origin. With this approach the collision test is super fast — just a dot product and a compare. It is also really easy to parallelize the test or run it off-CPU, since it just uses local particle data and doesn't need to access any shared memory. With this method we have divided the original collision problem into two simpler ones:
No tags.
