I'm writing a simple explosion particle system for a game I'm working on and I'm wondering if the way I'm doing it is efficient.

Currently, I have a class called Explosion which contains an array of instances of a class called Particle. It's a fixed size array which is initialised when the Explosion is created to the maximum number of particles for that system. When each Particle instance is created its attributes (life, colour, velocity, etc.) are modified via stochastic modifiers to create a more organic feel to the explosion.

Every Update() I cycle through the array of particles and emit them (by setting their life > 0) and update them as nescessary.

What I'm wondering is if the way I'm rendering them is particularly efficient. Currently, at the beginning of each Render() I'm creating a linked list of VertexPositionColor elements using List<VertexPositionColor>. I then cycle through every particle in the array and if it's life is greater than zero (ie, it's active) I create a new VertexPositionColor using the particle's position and colour variables and add it to the linked list. Once I've cycled through the entire array I then have a vertex buffer which I pass into DrawUserPrimitives to render.

There's two reasons why I'm worried about the above method. Firstly, because I'm using a linked list rather than a fixed size array I'm going to be fragmenting memory, which isn't particularly efficient (but I could simple change this to be a fixed size array to fix this). But secondly, and more importantly, I'm worried that I'm passing a lot of memory around every frame by clearing and setting a brand new frame buffer each frame which has got to be slow.

I thought I had a good solution in that I was going to create my Particle class using VertexPositionColor as the base class. Then, I could just create a fixed size array of Particle objects and it would already inherit from a supported vertex type which I could pass into DrawUserPrimitives.... but obviously this wont work as VertexPositionColor is a struct. It sounded great in my head, though ;)

Another solution I thought of was to store an instance of VertexPositionColor inside each Particle for it's position and colour and then have a separate fixed size array of pointers to VertexPositionColor elements, which would actually exist inside each Particle instance... but obviously this isn't C++ and once again I'm irritated by the limitations of C# ;)

Anyway, there's got to be a better method and I'm hoping someone can give me some pointers (pun wholly intended). I did spot the particle system example in the education catalogue but from a quick look it seems a bit over-complicated for my needs. For a start I don't want/need to use point sprites. Just a simple VertexPositionColor vertex buffer will do.

Define "efficient".

If you are serious about wanting the most efficient particle system possible, you should use something along the lines of our 3D Particle sample. Use point sprites, and do the particle animation on the GPU. This will be an order of magnitude faster than the way you are doing it.

But, if your approach is working for you (ie. you can draw enough particles with a good enough framerate, and still have enough CPU left for whatever other work you need to do) then that's a fine way to go too.

In this instance I'm afraid you have to choose between simplicity and performance  :-)

SM, I used to create particles in the way you talk about but the 3D Particle Sample code is much faster at rendering and won't result in the amount of garbage you are going to see with the method you are using.  You also get the benefit of automatic camera facing with sprites (they always face the camera.)

If you are bent on using your method I'd suggest not using a linked list but rather create a fixed vertex buffer and just pass in the appropriate length to your render call (sort all of the active particles to the front of the buffer.)  This is how I did it and it did the job of not creating garbage.  Total performance won't compare to the method used in the education sample but it will be garbage lite.

List<T> isn't a linked list!

Or, you could do it all on the GPU... http://www.catalinzima.com/?page_id=97

PaulCunningham:

List<T> isn't a linked list!

Yeah, I know. I think I just see "list" and automatically stick "linked" on the front ;)

Thanks for your help, everyone. I think it would probably be best if I just use the particle system sample.

I was searching through these forums after I posted last night and completely forgot I'd asked a similar question before. It's pretty bad that it was only a year ago but I can't remember what I actually ended up doing.

Just another quick question.

I'm looking at the 3D particle system and the shader seems to be set up to only use point sprites. I don't need point sprites at all. Is it possible to change this to draw primitives rather than point sprites?

Sorry if it's a stupid question. I've never really done anything with shaders before.

Ideally, I'd be after about 15,000 particles on screen comfortably and I can't see that happening with point sprites.

EDIT: Plus, I'd like to point out that even if it would work with point sprites I don't actually need anything fancy so point sprites seem a bit over the top. If I did end up using point sprites, to get the effect I want I'd just end up using a small square or round texture for each particle.

Looks like Catalin Zima's site renders the article pretty badly. You can check out the original particles via GPU as well as several other topics Catalin has written about focusing on vertex textures here: http://www.ziggyware.com/readarticle.php?article_id=127

