I have a sphere and a object bounding box. I wish to transform the sphere to the OBB object space to peform a collision test. I know that to get the transformation matrix to object-space, i need the local axis of the OBB Transformation Matrix(MyMatrix) to Object Space: [OBB x-axis] [OBB y-axis] [OBB z-axis] Is this matrix correct? What I wish to know is that this matrix that i construct, before i apply to the sphere, do i have to apply the world transformation for the sphere too? Can I go: Sphere > MyMatrix > becomes in OBB Object space. Or must i do: Sphere > SphereWorldMatrix > MyMatrix > becomes in OBB Object space. Sorry if this question appear stupid. I am just trying to learn my linear algebra. Thanks a million

The testing can be done as soon as all data involved are given in the same co-ordinate frame. This can be the global frame, one local frame of the collision volumes, or any other.

A co-ordinate frame is both an orientation as well as a position, both given w.r.t. the parental frame. (So your "MyMatrix" is insufficient, since it shows an orientation but no position, if I understand it correctly.)

Assuming a local frame L, then any geometry given in that frame is transformed to the parental frame by applying the matrix L to the geometry. When using column vectors, that looks like
p' := L * p
Going the opposite way, namely transforming geometry from the parental frame into the local frame, is the inverse operation
L-1 * p' = p

Lets assume furthur that the local frames of the both collision objects are L1 and L2, and that the next more global spaces of both is common, then 1st transforming geometry from L1 into the common frame
p' = L1 * p
and furthur transforming the result into L2
p" = L2-1 * p'
can be summarized to
p" = L2-1 * L1 * p'

So, extracting the transformation matrix from this, one gets
M = L2-1 * L1


I hope that has clarified the issue somewhat.


EDIT: Please bear in mind that collision volumes are often "simple" geometry, e.g. a sphere centered around the origin of the local frame. Hence often M can be optimized.

thanks haegarr. I understands the concept of the local frames.

I do understand the derivation of: M = L2-1 * L1

However, why is it that M is also just simply the equivalent of the L2 local axes? From ur derivation it isn't so is it?

Plus any insight on what you mean by optimize M for simple geometry?

should I use:

[x1, x2, x3]
[y1, y2, y3]
[z1, z2, z3]
where local x-axis = (x1,y1,z1), y-axis = (x2, y2, z2)

or

[OBB x-axis]
[OBB y-axis]
[OBB z-axis]

The main problem I am having is trying to build a matrix to get the sphere to the Object Bounding Box, object space to perform collision detection

[Edited by - littlekid on November 24, 2007 12:08:59 AM]

Quote:Original post by littlekid
However, why is it that M is also just simply the equivalent of the L2 local axes? From ur derivation it isn't so is it?

Plus any insight on what you mean by optimize M for simple geometry?

As already stated in my previous post, any matrix you want to use has to consist of both an orientation and a position. It can be understood as a concatenation (still using column vectors)
L := T * R
where T denotes the position (as a translation from the origin) and R denotes the orientation (as a rotation from the standard orientation).

My derivation of M computes a matrix to transform geometry from the frame L1 to the frame L2.
M := L2-1 * L1
= R2-1 * T2-1 * T1 * R1
Now assuming that the geometry is a perfect sphere with its center at the local (0,0,0)
c := [0,0,0,1]t
and a radius r, as would be typical for a sphere as a collision volume. Transforming the sphere's center then means to compute
c" := R2-1 * T2-1 * T1 * R1 * [0,0,0,1]t

But since [0,0,0,1]t is the identity value for a rotation (i.e. it is the only one value in the entire space that isn't altered by applying the rotation), and since T1 denotes the origin of the frame, the above formula is principally the same as
c" := R2-1 * T2-1 * [tx,ty,tz,1]t
Moreover, since the space doesn't scale (we've defined it w/o any scaling matrix part), the radius is left as is and hence need not explicitely be transformed. So, for the given simple geometry, computing M can be done optimized as
M = L2-1


Obviously, my M is not "just simply the equivalent of the L2 local axes". That has up to 3 reasons: First, as written above, M must provide also a position! Second, the axes that are given by you as an equivalent of the orientation of the local frame define the local axes w.r.t. the parental frame, and hence are part of the local-to-parent transformation! But your intention of M is to do a parent-to-local transformation (when looking at L2 only), so you have to invert. Third, generally you have to consider the first local frame L1, too.

Quote:Original post by littlekid
should I use:

[x1, x2, x3]
[y1, y2, y3]
[z1, z2, z3]
where local x-axis = (x1,y1,z1), y-axis = (x2, y2, z2)

or

[OBB x-axis]
[OBB y-axis]
[OBB z-axis]

