Particle data structure

Particles are usually some kind of simple structs stored in an array. Then every frame vertex buffer is filled using that array. You really don’t want to sort them (at least not all particles and sometimes sorted particles don’t look good). You need also to retain insertion order to prevent particle popping. Using simple array and replacing deleted element with the last one isn’t a good idea.

Straightforward solution is to use circular buffer. This has some issues – if particles have no uniform lifetime it needs some checks in order to detect dead particles when filling the vertex buffer. There will be also some holes in the circular buffer, so memory won’t be used effectively.

Another solution is to use array and defragment it every frame. This means no conditional statements, but could lead to a lot of memory copying (depending on the lifetime of particles).

The interesting thing is that above methods can be combined. Third method uses an assumption that in case of the defragmented array You usually remove particles from the beginning and add to the end. So why not just have large array and two floating pointers for marking begin and end of particle data. Now when You add something – increase end pointer. When You remove an element – increase begin pointer. In case of removal from the middle of data – defragment by shifting data from left or right. When end pointer can’t be increased just defragment by copying data to the beginning of the array. This doesn’t change the worst case – removal from the array middle, but should greatly speed up the average case.

Advertisements
This entry was posted in Graphics. Bookmark the permalink.

3 Responses to Particle data structure

  1. Hi there, few more ideas:

    (1) Instead of defragmenting whole array at once, do it gradually over multiple frames; maintain current “defragmentation pointer” and move it forward every frame by specific number; when reached the end, start again from the beginning.

    (2) Don't defragment at all and instead use freelist (http://en.wikipedia.org/wiki/Free_list) to allocate and free slots for particles; particles that are already being displayed won't change their ordering, so it's just the new ones that might suddenly pop on top other ones – but in real-life this often won't matter; the downside is that the iteration takes longer now.

    Like

  2. KriS says:

    (1) Yes, gradual defragmention looks like a good idea. Worth checking for next iteration of our (FWH) engine.

    (2) Linked list for particles sounds hardcore :). I don't think it's a good idea to iterate through linked list every frame.

    Like

  3. Re (2): You don't need to do that. Linked list in a freelist is only used to store unused elements. To iterate over all used freelist elements you may use an additional usage array (e.g. 1-bit per element: 0-unused 1-used). So, the good thing is that iteration is still cache friendly. But the main disadvantage here is you have to visit ~all elements to check their usage bit even when there's very few of them actually used – yep, it's just as bad as pessimistic case of iterating over all elements. You may use some tricks to speed it up by checking multiple 32-bits at once etc.

    Anyway, that's what I meant by longer iteration times. I don't mean it's perfect, but it might be a good choice in certain scenarios.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s