Sign in to follow this  
hoogie

Extracting a viewing frustum

Recommended Posts

Hi all, I am currently about to add frustum culling support to my quadtree based terrain engine and am slightly confused about extracting the viewing frustum. I was initially under the impression that I could extract the frustum from just the viewing matrix but having look through the "Fast Extraction of Viewing Frustum Planes from the World-View-Projection Matrix" I saw that I was somewhat mislead. My question is in very basic terms what is the algorithm to extract my viewing planes? Thanks alot for any help

Share this post


Link to post
Share on other sites
This is how I do it. Each Frust_* is a vector..

// View * Projection
MATRIX ViewProj = View * Projection;

// Calculate Frustum normals
Frust_Left.x = ViewProj._14 + ViewProj._11;
Frust_Left.y = ViewProj._24 + ViewProj._21;
Frust_Left.z = ViewProj._34 + ViewProj._31;
Frust_Left.Normalize();

Frust_Right.x = ViewProj._14 - ViewProj._11;
Frust_Right.y = ViewProj._24 - ViewProj._21;
Frust_Right.z = ViewProj._34 - ViewProj._31;
Frust_Right.Normalize();

Frust_Top.x = ViewProj._14 - ViewProj._12;
Frust_Top.y = ViewProj._24 - ViewProj._22;
Frust_Top.z = ViewProj._34 - ViewProj._32;
Frust_Top.Normalize();

Frust_Bottom.x = ViewProj._14 + ViewProj._12;
Frust_Bottom.y = ViewProj._24 + ViewProj._22;
Frust_Bottom.z = ViewProj._34 + ViewProj._32;
Frust_Bottom.Normalize();



I don't calculate the near and far planes because they can be pulled right out of the camera transform. The origin for all planes is the camera position.

Share this post


Link to post
Share on other sites
Well, you have to compare an object's world position with the frustum planes to see if it's inside or outside. And the view matrix is an inverted camera world matrix. So it's all related to world space.

Share this post


Link to post
Share on other sites
Hey,

I am currently extracting the viewing planes as described but dont seam to get the results I would expect.

For example both my left plane has the values (0.106, 90.129, 0.985) whilst the right plane has the values (-0.877, -0.129, -0.462).

I am assuming that these values are completely incorrect as there is no way I can clip my quadtree against this with their world positions.

Is there anything im missing here? Or does anyone have any ideas as to what could be causing these problems?

Thanks a lot for any help

Share this post


Link to post
Share on other sites
I don't know about the values, but it isn't all impossible I guess (btw, planes have 4 components)

I have the C++ code for extraction and culling spheres (and points) if you would like it... I think I still have it or some version of it.

Share this post


Link to post
Share on other sites
Those are plane normals. You need to see if a position is inside or outside of each plane. Here is my code to cull a single position:

BOOL Camera::Cull_Point(const VECTOR &p)
{
const VECTOR off = p - GetCameraPositionVector();

// it's hidden?
if( Frust_Left.Dot( off ) < 0.0f
|| Frust_Right.Dot( off ) < 0.0f
|| Frust_Top.Dot( off ) < 0.0f
|| Frust_Bottom.Dot( off ) < 0.0f )
return TRUE;

// It's visible
return FALSE;
}



This is not clipping the near and far planes. To do that, just dot your camera's forward direction with off. The result is how far in front of the camera the point is. You can compare that directly with your near and far distance values.

edit:
Quote:
Original post by Syranide
I don't know about the values, but it isn't all impossible I guess (btw, planes have 4 components)

Yeah, my method is a bit different than most. Maybe I shouldn't be the one teaching this guy. By the way, nice sig. LOL - isn't that from the SDK docs?

edit2:
Oh yeah. To cull a sphere, just change the 0.0's to -radius.

Share this post


Link to post
Share on other sites
Well one of the things im unsure about was the checking of points against the plane. Each node in my quadtree has its minimum and maximum world coordinates so initially I assumed I could check if it was viewable by checking if the world coordinates were within the frustum planes. Obviously if the frustum plane values are meant to be along the line of (0.106, 90.129, 0.985) then I am missunderstanding the approach needed for clipping.

