Depth-first sorting

cecilkorik
Unregistered
 
Post: #1
I'm writing a small game with a completely home-made 3d engine (in pygame/PyOpenGL), mostly for my own educational purposes. Everything's been progressing smoothly so far, I've got models moving around, physics working properly, and particle systems mostly working... but that's where I've run into a snag.

I want my particle systems to use alpha blending, but it seems that for blending and several other OpenGL features to work properly all objects (individual triangles, even?) need to be sorted from back-to-front. Considering the camera and the rest of the scene is always potentially in motion, it seems like a tremendous amount of work to keep things sorted properly, how do people generally tackle this problem? I can't find much information on this topic, tutorials or otherwise, so if you know of any please link them!

Is there a "standard way" of doing it, or is it one of those things where it's very specific to what you're trying to do, or is it just something simple like "use qsort" or "don't use blending"?
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #2
The easiest way is to disable writes to the depth buffer when drawing your particles. In OpenGL, this is done by making the call glDepthMask(0). (and then undone by calling glDepthMask(1)) That way they will be obstructed by other objects in your world, but particles will draw and blend over each other regardless of their depth. Unless you're doing something fancy, this method tends to work pretty well. (you may still want to make sure that groups of different particles draw back to front, though)
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #3
Sorting isn't that expensive, so there's not much more to say than "sort".
Quote this message in a reply
cecilkorik
Unregistered
 
Post: #4
OneSadCookie, it's good to know that as usual I am probably just overthinking things. I'll just use qsort until I start running into problems.

akb825, thanks for the tip! I had disabled depth testing completely, but that resulted in draw-through of existing objects. Re-enabling depth testing seems to cause some minor graphical glitches however. I think your way is the "right" way though, thanks!
Quote this message in a reply
Moderator
Posts: 522
Joined: 2002.04
Post: #5
Another option that may work depending: A common trick is to use two passes. On the first pass, alpha test above a certain threshold, say, 0.8, and draw that without blending. Then on the second pass, turn on blending and draw everything below the threshold.

See http://unity3d.com/support/documentation...aTest.html for further explanation of this technique and a screenshot of it in action. (The trees)
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #6
I use multiple depth sorted passes in my code without any significant performance hit.

Basically, I render all the solid geometry in my scene, sorted by required gl state ( to minimize gl state changes ). Then I render transparent objects forted back to front.

Then for each light I re render the same as above. Admittedly, I cache the sorted lists but the fact is that std::sort ( which is just qsort ) is more than fast enough. In profiling the sorting takes up significantly less than a percent of my runtime cpu usage.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #7
TomorrowPlusX Wrote:std::sort ( which is just qsort )

No.

It's a quicksort, but it's a much more efficient one than C's qsort().
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #8
OneSadCookie Wrote:No.

It's a quicksort, but it's a much more efficient one than C's qsort().

Well sure, to be pedantic Rasp

So, yeah, it's a custom templated implementation using type-specialized function objects for comparison instead of function pointers acting on void *. The compiler can produce more optimized code since it knows the datatype it's acting on.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #9
The compiler can produce much better code because it doesn't have to issue an indirect branch for every comparison...

Of course, Core 2 machines predict indirect branches, so it's less of an issue there.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  bad depth sorting in Cocoa OpenGL aldermoore 2 4,570 Dec 30, 2008 03:07 PM
Last Post: ThemsAllTook
  Depth Sorting Polygons thaeez 2 3,120 Aug 11, 2004 04:23 PM
Last Post: thaeez
  Algorithm for sorting Vertices LongJumper 7 5,383 Jul 30, 2004 12:41 AM
Last Post: Bames53