When looking at this, I see 2 things perhaps buried in the question (but perhaps I misunderstand your question): The one is whether to use column or row vectors, and the other is whether you should use local frame axes or else OBB axes. Whether to use column or row vectors is a matter of taste. I personally prefer column vectors, and so chosen it for the math I've written down here. The axes (and position) you should use for the transformation are defintely those of the local co-ordinate frame! The box (or which volume ever) is just a geometry given w.r.t. that frame. E.g., if you use an AABB (i.e. an axes-aligned BB) then the geometry has some simplification potential, similar to the center of the sphere coincident w/ the frame's origin in the example above. The difference of a general OBB w.r.t. an AABB is just that its orientation is explicitely allowed to differ from the local axes orientations.

Quote:Original post by littlekid
The main problem I am having is trying to build a matrix to get the sphere to the Object Bounding Box, object space to perform collision detection

Well, with the stuff above, I've already shown that
M = L2-1
can be used to simply transform the origin of the bounding sphere into the local frame of the OBB (assuming that L2 denotes the frame of the OBB, of course), and that r can be used as is. You can, if you wish, use the OBB's local definition to make the problem a sphere-AABB collision detection, if you apply an additional parent-to-local transformation, yielding in
LB-1 * M
where LB denotes the local frame of the OBB w.r.t. L2.


In summary:
(1) Build L2 as shown at the top of this post from the orientation and position of the frame the OBB is defined in.
(2) Compute its inverse L2-1 and use the resutl as M.
(2a) If you want to do an AABB test instead of OBB, perform (1) and (2) also for the local frame of the OBB, multiplying the result from the left with the previous M, and use the result as new M.
(3) Apply the transformation M to the sphere's origin and take the sphere's radius over.
(4) Do the actual collision test.


Whop, I must try to make less words. However, I hope it helps you to understand the mechaniscs behind the problem :)

ahh.. let me try and rephrase what you just say, and check if I understood your post.

A sphere has a transformation from its own object space to world space denoted my M1
A Box has a transformation from its own object space to world space denoted my M2

Hence to get the sphere in to the object space of the Box to peform a Sphere-AABB collision test I would

Sphere.orgin * M1 * Inverse(M2); --- eqn(1)

Would that be it?

A side question if the M2 matrix includes a non uniform scaling, how should i scale the radius of the sphere. If i just plug the values into eqn(1), which i hope i got it right, wouldn't the sphere become a espilloide after the transformation to the Box object space?

Quote:Original post by littlekid
A sphere has a transformation from its own object space to world space denoted my M1
A Box has a transformation from its own object space to world space denoted my M2

I've named it L (for "local") so far, but okay, its just a convention how to name the things.

Quote:Original post by littlekid
Hence to get the sphere in to the object space of the Box to peform a Sphere-AABB collision test I would

Sphere.orgin * M1 * Inverse(M2); --- eqn(1)

This equation is true but if and only if you're using row vectors. (In my explanations so far I've used column vectors, therefore I've written those equation in "transposed order" compared to your writing.)

Quote:Original post by littlekid
A side question if the M2 matrix includes a non uniform scaling, how should i scale the radius of the sphere. If i just plug the values into eqn(1), which i hope i got it right, wouldn't the sphere become a espilloide after the transformation to the Box object space?

Yes, indeed. If your frame shows also scaling, then its simplest form is typically like (I stick with my conventions here to be consistent with previous posts)
L2 := T2 * R2 * S2
where S2 denotes said scaling. Then
M := L2-1 = S2-1 * R2-1 * T2-1
obviously still contains the scaling. Notice please that the scaling not only affects the radius but the position of the sphere as well.

You can compute it then e.g. by
(a) transforming its position as usual c" := M * c, and
(b) creating an artificial direction vector (r,r,r) from the sphere's radius r in L1, and computing
r" := M * [r,r,r,0]t
to yield in a vector (rx,ry,rz) describing the axes aligned radii of the ellipsoid in L2.

Thanks, I think I now better understand the maths behind it.

However I did would like to know from the last eqn:

r" := M * [r,r,r,0]t

hence getting the radii of the ellipsoid. However, by making it to a ellipsoid, wouldn't it defeat the purpose of going all the trouble for the collision test?

As I was thinking along the line to change from Sphere-OOBB test to Sphere-AABB test to simplfiy the algorithm. By changin the sphere to a ellipsoid, isn't it harder to perform the collision test?

my method of testing a sphere against a AABB is just:

Quote:Original post by littlekid
However I did would like to know from the last eqn:

r" := M * [r,r,r,0]t

hence getting the radii of the ellipsoid. However, by making it to a ellipsoid, wouldn't it defeat the purpose of going all the trouble for the collision test?

