 # Depth sorting polys!

Hi!
Is there a fast + accurate method to depth sort transparent polys if I don´t have the center of the poly?
The actual sorting is no prob I do it with qsort()…
What I need to know is how to calc the distance between the player and the poly.
I tried it with the plane equation but this dosn´t work in some cases(You can be infinetly far away of the poly but still be very near to it´s plane).

Any ideas?

P.s.: I did a search already but I din´t find what I wanted.

[This message has been edited by XBCT (edited 01-26-2001).]

Hi!
I tried it with the following method now:
I calculate the average of the distances between the player and the poly´s vertices.
This gives me correct results, but I think it´s a waste of processing power…There has to be a faster solution…

Are the polygons static or dynamic? If they are static you could easily solve it with a BSP tree.

You could also calculate the distance from the player to all the vertices of the polygon and use the shortest one (which shows the minimum distance between player and polygon).

Just an “optimization” :
U can use bounding “things” (these days there are lot of bounding shapes around! )
and just calculate the distance between the nearest bounding vertex or the bounding center.

Maybe what I’m saying is useless…

I think if you want to sort polys correctly, you should test sorting using the projected Z coord of the closets vertex of the object, rather than the distance, so you get correct sorting when objects are in the corners of the screen.

Actually, getting the correct distance of a vertex from the near culling plane is easy to implement, more correct for opengl and faster to accomplish than sqrt( xx+yy+z*z ).

You have the unit normal vector of the near plane, a point which lies on the near plane. Then the distance is d=(p-q)*n. (Or was it q-p?) Where q is the point on the plane, p the vertex to test and n the unit normal.

And you’re saying that the resultant ‘d’ variable would be a vertex? So how do you descern the distance from the vertex? Is the resultant vertex an un-normalized vector or something? What do you do with it once you have it? If you’re supposed to then find the length of it, then you havn’t saved any CPU at all because you’d have to do a sqrt(x^2+y^2+z^2) anyway. However, I’m sure this isn’t what you mean. Please explain as this sounds very interesting. Thanks!

No, since p, q and n are vectors (or more correctly, p and q are the place-vectors of points P and Q), the result of the multiplication (in german we call this vector product Skalarprodukt) of two vectors is a scalar. A simple float for example. A simple value for a simple distance.

To get it sorted out:
ab = a1b1+a2b2+a3b3

Where a and b are vectors of the room R3 I think it is called.

If you divide this product by the product of the lengths of a and b, you’ll get the cosine of the (smallest!) angle between these two vectors btw…

[This message has been edited by Michael Steinberg (edited 01-26-2001).]

Averaging the vertex coords (the simple
barycenter of the vertexes) is a pretty good
number to use, and isn’t that expensive;
especially if you know the number of vertexes
and multiply by the reciprocal instead of
doing a division.

Another way which may very well be good
enough is to just pick one vertex (say, the
first) – if your billboarding and other
transparent geometry is far enough apart,
this will work quite sufficiently.

Hi!
First of all thanx alot for all your ideas\answers… Just to clarify the purpose of the sorting:
I need to depth sort the transparent polys in my Q3 Viewer. Perhaps it would be faster to use the bsp´s back to front order but I don´t traverse the tree back to front which cuts down the time needed for traversing the tree. Therefore I thougt it would be faster to sort those few transparent polys afterwards with some fast algo. But I have to try if it is faster to traverse the tree correctly or to sort the transparent faces afterwards.

Michael: Your method needs exactly as much calculations as mine(If I don´t do the sqrt which isn´t neccessary):

p-q: 3sub
dotproduct: 2

My method:
(x1-x)(x1-x)+(y1-y)(y1-y)+(z1-z)(z1-z):
3

coco: I don´t understand exactly what you mean with “so you get correct sorting when objects are in the corners of the screen.”

bgl: Unfortunately I don´t know the number of vertices ´cause it ain´t fixed.

Anyway I could perhaps store the the average vertex of every face or the center of the face in my face struct and calc it ahead of runtime. But that would make my face struct bigger and therefore my engine would need more memory bandwidth…

Anyway thanx for all your help…

Greets, XBTC!

[This message has been edited by XBCT (edited 01-27-2001).]

You see, my distance is the real distance, yours is d^2. So whenever one needs correct results, it might be better to use mine. If not it is better to use yours, since you don’t have to calculate the unit normal.

And theo had problems sorting his billboards in your way, but I don’t give a quarter for him if anyone bets he did something wrong.

Hi!

>You see, my distance is the real distance, yours is d^2. So whenever one needs correct results, it might be better to use mine. If not it is better to use yours, since you don’t have to calculate the unit normal.<

Yes you´re right…And I don´t need correct results, I only need relative values.

>And theo had problems sorting his billboards in your way, but I don’t give a quarter for him if anyone bets he did something wrong.<

Dunno about theo but for me it works perfectly so far…

Greets, XBTC!

Michael, so to get correct results from your algo, you have to use normalized vectors? So for objects that move about and change position alot, you’ll have to recalculate the unit vector from it? If so, you might as well just use sqrt() to begin with. Because that’s what you have to use to get the unit vector anyway. Please clarify this. Thanks!

Forget all these distance calculations. You should, as someone said earlier, use the projected z-value (or w-value; both work equally well). Add all the z- or w-values for the vertices of each transparent polygon, divide by the number of vertices (it’s faster if you precalculate the inverse and multiply by that), and that’s the value you will sort with.

If you absolutely must do this in world-space, you’ll have to calculate this distance yourself, instead of using the projected z- or w-values. But I can’t think of any reason why you’d need to, except for compiling PVS-type data in the level editor.

Hi!
What do you mean with projected z-value?
The z-values of the vecrtices after going through the modelview-matrix?

Punchey: Only the normal of the plane must be unit (and it doesn’t change over a frame).

CGameProgrammer:
If you want to test it in eye space, you need to pretransform the vertices to eyespace. That would be good, if not the accelerator card would offer that optimized.
Anyway, if I’m wrong in that, I’m here to learn, not to say any others here would be silly…

Trust me.

Hi!
>If you want to test it in eye space, you need to pretransform the vertices to eyespace. That would be good, if not the accelerator card would offer that optimized.<

Exactly what I wanted to know too…
Maybe he´ll enlighten us soon… Greets, XBTC!

[This message has been edited by XBCT (edited 01-29-2001).]