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.
 
FireFoX

October 24, 2001, 05:41 PM


It's called "Tsjernobyl snowstorm"

 
Max

October 24, 2001, 06:05 PM

You should search for information on the [unnamed] return value optimization.

Max

 
Ian Romanick

October 24, 2001, 06:29 PM

Eh-hem...the "joke" was just that you made a typeo. You used "src1" as the name for both parameters in your function:

void addVector(Vector3D& src1, Vector3D& src1, Vector3D& dst);





So, SilentStrike make a joke that would be totally missed if you didn't notice the typeo. I don't think anyone is actually laughing at you.

 
Ian Romanick

October 24, 2001, 06:32 PM

Right. One of the ways that this is commonly done is to just a linked list of free objects. If the list is empty, then there's none free and you don't make any more. Otherwise, the "allocation" process is just removing the head of the list. The "deallocation" process is just adding an element to the head of the list.

 
Dr.Mosh

October 24, 2001, 06:51 PM

heh, didnt even notice that yet?

we need an edit post feature :))))

 
Dr.Mosh

October 24, 2001, 07:01 PM

Well, I searched google for "[unnamed] return value optimization",
and found this very good link for C++ optimisation.

http://www.tantalon.com/pete/cppopt/final.htm

 
John Hoffman

October 24, 2001, 08:19 PM

hmm.. I see this paper promotes inline functions, which I've heard are slower that regular functions, because (I suppose) inline functions don't get stored in the CPU's cache. I'm definately no expert on this topic, so I got excited about reading this. Would anyone be willing to comment on the good/bad points in that paper? =)

Original Link:
http://www.tantalon.com/pete/cppopt/final.htm

Whole thing:
http://www.tantalon.com/pete/cppopt/main.htm

-John

 
DirtyPunk

October 25, 2001, 02:14 AM

You make a few assumptions here :)

Lets debunk a few hey? :)
1) That the program isn't fill rate limited - being particles it is a high chance that it is.

2) Particles aren't typical triangles - they aren't as easily optimisable and you can either use pointsprites/vertex shaders or end up having to do a reasonable amount of the T&L yourself.

3) That he has a whole head of triangles to draw - he may well be hitting the refresh rate and only drawing X number of particles per frame anyway - so his rates are the maximum

4) They are particles - he has to evaluate the movment for each particle - if he has a complex system, this can take some horse power.

Well - I guess things aren't as clear cut as they looked :)

 
Rasmus Christian Kaae

October 25, 2001, 02:40 AM

I prefer www.brinkster.com as free-host.

 
LordDaha

October 25, 2001, 02:50 AM

>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

