On-Line Computer Graphics Notes
BOUNDING BOXES

Overview

In implementing computer graphics algorithms, we frequently need a low-cost method to ``keep track of'' an object without having to continually reference the object's mathematical complex definition. In many cases, a bounding box can be placed about the object and the algorithms can refer to the box when necessary, rather than the object.

For a pdf version of these notes look here.

What is a Bounding Box?

A bounding box for an object is just a rectangular box in three-dimensional space, with sides parallel to the coordinate planes, that contains (or surrounds) the object. This illustration below shows a two-dimensional box surrounding a curved object.

How Do We Construct Bounding Boxes?

If we are given an object represented by a set of points

$${\bf P} _0 = ( x_0, y_0, z_0 ),$$

$${\bf P} _1 = ( x_1, y_1, z_1 ),$$

$$\vdots$$

$${\bf P} _n = ( x_n, y_n, z_n )$$

(e.g. the vertices of a polygon, or the control points of a Bézier Patch), we can build a bounding box about the object simply by defining the box to be

$$\min_{0\leq i \leq n} \left\{x_i \right\} \leq x \leq \max_{0\leq i \leq n} \left\{x_i \right\}$$

$$\min_{0\leq i \leq n} \left\{y_i \right\} \leq y \leq \max_{0\leq i \leq n} \left\{y_i \right\}$$

$$\min_{0\leq i \leq n} \left\{z_i \right\} \leq z \leq \max_{0\leq i \leq n} \left\{z_i \right\}$$

Of course, many other boxes may be defined which contain the object, but this is a minimal box that has sides parallel to the coordinate axes.

In Relation to the Convex Hull ...

If we consider the above points ${\bf P} _0, {\bf P} _1, ..., {\bf P} _n$, the bounding box is a convex set containing the points. Since we know that the convex hull is the smallest convex set that contains all the points, it must also be contained in the bounding box. That is, a bounding box contains the convex hull.

A Simple Intersection Test

If we have two complex models ${\cal M} _1$ and ${\cal M} _2$ and we wish to see if these models do not intersect, we can use a ``bounding-box test'' to give a quick initial answer. If ${\cal B} _1$ and ${\cal B} _2$ are bounding boxes containing ${\cal M} _1$ and ${\cal M} _2$ respectively, it is easily seen that ${\cal M} _1$ and ${\cal M} _2$ cannot intersect if the two bounding boxes do not intersect.

This test can only be used to see if the objects do not intersect, it cannot be used to test for intersection. If the bounding boxes do intersect, we can only say that it is possible that the objects intersect. We cannot say it with certainty.

A Ray/Object Intersection Test

Suppose we have a complex models ${\cal M}$ and we wish to see if a ray intersects ${\cal M}$. This is normally a complex operation, and we can simplify it somewhat by using a simple ``bounding-box test'' to see if the ray misses ${\cal M}$.

By placing a bounding box ${\cal B}$ around ${\cal M}$, we first see if the ray hits ${\cal B}$, and if not, we know that the ray does not hit the model ${\cal M}$. Of course, if the ray hits the bounding box, we then must test it against ${\cal M}$ for intersection which may be expensive. But by testing first against the bounding box, we can eliminate a number of complex expensive calculations.

Return to the Graphics Notes Home Page
Return to the Geometric Modeling Notes Home Page
Return to the UC Davis Visualization and Graphics Group Home Page

This document maintained by Ken Joy

Mail us your comments

All contents copyright (c) 1996, 1997, 1998, 1999
Computer Science Department
University of California, Davis

All rights reserved.