Hi, im looking into the AABB vs Triangle test found at :
http://www.acm.org/tog/GraphicsGems/gemsv/ch7-2/
They test the triangles against a "unit cube".
Dose this mean that all triangles has to be transformed into this unit cube's space ?
It seems ineffectiv to me, to "move" all the triangles into the unit cube's space, insted of the other way around ?
And if so, how would I transform a traingle defined by (vec1,vec2,vec3), with an AABB defined by (vecmin, vecmax) ?

**0**

# AABB vs Triangle test ?

Started by Mythar, Feb 17 2007 07:33 AM

9 replies to this topic

Sponsor:

###
#2
Crossbones+ - Reputation: **2025**

Posted 17 February 2007 - 09:47 AM

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]

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]

###
#3
Members - Reputation: **869**

Posted 17 February 2007 - 10:28 AM

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...

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...

###
#4
Members - Reputation: **138**

Posted 17 February 2007 - 11:34 AM

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.

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.

###
#5
Members - Reputation: **869**

Posted 17 February 2007 - 07:53 PM

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:

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.

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.

###
#6
Members - Reputation: **138**

Posted 18 February 2007 - 08:22 AM

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)

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)

function OGLVec3TransformCoord(v : TD3DVECTOR; m : TD3DMATRIX) : TOGLVector;

Var x,y,z,w : single;

Begin

x := V.x*M._00 + V.y*M._10 + V.z*M._20 + M._30;

y := V.x*M._01 + V.y*M._11 + V.z*M._21 + M._31;

z := V.x*M._02 + V.y*M._12 + V.z*M._22 + M._32;

w := V.x*M._03 + V.y*M._13 + V.z*M._23 + M._33;

if w = 0.0 then w := 1.0;

Result[0] := x/w;

Result[1] := y/w;

Result[2] := z/w;

End;

function TriangleIntersectAABB(aabb: TAABB; v1, v2, v3: TD3DVector; TriangleWorldMatrix : TD3DMatrix): boolean;

Var m,

AABBtoCube : TD3DMatrix;

Triangle : array[0..2] of TOGLVector;

normal : TOGLVector;

Begin

AABBtoCube := ZeroMatrix;

AABBtoCube._00 := 1/(AABB.max.x - AABB.min.x);

AABBtoCube._03 := -(AABB.min.x + AABB.max.x) / (2*(AABB.max.x - AABB.min.x));

AABBtoCube._11 := 1/(AABB.max.y - AABB.min.y);

AABBtoCube._13 := -(AABB.min.y + AABB.max.y) / (2*(AABB.max.y - AABB.min.y));

AABBtoCube._22 := 1/(AABB.max.z - AABB.min.z);

AABBtoCube._23 := -(AABB.min.z + AABB.max.z) / (2*(AABB.max.z - AABB.min.z));

AABBtoCube._33 := 1;

m := MatrixMultiply(TriangleWorldMatrix, AABBtoCube);

Triangle[0] := OGLVec3TransformCoord(v1, m);

Triangle[1] := OGLVec3TransformCoord(v2, m);

Triangle[2] := OGLVec3TransformCoord(v3, m);

normal := get_polygon_normal(Triangle);

Result := Boolean(fast_polygon_intersects_cube(Triangle,normal));

End;

###
#7
Members - Reputation: **138**

Posted 19 February 2007 - 07:25 AM

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...

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...

###
#8
Crossbones+ - Reputation: **2025**

Posted 19 February 2007 - 11:02 AM

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.

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

###
#9
Members - Reputation: **869**

Posted 19 February 2007 - 12:14 PM

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.

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.