Sign in to follow this  
jujumbura

oriented boundingbox to triangle intersection?

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Here's another method that makes use of edge-obbox and point-obbox tests.
I don't have code to give you for it, but if you know about barycentric coordinates and obbox-point and obbox-edge tests this will be useful to you.

Imagine your triangle is made of points 0,1,2 in counter-clockwise order. The order doesn't really matter but I've specified it just for visualization purposes.

Project the obbox's centre point into the triangle's barycentric space and obtain barycentric coordinates (u,v). u will be the coordinate along the edge 0-2 and v will be the coordinate along the edge 0-1.

The barycentric coordinate will now be in one of 7 regions. Based on which region the (u,v) is, test it against sub-components of the triangle as follows:

(u<0,v<0) : test obbox against point 0.
(u<0,v>=0,v<=1) : test obbox against edge 0-1
(u<0,v>1) : test obbox against point 1
(u+v<=1,u>=0,v>=0 : triangle intersects obbox, return true.
(u>=0,v<0,u+v<=1) : test obbox against edge 0-2
(v<0,u>0,u+v>1) : test obbox against point 2
(u>0=,v>=0,u+v>1) : test obbox against edge 1-2

This allows you to decompose your triangle-obbox test into a single edge-obbox test or point-obbox test.

Hope that helped :)

Share this post


Link to post
Share on other sites
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...)

Share this post


Link to post
Share on other sites
ajas, you are of course completely correct, and thanks for correcting me. The algorithm as I described it has exactly the flaws that you just pointed out.
I must have been thinking of the sphere-triangle intersection. And condition 4 would have to be changed to:
(u+v<=1,u>=0,v>=0 : test sphere against triangle plane

Silly me :)

Ignore my last post Michael! :)

Share this post


Link to post
Share on other sites
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]


bool Culling::
FrustumCulling(const AC::_3D::Frustum& frustum,
AC::_3D::VectorArray& varray){
for(AC::_3D::Frustum::const_iterator plane = frustum.begin();
plane!=frustum.end() && varray; plane++)
PlaneCulling(*plane,varray);
return varray;
}





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


bool Culling::
PlaneCulling(const AC::_3D::Plane& plane,
AC::_3D::VectorArray& varray){
static AC::_3D::VectorArray _front(8); // front split (static makes it faster)
static AC::_3D::VectorArray _back(8); // back split (8 is probably >> max)

SIZET nvertices = varray.size();
if(!nvertices) return false;

AC::_3D::VectorArray* pva1 = &_front; // insertion ptr 1
AC::_3D::VectorArray* pva2 = &_back; // insertion ptr 2
AC::_3D::VectorArray* pvtmp = NULL;
_front.clear();
_back.clear();

// STABILIZZAZIONE BSP
SIZET istart = 0;
REAL dist, absd, maxdist;
REAL epsilon = AC::REAL_SMALL; // tollerance (example 10e-8 or something ~0)
bool bback = false;
maxdist = 0;
for(SIZET i=0; i<nvertices; i++){
dist = plane.n * varray[i] + plane.D; // distance
absd = dist>0?dist:-dist; // abs di dist
if(absd > epsilon){ // well classified
bback = dist<0?true:false;
istart = i;
break;
}
else{ // the best found...
if(absd>maxdist){
maxdist = absd;
istart = i;
bback = dist<0?true:false;
}
}
} // find other vertex
//////////////////////////////// end stab

// if the first vertex is back we start to fill the back polygon
if(bback){
pvtmp = pva1; pva1 = pva2; pva2 = pvtmp; // swap
}

SIZET j,k;
// for each edge in the polygon...(with rotation)
for(i=0,j=istart,k=istart+1; i<nvertices; i++,j++,k++){
if(j==nvertices) j=0; // rot
if(k==nvertices) k=0; // rot
Vector A = varray[j];
Vector B = varray[k];

// A and B are in different halfspaces ?
REAL Da = (plane.n*A)+plane.D;
REAL Db = (plane.n*B)+plane.D;
if((Da>0)^(Db>0)){
// C is the interpolated point between A and B splitted by the plane
Vector AB = B-A;
Vector C = A - AB * (Da/(plane.n*AB)); // 'optimized' version
pva1->push_back(C);
pva2->push_back(C);
pvtmp = pva1; pva1 = pva2; pva2 = pvtmp; // swap
}
pva1->push_back(B); // always
}
// copy front -> varray and exit
return varray = _front;
}





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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this