Quadtree Frustum culling
Author
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...
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
Author
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.
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.
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
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
Author
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.
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.
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?
Author
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 ;).
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 ;).
here is an example of how I built my frustum, I have a class called camera which holds this frustum in it....
this is where I update it, by ripping the planes from the matrix. Its pretty standard code for doing it in directx.
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]
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 = Plane( Vector( matLocal._14 + matLocal._11, matLocal._24 + matLocal._21, matLocal._34 + matLocal._31 ), matLocal._44 + matLocal._41); plPlane.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 = Plane( Vector( matLocal._14 - matLocal._11, matLocal._24 - matLocal._21, matLocal._34 - matLocal._31 ), matLocal._44 - matLocal._41); plPlane.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]
Author
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?
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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement