Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
31 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to Graphics and GPU Programming

OpenGL Frustum Culling Problem

Started by
24 comments, last by n0obAtroN 14 years, 10 months ago
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]
Advertisement
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!
[size=2]Portfolio [size=2]| Youtube channel | Paper modeller development blog | Journal
The Modelview matrix isn't orthogonal.
So invert != transposed matrix
SORRY!
[size=2]Portfolio [size=2]| Youtube channel | Paper modeller development blog | Journal
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.
[size=2]Portfolio [size=2]| Youtube channel | Paper modeller development blog | Journal
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...

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

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

This topic is closed to new replies.

Advertisement

Popular Topics

Aybe One
How do you manage yourself and your time as years pass on? GDNet Lounge
Jikoob
Too many managers? General and Gameplay Programming
ReignOnU
Do your part to stop global warming and climate change GDNet Lounge
Konjointed
C++ how do you use dependency injection? For Beginners
aigan
The promise of freedom in story games Game Design and Theory
robertrobert
Facebook Ads for sales on steam, does it work? Games Business and Law
Advertisement

Recommended Tutorials

Carsten Germer
"Not So Random Randomness" in Game Design and Programming Game Design and Theory
Myopic Rhino
Visual Studio Macros for the Game Programmer General and Gameplay Programming
Myopic Rhino
Code on the Cob Part 9 General and Gameplay Programming
David Xicota
How to Expand Games (and more) Eluding App Store Updating Production and Management
Myopic Rhino
Handy PC/Mac OS X Snippets for Indie Development General and Gameplay Programming

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top