Jump to content
  • Advertisement
Sign in to follow this  
STORM76

OpenGL Frustum plane extraction in OpenGL

This topic is 4672 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

Hi there, I got stuck with my frustum culling code in my little OpenGL 3D engine project for a while now and would like to ask if someone can provide me with a working excerpt of frustum plane extraction code in OpenGL. I am a little bit confused on the input matrix whether it should be a combination of the projection and modelview matrix or just the modelview matrix and so on. That would be great:-) Thanks in advance, Guido

Share this post


Link to post
Share on other sites
Advertisement
The input matrix is projection * modelview. This reflects OpenGL's column vector order, and that the vertex is transformed first by the modelview matrix and then by the projection matrix. Intuitively, the projection matrix must be involved as without it you would have no information about the location of the frustum planes in camera space.

Gotta go now, but I have code I could post later if you still need help with this.

Share this post


Link to post
Share on other sites
I stole this from Beginning OpenGL Game Programming.

void Camera::ExtractPlane(PLANE &plane, GLfloat *mat, int row)
{
int scale = (row < 0) ? -1 : 1;
row = abs(row) - 1;

plane.A = mat[3] + scale * mat[row];
plane.B = mat[7] + scale * mat[row + 4];
plane.C = mat[11] + scale * mat[row + 8];
plane.D = mat[15] + scale * mat[row + 12];

float length = sqrtf(plane.A * plane.A + plane.B * plane.B + plane.C * plane.C);

plane.A /= length;
plane.B /= length;
plane.C /= length;
plane.D /= length;
}

void Camera::CalculateFrustum() {

float MV[16];
glGetFloatv(GL_MODELVIEW_MATRIX, MV);
float PM[16];
glGetFloatv(GL_PROJECTION_MATRIX, PM);

glPushMatrix();
glLoadMatrixf(PM);
glMultMatrixf(MV);
glGetFloatv(GL_MODELVIEW_MATRIX, MV);
glPopMatrix();

ExtractPlane(view_frustum

, MV, 1);
ExtractPlane(view_frustum

, MV, -1);
ExtractPlane(view_frustum[BOTTOM], MV, 2);
ExtractPlane(view_frustum[TOP], MV, -2);
ExtractPlane(view_frustum[NEAR], MV, 3);
ExtractPlane(view_frustum[FAR], MV, -3);

return;
}[/src]

Share this post


Link to post
Share on other sites
Yes, if you have some code, that would be great. I have tested alreday the combined matrix projection * modelview; it seems that I do something different wrong?!

Thanks,
Guido

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Gotta go now, but I have code I could post later if you still need help with this.


Alternatively, you could post your own code and I can look at it now :)

Tom

Share this post


Link to post
Share on other sites
Here's some more code for you to refer to. This extracts the planes using column-vector order and [-1,1] z-clipping as per OpenGL convention. If you're using 1d indexing, you'll have to convert from the 2d indexing used here.


template <class T> void Matrix4<T>::ExtractFrustumPlanes(T planes[6][4], bool normalize) const
{
// Left: [30+00, 31+01, 32+02, 33+03]

planes[0][0] = m_(3, 0) + m_(0, 0);
planes[0][1] = m_(3, 1) + m_(0, 1);
planes[0][2] = m_(3, 2) + m_(0, 2);
planes[0][3] = m_(3, 3) + m_(0, 3);

// Right: [30-00, 31-01, 32-02, 33-03]

planes[1][0] = m_(3, 0) - m_(0, 0);
planes[1][1] = m_(3, 1) - m_(0, 1);
planes[1][2] = m_(3, 2) - m_(0, 2);
planes[1][3] = m_(3, 3) - m_(0, 3);

// Bottom: [30+10, 31+11, 32+12, 33+13]

planes[2][0] = m_(3, 0) + m_(1, 0);
planes[2][1] = m_(3, 1) + m_(1, 1);
planes[2][2] = m_(3, 2) + m_(1, 2);
planes[2][3] = m_(3, 3) + m_(1, 3);

// Top: [30-10, 31-11, 32-12, 33-13]

planes[3][0] = m_(3, 0) - m_(1, 0);
planes[3][1] = m_(3, 1) - m_(1, 1);
planes[3][2] = m_(3, 2) - m_(1, 2);
planes[3][3] = m_(3, 3) - m_(1, 3);

// Far: [30-20, 31-21, 32-22, 33-23]

planes[5][0] = m_(3, 0) - m_(2, 0);
planes[5][1] = m_(3, 1) - m_(2, 1);
planes[5][2] = m_(3, 2) - m_(2, 2);
planes[5][3] = m_(3, 3) - m_(2, 3);

// Near: [30+20, 31+21, 32+22, 33+23]

planes[4][0] = m_(3, 0) + m_(2, 0);
planes[4][1] = m_(3, 1) + m_(2, 1);
planes[4][2] = m_(3, 2) + m_(2, 2);
planes[4][3] = m_(3, 3) + m_(2, 3);

// Normalize
if (normalize)
{
for (int i = 0; i < 6; ++i)
{
T invl = Math<T>::InvSqrt(planes[0] * planes[0] +
planes[1] * planes[1] +
planes[2] * planes[2]);

planes[0] *= invl;
planes[1] *= invl;
planes[2] *= invl;
planes[3] *= invl;
}
}
}


This isn't production-quality code, but it should work. I did have to do a little cutting and pasting to post the example, so I suppose I could have messed something up. Anyway, here are some 'gotchas' that can cause problems when using this algorithm:

1. You have to make sure you're treating the plane normals as 'pointing' in the right direction. (I can't remember off the top of my head whether the algorithm extracts them pointing 'in' or 'out' of the frustum volume.)

