# Sorting alpha-blended objects

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

## Recommended Posts

Hi!

I am currently programming a little engine for terrain rendering with trees and plants.
I´ve just built in trees and grass already. But i have a huge problem with alpha blended objects(both grass and trees needs them).

Are there any techniques to sort the object by the distance to the camera so I can draw them from back to front? If, are there any helpfull render states or do i have to do it in vertex shader or something like this?

I hope you can help me, that i can get on with my current work ;)

##### Share on other sites
You do it on the CPU side - sort your meshes by distance, then issue the draw commands for those meshes in that order

##### Share on other sites
Thank you!

Ok can you give me a little code snippet how i compute the distance to the camera?
Do i have to use the worldMatrix for each object?

like this:
 D3DXVECTOR vObjPos = (D3DXVECTOR) *m_World.41; D3DXVECTOR3 vDistance = vObjPos - camera.vEye; float fDistance = length(vObjPos); 

Isn´t this to inefficient for 100 leaves on a tree or 100 grass tufts?

EDIT: How can i do that with the LPD3DXMESH class?

##### Share on other sites

like this:
 D3DXVECTOR vObjPos = (D3DXVECTOR) *m_World.41; D3DXVECTOR3 vDistance = vObjPos - camera.vEye; float fDistance = length(vObjPos); 

Isn´t this to inefficient for 100 leaves on a tree or 100 grass tufts?

What's inefficient about it? How long does it take on your hardware?

Computing the lengthSquared might be slightly cheaper as it'll avoid a divide, and you can sort by that just the same

##### Share on other sites

[quote name='IceBreaker23' timestamp='1325280320' post='4898247']
like this:
 D3DXVECTOR vObjPos = (D3DXVECTOR) *m_World.41; D3DXVECTOR3 vDistance = vObjPos - camera.vEye; float fDistance = length(vObjPos); 

Isn´t this to inefficient for 100 leaves on a tree or 100 grass tufts?

What's inefficient about it? How long does it take on your hardware?

Computing the lengthSquared might be slightly cheaper as it'll avoid a divide, and you can sort by that just the same
[/quote]
Or a hidden square root.

Your sorting algorithm matters more than the specific operation. Or, O (n log n) is going to just be faster than O (n^2), for most cases. More than that, premature optimization is a root of evil - Optimize once you've profiled the code and know where the slow-downs are. Otherwise, drive yourself mad, you will.

##### Share on other sites
ill take std::sort for it(i think its a quick sort) and I think an i7 can handle this ;)
Thank you very much!

##### Share on other sites
Now i have a tree. His leaves need alpha blending. But how can i sort LPD3DXMESH?

##### Share on other sites

Isn´t this to inefficient for 100 leaves on a tree or 100 grass tufts?

In general you're probably not going to be able to properly sort the individual leaves of a tree, it's just not practical. It's a lot of items to sort, and more importantly it would mean a draw call per leaf (unless you dynamically generated an index buffer, which brings its own problems). Usually people will just coarsely sort by object and try to minimize the artifacts on things on like leaves (or they just live with them). For certain categories of meshes it's possible to create a pre-sorted index buffer that will always render the triangles of that mesh in back-to-front order with respect to itself. However this won't work for a lot of cases, particularly cases where triangles intersect or overlap. In fact any kind of sorting will always fail when triangles intersect.

As an alternative, you can try using something other than traditional blending. Such as...

1. Alpha testing
2. Alpha-to-coverage
3. Post-process blending

There are also methods for achieving order-independent transparency, but in general these tend to be too expensive for games.

##### Share on other sites
Hello
I'm currently experimenting an algorithm to sort objects per distance very fastly, here's a description :

The main structure of the sorting object is an hash table ;for instance, let's say the depth range (in view space) is [0,1000], and there are 1000 entries in the hash table : the first entry covers [0,1] depth range, the second covers [1,2] depth range and so on. So when just storing objects , we already presort them in subsets . Each entry of the hash table contains a subset of objects that now must be sorted. I use then std::qsort() on each table entry. (I cut into chunks the entries and put a worker thread on each chunk)

Results : I sort 1.000.000 int objects in 8 ms (average)
CPU : Phenom 4 Cores
RAM : 3 GB
OS : Vista 32 bit
config for this result : 1024 entries in the table, 4 threads (one on each core) (the computation time seems more stable with 8 threads) ; depth range : [0,1000]

(It needed 100 ms for a 'single entry hash table' with one thread ; ie pure std::qsort() sort)

My plan is to sort transparent faces ( I ignore the intersection case and the "A over B ; B over C ; C over A" overlap case )
Today, my transparent faces all use united color so I will build a (pre sized at cooking) unique buffer containing all these faces, so I'd need only one draw call for transparency

But that's just a personal experiment, I think it can work mostly because there's quite few transparent primitives and because they all use the same layout/technique.

I can post/send my code for this if you're interested or just curious

For what it worthes

Nico

1. 1
2. 2
Rutin
19
3. 3
4. 4
khawk
15
5. 5
A4L
13

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633743
• Total Posts
3013644
×