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 - point-triangle collision and triangle-triangle 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 point-Triangle 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...

Triangle-Triangle collision is a bit more complicated, but the maths really doesn't matter a huge amount (again, look it up if you want). For triangle-triangle collision we use a line-plane 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 line-plane 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 pre-lit, 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 un-lit untransformed vertices (for example).
- Triangle-Triangle 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 triangle-triangle 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 whole-lot-of 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 physics-type-stuff...
- 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 (triangle-point detection) or a point in space (triangle-triangle 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...