2. The planes are not normalized on extraction by default. Note that I added normalization code in the above example.

3. The planes are in p.n+d = 0 form by default, so if you're trying to use them in p.n = d form without converting first, it probably won't work as you expect.

Share this post


Link to post
Share on other sites
Quote:
Original post by dimebolt
Quote:
Original post by jyk
Gotta go now, but I have code I could post later if you still need help with this.


Alternatively, you could post your own code and I can look at it now :)

Tom


Here is my code to extract and update the six frustum planes:


void Frustum::Update(Matrix4x4f& comboMatrix)
{
/*
column-majored matrix form:

0 4 8 12
1 5 9 13
2 6 10 14
3 7 11 15
*/


// left clipping plane:
planes_[0].n.x = comboMatrix.m[12] + comboMatrix.m[0];
planes_[0].n.y = comboMatrix.m[13] + comboMatrix.m[1];
planes_[0].n.z = comboMatrix.m[14] + comboMatrix.m[2];
planes_[0].d = comboMatrix.m[15] + comboMatrix.m[3];

// right clipping plane:
planes_[1].n.x = comboMatrix.m[12] - comboMatrix.m[0];
planes_[1].n.y = comboMatrix.m[13] - comboMatrix.m[1];
planes_[1].n.z = comboMatrix.m[14] - comboMatrix.m[2];
planes_[1].d = comboMatrix.m[15] - comboMatrix.m[3];

// top clipping plane:
planes_[2].n.x = comboMatrix.m[12] - comboMatrix.m[4];
planes_[2].n.y = comboMatrix.m[13] - comboMatrix.m[5];
planes_[2].n.z = comboMatrix.m[14] - comboMatrix.m[6];
planes_[2].d = comboMatrix.m[15] - comboMatrix.m[7];

// bottom clipping plane:
planes_[3].n.x = comboMatrix.m[12] + comboMatrix.m[4];
planes_[3].n.y = comboMatrix.m[13] + comboMatrix.m[5];
planes_[3].n.z = comboMatrix.m[14] + comboMatrix.m[6];
planes_[3].d = comboMatrix.m[15] + comboMatrix.m[7];

// near clipping plane:
planes_[4].n.x = comboMatrix.m[12] + comboMatrix.m[8];
planes_[4].n.y = comboMatrix.m[13] + comboMatrix.m[9];
planes_[4].n.z = comboMatrix.m[14] + comboMatrix.m[10];
planes_[4].d = comboMatrix.m[15] + comboMatrix.m[11];

// far clipping plane:
planes_[5].n.x = comboMatrix.m[12] - comboMatrix.m[8];
planes_[5].n.y = comboMatrix.m[13] - comboMatrix.m[9];
planes_[5].n.z = comboMatrix.m[14] - comboMatrix.m[10];
planes_[5].d = comboMatrix.m[15] - comboMatrix.m[11];

for (int i = 0; i < 6; ++i) {
NormalizePlane(planes_);
}
}



On a per frame basis I update the frustum with this:


glGetFloatv(GL_PROJECTION_MATRIX, projMatrix.m);
glGetFloatv(GL_MODELVIEW_MATRIX, viewMatrix.m);
comboMatrix = viewMatrix * projMatrix;
frustum_.Update(comboMatrix);



I received the plane extraction code from a white paper from Gil Gribb (Ravensoft) and Klaus Hartmann (title: "Fast Extraction of Viewing Frustum Planes from the World-View-Projection Matrix"). I debugged already the code for a simple point-intersection test and found out that the near plane may be the problem. I use the following code to classify a point:


inline Halfspace Frustum::ClassifyPoint(const Planef& plane, const Vector3f& point) const
{
float d = plane.n.x * point.x + plane.n.y * point.y + plane.n.z * point.z + plane.d;

if (d < 0) {
return NEGATIVE;
}

if (d > 0) {
return POSITIVE;
}

return ON_PLANE;
}



Hope this helps. Thanks in advance!

Cheers,
Guido

Share this post


Link to post
Share on other sites
You plane extraction looks wrong- It seems you've transposed the matrix indices (ie. 1 becomes 4.) If it helps, my code looks like this:


left.x = projection.data[3] + projection.data[0];
left.y = projection.data[7] + projection.data[4];
left.z = projection.data[11] + projection.data[8];
left.d = projection.data[15] + projection.data[12];

right.x = projection.data[3] - projection.data[0];
right.y = projection.data[7] - projection.data[4];
right.z = projection.data[11] - projection.data[8];
right.d = projection.data[15] - projection.data[12];

bottom.x = projection.data[3] + projection.data[1];
bottom.y = projection.data[7] + projection.data[5];
bottom.z = projection.data[11] + projection.data[9];
bottom.d = projection.data[15] + projection.data[13];

top.x = projection.data[3] - projection.data[1];
top.y = projection.data[7] - projection.data[5];
top.z = projection.data[11] - projection.data[9];
top.d = projection.data[15] - projection.data[13];

near.x = projection.data[3] + projection.data[2];
near.y = projection.data[7] + projection.data[6];
near.z = projection.data[11] + projection.data[10];
near.d = projection.data[15] + projection.data[14];

far.x = projection.data[3] - projection.data[2];
far.y = projection.data[7] - projection.data[6];
far.z = projection.data[11] - projection.data[10];
far.d = projection.data[15] - projection.data[14];


Edit: Come to think of it, you're doing your multiplication comboMatrix = viewMatrix * projMatrix;, which is the opposite to how I do it. In which case, I'm not sure how much my code will help.

Share this post


Link to post
Share on other sites
@The Rug: Are you sure? It looks like your code is for Direct3D. In OpenGL the matrix is column-majored. But I may be wrong anyway...

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!