A *bounding box* generally refers to an axis-aligned rectangular region of
space used as a first, coarse step of collision detection. Every object is
given a bounding box which covers all space the object could possibly occupy.
If the bounding boxes of two objects overlap, the simulation needs to do a more
precise but expensive collision check; but if they do not overlap, they
certainly do not collide and the pair can be skipped.

Since *Hexeline* uses an oblique coordinate
system, the same approach results in
bounding rhombi instead of boxes, though that distinction is not particularly
interesting here. What is interesting is how bounding boxes/rhombi can be
handled extremely efficiently with SIMD. I fully expect that this technique has
been discovered by someone else previously, but it’s still worth discussing.

One of the central design principles in my still extremely early space shooter
*Hexeline* (read: has neither space nor shooting) is that spacecraft will be
defined in terms of a hexagonal grid, rather than cells of varying shape, which
simplifies things for both the software and the player while still allowing
more interesting shapes than a square grid.

A useful property of regular grids is that they are *directly addressable*;
i.e., you can put the elements of an array and immediately access an element
just by knowing its coordinate. Ideally, it’s also efficient to go from
continuous spatial coordinates to a grid coordinate. This is trivial in a
square grid: depending on how you define your coordinates, you can usually just
divide spatial coordinates by the cell size to get the coordinate of the cell a
point falls within.

In effort to get a similar property for hexagonal grids, I’ve taken the unusual
step of basing a Newtonian physics engine on non-cartesian coordinates. It
turns out this is not as bad as it sounds, and quite a few useful properties
fall out of it.

Note: This post is going to be comparatively math-heavy and assumes some
familiarity with linear algebra.