Archived

This topic is now archived and is closed to further replies.

Frank Henry

Need Help with Frustum Culling

Recommended Posts

Hi all. I seem to be having problems with Frustum Culling after using gluLookAt. using digiben''s and mark morley''s tutorials here''s the basic rundown: translate to pos rotate translate to chase pos get modelview matrix load identity glulookat (using the pos contained in the modelview matrix and whatever i am looking at) then i basicly do like the tutorials say. only exception is that i am using objects for the planes and matrices. problem is i get wierd results! portions that are in the frustum are getting culled, others are not. could it be that glulookat is screwing up something? code can be sent on demand only. thanks frank

Share this post


Link to post
Share on other sites
I think you should do :

glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
gluLookAt(...);
draw_the_scene_from_here();

If you go to the camera pos and chase something manually, I don''t see why gluLookAt should be called.

Share this post


Link to post
Share on other sites
hi,

thanks for anwering. :-)
It is supposed to be a ChaseCam.
i use the pre-load identity matrix to determine the cam position.
detailed:
translate and rotate based on object info
then translate to cam-pos
get modelview matrix to get the real pos of the cam
load identity
gluLookAt (real cam pos, object position, up-vector)
(this also saves me from calculating the angle i have to rotate downward)
then do the frustum stuff.

or is there a better way?

i''ll try your suggestions tonight.

thanks

frank

Share this post


Link to post
Share on other sites
Ok. Now I see a bit better what you want to do.

The algorithm seems ok to me.
There are just two things you have to take care about getting the camera position from the modelview matrix :
1- you have to "apply" (eg multiply) the modelview matrix on the vector (0,0,0,1), and then divide the resulting x, and z with w.
2- you have to take care of OpenGL''s "transposed" matrix specification (eg columns are stored first, not rows).


> portions that are in the frustum are getting culled, others are not.

1- What kind of frustum operations do you perform ? (backface culling, frustum clipping, ...)

2- And on which frustum ? The one defined by OpenGL''s modelview and projection matrices ? Or the one that you compute yourself from object''s and camera''s positions ?

Share this post


Link to post
Share on other sites
thanks again for replying.
I''m going totally batty here! ;-)

1- you have to "apply" (eg multiply) the modelview matrix on the vector (0,0,0,1), and then divide the resulting x, and z with w.

what vector would that be?

2- you have to take care of OpenGL''s "transposed" matrix specification (eg columns are stored first, not rows).

do i have to transpose them?
i''ll try and post again later!

> portions that are in the frustum are getting culled, others are not.

1- What kind of frustum operations do you perform ? (backface culling, frustum clipping, ...)

frustum clipping, ifaik.
in the code i test to see if a point is in the frustum,
if not it is not clipped.

2- And on which frustum ? The one defined by OpenGL''s modelview and projection matrices ? Or the one that you compute yourself from object''s and camera''s positions ?

the latter, yes.

thanks

frank

here''s the frustum code:

float CFrustum::GetMagnitude (const int Plane)
{
return (float) this->Frustum[Plane].N.Length();
}

