A Generic Design for Implementing Intersection between Triangles in Computer Vision and Spatial Reasoning

Introduction

Triangular mesh is used to represent the boundary of freeform 3D objects. 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’ boundaries (approximate triangulations of objects) in region connection calculi (RCC8), leading to computing triangle-triangle intersection. Traditionally there are specialized algorithms for cross intersection and coplanar intersection. The intersection detection is a byproduct of actual intersection computations. Most of the time intersection detection is done prior to the determination of the actual intersection so that the non-intersecting objects can be discarded. For example, in qualitative spatial reasoning, intersection detection is sufficient, actual intersection is not required; however in geometric applications, it is desirable to have actual intersections. For early intersection detection, we present a complete uniform integrated algorithm that is independent of cross and coplanar intersection. Herein we illustrate this with an algorithm, and with a Python implementation where the output is displayed with tables and figures.

The ability to detect the existence of possible intersection between pairs of objects is important in a variety of problem domains such as geographic information systems (Egenhofer & Golledge, 1998), real-time rendering (Tropp, Tal & Shimshoni, 2006), collision-detection, geology (Caumon, Collon, Le Carlier de Veslud, Viseur, & Sausse, 2009), surface modeling (Houghton, Emnett, Factor, & Sabharwal,1985), computer vision, networking and wireless computing. Typically, the boundary of each object is represented as a triangulated surface and a triangle-triangle intersection is the computational basis for determining intersection between objects. Since an object boundary may contain thousands of triangles, algorithms to speed up the intersection detection process are still being explored for various applications, sometimes with a focus on innovations in processor architecture (Elsheikh & Elsheikh, 2012).

For pairs of triangles, there are three types of intersections: zero dimensional (single point), one dimensional (line segment), and two dimensional (area) intersection. In the past, almost all attention has been devoted to determining the cross intersections, which resulted in an absence of analysis in two dimensional intersections. Coplanar triangle intersections are unique because an intersection may be any of the aforementioned three types. If the triangles cross intersect, only zero or one dimensional intersection is possible. If the planes are parallel and distinct, the triangles do not intersect. If the triangles are coplanar, then there is a possibility of intersection. Even when the cost of intersecting a triangle pair is constant, the cost of intersecting a pair of objects A and B is order O(T_A* T_B) where T_A is the number of triangles in object A, and T_B is the number of triangles in object B.

In qualitative spatial reasoning, spatial relations between regions are defined axiomatically using first order logic (Randell, Cui, & Cohn, 1992), or the 9-Intersection model (Egenhofer & Franzosa, 1991). Using the latter model, the spatial relations are defined using the intersections of the interior, boundary, and exterior of one region with those of a second region. It has been shown in (Sabharwal & Leopold, 2011) that it is sufficient to define the spatial relations by computing 4-Intersection predicates, (namely, Interior–Interior (IntInt), Boundary–Boundary (BndBnd), Interior–Boundary (IntBnd), and Boundary–Interior (BndInt)) instead of 9-Intersections. Since IntBnd and BndInt are the converse of each other, only three algorithms are necessary for these predicates. In order to implement these algorithms, we must first implement the triangle-triangle intersection determination. The triangle-triangle intersection is a lower level problem that must be solved in order to determine the 4-Intersection predicates which, in turn, determine the qualitative spatial relation between two objects.