## Automatic tracking of bounding boxes

In Ao's kernel, shapes are represented as lambda functions that take in (x y z) coordinates and return a single distance value.

Each shape may be associated with a bounding box, represented as the values
((xmin ymin zmin) (xmax ymax zmax))

How can we track these bounds as shapes are moved, rotated, and otherwise deformed?

### Example

Ao> (define c (circle '(0 0) 1))
Ao> (get-bounds c)
$1 = (( -1.0 -1.0 -inf.0) ( 1.0 1.0 +inf.0)) Ao> (define m (move c '(1 2))) Ao> (get-bounds m)$2 = ((  0.0  1.0 -inf.0) ( 2.0 3.0 +inf.0))


get-bounds is a function that returns the shape's bounds in the form
((xmin ymin zmin) (xmax ymax zmax)).

In this example, we defined a circle with radius 1 and printed its bounding box, then moved it and confirmed that the bounding box moved in the right direction.

This isn't yet impressive: we could have hard-coded bounding box translation into the move function.

Of course, it's not that obvious. To prove it, let's construct a transform on the fly:

Ao> (define rect (rectangle '(0 0) '(1 1)))
Ao> (get-bounds rect)
$1 = (( 0.0 0.0 -inf.0) ( 1.0 1.0 +inf.0)) Ao> (define rotated ... (let ((angle (/ pi 2))) ... (apply-transform rect (x y z) ... (+ (* x (cos angle)) (* y (sin angle))) ... (- (* y (cos angle)) (* x (sin angle))) ... z))) Ao> (get-bounds rotated)$2 = (( -0.7071068286895752 0.0 -inf.0)
(  0.7071068286895752 1.4142136573791504 +inf.0))


In this example, we construct a rotation matrix that rotates the input shape by 45º, then apply it to the rectangle with the apply-transform function. After rotation, the bounds grow by $\sqrt 2$ along each axis
(shown by the dotted lines): This is more interesting: the transform was defined in-line, so it can't be explained with a hard-coded solution. This introduces our fundamental question:

How can we automatically track bounds when applying arbitrary transforms?

In the rest of this write-up, we'll spiral towards a partial solution to this question.

### Transform functions

In the example above, we saw code of the following form:

(apply-transform rect (x y z)
(+ (* x (cos angle)) (* y (sin angle)))
(- (* y (cos angle)) (* x (sin angle)))
z)))


In general, our shapes are a function $f(x, y, z) \rightarrow \mathbb{R}$.

A transform is a remapping of those coordinates, i.e. $$T\left(x, y, z\right) \rightarrow \left(x', y', z'\right)$$

To use our specific example, the code above is applying the transform $$T\left(x, y, z\right) \rightarrow \left(\begin{array}{c} x \times \cos(a) + y \times \sin(a), \\ x \times \sin(a) - y \times \cos(a), \\ z \end{array} \right)$$

### Transforms and bounds

If we have a transform $T$ and an original bounding box $B$, the new bounding box is found with the inverse transform, i.e. $T^{-1}(B)$

This is counterintuitive, so let's look at a few examples.

To move a shape by the offset $(+ 1, + 2)$, we apply the transform and inverse $$T\left(x, y, z\right) \rightarrow \left(\begin{array}{c} x - 1,\\ y - 2, \\ z \end{array} \right) \qquad T^{-1}\left(x, y, z\right) \rightarrow \left(\begin{array}{c} x + 1,\\ y + 2, \\ z \end{array} \right)$$

To scale a shape, making it twice as large on all axes, we use $$T\left(x, y, z\right) \rightarrow \left(\begin{array}{c} x/2,\\ y/2, \\ z/2 \end{array} \right) \qquad T^{-1}\left(x, y, z\right) \rightarrow \left(\begin{array}{c} x\times 2,\\ y\times 2, \\ z\times 2 \end{array} \right)$$

In both cases, it's the forward transform that seems counterintuitive; the inverse transform closely matches the text description of what happens to the shape.

Once you wrap your head around this, it seems pretty easy: just apply $T^{-1}$ to the corners of your original bounding box to get your transformed bounding box.

It's not quite that simple. Let's think about our rotation example from earlier: $$T\left(x, y, z\right) \rightarrow \left(\begin{array}{c} x \times \cos(a) + y \times \sin(a), \\ x \times \sin(a) - y \times \cos(a), \\ z \end{array} \right)$$ $$T^{-1}\left(x, y, z\right) \rightarrow \left(\begin{array}{c} x \times \cos(-a) + y \times \sin(-a), \\ x \times \sin(-a) - y \times \cos(-a), \\ z \end{array} \right)$$

When you apply this to the corners of your bounding box, you get a diamond, since the original box is rotated by 45º. Our bounding boxes should be axially-aligned, so this won't work.

Instead, $T^{-1}$ should be evaluated against the interval of the bounding box. Using interval arithmetic guarantees that the result fully encloses the new bounds.

### Finding the inverse

We're closing in on our goal here, having realized:

• Transforms are functions of the form $T(x, y, z) \rightarrow (x', y', z')$
• The transformed bounds are $T^{-1}$ applied to the original bounds

The last step is to find the inverse transform. Unfortunately, there's no general-purpose solution (and indeed, it's trivial to construct transforms with no closed-form inverse)

Still, there's obviously something that works for many cases.
Did you spot what all of the examples have in common?

That's right: they are all affine transforms.

In particular, they all can be representing with a matrix $M$ such that $$\left( \begin{array}{c} x'\\ y'\\ z'\\ \_ \end{array}\right) = M \left( \begin{array}{c} x\\ y\\ z\\ 1 \end{array}\right)$$

Now, the path forward becomes clear:

• Find the matrix $M$ that represents a particular transform
• Invert it, producing $M^{-1}$
• Multiply $M^{-1}$ against the original bounds

This is the solution implemented in Ao. The apply-transform macro checks to see if the transform is affine; if so, it automatically sets the resulting bounds.

In practice, this works quite well. Of the operations in transforms.scm, all but two are affine. The two outliers are tapering operators.