Collision Detection and Force Response in Highly-Detailed Point-Based Hapto-Visual Virtual Environments

In this paper, we present a collision detection algorithm and a force response algorithm both for use in dynamic, rigid-bodied, highly-detailed, hapto-visual virtual environments in which the models´ geometry is point-based. Our collision detection algorithm partitions the virtual space into a modified octree in a preprocessing step. At runtime, collision detection involves querying the octree for the octant where the end-effector currently is, as well as the indices of neighboring octants. After the world space is narrowed down to a volume of interest, the algorithm checks to see if the end-effector falls inside any axes-aligned bounding box that is centered at the model surface points that reside in the aforementioned volume of interest. A collision is defined as the haptic endeffector being found inside an axes-aligned bounding box centered at a model surface point. After a collision is detected, the force response algorithm calculates a force vector that starts at the end-effector´s current position and ends at the model surface point closest to the end-effector. This is an adaptation of the common god/proxy-object approach but for use in point-based models.