Collision Detection Technique for 3D
By Joshua Cantrell
last updated: 9-24-99
Even with the event of graphics acceleration cards, I don't know of any
helper cards for collision detection. (I assume that is the next step.)
For this reason, it makes sense that I must design my own routines to
detect and handle collisions of freeform objects moving in a dynamic
world. I certainly don't want object bouncing around at great distances
from each other, or just as bad, flying right through each other without
IDEAS BEHIND THE METHOD
After much thought on the issue, I decided to go back to basic 2D and 3D math
relationships. This has to do with points, lines, vectors, and planes. The
reason why I decided to start simple was that sometimes I find it easier
to build complex algorithms from simpler identities and algorithms. If
you can be assured of successful implementation of simple algorithms and
build upward with success at each step, then the finished product
is sure to work! :-)
For simple 2D properties and collision detection, I suggest you look at
my Collision Detection Technique for 2D
description first. It's simpler than dealing with 3D, and my 3D ideas
are simply steps up from it. (3D can describe 2D, so that they are
related makes complete sense.)
Before my explanation on collision detection, I'll cover three 3D
properties. I'm first going to cover a point within a convex solid,
followed by intersecting a line with a solid, and last instersecting
a plane with a solid.
FUNDAMENTAL MATH CONCEPTS USED
Without the understanding of certain math concepts, it may hard to
understand everything that goes into collision detection. This is one
reason why I think good programmers should feel comfortable with math.
(It's only an opinion, so don't jump on me if you hate math.)
The dot product and cross product are covered in my
2D explanation, Collision Detection Technique
for 2D. Adding another dimension to collision detection produces
many more possibilities not encountered in the 2D case. For this
reason even more math is required.
3D Line Intersections
To find out if two lines collide in 3D space is non-trivial. Any
number of numerical rounding errors could cause two lines which would
have intersected appear not to intersect. Such problems can be avoided
by assuming that lines never really intersect, they simply become
convincingly close to each other. The intersection can then be found
by finding the closest points on the lines and the distance between
that given point. If the distance is within a certain region, they
are considered to be touching.
The values we require can be found by realizing a few features of
lines in 3D space. The shortest distance between two lines (with directions
unique to eachother) is a straight line. The shortest distance between
a point and a line is a straight line which lies orthogonal to the line.
This means a line must lie orthognal to both lines (dot product is zero).
This should only happen at one location given that the lines aren't parallel,
so we can write our equation to find the two points P1 and P2.
Let L1 and L2 = Non-parallel lines in 3D space.
Let V1 = Vector representing the direction of L1.
Let V2 = Vector representing the direction of L2.
Let P1 = Point on L1 closest to L2.
Let P2 = Point on L2 closest to L1.
Let W = Vector formed by subtracting P1 from P2.
W = (P1x-P2x, P1y-P2y, P1z-P2z)
1) P1 and P2 form a line perpindicular to both lines L1 and L2.
W.V1 = 0
W.V2 = 0
2) Length of the line formed by P1 and P2 is the shortest distance
between L1 and L2.
3) Points on a line follow: P = s*(Vx, Vy, Vz)+D
(P1x-P2x)*V1x + (P1y-P2y)*V1y + (P1z-P2z)*V1z = 0
(P1x-P2x)*V2x + (P1y-P2y)*V2y + (P1z-P2z)*V2z = 0
V1.(s1*V1 - s2*V2 + D1 - D2) = 0
V2.(s1*V1 - s2*V2 + D1 - D2) = 0
We know V1, D1, V2, and D2. Solve the system of equations for s1 and s2
to get P1 and P2.
POINT IN A 3D CONVEX SOLID
For each side of the 3D Convex Polygon, you must determine if the point,
P, is on the inside or outside of a side. This is done using both the
cross product and dot product. First a vector normal
to the surface and pointing outward, N, must be found using the
cross product. A point on the surface is then chosen, Q, and a vector,
V, from Q to P is found. The sign of the dot
product of N and V tells us whether the point
is inside or outside. If the sign is positive, it is outside, otherwise
it is negative and inside.
LINE SEGMENT INTERSECTING A 3D CONVEX SOLID
For each side of the convex solid, three things must be done. First
the place where the line interesects with the side's plane must be found
(assuming the line doesn't lie on the plane). This point must then be
checked to lie on the line segment. Last of all this point must lie
within the edges of the side.
Line Intersecting a Plane
The equation of plane can be found on my page "
A Texture Mapping Technique". Using the equation of a line and
substitution, we can find the point of intersection.
Let S = A plane.
Let N = A vector normal to S.
Let V = A point on S.
Let L = Line not on S1.
Let P = Point of intersection.
Equation of a plane: N.(x, y, z) = N.V
(Nx*x) + (Ny*y) + (Nz*z) = (Nx*Vx + Ny*Vy + Nz*Vz)
Equation of a line: (x, y, z) = s*M + B = s*(Mx, My, Mz) + (Bx, By, Bz)
N.(s*M + B) = N.V
We know N, M, B, and V. Solve for s to get P.
FINITE SURFACE INTERSECTING A 3D CONVEX SOLID
For each side of the convex solid, three things must be done. First
the line, L, formed by the non-parallel intersecting planes must be found.
Now find the points where the line intersects the edges of the side and
the surface. If either doesn't have intersecting points, there is no
intersection, otherwise the line segments found must be compared to
find out if they overlap. If they don't overlap, then there is no
3D CONVEX SOLID COLLISION DETECTION (1st Way)
Collision detection of 3D convex solids is very similar to
2D convex polygons. The main difference is that
instead of being interested in intersecting lines, we are now interested
in intersecting sides (faces) of the solids. Like 2D convex polygons,
there are two ways of approaching how to detect collisions, either move
the object and check whether they overlap, or if the moving solid
intersects the other solid. I discuss the latter.
Given the two objects and their displacement vector, all sides pointing
away from the direction of displacement are culled away. The endpoints
from the culled sides then become points of new sides formed by moving
all of the remaining points by the displacement vector.
The last step is simply to check and see if any of the sides intersect.
If any of them do, a collision was detected. If none intersect, there is
still one possibility which is that the object's region of displacement
enveloped the other object, so simply test to see if one of the other
object's points is in the region of displacement. If one is there,
they must all be in the region of displacement, and a collision occurred.
3D CONVEX SOLID COLLISION DETECTION (2nd Way)
Not unlike the 2D collision detection, there is yet another way of
detecting a collision which allows you to also find out where the first
occured. The idea is the same except for everything is scaled up one
dimension. Instead of points, you use edges. Instead of lines, you use
First the surfaces that could not be involved in a collision are culled
away by using the dot product of the displacement vector and the surface
normals. The remaining edges of the moving solid are then projected forward
in the direction of displacement to create surfaces. These are then checked
against the static solid to see if a collision occured. If no collision is
detected, the remaining edges of the static solid are projected in the
opposite direction of the displacement to create surfaces. These are then
checked against the moving solid to see if a collision occured. A collision
occurs if the projected edges intersect any of the other solid's remaining
Given all possible locations of collision, with some effort, they can be
traced back to the places where the collision actually occured. Using this
information a distance can be obtained for each point of collision, and
the shorted distance belongs to the initial collision.
3D CONVEX POLYGON COLLISION REGION FINDING
Once a collision has been found, if you wish to find out where it occurred,
the second collision detection technique should be used. This not only
tells you that the collision occured, but, with reasonable effort, where it
(My Home Page)
- (My Computer Science Page)
- (My Personal Page)
- (My Resume)