A Collision Detection Algorithm for Point-Like Haptic Interactions in Highly Detailed Virtual Environments

In this paper, we present a collision detection algorithm for use in hapto-visual virtual environments containing highly- detailed, rigid, and dynamic models that are manipulated with probe-like haptic devices. Our approach is primarily motivated by the observation that highly detailed virtual models are typically represented by dense point clouds (specifically those that result from high-resolution laser-scans of real-life objects). By not viewing models as the sum of their constituent points, but rather dealing with the vertices individually, we present a novel collision detection algorithm that bounds each individual vertex with an axes-aligned bounding box that is arranged in a modified octree during a preprocessing phase. Collision detection at run-time is then performed via an involved query of the octree searching for the haptic probe´s coordinates inside one of the aforementioned bounding boxes. Our algorithm runs in logarithmic time 0(log n) where n is the number of vertices that makes up the model(s). Our approach accommodates environments where objects undergo rotation and translation but on the condition that models remain rigid