Sign in to follow this  

Quadtree Frustum culling

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

Okay, so I'm trying to implement frustum culling for my object quadtree, but keep running into a problem: How do I check if a quadtree is in the frustum if I don't know it's height? Since theres no limitation to it's height, I have to assume objects can be anywhere along the z-axis. So how do I perform this kind of test? Thanks in advance...

Share this post


Link to post
Share on other sites
Quote:
I don't know it's height? Since theres no limitation to it's height, I have to assume objects can be anywhere along the z-axis. So how do I perform this kind of test?

Why don't you know its height?

My quadtree/terrain implementation builds (at load time) the initial vertex buffer and then recursively subdivides this into the component index buffers and at the same time stores a bounding box for each node in the tree. Thus I know exactly the constraints for each node/leaf.

If you have a dynamic terrain then you can still process it at load time, just be sure to update your bounding box whenever you update the physical geometry.

Is that of any help? If not, provide some more details on why you cant get the bounding box and/or what information you have available...

hth
Jack

Share this post


Link to post
Share on other sites
Well, my terrain quadtree works like that too (only I use bounding spheres only).

However, my OBJECT quadtree doesn't keep track of it's height, since the objects are in linked lists and, well, frankly, doing that is a pain.

What I'm really looking for is a way to check the frustum against 4 rays (one in each corner), giving me a check against any height.

Each object has sphere based checking anyways, it's just that I need to quickly eliminate high-level nodes. I'm not too worried about the low-level incorrect trues it might return.

Share this post


Link to post
Share on other sites
Hi,

Sorry for the slow reply... I was doing a recruitment event on Tuesday and been too busy since to look at GDNet [sad].

Anyway, for your ray-frustum check, I could see two possible ways of doing this:

Firstly; create a small sphere at each corner of your bounding area - you already have the code for sphere/frustum checking you say. Although this doesn't strike me as an elegant solution it should work.

Secondly; ray/plane collision tests are fairly simple mathematically (been a while since I messed with this though). You could generate a ray from your camera position to each corner; if the distance to the point is between the distances of the near plane and the far plane, and the intersection of the ray and the near plane is within the defined viewport, the corner must be visible. By implication, if all 4 corners are visible the whole area is, and if some of the corners are visible it's partially visible and you should recurse further...

I'm not too sure how you could compensate for the lack of a know height. Depending on whether your camera is fixed to a given DoF you might be able to improvise by only doing a ray-plane intersection on the XY axis' and ignoring the Z intersection (where Z is height). Or you could try and be clever and use plane-plane intersections; where you express your "ray" to each corner as a plane expanding infinitely up/down the height axis.

hth
Jack

Share this post


Link to post
Share on other sites
Thanks for responding, and I'm sorry for being pushy, I was too away from home and was expecting replies when I got back -- and got worried when there were none ;).

Anywho, back to my question, after really thinking it over, I've come to the conclusion that when I really need is some way to measure height, since an indefinate ray would alway intersect a plane if it wasn't exactly parallel, which would really never happen in my case.

So, I guess I'll have no choice but to set a maximum height for my engine, which is something I didn't want to do. Then, I'll have to write a box-frustum intersection function and use that to check if the whole quad is in view.

Kinda lousy, but I can't really think of doing anything else :).

Thanks for your help anyways.

Heres a link to my terrain engine (I'm adding the object tree to it now), if you're interested:
http://www.devimg.net/?View=484

Again, thanks for your help.

Share this post


Link to post
Share on other sites
First off, maybe I dont understand ya. But why are you trying to check hieght at all? Unless you make an Oct-Tree which has the heights diveded into bboxs as well... I do 3 different tests on the bounding box's planes including sphere-box and box-box. I have never needed a reason to include height, I simply set hte heights to 1.0f :). If you want to look at some example code then I can post some if you tell me exactly what you are looking to test against and why height is a factor. This is a quad-tree right?

Share this post


Link to post
Share on other sites
That's perfect!

My problem was, that since I'm writting a 3D game -- I was thinking 3D. How over-complicated that is :).

I was thinking that since my frustum is 3D, and my QuadTree is 2D, I need to make my QuadTree 3D, but in reality, making the frustum 2D would be so much simpler.

So, now I need to find a way to get a 2D frustum, that is squash it down to z=0.0f; but how do I do that? I'd like to get all 8 corners, then move each of them to z=0.0f, and perform some kind of check against them. But how would I perform that? any suggestions?

Thanks a lot -- that was tremendously helpful ;).

