A Collision Detection Algorithm for Point-Like Haptic Interactions in Highly Detailed Virtual Environments
Naim R. El-Far, Nicolas D. Georganas, Abdulmotaleb El Saddik · 2007
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