Does this really help? AFAIK the c-runtime allready does this for you (reusing small blocks of memory so a new doesn't really 'allocate' all the time). I guess you'd spare a few constructors, but that wouldn't be much of a gain, since you'd have to reinitialize a reused particle anyway?

 
Pet

October 25, 2001, 02:57 AM

LordDaha: The amount of particles beeing deleted/created in a seccond can reach a high limit we are not talking here about 'few' particles; and calling or not delete/new thousants of times per seccond make a difference.
Pet.

 
Jari Komppa

October 25, 2001, 03:02 AM

I'd like to take this opportunity to post the best definition of particle systems I've found so far, by late Douglas Adams, may he rest in peace:

1. Anything that happens, happens.

2. Anything that, in happening, causes something else to happen, causes something else to happen.

3. Anything that, in happening, causes itself to happen again, happens again.

4. It doesn't necessarily do it in chronological order, though.

 
Hiro Protagonist

October 25, 2001, 03:04 AM

I don't think that was a typo. src1 is added to dest1 and the result is stored in src1.
its the equivalent of src1 = src1 + dest1;

 
Mournblade

October 25, 2001, 03:18 AM

I read once that "If you have anything worth saying on the Net, then it is worth paying for a site without banners + ads". I stand by that.

 
LordDaha

October 25, 2001, 03:45 AM

>The amount of particles beeing deleted/created in a
>seccond can >reach a high limit we are not talking here
>about 'few' particles; and calling or not delete/new
> thousants of times per seccond make a difference.
>Pet.

yes, this is the difference :
1. normal situation
- need a new particle?
-> call new
- new checks, is there a spare block of memory?
yes : use it
no : allocate

2. implement your own memory management
- need new particle?
->check, do I have a spare particle?
yes : use it
no : allocate by calling new
-> call new
- new checks, is there a spare block of memory?
yes : use it
no : allocate


You see? It actually can get slower...

 
Pet

October 25, 2001, 05:08 AM

Maybe there is a missunderstanding. In the seccond option, there is a better change of getting a spare particle than creating a new one using new. That's the difference: in the first case, you allways call new ( let's say you need 100.000 particles/seccond -> 100000 times/seccond call new). In the seccond case, you end up (after the system reach his 100000 particles, let's say after 1 seccond of simulation) never to call again the new opertor cause you allready have the particles: dead or alive. Any way, if it's not so clear what I'm saying, just try both methods and see the difference.
Pet.

 
LordDaha

October 25, 2001, 07:02 AM

Ok, I need to apologize, you were right about the particle cache optimization, there _is_ a gain, I've written a rough little test program and these are my results :

1. 'particle manager' allways uses new :

time (ms) : 2824
number of creations : 161000
number of news : 161000

2. 'particle manager' reuses particles :

time (ms) : 1462
number of creations : 161000
number of news : 60000

for those who want to try it out for themselves, this is the code of the test program :


#pragma warning (disable : 4786)

#include <windows.h>
#include <list>
#include <set>
#include <iostream>

class Particle;

class ParticleManager
{
friend class Particle;
public:
enum Mode
{
eREUSE, // in this mode particles are reused
eALLWAYSNEW // in this mode particles are allways newed
};
Mode m_mode;

long m_numCreated; // number of created particles
long m_numNewed; // number of 'newed' particles

ParticleManager(Mode mode) : m_mode(mode), m_numCreated(0), m_numNewed(0) {}

protected:
std::list < Particle *> m_cache; // cache of reusable particles

std::set < Particle * > m_particles; // all living particles
public:
Particle * createParticle(long life);
void deleteParticle(Particle * particle);

void step();

~ParticleManager();
};

class Particle
{
friend class ParticleManager;
protected:
long m_life; // how many 'steps' can the Particle live?
ParticleManager * m_manager; // controls the creaétion/deletion of particles
bool m_dead; // indicates a particle is dead

Particle(long life, ParticleManager * manager); // note : only Particle Manager can create particles
public:
void step(); // 1 step
};

Particle::Particle(long life, ParticleManager * manager) : m_dead(false), m_manager(manager), m_life(life)
{
}

void Particle::step()
{
if ((--m_life) <= 0)
{
// its dead, remove it
m_manager->deleteParticle(this);
}
}

Particle * ParticleManager::createParticle(long life)
{
Particle * particle;
if (m_mode == eALLWAYSNEW)
{
particle = new Particle(life, this);
m_numNewed++;
}
else if (m_mode == eREUSE)
{
// still something in the cache?
if (m_cache.size())
{
// pop it
particle = m_cache.front();
m_cache.pop_front();
}
else
{
// otherwise create it
particle = new Particle(life, this);
m_numNewed++;
}
}

m_particles.insert(particle); // add to the list of living particles

m_numCreated++;
return particle;
}

void ParticleManager::deleteParticle(Particle * particle)
{
// delete from the list of living particles
std::set < Particle * >::iterator i = m_particles.find(particle);
if (i != m_particles.end())
{
m_particles.erase(i);
}
if (m_mode == eALLWAYSNEW)
{
// in this mode, just delete it
delete particle;
}
else if (m_mode == eREUSE)
{
// otherwise push it on the list, and make sure it's dead
particle->m_dead = true;
m_cache.push_back(particle);
}
}

ParticleManager::~ParticleManager()
{
// clean up the cache
while (m_cache.size())
{
Particle * particle = m_cache.front();
m_cache.pop_front();
delete particle;
}
}

void ParticleManager::step()
{
// copy the list of living particles
std::set < Particle * > m_copy = m_particles;

std::set < Particle * >::iterator i = m_copy.begin();

while (i != m_copy.end())
{
(*i)->step();
++i;
}
}

int main()
{
{
// put 1 of the following lines out of comment :
//ParticleManager manager(ParticleManager::eALLWAYSNEW);
ParticleManager manager(ParticleManager::eREUSE);

DWORD start = GetTickCount();

// create 50000 particles that live 10 steps
for (long i = 0; i < 50000; i++)
{
manager.createParticle(10);
}

// 10 steps
for (i = 0; i < 11; i++)
{
manager.step();

// each step I create another 1000 particles that live 15 steps
for (long i = 0; i < 1000; i++)
{
manager.createParticle(15);
}
}

// create 50000 particles that live 15 steps
for (i = 0; i < 50000; i++)
{
manager.createParticle(10);
}

// 10 steps
for (i = 0; i < 11; i++)
{
manager.step();
}

// create 50000 particles that live 10 steps
for (i = 0; i < 50000; i++)
{
manager.createParticle(10);
}

// 20 steps
for (i = 0; i < 11; i++)
{
manager.step();
}

DWORD total = GetTickCount() - start;

std::cout << "time (ms) : " << total << std::endl;
std::cout << "number of creations : " << manager.m_numCreated << std::endl;
std::cout << "number of news : " << manager.m_numNewed << std::endl;
}
return 0;
}





 
Stefan Karlsson

October 25, 2001, 09:24 AM

wow. amazing stuff..

but..
since when is GL ported to gameboy?

 
=[Scarab]=

October 25, 2001, 09:59 AM

Hehehehe. ROFL. :)
Well I could've previewed my post but I normally don't do that for such a short message... (silly me ;)

 
Dr.Mosh

