Jump to content
  • Advertisement
Sign in to follow this  
hoogie

Extracting a viewing frustum

This topic is 4829 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 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
Advertisement
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
Cool, so am I right in thinking that your not using the world matrix at all? Just extract the planes from a View*Projection matrix?

Thanks again

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, &pOut->p );
}

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
Sign in to follow this  

  • Advertisement
×

Important Information

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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!