Sign in to follow this  
Geno the Great

OpenGL particle engine issues

Recommended Posts

Geno the Great    180
Well, I've finally moved from SDL to OpenGL (Using SDL to create the window and get input, OGL for all drawing), and as you can imagine, I'm quite impressed by the efficiency. I had it drawing thousands and thousands of particles (Using GL_POINTS) at a smooth 100 FPS, which SDL could never dream of. However, my question isn't related to graphics at all. Rather, vectors. The problem I have is that in the particle engine, it keeps a vector of sParticle structs, which contain X, Y, RGB, timeout and velocity values, etc. I decided to use a vector since the number of particles on screen at once is unknown, and I need access to any element in the vector at any time (So stacks/queues wouldn't work) When a particle is off the screen, or it's time is up, it should be removed from the vector. I do this by finding the index of the particle, iterating to it, deleting it, and exiting the loop. Thus, you should see the problem: Only one particle can be removed from the vector per loop, so only one can be removed per frame, because if I didn't exit the loop, all the indexes would be messed up. (As in, if I removed particles.at(100), and then tried to remove particles.at(101) without finding the new index of the element that used to be at 101, I'd remove a particle that I didn't want to remove) In short, the issue is that with a small amount of particles on the screen, the one-per-frame method is fine. But when it starts adding loads of particles per loop, the system simply cannot keep up with all the particles it needs to remove, so the array bloats and the whole thing bogs down. The solutions I have thought of would be to create a list of the particles to be removed, arrange it in numerical order by index, and then remove all them via vector.remove(start, end), but the ordering of the list would take a lot of CPU time, and obviously a bunch of particles on the screen do not lend well to being in perfect order to remove. The other solution is to give them all a unique ID number, and then once I remove a particle, look for the next one by it's ID number, etc. Again, that would take insane amounts of CPU time. Are there better data structures to use? I'm pretty open to suggestions at the time, since my code is rather short and I'm not in the middle of any serious project.

Share this post


Link to post
Share on other sites
xEricx    572
I'm not sure you really want to remove the particle, what if the camera rotates the frame after?

What I'd recommend is simply to flag the particles you don't want to render, and simply, don't render them :)

If you need more ideas, feel free to ask, but I'm pretty sure with this simple trick you'll be able to come up with a viable solution, and no more limit / frame ;)

Cheers

Eric

Share this post


Link to post
Share on other sites
yckx    1298
Set the vector's size to the maximum number of particles you will allow from an emitter. Instead of adding and removing particles from the vector, give the particles an is_live flag. When a particle dies, set its is_lave flag to false. Then just check for dead particles when you iterate through the container, and don't process them. When you need to add new particles, iterate through the container and reuse the first X dead particles you find, where X is the number of particles to add. Just re-initialize them. You can even add new particles and process live ones in the same loop.

Share this post


Link to post
Share on other sites
tolaris    288
Quote:
Original post by yckx
Set the vector's size to the maximum number of particles you will allow from an emitter. Instead of adding and removing particles from the vector, give the particles an is_live flag. When a particle dies, set its is_lave flag to false. Then just check for dead particles when you iterate through the container, and don't process them. When you need to add new particles, iterate through the container and reuse the first X dead particles you find, where X is the number of particles to add. Just re-initialize them. You can even add new particles and process live ones in the same loop.

As posible modification to that, have a collection (vector, stack or something along these lines) where you push reference to each particle that dies. Then, when you need to reuse a dead particle in main list, rather than iterate through the list in search of one just pop back the info on latest dead particle from the stack of dead particles and use it. When the stack of dead things is/becomes empty you can just add new particles to the end of main list.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
You can use the remove_if function to what you want:


bool isDead(const particle &P)
{
//return true if the particle is dead.
}

myVector.erase(remove_if(myVector.begin(),myVector.end(),isDead),myVector.end());



Now it only takes 1 pass to remove all dead particles and to add a new particle you just need to call push_back() (you'lll want to check that the vector won't need to be resized before you call push_back though).

