list, vector or deque for particle system demo?

hi all,

i only recently started learning how to work with particle systems and forces via daniel shiffman’s great ‘nature of code’ online syllabus for processing:
http://www.shiffman.net/teaching/nature/
and even more recently started working with OF, which i’m loving so far!

i REALLY want to be able to apply the info in those tutorials to OF as seamlessly as possible. i think a good way to start is to make a version of the simple 2D particle system with OF:
http://www.shiffman.net/itp/classes/nat-…-particles/

i think this could be a great reference for people new to OF and particles/forces but i need some feedback on my plan of attack before starting…

firstly, daniel uses a custom 3D vector class:
http://www.shiffman.net/itp/classes/nat-…-tor3D.java
which i plan to replace with OF’s ofxVec2f class, as i will keep things 2D for now.

i’ll create a particle class with an instance of ofxVec2f for acceleration, velocity and location. a particle_system class will then contain a dynamic array of these particles.

I am not sure what to replace java’s array list with: list, vector or deque
can anyone suggest which would be most appropriate?

any advice greatly appreciated
~nay.

Hi Nay, I personally use linked lists for this. Iterating through them is very fast and easy, and adding/deleting is very quick too. The only downside is its slower for random access (e.g. jump to the 517th item - you need to cycle through them all), but usually you don’t need to do that in particle systems so no problems there.

I’ve actually posted a simple particle system using linked lists (and ofxVec2f) here
http://www.memo.tv/files/memotv/advTexture.zip

though that was to demonstrate another point (more details on this thread)
http://www.openframeworks.cc/forum/view-…-sc&start=0

and you’ll have to change the particle drawing code to use ofImage instead of ofxSprite if you want to get it working…

1 Like

Here’s another design in the Particle Systems API http://www.particlesystems.org/ . It uses std::vector to manage a group of particles and puts objects in the vector instead of pointers to the objects for speed purposes. The lib uses some tricky memory swapping to move dead particles out of the middle of the memory buffer but this is hidden from the user.

i’d use a vector. a linked list would be fine as well, just as long as you use the iterator objects to iterate through the list, rather than manually getting each element (which is what happens when you go myList[index]).

basically

  • a vector is a general list. it’s usually implemented internally as an array. inserting and deleting elements from a vector can take a long time because you have to shuffle the other elements around; but you can get to any element instantly.

  • a linked list is good for things that will only be accessed sequentially, and/or for situations where you need to do a lot of deleting and inserting in the middle of the list.

  • a deque is good for when you want to do most of your access at either the front or the back of the list. strictly speaking, you’re not supposed to be able to access elements in the middle of a list using a deque.

thanks all,

memo, thanks for the code, very helpful for this and other things. will have to revisit that thread link about reusing textures.

damian, thanks for breaking the differences down. even though i am only iterating through for this, i think i will try vectors first as the syntax/implementation is more like what i’m used to, then i might try lists afterwards.

will post my results after i get a chance to implement this next week sometime.

cheers
nay.

alright, so i’m pretty close:
http://renechristen.net/temp/particle-sys.zip

it’s working but i’m confused about initialising the particle system object. i declare ‘ParticleSystem ps;’ in ‘testApp.h’ which forces me to create a particleSystem() constructor with no arguments to compile.

i want to call the constructor with arguments in setup() but it is ignored. is there a way to do this without creating another function to reset the relevant variables?

A solution should be to use pointers…

Declare ps in testApp.h as:

  
  
ParticleSystem * ps;  

That way it won’t be initialized, then in setup

  
  
ps = new ParticleSystem(1, ps_loc)  

and in draw instead of:

  
ps.run();  
ps.addParticle();  

You should use:

  
ps->run();  
ps->addParticle();  

thanks arturo, just uploaded changes

i’m actually trying to avoid using pointers (for this first version), so just added an init() function to be called in setup after the particle sys is declared/initialised in the header.

the other change to this update was separating the update and render functions of the particle system so that calculations are no longer done in draw().

i think this is now the simplest port of this demo i could have made. I was going to make a version next which uses a vector of pointers for particles but otherside mentioned that that other particle API uses a vector of objects instead of pointers to objects for speed. so would there be any performance gain or other benefit in using pointers to particles here?

would there be any performance gain or other benefit in using pointers to particles here?

It depends on the use you make of the vector, if you create more new particles than you read them later, it should be faster to use pointers to particles, if not you are creating the particles twice, one when you create it and then a copy when you insert it in the vector. But then to read them, with particles directly in the vector, you make only one memory read to access them while with pointers, you make two reads, one to read the pointer and another one to the particle itself.

