🔒 Locked

Particle System Sorting

Started by Evil Bill Aug 9, 2002 at 12:29 PM 10 replies 1k views

Original Post

Aug 9, 2002 at 12:29 PM

Hey all. I'm trying to make a particle system for my little app. I've got as far as making a kind of smoking / steaming particle system that works fine. The only problem is that they use alpha, so i need to sort the particles. At the moment, all of my particles are in a std::vector, and they have a bActive flag. When i spawn a new particle, i first check if i can reuse an inactive particle, and if not, then i add to the vector. This way i only have one list, not a used and unused list (oppinions?). Here's a picture of what it loks like at the mo. As you can see, theres a lot of particles that aren't at the correct depth. Each particle has a random velocity and is affected by gravity, and i just render the particles as they appear in the list. In this shot theres about 380 particles. So, on to the question: whats the best (quickest) way to sort these particles? With 300 particles, its a bit extreme to loop through the list, getting the furthest Z-value, adding it to the list, and repeating (I can't remember what that type of sorts called). Cheers, Steve [edit] Fixed link [/edit] Steve
DirectX Programmer
Soon to be the new Bill Gates

[edited by - Evil Bill on August 12, 2002 10:20:08 AM]

Teknofreek

Aug 10, 2002 at 10:43 PM

Hey Evil Bill,

You might want to check out "Special Effects Game Programming with DirectX", by Mason McCuskey. It has lots of tips about how to work with particles and other special f/x.

Anyway, as to your current setup, my main opinion would be to not add anything to the vector at all as you go along. Instead, start with an array, or vector I suppose, that''s already allocated to a maximum number of particles. That way, you only need to allocate the memory once. Then as you go along you can turn elements of that array on and off as they die and spawn. I think this will give you a much quicker setup in the end...especially if you start working with a decent number of particles, since allocating on the fly will likely cause some memory thrashing.

As for the sorting....hmmm...I''m not quite sure. I too would be interested to know if there''s a tried and true preferred method.

-John

DrunkenHyena

Aug 11, 2002 at 1:05 AM

In a lot of cases, (such as the room example your pic shows, URL''s mangled in the post BTW) you can simply draw the particles after all other geometry. There may be tiny glitches here and there, but if things are moving around, you''ll never notice.

IIRC, vector batch allocate, so creating a new particle shouldn''t be a big deal.

Stay Casual,

Ken
Drunken Hyena

FantasyGuy

Aug 11, 2002 at 6:27 AM

Well, you can group your particles into groups of particle for every effect. For example, if you''re making a particle engine for explosions, you can group the particles of every single explosion in one group and then make the sorting based on the whole group. The particles inside a single group need not be sorted.
Advice:
Don''t use std::vector. It''s not meant to be used in real-time applications. Use a static array, it''s much faster.

My site

CpMan

Aug 11, 2002 at 2:57 PM

Just draw your particles after everything else, and turn off Z-Buffer writes (still keep compares)

Trip99

Aug 11, 2002 at 4:10 PM

You still have to sort the textures by z distance due to transparency blending issues and yes, you do not write to z buffer just use z test,

Evil Bill

Author

Evil Bill

Aug 12, 2002 at 9:26 AM

D''oh! never noticed the duff link. It works now though.

I use vectors because they let me add more particles if needed. When i construct the particle system is allocate a set amount of memory (vector::resze()). I rarely need to add more particles though.
I totally forgot about disabling Z-writes, that''ll probably make a difference, i''ll do thta when i get time.

I already own Special Effects Game Programming With DirectX, but i haven''t had time to read it yet, i''m still ploughing through Programming Role Playing Games with DirectX8.

Thanks for the replies.

Steve

Steve
DirectX Programmer
Soon to be the new Bill Gates

benjamin bunny

144

benjamin bunny

Aug 12, 2002 at 9:49 AM

The radix sort is almost certainly the fastest algorithm for this. It's usually used for integers, but can be adapted to use floats too. The method is described here.

There's a cut down version of this algorithm designed just for positive floating point numbers in my 4e3 entry, Wizard Duel 2, if you're interested (files RadixSort.h and RadixSort.cpp).

*500 error*

____________________________________________________________
www.elf-stone.com

[edited by - benjamin bunny on August 12, 2002 10:49:58 AM]

Evil Bill

Author

Evil Bill

Aug 12, 2002 at 3:40 PM

Yeah, that looks a lot better now,
As you can see here.

I still need to change a few things: i need to load TGAs so i can use alpha channels, and i need to render a hexagon or octagon shape for my particles to make it look better.
I''ll have a look at the radix sort, but i don''t think its needed now.

Thanks, Steve

Steve
DirectX Programmer
Soon to be the new Bill Gates

Evil Bill

Author

Evil Bill

Aug 12, 2002 at 7:04 PM

*Sigh*
Ok, does anyone know of a free program that can save TGA files with alpha channels? I''ve got Paint Shop Pro 7, but it insists on merging the mask with the background when it saves a TGA.

Cheers, Steve

Steve
DirectX Programmer
Soon to be the new Bill Gates

Sharky

Aug 12, 2002 at 7:15 PM

quote:
Original post by Evil Bill
*Sigh*
Ok, does anyone know of a free program that can save TGA files with alpha channels? I''ve got Paint Shop Pro 7, but it insists on merging the mask with the background when it saves a TGA.

Cheers, Steve

Hi, Steve.
As far as I am aware you can use PSP7 to save TGA files with an alpha channel. It''s a bit messy and I cannot remember how to do it exactly - take a look at the help file as I *think* it explains how to do it. IIRC there is an option along the lines of ''Save to Alpha Channel'' (or similar). Stick with it because it can be done! Good luck.

Regards,
Sharky

Evil Bill

Author

Evil Bill

Aug 12, 2002 at 7:51 PM

I'v been trying for 45 mins, and its now 1:40 here, so i'm giving up. The PSP help does say that it saves 24-bit TGA files as 24bit files and 8bits of alpha, but i can't seem to persuade it to save alpha. I create an alpha channel from my image and apply it to another image. This works fine, i can see the blended image. The i save it, and reload it and PSPs done the blending for me and duffed it up

I'll post on the Visual Arts forum and see if anyone can help.

[edit]
I duffed the link again
[/edit]

Cheers, Steve

Steve
DirectX Programmer
Soon to be the new Bill Gates

[edited by - Evil Bill on August 12, 2002 8:59:29 PM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.