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.