void CFrustum::ResetFrustum ()
{
this->ModelMatrix.Clear();
glGetFloatv(GL_MODELVIEW_MATRIX, this->ModelMatrix.m);
this->ModelMatrix.Print("ModelMatrix");

this->ProjectionMatrix.Clear();
glGetFloatv(GL_PROJECTION_MATRIX, this->ProjectionMatrix.m);
this->ProjectionMatrix.Print("ProjectionMatrix");

this->Clip = this->ModelMatrix * this->ProjectionMatrix;
this->Clip.Print("ClipMatrix");

// Right
this->Frustum[RIGHT].N = CVector (Clip.m[ 3] - Clip.m[ 0],
Clip.m[ 7] - Clip.m[ 4],
Clip.m[11] - Clip.m[ 8]);
this->Frustum[RIGHT].N.Normalize ();

this->Frustum[RIGHT].D = Clip.m[15] - Clip.m[12];
this->Frustum[RIGHT].D /= GetMagnitude(RIGHT);
this->Frustum[RIGHT].Print ("Right");

// Left
this->Frustum[LEFT].N = CVector (Clip.m[ 3] + Clip.m[ 0],
Clip.m[ 7] + Clip.m[ 4],
Clip.m[11] + Clip.m[ 8]);
this->Frustum[LEFT].N.Normalize ();

this->Frustum[LEFT].D = Clip.m[15] + Clip.m[12];
this->Frustum[LEFT].D /= GetMagnitude(LEFT);
this->Frustum[LEFT].Print ("Left");

// BOTTOM
this->Frustum[BOTTOM].N = CVector (Clip.m[ 3] - Clip.m[ 1],
Clip.m[ 7] - Clip.m[ 5],
Clip.m[11] - Clip.m[ 9]);
this->Frustum[BOTTOM].N.Normalize ();

this->Frustum[BOTTOM].D = Clip.m[15] - Clip.m[13];
this->Frustum[BOTTOM].D /= GetMagnitude(BOTTOM);
this->Frustum[BOTTOM].Print ("Bottom");

// TOP
this->Frustum[TOP].N = CVector (Clip.m[ 3] + Clip.m[ 1],
Clip.m[ 7] + Clip.m[ 5],
Clip.m[11] + Clip.m[ 9]);
this->Frustum[TOP].N.Normalize ();

this->Frustum[TOP].D = Clip.m[15] + Clip.m[13];
this->Frustum[TOP].D /= GetMagnitude(TOP);
this->Frustum[TOP].Print ("Top");

// BACK
this->Frustum[BACK].N = CVector (Clip.m[ 3] - Clip.m[ 2],
Clip.m[ 7] - Clip.m[ 6],
Clip.m[11] - Clip.m[10]);
this->Frustum[BACK].N.Normalize ();

this->Frustum[BACK].D = Clip.m[15] - Clip.m[14];
this->Frustum[BACK].D /= GetMagnitude(BACK);
this->Frustum[BACK].Print ("BACK");

// FRONT
this->Frustum[FRONT].N = CVector (Clip.m[ 3] + Clip.m[ 2],
Clip.m[ 7] + Clip.m[ 6],
Clip.m[11] + Clip.m[10]);
this->Frustum[FRONT].N.Normalize ();

this->Frustum[FRONT].D = Clip.m[15] + Clip.m[14];
this->Frustum[FRONT].D /= GetMagnitude(FRONT);
this->Frustum[FRONT].Print ("FRONT");
}

bool CFrustum:ointInFrustum (const CVector Point)
{
return true;

// RIGHT
// Calculate the plane equation and check if the point is behind a side of the frustum
if(this->Frustum[RIGHT].N.x * Point.x +
this->Frustum[RIGHT].N.y * Point.y +
this->Frustum[RIGHT].N.z * Point.z +
this->Frustum[RIGHT].D <= 0)
// The point was behind a side, so it ISN''T in the frustum
return false;

// goes like this for all sides!

}


Share this post


Link to post
Share on other sites
> > 1- you have to "apply" (eg multiply) the modelview
> > matrix on the vector (0,0,0,1), and then divide the
> > resulting x, and z with w.
>
> what vector would that be?

That would be the coordinates of the origin of the camera in "world" coordinates.


> > 2- you have to take care of OpenGL''s "transposed"
> > matrix specification (eg columns are stored first
> > not rows).
>
> do i have to transpose them?

In fact, "standard" matrix 4x4 are represented so that the first 4 elements define the 1st row. In OpenGL, the first 4 elements define the 1st column.


  
this->ModelMatrix.Clear();
glGetFloatv(GL_MODELVIEW_MATRIX, this->ModelMatrix.m);
this->ModelMatrix.Print("ModelMatrix");

this->ProjectionMatrix.Clear();
glGetFloatv(GL_PROJECTION_MATRIX, this->ProjectionMatrix.m);
this->ProjectionMatrix.Print("ProjectionMatrix");

you clear the matrices before getting them ?
What do you mean by "clear" ? does that load the identity matrix ?


  
this->Clip = this->ModelMatrix * this->ProjectionMatrix;
this->Clip.Print("ClipMatrix");

I think the clipping matrix is ( Projection * ModelView ). That may be your problem.



Moreover, I suggest to clip the frustum using OpenGL''s method, which is faster IMO.
Once you have your clipping matrix "Clip", for a vertex "V", compute the projection of the vertex in the clip volume as ( Clip * V ). You get a vector of 4 elements (Xc, Yc, Zc, Wc). OpenGL specifies :
quote:

Primitives are clipped to the clip volume. In clip coordinates, the view volume is defined by
-wc <= xc <= wc
-wc <= yc <= wc
-wc <= zc <= wc



So, to test a vertex you have to process :
- 16 products,
- 12 additions,
- and 1 test (at best) up to 6 tests (at worst).

