PDA

View Full Version : Box visibility

Catman
02-26-2003, 03:25 AM
Hello! I need some help here. I'd like to test if a box is visible. I tried checking the visibility of the corners but it doesn't seem to be enough. I think I should test the visibility of the edges but I can't think of a fast algorithm to do this. Are there any tutorials or papers dealing with this?

Eric
02-26-2003, 03:35 AM
You can have a look here:
http://www.markmorley.com/opengl/frustumculling.html

There's a topic that says "Is the box in the frustum?" which gives a way of solving your problem.

Regards,

Eric

Catman
02-26-2003, 03:37 AM
Thanks, I'll have a look at that...

antipop
02-26-2003, 04:37 AM
Originally posted by Catman:
Thanks, I'll have a look at that...

An elaboration on the algortihm in the link: A box is the convex hull of its eight corners. The view frustum is a convex set as well, defined by the intersection of six (convex) half-spaces.

Thus, if the points which define a convex hull is completely outside one of these half-spaces, the convex hull (the box) is outside as well.

A more general algortihm (from the top of my head):

For each point defining the convex hull (in this case, the eight corners) assign a bitmask of six bits. Each of these bits correspond to one of the six half spaces. Run through the vertices and set the bits: if the point is inside the half-space, the bit is 0, otherwise it is 1.

Run through the vertices yet another time and OR together the bitmasks. If the result is %111111 the shape is probably visible, otherwise all points are outside at least one of the half spaces.

This culling stategy works with any kind of geometry which has the convex hull of some points as a boundary volume. Beziers are always inside the convex hull of the control points, as well as B-splines, and quite some subdivision schemes in addition.

Further, one may utilize the local support property (if the geometry scheme has it) and get quite sharp bounding volumes on a patch-by-patch basis.

Catman
02-26-2003, 06:47 AM
I think this algorithm will work fine for me...

jwatte
02-26-2003, 09:59 AM
Antipop,

You are not correct. Consider the case where one point is to the left of the frustum (entirely outside) and one point is above the frustum (entirely outside). However, the edge between these two points intersects the frustum. The two volumes intersect; you need to draw the geometry, but just culling based on the points would falsely reject it.

147-2
02-26-2003, 10:39 AM
Antipop is right, you're not reading what he posted correctly. If the box is completely to the left of the left culling plane, then the box is outside. Same thing goes for each of the other planes. The error exists when you have an object that is completely outside the frustum, but still has elements inside each of the planes. A good example of this is a box that lays diagonally, the left side of it goes lower than the top frustum but left of the left frustum, the top right of the object goes right of the left frustum but above the top frustum such that it never actually passes thru the frustum. In that case you will get a false positive. There are no false negatives that I know of with this test.