In the source code from Ian Millington's Game Physics Engine Development, there's a function which plays a crucial role in performing OBB->OBB intersection tests.
I'm having trouble understanding exactly how to interpret this. The operations which are puzzling are found in this function:
static inline real transformToAxis(
const CollisionBox &box,
const Vector3 &axis
)
{
return
box.halfSize.x * real_abs(axis * box.getAxis(0)) +
box.halfSize.y * real_abs(axis * box.getAxis(1)) +
box.halfSize.z * real_abs(axis * box.getAxis(2));
}
The * operator for vectors is overloaded to produce the dot product between two vectors. The engine which is coded uses post multiplication notation for its matrix transformations, which basically means that, given a matrix $M$ and a vector, $\vec{u}$, where,
$$M = \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \\ \end{bmatrix}$$
and,
$$ \vec{u} = \begin{bmatrix} u_x \\ u_y \\ u_z \end{bmatrix} $$
A transformation of $\vec{u}$ by $M$ is,
$$M\vec{u} = \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \\ \end{bmatrix} \begin{bmatrix} u_x \\ u_y \\ u_z \end{bmatrix} = \begin{bmatrix} a\,u_x + b\,u_y + c\,u_z \\ d\,u_x + e\,u_y + f\,u_z \\ g\,u_x + h\,u_y + i\,u_z \end{bmatrix}$$
As we can see, when the transform is performed, each component of the resulting vector involves dot product with $\vec{u}$ by one of the matrix's rows.
With this convention, however, the columns of a matrix are what actually refer to the axes (aka basis vectors) of the coordinate space defined by the linear transformation.
So, for example, the X basis for $M$ is simply,
$$ \begin{bmatrix} a \\ d \\ g \end{bmatrix}$$
Using this understanding, and looking at the operations found in the code, we can see that something similar is happening.
The arbitrary vector, axis, is being dotted against each of the basis vector's of the linear transformation found in the CollisionBox data structure; box.getAxis(i) refers to fetching a basis vector from a box's governing transformation.
Furthermore, we can then see that a second vector is (inadvertently) then dotted with the resulting operation: box.halfSize, which represents merely the sizes of the box as it corresponds to each cardinal axis.
If we let $\vec{u}$ represent the variable axis, have $\vec{h}$ be the vector represented by box.halfSize, and $M$ be the box's linear transformation from which the basis vectors returned by box.getAxis(i) correspond to, we can derive the following mathematical function:
$$T(\vec{u}, \vec{h}, M) = \vec{h} \cdot M^T\vec{u}$$
Since the transpose of $M$ replaces all of $M$'s columns with its rows, we can translate what's going on in the above code to the function just defined.
For someone with just enough linear algebra to get by in game development, and a formal calculus III background, can you give a geometric interpretation of what's going on with this function, here?
Edit
The main purpose behind the code is used for an intersection test between two oriented bounding boxes within a physics engine. Here's some the complete source, for those who are interested:
static inline real transformToAxis(
const CollisionBox &box,
const Vector3 &axis
)
{
return
box.halfSize.x * real_abs(axis * box.getAxis(0)) +
box.halfSize.y * real_abs(axis * box.getAxis(1)) +
box.halfSize.z * real_abs(axis * box.getAxis(2));
}
/**
* This function checks if the two boxes overlap
* along the given axis. The final parameter toCentre
* is used to pass in the vector between the boxes centre
* points, to avoid having to recalculate it each time.
*/
static inline bool overlapOnAxis(
const CollisionBox &one,
const CollisionBox &two,
const Vector3 &axis,
const Vector3 &toCentre
)
{
// Project the half-size of one onto axis
real oneProject = transformToAxis(one, axis);
real twoProject = transformToAxis(two, axis);
// Project this onto the axis
real distance = real_abs(toCentre * axis);
// Check for overlap
return (distance < oneProject + twoProject);
}
// This preprocessor definition is only used as a convenience
// in the boxAndBox intersection method.
#define TEST_OVERLAP(axis) overlapOnAxis(one, two, (axis), toCentre)
bool IntersectionTests::boxAndBox(
const CollisionBox &one,
const CollisionBox &two
)
{
// Find the vector between the two centres
Vector3 toCentre = two.getAxis(3) - one.getAxis(3);
return (
// Check on box one's axes first
TEST_OVERLAP(one.getAxis(0)) &&
TEST_OVERLAP(one.getAxis(1)) &&
TEST_OVERLAP(one.getAxis(2)) &&
// And on two's
TEST_OVERLAP(two.getAxis(0)) &&
TEST_OVERLAP(two.getAxis(1)) &&
TEST_OVERLAP(two.getAxis(2)) &&
// Now on the cross products
TEST_OVERLAP(one.getAxis(0) % two.getAxis(0)) &&
TEST_OVERLAP(one.getAxis(0) % two.getAxis(1)) &&
TEST_OVERLAP(one.getAxis(0) % two.getAxis(2)) &&
TEST_OVERLAP(one.getAxis(1) % two.getAxis(0)) &&
TEST_OVERLAP(one.getAxis(1) % two.getAxis(1)) &&
TEST_OVERLAP(one.getAxis(1) % two.getAxis(2)) &&
TEST_OVERLAP(one.getAxis(2) % two.getAxis(0)) &&
TEST_OVERLAP(one.getAxis(2) % two.getAxis(1)) &&
TEST_OVERLAP(one.getAxis(2) % two.getAxis(2))
);
}
#undef TEST_OVERLAP
The theoretical basis for this code is explained in this tutorial (pp. $17$-$23$). Each of the $15$ applications of
TEST_OVERLAPtests overlap in the projections onto one particular line (the three axes of each box and the nine cross products, i.e. the normals to all planes spanned by two edges).Each box is spanned by the vectors $M_1$, $M_2$ and $M_3$ that make up the matrix $M$ that specifies its orientation in space, and by its centre $c$ (which in this implementation appears to be stored in a fourth component of $M$). The corners of the box are given by $c+\frac12\sum_i\sigma_id_iM_i$, where $d_i$ is the dimension of the box in direction $i$ and $\sigma_i=\pm1$, with the $8$ possible sign combinations yielding the eight corners.
The box's projection onto a line $l$ is centred around the projection of its centre onto $l$. To find how far the box's projection extends away from the centre 's projection, we need to project the corner with the furthest possible projection from the centre. Each $M_i$ has a given projection onto $l$, and to get the extremal projection for a corner, we need to choose the $\sigma_i$ such that every term in the projection is positive – this is why the absolute value is being taken.
Thus, to project the extremal corner, each $M_i$ is projected onto $l$; the absolute values are taken, corresponding to a choice of $\sigma_i$ to make all contributions add up; the projections are multiplied by $\frac12d_i$ to account for the box dimensions, and the contributions are added up. This yields the distance along $l$ from the centre to the extremal corner. This distance is computed for both boxes, and the sum is compared to the distance of the centres along $l$ to test if the projections of the boxes onto $l$ overlap.