October 25, 2001, 10:01 AM

Nah, it was a typo :)))

 
Dr.Mosh

October 25, 2001, 10:03 AM

Wow, you store a pointer to the particle manager for every particle?!?!

What happens when you need 10000000 particles? Surely that is too memory intensive.

 
LordDaha

October 25, 2001, 11:01 AM

1. this was a conceptual test (not a real particle system), it isn't optimized.
2. yes, of course you store a pointer for each particle, how would you sugest to keep a list of created particles?
3. If you want a system that displays 10000000 particles in real time, I don't think storing a pointer for eacht particle will be the biggest problem you'd have to deal with.

 
Hiro Protagonist

October 25, 2001, 11:11 AM

Your particlies seem to hit the ground above the ground plane, as circled in red. Is that simply an illusion caused by the fact that your ground plane doesnt extend far enough in the +Z direction? Or is your collision detection off a bit?

 
Pet

October 25, 2001, 11:22 AM

The plane is not extending as much as the box particle emitter. And the collision plane is a little bit above the land.
Pet.

 
Alex Herz

October 25, 2001, 11:36 AM

I am well aware that there might be a couple of problems which force down the tri throughput...as I implemented a couple of such systems myself...

maybe it's just a debug version or so...you never know..thats why I asked...

but in the end..a particle system normally plays a siderole in a bigger concept(maybe a game)...and a that slow system is not realy applicable imho.
..but I know..I tend to think to much of the real world..

indeed I assume that the app is not gfx hardware limited...
also I assumed that his tri count is correct and that he actually uses triangles(due to the tri count)

you can blow easily 4k tris per frame at 30fps on a voodoo1 with p133
so 2k particles..and there is no T&L..

I don't mean to be anything..just wanted to point out that it might need a little optimization

Alex

 
LordDaha

October 25, 2001, 11:39 AM

Damn, the test program is buggy. The lifetime of the 'reused' particles isnt't initialized (so reused particles live just one step). In the fixed version, the 'reusing' of particles is as slow/fast as allways calling new. Nevermind. A serious test would need other datastructures, anyway.

 
Manuel Astudillo

October 25, 2001, 11:44 AM

Hi,

I dont wanted to be rude but...

well, 56 messages and honestly, the IODT is quite simple... and not really cool IMHO.

greets,

Sarwaz.

 
Ron Frazier

October 25, 2001, 12:23 PM

I just wanted to ring in and reaffirm that a memory allocation cache can indeed be a significant performance enhancement over always using new/delete.

In one of the rendering engines I was working on, I ran the application through Intel's v-tune (which I would gladly proclaim the single most powerful profiling tool I've ever used, everyone should give it a go) and found the the memory management routines were together consuming roughly 10% of execution time.

After creating a memory allocation cache, I reran the application through v-tune and found that the memory management routines + my cache routines were using a combined 5% of execution time. I would consider that to be a pretty useful improvment (especially for about 1 hours worth of work).

 
Union-N8DaWg

October 25, 2001, 12:32 PM

Does it say anywhere that the IOTD has to be complex and ultra super duper crazy fantastic out of this world cool?

Pfft.. This forum is for developers to show off work that can be seen as a screenshot, or simply as a .jpg image. I'm sick of you kids who just wanna see the cool stuff, yet you can't even speak english correctly.

 
Warren Marshall

October 25, 2001, 12:37 PM

Exactly right. This isn't a demo competition ... it's a forum to share what you've been working on.

 
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.