Share this post


Link to post
Share on other sites
here is an example of how I built my frustum, I have a class called camera which holds this frustum in it....


class Frustum
{
public:
Plane plPlane[6];
Sphere sphBoundingSphere;
Cone cneBoundingCone;
float fNearPlane;
float fFarPlane;
float fFieldOfView;
float fHalfSHeight;
float fHalfSWidth;
Vector vecCamPos;
Vector vecLook;

int ContainsSphere(Sphere& pSphereInc);
int ContainsAABB(AABB& pAABBInc);
void Update(D3DXMATRIX& pmatView, D3DXMATRIX& pmatProj);
void ConstructBoundingSphere(void);
void ConstructBoundingCone(void);
Frustum();
virtual ~Frustum();

};










this is where I update it, by ripping the planes from the matrix. Its pretty standard code for doing it in directx.


void Frustum::Update(D3DXMATRIX& pmatView, D3DXMATRIX& pmatProj)
{
D3DXVECTOR3 vecLocal(1.0f, 1.0f, 1.0f);
D3DXMATRIX matLocal = *D3DXMatrixIdentity(&matLocal);
D3DXMatrixMultiply(&matLocal, &pmatView, &pmatProj);
vecCamPos = Vector( -matLocal._41, -matLocal._42, -matLocal._43 );
vecLook = Vector( matLocal._13, matLocal._23, matLocal._33 );

// LEFT SIDE
plPlane[LEFT] = Plane( Vector( matLocal._14 + matLocal._11,
matLocal._24 + matLocal._21,
matLocal._34 + matLocal._31 ),
matLocal._44 + matLocal._41);
plPlane[LEFT].Normalize();

// TOP SIDE
plPlane[TOP] = Plane( Vector( matLocal._14 - matLocal._12,
matLocal._24 - matLocal._22,
matLocal._34 - matLocal._32 ),
matLocal._44 - matLocal._42);
plPlane[TOP].Normalize();

// RIGHT SIDE
plPlane[RIGHT] = Plane( Vector( matLocal._14 - matLocal._11,
matLocal._24 - matLocal._21,
matLocal._34 - matLocal._31 ),
matLocal._44 - matLocal._41);
plPlane[RIGHT].Normalize();

// BOTTOM SIDE
plPlane[BOTTOM] = Plane( Vector( matLocal._14 + matLocal._12,
matLocal._24 + matLocal._22,
matLocal._34 + matLocal._32 ),
matLocal._44 + matLocal._42);
plPlane[BOTTOM].Normalize();

// NEAR SIDE
plPlane[CLOSE] = Plane( Vector( matLocal._13,
matLocal._23,
matLocal._33),
matLocal._43);
plPlane[CLOSE].Normalize();

// FAR SIDE
plPlane[AWAY] = Plane( Vector( matLocal._14 - matLocal._13,
matLocal._24 - matLocal._23,
matLocal._34 - matLocal._33 ),
matLocal._44 - matLocal._43);
plPlane[AWAY].Normalize();

ConstructBoundingSphere();
ConstructBoundingCone();

}







Once you have your planes, go ahead and test
1. if the box contains the camera pos, if it does then stop testing you know u need to render the quad, or keep traversing tree.

2. do a sphere-sphere test, if they do intersect continue

3. do a cone-sphere test, if that intersects continue

4. check if the frustum contains the sphere, if so then check
a. out frustum
b. in frustum
c. intersect frustum - then do a frustum box test
in? out? intersect?


By Z you mean height? different axis than me :). You still need to test the height against the infinite planes of the quadtree's quads because what if your frustum has turned? the Roll, in yaw-pitch-roll? IE. flying a plane

PS. You dont hafta squish yer frustum planes down. They form a 6 sided box already which means something hasta either be IN it or OUT of it, or INTERSECTING it. Which you would hafta render it if its IN or INTERSECTING.

In all reality all you have to do is a box-box test, but when traversing a quadtree, you dont want to test EVERY quad by a box-box because that would be VERY cpu intensive and waste alot of precious time. So test by easier methods first. Most of the quadtree will be outside and by using multiple easy tests then you save alot of time for when something is inside of it.





