Controlling the contact levels of details for fast and precise haptic collision detection

For accurate and stable haptic rendering, collision detection for interactive haptic applications has to be done by filling in or covering target objects as tightly as possible with bounding volumes (spheres, axis-aligned bounding boxes, oriented bounding boxes, or polytopes). In this paper, we propose a method for creating bounding spheres with respect to the contact levels of details (CLOD), which can fit objects while maintaining the balance between high speed and precision of collision detection. Our method is composed mainly of two parts: bounding sphere formation and two-level collision detection. To specify further, bounding sphere formation can be divided into two steps: creating spheres and clustering spheres. Two-level collision detection has two stages as well: fast detection of spheres and precise detection in spheres. First, bounding spheres are created for initial fast probing to detect collisions of spheres. Once a collision is probed, a more precise detection is executed by examining the distance between a haptic pointer and each mesh inside the colliding boundaries. To achieve this refined level of detection, a special data structure of a bounding volume needs to be defined to include all mesh information in the sphere. After performing a number of experiments to examine the usefulness and performance of our method, we have concluded that our algorithm is fast and precise enough for haptic simulations. The high speed detection is achieved through the clustering of spheres, while detection precision is realized by voxel-based direct collision detection. Our method retains its originality through the CLOD by distance-based clustering.