# Depth sorting with transparant billboards

Hi,

I’ve got a problem with trying to draw transparant billboards. The problem is that I don’t know how to depth sort them correctly under all possible gl transformation matrixes. I have code for depth sorting made. What I have now is that it calculates the distance of each billboard to a certain point, that is extracted from the modelviewmatrix.

Now the problem I have is, that I can’t really calculate this point properly! I have no idea how to find this point, as everything I try doesn’t seem to work under all conditions, only under some.

Can someone explain to me what I should do? I don’t really know what the ModelView matrix does to glVertex3f coords passed. Are the coords first translated, then rotated? Or are they rotated, then translated? Is there anything special I should know about how the ModelView matrix affects glVertex3f coords passed?

I tried just extracting the modelview matrix translation values, but that didn’t work. I tried negative of the values, that didn’t work.

I tried just clearing the modelview matrix translation values, and then translating by what used to be the translation value. Because translations are translated after being warped by the rotation matrix, I can find out how OpenGL affects the translation, but that didn’t work either. I tried all sorts of different combinations of things, but none of them worked under all conditions.

Someone please? Multiple transparant billboards MUST have been covered before. Is there a webpage? Or even just a general depth sorting algorithm for blended primitives.

It will probably suffice to sort them simply after their distance from the eyes, if they don’t get too big.

Well, reread your’s. You will most probably have the world position of the billboards and also the world position of your “eye”. Calculate the distance of them and sort them.

> Well, reread your’s. You will most probably have the world position of the
> billboards and also the world position of your “eye”. Calculate the
> distance of them and sort them.

I have all the data. I just don’t know what to do with it. Everything I try fails

The problem is, that I don’t know what the transformation matrix does. Does it rotate then translate, or translate then rotate? And are there any other special things I need to know about what it does to the vertexes.

You see, I can’t calculate the distance from the eyeview to the vertexes if I don’t know what the transformation matrix does to the vertexes.

I’m still just as stuck as before you replied

> Well, reread your’s. You will most probably have the world position of the
> billboards and also the world position of your “eye”. Calculate the
> distance of them and sort them.

I have all the data. I just don’t know what to do with it. Everything I try fails

The problem is, that I don’t know what the transformation matrix does. Does it rotate then translate, or translate then rotate? And are there any other special things I need to know about what it does to the vertexes.

You see, I can’t calculate the distance from the eyeview to the vertexes if I don’t know what the transformation matrix does to the vertexes.

I’m still just as stuck as before you replied

OpenGL doesn’t do rotation or translation in any particular order. It simply does the transformation you give it. So if you created the transformation as M=RT or M=TR or something more complex, then that is what you need to do too. For example, say you have a matrix M intially set the identity matrix, M=I, via glLoadIdentity. Then you decide to translate the matrix with glTranslate, so that produces M=IT. Then you decide to rotate about the X axis with glRotate, so that produces M=(IT)Rx. Then say you also happen to rotate about Y and Z as well (in that order) so now you have M=(((IT)Rx)Ry)Rz. Now matrix multiplication is associative so you could solve for R=RxRyRz, then final matrix is just M=TR. Get my drift? OpenGL post-multiplies matrices. You also need to recognize that OpenGL matrices are column major rather than row major.

> OpenGL doesn’t do rotation or translation in any particular order.

Hi, you misread my question. Also I know about that OpenGL is the transpose of standard Math notation. I said before that I already know how to extract the position and rotation matrix (and I do).

In the OpenGL matrix you have position and rotation variables, correct?

Well, as I said in my first, and in the last message: I want to be able to know what OpenGL does to the vertexes. Does it first rotate them and then translate them, or translate and then rotate them? I’m not talking about calls to gltranslate or glrotate. I’m talking about what does it do with the values stored in the matrix. Does it act on the translation values stored in the matrix first, or on the rotation values stored in the matrix first? What happens to the vertexes? I can’t tell, because I don’t see what happens to them. Vertexes aren’t stored in any matrix, so I have no way of reading them. Because I don’t know how my vertexes are transformed, I can’t calculate the eyeview coordinate.

So, at the end, you got your billboards drawn. As I understand, you need to depth sort them, since they’re blended. Is that correct?
If you simply want to do that, you don’t need to think about any translation, it only depends on your position.

Say xp, yp, and zp is your position.
Say xb, yb, and zb is the billboards’ position. Both given in world coordinates (untranslated).

The distance is

distance = sqrt( (xb-xp)(xb-xp) + (yb-yp)(yb-yp) + (zb-zp)*(zb-zp) );

Smallest distance is the nearest…
You start drawing the billboards with the greatest distance and repeat it until you haven’t got any billboards left over.

Oh, and you’re getting that with the matrices wrong. If you do a glRotate or glTranslate, opengl will create a rotation matrix or a translation matrix respectively and multiply it with the modelview matrix (if that is currently activated). The matrix contains all translations, scaling and rotation. When you’re sending vertices to opengl, opengl will only multiply that matrix with the vertex. A vertex * a matrix results in a vertex.

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

Hi Michael.

I don’t know if I’m not expressing myself clear enough. Well, yes the code is:

distance = sqrt( (xb-xp)(xb-xp) + (yb-yp)(yb-yp) + (zb-zp)*(zb-zp) )

Now, in my first post I said "
Now the problem I have is, that I can’t really calculate this point properly! I have no idea how to find this point, as everything I try doesn’t seem to work under all conditions, only under some."

This seems to explain my problem. The code you gave me is the one I am using, the problem is, how do I calculate xp, yp, and zp? Simply extracting it from the ModelView matrix fails. It needs to take the rotation into account Somehow. Now what are the details of how to calcluate xp, yp and zp? Like I said again in my first post, everything i tried fails.

