View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Sign up now

# Sorting alpha-blended objects

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

8 replies to this topic

### #1IceBreaker23  Members

Posted 30 December 2011 - 02:14 PM

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 ;)

### #2rdragon1  Members

Posted 30 December 2011 - 02:56 PM

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

### #3IceBreaker23  Members

Posted 30 December 2011 - 03:25 PM

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?

### #4rdragon1  Members

Posted 30 December 2011 - 03:29 PM

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

### #5Narf the Mouse  Members

Posted 30 December 2011 - 03:37 PM

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

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.

### #6IceBreaker23  Members

Posted 30 December 2011 - 05:01 PM

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

### #7IceBreaker23  Members

Posted 31 December 2011 - 05:09 AM

Now i have a tree. His leaves need alpha blending. But how can i sort LPD3DXMESH?

### #8MJP  Moderators

Posted 31 December 2011 - 06:51 PM

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...
There are also methods for achieving order-independent transparency, but in general these tend to be too expensive for games.

### #9Tournicoti  Prime Members

Posted 01 January 2012 - 10:44 AM

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

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.