Bounding Box

In which you approximate the complex shape of a model with a simple box.

A mesh is an unwieldy pile of vertices. Determining if one pile is colliding with another pile, as is often needed in games, is challenging. Instead, graphics developers compare simpler shapes that approximate the meshes.

One common shape is the axis-aligned bounding box. This box is aligned with the cardinal axes and fits snugly around all mesh's vertices. It is computed in the following manner:

min = positions[0]
max = positions[0]

for each position
  if position.x < min.x
    update min
  else if position.x > max.x
    update max
  ditto for y
  ditto for z

The min and max vectors contain the smallest and largest coordinates encountered on each dimension.

The bounding box may not be a good fit for all meshes. Large chunks of the box might be empty, which leads to false collision detections and angry players. One way to fix a poor fit is to use different shapes, like spheres, cylinders, capsules, or rotated boxes. Another solution is to represent the mesh using multiple, smaller bounding boxes.

Many of the renderers that you've written so far have placed the geometry around the origin and then spun the model about its own center of gravity. A model loaded in from a file may not be positioned about the origin. To center it, you subtract away the centroid. Sometimes you see centroid defined as the average vertex position:

sum = (0, 0, 0)
for each position
  sum += position
centroid = sum / vertexCount

But regions of the model with dense vertices will have undue influence over the centroid. Taking the centroid as the average of the bounding extrema makes it independent of the density:

centroid = (min + max) / 2

This definition of the centroid is also a lot faster to compute if you've already got the bounding box. It runs in constant rather than linear time.

The renderer then translates the model to the origin first, and then applies any further rotations:

centerer = translate by -centroid
set worldFromModel matrix to rotater * centerer

Add a method to your Trimesh class to compute the bounding box and centroid.