# Triangle-Triangle Intersection Determination and Classification to Support Qualitative Spatial Reasoning

### Authors: Chaman L. Sabharwal, Jennifer L. Leopold, Douglas McGeehan

*Polibits,* Vol. 48, pp. 13-22, 2013.

Abstract: In CAD/CAM modeling, objects are represented using the Boundary Representation (ANSI Brep) model. Detection of possible intersection between objects can be based on the objectsâ€™ boundaries (i.e., triangulated surfaces), and computed using triangle-triangle intersection. Usually only a cross intersection algorithm is needed; however, it is beneficial to have a single robust and fast intersection detection algorithm for both cross and coplanar intersections. For qualitative spatial reasoning, a general purpose algorithm is desirable for accurately differentiating the relations in a region connection calculus, a task which requires consideration of intersection between objects. Herein we present a complete uniform integrated algorithm for both cross and coplanar intersection. Additionally, we present parametric methods for classifying and computing intersection points. This work is applicable to most region connection calculi, particularly VRCC-3D+, which detects intersections between 3D objects as well as their projections in 2D that are essential for occlusion detection.

Keywords: Intersection Detection, Classification Predicates, Spatial Reasoning, triangle-triangle Intersection

PDF: Triangle-Triangle Intersection Determination and Classification to Support Qualitative Spatial Reasoning

PDF: Triangle-Triangle Intersection Determination and Classification to Support Qualitative Spatial Reasoning