[Edited by - xsirxx on March 10, 2005 7:29:55 PM]

Share this post


Link to post
Share on other sites
Okay, a bit confusion there :)

The reason I can't do plane sphere tests, is that I don't want to limit myself to a certain height (although doing so might be wise, at this point).

However, since I think I may have found a simple solution, I'm gonna give it a try. What I intend to do (gonna write it today, when I can clear some free time), is to extract the 8 corners of my frustum (dunno how to do that yet).

Then , I'll move them to z = 0.0f, to flaten the frustum to 2D. Then, I'll construct a bounding square around the 8 points (that's simple) and finally, test all my quads against this specific square.

Sounds quite simple, all things considered. I just need to find out how to extract the 8 points.

What do you guys think, is this viable?

Share this post


Link to post
Share on other sites
I wouldnt do that, box-box testing is a HUGE waste of cpu time. Try it that way, then try it the other way if ya like. Its worth it now to write sphere-sphre, cone-sphere, box-box testing... You WILL use all this code over and over and over. I can give you examples of code for these tests, but I would study them, go over and really understand them. This is some easy 3d code comparable to what else is out there :). Also this is not the fastest, but its easy to understand for me and runs :).

Also your in NO WAY limiting height at all, nor do ya need to know a height. thats the beauty, its height free :).



bool Cone::Intersects(const Sphere& sphereInc) const
{
Vector vecU, vecD;
float fSin = sinf(this->fAngle);
float fCos = cosf(this->fAngle);
vecU = this->vecEye - (sphereInc.r / fSin) * this->vecAxis;
vecD = sphereInc.c - vecU;

if( vecAxis.Dot(vecD) >= (vecD.Magnitude() * fCos) )
{
// center is inside K''
vecD = sphereInc.c - this->vecEye;
if( -this->vecAxis.Dot(vecD) >= (vecD.Magnitude() * fSin) )
{
//center is inside K'' and inside K'
return (vecD.Magnitude() <= sphereInc.r);
}
else
{
//center is inside K'' and outside K'
return true;
}
}
else
{
//center is outside K''
return false;
}
}







bool Sphere::Intersects(const Sphere& sphereInc) const
{
Vector vSepAxis = (this->c - sphereInc.c);
float fRadiiSum = (this->r + sphereInc.r);
if( vSepAxis.MagnitudeSQ() < (fRadiiSum * fRadiiSum) )return (true);

return(false);
}







eCD AABB::ContainsPoint2d(Vector &pvecInc)
{

Plane planeL;
Plane planeR;
Plane planeT;
Plane planeB;

planeL = Plane( vPoint[LBL], Vector( vPoint[LBL].x, (vPoint[LBL].y - 1), ((vPoint[LBL].z + vPoint[LTL].z) / 2)), vPoint[LTL]);
planeT = Plane( vPoint[LTL], Vector( ((vPoint[LTL].x + vPoint[LTR].x) / 2), (vPoint[LTL].y - 1), vPoint[LTL].z), vPoint[LTR] );
planeR = Plane( vPoint[LTR], Vector( vPoint[LTR].x, (vPoint[LTR].y - 1),((vPoint[LTR].z + vPoint[LBR].z) / 2)), vPoint[LBR] );
planeB = Plane( vPoint[LBR], Vector( ((vPoint[LBR].x + vPoint[LBL].x) / 2), (vPoint[LBR].y - 1), vPoint[LBR].z), vPoint[LBL] );

if( planeL.ClassifyPoint(pvecInc) == Plane::eCP::BACK )return OUTSIDE;
else if( planeT.ClassifyPoint(pvecInc) == Plane::eCP::BACK )return OUTSIDE;
else if( planeR.ClassifyPoint(pvecInc) == Plane::eCP::BACK )return OUTSIDE;
else if( planeB.ClassifyPoint(pvecInc) == Plane::eCP::BACK )return OUTSIDE;
else
{
return INSIDE;
}
}






I REALLY REALLY REALLY cant stress how important it is that you go the distance on this quadtree. If the quadtree is halfassed or the right managing doesnt go into it, it can kill your game. Your going to run this code THOUSANDS and THOUSANDS of times per render, more than any other code(most likely) :).

