Some Notes and Possible Optimizations

Spheres as Bounding Volumes for Boxes

As shown throughout this tutorial is easier to do tests with spheres than it is with boxes. Therefore, if a large number of boxes will normally be outside the view frustum, then a bounding sphere should be considered as a possible optimization. Testing a sphere requires only a distance computation against more complex calculations for the box case.

If the sphere is totally outside of the frustum (case A) then the box is also totally outside the box. If the sphere is totally inside the frustum so must be the box (case B). When the sphere intersects the frustum walls two options are available: consider that the box also intersects, which may be false (case C), or test the box itself.

Only in this latter case, sphere intersecting the frustum walls, there is a penalization for using a sphere as a bounding volume for the box. In all the other cases the test is faster. Note that this optimization should be used with care when considering long skinny boxes, since in this case a sphere is not the best bounding volume.

Spheres everywhere

Sphere-sphere test is also very fast: just sum the radius of both spheres and compute the distance between the two centers. If the distance is larger than the sum of the radius then the spheres are separated.

Based on this, one could consider a bounding sphere for the frustum itself. Then a first test would be to check if the object’s bounding sphere is outside the frustum’s bounding sphere, and in this case reject the object immediately.

However this test should be used with care since the sphere that is bounding the view frustum is significantly larger than the frustum itself. Nevertheless if the frustum is small compared to the 3D world then it makes sense to use this as an initial test.

Axis-Aligned Boxes everywhere

Computing an AAB as a bounding volume for an object (or frustum) is extremely easy, just compute the minima and maxima for each axis.

Testing if something is inside of an AAB is also very simple and it doesn’t involve distance computations. Just check if there are overlaps on each axis. Consider an AAB bounding volume, or just AABB, for the frustum, fb and an AABB for an object ob. The following algorithm performs the intersection test:

if (fb_xmin > ob_xmax || fb_xmax < ob_xmin || 	fb_ymin > ob_ymax || fb_ymax < ob_ymin || 	fb_zmin > ob_zmax || fb_zmax < ob_zmin)
	return (OUTSIDE);

else if (fb_xmin < ob_xmin && fb_xmax > ob_xmax &&
		 fb_ymin < ob_ymin && fb_ymax > ob_ymax &&
		 fb_zmin < ob_zmin && fb_zmax > ob_zmax)
	return (INSIDE);
else
	return(INTERSECT);

If the result is OUTSIDE the case is closed. Otherwise, when the result is INTERSECT or INSIDE, then further testing is required.

As for the case when a sphere was proposed as a bounding volume for the view frustum, some care must be taken to check if a bounding box is an appropriate bounding volume for the view frustum. Oblique, long and skinny frusta are not particularly suited.

Floats and precision (or lack of it)

When computing the relative position of objects regarding the frustum in this tutorial comparisons such as ” > 0″ or ” < 0″ were used. Note that due to the limited precision of numbers in computers something that is slightly outside of frustum may be reported as inside, and vice-versa. It will only happen when there is a very close call, but it will happen eventually. Two solutions: never mind because these cases are such a close call that no one cares; be extra conservative and give a tolerance, i.e. consider a slightly larger frustum.

This latter solution, increasing the frustum can be achieved in several ways. For instance the planes themselves can be pushed a little bit further away, inflating the view frustum, by adding a small vector ( a fraction of the plane’s normal) to the points that define the plane. Another solution is to change the way the comparisons are performed, for instance instead of testing ” < 0″ test ” < -0.001″.

Precision increase is possible using doubles instead of floats, but all the math for the tests becomes more expensive.