Don’t you know where you placed your viewpoint at all? I mean, if you call gluLookAt(xp, yp, zp, … blah), you got your xp, yp and zp right there, in the arguments to the function. No need to take rotations into consideration. Same goes for particle position. You must have placed the somewhere in the space, and you should know where.

It doesn’t matter how you rotate the scene, the distance is always the same. In both eye-coordinates, aswell as in worldspace.

Bob, you’re saying the point. Rotation is not interresting at all in this point. (Actually it might have been insulting that I wrote how to calculate the distance between two points… )

Theo, I must say I’m a bit disappointed from you. How can one be, sorry, so silly to have a correct matrix uploaded or however, without having known before where he had been? OpenGL doesn’t need an extension for that, maybe you!

I’m almost sure that you used ONE glTranslate and maybe several glRotatef.
I need code here to be able to help you, but don’t tell anywhere we would only talk useless stuff.

>Don’t you know where you placed your viewpoint at all? I mean, if you call gluLookAt(xp, yp, zp, … blah), you got your xp, yp and zp right there, in the arguments to the function. No need to take rotations into consideration. Same goes for particle position. You must have placed the somewhere in the space, and you should know where.

I don’t use gluLookAt. I use glLoadIdentity, then glTranslate then glRotate, then another glTranslate.

>It doesn’t matter how you rotate the scene, the distance is always the same. In both eye-coordinates, aswell as in worldspace.

You mean I just extract the x,y,z from the modelview matrix? I tried that, and it didn’t work. I even tried using negative values and it didn’t work.

> Theo, I must say I’m a bit disappointed from you. How can one be, sorry, so silly to have a correct matrix uploaded or however, without having known before where he had been? OpenGL doesn’t need an extension for that, maybe you!
I’m almost sure that you used ONE glTranslate and maybe several glRotatef.
I need code here to be able to help you, but don’t tell anywhere we would only talk useless stuff.

I’m not quite sure about what you are saying. You just mean I should have xp, yp, zp because I am the one who made them? I tried using those values and it didn’t work. I ended up with ones that should have been infront (and drawn last), being drawn first.

<<I don’t use gluLookAt. I use glLoadIdentity, then glTranslate then glRotate, then another glTranslate.>>
this sounds a bit complicated u might wanna think about using gluLookAt or check out somebody elses camera code on the net as with most things it helps if u keep them as simple as possible, at least thats what i find

>>I don’t use gluLookAt. I use glLoadIdentity, then glTranslate then glRotate, then another glTranslate.

Ok, maybe i should rephrase the sentance: I mean, if you call glTranslate(xp, yp, zp) and then some glRotate’s, you got your xp, yp and zp right there, in the arguments to the function. No need to take rotations into consideration.

>>You mean I just extract the x,y,z from the modelview matrix? I tried that, and it didn’t work. I even tried using negative values and it didn’t work.

Forget about the modelview matrix! (sorry for that one, but it feels like we have said it enough)

Consider the following example code.

glMatrixMode(GL_MODELVIEW);
// Place the viewpoint (camera)
glTranslatef(xp, yp, zp);
glRotatef(10.0f, 0, 1, 0);
// Place the particle
glTranslatef(xb, yb, zb);
glRotatef(20, 0, 1, 0);
// Draw the particle

Now you use the formula mentioned above to get the distance: distance = sqrt( (xb-xp)(xb-xp) + (yb-yp)(yb-yp) + (zb-zp)*(zb-zp) )

The numbers you need to insert in this formula is the one in the code above. Forget about rotations, forget about the modelview matrix. Just find where you place the camera, and where the particles are, and just calculate the distance.

P.S. In case you didn’t knew it, gluLookAt is just a series of otations, follower by a glTranslate. So in theory, using either gluLookAt or glTranslatef/glRotatef is mathematically the same.

[This message has been edited by Bob (edited 01-14-2001).]

Actually, I think Theo does really not know where he is. Can you please post some code? Actually, I don’t need 2 glTranslates, why do you?
You can also email me the code if it’s secret.

The problem is that you don’t exactly know where you are, if you did a glRotate before another glTranslate (does that make any sense?)

Consider:

glTranslatef( 12124.0, 2.4123, 123123.444 );
glRotatef( 2323.4, and something normalized )
glTranslatef( 121.4, -1212.42323, 1235632.0 );

I don’T know any sense in that attempt to translate the world, but actually you won’t know the position afterwards, without calculation.

You can get the current modelview matrix through matrix = glGetFloatv( some matrix parameter );

Take the translation indices ( 12, 13, 14 ) and switch signs and you should have the global position.

Theo,

A not-optimal method for getting the pts in eye-space is

glGet( GL_MODELVIEW_MATRIX );

And then use that 4x4 matrix to transform your pt. Something like

Theos_GlMat_Mult(&eye_pt, &matrix, &model_pt);

Then use that eye_pt in your distance computation. When you have that working, you can replicate the glTranslate/Rotate calls in your code for optimal speed. (i’m assuming glGet(GL_MODELVIEW_MATRIX) will be quite slow w/ T&L hardware, such as a GeForce).

Good luck-

PS You may wish to check out “Manhattan Distance” for quick computations.

Retrieving matrices will be “slow” but not any slower than on any other card. Remember that all the glGet[Integer,Float,Double,…]v commands all go through a huge switch statement, because the first argument can be so many things. That’s the real overhead.

Never use glGet of ANYTHING if you care about performance. Always shadow the state in your app if you will be needing it. This also applies to glIsEnabled, glGetTexParameter[i,f]v, etc.

• Matt