Collision Detection Technique for 3D

Convex Solid

By Joshua Cantrell

last updated: 9-24-99

INTRODUCTION

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 flinching!

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)

Given:
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

Solution:
(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)

Solution:
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 intersection.

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 collision 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 finite surfaces.
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 surfaces.
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 occured.

joshuacantrell@yahoo.com
(My Home Page) - (My Computer Science Page) - (My Personal Page) - (My Resume)