Sign in to follow this  

Frustum Culling in Direct3D

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

I have searched EVERYWHERE for code or detailed information.. ANYTHING. My objective so far has been to implement frustum culling in my Direct3D graphics engine then build a couple of functions to determine if a vector, sphere, or most of all, a box, is in the frustum. But so far out of all my endless amounts of searching (via Google and AltaVista) and experamentation, no luck. So maybe somebody could help me out? I am using Visual Basic .NET (thus Managed DirectX) but if any code or langauge specific things are brought up, C# will do as well. I did try to convert the code from "cull" example in the C++ DX9 SDK, but it didn't work. I want to use it to implement a octree and/or quadtree for various purposes, e.g. Terrain engine, Wolf3D type environment (one from the early 90's), etc.. If you can help or point me somewhere THANK YOU SO MUCH!

Share this post


Link to post
Share on other sites
how about this flipcode article here http://www.flipcode.com/articles/article_frustumculling.shtml its pretty good, i used this to implement frustum culling for my engine. [google] link http://www.google.com.au/search?hl=en&q=frustum%2Bculling&btnG=Search&meta= returns heaps of information! if you want an octree example then here is the best i've seen http://www.gametutorials.com/Tutorials/OpenGL/OpenGL_Pg5.htm

Share this post


Link to post
Share on other sites
Call me stupid, but I've looked at the plane extraction document from RavenSoft,
but not quite sure what to make of it. As for everything else,
its all "in OpenGL", and since I don't know
OpenGL, so I can't make anything out too well of that either :(

Share this post


Link to post
Share on other sites
Although... I just found some sample code in that document, that for some reason
I never noticed before. Hopefully this will answer my question.

Now do I feel stupid. lol

Share this post


Link to post
Share on other sites
Just one last thing. Here is the sample code from
the plane extraction pdf:


struct Matrix4x4
{
// The elements of the 4x4 matrix are stored in
// row-major order.
float _11, _12, _13, _14;
float _21, _22, _23, _24;
float _31, _32, _33, _34;
float _41, _42, _43, _44;
};

void ExtractPlanesD3D(
Plane * p_planes,
const Matrix4x4 & comboMatrix,
bool normalize)
{
// Left clipping plane
p_planes[0].a = comboMatrix._14 + comboMatrix._11;
p_planes[0].b = comboMatrix._24 + comboMatrix._21;
p_planes[0].c = comboMatrix._34 + comboMatrix._31;
p_planes[0].d = comboMatrix._44 + comboMatrix._41;
// Right clipping plane
p_planes[1].a = comboMatrix._14 - comboMatrix._11;
p_planes[1].b = comboMatrix._24 - comboMatrix._21;
p_planes[1].c = comboMatrix._34 - comboMatrix._31;
p_planes[1].d = comboMatrix._44 - comboMatrix._41;
// Top clipping plane
p_planes[2].a = comboMatrix._14 - comboMatrix._12;
p_planes[2].b = comboMatrix._24 - comboMatrix._22;
p_planes[2].c = comboMatrix._34 - comboMatrix._32;
p_planes[2].d = comboMatrix._44 - comboMatrix._42;
// Bottom clipping plane
p_planes[3].a = comboMatrix._14 + comboMatrix._12;
p_planes[3].b = comboMatrix._24 + comboMatrix._22;
p_planes[3].c = comboMatrix._34 + comboMatrix._32;
p_planes[3].d = comboMatrix._44 + comboMatrix._42;
// Near clipping plane
p_planes[4].a = comboMatrix._13;
p_planes[4].b = comboMatrix._23;
p_planes[4].c = comboMatrix._33;
p_planes[4].d = comboMatrix._43;
// Far clipping plane
p_planes[5].a = comboMatrix._14 - comboMatrix._13;
p_planes[5].b = comboMatrix._24 - comboMatrix._23;
p_planes[5].c = comboMatrix._34 - comboMatrix._33;
p_planes[5].d = comboMatrix._44 - comboMatrix._43;
// Normalize the plane equations, if requested
if (normalize == true)
{
NormalizePlane(p_planes[0]);
NormalizePlane(p_planes[1]);
NormalizePlane(p_planes[2]);
NormalizePlane(p_planes[3]);
NormalizePlane(p_planes[4]);
NormalizePlane(p_planes[5]);
}
}



What goes in parameter 'comboMatrix'? The projection, world, view, matrix?

[Edited by - Coder on December 15, 2004 2:16:03 AM]

Share this post


Link to post
Share on other sites
This is a post by Razor98 from a duplicate, now closed, thread:

Could somebody explain to me why this doesn't work?

Here is my plane extraction code (VB.NET):

Public Sub ExtractFrustumPlanes(Optional ByVal Normalize As Boolean = True)

