Geometric Approach – Testing Boxes

Testing a box is a little bit trickier than spheres and points. A simple way to do this is to test the eight corners of the box. A naive approach would be to consider that the box is outside of the frustum if all the points are outside the frustum. However the simple diagram shows that this is not always the case.

The points of the yellow box are all outside the frustum, yet the box is partially inside the frustum, hence it can’t be rejected. A safe way of solving the problem is to reject a box if, and only if, all points are on the wrong side of the same plane. In the figure above it is clear that there is no such plane for the yellow box.

There is a nasty side effect to this solution: in the figure below, the orange box, although totally outside the frustum will not be rejected according to this test. Two options are available: accept these boxes since the cost of testing should be kept to a minimum, or do some further testing.

In here the first solution is taken, hence some boxes outside the frustum are accepted, in order to keep the cost of testing to a minimum (Assarsson and Moller report that they found no observable penalty in the rendering when skipping further tests).

int FrustumG::boxInFrustum(Box &b) {

	int result = INSIDE, out,in;

	// for each plane do ...
	for(int i=0; i < 6; i++) {

		// reset counters for corners in and out
		out=0;in=0;
		// for each corner of the box do ...
		// get out of the cycle as soon as a box as corners
		// both inside and out of the frustum
		for (int k = 0; k < 8 && (in==0 || out==0); k++) {

			// is the corner outside or inside
			if (pl[i].distance(b.getVertex(k)) < 0)
				out++;
			else
				in++;
		}
		//if all corners are out
		if (!in)
			return (OUTSIDE);
		// if some corners are out and others are in
		else if (out)
			result = INTERSECT;
	}
	return(result);
 }

This function is clearly more complex since for each plane, the eight corners of the box may have to be tested. Note that two new variables in and out are declared. These variables track, for each plane the number of corners that fall on each side of the plane. If all points are on the wrong side of the plane then in is going to be zero and the Box can be immediately rejected. If the corners fall on both sides of the plane, then the box is potentially intersecting the frustum. A box will be inside the frustum if for all planes, it is not on the wrong side of the planes, and it is not intersecting any plane.

Testing the points against a plane stops as soon as there are points on both sides of the plane (notice the stop condition on the for cycle), meaning that the box is intersecting the plane.