Reducing feasible contacts between polyhedral models to red-blue intersections on the sphere

Abstract

Orientation-related problems in geometric design can be naturally expressed on the spherical surface S2 . A wide subset of such problems can be solved directly on the sphere by adapting well-known planar data structures and algorithms. This paper shows that the detection of feasible contacts between two translating polyhedral models can be formulated as a problem of this type. First, a dual spherical representation of polyhedra is introduced, which reduces the contact detection above to finding intersections between two sets of spherical polygons. Next, the red-blue blocks plane sweep algorithm is adapted to obtain both edge intersections and point-in-polygon inclusions in the spherical setting. An experimental comparison of this algorithm against a naive one shows an increasing advantage of the former as the complexity of the setting grows. The obtained edge-edge and vertex-face polyhedral contacts provide the relevant feature pairs to be tested for interference, leading to considerable savings in collision detection between polyhedral models, as shown in the experimental test performed.