Dim comboMatrix As Matrix = Matrix.Multiply(ccCore.Device.Transform.View, ccCore.Device.Transform.Projection)

'Left clipping plane
ccFrustum(0).A = comboMatrix.M14+ comboMatrix.M11
ccFrustum(0).B = -(comboMatrix.M24+ comboMatrix.M21)
ccFrustum(0).C = -(comboMatrix.M34+ comboMatrix.M31)
ccFrustum(0).D = -(comboMatrix.M44+ comboMatrix.M41)

'Right clipping plane
ccFrustum(1).A = -(comboMatrix.M14- comboMatrix.M11)
ccFrustum(1).B = -(comboMatrix.M24- comboMatrix.M21)
ccFrustum(1).C = -(comboMatrix.M34- comboMatrix.M31)
ccFrustum(1).D = -(comboMatrix.M44- comboMatrix.M41)

'Top clipping plane
ccFrustum(2).A = -(comboMatrix.M14- comboMatrix.M12)
ccFrustum(2).B = -(comboMatrix.M24- comboMatrix.M22)
ccFrustum(2).C = -(comboMatrix.M34- comboMatrix.M32)
ccFrustum(2).D = -(comboMatrix.M44- comboMatrix.M42)

'Bottom clipping plane
ccFrustum(3).A = -(comboMatrix.M14+ comboMatrix.M12)
ccFrustum(3).B = -(comboMatrix.M24+ comboMatrix.M22)
ccFrustum(3).C = -(comboMatrix.M34+ comboMatrix.M32)
ccFrustum(3).D = -(comboMatrix.M44+ comboMatrix.M42)

'Near clipping plane
ccFrustum(4).A = -(comboMatrix.M14+ comboMatrix.M13)
ccFrustum(4).B = -(comboMatrix.M24+ comboMatrix.M23)
ccFrustum(4).C = -(comboMatrix.M34+ comboMatrix.M33)
ccFrustum(4).D = -(comboMatrix.M44+ comboMatrix.M43)

'Far clipping plane
ccFrustum(5).A = -(comboMatrix.M14- comboMatrix.M13)
ccFrustum(5).B = -(comboMatrix.M24- comboMatrix.M23)
ccFrustum(5).C = -(comboMatrix.M34- comboMatrix.M33)
ccFrustum(5).D = -(comboMatrix.M44- comboMatrix.M43)

If Normalize Then
For I As Integer = 0 To 5
ccFrustum(I).Normalize()
'NormalizePlane(ccFrustum(I))
Next
End If

End Sub




And my sphere testing code (of course, also VB.NET):


Public Function FrustumTestSphere(ByVal vCenter As m3dVector3D, ByVal Radius As Single) As Boolean

Dim Distance As Single
Dim tCenter As Vector3

tCenter = vCenter.ToVector3
tCenter.TransformCoordinate(ccCore.Device.Transform.World)

For I As Integer = 0 To 5
Distance = Plane.DotNormal(ccFrustum(I), tCenter)
Debug.WriteLine(Distance)
If Distance < -Radius Then
Return False
End If
Next

Return True

End Function





Thanks!

Share this post


Link to post
Share on other sites
The code could not work because MDX uses a left-handed coordinate system, which means that the matrix is not row-major.
To avoid that you will have to create the view matrix using the LookAtRH() method instead of LookAtLH().
Note that you will have to convert your Z-values in that case, too because the axis will be inversed.

Good luck,
Pat.

Share this post


Link to post
Share on other sites
Hi, here is some code straight from a Direct3D app I have written that calcs the view frustum the AABB a sphere and a cone:


