DirectXGraphics:
3D Collision Detection
Author:
Jack Hoxley
Written: 23rd August 2001
Contact: [EMail]
Download: GR_Coll3D.Zip
(103kb)
Contents
of this lesson
1. Introduction
2. About the algorithm
3. Application of the algorithm
1.
Introduction
welcome
back for another extended graphics tutorial. This
article should hopefully help out a lot of people
 I quite often get asked "How do i stop
my characters walking through walls?", technically
this article doesn't directly address this, but
it will provide you with the required tools with
which to solve the problem.
2.
About the algorithm
The
algorithm used is entirely based upon the article
written by Kevin Kaiser entitled "3D Collision
Detection"  which I found in an excellent
book called "Game Programming Gems"
(Deloura, Mark). Basically, I take no credit for
the actual alogrithm or process here  all I've
done is adapt it into a few more useful functions
and rewrite it in another language (the original
is in C). I've tried not to directly copy his
code, but obviously there are going to be a few
similiarities...
Anyway,
there are two functions presented in the downloadable
code  pointtriangle collision and triangletriangle
collision. Both make use of the standard equation
for a plane  aX+bY+cZ+d=0; the actual maths behind
this isn't too important right now and it's beyond
this article to explain it  search around the
net for further info if you need it. The first
step in all of the functions is to generate a
plane for the source triangle, we then get the
a,b,c and d coefficients for the above plane equation.
Then
in the case of pointTriangle collision we just
run the equation  if aX+bY+cZ+d=0 the point is
touching the triangle, thus we judge it as colliding.
Simple really...
TriangleTriangle
collision is a bit more complicated, but the maths
really doesn't matter a huge amount (again, look
it up if you want). For triangletriangle collision
we use a lineplane intersection test, basically
we check the 3 lines that define the 2nd triangle
and see if any of them intersect the plane for
the 1st triangle  if they do then we have a positive
collision. The lineplane intersection test is
based on parametric equations and calculus, thus
the resulting value ('t' in the code) will allow
you to linearly interpolate along the given line
to find the actual coordinate at which the triangle
intersects the other triangle.
3.
Application of the algorithm
okay,
now that I've presented the type of algorithm,
there are a few things that need to be pointed
out  with respect to actually using it in a game
environment...

Data format
The data format used by all the functions
is a standard prelit, untransformed 3D vertex;
the actual algorithm only uses the coordinates
for the triangle so the other data is a little
irrelevent, but you may need to customise it's
function prototypes and definitions should you
want to use unlit untransformed vertices (for
example).
 TriangleTriangle coordinates
The triangles are described in the parameters
for the functions in clockwise order, this is
important. The function must generate a normal
for the triangle, so if it's presented in the
wrong order you'll possibly get an incorrect plane
being generated and thus bogus collisions will
be reported.
 Certain cases where it wont generate a collision.
If the two triangles being tested are on
the same plane already the function will return
no collision as it is impossible for this algorithm
to detect a collision in such a case (you get
divide by 0 errors). Also, as you may have already
realised, a triangletriangle collision cannot
be detected unless the edge of a (secondary) triangle
intersects the plane of the primary triangle.
This can easily be solved by checking primary
against secondary and then secondary against primary,
but that requires a wholelotof extra work to
be done...
 Result
The result of this function is just a boolean
true/false indicating if there was a collision
 no other physics is calculated or applied, should
you want the resulting coordinate you'll need
to extend the function according to what I said
earlier, or apply a second algorithm that works
out physicstypestuff...
 Array version in DLL.
As much for my own practise as for your convenience
I've written a 2nd version of this library in
a C/C++ DLL. Naturally this version of the function
is considerably faster than VB's version. But
due to the overhead of calling a DLL function
I've included an array version of the function
so that you can pass 1000's of triangles to be
tested in one call, which cuts the time (compared
with 1000's of calls) by 10 fold.
 Using the functions for game objects.
Now this is a big one. How do you use this
function in your game world? there is no set answer,
as it depends on how you've structured your world
and it's characters. one option is to test a bounding
box(s) for the chararacter/objects and if that
results in a collision you can then narrow it
down to where abouts on the model  an individual
vertex (trianglepoint detection) or a point in
space (triangletriangle detection). Just bare
in mind that scanning 1000 triangles against 10,000
points each frame is going to kill your frame
rate straight away  so try to reduce the potential
set early on.
You
can download the source code from the top of the
page, or from the downloads
page. enjoy...
any
feedback or improvements can be emailed to me
 I'm always interested...