Share this post


Link to post
Share on other sites
Doggan    528
Quote:
Original post by tolaris
Quote:
Original post by yckx
Set the vector's size to the maximum number of particles you will allow from an emitter. Instead of adding and removing particles from the vector, give the particles an is_live flag. When a particle dies, set its is_lave flag to false. Then just check for dead particles when you iterate through the container, and don't process them. When you need to add new particles, iterate through the container and reuse the first X dead particles you find, where X is the number of particles to add. Just re-initialize them. You can even add new particles and process live ones in the same loop.

As posible modification to that, have a collection (vector, stack or something along these lines) where you push reference to each particle that dies. Then, when you need to reuse a dead particle in main list, rather than iterate through the list in search of one just pop back the info on latest dead particle from the stack of dead particles and use it. When the stack of dead things is/becomes empty you can just add new particles to the end of main list.


To elaborate on this... I recently implemented a particle engine. You have a liveList, and a deadList. Each frame, you go through and render every particle in your live list. If the particle's life is over, or it's out of the bounding box, you remove it from the liveList and add it to the deadList. Then, once per frame you can go through every particle in the deadList and give it new properties, and add it to the live list. All you do is pass the pointer back and forth between the live and dead lists - no new memory allocation needs to be done after initializiation.

Also, using a vector for this purpose is not a good idea. Use a list. You will be constantly removing items from random spots in your liveList, and vectors were not meant for this, whereas linked lists are.

Share this post


Link to post
Share on other sites
Nitage    1107
Quote:
Original post by Doggan
Quote:
Original post by tolaris
Quote:
Original post by yckx
Set the vector's size to the maximum number of particles you will allow from an emitter. Instead of adding and removing particles from the vector, give the particles an is_live flag. When a particle dies, set its is_lave flag to false. Then just check for dead particles when you iterate through the container, and don't process them. When you need to add new particles, iterate through the container and reuse the first X dead particles you find, where X is the number of particles to add. Just re-initialize them. You can even add new particles and process live ones in the same loop.

As posible modification to that, have a collection (vector, stack or something along these lines) where you push reference to each particle that dies. Then, when you need to reuse a dead particle in main list, rather than iterate through the list in search of one just pop back the info on latest dead particle from the stack of dead particles and use it. When the stack of dead things is/becomes empty you can just add new particles to the end of main list.


To elaborate on this... I recently implemented a particle engine. You have a liveList, and a deadList. Each frame, you go through and render every particle in your live list. If the particle's life is over, or it's out of the bounding box, you remove it from the liveList and add it to the deadList. Then, once per frame you can go through every particle in the deadList and give it new properties, and add it to the live list. All you do is pass the pointer back and forth between the live and dead lists - no new memory allocation needs to be done after initializiation.

Also, using a vector for this purpose is not a good idea. Use a list. You will be constantly removing items from random spots in your liveList, and vectors were not meant for this, whereas linked lists are.


NO! You should use a vector or array for a aprticle system and you should ensure that the vector NEVER resizes.

For a vector:
Call reserve() with the max number of particles you can have.

Now make your system in some way reject a call to add a new particle when the array is full.

Now to erase all particles that are dead you simply copy the last particle in the vector over the dead particle and resize (the size of allocated memory does not change) to size()-1. This operation doesn't invalidate the iterators, so you can do it in one pass.

So:

This system never allocates memory (which causes huge slowdown).
The memory used is contiguous, so you'll probably gain benefits from it being cached.
If you design your particle class carefully you can use the vector as a vertex buffer.
Insertions are constant time.
Deletions are constant time.


Finally, for Doggan - DELETION IS ONLY QUICKER IN A LINKED LIST IF YOU NEED TO PRESERVE THE ORDER OF ELEMENTS.

Share this post


