# 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.

## 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 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 on other sites
This explains how to extract the frustum planes from the view-projection matrix. Then you can take a look at frustum-AABB intersection routines, like those mentioned here. This also looks interesting.

##### 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 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 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 planep_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 planep_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 planep_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 planep_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 planep_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 planep_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 requestedif (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 on other sites
View * Projection

##### 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 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 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 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 on other sites
Quote:
 Original post by darookieThe 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 on other sites
One other thing, Trip, What does 'MakeMatrixFor3D' do?

##### 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 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

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 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 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 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.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628658
• Total Posts
2984078

• 10
• 9
• 9
• 10
• 21