4 replies to this topic

[rouncer]

I need to test if a triangle is inside an AABB.
I found one, and it uses 13 separating axis tests to
find out if the triangle is inside the box.
I dont know really what the separating axis test is...
When I was highschool, cutting class to code my Mario
Brothers conversion seemed more important than learning algebra.
(how wrong I was...)

But I need a bit of extra functionality, I need to know
what sides of the cube the triangle intersected with, so
I can continue on box intersecting with it to form a voxel
version of a triangle.

Would be any slower to do 6 triangle axis aligned plane
intersections?

[.oisyn]

triangle-plane tests won't get you far because you'll need to test against an actual face of the box, not the whole plane that face is on.

triangle-quad intersection test can be done with a separating axis test as well (as it works with any two convex polytopes). A separating axis test is a test where you test objects A and B as follows:

for each face fA in A
    test with fA.normal;

for each face fB in B
    test with fB.normal;

for each edge eA in A
    for each edge eB in B
        test with cross(eA.direction, eB.direction)

Where each 'test' consists of an 1D overlapping test - project both objects on the normal, giving you a min-max range for each object, and test whether these ranges overlap (if not, this normal is the 'seperating axis' and the objects don't intersect eachother)

Of course, parallel and oposite vectors only have to be tested once. Since a triangle has 1 unique plane and 3 unique edges, and a box has 3 unique planes and 3 unique edges, that leaves you with 1+3+(3*3) = 13 tests. A quad has 1 unique plane and 2 unique edges, so you'll end up with only 1+1+(3*2) = 8 axis tests.

[rouncer]

And its quicker for axis aligned stuff.. right?

[.oisyn]

basically, yes

[karligula]

Don't you wish there were simpler ways to do these sorts of things? I had a look at geometric algebra which is supposed to be a far more elegant way of doing intersection tests with objects of varying dimensionality... I sort of got the gist of it but it's such an odd way of doing things after all my years with good old vector maths that I didn't follow up on it much.

Geomerics has a realtime radiosity demo on their website which uses geometric algebra. It's quite cool, although to me it looks heavily pre calculated... hope that's not libellous!

You might like to have a look at geometric algebra though... it's the way of the future... supposedly...