Geometric Approach – Testing Boxes II

Box testing can be optimized, up to a certain extent, by testing only two of its vertices, namely the “positive vertex” and the “negative vertex” (aka the maximum vertex and the minimum vertex).

Testing a single vertex is enough for the cases where the box is outside, and the second vertex needs only to be tested if one requires distinguishing between boxes totally inside and boxes partially inside the view frustum.

So what are these vertices? And how hard is it to find them?

Consider a plane and its normal. The positive vertex is the vertex from the box that is further along the normal’s direction. The negative vertex is the opposite vertex.

If the p-vertex is on the wrong side of the plane, the box can be immediately rejected, as it falls completely outside the frustum. On the other hand, if the p-vertex is on the right side of the plane, then testing the whereabouts of the n-vertex tells if the box is totally on the right side of the plane, or if the box intersects the plane.

As to how hard it is to find them lets consider two cases: Axis Aligned Boxes (AAB), and Oriented Boxes (OB). In the first case, AAB, it is very easy and computationally inexpensive to find them.

Assume a AAB that has its components x,y,and z varying between xmin and xmax; ymin and ymax; and zmin and zmax. The components of the positive vertex p are selected as follows:

	p = (xmin,ymin,zmin)
	if (normal.x >= 0)
		p.x = xmax;
	if (normal.y >=0))
		p.y = ymax;
	if (normal.z >= 0)
		p.z = zmax:

The negative vertex n follows the opposite rule:

	n = (xmax,ymax,zmax)
	if (normal.x >= 0)
		n.x = xmin;
	if (normal.y >=0))
		n.y = ymin;
	if (normal.z >= 0)
		n.z = zmin:

If the box is not axis aligned, i.e. an OB, then it is more expensive to find these two special vertices. An approach presented by Moller and Haines is to transform the normal into the box’s space. So consider the box’s three axis, bx, by and bz. To transform the normal into the box’s space just perform the projections of the normal onto these axes:

	nb = (bx . n, by . n, bz . n)

This new normal in the box’s space, nb, is used to determine the p-vertex and n-vertex. For an OB, the test implies three dot products, plus the testing itself that requires one or two distance computations. Still for boxes outside the frustum it should be faster than testing the eight vertices of the box.

Given both p-vertex and n-vertex, the code to find the position of an axis aligned box in a frustum is as follows:

int FrustumG::boxInFrustum(AABox &b) {

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

		// is the positive vertex outside?
		if (pl[i].distance(b.getVertexP(pl[i].normal)) < 0)
			return OUTSIDE;
		// is the negative vertex outside?
		else if (pl[i].distance(b.getVertexN(pl[i].normal)) < 0)
			result =  INTERSECT;
	}
	return(result);
}