Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 


Submitted by Petru Soroaga, posted on October 24, 2001




Image Description, by Petru Soroaga



I just finished writing a new particle system. I just wnat to know what you guys think about it's design. The concept is as follows: There is a component that handles creation and destruction of individual particles using some heaps of used and unused particles to avoid new and delete opertators to be called to often. Then there are some components called emitters that emits particles in different ways: point emitters, box emitters, etc. Then to handle particle updates, there is an interface that can overritten and that is called by the first component for each active particle active in the system. The interface for update gets an pointer to the particle and a time slice. This way you can write what updaters you need.

The demo can be downloaded from http://www.geocitities.com/whiteblobs/ps.zip
It requires DX8, but the concept can be ported to OGL also. Thanks,
Pet.


[prev]
Image of the Day Gallery
www.flipcode.com

[next]

 
Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Hiro Protagonist

October 25, 2001, 12:47 PM

Well I must say I agree with you, the IOTD is for images, complex or simple, fun or serious. However, the internet is a global thing, so let's not start criticizing peoples' English. There are many people here who speak/write/read English incredibly well for being their secondary language. I respect that.

 
DWORD

October 25, 2001, 01:56 PM

No one is laughing at you! It was just a copy/paste error i guess (in Dr.Mosh' post.
I was just wondering what the function: dest = src1 + src1 was meant to do. Although I did get the point...

 
Neil Edelman

October 25, 2001, 02:15 PM

Just use a browser that is smart enough not to support JavaScript :].

 
dom

October 25, 2001, 02:47 PM

hm...

i got an access violation after running your app. occured before any rendering.

:0

 
Dr.Mosh

October 25, 2001, 02:48 PM

Sigh, you didnt read what I wrote..

You are storing a pointer to the PARTICLE MANAGER in each particle!

 
John Hoffman

October 25, 2001, 03:19 PM

he addresses that issue.. sweet!

-John

 
Godflesh

October 25, 2001, 07:39 PM

Sorry for coming to the party late.

Did you ever consider sticking with the new/delete paradigm and just overloading new and delete? That's what I just did for the particle system on my current GBA project and it works beautifully.

In my CParticle class, I first call a static member function 'Init()' which allocates a single large block of memory for holding all my particles. Then my overloaded new and delete operators can mark off individual particles in the array as allocated or available. There's a little more code to it for book-keeping and speed purposes, but that's the gist. Updating the entire particle system is then as simple as stepping through the array (rather than a list) and updating every allocated particle. Finally, a static member function 'Quit()' deletes the memory block.

I find overloading new and delete operators in specific classes to be a simple way of getting exactly the memory allocation behaviour and speed I want without resorting to a different style of coding for each class.

 
phk

October 25, 2001, 08:45 PM

Mr Godflesh,

You should probably be using linked lists instead of an array. You can of course link the elements in the array. Use one list for active particles and one for non-active. This saves the effort of scanning an array looking for active particles, as well as finding an available one when you need it. Perhaps this was the "little more code" you spoke of...

 
Godflesh

October 26, 2001, 07:01 AM

It certainly was. My constructor knows the index of the first *probably-available* particle (accurate probably 95% of the time) and if it gets wrong, only then does it need to scan from that index on, and is likely to only scan 2 or 3 particles before finding an available one. Similarly, my destructor quickly finds the index of the particle it's deleting and updates the 'first free index' variable that I use in the constructor.

I also keep a count of the number of active particles which is used when scanning through the array. I can early-out of the loop when I've scanned through that many active particles.

This has the benefit of not storing any pointers to particles (except for the pointer to the array), not having to manage a linked list, and not having to call ::new() or ::delete() except in my Init and Quit member functions before and after I use the particle system.

 
Ogotay

October 26, 2001, 11:25 AM

Oh yeah, and what if the homepage you attempt to view within your browser window heavily relies on JavaScript itself?

 
ZubZorro

October 27, 2001, 11:49 AM

You failed CS class.

Rule #47:
Always trust your compilers


For optimum performance you must.

1. inline the calls.
... this includes calls to constructors/destructors of course
and to the thing about the instructions not beeing cached, its bullshit, inline is perfect for small calls like this one.

2. the return value optimization

just do

return vector3( a[0],a[1],a[2] );

This will hint your compiler that the new object should be constructed inside where you want it to, and should allow it to remove all possible overhead.

 
Manuel Astudillo

October 28, 2001, 04:23 AM

Hi,

after all this discussion I will post here my solution for the particle system. I dont have any particle class, just a ParticleField class since I found this faster. The most complicated thing to achieve was to make the particle system frame dependent: the emision rate constant independent of the frame rate.
Well, the code is commented so I hope you can understand it without any more explanations.

greets,

Sarwaz.


