View Full Version : problem w/ depth sorting

10-18-2003, 06:44 AM
Howdy all. I'm having a problem conceptually figuring out how to do proper, fast depth sorting.
I've got a world made up of objects, each with a bounding box. The objects are frustum culled, and because i'm using gluLookAt for my camera, I can't simply do a qsort with the z value of the objects.

The first conecpt is to use a proper Dist() formula, but with a lot of objects, I know that square root computation will eat up my CPU processing. I haven't been able to find anything else except using the ZBuffer, which would require a glReadPixels, and in my mind, has the same slowdown effect as sqrt().

Can someone help point me in the right direction as to how the data should be sorted?

10-18-2003, 07:18 AM
The first conecpt is to use a proper Dist() formula, but with a lot of objects, I know that square root computation will eat up my CPU processing.
First, are you sure that the square root computation will have a significant, or even noticable, impact on performance, or are you just guessing? Using a profiler, one can be mighty surprised where the bottlenecks actually are. Sometimes they show up where you least exepct them, and where you expect them to be, there's no problem at all.

Second, if you know that A > B, then A*A > B*B. This is true for all positive numbers of A and B, and a distance is always a positive number. So do you really need a square root to sort by distance?

10-18-2003, 11:19 AM
I believe the usual way to do object depth sorting is to tranform the objects' center coordinates by the modelview matrix and then sort them by their transformed z values. If you are using gluLookAt, you can query the matrix after setting the transform.

You don't need to compute the distance to the camera, but even if you did, I agree with Bob that this probably wouldn't have a noticable penalty. The days of avoiding square roots like the plague are over. After all, lighting calculations usually involve a square root per vertex.

10-18-2003, 12:08 PM
Humm.. I've taken aarons advice, and I calculated the AABB center, and projected it to the screen via gluProject.

Problem is, gluProject is giving me a huge slowdown! (~-20fps)
When i get the Modelview and Projection, and multiply the point manually, i get major incorrect values. i didn't thing gluProject was that slow? Ideas?


10-18-2003, 01:10 PM
How are you transforming the point? OpenGL works with row vectors internally, so you have to left-multiply the matrix by the transposed vector, which is equivalent to multiplying by the transpose of the matrix.

As for the slowdown with gluProject, my guess is that this is due to the modelview matrix being queried on each call. You shouldn't use this function.

10-18-2003, 03:05 PM
Figured it out. Seems as though the gluProject gives a differing scale factor than just the multiplication method.

Thanks all!

[This message has been edited by duhroach (edited 10-18-2003).]