## Hierarchical View Frustum Culling

Individually checking every polygon for containment within the view frustum is very inefficient. We can be more efficient by introducing a hierarchy into our checks. Instead of checking each polygon, we can first perform a coarse check at the object level. If an entire object is found to be outside of the view frustum, then all of its polygons must also lie outside of the frustum, so we don't need to waste time checking every polygon in the object. If the object is entirely inside the view frustum, then all of its polygons are also inside. If the object is partially inside and partially outside the view frustum, then we must check each polygon individually.

¿VSQ NOTE With hardware acceleration, it might be faster to consider partially contained ^^ bounding volumes as being fully contained, and simply send all of their geometry to the hardware to be drawn. As we said at the beginning of this chapter, this may be inefficient, but hardware acceleration can often make the actual time penalty of such inefficiency virtually disappear.

Extending the hierarchy even further, we can collect objects into larger groups, and check each group first. If the entire group is inside or outside, then so are all of the constituent objects; if it is partially inside and partially outside, each constituent object must be checked separately. Checking the objects then proceeds as outlined above. The hierarchy can be extended to an arbitrary number of levels, starting with very large groups of objects, proceeding to medium-sized groups of objects, proceeding down to objects, proceeding down to individual polygons. Figure 4-8: Hierarchical view frustum culling. First, check the hierarchically higher groups of polygons (A, B, and C), before investing time checking the individual polygons (1, 2, 3, 4, 5, 6, etc.). Here, A is completely outside, so all of its six polygons can be immediately skipped without traversing that branch of the hierarchy further. B is completely inside, so all of its polygons can be immediately passed on for further processing. C is partially inside and partially outside, so all of its individual polygons must be examined separately, thus requiring a further traversal of this branch of the hierarchy.

Figure 4-8: Hierarchical view frustum culling. First, check the hierarchically higher groups of polygons (A, B, and C), before investing time checking the individual polygons (1, 2, 3, 4, 5, 6, etc.). Here, A is completely outside, so all of its six polygons can be immediately skipped without traversing that branch of the hierarchy further. B is completely inside, so all of its polygons can be immediately passed on for further processing. C is partially inside and partially outside, so all of its individual polygons must be examined separately, thus requiring a further traversal of this branch of the hierarchy. Figure 4-9: Multi-level hierarchy in view frustum culling. Here, group A is found to be partially inside the view frustum, so processing continues with all groups within A, namely, C, D, and E. Group C is partially inside, so processing continues with all polygons in group C. Group D is completely outside, so all of its polygons are immediately discarded. Group E is completely inside, so all of its polygons are immediately passed on for further processing. Group B, again at the top level of the hierarchy, is completely outside the frustum, meaning that everything within group B can be instantly discarded.

Figure 4-9: Multi-level hierarchy in view frustum culling. Here, group A is found to be partially inside the view frustum, so processing continues with all groups within A, namely, C, D, and E. Group C is partially inside, so processing continues with all polygons in group C. Group D is completely outside, so all of its polygons are immediately discarded. Group E is completely inside, so all of its polygons are immediately passed on for further processing. Group B, again at the top level of the hierarchy, is completely outside the frustum, meaning that everything within group B can be instantly discarded.

Chapter 4: Visible Surface Determination I: General Techniques 225

The key condition for such a hierarchical scheme to work is an efficient way of checking for view frustum containment of a group of polygons or objects. This group check must be faster than checking each individual polygon or object individually; otherwise, the whole scheme wastes time rather than saving it. The way that we can make group checks faster than individual checks is through the concept of a bounding volume. A bounding volume is a mathematically simple object, such as a sphere or a cube, that is large enough to contain all polygons of the object it bounds. Spheres are particularly simple and convenient for use as bounding volumes. Let's look more closely at how we can use spheres to save time in view frustum culling.

### Bounding Spheres and the View Frustum

