• Advertisement
Sign in to follow this  

How to do frustum checks for a QuadTree?

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

Right now im using 3d boxes to check to see if nodes are in the view frustum. Thats a problem because I have to set a arbitrary 'height' for the boxes, when all I really care about are the x and z coords. This is causing a lot of my nodes to be 'partially' in the view frustum, because they are being clipped at some vertical point (this leads to unnecessary checks). Is there anyway to modify the following code so that it works in a more 2d, quadtree sense (ignoring y/height)? //returns 0 if completely outside, 1 if partialy inside, and 2 if completely inside int isBoxInFrustum( float x, float y, float z, float xsize, float ysize, float zsize ) { int p; int c; int c2 = 0; for( p = 0; p < 6; p++ ) { c = 0; if( frustum

[0] * (x - xsize) + frustum

[1] * (y - ysize) + frustum

[2] * (z - zsize) + frustum

[3] > 0 ) c++; if( frustum

[0] * (x + xsize) + frustum

[1] * (y - ysize) + frustum

[2] * (z - zsize) + frustum

[3] > 0 ) c++; if( frustum

[0] * (x - xsize) + frustum

[1] * (y + ysize) + frustum

[2] * (z - zsize) + frustum

[3] > 0 ) c++; if( frustum

[0] * (x + xsize) + frustum

[1] * (y + ysize) + frustum

[2] * (z - zsize) + frustum

[3] > 0 ) c++; if( frustum

[0] * (x - xsize) + frustum

[1] * (y - ysize) + frustum

[2] * (z + zsize) + frustum

[3] > 0 ) c++; if( frustum

[0] * (x + xsize) + frustum

[1] * (y - ysize) + frustum

[2] * (z + zsize) + frustum

[3] > 0 ) c++; if( frustum

[0] * (x - xsize) + frustum

[1] * (y + ysize) + frustum

[2] * (z + zsize) + frustum

[3] > 0 ) c++; if( frustum

[0] * (x + xsize) + frustum

[1] * (y + ysize) + frustum

[2] * (z + zsize) + frustum

[3] > 0 ) c++; if( c == 0 ) return 0; if( c == 8 ) c2++; } return (c2 == 6) ? 2 : 1; } //end isBoxInFrustum() *ps how do i get my code into one of those neat 'code boxes'?

Share this post


Link to post
Share on other sites
Advertisement
Don't know how much help this will be, but here goes...

I've been doing some work with quadtrees recently, and the whole idea of frustum culling (assuming you are working in a 3D view space) is that you have height, width, and depth. I'll assume you're going to use a camera of some sort, in which case the height does come in handy when rotating about the place, and culling what isn't seen, so if you can try and include proper height info.

