Jump to content
  • Advertisement
Sign in to follow this  
REF_Cracker

Billboard Particle Sorting

This topic is 645 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

What is the proper way to sort billboard particles?

A - Distance to eye (pythagoras)
or
B - Distance along cameras forward axis? (plane equation)

Thanks,

Share this post


Link to post
Share on other sites
Advertisement

Distance to eye (pythagoras)

 

If you do that, don't forget that you only need to compare (A2 + B2), you don't have to get the real distance (sqrt(A2 + B2)).

Save yourself a few hundred thousand square roots.  :)

 

Do you even need to sort them? Have you already tried just disabling depth-writing (but still depth-test), and see how it looks? Sure, it won't be accurate, but it might look good enough to satisfy you.

Share this post


Link to post
Share on other sites

Thanks for the replies.

I looked through billboard code (I wrote it a few years ago) and I am aligning them to be (0,0,-1) in viewspace so I guess that answers my question.
I will use the plane equation for sorting.
 

"Do you even need to sort them? Have you already tried just disabling depth-writing (but still depth-test), and see how it looks? Sure, it won't be accurate, but it might look good enough to satisfy you."


In this case I do need to sort them because I am lighting and shadowing the particles.

Thanks,
 
Edited by REF_Cracker

Share this post


Link to post
Share on other sites

I assume also that the depth sort you have already occluded in screen space/frustrum and then used a quick sort once you have the depth of every particle?

 

Just interested in your execution.

 

I have to do the same thing soon for my particle engine, in fact I spent the weekend changing my code in preparation for this.

Share this post


Link to post
Share on other sites

I assume also that the depth sort you have already occluded in screen space/frustrum and then used a quick sort once you have the depth of every particle?

 

Just interested in your execution.

 

I have to do the same thing soon for my particle engine, in fact I spent the weekend changing my code in preparation for this.

Not sure what you mean about "occluded in screen space"....
A rough outline of what I have right now.

Solve particle system (does a lot but it's basically an ubershader-esque design of different functions to transform the particle data. sizeOverLife() colorOverLife() etc etc etc
One of the most important things to get right here I feel is the "swap deletion" method of maintaining a contiguous list of particles in an array. Helps with allocation from a pool.

Sort the particles. I do this with a key rather than sorting the actual particle data. I have a simpler struct that contains an {index,depth} pair and I qsort them.

 

I now have a list of active particles and their attributes. One thing to note is I solve this system at a fixed time step of 30 FPS. I also double buffer all attributes related to rendering (position, rotation, color, etc) this allows me to tween the particle for rendering at an fps higher than 30 and still get smooth consistent results.

 

Using the sorted key list I iterate over all the particles and build a vertex buffer (dynamic) to send to the GPU. I submit one vertex per particle that contains both frames of the double buffered data. This allows me to only update that GPU buffer at 30 FPS as well.

ON GPU:

vertex shader - to expand the packed particle data and tween it for the current delta time
geometry shader - turn the one vertex into 4 verticies of a quad
pixel shader - sample textures and output

I also have a lighting system now built for the particles that decouples lighting from screen size much the same way as mentioned in the latest DOOM tech papers.
 

Edited by REF_Cracker

Share this post


Link to post
Share on other sites

Hi, when I meant occluded, I was actually inferring if the particle was in the viewable space.

 

For me, my game is a mostly top down view game.  As such, the terrain is the full view on screen.  My quad tree implementation not only relates to terrain culling though, but all entities.  

 

I've set up a 2d array aligned to my terrain, the array is at most 1024 x 1024.   I've then filled this array with the relevant leaf of my quadtree.  So when I traverse the tree and either enable or disable parts of the tree for rendering the array effectively is updated at the same time, the tree pruning also culls static assets for those leaves.   But, for dynamic assets that move, I use the 2d array to find out where they are if they need to be rendered.  I am going to use this for my particle system too, to remove the particles that aren't on screen at that point in time.  Sorting should be quicker.

 

You answered the question on your quick sort, and I probably will use the same mechanism as you for handling the sort, a container.  Other components such as sizeoverlife and colour (not so much at the moment) are in mind.  I also use the Geometry shader to expand the single vert to a quad.  Because of the view of the game, I have need for 2 billboards in different planes, XZ, XY planes as well as the camera plane.  I'm passing enough information to calculate the plane I need.  Just simple stuff really.

 

Gl on the implementation, if I get mine working in the next few weeks (i need to!) then I will post my initial efforts.

Edited by ErnieDingo

Share this post


Link to post
Share on other sites

 

I've set up a 2d array aligned to my terrain, the array is at most 1024 x 1024.   I've then filled this array with the relevant leaf of my quadtree.  So when I traverse the tree and either enable or disable parts of the tree for rendering the array effectively is updated at the same time, the tree pruning also culls static assets for those leaves.   But, for dynamic assets that move, I use the 2d array to find out where they are if they need to be rendered.  I am going to use this for my particle system too, to remove the particles that aren't on screen at that point in time.  Sorting should be quicker.

 

As far as culling goes ... what I've got working is a simple sleeping mechanism

Each emitter has a uint sleep counter, while processing the particle system I do a min max on all points to generate a AABB.
The AABB is checked against the view frustum. If it's visible I reset the counter to zero... otherwise I increment.
If the counter is above lets say 30 I just stop updating it and wait for the last bounding box to become visible again before resuming.

This works well for environmental emitters (working on a waterfall at the moment) but other uses might need to time out destroy themselves.

Edited by REF_Cracker

Share this post


Link to post
Share on other sites

I doubt the quicksort is really a bottleneck, but if you want to try something out, then this is a perfect opportunity to implement a radix sort - it'll be faster. You don't even have the slight headache of negative float values to worry about (assuming you sort with distance along z, anything negative can be culled as out of view).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!