Point sprites are fast on current hardware, including the Xbox. Whether you use point sprites or other primitives doesn't really matter, because all good particle systems are fill rate limited.
You'll have a really hard time getting to 15,000 particles on the CPU on Xbox, even if you use the most optimized particle system CPU code possible (which means using a ParticleVertex[, updating the array in-place, and using SetData<> on a dynamic vertex buffer each frame).

SuburbanMonkey:

I don't need point sprites at all. Is it possible to change this to draw primitives rather than point sprites?

Possible, sure, but it would be more complex and run slower. To draw using triangles, for instance, you would have to create three vertices per particle, rather than just one, and include an extra channel of data to tell the shader which corner it is currently processing, then add some computations in the vertex shader to adjust the particle position accordingly. This would also require you to run the vertex shader three times per particle, rather than just once.

SuburbanMonkey:

Ideally, I'd be after about 15,000 particles on screen comfortably and I can't see that happening with point sprites.

Why not? I think you are under the misapprehension that point sprites are somehow complicated. They aren't: in fact they are the simplest and most efficient way to render a particle system.

Don't know if this will help but there is an article on my site focusing on point sprites that may be of use: http://www.ziggyware.com/readarticle.php?article_id=223

once you realise that the particles in an explosion all share (roughly) the same lifetime and the same start position

you can:

- use a static vertex buffer
- each particle can be defined as a direction and some other parameters to vary its behaviour
- no updating of data is required
- just calculate everything from ElapsedTime

this same system can be used with a circular dynamic vertex buffer
for individual particles that have similar durations but different lifetimes (ie: bullets)

very interesting / complex movements can be constructed using simple trigonmetric / exponential functions
for instance smoke is just a straight line combined with a circle

this approach also has another useful side effect:

the cpu can "guess" the exact location of any particle
because it has all the information it needs: start position, parameters, elapsedtime

furthermore collision detection can (sometimes) be done backwards - because you know the trajectory of the particle
you know in advance what it will collide with

this technique is very efficient and can run millions of particles

in the case of explosions this technique allows you to have thousands of simultaneous explosions all using the same vertex buffer
just with different elapsedTimes passed in ...

Shawn Hargreaves:

I think you are under the misapprehension that point sprites are somehow complicated. They aren't: in fact they are the simplest and most efficient way to render a particle system.

I think you're probably right.

When I said primitives, though, I was referring to points, rather than triangles. I think I probably used the wrong terminology.

As I said before, though, if I do end up using point sprites I'll just use a small square or round texture to get the effect that I'm after. In which case, I can achieve this effect without using textures at all. Rendering each particle as a point rather than a point sprite would produce exactly the same effect so surely using point sprites would be overkill?

Now I'm back from work I'm going to try and modify the particle system example to ignore the texture element and just render a simple point instead.

Ok, I understand your confusion now.

There is no difference between a "point" and a "point sprite". The basic types of primitive supported by the GPU are:

• Triangles
• Lines
• Point sprites

Ah, ok. So is the PrimitiveType enum for CPU only?

EDIT: Forget I said that. For some reason I thought there were separate elements for points and point sprites in that enum...

For my particles I have:

Particle Class - with postion, velocity, color, etc.

ParticleSystem Class - has an array of particles

Basically, the same as yours, except each Particle and ParticleSystem has a bool "active" flag. During Update() and Render() only active ParticleSystems are considered, and only active Particles in a ParticleSystem are considered. Simpler imho, and less garbage prone because:

- There is no need to create a list of what needs to be updated or rendered, just iterate through all objects and draw/update active ones

- There is no need to create or delete anything. To destroy something in game flag it as inactive. To create something in game find an inactive one and active it.

- Your memory is fixed and re-used, which can give the benefits of Locality of Reference: http://en.wikipedia.org/wiki/Locality_of_reference

I'd use a particle struct, not class, if improving locality of reference and adding additional dereference instructions was really important.
In fact, that is what I do in my CPU-side particle system :-)

Shawn Hargreaves:

Ok, I understand your confusion now.

There is no difference between a "point" and a "point sprite". The basic types of primitive supported by the GPU are:

• Triangles
• Lines
• Point sprites

I thought there was FillMode.Point as well ?

that renders each vertex as a pixel

jwatte:

I'd use a particle struct, not class, if improving locality of reference and adding additional dereference instructions was really important.
In fact, that is what I do in my CPU-side particle system :-)

Hmm really? Wasn't aware struct would give better performance. I'll give it a try. My particle systems are forced to be CPU bound because I must control them every frame.

Fippy Darkpaw:

jwatte:

I'd use a particle struct, not class, if improving locality of reference and adding additional dereference instructions was really important.
In fact, that is what I do in my CPU-side particle system :-)