Can anyone comfirm the kind of values I should be expecting from a viweing frustum extracted from the view and projection matrices?

Also in response to Jiia's does the call to Frust_Left.Dot( off ) return the dot product of the left frustum and offset position?

Thanks again for all the help

Share this post


Link to post
Share on other sites
Just to clarify

Frustum culling is commonly used with quadtrees etc to discard "objects"/sections that is outside the field of visibilty (as I guess you already knew quiet well).

Those 3 components you have give ous... I'm guessing A B C (or x y z) is the normal to the plane... which can infact be any number... however the D-component (which you haven't specified) is also necessary...

Which is funny... that makes me wonder how his code would ever work. I don't know really... perhaps it is possible to do that way... but this is the way done in papers and articles on the internet.

Here you have my C++-code which works splendid (I've verified it in some manner too). Hope you can make any use of it.


D3DXINLINE D3DXFRUSTUM* D3DXMatrixFrustum( D3DXFRUSTUM *pOut, CONST D3DXMATRIX *mCombo ) {
pOut->l.a = mCombo->_14 + mCombo->_11;
pOut->l.b = mCombo->_24 + mCombo->_21;
pOut->l.c = mCombo->_34 + mCombo->_31;
pOut->l.d = mCombo->_44 + mCombo->_41;

pOut->r.a = mCombo->_14 - mCombo->_11;
pOut->r.b = mCombo->_24 - mCombo->_21;
pOut->r.c = mCombo->_34 - mCombo->_31;
pOut->r.d = mCombo->_44 - mCombo->_41;

pOut->t.a = mCombo->_14 - mCombo->_12;
pOut->t.b = mCombo->_24 - mCombo->_22;
pOut->t.c = mCombo->_34 - mCombo->_32;
pOut->t.d = mCombo->_44 - mCombo->_42;

pOut->b.a = mCombo->_14 + mCombo->_12;
pOut->b.b = mCombo->_24 + mCombo->_22;
pOut->b.c = mCombo->_34 + mCombo->_32;
pOut->b.d = mCombo->_44 + mCombo->_42;

pOut->n.a = mCombo->_13;
pOut->n.b = mCombo->_23;
pOut->n.c = mCombo->_33;
pOut->n.d = mCombo->_43;

pOut->f.a = mCombo->_14 - mCombo->_13;
pOut->f.b = mCombo->_24 - mCombo->_23;
pOut->f.c = mCombo->_34 - mCombo->_33;
pOut->f.d = mCombo->_44 - mCombo->_43;

for( INT i = 0; i < 6; i++ ) {
D3DXPlaneNormalize( &pOut->p[i], &pOut->p[i] );
}

return pOut;
}

D3DXINLINE INT D3DXPlaneContainsSphere( CONST D3DXPLANE *pPlane, CONST D3DXVECTOR3 *vCenter, CONST FLOAT fRadius ) {
FLOAT fDistance = D3DXPlaneDistance( vCenter, pPlane );
if( fDistance < -fRadius )
return D3DX_OUTSIDE;
if( fDistance < fRadius )
return D3DX_INTERSECT;
return D3DX_INSIDE;
}

Share this post


Link to post
Share on other sites
Quote:
Original post by hoogie
Well one of the things im unsure about was the checking of points against the plane. Each node in my quadtree has its minimum and maximum world coordinates so initially I assumed I could check if it was viewable by checking if the world coordinates were within the frustum planes. Obviously if the frustum plane values are meant to be along the line of (0.106, 90.129, 0.985) then I am missunderstanding the approach needed for clipping.Thanks again for all the help

The camera position represents the origin of all planes. It's like the top of the pyramid. The Frust_Left, Frust_Right, etc, represent the direction of each wall of it. You can build the pyramid walls just by having their direction and the pyramid top peak position. Makes sense?

Quote:
Original post by hoogie
Can anyone comfirm the kind of values I should be expecting from a viweing frustum extracted from the view and projection matrices?

You can't expect any kind of value. Your camera can be facing any direction, which means your frustum walls can as well. Their values depend on where the camera is looking.

Quote:
Original post by hoogie
Also in response to Jiia's does the call to Frust_Left.Dot( off ) return the dot product of the left frustum and offset position?

Yes. It tells you how far inside of the frustum pyramid the point is, on the left. So if the value is less than zero, it means it's outside, not inside.

Quote:
Original post by Syranide
Those 3 components you have give ous... I'm guessing A B C (or x y z) is the normal to the plane... which can infact be any number... however the D-component (which you haven't specified) is also necessary...

