   OpenGL Frustum Culling Problem
  Hello everybody.  I have a rather complex scene I want to cull via the frustum.  However, for some strange reason my implementation is not working (nothing is drawn).  I have looked at *many* of other people implementations, and it seems as if they are identical to mine.Here are my various data structures:struct Plane{    f32 a, b, c, d;};struct Matrix4x4{    f32 m[16];};struct vector3df{    f32 x, y, z;};Here are various mathematical functions:FASTCALL struct Matrix4x4 multiplyMatrix4x4(struct Matrix4x4 a, struct Matrix4x4 b){    struct Matrix4x4 c;c.m[0]  = a.m[0] * b.m[0] + a.m[1] * b.m[4] + a.m[2] * b.m[8] + a.m[3] * b.m[12];c.m[1]  = a.m[0] * b.m[1] + a.m[1] * b.m[5] + a.m[2] * b.m[9] + a.m[3] * b.m[13];c.m[2]  = a.m[0] * b.m[2] + a.m[1] * b.m[6] + a.m[2] * b.m[10] + a.m[3] * b.m[14];c.m[3]  = a.m[0] * b.m[3] + a.m[1] * b.m[7] + a.m[2] * b.m[11] + a.m[3] * b.m[15];c.m[4]  = a.m[4] * b.m[0] + a.m[5] * b.m[4] + a.m[6] * b.m[8] + a.m[7] * b.m[12];c.m[5]  = a.m[4] * b.m[1] + a.m[5] * b.m[5] + a.m[6] * b.m[9] + a.m[7] * b.m[13];c.m[6]  = a.m[4] * b.m[2] + a.m[5] * b.m[6] + a.m[6] * b.m[10] + a.m[7] * b.m[14];c.m[7]  = a.m[4] * b.m[3] + a.m[5] * b.m[7] + a.m[6] * b.m[11] + a.m[7] * b.m[15];c.m[8]  = a.m[8] * b.m[0] + a.m[9] * b.m[4] + a.m[10] * b.m[8] + a.m[11] * b.m[12];c.m[9]  = a.m[8] * b.m[1] + a.m[9] * b.m[5] + a.m[10] * b.m[9] + a.m[11] * b.m[13];c.m[10] = a.m[8] * b.m[2] + a.m[9] * b.m[6] + a.m[10] * b.m[10] + a.m[11] * b.m[14];c.m[11] = a.m[8] * b.m[3] + a.m[9] * b.m[7] + a.m[10] * b.m[11] + a.m[11] * b.m[15];c.m[12] = a.m[12] * b.m[0] + a.m[13] * b.m[4] + a.m[14] * b.m[8] + a.m[15] * b.m[12];c.m[13] = a.m[12] * b.m[1] + a.m[13] * b.m[5] + a.m[14] * b.m[9] + a.m[15] * b.m[13];c.m[14] = a.m[12] * b.m[2] + a.m[13] * b.m[6] + a.m[14] * b.m[10] + a.m[15] * b.m[14];c.m[15] = a.m[12] * b.m[3] + a.m[13] * b.m[7] + a.m[14] * b.m[11] + a.m[15] * b.m[15];    return c;}FASTCALL void normalizePlane(struct Plane * plane){    f32 mag = sqrtf(plane->a * plane->a + plane->b * plane->b + plane->c * plane->c);    if(mag)    {   plane->a /= mag;   plane->b /= mag;   plane->c /= mag;   plane->d /= mag;    }}Here is the global frustum planes declaration:struct Plane frustumPlane[6];Here is the frustum extraction function:FASTCALL void updateFrustum(){    struct Matrix4x4 proj, modl, clip;    struct Plane * p;    glPushMatrix();    glLoadIdentity();    glGetFloatv(GL_PROJECTION_MATRIX, &proj.m[0]);    glGetFloatv(GL_MODELVIEW_MATRIX, &modl.m[0]);    glPopMatrix();    clip = multiplyMatrix4x4(proj, modl);    printf("{%f, %f, %f, %f\n %f, %f, %f, %f\n %f, %f, %f, %f\n %f, %f, %f, %f}\n\n", clip.m[0], clip.m[1], clip.m[2], clip.m[3], clip.m[4], clip.m[5], clip.m[6], clip.m[7], clip.m[8], clip.m[9], clip.m[10], clip.m[11], clip.m[12], clip.m[13], clip.m[14], clip.m[15]);    p = &frustumPlane;    p->a = clip.m[3]  - clip.m[0];    p->b = clip.m[7]  - clip.m[4];    p->c = clip.m[11] - clip.m[8];    p->d = clip.m[15] - clip.m[12];    p = &frustumPlane;    p->a = clip.m[3]  + clip.m[0];    p->b = clip.m[7]  + clip.m[4];    p->c = clip.m[11] + clip.m[8];    p->d = clip.m[15] + clip.m[12];    p = &frustumPlane[BOTTOM];    p->a = clip.m[3]  + clip.m[1];    p->b = clip.m[7]  + clip.m[5];    p->c = clip.m[11] + clip.m[9];    p->d = clip.m[15] + clip.m[13];    p = &frustumPlane[TOP];    p->a = clip.m[3]  - clip.m[1];    p->b = clip.m[7]  - clip.m[5];    p->c = clip.m[11] - clip.m[9];    p->d = clip.m[15] - clip.m[13];    p = &frustumPlane[BACK];    p->a = clip.m[3]  - clip.m[2];    p->b = clip.m[7]  - clip.m[6];    p->c = clip.m[11] - clip.m[10];    p->d = clip.m[15] - clip.m[14];    p = &frustumPlane[FRONT];    p->a = clip.m[3]  + clip.m[2];    p->b = clip.m[7]  + clip.m[6];    p->c = clip.m[11] + clip.m[10];    p->d = clip.m[15] + clip.m[14];    u8 i;    for (i = 0; i < 6; i++)   normalizePlane(&frustumPlane);}Here is the function to test if a vertex is in the frustum:FASTCALL bool isVector3dfInFrustum(struct vector3df d){    if(frustumPlane.a * d.x + frustumPlane.b * d.y + frustumPlane.c * d.z + frustumPlane.d > 0)   return false;    if(frustumPlane.a * d.x + frustumPlane.b * d.y + frustumPlane.c * d.z + frustumPlane.d > 0)   return false;    if(frustumPlane[BACK].a * d.x + frustumPlane[BACK].b * d.y + frustumPlane[BACK].c * d.z + frustumPlane[BACK].d > 0)   return false;    if(frustumPlane[FRONT].a * d.x + frustumPlane[FRONT].b * d.y + frustumPlane[FRONT].c * d.z + frustumPlane[FRONT].d > 0)   return false;    if(frustumPlane[TOP].a * d.x + frustumPlane[TOP].b * d.y + frustumPlane[TOP].c * d.z + frustumPlane[TOP].d > 0)   return false;    if(frustumPlane[BOTTOM].a * d.x + frustumPlane[BOTTOM].b * d.y + frustumPlane[BOTTOM].c * d.z + frustumPlane[BOTTOM].d > 0)   return false;    return true;}And a simple test case scenario:    glBegin(GL_POINTS);    glPointSize(5.0f);    s32 x, y, z;    u32 count = 0;    for(x = -100; x < 100; x++)   for(y = -100; y < 100; y++)  for(z = -100; z < 100; z++) if(isVector3dfInFrustum(makeVector3df(x, y, z))) {glVertex3i(x, y, z);count++; }    glEnd();    printf("%lu\n", count);This test case scenario renders 0 of the points, regardless of the camera orientation.  Any ideas on what I might be doing wrong?[Edited by - n0obAtroN on June 10, 2009 2:39:47 AM]
  Edited last post, added test case scenario.Anyone?   ;  Couple of things:1. In updateFrustum(), you're not setting the matrix mode before pushing the matrix stack, so it's not clear which stack is being manipulated. Also, since you're loading the identity matrix before querying for the projection and modelview matrices, I would think that one of the two would always come back as identity (which would definitely be wrong in the case of the projection matrix, and is likely to be wrong in the case of the modelview matrix).2. I'd recommend creating a separate function for testing a point against a plane rather than writing the test out manually each time; this will help avoid typos and copy-and-paste errors.Frustum culling code (especially based on this particular algorithm), as well as math library code in general, is difficult to debug just by looking at it; a single typo (such as a wrong index in a matrix multiplication function) can throw the whole thing off.Testing the functions and components individually can help. With frustum culling, I recommend confirming visually that the frustum planes are correct before moving on to culling. It can be a bit of a pain to set up, but a fairly straightforward way to generate debug graphics for the frustum is to intersect the planes in sets of three to yield the corners of the frustum, and then render the 6 quadrilaterals making up the frustum. (You'll most likely need to attach the frustum to an object other than the camera in order to see the debug graphics clearly.)   ;  Hi all!I have a similar problem:I want to calculate the points of the View frustum (after the transformations of course).I just don't know why it isn't working.Calculating code:float MVM[16];void Calc_Frustum(){float pt[16] = {0,0,0,1,  0,0,0,1,  0,0,0,1,  1,1,1,1};float out[16];float inv_MVM[16];glGetFloatv(GL_MODELVIEW_MATRIX, MVM);MatrixTranspose(MVM,inv_MVM);for( int i = 0; i < 5; i++ ){pt[0] = Frustum_Points[0];pt[1] = Frustum_Points[1];pt[2] = Frustum_Points[2];MatrixMult(inv_MVM,pt,out);Frustum_Tarnsformed_Points[0] = out[0];Frustum_Tarnsformed_Points[1] = out[1];Frustum_Tarnsformed_Points[2] = out[2];}}void MatrixMult(float *in,float *in2, float *out){out[ 0] = in[0]*in2[0]+in[4]*in2[1]+in[8]*in2[2]+in[12]*in2[3];out[ 1] = in[1]*in2[0]+in[5]*in2[1]+in[9]*in2[2]+in[13]*in2[3];out[ 2] = in[2]*in2[0]+in[6]*in2[1]+in[10]*in2[2]+in[14]*in2[3];out[ 3] = in[3]*in2[0]+in[7]*in2[1]+in[11]*in2[2]+in[15]*in2[3];out[ 4] = in[0]*in2[4]+in[4]*in2[5]+in[8]*in2[6]+in[12]*in2[7];out[ 5] = in[1]*in2[4]+in[5]*in2[5]+in[9]*in2[6]+in[13]*in2[7];out[ 6] = in[2]*in2[4]+in[6]*in2[5]+in[10]*in2[6]+in[14]*in2[7];out[ 7] = in[3]*in2[4]+in[7]*in2[5]+in[11]*in2[6]+in[15]*in2[7];out[ 8] = in[0]*in2[8]+in[4]*in2[9]+in[8]*in2[10]+in[12]*in2[11];out[ 9] = in[1]*in2[8]+in[5]*in2[9]+in[9]*in2[10]+in[13]*in2[11];out[10] = in[2]*in2[8]+in[6]*in2[9]+in[10]*in2[10]+in[14]*in2[11];out[11] = in[3]*in2[8]+in[7]*in2[9]+in[11]*in2[10]+in[15]*in2[11];out[12] = in[0]*in2[12]+in[4]*in2[13]+in[8]*in2[14]+in[12]*in2[15];out[13] = in[1]*in2[12]+in[5]*in2[13]+in[9]*in2[14]+in[13]*in2[15];out[14] = in[2]*in2[12]+in[6]*in2[13]+in[10]*in2[14]+in[14]*in2[15];out[15] = in[3]*in2[12]+in[7]*in2[13]+in[11]*in2[14]+in[15]*in2[15];} This works well in any other places.void MatrixTranspose(float *in, float *out){out[ 0] = in[0];out[ 1] = in[4];out[ 2] = in[8];out[ 3] = in[12];out[ 4] = in[1];out[ 5] = in[5];out[ 6] = in[9];out[ 7] = in[13];out[ 8] = in[2];out[ 9] = in[6];out[10] = in[10];out[11] = in[14];out[12] = in[3];out[13] = in[7];out[14] = in[11];out[15] = in[15];}The Calc_Frustum() is called at the proper place in the main code, look at the glLoadMatrixf(MVM) for the debugging....SetupView();Calc_Frustum();glLoadMatrixf(MVM); // its unnecessary//drawing stuff...Drawing the calculated frustum points:...glLoadMatrixf(MVM);Draw_Frustum();...There are no transformations in Draw_Frustum(), just drawing the lines. If the calculation is correct, the frustum should appear as a screen sized rectangle, regardless of the camera orientation.The rotations apply, but the translations don't, so I see the rectangle, but its position is changing.Maybe matrix representation of the points are wrong? Or I shouldn't invert the modelview matrix? Or something totally wrong here...Thanks!;  The Modelview matrix isn't orthogonal.So invert != transposed matrixSORRY!   ;  The matrix stack being manipulated in updateFrustum() is the modelview matrix (GL_MODELVIEW).   ;  You should try to draw the frustum. This isn't easy, try to draw the normals of the side planes, then draw the front and back planes as Quads with different colors and backface culling enabled. So you can determine if the orientations are good.Or you could try (if you haven't yet) to comment all the statements in the isVector3dfInFrustum() function, so the points always pass, then uncomment the statements one by one, and just one at a time. Because if one of them is incorrect, the points will always fail.The glLoadIdentity() in the updateFrustum() isn't clear for me.   ;  I have updated the code to try to eliminate typos.  Here it is:#define calculateFrustumPlane(a, b, c)for(i = 0; i < 4; i++)    p->d =  clip.m[a + i * 4] b clip.m[c + i * 4]FASTCALL void updateFrustum(){    struct Matrix4x4 proj, modl, clip;    struct Plane * p;    u8 i; // used in calculateFrustumPlane() macro    glMatrixMode(GL_MODELVIEW);    glPushMatrix();    glGetFloatv(GL_PROJECTION_MATRIX, &proj.m[0]);    glGetFloatv(GL_MODELVIEW_MATRIX, &modl.m[0]);    glPopMatrix();    clip = multiplyMatrix4x4(proj, modl);    p = &frustumPlane;    calculateFrustumPlane(3, -, 0);    p = &frustumPlane;    calculateFrustumPlane(3, +, 0);    p = &frustumPlane[BOTTOM];    calculateFrustumPlane(3, +, 1);    p = &frustumPlane[TOP];    calculateFrustumPlane(3, -, 1);    p = &frustumPlane[BACK];    calculateFrustumPlane(3, -, 2);    p = &frustumPlane[FRONT];    calculateFrustumPlane(3, +, 2);    for (i = 0; i < 6; i++)   normalizePlane(&frustumPlane);}FASTCALL bool isVector3dfInFrustum(struct vector3df d){    u8 i;    for(i = 0; i < 6; i++)   if(frustumPlane[BOTTOM].d[0] * d.x + frustumPlane[BOTTOM].d[1] * d.y + frustumPlane[BOTTOM].d[2] * d.z + frustumPlane[BOTTOM].d[3] > 0)  return false;    return true;};  Now you are only testing against a single frustum plane...   ;  As noted above, you're testing against the same plane each time through the loop. Also, you should really make the point-plane test a function; using a loop to eliminate some of the redundant code is a good start, but it would make much more sense to make this a separate function that can be tested in isolation and used elsewhere in your code if needed.I would also advise against making calculateFrustumPlane a macro. It looks like you're programming in pure C (where use of macros is a little more defensible than in C++), but there are still better, safer alternatives to using a macro (for example, you could use a function rather than a macro, and use a function pointer to abstract away the summation operation).   