Jump to content
  • Advertisement
Sign in to follow this  
n0obAtroN

OpenGL OpenGL Frustum Culling Problem

This topic is 3317 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Advertisement
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.)

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
The Modelview matrix isn't orthogonal.
So invert != transposed matrix
SORRY!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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;
}

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!