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