Link to post
Share on other sites
CyberFox    198
I would toss out the canned storage structure all together and write your own linked list for the particles. Why, because it allows you to have complete control over the system and results in far cleaner code. So when you update the particles you start at the beginning and loop through them, when you reach a dead one you unlink and delete it. If your not accustom to linked lists then this can be a bit challenging at first, and null pointer errors can really frustrate you. However if you just keep it simple and logically follow your code you can usually spot these errors with relative ease. If you feel up to it that is what I recommend you do.

*edit* in response to above, I disagree (thought I may not be understanding correctly). A deletion from an array leaves a blank that you must fill. So you must actually copy data into that blank. In a linked list implementation you simply edit a couple of pointers.

Share this post


Link to post
Share on other sites
tolaris    288
Quote:
Original post by CyberFox
*edit* in response to above, I disagree (thought I may not be understanding correctly). A deletion from an array leaves a blank that you must fill.

What was suggested is actually, 'deletion' from the array leaves a clearly marked 'dead' particle which you simply _skip_ as you iterate through the collection. This is not really different than checking for dead particles as you iterate through the linked list, except you don't stop to delete the dead particle, fix the pointers etc but simply move on to the next particle.

(although i suppose if someone was determined to keep their collection contiguous, they could copy the data from last particle in the collection there, and take note the actual set of live particles is now 1 unit less)

Share this post


Link to post
Share on other sites
Nitage    1107
Quote:

(although i suppose if someone was determined to keep their collection contiguous, they could copy the data from last particle in the collection there, and take note the actual set of live particles is now 1 unit less)


Exactly. Deletion from an array/vector in which order is unimportant requires exactly 1 call of the element's copy constructor and a decrement of the array/vector size.


Deletion from a list is (usually) more expensive. It requires pointer manipulation AND (the expensive part) a memory deallocation (the only case where it is less expensive is when the copy constructor is more expensive than memory deallocation - this can happen, but not for classes as simple as particles).

The vector/array approach also guarantees that the particles are stored in a single memory block.

A well implemented array based particle system will out perform a linked list implementation - no question.

My first particle system (which was pretty näive) used new for every added particle and delete for every dead particle. My optimised version used a vector of particles and the techniques I've described and is capable of rendering between 10-100 times as many particles in the same time (depending on the number of state changes etc).



Share this post


Link to post
Share on other sites
Doggan    528
Quote:
Original post by Nitage
Finally, for Doggan - DELETION IS ONLY QUICKER IN A LINKED LIST IF YOU NEED TO PRESERVE THE ORDER OF ELEMENTS.


Nitage - We are describing 2 different approaches to the same problem. In my original post, I quoted a previous post that suggested an is_live flag. This would be wasteful as you iterate through the entire list each time checking this flag. So, I suggested the 2 list approach. Using THAT approach, a vector would be horribly inefficient because order IS important and you are constantly removing items from the middle of the vector. Hence, I suggested a linked list.

As to which approach is better?

Quote:
Original post by Nitage
So:

1. This system never allocates memory (which causes huge slowdown).
2. The memory used is contiguous, so you'll probably gain benefits from it being cached.
3. If you design your particle class carefully you can use the vector as a vertex buffer.
4. Insertions are constant time.
5. Deletions are constant time.


1. My system doesn't either (except at initialization obviously). Both my liveList and deadList contain pointers to Particle objects.
2. You win.
3. True you can't use my lists as vertex buffers, but I was able to achieve this with a few modifications quite easily :)
4. Tie.
5. Tie.

I would argue that my system seems a little more intuitive, but I will leave it at that. I would also argue that neither system is the most ideal approach to the problem, but the basic theory of both concepts is probably useful to the original poster, so we both win ;)

Share this post


Link to post
Share on other sites
Nitage    1107
Quote:

Quote:
Original post by Nitage
1. This system never allocates memory (which causes huge slowdown).

1. My system doesn't either (except at initialization obviously). Both my liveList and deadList contain pointers to Particle objects.


Careful. Each node in your linked list will require 3 pointers (next, previous from std::list and the pointer to your particle). These have to be stored somewhere. A std::list implementaton may keep a cache aound to store these, but it has to be allocated at some point and you have no control over when it is, or when/if it grows.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this