So let me start with the basics. I want to determine if a character hits a wall. My thinking was that a bounding box represents the player, and the wall ( a rectangle ) is represented by 2 triangles. Hence, I need to test for an intersection between a bounding box and a triangle. Does anyone have any code that would produce a result for this intersection? Yes, I've seen the 3D intersection table that everyone links. The only example for oriented bounding-box to triangle on that page is to GeometricTools.com. GeometricTools, to my knowledge, does not have an intersection class for oriented bounding-box to triangle. They have box to box, triangle to triangle, even box to plane, but no box to triangle. Or have I missed it somehow? Now, I suppose I COULD split up the box into 12 triangles, and do triangle to triangle tests. But that doesn't seem efficient; my impression is that bounding boxes use the center, axis, and extent of an OBB to determine a radius to the opposing polyhedra. Splitting the OBB into lots of triangles seems wasteful. Does anyone have any good suggestions for how to go about this, the most simple of collisions? Thanks much! Mike

The basic way that everybody does it with the Separating Axis Theorem, which says that "If you project all the points from the triangle onto an axis and call the extents of the projection region A, and then do the same thing with the box verts, call that region B. If A and B don't overlap, then there is no intersection. If they do overlap, you need to test more axes." And the SAT lists 13 particular axes that need to be tested, and if the A and B regions overlap on all 13 axes, there is definitely an intersection.

The 13 particular axes are : the cross product of each triangle edge with each box axis (3 edges * 3 axes = 9 axes). The normal to the triangle. And the 3 normals to the faces of the box (which happen to be the same as its axes). So, 9 + 1 + 3 = 13 axes.

Once you do this and determine there is an intersection, it is more work still to compute the point of intersection and penetration depth. Triangle / Box intersection is probably more expensive than you expected! There are a couple tricks, but it's just minor improvements... the algorithm is still the same.

FReY, are you sure that algorithm is correct?

Especially condition 4: "(u+v<=1,u>=0,v>=0 : triangle intersects obbox, return true." It seems any triangle whose normal points from the triangle centroid at the obb center would satisfy this case, regardless of intersection. And if you imagine a triangle whose normal extending from any triangle vertex points at the OBB center, there are many non-intersecting cases where this would return intersection.

Your algorithm looks very much like sphere-triangle. Maybe that's what you're thinking of? (And maybe I'm wrong, and I've just never seen this method before...)

The solution I propose is based on the frustum cull algorithm
The algorithm can be implemented in different flavours but basically it resolve
the problem of determine the intersection between a polygon and a convex volume.

Build the frustum
First you need to compute the frustum that describes your OOBB; a frustum is simply
a list (or a vector) of planes.
For each face of your box consider 3 points and build the plane. Be carefull
when describe the normal! Each normals should point toward the convex volume or
at least in the same versus (in/out).
So at the end you have 6 planes that describe your box; you can generalize this approach
to every convex volume (AABB, OOBB, view frustum, shadow volume, light spot, convex
objects,...).
There are also other methods to build the box; for example you can apply the transform matrix
to the original AABB. Choose what you prefer.

Cull the triangle against the frustum
The idea is to use each plane to split a triangle (for which you want to
test intersection) into two polygons: a polygon in the volume (you keep) and a
polygon out of the volume (you discard).
If after a plane cull the inner polygon is empty you know that actually there is no
intersection. It comes from the definition!
This test is efficient because it can happen after the first test and in general
after each cull your inner polygon become smaller and smaller. Note that
intersections are 'rare' so probably you will abort the function at the first
test without any insertion (see after).

This algorithm is widely used in BSP building, view frustum cull, pre rendered
lighting, and of course intersection.

I post the variant I use in my simulation so I'm sorry if the code seems strange
(but it works!) [smile]



vector array is a vector of point describing your polygon.
I consider each plane in the frustum and cull the polygon; then I keep the inner
part of the polygon. If varray becomes empty I exit and return false (no intersection).

Why use a vector of points if you have only triangle ?
First you can generalize to other problems without changing the code [smile]
But most important: because each cull can generate a polygon with n>3 vertices
(think for example about a 2D triangle and cull it with a line in the
middle...you split the triangle into a smaller triangle and a quadrilateral!)
In general each cull adds an edge.

The test return false if varray, after a test (possibly the last) is empty; if
varray is empty the triangle is extern.
The array is casted to false via an operator (I like this kind of overloadings...)

Cull a polygon against a plane

The source I post is a modified version I use; in general one could add the
possibility to interpolate also texture, color, normal components of the polygon.
In this case I am interested only in the intersection; but the mod is straightforward
when you know the interpoation coefficient on the edge!
The algorithm is also stabilized to reduce numeric errors when choose the
first point (the tutorials dont say...).



Another hint (probably a must) can be select a set of potentially intersecant
triangles; this can be performed via BSP, hash maps ( octree , voxel matrix,...)
For example some games (see Quake2) use BSP to select potentially interesecant
triangles (and also PVS); when you know that a triangle can intersect your OOBB
go for the precise test. If the final clipped polygon is not empty you know
there is an intersection but you have also the part of the triangles that is contained in the convex volume!

I hope this simple tutorial will help you and who are asking about view frustum culling and similar problems.