It is a range of grays from the simplest sphere-sphere collision test to the complex triangle-triangle test. Of course, testing an ellipsoid against an AABB is more complex than testing a sphere against an AABB, but on the other hand it may produce less 2nd order tests. Its all a matter of costs vs. benefits, sadly dependend on the geometry inside the bounding volume.

However, 1st, if the local frame does non-uniform scaling then you have to deal with it. Most likely it doesn't, and you were lucky then. 2nd, you can have situations where optimized handling is possible, namely:

(a) If the frame of the AABB is the scaling one (as you've requested if I remember correctly), then you have 3 radii, one for each principal axis direction, instead of 1 for all of them. That is perhaps (dependind on what you're doing) nothing that really harms: Instead of

if (x < r) ...if (y < r) ...if (z < r) ...

you'll use something like

if (x < rx) ...if (y < ry) ...if (z < rz) ...

(b) You can operate also in a variant of the frame where the ellipsoid is still a sphere. That means nothing else than to inversely scale the AABB instead of forward scale the sphere. Then you still perform a sphere-AABB test. I.e. store and use the box's extend w/o the scaling.


Looking at your code snippet I would suggest some things if I'm allowed to do:

(1) I don't know whether your compiler knows an intrinsic to replace a pow(...,2) by a multiplication. I would use a*a instead of pow(a,2).

(2) pow(SphereRadius, 2) is constant at runtime as long as the sphere isn't altered. You may consider to store and use the squared radius instead of computing it again and again.

(3) Mainly a matter of readibility: The ternary operator
return (Distance > pow(SphereRadius, 2)) ? E_FAIL : S_OK;
or even better, a real boolean result
return Distance > pow(SphereRadius, 2); or return Distance <= pow(SphereRadius, 2);
is IMHO easier to read (less program code) any presumbly produces less assembler code.

I am using the visual studio compiler.

I don't quite really understand your 2nd method where you inversely scale the AABB so to retain the Sphere property as well as the Axis Aligniness of the box.

I was also thinking another method which I do not know if it is viable:

Say to make a Object Bounding Box Axis Align, all I need to do is multiply it my a rotational matrix, M. (Just a rotation, no scale/shear/translation).

Hence by multipling the sphere by the same rotational matrix, I can get a sphere-AABB test done.

I am not sure if this is workable? Just sudden;y popped in my head after thinking of this for a long time.

Quote:Original post by littlekid
I don't quite really understand your 2nd method where you inversely scale the AABB so to retain the Sphere property as well as the Axis Aligniness of the box.

Well, look at the math. Our recent transformation, namely that inclusive scaling, was
MS := L2-1 = S2-1 * R2-1 * T2-1
to transform the sphere (above indicated by the index S) from L1 to L2. Because it become senseful in the next step, we'll also define a transformation for the box. Since the box is already given in L2, so its transformation is of course the identify matrix:
MB := I

Now we want to undo the scaling of the sphere, making the S2-1 unhappen inside MS:
S2 * MS = S2 * S2-1 * R2-1 * T2-1 = R2-1 * T2-1
Since we need to test both volumes in the same frame, we need to perform the same transformation on the box:
S2 * MB = S2 * I = S2

Notice please that the scaling as is applied by S is always along the principal axes (other scalings are possible, too, but require surrounding rotations and translations; look e.g. at the "Transform" node of VRML/X3D). That means, that an axes aligned box will remain an axes aligned box; the axes alignment property is invariant against scaling.

In other words, if we scale the box but don't scale the sphere, we're still able to test against the sphere. (I've written "inverse scaling" in my above post since S2 is applied to the box what is the inverse of S2-1 that was formerly applied to the sphere.) All we've done is choosing another, more appropriate co-ordinate frame.

Quote:Original post by littlekid
Say to make a Object Bounding Box Axis Align, all I need to do is multiply it my a rotational matrix, M. (Just a rotation, no scale/shear/translation).

Yes, the operation to make a OBB axis aligned is a rotation, so far you're right. BUT: The resulting AA box will in general not contain the entirety of the orignal OBB, and hence it would perhaps not be a proper AABB. In general an AABB is greater than an equivalent OBB, and it is at least of the same size (namely if the OBB is already axes aligned). That is in fact the reason why OBBs are used besides AABBs at all.

To compute an AABB from an OBB, one can look at the 8 corners of the OBB and compute the 6 minimums and maximums of their x,y,z co-ordinates. These values are then the boundary values of the equivalent AABB. Of course, the resulting AABB may be too great, but that cannot be verified when only looking at the original OBB. If you want to have the smallest AABB, you have to investigate the wrapped geometry itself.

EDIT: To clarify, please read also my next post!

EDIT2: Bug corrected.

[Edited by - haegarr on November 28, 2007 1:10:07 AM]