Cliff Jolly (cjolly@ucsc.edu)
CMPS161 Winter 2008
Final Project

Problem

Determine whether or not two convex polyhedrons, each defined by a series of planes, are intersecting.

This forms the basis of more complicated collision detection, including that of concave objects. This is done by breaking the complicated concave object into smaller convex objects so that we can use the unique properties of the convex polyhedrons for our calculations.

Converting concave objects and polyhedrons to convex polyhedrons is beyond the scope of this project, however, and it will focus primarily on collision detection in the simpler case.

Building the Program

Requirements:

• SDL development libraries must be installed. (http://www.libsdl.org)
• OpenGL development libraries must be installed.
• A MinGW or Unix-like environment (Linux, Mac OSX, etc) is required to build using the supplied Makefile.

To compile on a Unix-like environment, run "make" in the project directory. Assuming that all the required elements are in place, the program should build and output a binary simply named "a" or "a.exe".

This Makefile was tested on Ubuntu 7.10.

Running the Program

Start the program by executing the "a" binary.

Controls:

• Left, Right - Rotate the camera around the y axis.
• W, A, S, D - Move one of the polyhedrons.
• Escape or closing the window - Quit the program.

You may move one of the polyhedrons around using the W, A, S, and D keys on the keyboard. The left and right arrow keys rotate the camera around.

What you should see, when the program is running correctly, is two wireframe polyhedrons. The area where they overlap will be shown as a solid polyhedron. There is also a bounding box around the area strictly for visual reference and a colored axis indicator.

Program Structure

Program classes:

• Vector3D (vector.h, vector.cpp) - 3D vector class with overloaded operators for vector operations.
• Matrix4x4 (matrix.h, matrix.cpp) - Matrix math class, geared towards 3D transformations.
• Line (line.h, line.cpp) - A line segment or ray in 3D space.
• Plane (plane.h, plane.cpp) - A plane, defined by a normal and distance from origin. Also includes several functions for manipulation.
• Polygon (polyhedron.h, polyhedron.cpp) - A plane and a series of points on the plane used for drawing.
• Polyhedron (polyhedron.h, polyhedron.cpp) - A convex polyhedron. Most of the meat of the program is here.

Building a Polyhedron

A polyhedron in the context of the program is little more than a collection of planes, each of which excludes the area in front of it from being in the shape. It is as if, when constructing these by hand, the constructor is sculputing it by shaving off slices of material using an infinitely large chisel. The polyhedron starts by taking up infinite space and by appropriately removing chunks using these planes, it is reduced to a finite volume.

A simple case would be to build a box by adding six planes for the top, bottom, and sides of the box. Adding more planes would cut away more from that.

Note that using this technique it is impossible to get a concave object.

How It Knows What to Draw - Computing Polygons

Lists of points are computed by taking each plane and finding the points where it intersects every combination of two other planes. Then, from that list of points, every point that is on the outside side of any plane in the polyhedron is removed. This will leave a list of points that, when put in the proper order, represent the points of a polygon.

To get them into order, we use a cross product test against all the points for each point to determine consistent, clockwise order.

The result of these operations will be a list of points that can be fed directly into OpenGL in the triangle fan drawing mode to draw the polygon for the given plane.

Collision Detection

Line / Polygon:

To do a collision test for a line/polygon intersection we first test to see if the line even intersects a plane and, if it does, get the point in 3D space where that happens. Another test is then done to see if the collision point is within the bounds of the line segment. Finally, we check to see if the collision point is within the polygon by checking, using the cross product, that it is on the inside side of all the edges of the polygon.

Polyhedron / Point:

Computing which side of a plane a point is on is trivial. So for each plane in the polyhedron, check to see if the point is on the inner side of the plane. If it is true for all the planes, then the point is inside the polyhedron.

Polyhedron / Polyhedron

First test to see if any point from any polygon on either polyhedron is inside of the other polyhedron. If even one is found to be inside the other polyhedron, then there is a collision.

Then test to see if any line that makes up an edge on either polygon on one polyhedron collides with any polygon on the other polyhedron. If one is found to do this, then there is a collision.

If not at least one of these cases are found to be true, then there is no collision.

Future Ideas and Possible Improvements

The algorithm would benefit from several optimizations and improvements:

• Any polygon that has zero points should be removed from the polyhedron automatically. They are redundant.
• The number of tests performed could be significantly reduced to only the necessary ones. At the moment it uses a very brute-force approach.

Screenshots and Video

Video file (6.9M)