Frustum checks for a quadtree - GameCreators Forum

Author

Message

Zeal

22

Years of Service

User Offline

Joined: 10th Oct 2002

Location: Colorado Springs, CO

Posted: 30th May 2006 02:19 Edited at: 30th May 2006 02:20

Link

So I got my quad tree working, but atm 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.

Is there anyway to modify the following code so that it works in a more 2d, quadtree sense (ignoring y/height)?

int CubeInFrustum( float x, float y, float z, float size )
{
   int p;
   int c;
   int c2 = 0;

for( p = 0; p < 6; p++ )
   {
      c = 0;
      if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
         c++;
      if( c == 0 )
         return 0;
      if( c == 8 )
         c2++;
   }
   return (c2 == 6) ? 2 : 1;
}

+ Code Snippet

int CubeInFrustum( float x, float y, float z, float size )
{
   int p;
   int c;
   int c2 = 0;

   for( p = 0; p < 6; p++ )
   {
      c = 0;
      if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
         c++;
      if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
         c++;
      if( c == 0 )
         return 0;
      if( c == 8 )
         c2++;
   }
   return (c2 == 6) ? 2 : 1;
}

All you need is zeal

Back to top

Profile PM Email

Lost in Thought

21

Years of Service

User Offline

Joined: 4th Feb 2004

Location: U.S.A. : Douglas, Georgia

Posted: 30th May 2006 06:49

Link

Sorry I haven't gotten around to this yet

However the easiest way would be to just not check the top an bottom planes (p=2 and p=3) But remember that the frustum is cone shapped so if you look far enough up or down the taper of the other 4 planes may still cut it out. May be worth a shot though.

Back to top

Profile PM Email

Zeal

22

Years of Service

User Offline

Joined: 10th Oct 2002

Location: Colorado Springs, CO

Posted: 31st May 2006 01:08

Link

NP I got the code itself working (ended up writing a lot of it longhand :p but it works damnit). I have a couple ideas that might work for this issue, will test tonight.

All you need is zeal

Back to top

Profile PM Email

Lost in Thought

21

Years of Service

User Offline

Joined: 4th Feb 2004

Location: U.S.A. : Douglas, Georgia

Posted: 31st May 2006 06:38 Edited at: 31st May 2006 07:12

Link

Why didn't you match the y size and position of each bounding box by the min and max vert positions of the limbs inside? I still haven't had much time to look into this. Messing with it as time permits. All of my systems take longer to reset all the flags in DBP than the culling

So far the fastest code has been a simple sphere plus box test with no trees at all for complex levels and just simply sphere testing for simple levels.

I still want to find a fast and all purpose tree of some sort in DBP code though for everyone to use. Did you do something similar to what you posted earlier? I am going to attemp to enclose the frustum in a sphere and then use a simple sphere to sphere test followed by a box to frustum test. But I am having a hard time trying to fit the sphere to the frustum lol.

I may just have to stop and learn c++ first as all the codes and articles I can find are written for it.

[edit] Also I was using spheres for my quadtree bounds. They are not as accurate, but require from 1 to 6 tests instead of 8 to 48 for the boxes and spheres. The I used box testing to test the children inside the spheres that were partially inside the frustum and just showed all the children of the spheres that were totally inside.

Of course I had so many checks (based on some c++ codes I found) that it was slow as DBP is slow lol.

Back to top

Profile PM Email

Zeal

22

Years of Service

User Offline

Joined: 10th Oct 2002

Location: Colorado Springs, CO

Posted: 31st May 2006 11:28 Edited at: 31st May 2006 11:33

Link

Quote: "I may just have to stop and learn c++ first as all the codes and articles I can find are written for it."

Its really not that bad, you should just do it. Ive never taken a single programming class period, and it took me a matter of days to convert my project from basic to c++. I did have a bit of HLSL experience (which is exactly like c++), but other than that all I needed were a few online tuts I found via google.

In short, do it.