If you really don't want a full 3D culling system, I'd recommend changing how you handle the frustum - make that 2d, and code based on that.Project the 3d frustum onto the 2d x-z plane, and once you have that, intersection as normal for 2d objects (quadtree nodes with the y value stripped - method of separating axis seems ok for that, though I've only just started working with it).

Share this post


Link to post
Share on other sites
Quote:
Original post by ZealousEngine
Is there anyway to modify the following code so that it works in a more 2d, quadtree sense (ignoring y/height)?

//returns 0 if completely outside, 1 if partialy inside, and 2 if completely inside
int isBoxInFrustum( float x, float y, float z, float xsize, float ysize, float zsize )
{
int p;
int c;
int c2 = 0;

for( p = 0; p < 6; p++ )
{
c = 0;
if( frustum

[0] * (x - xsize) + frustum

[1] * (y - ysize) + frustum

[2] * (z - zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x + xsize) + frustum

[1] * (y - ysize) + frustum

[2] * (z - zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x - xsize) + frustum

[1] * (y + ysize) + frustum

[2] * (z - zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x + xsize) + frustum

[1] * (y + ysize) + frustum

[2] * (z - zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x - xsize) + frustum

[1] * (y - ysize) + frustum

[2] * (z + zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x + xsize) + frustum

[1] * (y - ysize) + frustum

[2] * (z + zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x - xsize) + frustum

[1] * (y + ysize) + frustum

[2] * (z + zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x + xsize) + frustum

[1] * (y + ysize) + frustum

[2] * (z + zsize) + frustum

[3] > 0 )
c++;
if( c == 0 )
return 0;
if( c == 8 )
c2++;
}
return (c2 == 6) ? 2 : 1;
} //end isBoxInFrustum()


u mean if there is no y and no ysize like y==0 and ysize==0? let me guess:


int isBoxInFrustum( float x, float y, float z, float xsize, float ysize, float zsize )
{
int p;
int c;
int c2 = 0;

for( p = 0; p < 6; p++ )
{
c = 0;
if( frustum

[0] * (x - xsize) + frustum

[1] * (0 - 0) + frustum

[2] * (z - zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x + xsize) + frustum

[1] * (0 - 0) + frustum

[2] * (z - zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x - xsize) + frustum

[1] * (0 + 0) + frustum

[2] * (z - zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x + xsize) + frustum

[1] * (0 + 0) + frustum

[2] * (z - zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x - xsize) + frustum

[1] * (0 - 0) + frustum

[2] * (z + zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x + xsize) + frustum

[1] * (0 - 0) + frustum

[2] * (z + zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x - xsize) + frustum

[1] * (0 + 0) + frustum

[2] * (z + zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x + xsize) + frustum

[1] * (0 + 0) + frustum

[2] * (z + zsize) + frustum

[3] > 0 )
c++;
if( c == 0 )
return 0;
if( c == 8 )
c2++;
}
return (c2 == 6) ? 2 : 1;
} //end isBoxInFrustum()


or maybe a bit shorter


int isBoxInFrustum( float x, float y, float z, float xsize, float ysize, float zsize )
{
int p;
int c;
int c2 = 0;

for( p = 0; p < 6; p++ )
{
c = 0;
if( frustum

[0] * (x - xsize) + frustum

[2] * (z - zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x + xsize + frustum

[2] * (z - zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x - xsize)) + frustum

[2] * (z + zsize) + frustum

[3] > 0 )
c++;
if( frustum

[0] * (x + xsize) + frustum

[2] * (z + zsize) + frustum

[3] > 0 )
c++;
if( c == 0 )
return 0;
if( c == 4 )
c2++;
}
return (c2 == 6) ? 2 : 1;
} //end isBoxInFrustum()

i did not test it, but should work ;)

greets
rapso

Share this post


Link to post
Share on other sites
I guess each of your objects that are passed to the quadtree have a bounding box, so you could find the maximum and minimum height of your quadtree node and adjust it appropriately. If you remove an object whose bbox is < you maxheight and > you min height you can just get rid of it

if the objects min or max height is equal to your node's min/max height you have to recalculate the height by traversing your object list and finding the new min and max value.

This way you are basically doing a 3D box check, similar to 3D box checks in octrees, however you get rid of unneeded quadtree nodes here and there.


In my current quadtree implementation I use a fixed min and max height, but this is a matter of a few lines of code to add this.

Share this post


Link to post
Share on other sites
@ rapso

That code will only work if I extract a special '2d' frustum (ie set the camera to a 0 degree x angle). Otherwise the x angle of the camera messes things up. However if I extract a '0 degree x angle frustum', then I have a problem when you look straight up or straight down (youll be able to see slightly BEHIND your position, but as far as the quad tree is concerned, everything behind you is behind the 2d view frustum).

@ mirv

Ive thought about calculating the height/size of these boxes, but it seems like a lot of extra checking. And a fixed size has to be so large that it results in a LOT of partially in view boxes, which lead to more and more checks. Heck even dynamic sized boxes result in boxes being clipped at some point along the y axis (which I dont care about since the world is mostly flat), which lead to more and more checks (all 'partially in view' boxes have to do 4 more checks for all their children, and so on).

I think the best solution is to extract a 2d frustum (simply based on the y angle of the camera), then figure out a way to deal with situations where you might catch a glimpse of nodes BEHIND the camera (ie if you look straight up or straight down).

Anyone have any more ideas?

Share this post


Link to post
Share on other sites
What when you look straight up? How will this work out then?

Share this post


Link to post
Share on other sites
Yes if I just did a 'flat' 2d frustum check (ignoring height) that WOULD be a problem if you looked straight up. Due to the fov of the camera, youd see a little bit behind yourself, but the quadtree would consider everything behind you out of view (due to it not factoring the x angle of the camera).

