Particle System

Recently I have been working intermittently on a particle system. I was inspired by a screenshot of Unreal Tournament 2004 in which a rocket had been launched at a jeep and a very beautiful smoke trail was left behind. I thought to myself what better way to spend a bit a spare time than working on cool smoke trails. So I began coding starting with a simple GLUT application with nothing going on.

Hmmm… How do I render the smoke? I have written an elementary point particle system in the past and wanted to step it up a notch now that I am more experienced. Also it would take a ton of point particles to make the smoke cloud look realistic and not grainy. Time to hit google and see what’s out there. The first thing I searched for was “point sprite” since I had heard that buzz word several times and was curious to see if it would be helpful or not. Low and behold it looks promising, uses ARB_point_sprite [oss.sgi.com] or NV_point_sprite [oss.sgi.com] in OpenGL and draws a texture mapped, screen aligned Quad with only a bound texture and one vertex; efficiency at its best. Well I knew about using actual texture mapped Quads and decided that it would be best left to the hardware to do the billboarding (screen aligning).

A couple of minutes passed and I had a horribly ugly “smoke” texture for my sprite using the spray can in paint. And a day or so later I had a much improved smoke texture flying around the screen leaving a trail of increasingly transparent copies. From here I added a particle depth sort to remove blending artifacts, disabled depth buffer writing during particle rendering and tested the smoke trails with actual 3D objects in the scene (particles are drawn last). There is unnatural “cutting” when the smoke passes through the objects but that is to be expected with flat particles in a 3D scene. Things to look into include cleaning up the “cutting” and trying out a slick idea from Mark Kilgard of NVidia for rotation of the smoke texture. (Since rotation transformations don’t affect the resulting point sprites). I will likely go into more detail later since I want to compare two techniques for point sprite rotation.

At this point I decided that I wanted to create the standard spark fountain using my particle engine. However, it turned out that I had written myself into a bit of a corner and I didn’t really have a particle system at all, only a static smoke tail that wouldn’t scale. Ooops! back to the drawing board. I then defined all my needed data and realized how ugly it all was when put together. Firstly I was using static particle arrays and the dynamic nature of particle life times just wouldn’t stand for that type of constraint so a linked list is necessary. Secondly now that I am settled on a linked list how do I depth sort my particles for proper alpha blending? Sitting back I came up with the system outlined in the figure below.

I use C so I needed my particle system to be able to house different types and different groups of particles that could be handled separately by the library functions and by the user. This led to the Root set and the linked list of particle sets across the top. Next I added in my linked list of particles in each set. I figured that doing an insertion sort every frame is probably not the greatest idea and I really wanted to use the qsort() function some how. This led me to create the Link Sorter array. It is simply an array of pointers to the list elements so that you can directly index each. This list is maintained by adding in the references at the end and setting the dead particles reference to NULL. Now we can qsort the link sorter based on the distance value in the particle structure and when finished update the next pointers of each list item.

The other thing I wanted to avoid was a high amount of malloc() and free() calls so when a particle dies I throw the structure onto the free list and then take from there when I need a new one. With the link sorter I make sure that it grows in increments to reduce the number of times that realloc() is needed to be called.

I have yet to implement this idea but I think it is sound and will probably result in a very fast software particle system. I specify software because one very ambition researcher came up with this [www.2ld.de] very intriguing paper about using the GPU to do all the particle work. Its a good read if this topic interests you. Doing particles in software today causes a bottle neck on the vertex pipeline of the graphics card. Generally the vertex pipeline is much thinner than the fragment (pixel) pipeline which results in fewer vertices per second transfer. If you are not sure what a pipeline is then you can think of it as a link between one processor and another. In our case the cpu and the vertex processor. Newer cards have multiple pipelines that operate in parallel to transfer the data. So when you are doing a software particle system with 10000 particles its like drawing a model with 10000 vertices or ~15000 triangles (yikes).

I love the smell of particle simulated napalm in the late evening / early morning :o)