Computational Geometry and Object Modeling — Geometric

Haptic interaction in six degrees of freedom is critical to numerous applications, but is still prohibitively complex for realistic environments. This paper presents an approach to rendering six-degree-of-freedom contact among virtual objects using a novel data structure referred to as an implicit sphere tree. This data structure allows an extremely compact representation of volumetric objects and extremely rapid intersection testing among objects, which broadens the scope of virtual environments that can be rendered in six degrees of freedom at interactive rates. We introduce this data structure, along with appropriate techniques for collision detection and haptic rendering, and demonstrate its efficiency in representing and manipulating complex models