PS. I used a VERY nice tutorial at one point for alot of these ideas, so if any1 can recognize what tutorial it was and has it, please post a link! :)

Share this post


Link to post
Share on other sites
Okay, my problem isn't the part of checking against the frustum. Really, I have all the code I need to check both sphere, a box and whenever I need against the frustum.

What I'm missing is a way to convert my quadtree node to either a sphere, a box or any other shape I know how to check against the frustum.

In fact, speed is not (yet) an issue.

I need to find a way to check a quadtree node against the frustum, and naturally, since it's a quadtree, and not an octree, it isn't limited in height (I don't plan to limit it).

I hope this clears up my issue some more.

I'll attemp to implement my method tomorrow, and post back some results.

Share this post


Link to post
Share on other sites
Yea, but you really dont have a problem at all. You already have all your box-sphere-cone testing code, alls ya hafta do is take the box against the frustum by the most expensive test there is:


int Frustum::ContainsAABB(AABB& pAABBInc)
{
Plane::eCP localeeCP;
int iPointOut = 0;
int iPlaneIn = 0;

for(int i = 0; i < MAX_PLANES; i++)
{
iPointOut = 0;

for(int ii = 0; ii < MAX_POINTS; ii++)
{
localeeCP = plPlane[i].ClassifyPoint(pAABBInc.vPoint[ii]);
if(localeeCP == Plane::eCP::BACK)iPointOut++;
}

if(iPointOut == MAX_POINTS) return(OUTFRUSTUM);
else if(iPointOut == 0) iPlaneIn++;
}

if(iPlaneIn == MAX_PLANES) return(INFRUSTUM);

return(INTERSECTFRUSTUM);
}




and test like so


switch(m_Camera->frFrustum.ContainsSphere(pTL->sphere))
{
case OUTFRUSTUM:
bSkip = true;
break;

case INFRUSTUM:
bLocalTest = false;
break;

case INTERSECTFRUSTUM:

switch(m_Camera->frFrustum.ContainsAABB(pTL->aabb))
{
case INFRUSTUM:
bLocalTest = false;
break;
case OUTFRUSTUM:
bSkip = true;
break;
case INTERSECTFRUSTUM:
break;
}

break;
}




but in all reality testing against sphere-cone is much nicer and doesnt have the height problem either. This tests against points of the box against the planes of the frustum.

Share this post


Link to post
Share on other sites
But where do I get the AABB box from? If this were an octree, I'd have the AABB, but in a quadtree, I don't have an AABB box, all I have is a square with unlimited height.

Heres a diagram I made to show the difference.

Gonna try to implement my method today and see how it goes.

Free Image Hosting at www.ImageShack.us

Blue is an AABB box,
Red is a quadtree node.

Share this post


Link to post
Share on other sites
Success! or at least, sort of :).

I finally got about an hour of free time, and managed to write all the code I needed. Though it's not working with my object tree, I was so pleased with how fast this check was, that I decided to add it to my terrain tree too, as the first check. It works very well in my terrain tree, so I suspect an error in my object tree is what's causing problems, and not the actual testing code.

Actually, the hardest part turned out to be finding the frustum's AABB. Once I had that, the checks were very simple.

Heres the code I added:
Creating the frustum's AABB:

D3DXMATRIX tmpMat;
float flt;
D3DXMatrixInverse(&tmpMat, &flt, &mat); // mat is the proj * view * world matrix.

// Calculate AABB;
D3DXVECTOR3 vec = D3DXVECTOR3(1.0f, 1.0f, 1.0f);
D3DXVec3TransformCoord(&vec, &vec, &tmpMat );
m_AABB[0] = vec.x;
m_AABB[1] = vec.x;
m_AABB[2] = vec.y;
m_AABB[3] = vec.y;

vec = D3DXVECTOR3(-1.0f, 1.0f, 1.0f);
D3DXVec3TransformCoord(&vec, &vec, &tmpMat );
m_AABB[0] = max(vec.x, m_AABB[0]);
m_AABB[1] = min(vec.x, m_AABB[1]);
m_AABB[2] = max(vec.y, m_AABB[2]);
m_AABB[3] = min(vec.y, m_AABB[3]);