The D component is how far the plane is from the origin of "space". It's pretty much useless here. If you ommit the D value, you only have to update your frustum normals when your camera rotates. You have to calculate the distance to each plane either way. Although my method only calculates a vector difference then a dot product for each frustum.

Quote:
Original post by Syranide
Which is funny... that makes me wonder how his code would ever work. I don't know really... perhaps it is possible to do that way...

Must be new to math?

Share this post


Link to post
Share on other sites
Quote:
Original post by hoogie
Well one of the things im unsure about was the checking of points against the plane. Each node in my quadtree has its minimum and maximum world coordinates so initially I assumed I could check if it was viewable by checking if the world coordinates were within the frustum planes.

Sorry, I forgot to answer this one. To know if a box shape is outside of the frustum, all of the 8 corners of the box must be outside of a plane. That doesn't mean pass all 8 corners to Cull_Point. It means all 8 points must be outside of a single plane.

If you were looking directly at your box, the four top corners may be outside of the top plane, and the four bottom corners may be outside of the bottom plane. So all points are outside of the frustum, yet your box is totally centered in view. So all points of the object must be outside of a single plane.

Share this post


Link to post
Share on other sites
Hey, first thanks for all the replys.

I am trying to implement my checks like Jiia described and am almsot there. Currently clipping is taking place but not entirely as it should, sometimes the clipping can be seen and at other time the entire terrain dissappears. This is how im currently doing my tests



// calculates position data to test against the frustum planes
D3DXVECTOR3 minOff, maxOff;
minOff = node->GetMinimumBounds() - cameraPos;
maxOff = node->GetMaximumBounds() - cameraPos;

// if node completely invisible set all child nodes to invisible
if( D3DXVec3Dot(&minOff, &m_leftPlane.normal) < 0.0f &&
D3DXVec3Dot(&maxOff, &m_leftPlane.normal) < 0.0f ||
D3DXVec3Dot(&minOff, &m_rightPlane.normal) < 0.0f &&
D3DXVec3Dot(&maxOff, &m_rightPlane.normal) < 0.0f )

CFrustum::SetAllInvisible(node);

// else if node completely visible set all child nodes to visible
else if( D3DXVec3Dot(&minOff, &m_leftPlane.normal) >= 0.0f &&
D3DXVec3Dot(&maxOff, &m_leftPlane.normal) < 0.0f ||
D3DXVec3Dot(&minOff, &m_rightPlane.normal) >= 0.0f &&
D3DXVec3Dot(&maxOff, &m_rightPlane.normal) < 0.0f )

CFrustum::SetAllVisible(node);

// else if partially visible but has children progress further down quadtree
else if( node->m_childNode[0] != NULL && node->m_childNode[1] != NULL &&
node->m_childNode[2] != NULL && node->m_childNode[3] != NULL )
{
CFrustum::ClipQuadTree(node->m_childNode[0], cameraPos);
CFrustum::ClipQuadTree(node->m_childNode[1], cameraPos);
CFrustum::ClipQuadTree(node->m_childNode[2], cameraPos);
CFrustum::ClipQuadTree(node->m_childNode[3], cameraPos);
}

// else if partially visible but has no children set to visible
else
CFrustum::SetAllVisible(node);




Does that look correct or am i doing something wrong somewhere?

Thanks

Share this post


Link to post
Share on other sites
I haven't actually culled a bounding box with my routine yet. But I think your problem is in using GetMinimum/MaximumBounds. This is what I was trying to explain before about all points having to be outside of a single plane.