So how would you solve that problem?

Share this post


Link to post
Share on other sites

I ended up giving up the quadtree as a spatial partitioning system, since it is too 2d.

The problem was always that my bound boxes got too big in height.

Well anyway, back to your problem.

- I think that you should do the full 3d-check (that code is useful with the octree also).

- Search the net for a AABB in a frustum intersection check.

http://www.cescg.org/CESCG-2002/DSykoraJJelinek/

gives some good answers.

- I'd suggest implementing a simple vector class in order to make your code more readable.

Cheers !

Share this post


Link to post
Share on other sites
You could use a kd-tree for the organization of the AABBs, that should make collision detection a matter of traversal and bounds checking against all bounding boxes which lie (partially or wholly) lie within the box in question's volume.

Share this post


Link to post
Share on other sites
Quote:
Original post by ZealousEngine
Yes if I just did a 'flat' 2d frustum check (ignoring height) that WOULD be a problem if you looked straight up. Due to the fov of the camera, youd see a little bit behind yourself, but the quadtree would consider everything behind you out of view (due to it not factoring the x angle of the camera).

So how would you solve that problem?


The way I suggested above

You partition your scene in 2D(Quadtree) but you calculate 3boxes of each quadtree node when you add or remove objects from a node.

This way you can simply clip the quadtree nodes against the 3D frustrum

Algorithm:
1. Quadtree node <-> frustrum test (with sphere surround the quadtree node)
2. If the quadtree node's sphere touches the frustrum do a frustrum on box intersection test
a) You got the node's bbox's 8 corner vertices. ==> 12 edges

for each edge e do
for each frustrum plane p do
v = p.intersec(edge e);
for each frustrum plane p2 do
if
p2.onplane(v) == (onplane || at the back)
{
return frustrum intersects bbox
}


thats basically the algorithm.
Id just checks if the bbox's edges intersect the frustrum planes and if the intersection points ly on the frustrum or are inside the frustrum

Share this post


Link to post
Share on other sites
Ok thanks for the input guys, so it sounds like you just HAVE to calculate the y height for all your nodes and keep things 3d. Its just a shame, because that means a LOT of my nodes are going to be entirely 'inside' the frustum (at least for the left and right plains, which are all I really care about since my landscape is mostly flat), HOWEVER either the top, far, or bottom plain will still CLIP these boxes due to their height (each clip results in at LEAST 4 more checks, potentially dozens more).

Well I guess thats how its done eh?

Im just wondering if anyone else sees a problem with this. Imagine a completely flat landscape with very short boxes for all your nodes, now imagine tilting the camera up sligltly so all those box are only partially in view. JUST like that youve gone from incredibly fast checks (most boxes were entirely in view, thus only one node check was required), to incredibly slow checks (now EVERY box has to be checked ALL THE WAY down to the finest leaf, simply because every single node is now 'partially in view').

Share this post


Link to post
Share on other sites
Testing a box against the frustums should be pretty fast, even if you have lots of them.

Keeping the min and max height of your quads is useful for other reasons like projecting the difference into screen space to determine if you should change lod.

BennyW

Share this post


Link to post
Share on other sites
Sure I never said checking a single box/node was slow, just unnecessary. But it does become somewhat slow when a node is clipped at some point along its height (which I dont care about, my landscape is flat), and then that one box check turns into at least 4 more box checks, and so on.

Share this post


Link to post
Share on other sites
You could add another test where you check whether the 8 corners of the bbox are behind your left&right planes if so you don t have to do the frustrum bbox intersection further more

behind the planes means inside the frustrum, I have seen implementations that take the front side as the inside.

Share this post


Link to post
Share on other sites

Well the height issue will be always a problem. Consider that your landscape will have considerable height differences, such as Japanese terrain with mountains ranging from 0m to 1000m or more.

With a 2d approach you'll end up rendering non visible blocks. Actually, with the 2d approach you'll _always_ render blocks which may not be visible.

Don't worry, about the nodes totally inside the frustum. I think that they are the cheapest nodes after the totally outside case when concerning calculations.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement