OpenGL particle engine issues
Author
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.
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
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
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.
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.
You can use the remove_if function to what you want:
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).
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).
Quote:Original post by tolarisQuote: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.
Quote:Original post by DogganQuote:Original post by tolarisQuote: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.
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.
*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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