For example, if your bounding box has 8 points, you have to test every single point against the left plane. If all of them are outside of that plane, then it's hidden. If not, do it again for another plane. Then again until you find a plane that all points are outside of. If none are found, the box is visible.

The reason your entire terrain is being hidden is because all of it's points are outside of planes, yet the center of the box is in view. That's why all points must be outside of a single plane.

Like I said, I haven't experimented with it much. Don't take my word for gold ;)

edit:

I think there might some optimizations you could do, though. If you can find the point that is most-left relative to the camera, you only need to test that point against the right plane. Test the most-right point against the left plane, etc. But finding a point most left/right/etc of the camera may require more processing than is needed to check the planes to begin with. It all depends on how you caclulate most extreme points.

The first idea that comes to mind to find the most right point is to dot each offset with the camera right-vector. But I doubt this would show any performance boost; it may even slow it down.

Also, depending on how your camera and bounding boxes rotate, you may be able to test fewer points. For example, if UP is always UP (your camera doesn't twist - meaning your world isn't ever viewed sideways, and your bounding box is AABB or also doesn't twist), you don't need to test both top and bottom points against the left and right planes. Is this case, you could just test the four bottom points against each side.

[Edited by - Jiia on April 1, 2005 6:27:49 AM]

Share this post


Link to post
Share on other sites
It sounds like you may be getting this figured out, so I'm not sure this'll help. However, I found Mark Morley's frustum culling tutorial really helpful. It's in OpenGL, but I think only the plane extraction should be different (is that true?). I found this article about plane extraction to be really helpful and it covers both opengl and directx and has example code. Anyway, hope you get it working.

Share this post


Link to post
Share on other sites
Well currently my only test that leads to anything being set as invisible is

// if node completely invisible set all child nodes to invisible
if( D3DXVec3Dot(&minOff, &m_leftPlane.normal) < 0.0f &&
D3DXVec3Dot(&maxOff, &m_leftPlane.normal) < 0.0f ||
D3DXVec3Dot(&minOff, &m_rightPlane.normal) < 0.0f &&
D3DXVec3Dot(&maxOff, &m_rightPlane.normal) < 0.0f )

CFrustum::SetAllInvisible(node);

And im under the impression that that is only called when the min and max bound are outside of the same plane.

I cant think that my planes could be wrong as they are extracted like all the turorials say and theres no way that my view matrix could be incorrect

Share this post


Link to post
Share on other sites
I'm not sure I follow what the problem is. Here is a snap shot from my debug cam in my project:

Free Image Hosting at www.ImageShack.us
The screen is viewed from the debug camera looking at the real camera. All lighting and culling is done relative to the real camera. The white lines are the frustum of the real camera. It's looking almost completely down on the guy standing in grass. Culling isn't activated in this snap shot, but you can see how it would be easy to mess this up. The entire flat grass area is a single quad. All four points of the quad are outside of the frustum planes, yet the camera is staring right at it.

Hope that helps a bit, if that is the problem.

Share this post


Link to post
Share on other sites
Hey,

Ive been continuing with my implementation of the frustum culling and found a good tutorial covering the kind of loop needed to clip a cube.

Im having one final problem and think I might know the reason why. Basically the implementation I currently have is clipping my quadtree nodes but the clipping is always slightly off so the clip is noticeable, as such I figured that my data must be slightly off somewhere.

When I set my quadtree it is essentially a 2D quadtree covering the terrain in the x and z directions, by default the y values are left as zero and never changed. Could this be the cause of my clipping algorithm being slightly off? I figured it might be as the equation utilizes the x, y, and z coords of a point to test if its inside a plane or out.

If this is the cause of the problem is there any way that I can alter my frustum clipping to ignore the y data and clip based solely on the x and z data?

Thanks again for any replies

Share this post


Link to post
Share on other sites
An object shouldn't need any mass to cull correctly. I don't know if the problem is related to it or not, but having the top and/or bottom of all points as zero would make no difference.

However, if your meshes are sticking up off of the ground, and you're culling them like they are flat, then yeah, it would definitely be noticable and it won't work correctly. If you don't want to scan for sizes, you can just give them really tall boxes, big enough to fit any size mesh in your game.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this