PDA

View Full Version : Depth sorting polys!

XBCT
01-25-2001, 11:59 PM
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).]

XBCT
01-26-2001, 01:34 AM
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....

Humus
01-26-2001, 04:38 AM
Are the polygons static or dynamic? If they are static you could easily solve it with a BSP tree.

01-26-2001, 05:06 AM
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).

rIO
01-26-2001, 08:48 AM
Just an "optimization" :
U can use bounding "things" (these days there are lot of bounding shapes around! http://www.opengl.org/discussion_boards/ubb/biggrin.gif )
and just calculate the distance between the nearest bounding vertex or the bounding center.

Maybe what I'm saying is useless...

coco
01-26-2001, 11:53 AM
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.

Michael Steinberg
01-26-2001, 01:20 PM
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( x*x+y*y+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.

Punchey
01-26-2001, 01:28 PM
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!

Michael Steinberg
01-26-2001, 01:36 PM
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:
a*b = a1*b1+a2*b2+a3*b3

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).]

01-26-2001, 03:13 PM
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.

XBCT
01-27-2001, 02:09 AM
Hi!
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: 3*sub

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

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).]

Michael Steinberg
01-27-2001, 06:20 AM
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.

Michael Steinberg
01-27-2001, 06:22 AM
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.

XBCT
01-27-2001, 02:00 PM
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!

Punchey
01-29-2001, 06:07 AM
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!

CGameProgrammer
01-29-2001, 06:19 AM
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.

XBCT
01-29-2001, 08:58 AM
Hi!
What do you mean with projected z-value?
The z-values of the vecrtices after going through the modelview-matrix?

Michael Steinberg
01-29-2001, 09:15 AM
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.

XBCT
01-29-2001, 12:47 PM
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.... http://www.opengl.org/discussion_boards/ubb/wink.gif

Greets, XBTC!

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