Bounding Box Visible In View Frustrum??

Mongoose · July 28, 2000, 4:12am

Can anyone out there explain in great detail how you can test to see if a bounding box is visible within the view frustrum?

I need to know this so I can test to see if the current octree node is partially visible.

Here are the classes being used

cBox
cVector3 m_Center
float m_Radius

cOctree
llist<cTriangle> m_llTriangles
cBox m_BoundingBox

cCamera
cVector3 m_WorldPos
cVector3 m_Orientation

I’m not sure if this information will help but just a though…

Thankx,

drakaza · August 1, 2000, 3:16am

You test to see if all of the bounding box’s points are behind each frustum plane
(test each point against each frustum plane)

If there are some points still in front of the planes (even only 1 point), then the object is theoretically visible

(I have no idea what that code that you posted means )

Mongoose · August 1, 2000, 7:40am

Ok that makes sense… but can anyone show me how to check a point against the frustrum planes… well i know how to check a point against a plane… but I guess I don’t know how to get openGL’s frustrum planes…

Also I think it would be better to back project the frustrum planes into world space and do my testing there…

Can anyone show me some example code as to how to do this??

Thankx,
Mongoose

elmargo · August 1, 2000, 10:06am

I had the very same problem (not knowing how to extract the frustum’s planes) so what I did is I created my own clipping planes which, with a bit of tweaking around, I made almost exactly like opengl’s frustum. I know this is a lame way to go, but it worked for me, especially after spending a week trying to figure out how to get those planes…so if you can bear with the fact that your “clipping” frustum won’t be exactly like your viewing frustum (but close enough) you can always go this way…

Lord_Chaos · August 3, 2000, 12:25am

There was a post about this on some message forum (this, Gamedev.net or some other I don’t remember) a while ago.

Naturally, all the info for the clipping planes are in your projection matrix. After all, this matrix is what defines the viewing frustum. I don’t remember exactly how to extract the normals for the four planes (the near and far z clipping planes are trivial), but you should be able to figure that out with some trial-and-error

Lord_Chaos · August 3, 2000, 12:37am

I found the post. It wa son the opengl-gamedev-l list. Read and enjoy:

There is a far easier and faster way to get the frustum planes from the
projection matrix. The 4 plane coeficients for the six planes are obtained
almost directly from the projection matrix as:

row[3] + row[0]
row[3] - row[0]
row[3] + row[1]
row[3] - row[1]
row[3] + row[2]
row[3] - row[2]

(Where row is definited as in the opengl doc). The nice thing about this
method is it works with any projection matrix at all. Also, if you subtract
the rows of the view matrix times the projection matrix, you get the planes
in object space which is very handy for culling. Below is an old post that
tom wrote up about this stuff.
-Gil

So you want to get the current view frustum into an objects coordinate
system as quickly as possible? Well, here’s the code!

void ExtractPlanes(CPlane Planes[6])
{
C4Vector tmpVec;
float fTmpLength;
C4Matrix ProjMat, MViewMat, ComboMat;

glGetFloatv(GL_PROJECTION_MATRIX, ProjMat[0]);
glGetFloatv(GL_MODELVIEW_MATRIX, MViewMat[0]);
ComboMat = MViewMat * ProjMat;
ComboMat.transpose();

tmpVec = ComboMat[3] - ComboMat[0];
Planes[0].normal().set(-tmpVec[0], -tmpVec[1], -tmpVec[2]);
Planes[0].distance() = -tmpVec[3];

tmpVec = ComboMat[3] + ComboMat[0];
Planes[1].normal().set(-tmpVec[0], -tmpVec[1], -tmpVec[2]);
Planes[1].distance() = -tmpVec[3];

tmpVec = ComboMat[3] - ComboMat[1];
Planes[2].normal().set(-tmpVec[0], -tmpVec[1], -tmpVec[2]);
Planes[2].distance() = -tmpVec[3];

tmpVec = ComboMat[3] + ComboMat[1];
Planes[3].normal().set(-tmpVec[0], -tmpVec[1], -tmpVec[2]);
Planes[3].distance() = -tmpVec[3];

tmpVec = ComboMat[3] - ComboMat[2];
Planes[4].normal().set(-tmpVec[0], -tmpVec[1], -tmpVec[2]);
Planes[4].distance() = -tmpVec[3];

tmpVec = ComboMat[3] + ComboMat[2];
Planes[5].normal().set(-tmpVec[0], -tmpVec[1], -tmpVec[2]);
Planes[5].distance() = -tmpVec[3];
}