A 3D sphere can be defined in terms of a center and a radius. Let us assume that we have a sphere that is large enough to contain a polygonal model. (We look at computing such spheres later; it's quite easy.) We call such a sphere a bounding sphere. Checking for frustum containment of such a sphere is extremely fast and easy. It relies on the fact that evaluating a plane equation with a particular point (x,y,z) gives the shortest (i.e., perpendicular) distance between the plane and the point. Recall that the side_of_point function does exactlythis: it evaluates the plane equation fora given point, and returns a positive, negative, or zero value if the point is in front of, behind, or on the plane, respectively. The function can be understood in terms of vector projections; the result of the side_of_point function is essentially the difference in the length of the projection onto the plane's normal vector of the vector from the origin to the point in question. In other words, the result of l3d_plane::side_of_point is the shortest distance from the point to the plane. If the point is on the plane, the distance from the point to the plane is zero. If the point is in front of the plane, it is a positive displacement from the plane; if it is behind the plane, it is a negative displacement from the plane.

CAUTION The plane's normal vector (the terms A, B, and C in the plane equation) must be normalized (have a length of 1) for the above computation to work. Plane vectors computed through the method l3d_plane::align_with_points satisfy this property, since this method creates a normalized vector. If you create your own planes by explicitly specifying plane equation coefficients, remember that the plane normal must be normalized. If it is not normalized, you can still use the plane equation to compute the distance between a point and the plane. To do this, first normalize the vector (divide it by its length). Then, evaluate the plane equation using the point for the x, y, and z values, using the normalized A, B, and C components of the normalized vector, and using the original D component of the plane equation. Generally, it's easiest to store normalized vectors from the beginning, so we don't have to re-normalize them later to do distance computations.

The trick that makes sphere checking easy is that the very definition of a sphere is based upon distance. A sphere is defined to be the set of all points in 3D space that are a certain distance, termed the radius, from a given center point. This means that the following are true: ■ If the distance between a sphere's center and a plane is positive, negative, or zero, the center of the sphere is in front of, behind, or exactly on the plane, respectively.

If the absolute value of the distance between a sphere's center and a plane is greater than the sphere's radius, the sphere is completely on one side of the plane; the sign of the distance determines which side it is on (inside or outside).

If the absolute value of the distance between a sphere's center and a plane is less than the sphere's radius, the sphere is partially inside and partially outside the plane; in other words, the sphere intersects the plane.

If the absolute value of the distance between a sphere's center and a plane is exactly equal to the sphere's radius, then the sphere grazes the plane. Figure 4-10: Checking for intersection between a bounding sphere and a plane. Given a plane with normalized normal vector (A,B,C), and a sphere with radius r and center at (cx,cy,cz), this diagram shows how to classify the position of the sphere with respect to the plane. We evaluate the plane equation with the center point of the sphere, and compare the result to r. The value of r tells us the position of the sphere with respect to the plane. From top to bottom, the sphere is completely outside of, grazing the outside of, mostly on the outside of, split exactly in half by, mostly inside of, grazing the inside of, or completely inside of the plane.

These facts mean that to check for containment of a bounding sphere in the view frustum, we evaluate the plane equation for each of the frustum's planes by using the center of the sphere as the (x,y,z) point in the plane equation. The result can be analyzed using the above facts to tell us if the sphere is completely outside, completely inside, or partially inside and partially outside of one individual frustum plane. If the sphere is completely outside of any one frustum plane, it and all of its bounded geometry are completely outside of the entire frustum, and can be eliminated from further processing. If the sphere is completely inside all frustum planes, then it and all of its bounded geometry are completely inside the entire frustum, and should be passed on for further processing. In any other case, the sphere and its bounded geometry are partially inside and partially outside of the entire frustum, and view frustum culling must continue at the next more detailed level of the hierarchy for each polygon or object within the bounding sphere.

Note that this computation can be performed in either world space or camera space; we simply need the sphere's center point and the planes in the appropriate coordinate system.

■ - ; TIP The classification of a bounding sphere with respect to a plane can also be interpreted ' as the detection of whether the sphere collides with the plane. See Chapter 8 for more on the topic of collision detection.

Also, notice that we can save time by first transforming only an object's bounding sphere from object space into world space to be tested against the world space frustum. If the sphere turns out to be outside of the frustum, we have saved the work of transforming all of the object's vertices. If the sphere turns out to be inside or partially inside the frustum, only then do we expend computational effort transforming the entire object geometry into world space.

Computing Bounding Spheres

We can compute a bounding sphere for a polygonal object by computing two values: a center and a radius.

Compute the center of the object by finding the maximum and minimum x, y, and z values among all vertices. Then, for eachx, y, and z, add the maximum and minimum value and divide by two to arrive at the average middle position along the x, y, and z axes. This yields a single (x,y,z) location representing the center of the object. Then, with the center point, calculate the distance of each vertex from the center, using the 3D distance formula. Keep track of the maximum distance found. Then, define the radius of the sphere to be the maximum distance found. In this way, all vertices, and thus all polygons, are guaranteed to lie within the sphere, because they all have a distance smaller than the maximum distance from the sphere's center. Figure 4-11: Computing a bounding sphere.

Note that regardless of how the object is rotated, the bounding sphere remains the same.

CAUTION If the object contains vertices that are not referenced by any polygon, then be sure not to use such vertices when computing the center and radius.

It is possible for an object to contain unused vertices—that is, vertices which are not referenced by any polygon. It is important not to use such vertices when computing the center or radius of the polygon, since such vertices do not contribute to the geometry of the object. The world editing scheme covered in Chapter 6 intentionally adds "unused" vertices to the polygonal mesh (vertices not referenced by any polygon) to encode non-geometric information within the mesh. This non-geometric information is a unique integer object identifier, which we can then use to associate arbitrary information with every polygonal mesh: a name, the name of a texture file to be associated with the mesh, and so forth. We should be careful that such non-geometrical vertices do not contribute to the bounding sphere computation.

Class l3d_bounding_sphere

Class l3d_bounding_sphere is the l3d class representing abounding sphere.

Member variables radius and center store the radius and center of the bounding sphere. The center is stored as l3d_coordinate, so it has an original and a transformed location. The method compute_around_object computes the bounding sphere around a given object by computing the center and finding the maximum required radius among all of the object's vertices which are used by at least one polygon. Method distance_to_plane computes the distance between the center of the sphere and a plane, simply by calling the plane's side_of_point method with the center point; it is merely another interface to the same functionality.

The member variable transform_stage, along with methods transform and reset, are responsible for transforming the bounding sphere and tracking how many times the sphere has already been transformed, just as is the case with the vertices of objects. Since a bounding sphere is sort of a simplified version of an object, we also provide for similar means of transforming the bounding sphere.

Transforming a bounding sphere is as simple as transforming its center point; no transformation we use for the code in this book can change the shape or orientation of a sphere (only a non-uniform scaling or a shearing transformation could squash or tug the sphere into an asymmetric ellipsoid with an identifiable orientation). We track the number of times the sphere has been transformed because the bounding sphere should, eventually, be transformed the same number of times (and with the same matrices) as the geometry it bounds. We say "eventually" because in the case of a culling operation, the whole idea is to save time by first transforming only the bounding sphere, then later transforming the geometry if needed. However, for other operations (such as collision detection), we transform the geometry, then use the bounding sphere later, expecting that the bounding sphere has also been transformed along with the geometry. In such a case, the bounding sphere is transformed after the geometry, not before. We use the transform_stage variable to synchronize the transformations of the bounding sphere with those of its underlying geometry.

We saw earlier how to check for containment of a bounding sphere within the view frustum; we check the distance between the sphere's center with every plane in the frustum. If the sphere is on the inside side of every plane, it is in the frustum; otherwise, it is outside. The method l3d_view_frustum::intersects_sphere, which we saw earlier, performs exactly this test, using the bounding sphere's distance_to_plane method. The inter-sects_sphere method considers any sphere that is even partially within the frustum to be inside; the distance tests check the distance against the negative radius of the sphere. If the signed distance between the sphere's center and the plane is greater than the negative radius, this means that at least some part of the sphere is on the inside side of the plane. This implies that the view frustum test with bounding spheres, as implemented here, is a conservative test. It may conservatively flag an object as being "inside" the frustum, even if only a tiny part of the bounding sphere is inside the frustum. Since a bounding sphere cannot perfectly fit its underlying geometry (unless the underlying geometry is also a sphere), the actual geometry might be completely outside the frustum even if our test says it might be inside. But no geometry inside the frustum is ever rejected with our test. This is a general characteristic of conservative tests: they overestimate the work that might need to be done, but never underestimate it.

Listing 4-8: boundsph.h

#ifndef _BOUNDSPH_H

#define _BOUNDSPH_H

#include "../../system/sys_dep.h" #include "../plane/plane.h" #include "../../math/matn'x.h" #include "../vertex/coord.h" class l3d_object;

class l3d_bounding_sphere { public: int transform_stage; virtual void reset(void);

virtual void transform(const l3d_matrix &xform);

l3d_real distance_to_plane(const l3d_plane & plane) const; void compute_around_object(const l3d_object *object);

#endif

Listing 4-9: boundsph.cc

#include "boundsph.h"

#include "../plane/plane.h"

#include "../object/object3d.h"

void l3d_bounding_sphere::reset(void) { transform_stage = 0; center.reset();

void l3d_bounding_sphere::transform(const l3d_matrix &xform) { transform_stage++;

center.transform(xform, transform_stage);

l3d_real l3d_bounding_sphere::distance_to_plane(const l3d_plane & plane) const {

//- ensure the size of the plane's normal vector is 1, otherwise this //- computation doesn't work return plane.side_of_point(center.transformed);

void l3d_bounding_sphere::compute_around_object(const l3d_object *object) { int i;

center.original.set(0,0,0,1);

l3d_point min, max; int first_vtx=1;

for(i=0; i<object->vertices->num_fixed_items; i++) { int vtx_is_referenced=0;

for(int pi=0; pi<object->polygons.num_items && !vtx_is_referenced;pi++) { for(int vi=0; vi<object->polygons[pi]->ivertices->num_items; vi++) { if((*object->polygons[pi]->ivertices)[vi].ivertex == i) { vtx_is_referenced = 1; break;

if(vtx_is_referenced) { if(first_vtx) { first_vtx = 0;

min.X_ = (*object->vertices)[i].original.X_; max.X_ = (*object->vertices)[i].original.X_; min.Y_ = (*object->vertices)[i].original.Y_; max.Y_ = (*object->vertices)[i].original.Y_; min.Z_ = (*object->vertices)[i].original.Z_; max.Z_ = (*object->vertices)[i].original.Z_; }else {

if ( (*object->vertices)[i].original.X_ < min.X_) { min.X_ = (*object->vertices)[i].original.X_;

if ( (*object->vertices)[i].original.X_ > max.X_) { max.X_ = (*object->vertices)[i].original.X_;

if ( (*object->vertices)[i].original.Y_ < min.Y_) { min.Y_ = (*object->vertices)[i].original.Y_;

if ( (*object->vertices)[i].original.Y_ > max.Y_) { max.Y_ = (*object->vertices)[i].original.Y_;

if ( (*object->vertices)[i].original.Z_ < min.Z_) { min.Z_ = (*object->vertices)[i].original.Z_;

if ( (*object->vertices)[i].original.Z_ > max.Z_) { max.Z_ = (*object->vertices)[i].original.Z_;

center.original.X_ = l3d_divri(min.X_ + max.X_, 2);

center.original.Y_ =

l3d_divri(min.Y_ + max.Y_, 2); center.original.Z_ = l3d_divri(min.Z_ + max.Z_, 2);

for(i=0; i<object->vertices->num_fixed_items; i++) { int vtx_is_referenced=0;

for(int pi=0; pi<object->polygons.num_items && !vtx_is_referenced;pi++) { for(int vi=0; vi<object->polygons[pi]->ivertices->num_items; vi++) { if((*object->polygons[pi]->ivertices)[vi].ivertex == i) { vtx_is_referenced = 1; break;

if(vtx_is_referenced) { l3d_real dist_squared;

dist_squared = dot((*object->vertices)[i].original - center.original, (*object->vertices)[i].original - center.original);

//- the value computed in the above loop was the max squared distance, //- now take the square root to retrieve the actual distance radius = l3d_sqrt(radius);

reset(); //- copy original into transformed

Other Bounding Volumes

Other bounding volumes are also used in 3D graphics for the purposes of faster testing and early rejection. Two common ones are the arbitrarily oriented bounding box (OBB) and the axially aligned bounding box (AABB).

An arbitrarily oriented bounding box is a cube-like box, with pairwise parallel sides which fully encompass the geometry it bounds. Like a cube, it can be defined with eight points. In general, a bounding box is stored along with the geometry it bounds, and is transformed the same way. For instance, if we rotate an object, we rotate its bounding box as well. This means that a bounding box can be arbitrarily oriented in space. On the one hand, this makes bounding boxes good bounding volumes, because they can tightly "fit" the underlying geometry (i.e., the bounding volume contains relatively little empty space around the bounded geometry), but on the other hand, the arbitrary orientation of the bounding box means that we have six arbitrarily oriented faces and eight arbitrarily located points. For instance, computing if two arbitrarily aligned bounding boxes intersect is not trivial; any one point of one box might pierce any face of the other box. For the purposes of view volume culling, we can check all corner points of the bounding box against all planes of the view frustum, then use the same logic we used for spheres for determining containment in the view frustum. One special case which must be handled is a huge bounding box larger than the frustum itself; all eight corners lie outside the frustum, but part of the box does lie within the frustum. Figure 4-12: An arbitrarily oriented bounding box is transformed along with its geometry, making for a tight fit but possibly more complicated computations.

An axially aligned bounding box is the same as a bounding box, with the exception that all of its sides are always parallel to one of the x-y, y-z, or x-z planes. In other words, the normal vectors of the sides of the AABB must lie along one of the principal coordinate axes, hence the term "axially aligned." In contrast to an arbitrarily oriented bounding box, an axially aligned bounding box is not transformed along with its underlying geometry due to the alignment restriction on the sides. This means that as an object rotates, its AABB might need to be recomputed. Since the sides of an AABB are all conveniently aligned, we only need to store two opposite corner points of the AABB, not all eight corner points. AABBs generally provide a fairly poor fit to the underlying geometry, but certain operations on AABBs are very easy. For instance, intersection of two AABBs can be determined by three consecutive one-dimensional overlap tests; if the x, y, and z intervals defining the sides of the two AABBs overlap, then the AABBs themselves overlap; otherwise they are disjoint. For the purposes of view volume culling, AABBs can be handled like OBBs; we test the corner points of the AABB against the view frustum to see if the entire AABB is inside or outside of the view frustum.

 / \/

Figure 4-13: An axis-aligned bounding box has sides whose normal vectors lie along the principal coordinate axes. It provides a poor fit to geometry, but simplifies some computations.

Figure 4-13: An axis-aligned bounding box has sides whose normal vectors lie along the principal coordinate axes. It provides a poor fit to geometry, but simplifies some computations.