AABB vs Triangle test ?

not necesseraly. You transform the triangle vertices to convert into the cube space, which is really fast on nowaday's FPUs, and you save some register space and memory accesses by not having to deal with the cube data at all.

Besides, you do not need to transform the whole collision map. Your BVH should reduce the amount of triangles to test.

But that's probably more suited for Oriented bounding boxes. Not sure if there is much gain with AABBs.

[Edited by - oliii on February 17, 2007 4:47:54 PM]

There is a box and there are triangles.

Under certain linear transformations, the box will become a unit cube centered about the origin. Such a transformation is found and it is applied to all of the triangles.

The triangles are not transformed into the box's space, but rather both the box and the triangles are transformed into a space where the box is a unit cube. No matter how this is viewed, it requires the same amount of computation: transforming all of the triangles into this space. There is no need to apply the transformation to the box because the transformation was already designed such that the box's shape in the transformed space would be known.

The transformation needed for your box will be a translation and a stretching/compressing. First a translation puts the box in the correct position relative to the origin. Then a stretching/compressing operation is performed on each axis to make the box unit length along that axis. The transformation is thus defined by the box, but this transformation is then applied to the triangles.

Actually I didn't read the entire algorithm, but I'm wondering why the cube needs to be centered at the origin. Couldn't the dimensions of the cube be used in comparisons instead to get the same effect? But even if that is the case, it would just be an optimization, and there might be some steps I'm not seeing where this wouldn't be an optimization at all...

I did google for OBB vs Triangle but did not find any samples.
So I tryed looking for the AABB vs Triangle.

Im trying to understand how to transform the triangles.

Lets say I have the AABB(min,max-vector) in worldspace, the triangle's vectors are in object space, and the matrix "m" is the transform of the triangles to world space.

Do I need to transform the triangle vectors by "m" be4 applying the "unit cube" transform, or could "m" somehow be a part of the "unit cube" transform ?

Im not that strong in math, so any sample world be great.

Ultimately everything will end up in "cubespace". From the cube's position in worldspace you can calculate the transformation from worldspace to cubespace. Then you transform the triangles from their object space to worldspace to cubespace. The transformations from object space to worldspace and from worldspace to cubespace can be combined to obtain a transformation from the object space to cubespace. With transformation matrices you just multiply the matrices to combine them.

v = vertex in object space
M1 = transformation matrix from object space to worldspace
M2 = transformation matric from worldspace to cubespace

M2 * M1 * v = vertex in cubespace

The multiplications are associative. (M2 * M1) * v = M2 * (M1 * v)

With the box in worldspace defined by (x1,y1,z1) and (x2,y2,z2) the transformation matrix from worldspace to cubespace will look something like this:

1/(x2-x1)   0        0       -(x1+x2)/(2*(x2-x1))   0     1/(y2-y1)   0       -(y1+y2)/(2*(y2-y1))   0        0     1/(z2-z1)  -(z1+z2)/(2*(z2-z1))   0        0        0       1

The 1/(x2-x1) terms are for scaling the sides of the box to be of unit length. The -(x1+x2)/(2*(x2-x1)) terms are displacements to center the box at the origin. If there was no scaling involved, -(x1+x2)/2 would be the displacement to move the box to the origin (it is the center of the box, negated). The way the transformation works, the scaling changes the displacement from the center and so that needs to be factored in, giving the actual terms. Really I made a displacement and a scaling matrix and then multiplied them together in the correct order to get this result.

Thx that helped alot :)

Next problem, I tested it, and it dose not work.

Eighter the code found at (http://www.acm.org/tog/GraphicsGems/gemsv/ch7-2/) dose not work or...

My code of your sample - its pascal so dont run away screaming :)
(AABB must be in world space)

Sample screenshoot.

An object rendered in the actual scene.
The white triangle is the one being tested against.
The white line is the AABB (min to max)

As you can see they do not intersect.



Same scene rendered in unit cube space.
The white box is the unit cube.
The white "line" going through it is the transformed triangle you can see in the above image.

As you can see they do intersect, using your transform, even tho they shoud not.



Not sure what the bug is...

I don;t like debugging someone's code. If you don;t understand the algo they use, then you will have trouble debugging it.

The box / triangle test is actually fairly easy, especially if you do not really concern yourself with optimisations.

Try transposing the matrix, ie instead of _03, _30, etc.

If you're concerned about optimization, your matrix multiplications can just ignore the w component. The w is only there because it allows translations to be represented as part of the transformation matrix. It's only used if the hardware provides vector operations or for the projection step, which is the only place where the division by w takes place.

Thx for all the help Vorpy !

Transposing did the trick, its working now :)