Fail-safe box frustum culling

if ONE of your bounding-box''s vertices is in the frustum, the box is visible

yep well if the camera is near the box and the box is very tall the box''s verts are outside the frustum but the box is inside

  +
  |_/
 _/
/ |
\_| 
  \_
  | \
  +
 

the plane is inside the frustum but its end points are outside

actually i solved the prob using sphere to frustum collision


/*ilici*/

a bit rusty with culling but if i remember correctly the only time a box is NOT visible is when all points are behind one of the planes else its potentially visible... not 100% sure its been a while since i played around with that

- Damage Inc.

Something I''ve heard:
Test if just one point is in front of every plane. It doesn''t have to be the same point. If there''s at least one point in front of each plane, it''s visible. Think of it: if a point actually is in the frustum, of course it''s in front of every plane. If it''s your scenario, There''s still ONE point in front of each plane, it''s just not the same point.

i test all the vertices of the box, if they are inside the frustrum, its totally visible, if one of the vertices is in, its intersecting, and if none are inside, it proceeds to check if the vertices of the frustrum are inside the box (intersecting the planes to find the vertices)

Ok, this way is 100 % foolproof as far as I know. When you test a bounding box against your frustum, first construct a plane eminating from the camera position splitting the view frustum right in two DIAGONALLY:

A--------B
|      / |
|    /   |
|  /     |
|/       |
D--------C
 

The square is your view frustum (they're actually planes) and the diagonal line BD is the 'clipping plane'. Now, my (axis aligned, though this works with OBB as wells...) bounding box would have points at like A and C, so if you have your points oriented different ways, you gotta change the orientation of the plane. Anyway, test these two points against this plane, and if the points are on different sides, the box is in the (at least partially, though it COULD be totally) view frustum. If this test evaluates to false, then you can resort to the test the points against the four viewing planes (or 6, depending on your system) and if at least one is in the frustum, you can see it. If BOTH of these tests are false, you DEFINATELY cannot see the object. Good luck!

I hope I explained this well! If you have problems, I could probably dig up some source code. :D

Chris Pergrossi
< ctoan >
My Realm

[edited by - ctoan on May 19, 2003 2:45:25 AM]

[edited by - ctoan on May 19, 2003 2:46:11 AM]

quote:

---

Original post by Ilici
yep well if the camera is near the box and the box is very tall the box''s verts are outside the frustum but the box is inside

  +
  |_/
 _/
/ |
\_| 
  \_
  | \
  +
  

the plane is inside the frustum but its end points are outside

actually i solved the prob using sphere to frustum collision


/*ilici*/

---

An object is only invisible from the frustum if ALL the vertices are on the outside of ALL the planes. If not, then it is eighter visible or intersecting. In the above example the vertices are on the outside of different planes. Also, both vertices are on the INSIDE of the far clipping plane. You should alter the order in which you check your vertices. What you do now is:

- take one vertices. cycle through all 6 planes. Check. Take next vertice.

What you should be doing is:
- take a plane. cycle through all vertices. check. Take next plane




Sander Maréchal
[Lone Wolves Game Development][RoboBlast][Articles][GD Emporium][Webdesign][E-mail]

quote:

---

Original post by smarechal

An object is only invisible from the frustum if ALL the vertices are on the outside of ALL the planes.

---

thats not making much sense is pretty impossible. if a point is outside the right plane then it must obviously be _inside_ the left plane (though inside and outside doesnt make any sense when talking about planes i guess everybody knows what we mean).

it is outside if all points are "outside" the same plane. if you test each vertex for every plane or each plane for every vertex doesnt matter, but i cycle through the points, test all the planes (not exactly, because in view space the plane is reduced to just a distance to compare against the points respective coord). 6 counters are increased (one for each plane) and if one of them is 8 at the end then its most likely outside (it will consider some boxes inside when they are not). if of course one point is inside then the box is visible. for your tree you want to know if its completely inside or intersecting. if all counters are 0 then all points are inside, if not and no counter is 8 then its intersecting.

Hehe, my mistake. You are right Trienco. That''s what I meant to say.

The reason why I said to take one plane and check it against all the vertices is to make it easier to check if all vertices lay on the outside of the same plane. Most frustum culling problems occuce because people do it the other way around. They make some function to check if a point is inside the frustum. When they want to check a box the simply call this point-in-frustum function 8 times (once for each vertex). And this gives the intersection problems this thread is about. You really need a separate box-in-frustum function.

Sander Maréchal
[Lone Wolves Game Development][RoboBlast][Articles][GD Emporium][Webdesign][E-mail]

Check the Q2-source which has an effective 100% proof routine. The frustum-culling loops through the 6 frustum planes and tests the most "extreme" vertex depending on the side of the current plane. Code:




I've used this since I found it, and it has worked beautifully

[edited by - coelurus on May 19, 2003 10:28:51 AM]

quote:

---

I''ve used this since I found it, and it has worked beautifully

---

does it work well with bounding boxes? sorry for my idiocy, just it looks very similar to the bounding-sphere code!

as an interesting point to note, the DirectX9 SDK has a full bounding-box/frustum culler in one of the samples. Granted you may not want DX-style, but maths is maths and I''m sure you can extract the stuff you want

Jack

DirectX 4 VB: All you need for multimedia programming in Visual Basic
Formula 1 Championship Manager, My Game Project.