Hmm really? Wasn't aware struct would give better performance. I'll give it a try. My particle systems are forced to be CPU bound because I must control them every frame.

On a Windows machine you won't see a massive difference, but on the XBox using a reference type for particles is a really bad idea. Because of the way the garbage collector works on the 360, instantiating thousands of reference types is going to slow down garbage collection even if they're not being collected.

I have a pretty efficient CPU based particle system that I've been evolving since the first days of XNA. It can update and render around 150,000 particles before it starts slowing down. If you're interested in taking a look at the code I'll upload it to codeplex later today :)

Ok. I've started porting my particle system onto the GPU. Essentially creating my own vertex type for the particle and then storing all the variables for the particle in the vertex type for processing by the shader. I'm assuming this is the right way to do it? Effectively, what's happened is that my Particle class has now become a Particle struct which is a vertex type (much like ParticleVertex is in the 3D example).

The difference between my particle system and the 3D sample is that my particles have a variable life so I can't do the circular list thing. The way I did this on the CPU side in C++ is when I created my emitter, I gave it a maximum number of particles. I would then create a fixed array of Particle object instances of this size. I also had a linked list of pointers to elements in this array for the particles which were currently active.

Each update I would cycle through the linked list of active particles, updating them and removing the ones that had died. Then I would calculate how many new particles needed to be emit this frame and cycle through the array of particles adding pointers to them to the linked list. This meant that when rendering in OpenGL I could just do a glBegin(GL_POINTS) and then cycle through this linked list calling say glAddVertex3f(activeParticles[i]->GetX(), activeParticles[i]->GetY(), activeParticles[i]->GetZ()); or something similar.

I can't really do the above method in C# because the Particle type is now a struct so it can be used for the vertices. Also, I want to create a dynamic vertex buffer whos elements in the array are the same indexes as the elements in my particle array, as was done in the 3D particle system example.

So what I'm going to have to do is create the entire particle array on initialisation and create the dynamic vertex buffer of the size of the array. What I'm worried about, however, is because my particles have a variable life, I'm going to have to cycle through the entire array each frame to emit the new particles (which will require a lot of individual calls to SetData() on the dynamic vertex buffer as the inactive particles wont nescessarily be together) but I'll also have to cycle through the entire array on render too and just call DrawPrimitives() on the ones that are active. This all seems a bit wasteful to me. Especially the individual calls to SetData() as I believe this will be slow, right?

Any ideas on how I can improve this method?

How "variable" are their lifetimes ?

if they always fall within the same range you can kill them in the vertex shader by drawing them outside of ndc
then use the circular buffer technique as usual.

even if their lifetimes are wildly variable you can split them into 4 approximate lifetime groups: short, medium, long, forever

I am glad to hear your particles are back in the GPU.

Don't forget you can use texture(s) to control individual particles and just use a static vertex buffer to "drive" the shader (using VTF)

You can "draw" new behaviours onto any set of particles you like ...

Also consider using a custom mip map to quickly extract "dead" particles from the texture for presentation to the CPU.

As you can probably tell - I like GPU particle systems.

It all depends on the parameters that the emitter is given as to how much they vary. I have a parameter called life and a parameter called lifeVar, from which a random value is taken and then added onto life.

The problem comes when the particle system has been running for a while and the lives of the particles in the array vary a lot. If I understand your solution to the lifetime variation correctly then the groups would only work if the particles were all spawned at the same time. After the particles have been recyled many times everything becomes jumbled up. For example, I may spawn a particle with a long lifetime but there will be particles in the long group who are due to die soon.

As I said above. I haven't done shaders at all before so this is all very new to me. I'm not using textures per se, by which I mean that I'm not returning with the tex2d function, I'm just returning the colour of the particle. This is simply so I can use coloured points, as that's all I'm needing.

I have to admit, I don't know what you mean by VTF or drawing new behaviours onto particles...

You can keep list of indices, where one list contains indices of "dead" particles, and the other contains indices of "live" particles. Thus, when allocating a new particle, take the first index in the "dead" list. When a particle dies, put it back on the "dead" list. Keep the "live" particle index list as a priority queue, so that you know when the particles will die, and don't have to scan each live particle each frame.

Another trick is to make all particles live long, but have zero size and zero alpha after some time, so that they are not actually visible.

jwatte:

You can keep list of indices...

That's a really good idea. I think I'll do that. Cheers. It wouldn't solve the problem of me having to call SetData() many times, but I was thinking I could optimise this by only calling SetData() when there's a gap in the indices, adding the particles between gaps in one call.