Interface

The input to this implementation of the voxel algorithm is a set of triangles presented on each processor. That is, the input is expected to already be distributed; although the method will still work if all the triangles are presented on a single processor. The details of the input format are described in Appendix .

Triangles are widely used in computer graphics because they are a flexible, simple to handle lowest common denominator. It is easy to exactly triangulate any piecewise flat object; and curved objects can be approximated with any desired (but finite) degree of precision.

A collision is considered to have occurred if two triangles penetrate each other's planes. This definition does not require any ``inside/outside object'' tests, so no assumptions need be made about the underlying object topology. In particular, the triangles representing an object may form cracks, gaps, or holes without affecting the algorithm. This is important for supporting automatically generated or acquired geometric models, in which such irregularities may abound.