Transform Axis Aligned Bounding Boxes

Axis aligned bounding boxes are quite often used in computer graphics, for example for fast collision detection. Often, you need to transform a given axis aligned bounding box by some matrix and then convert it into an axis aligned bounding box in the resulting coordinate space again. Here’s an efficient algorithm to do so:

public static BoundingBox transformBoundingBox(BoundingBox boundingBox, Matrix m)
{
    var xa = m.Right * boundingBox.Min.X;
    var xb = m.Right * boundingBox.Max.X;

    var ya = m.Up * boundingBox.Min.Y;
    var yb = m.Up * boundingBox.Max.Y;

    var za = m.Backward * boundingBox.Min.Z;
    var zb = m.Backward * boundingBox.Max.Z;

    return new BoundingBox(
        Vector3.Min(xa, xb) + Vector3.Min(ya, yb) + Vector3.Min(za, zb) + m.Translation,
        Vector3.Max(xa, xb) + Vector3.Max(ya, yb) + Vector3.Max(za, zb) + m.Translation
    );

Note that Matrix.Right returns the Matrix’s first column vector, i.e. (M_{11} M_{21} M_{31} M_{41})^T and Matrix.Up and Matrix.Backward return the second and third column vectors respectively. So looking at the source code above, all you have to do is multiply the bounding box min and max values in each coordinate direction by the corresponding Matrix column vector and then combine them to generate the result. Why does this work?

Let’s think about the definition of an axis aligned bounding box: It can be described by a center position \mathbf{c} = (c_x c_y c_z)^T and offsets for each coordinate axis \mathbf{r} = (r_x r_y r_z)^T. We can then write the box’s delimiting positions as follows:

\mathbf{B} = \left[ \mathbf{\min} \begin{pmatrix} c_x \pm r_x \\ c_y \pm r_y \\ c_z \pm r_z \end{pmatrix}, \mathbf{\max} \begin{pmatrix} c_x \pm r_x \\ c_y \pm r_y \\ c_z \pm r_z \end{pmatrix} \right] = \left[ \mathbf{c} - \mathbf{r}, \mathbf{c} + \mathbf{r} \right]

Note the \mathbf{\min} and \mathbf{\max} operators are applied for each dimension independently. Since each dimension’s offset \mathbf{r} is added and subtracted independently from the other dimensions as well the \mathbf{\min}, \mathbf{\max} operators go over 2*2*2 = 2^3 = 8 corner positions. So, lets transform the positions by some matrix \mathbf{M} and then convert the resulting corners into an axis aligned bounding box \mathbf{B}' again by finding the minimum and maximum values in each coordinate direction:

\mathbf{B}' = \left[\mathbf{\min} \bigg(\mathbf{M}\begin{pmatrix} c_x \pm r_x \\ c_y \pm r_y \\ c_z \pm r_z \\ 1 \end{pmatrix} \bigg), \mathbf{\max} \bigg( \mathbf{M}\begin{pmatrix} c_x \pm r_x \\ c_y \pm r_y \\ c_z \pm r_z \\ 1 \end{pmatrix} \bigg) \right]

In my previous post Rant: Matrix Layouts I pointed out that we can split up matrix vector products into a sum over the product of the vector’s components with individual matrix columns. Let’s try this here, just for the \mathbf{\min} vector \mathbf{B}'_{min} of \mathbf{B}' first:

\mathbf{\min} \bigg(\mathbf{M}\begin{pmatrix} c_x \pm r_x \\ c_y \pm r_y \\ c_z \pm r_z \\ 1 \end{pmatrix}\bigg) = \mathbf{\min} \bigg( \mathbf{M}_{|1}(c_x \pm r_x) + \mathbf{M}_{|2}(c_y \pm r_y) + \mathbf{M}_{|3}(c_z \pm r_z) + \mathbf{M}_{|4}\bigg)

Note how something magic happened here: each component of \mathbf{c} and \mathbf{r} appears only once in the resulting equation and we only have two possible values for each component! Now we just need to split up the \mathbf{\min} operator:

\mathbf{B}_{min} = \mathbf{\min} \bigg( \mathbf{M}_{|1}(c_x \pm r_x) \bigg) + \mathbf{\min} \bigg(\mathbf{M}_{|2}(c_y \pm r_y)\bigg) + \mathbf{\min} \bigg(\mathbf{M}_{|3}(c_z \pm r_z)\bigg) + \mathbf{M}_{|4}

and we are done: We successfully decomposed the minimum over all eight bounding box coordinates into a component-wise minimum and a sum over all dimensions. Obviously, the same procedure holds for the maximum bounding box extent as well. Have another look at the code above again: It performs the very computation mentioned just before.

Links

3 thoughts on “Transform Axis Aligned Bounding Boxes

  1. Nice, but if you say: min ( M ( c \in R^4 ) ) this means min considers the w component which is invalid. I was a little confused by this.

Leave a Reply

Your email address will not be published. Required fields are marked *