vec = D3DXVECTOR3(1.0f, -1.0f, 1.0f);
D3DXVec3TransformCoord(&vec, &vec, &tmpMat );
m_AABB[0] = max(vec.x, m_AABB[0]);
m_AABB[1] = min(vec.x, m_AABB[1]);
m_AABB[2] = max(vec.y, m_AABB[2]);
m_AABB[3] = min(vec.y, m_AABB[3]);

vec = D3DXVECTOR3(-1.0f, -1.0f, 1.0f);
D3DXVec3TransformCoord(&vec, &vec, &tmpMat );
m_AABB[0] = max(vec.x, m_AABB[0]);
m_AABB[1] = min(vec.x, m_AABB[1]);
m_AABB[2] = max(vec.y, m_AABB[2]);
m_AABB[3] = min(vec.y, m_AABB[3]);

vec = D3DXVECTOR3(1.0f, 1.0f, -1.0f);
D3DXVec3TransformCoord(&vec, &vec, &tmpMat );
m_AABB[0] = max(vec.x, m_AABB[0]);
m_AABB[1] = min(vec.x, m_AABB[1]);
m_AABB[2] = max(vec.y, m_AABB[2]);
m_AABB[3] = min(vec.y, m_AABB[3]);

vec = D3DXVECTOR3(-1.0f, 1.0f, -1.0f);
D3DXVec3TransformCoord(&vec, &vec, &tmpMat );
m_AABB[0] = max(vec.x, m_AABB[0]);
m_AABB[1] = min(vec.x, m_AABB[1]);
m_AABB[2] = max(vec.y, m_AABB[2]);
m_AABB[3] = min(vec.y, m_AABB[3]);

vec = D3DXVECTOR3(1.0f, -1.0f, -1.0f);
D3DXVec3TransformCoord(&vec, &vec, &tmpMat );
m_AABB[0] = max(vec.x, m_AABB[0]);
m_AABB[1] = min(vec.x, m_AABB[1]);
m_AABB[2] = max(vec.y, m_AABB[2]);
m_AABB[3] = min(vec.y, m_AABB[3]);

vec = D3DXVECTOR3(-1.0f, -1.0f, -1.0f);
D3DXVec3TransformCoord(&vec, &vec, &tmpMat );
m_AABB[0] = max(vec.x, m_AABB[0]);
m_AABB[1] = min(vec.x, m_AABB[1]);
m_AABB[2] = max(vec.y, m_AABB[2]);
m_AABB[3] = min(vec.y, m_AABB[3]);



the checkAABB function:

bool cFrustum::CheckAABB(D3DXVECTOR3 Center, D3DXVECTOR3 halfSize)
{
if (m_AABB[0] > Center.x - halfSize.x)
if (m_AABB[1] < Center.x + halfSize.x)
if (m_AABB[2] > Center.y - halfSize.y)
if (m_AABB[3] < Center.y + halfSize.y)
return true;
return false;
}



And heres how I call a check:

// Render this quadtree.
int cQuadTree::Render(LPDIRECT3DDEVICE9 d3dDevice, cCamera *Camera, cFrameManager *FrameManager)
{
if (!m_HasChildren)
{
cTerrainCullData CullData = m_Terrain->GetCullData();
if (Camera->GetFrustum()->CheckSphere(CullData.Center.x, CullData.Center.y, CullData.Center.z, CullData.Radius))
{
return m_Terrain->Render(d3dDevice, Camera, FrameManager);
}
return 0;
}
else
{
D3DXVECTOR3 vec = D3DXVECTOR3(m_TSets.Width / 10.0f, m_TSets.Height / 10.0f, 0.0f);
if (Camera->GetFrustum()->CheckAABB(m_CullData.Center, vec))
{
if (Camera->GetFrustum()->CheckSphere(m_CullData.Center.x, m_CullData.Center.y, m_CullData.Center.z, m_CullData.Radius))
{
int sum = 0;
for(short i=0; i<2; i++)
for(short j=0; j<2; j++)
{
sum += m_Children[i + j * 2].Render(d3dDevice, Camera, FrameManager);
};
return sum;
}
return 0;
}
return 0;
};
}


BTW, I got my last post wrong, the red is the AABB, and the blue is the quadtree node.

Share this post


Link to post
Share on other sites

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