Of course you need to have a bit more info before this to be useful …

C4Vector is a class with an array of 4 floats for data and a bunch of
operators for addition, subtraction, etc.
C4Matrix is a class with an array of 4 C4Vectors for data and a bunch of
operators for addition, subtraction, etc.
CPlane is a class with a C3Vector for the normal and a float for the
distance.
I want the normals of the planes of my frustum to point outside the
frustum (if you want them to point inside then remove the negation of the
normal and distance)
If you are so inclined you can normalize the planes by dividing the
normal and the distance by the length of the normal, but it isn’t necessary
for culling algorithms to work (verified … I’ve used it both ways). The
only reason to normalize is so you can “see” the normals better when
debugging.
I’ve been told that this should work under D3D in DX7 as well (but not
previous versions). If someone can confirm/deny this I’d appreciate hearing
about it.
Here is my matrix multiplier routine. If yours works differently then
you can reverse the order of the multiply to ProjMat * MViewMat.

const C4Matrix C4Matrix::operator*(const C4Matrix _rhs)
{
C4Matrix dst;

 for ( int j = 0; j &lt; 4; j++ )
 {
   dst[0][j] = (vec[0][0] * _rhs[0][j] +
                vec[0][1] * _rhs[1][j] +
                vec[0][2] * _rhs[2][j] +
                vec[0][3] * _rhs[3][j]);

   dst[1][j] = (vec[1][0] * _rhs[0][j] +
                vec[1][1] * _rhs[1][j] +
                vec[1][2] * _rhs[2][j] +
                vec[1][3] * _rhs[3][j]);

   dst[2][j] = (vec[2][0] * _rhs[0][j] +
                vec[2][1] * _rhs[1][j] +
                vec[2][2] * _rhs[2][j] +
                vec[2][3] * _rhs[3][j]);

   dst[3][j] = (vec[3][0] * _rhs[0][j] +
                vec[3][1] * _rhs[1][j] +
                vec[3][2] * _rhs[2][j] +
                vec[3][3] * _rhs[3][j]);
 }

return dst;
}

To go along with this I also have an AABB culling routine.

int IsVisible(CPlane Planes[6], CAABBox AABB)
{
C3Point MinPt, MaxPt;
bool bIntersecting = false;

for (int i = 0; i < 6; i++)
{
for (int j = 0; j < 3; j++)
{
if (Planes[i].normal()[j] >= 0.0f)
{
MinPt[j] = AABB.min[j];
MaxPt[j] = AABB.max[j];
}
else
{
MinPt[j] = AABB.max[j];
MaxPt[j] = AABB.min[j];
}
}
if (Planes[i].dist_to_point(MinPt) > 0.0f)
return 0;
if (Planes[i].dist_to_point(MaxPt) >= 0.0f)
bIntersecting = true;
}
return bIntersecting ? 1 : 2;
}

Return Values:
0 = Outside
1 = Intersecting
2 = Inside

It will report some cases as being intersecting when in fact they are
outside. How much of a concern this is depends entirely on how your data is
set up. An example of a false intersecting case can be seen here at: http://www.3dgamedev.com/projects/falsepos.gif.

The AABB test is right about of the Real Time Rendering book with the
following caveats(authors are CC’d on this e-mail):

The book’s test doesn’t differentiate between inside and outside
The book’s pseudo code (on page 311) has an error in it (the else’s
should be removed)

Credit goes out to Gil Gribb for coming up with the method for extracting
the planes and helping me get all the signs right and working correctly.

Tom

Madoc · August 3, 2000, 9:43pm

I’d point out that testing each boundbox corner against the frustum is not very accurate to say the least.

phlake · August 4, 2000, 9:10am

that could be a real problem if you’ve got an object so large that it completely encompasses the frustum.

but that’s what octrees are for, right?