Also perhaps declaring a size for the vetor in the creation will make it a little bit faster, as internally I think it’s based in an array and increasing it size means to recreate the whole array again and again. It should be something like:

particlesVector = vector(2000);

Hi,

Arrays of pointers are very cache inefficient for this sort of memory access pattern.

If you’re going for maximum speed, I’ll second otherside’s suggestion: Allocate a std::vector of particle objects with the maximum number of particles you’re expecting to have. Then at runtime just run through the array and update those particle objects.

This is a form of cache efficient object-pool

You’ll have to be careful about not removing objects from the middle of the array when they’re “dead”. Keep a pointer to the first free object in the array, set a flag to disable them and move on.

This is probably the fastest layout you can get without starting to mess with memory layouts. For instance, for large numbers of small objects, the Structure-of-Arrays-layout-is-much-more-cache-efficient, but a bit more awkward to use.

Further on you, can start looking at leveraging SIMD instructions or offloading some work to the GPU, but these are some pretty hairy optimizations, and you should ask yourself if they’re really worth the extra work and the probable breaking of the structure and portability of your code.

If you’re interested in understanding these issues and getting the best performance out of your C++ code, I heartily recommend Noel Llopis’ C+±for-Game-Programmers

Hope this helps,
P.

If you are using a vector of pointers dont forget to delete them when you are done because vectors wont delete pointers.

  
vector<MyClass*> vec;  
  
   MyClass* p = NULL;  
  
   // Load up the vector with MyClass objects  
   for (int i = 0; i < NUM_OBJECTS; i++) {  
      p = new MyClass( );  
      vec.push_back(p);  
   }  
  
   // Do something useful with this data, then delete the objects when  
   // you're done  
   for (vector<MyClass*>::iterator pObj = vec.begin( );  
        pObj != vec.end( ); ++pObj) {  
      delete *pObj; // Note that this is deleting what pObj points to,  
                    // which is a pointer  
   }  
  
   vec.clear( ); // Purge the contents so no one tries to delete them  
                // again  

ding

ok I’ve been reading and here goes nothing:

Removing objects from the middle of a vector is costly because the vector has to rearrange all the objects by moving them down when erasing but it is no impossible to do it efficiently and there are several methods to do it. You need to swap the element you want removed to the back and then use pop_back(). this avoids rearanging the elements since you are just removing from the back of the array. Or use std::erase along with std::remove_if to achieve this. Also you need to create a predicate. remove_if does not actually erase elements. It swaps elements that must be retained to the front of the container and returns an iterator to the end of the swapped elements. It looks like this:

  
//** std::erase(std::remove_if(v.begin(),v.end(),pred), v.end()); **//  
  
//create the vector containing 1 thru 4 ints  
vector<int> v;  
v.push_back(1);  
v.push_back(2);  
v.push_back(3);  
v.push_back(4);  
  
//create the predicate function  
bool greater_than_2(int i)  
{  
return i > 2;  
}  
//do it all at once   
//** v.erase(remove_if(v.begin(), v.end(), greater_than_2), v.end()); **//  
//or   
vector<int>::iterator i = remove_if(v.begin(), v.end(), greater_than_2);  
  
// v contains (1, 2, 3, 4).  
//but since the retained alements were already in front, nothing  
//happened. However, i now points to 3, and you can erase from  
//there to v.end() to get your final answer.  
  
v.erase(i, v.end());  
  
//or you can use it this way  
//**   
struct predicate  
{  
predicate(int val): val_(val) {}  
bool operator()(int i) { return i > val_; }  
private:  
int val_;  
};  
  
v.erase(remove_if(v.begin(),v.end(),predicate(2)),v.end());  
**//  
//or you can use it this very complex way  
//**  
v.erase(remove_if(v.begin(), v.end(), bind2nd(greater<int>(), 2)), v.end());   
**//  

This is a great article about vectors and in it it contains the pop_back() method:
http://www.gamedev.net/reference/articl-…-le2327.asp
Someone correct me if I am wrong cause I am just learning this stuff.

ding

hi.

very interesting thread :slight_smile:

pelintra,

Unlike vectors lists are not sequential and thus you cant use an iterator+ operator. You can use something like:

  
list<MyObject>::iterator pos = myList.begin();  
advance (pos, 10);  
myList.insert(pos,MyObject);  

This is just from the top of my head so it might be a little off.

BTW are you using it with a particle system? I would be interested to see the code. Have you noticed any speed difference?

ding