About the frustum checks, yeah I could factor the size of each bounding box, but it would require a tad more work, thus that much slower. But the point is, I dont care about the 'height' of these boxes (quad trees are for flat landscapes, like mine). I want to be able to speed things up by saying, hey, if a node is in front of you, just consider it in view, regardless if the top and bottom plains are clipping it. Cause when the top or bottom plains clip a node, it results in at LEAST 4 more checks. (its funny, the speed of my quadtree program goes up and down greatly depending on the x angle of the camera, its just dumb).

Some guy on gamedev suggested this...

+ Code Snippet

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[p][0] * (x - xsize) + frustum[p][2] * (z - zsize) + frustum[p][3] > 0 )
c++;
if( frustum[p][0] * (x + xsize + frustum[p][2] * (z - zsize) + frustum[p][3] > 0 )
c++;
if( frustum[p][0] * (x - xsize)) + frustum[p][2] * (z + zsize) + frustum[p][3] > 0 )
c++;
if( frustum[p][0] * (x + xsize) + frustum[p][2] * (z + zsize) + frustum[p][3] > 0 )
c++;
if( c == 0 )
return 0;
if( c == 4 )
c2++;
}
return (c2 == 6) ? 2 : 1;
} //end isBoxInFrustum()

Basically it just uses 'flat' boxes, meaning they will go out of view if you look up or down ever so slightly. No good.

The onlything ive been able to think of is, extract a special '2d frustum' by setting the camera x angle to 0. This would work great except for one part - if you look straight up or down, youll see slightly behind your character, but the 2d frustum considers EVERYTHING behind you out of view.

Oh how I hate quadtrees

All you need is zeal

Back to top

Profile PM Email

Lost in Thought

21

Years of Service

User Offline

Joined: 4th Feb 2004

Location: U.S.A. : Douglas, Georgia

Posted: 31st May 2006 13:04

Link

This looks like it may be faster than the method I'm using since quad trees are AABB. You may want to try something like it. I'm still doing reseach now. I'll try and convert it to a basic style code later. Found here: http://skylab1.te.hik.se/projekt/grupp1/hemsidan/Doxygen/class_game_engine_1_1_math_1_1_frustum.html#d0ccce70e218ef9108d5b53b54dfb057

1 // ----------------------------------------------------------------------------
101 // Name: boxInFrustum()
102 // Desc: Check if a box is in frustum, and returns true or false.
103 // ----------------------------------------------------------------------------
104 bool Frustum::isPartiallyInside( const AABB& aabb ) const 
105 {
106         bool intersect = false;
107         Vector3 min;
108         Vector3 max;
109 
110         Vector3 aabbMin = aabb.getPosition(); //Gets the lower-left-close corner
111         Vector3 aabbMax = aabb.getPosition() + aabb.getDimensions(); //Gets the upper-right-far corner
112 
113         for ( int i = 0; i < 6; i++)
114         {               
115                 if ( m_plane[i].a <= 0 )
116                 {
117                         min.x = aabbMin.x;
118                         max.x = aabbMax.x;
119                 }
120                 else
121                 {
122                         min.x = aabbMax.x;
123                         max.x = aabbMin.x;
124                 }
125 
126                 if ( m_plane[i].b <= 0 )
127                 {
128                         min.y = aabbMin.y;
129                         max.y = aabbMax.y;
130                 }
131                 else
132                 {
133                         min.y = aabbMax.y;
134                         max.y = aabbMin.y;
135                 }
136 
137                 if ( m_plane[i].c <= 0 )
138                 {
139                         min.z = aabbMin.z;
140                         max.z = aabbMax.z;
141                 }
142                 else
143                 {
144                         min.z = aabbMax.z;
145                         max.z = aabbMin.z;
146                 }
147                 if ( m_plane[i].distance( min ) > 0 )
148                 {
149                         return false; //Box outide
150                 }
151                 if ( m_plane[i].distance( max ) >= 0 )
152                         intersect = true;
153         }
154         if (intersect == true)
155                 return true; //Intersect
156         else 
157                 return true; //Inside
158 }

