Chaman L. Sabharwal and Jennifer L. Leopold, Missouri University of Science and Technology, USA

The intersection between 3D objects plays a prominent role in spatial reasoning, geometric modeling and computer vision. Detection of possible intersection between objects can be based on the objects’ triangulated boundaries, leading to computing triangle-triangle intersection. Traditionally there are separate algorithms for cross intersection and coplanar intersection. There is no single algorithm that can intersect both types of triangles without resorting to special cases. Herein we present a complete design and implementation of a single algorithm independent of the type of intersection. Additionally, this algorithm first detects, then intersects and classifies the intersections using barycentric coordinates. This work is directly applicable to (1) Mobile Network Computing and Spatial Reasoning, and (2) CAD/CAM geometric modeling where curves of intersection between a pair of surfaces is required for numerical control (NC) machines. Three experiments of the algorithm implementation are presented as a proof this feasibility.

Intersection Detection, Geometric Modeling, Classification Predicates, Spatial Reasoning, Triangle-Triangle Intersection.