wow! A LOT more action on this thread than when i last checked…

i want to keep this example simple, so will revisit tricky optimisations when i implement this in a project that needs it.

but one thing that may be worth doing now (as i’d like to stick to vectors, not change to lists) is moving a dead particle to the end of the vector and popping rather than calling erase.

in something this simple i could swap() a dead particle with the last one and then pop_back(), but i’d rather not get in the habit of doing this in case i end up with an implementation that needs to stay in order sometime down the road.

so i guess the other option is remove_if() but i’m still confused as to how to implement this. i need to replace this code:

  
  
	for (int i = particles.size()-1; i >= 0; i--) {  
		if (particles[i].dead()) {  
			particles.erase(particles.begin() + i);  
		}  
	}  
  

so to keep things simple i’d like to do something like ding mentioned here:

  
v.erase(remove_if(v.begin(), v.end(), greater_than_2), v.end());  

but is there a way to set the ‘predicate’ to the result of a function of the particle element like dead() ?

assuming you have a static dead member function returning true:

  
v.erase(remove_if(v.begin(),v.end(),myObject::dead),v.end());  

ding

ah, i see. sadly, dead() can’t be static in this case as it needs to reference the particle’s variables to see if it’s true or not…

so i guess the simple options i have (other than leaving it as is) are to either swap with the last element and pop,
OR
to follow pangelo + othersides approach and have a vector the size of the maximum number of particles and just enabling/disabling them. but this will mean iterating through the entire vector, even if only a minority of elements are being updated/rendered.

in my example it seems that it’s always the first element which gets erased (which does make vectors the silly choice as they seem to be stacks), but it seems like it should just adjust it’s pointers for any elements either side of the deletion and be done.

one more thing before i call it a night. i’m not sure i understand
but as per that vector tutorial you linked to ding, this seems to work:

  
  
std::vector<Particle>::iterator itr = particles.begin() + i;  
*itr = particles.back();  
particles.pop_back();  
  

not sure if it has the same ordering prob as swapping though.

@nay:
hi. the whole erase/remove idiom can be confusing specially with the predicate thing but basically what the remove_if does is call a function which takes an element of the same type as your vector. so in your case you have a vector, and Particles has a boolean variable “dead”.

so your predicate could just be a function like this:

  
  
bool isParticleDead(Particles _particle){  
 return _particle.dead;  
}  
  
// and the erase function would be something like this:  
  
myParticlesVector.erase(std::remove_if(particles.begin(), particles.end(), isParticleDead), particles.end());  
  
  

this is pretty much how i’m using it (and was very suprised when it worked). hope it helps

@ding:
thanks, i got the list stuff working now:)

the remoeve-erase idiom was used in a particle system, and i think i got a few extra frames per second but nothing too notorious. I’m using it in a project that has so much other stuff going on, its probably not the best way to test this. this project will probably be over in a few days i’ll post the code once it’s done. (or i can send it to you as it is if you dont want to wait, its just kinda messy…)

Thats right. BTW from what I have been reading it might be more efficient to pass the function reference instead:

  
myParticlesVector.erase(std::remove_if(particles.begin(), particles.end(), &isParticleDead), particles.end());   

You can also create a predicate class to have more flexibility:
WARNING code from top of head not tested!

  
class isDead  
	public:  
		isDead(bool wellIsIt): dead(wellIsIt){}  
		bool operator()(const myObject& obj) const {  
			return obj.dead() == dead;  
		}  
	private:  
		const bool dead;  
};  

that way you can use isDead(true) or isDead(false). Look up unary predicate class.

@pelintra
I figured you where doing something with particles and I was just curious as to how you integrated this into your project.

[EDIT] @nay
I think I might be wrong about the static part of the equation. Give it a try and see if it works.

ding

  
 // Returns a valid iterator. If we deleted the end, it points to one past last.  
    inline ParticleList::iterator Remove(ParticleList::iterator it)  
    {  
        if (cb_death)  
            (*cb_death)((*it), cb_death_data);  
  
        // Copy the one from the end to here.  
        if(it != list.end() - 1) {  
            *it = *(list.end() - 1);  
            list.pop_back(); // Delete the one at the end  
        } else {  
            list.pop_back(); // Delete the one at the end  
            it = list.end();  
        }  
  
        return it;  
    }  

Above is the std::vector manipulation code for killing a particle in ParticleAPI. This is from ParticleGroup.h in the lib. Here’s the URL: http://www.particlesystems.org/

Perhaps this will help. The basic idea is to copy something into the hole left by a dead particle.