Share this post


Link to post
Share on other sites
>That would be the coordinates of the origin of the camera in "world" coordinates.

when would i have to do this? (totally lost somehow!)

>In fact, "standard" matrix 4x4 are represented so that the first 4 elements define the 1st row. In OpenGL, the first 4 elements define the 1st column.

I tryed and transposing them but it really went wierd then.
probably because the clip-calculation is already opengl-matix compliant.

>What do you mean by "clear" ? does that load the identity matrix ?

no.
the clear method just erases the contents.
cheaper then a memset.

>I think the clipping matrix is ( Projection * ModelView ). That may be your problem.

really?
i used the code from mark and digiben to calculate it.
basicly instead of clip = modelview * projection
they insert the portion from the matrix *-operator

>Moreover, I suggest to clip the frustum using OpenGL''s method, which is faster IMO.

sorry, can you be more specific?
(i''m havin a bad day today! ;-)

thanks again for the help

frank

Share this post


Link to post
Share on other sites
it looks like I''m going into an explanation course

I suggest you to do this :

Define identifiers
GLfloat modelview[16];
GLfloat projection[16];
GLfloat clip[16];
GLfloat cam_origin[3];

Set the camera at one frame
translate and rotate based on object info
then translate to cam-pos
glGetFloatv(GL_MODELVIEW_MATRIX, modelview); // get modelview matrix to get the real pos of the cam
cam_origin[0] = modelview[12] / modelview[15];
cam_origin[1] = modelview[13] / modelview[15];
cam_origin[2] = modelview[14] / modelview[15];
load identity
gluLookAt (real cam pos, object position, up-vector)
glGetFloatv(GL_MODELVIEW_MATRIX, modelview);
glGetFloatv(GL_PROJECTION_MATRIX, projection);
// Compute clip = projection * modelview
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
clip[ i ][ j ] = 0.0f;
for(int k=0;k<4;k++) clip[ i ][ j ] += projection[ k ][ i ] * modelview[ j ][ k ];
}
then do the frustum stuff.

Frustum testing
bool isInFrustum(GLfloat point[3])
{
GLfloat projected_point[4]; // (xc,yc,zc,wc)
projected_point[0] = point[0]*clip[0]+point[1]*clip[4]+point[2]*clip[8]+clip[12];
projected_point[1] = point[0]*clip[1]+point[1]*clip[5]+point[2]*clip[9]+clip[13];
projected_point[2] = point[0]*clip[2]+point[1]*clip[6]+point[2]*clip[10]+clip[14];
projected_point[3] = point[0]*clip[3]+point[1]*clip[7]+point[2]*clip[11]+clip[15];
return (-projected_point[3]<=projected_point[0]) && (projected_point[0]<=projected_point[3]) // -wc <= xc <= wc
&& (-projected_point[3]<=projected_point[1]) && (projected_point[1]<=projected_point[3]) // -wc <= yc <= wc
&& (-projected_point[3]<=projected_point[2]) && (projected_point[2]<=projected_point[3]) // -wc <= zc <= wc
}


The ''clip'' identifier has to be global, or a member of a class, and has to be computed every time the frustum changes (either the camera moves/rotates, or the window size changes)

Hope this helps

Share this post


Link to post
Share on other sites
Sorry I wrote matrices like they were [][] when they were [].
The algorithm works.
I missed one transposition, though. that''s why it didn''t work.

for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
{
this->Clip[ j*4 + i ] = 0.0f;
for (int k = 0; k < 4; k++)
{
this->Clip[ j*4 + i ] += this->ProjectionMatrix.m[ k*4 + i ] * this->ModelMatrix.m[ j*4 + k ];
}
}

ps: do NOT do that (that''s what you wrote) :
for (int k = 0; k < 4; k++)
{
this->Clip[ i*4 + j ] = 0.0f;
this->Clip[ i*4 + j ] += this->ProjectionMatrix.m[ k*4 + i ] * this->ModelMatrix.m[ j*4 + k ];
}
Because in that case you reset the matrix element at each iteration, thus making the addition useless.
(note that clip''s index is wrong too : but that was my mistake)

Conclusion : the algorithm works. That was just the implementation that had one *little* (too much, though) mistake.

btw your engine looks great.
I debugged it with ease. It''s really a nice work.
I would have wasted a lot of time if the engine was not so clean.
Congratulations !

Share this post


Link to post
Share on other sites