void ParticleField::update (float gTime) {
int i;
float t,tt;
long numParticleEmited = 0, deadParticles;

// Compute next position of the particles
gTime += timeOffset;

float diffTime = (gTime/100.0f) - globalTime;
globalTime = gTime/100.0f;


timeCounter += diffTime;
if (timeCounter >= 0.01) {
outputAccumulator += ppcs*diffTime*100;
maxParticleEmit += (long) floor (outputAccumulator);
outputAccumulator -= (long) floor (outputAccumulator);
timeCounter -= (long) floor (timeCounter);
}

// Count the dead particles
deadParticles = 0;
for (i = 0; i < numParticles; i++) {
if (particles.life <= 0) { deadParticles++; } } // Check how many particles we will emit int numParticlesToEmit; float timeBetweenParticles = 0; if (deadParticles <= maxParticleEmit) { numParticlesToEmit = deadParticles; } else { numParticlesToEmit = maxParticleEmit; } if (numParticlesToEmit != 0) { timeBetweenParticles = diffTime / (float) numParticlesToEmit; } float localTime = 0; float diffDecay = decay*diffTime*100; for (i = 0; i < numParticles; i++) { if (particles.life <= 0) { if (numParticleEmited < maxParticleEmit){ pointEmiter (i); particles.localTime = localTime; localTime += timeBetweenParticles; numParticleEmited++; } } else { // update particle position t = particles.localTime; tt = t*t; particles.position[0] = particles.origin[0] + particles.velocity[0]*t + particles.acceleration[0]*tt; particles.position[1] = particles.origin[1] + particles.velocity[1]*t + particles.acceleration[1]*tt; particles.position[2] = particles.origin[2] + particles.velocity[2]*t + particles.acceleration[2]*tt; particles.rotation[0] = particles.angularVelocity[0]*t; particles.rotation[1] = particles.angularVelocity[1]*t; particles.rotation[2] = particles.angularVelocity[2]*t; particles.localTime += diffTime; particles.life -= diffDecay; } } maxParticleEmit -= numParticleEmited; }

 
Fabian Giesen

October 28, 2001, 06:44 AM

Warning: This post is, for a change, really on the design :)

I don't think it's a good idea to call the step() routine once for every particle, and your choice of data structures seems bad too. Why? Let's elaborate on it a bit:


You are using a STL set to store the particles in. Sets are ordered by definition, but since you're only storing pointers to particles in there, I strongly suspect that ordering is not important in your case. The point is, sets are usually implemented using balanced trees, which is an enormously high overhead for cases where the main property (ordering) isn't important at all but inserts and removes occur frequently, thus pushing the management overhead.
Using a particle cache to avoid memory allocations, then using a STL list to store the freelist in isn't preferable either, because, depending on the STL implementation you are using, every list insert/remove operation may very well involve a new/delete too, plus you have a high memory overhead; you are storing pointers, which are 4 bytes. STL lists are doubly linked, which means each list item also has pointer to its predecessor and successor, which are also 4 bytes, so given this simplest structure that fits the standard requirements, you're already wasting two thirds of your memory usage for this information; depending on the implementation, again, this may very well be more.
You have a function call per particle. While function calls aren't nearly as expensive in relation as they were once, it is quite likely that the step() function for your particle only includes some very simple processing and is quite short, so the time needed for function calls WILL bite you here.
The set copy you are doing in your particle manager step() function is EVIL - try not to copy anything in your innerloops unless it's ABSOLUTELY necessary, really!


Okay, enough ranting, now it's time to propose some ideas :)


Try to kick the set and replace it by a vector of particles (not pointers to them), which has a LOT cheaper management costs. Also, try replacing your freelist with a singly-linked list of integers (vector indices), which has less overhead - if you're using STLport or the SGI STL, try using slist, else you'll have to code it yourself. Note: this still doesn't eliminate the possible memory allocations, but getting rid of those is a tad harder. These recommendations should give good results even WITH this additional overhead :)
Use another singly-linked list to manage a list of your currently
active particles; also I'd probably give the step-function for particles a boolean return value which specifies whether the particle is still alife or not. The problem with calling deleteParticle from the particle itself is that a) after deleteParticle returns, the particle is in (virtually) undefined state, yet you're still in a function operating on it and b) deleteParticle has to search for the particle again, while your step function already KNOWS which particle in the set it is operating on, so you don't have to do that search operation (which would be a lot more expensive with lists :)
Get rid of that copy in your particle manager step function - I can't really see what its use is anyway :)
Probably group your particles by type, introduce some helper classes for the respective particle types, and let THEM to the step handling on the particles; give them an iterator to the beginning of their "work area" and a number of particles in this group to process, and let it return an iterator to the end of its work area, then handle the particles in batches. This way, you get rid of the thousands of function calls you're currently doing.


These are some ideas on improving your design - all untested, but if I'm not totally mistaken this should already help a lot :) (Note that, as said, those two lists can and should be eliminated - if you're interested in details, feel free to ask :)

 
This thread contains 73 messages.
First Previous ( To view more messages, select a page: 0 1 2 ... out of 2) Next Last
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.