View Full Version : Depth sorting.

08-19-2004, 03:10 AM
Ok, im trying to implement some effects for my engine such as a grass field and other thing like particle system. For these things I need alpha blending, but then you need to have a back to front ordering of polygons.

My question is, what is an efficient way to order alot of polygona into back to front ordering? I mean, obviously you could just take their distances from the camera and do a quicksort or something, but isnt that really crappy and slow? There must be a better way to do it, this is obvious since ive seen alot of demos and games which use alpha blending...

08-19-2004, 04:50 AM
Try a google search for "depth peeling"

There's also some example code in the nvidia SDK.
You can download the individual example at



08-19-2004, 06:53 AM
Depth peeling will do the job, but I'm not sure if it's a technique well suited to games just yet. If you need to sort an unordered collection of polies, go with radix sort (http://codercorner.com/RadixSortRevisited.htm) .

08-21-2004, 12:36 AM
>> this is obvious since ive seen alot of demos and games which use alpha blending...

Most of the time games only sort particle systems (smoke trails etc) and are often wrong with dynamic blending other than additive. If the geometry is static, use BSP to pre-sort polygons.

Instead of sorting polygons, you can sort by object, if the blended parts define a convex hull (it works well for cars' windows).

08-21-2004, 06:34 PM
When you generate your grass, generate it correctly sorted for the current view direction. This means that if the viewer turns around 180 degrees and looks back, he'll see wrongly-sorted grass. However, in practice, this doesn't happen. Planetside used this mechanism, and it was very convincing.

You could also keep a vector per grass block for what the current sort order is, and when the view vector is "too different," you re-sort to the new view vector (but only if the grass block is actually visible :-). This way, you only pay the sorting once every N frames.

You of course need to sort blocks WRT each other, but that's somewhat simpler.

08-23-2004, 02:16 AM
I often use my own technique. Divide the render into two passes and render the grass with alpha mask and z buffer ( render only opaque part of grass) and then render unsorted alpha part (only semi and transparent part of grass) with alpha mask and no z depth. This is so much faster and usually works fine with grass, billboards etc. You will get the wrong sorting order on the transparent parts, but this can in most cases look good anyway...

(copyright tooltech ?) ;-)

08-23-2004, 03:14 AM
yeah, but the whole problem arises in the transparent parts. This is most noticeable as texture minification occurs, so you get an averaging of alpha 1.0 texels and alpha 0.0 texels, so at the edges of the grass blades you get semi transparency, which can look pretty ****e if youre order is wrong, blending with say the ground instead of the grass behind it...

08-23-2004, 03:28 AM
You still get transparent blending. But you get an error blending as the blend order is wrong between transparent geometry, but my point is that that order many times doesn't matter.

Some of my important rules.

1. All blended stuff must be blended and culled properly with opaque geometry ( so pass two must blend propely with pass 1)

2. mutiple layers of transparent blended geometry doesn't need to be properly sorted in the right order for good approx results. a1 blended with a2 blender with background is almost the same as a2 blended with a1 blended with background.

08-23-2004, 06:53 AM
I agree with ToolTech. I tried this some time ago, and it gave good results, as long as Ztest is disabled on second pass. Else you can get really ugly artifacts ...


08-23-2004, 02:29 PM
if the ztest is disabled? i dont understand, wont this result in far away grass possibly overwriting the near grass in the frame buffer? and this is a BAD thing.

08-23-2004, 04:04 PM
I think ToolTech is talking more generically than this specific case. In general, it isn't terrible to have two blended objects in the wrong order, especially if the blend factor is pretty small.

Grass, however, is not that case. The reason is that grass is usually opaque with fully transparent parts in it. If you render it in the wrong order, you will know it.

In general, if you can stand the artifacts, I would suggest using an alpha test for grass. Just have the texture be either 0 or 1 for the alpha, and let the alpha test sort it out. Otherwise, you're going to need to sort the objects correctly to get good results.

08-23-2004, 07:52 PM
Can anyone explain why depth peeling wouldn't work super well in games (it gives perfectly accurate results)? Is it because of the possible O(n) depth complexity? (which is normally more around O(log(n)))

In that case, could you use occlusion query to help figure that out (possibly increase or decrease number of passes for depth peeling depending on last frame's info?). Also, how much of a performance penalty would there be for having TONS of occlusion query (this usage could easily produce tons)?

08-23-2004, 11:18 PM
Unless my knowledge of depth peeling is seriously out of date:

-Too slow, for vegation or particles you potentially need dozens of layers
-Artifacts if the number of overlapping layers exceeds the number of passes
-No robust solution to work on all hardware. Or is there...?

Depth sorting is fast, and in most cases provides perfectly correct results. The only place I can think of where depth peeling could beat sorting is multipass algorithms, which become very unefficient with blending.

Fast sorting reciepe:
-Recieve an approxximate sort from your spatial structures (eg. octree)
-Inside each node, sort objects using quicksort/radix. There shouldn't be too many.
-For each transparent object store multiple index arrays sorted along different directions, and select the one that closest matches the viewing direction.
-Create a texture atlas of all your transparent textures, otherwise you'll end up switching state every couple of objects, since they can't be sorted by state.


Tom Nuydens
08-23-2004, 11:24 PM
Originally posted by Adruab:
In that case, could you use occlusion query to help figure that out (possibly increase or decrease number of passes for depth peeling depending on last frame's info?). Also, how much of a performance penalty would there be for having TONS of occlusion query (this usage could easily produce tons)?No, one query per peel is enough. I have a demo on my site that uses occlusion queries to dynamically adjust the peel count: www.delphi3d.net/download/oit.zip (http://www.delphi3d.net/download/oit.zip) (NVidia only IIRC).

The typical usage of depth peeling, however, would be to generate a fixed number of peels (say, four or five). On the last peel, all remaining surfaces are drawn in unsorted order. The idea is that the first three or four translucent surfaces will suffice to cover up any sorting errors in what lies behind them.

-- Tom

08-24-2004, 11:03 AM
Ok. I shall give you some more details about my work.

In my research for Gizmo3D i have developed a pseudo depth peel.

Kind of a poor mans solution for billboards, trees,grass etc where you want to have smooth antialiased edges.

1. First render all geometry using alpha mask GT 0.9x so all opaque geom is rendered. Update and use z buffer as normal rendering

2. render all geometry with alpha mask GT 0.y and disable color update, but enable z update.

3. render all geom again with alpha mask LTE 0.9x, enable color but use z accept LEQUAL so only semi transparent geom is rendered that is in the nearest layer or blended randomly where alpha is very low.

Ok. You think this is really sloppy, but you get some benefits...

1. All geom is rendered totally unsorted
2. All opaque parts are rendered correctly
3. You only get the nearest (one layer) transparent geom, but in most cases you get ok results as the nearest layer blends with all the opaque data. You can see that two adjacent transparent layers will occlude each other when you zoom in

try it and tell me what you think. I think proper depth påeel is the way to go and in the future it will be very efficient, but on very low end hw, this works quite well..

08-25-2004, 02:17 AM
I forgot to say that you can add a pass 1.5 that renders all geometry without z update with alpha mask LTE 0.9x.

This will add all blended unsorted transparent geometry. The pass will reduce the anomaly of pass 3 that only render the top most alpha layer. Bt using pass 1.5 you will get some kind of blended alpha data behind the top most alpha layer in pass 3.