## 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

Let's start with a demo:

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.

Visually, we start with an axially-aligned square: 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.