Jump to content
  • Advertisement
Sign in to follow this  
ZealousEngine

How to do frustum checks for a QuadTree?

This topic is 4376 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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!