void CFrustum::Calculate(const D3DXMATRIX *matView,const D3DXMATRIX *matProj,
const D3DXVECTOR3 &position,const D3DXVECTOR3 &look,float fov,unsigned int screenWidth,unsigned int screenHeight)
{
// Get combined matrix
D3DXMATRIXA16 matComb;
D3DXMatrixMultiply(&matComb, matView, matProj);

// Left clipping plane
m_frustumPlanes[0].m_normal.x = matComb._14 + matComb._11;
m_frustumPlanes[0].m_normal.y = matComb._24 + matComb._21;
m_frustumPlanes[0].m_normal.z = matComb._34 + matComb._31;
m_frustumPlanes[0].m_distance = matComb._44 + matComb._41;

// Right clipping plane
m_frustumPlanes[1].m_normal.x = matComb._14 - matComb._11;
m_frustumPlanes[1].m_normal.y = matComb._24 - matComb._21;
m_frustumPlanes[1].m_normal.z = matComb._34 - matComb._31;
m_frustumPlanes[1].m_distance = matComb._44 - matComb._41;

// Top clipping plane
m_frustumPlanes[2].m_normal.x = matComb._14 - matComb._12;
m_frustumPlanes[2].m_normal.y = matComb._24 - matComb._22;
m_frustumPlanes[2].m_normal.z = matComb._34 - matComb._32;
m_frustumPlanes[2].m_distance = matComb._44 - matComb._42;

// Bottom clipping plane
m_frustumPlanes[3].m_normal.x = matComb._14 + matComb._12;
m_frustumPlanes[3].m_normal.y = matComb._24 + matComb._22;
m_frustumPlanes[3].m_normal.z = matComb._34 + matComb._32;
m_frustumPlanes[3].m_distance = matComb._44 + matComb._42;

// Near clipping plane
m_frustumPlanes[4].m_normal.x = matComb._13;
m_frustumPlanes[4].m_normal.y = matComb._23;
m_frustumPlanes[4].m_normal.z = matComb._33;
m_frustumPlanes[4].m_distance = matComb._43;

// Far clipping plane
m_frustumPlanes[5].m_normal.x = matComb._14 - matComb._13;
m_frustumPlanes[5].m_normal.y = matComb._24 - matComb._23;
m_frustumPlanes[5].m_normal.z = matComb._34 - matComb._33;
m_frustumPlanes[5].m_distance = matComb._44 - matComb._43;

// Normalise them - only needed if later calcs require an accurate distance
for (int i=0;i<6;i++)
m_frustumPlanes[i].Normalise();

// Calc frustum AABB
// Create some points relative in clip space then transform them on to the far plane
D3DXVECTOR3 p[8];
p[0]=D3DXVECTOR3(-1.0f,1.0f,1.0f);
p[1]=D3DXVECTOR3(-1.0f,-1.0f,1.0f);
p[2]=D3DXVECTOR3(1.0f,-1.0f,1.0f);
p[3]=D3DXVECTOR3(1.0f,1.0f,1.0f);
p[4]=D3DXVECTOR3(-1.0f,1.0f,0.0f);
p[5]=D3DXVECTOR3(-1.0f,-1.0f,0.0f);
p[6]=D3DXVECTOR3(1.0f,-1.0f,0.0f);
p[7]=D3DXVECTOR3(1.0f,1.0f,0.0f);

D3DXMATRIX cameraWorldMatrix;
CMaths::MakeMatrixFor3d(&cameraWorldMatrix,position,D3DXVECTOR3(0,0,0));

// Transform to far plane using the inverse combined matrix of proj, view and world
D3DXMATRIXA16 projView;
D3DXMatrixMultiply(&projView, matView, matProj);

D3DXMATRIXA16 projViewWorld;
D3DXMatrixMultiply(&projViewWorld, &projView, &cameraWorldMatrix);

D3DXMATRIXA16 invProjViewWorld;
D3DXMatrixInverse(&invProjViewWorld,NULL,&invProjViewWorld);

D3DXMATRIXA16 invProjView;
D3DXMatrixInverse(&invProjView,NULL,&projView);

D3DXMATRIXA16 final=invProjView;

D3DXVECTOR3 planePnts[8];
for (i=0;i<8;i++)
D3DXVec3TransformCoord(&planePnts[i], &p[i], &final);

D3DXVECTOR3 min=position; // defaults
D3DXVECTOR3 max=position;

for (i=0;i<8;i++)
{
min.x=min(min.x,planePnts[i].x);
min.y=min(min.y,planePnts[i].y);
min.z=min(min.z,planePnts[i].z);

max.x=max(max.x,planePnts[i].x);
max.y=max(max.y,planePnts[i].y);
max.z=max(max.z,planePnts[i].z);
}

m_frustumAABB->SetMinimum(min);
m_frustumAABB->SetMaximum(max);


// Calculate bounding sphere - needs to be in centre of frustum with radius that goes to the far corner
// on the far plane

// Centre of sphere is half way between near and far clipping planes along the view vector of the camera
// starting at the camera position



// Calculate the radius of the frustum sphere
float frustumLength=m_frustumPlanes[FAR_CP].m_distance-m_frustumPlanes[NEAR_CP].m_distance;

// Calculate the height of the frustum at that distance, use some trig
// Its a half angle of course
float frustumFarHeight=frustumLength*tan(fov*0.5f);
float frustumFarWidth=frustumFarHeight; // correct when aspect ratio is 1

// Centre point in frustum is half way from near plane along length
D3DXVECTOR3 centre(0.0f,0.0f,m_frustumPlanes[NEAR_CP].m_distance+frustumLength*0.5f);

// Far corner point (top right)
D3DXVECTOR3 farCorner(frustumFarWidth,frustumFarHeight,frustumLength);

// Vector between the far corner and the centre:
D3DXVECTOR3 v=centre-farCorner;

// Radius is length of this vector
float radius=D3DXVec3Length(&v);

// Now get centre of sphere in world space
D3DXVECTOR3 sphereCentre=position+look* ((frustumLength*0.5f)+m_frustumPlanes[NEAR_CP].m_distance);
//_frusSphere.Center() = m_vCameraPosition + (vLookVector * (fViewLen * 0.5f) + m_fNearPlane);

m_frustumSphere->SetCentre(sphereCentre);
m_frustumSphere->SetRadius(radius);

// Calculate the bounding cone
// Its position is simply the position of the camera and its direction is the look
m_frustumCone->SetPosition(position);
m_frustumCone->SetFacing(look);

// The angle is a bit more tricky, if we set it to the same as FOV then the cone will be inside the frustum
// Instead we need it to encompass the corners of the frustum and not just the sides, use trig
// We use the screen sizes to get the angle between the centre of the viewport to the corner of it

float halfScreenHeight=(0.5f*screenHeight);
float halfScreenWidth=(0.5f*screenWidth);

// calculate the length of the fov triangle
float depth = halfScreenHeight / tan(fov * 0.5f);// calculate the corner of the screen
float corner = sqrt(halfScreenWidth * halfScreenWidth + halfScreenHeight * halfScreenHeight);// now calculate the new fov
float coneFov = atan(corner / depth);

m_frustumCone->SetSpreadAngle(coneFov);
}



hope that helps

Share this post


Link to post
Share on other sites
By the way I only just added the cone calcs. so there may still be bugs in there. Once I have checked it all I plan to add some notes to my site about this.

Share this post


Link to post
Share on other sites
Quote:
Original post by darookie
The code could not work because MDX uses a left-handed coordinate system, which means that the matrix is not row-major.
To avoid that you will have to create the view matrix using the LookAtRH() method instead of LookAtLH().
Note that you will have to convert your Z-values in that case, too because the axis will be inversed.

Good luck,
Pat.


Will I have to do this with Trip's code? (I assume I will)

Share this post


Link to post
Share on other sites
Hi, my code does not require any view matrix shenanigans :) The MakeMatrixFor3D fn is something in my library that creates a 3D matrix from position, rotation and scale, something like:


D3DXMatrixIdentity(mat);

D3DXMatrixRotationX( &matRotX, rot.x);
D3DXMatrixRotationY( &matRotY, rot.y);
D3DXMatrixRotationZ( &matRotZ, rot.z);

if (scale!=NULL)
D3DXMatrixScaling(&matScale,scale->x,scale->y,scale->z);

D3DXMatrixTranslation(&matTrans,pos.x,pos.y,pos.z);

*mat=(matScale*(matRotZ*matRotY*matRotX))*matTrans;



Share this post


Link to post
Share on other sites
*mat=(matScale*(matRotZ*matRotY*matRotX))*matTrans;

I assume this means that these matrixes are being multipled and being stored
into the reference that the pointer 'mat' is pointing to. Almost like saying:
(I'm rusty with what I know about C/C++ btw)

int * i;
int j;

i = &j
*i = ( A * ( B * C * D ) ) * E

but since VB.NET 2003 doesn't support operator overloading (but 2005 does),
would you know how to do this with D3DXMatrixMultiply (or whatever it is),
since you could probably figure it out faster than I could (I have an idea of how to do it in theory though)?

Thanks!

Share this post


Link to post
Share on other sites
You can of course use the D3DXMatrixMultiply instead, you multiply into temps and then mult them into results etc. just be aware of the order you do it - I am sure you can figure it out :)

Share this post


Link to post
Share on other sites
How does this look?

Private Sub MakeMatrixFor3D(ByRef Mat As Matrix, ByVal Position As Vector3, ByVal Rotation As Vector3, ByVal Scale As Vector3)

Dim matRotate(2) As Matrix
Dim matScale As Matrix
Dim matTrans As Matrix

Mat = Matrix.Identity

matRotate(0).RotateX(Rotation.X)
matRotate(1).RotateY(Rotation.Y)
matRotate(2).RotateZ(Rotation.Z)

matScale.Scaling(Scale)
matTrans.Translate(Position)

Dim TempRot As Matrix
Dim TempScale As Matrix
Dim TempTrans As Matrix

TempRot = Matrix.Multiply(matRotate(2), Matrix.Multiply(matRotate(1), matRotate(0)))
TempScale = Matrix.Multiply(matScale, TempRot)
TempTrans = Matrix.Multiply(TempScale, matTrans)

Mat = TempTrans

End Sub

Share this post


Link to post
Share on other sites

This topic is 4744 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.

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