Archived

This topic is now archived and is closed to further replies.

VanKurt

Quad vs frustum

Recommended Posts

Hi there! A little 2D problem: What would be the fastest way to check if a quad (given by the points ABCD) is inside a viewing frustum (given by the Camera''s X and Y pos + the cam''s yaw) ??? (This will ( hopefully ;-) ) later be used in my quad-tree!) Thanks a 1000 times !!!!

Share this post


Link to post
Share on other sites
A quad? Like a square with 2 triangles made up of 4 vertices?
There''s a lot of confusion about this, so why don''t we call a QuadTree "Quad" a Voxel, which is an arbitrary 3D Volume (which is what it is).

Anyhow, your QuadTree Voxel could be represented by a Sphere (or Cube) and you could just do a sphere-frustum check to determine whether it''s in there or not. That''s the fastest way to do it. The Sphere to Frustum check would use the Distance Formula to determine whether the sphere intersects, is contained, or is not contained. See, since each quadtree has a size or width or whatever measurement, you can use that as the radius for you sphere. Make sense? It works super fast and I reccomend it.

There''s a nice resource on this on the net but I don''t have the link right now. I quick search would probably find. Good luck!


"Love all, trust a few. Do wrong to none." - Shakespeare

Dirge - Aurelio Reis
www.CodeFortress.com
Current Causes:
Nissan sues Nissan

Share this post


Link to post
Share on other sites
you mean something like this..


    
bool CGLCamera::QuadInFrustum(float *q)
{
int p;
float x1,x2,y1,y2,z1,z2;

x1 = *q;
x2 = *(q + 1);
y1 = *(q + 2);
y2 = *(q + 3);
z1 = *(q + 4);
z2 = *(q + 5);

for( p = 0; p < 6; p++ )
{
if( frustum[p][0] * x1 + frustum[p][1] * y1 + frustum[p][2] * z1 + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * x2 + frustum[p][1] * y1 + frustum[p][2] * z1 + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * x1 + frustum[p][1] * y2 + frustum[p][2] * z1 + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * x2 + frustum[p][1] * y2 + frustum[p][2] * z1 + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * x1 + frustum[p][1] * y1 + frustum[p][2] * z2 + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * x2 + frustum[p][1] * y1 + frustum[p][2] * z2 + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * x1 + frustum[p][1] * y2 + frustum[p][2] * z2 + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * x2 + frustum[p][1] * y2 + frustum[p][2] * z2 + frustum[p][3] > 0 )
continue;
return false;
}
return true;

}


q is a pointer to 6 floats, which are the end points of the quad. the quad has a fixed height which is quite large.

the frustum is extracted from the viewing frustum.

then i just use the plane equation to check the distance.

sorry about the code being quite bad, i did this when i was learning to build my first quadtree. used it on a heightmap.

Its my duty, to please that booty ! - John Shaft

[edited by - jwalker on August 13, 2002 10:03:10 PM]

Share this post


Link to post
Share on other sites