+ Code Snippet

1 // ----------------------------------------------------------------------------
101 // Name: boxInFrustum()
102 // Desc: Check if a box is in frustum, and returns true or false.
103 // ----------------------------------------------------------------------------
104 bool Frustum::isPartiallyInside( const AABB& aabb ) const 
105 {
106         bool intersect = false;
107         Vector3 min;
108         Vector3 max;
109 
110         Vector3 aabbMin = aabb.getPosition(); //Gets the lower-left-close corner
111         Vector3 aabbMax = aabb.getPosition() + aabb.getDimensions(); //Gets the upper-right-far corner
112 
113         for ( int i = 0; i < 6; i++)
114         {               
115                 if ( m_plane[i].a <= 0 )
116                 {
117                         min.x = aabbMin.x;
118                         max.x = aabbMax.x;
119                 }
120                 else
121                 {
122                         min.x = aabbMax.x;
123                         max.x = aabbMin.x;
124                 }
125 
126                 if ( m_plane[i].b <= 0 )
127                 {
128                         min.y = aabbMin.y;
129                         max.y = aabbMax.y;
130                 }
131                 else
132                 {
133                         min.y = aabbMax.y;
134                         max.y = aabbMin.y;
135                 }
136 
137                 if ( m_plane[i].c <= 0 )
138                 {
139                         min.z = aabbMin.z;
140                         max.z = aabbMax.z;
141                 }
142                 else
143                 {
144                         min.z = aabbMax.z;
145                         max.z = aabbMin.z;
146                 }
147                 if ( m_plane[i].distance( min ) > 0 )
148                 {
149                         return false; //Box outide
150                 }
151                 if ( m_plane[i].distance( max ) >= 0 )
152                         intersect = true;
153         }
154         if (intersect == true)
155                 return true; //Intersect
156         else 
157                 return true; //Inside
158 }

Back to top

Profile PM Email

Zeal

22

Years of Service

User Offline

Joined: 10th Oct 2002

Location: Colorado Springs, CO

Posted: 31st May 2006 13:28

Link

hmm might be faster. of course it would have to be modified so it returned a 'partial' in view as well as true/false

All you need is zeal

Back to top

Profile PM Email

Lost in Thought

21

Years of Service

User Offline

Joined: 4th Feb 2004

Location: U.S.A. : Douglas, Georgia

Posted: 31st May 2006 13:40

Link

That appears to give you totally inside, totally outside, or partially in/out. What I don't understand is this part:

if ( m_plane[i].distance( min ) > 0 )

It appears to be close to this in my code:

if frustum#(p,3) * length vector3(min) > 0 or similar? But my c++ sucks. Would this be correct? 0_o

Back to top

Profile PM Email

Zeal

22

Years of Service

User Offline

Joined: 10th Oct 2002

Location: Colorado Springs, CO

Posted: 1st Jun 2006 00:43

Link

hmm well im just going off the guys description

+ Code Snippet

Desc: Check if a box is in frustum, and returns true or false.

and notice the function definition (the first part, where he names the function and sets the paramaters it takes). The first part of all functions is a data type (bool, float, int ect), in this case its bool, meaning the function can only return 0 or 1. Since 3 returns (0,1,2) are needed for a true, outside, partial, inside answer.

But heck just start using c++, and the current frustum code weve been using is PLENTY fast enough.

All you need is zeal

Back to top

Profile PM Email

Lost in Thought

21

Years of Service

User Offline

Joined: 4th Feb 2004

Location: U.S.A. : Douglas, Georgia

Posted: 1st Jun 2006 02:03

Link

I'm gonna change over soon I guess. I figure if I can find something that runs fast in DBP it should be lightning fast in c++ though

Back to top

Profile PM Email

Sorry your browser is not supported!

Dark GDK / Frustum checks for a quadtree