1995 · 112 citations · 0 references
ComputingRobotics EngineeringComputer GraphicsImmersive VisualizationVirtual Reality DesignCollision DetectionSense-and-avoid SystemsVirtual Environment DesignVirtual RealityVirtual Reality PrototypingVirtual World NavigationDistance-based Collision DetectionFly-through VisualizationReal-time Collision AvoidanceReal-time Collision DetectionVirtual Flythroughs
We consider the problem of preprocessing a scene of polyhedral models in order to perform collision detection very efficiently for an object that moves amongst obstacles. This problem is of central importance in virtual reality applications, where it is necessary to check for collisions at real-time rates. We give an algorithm for collision detection that is based on the use of a mesh (tetrahedralization) of the free space that has (hopefully) low stabbing number. The algorithm has been implemented and tested, and we give experimental results comparing its performance against three other algorithms that we implemented, based on standard data structures. A preliminary version of this paper appeared in the proceedings of the 7 th Canad. Conf. Computat. Geometry, Qu'ebec, Aug 10--13, 1995. y held@ams.sunysb.edu; Supported by NSF Grant DMS-9312098. On sabbatical leave from Universitat Salzburg, Salzburg, Austria. z jklosow@ams.sunysb.edu; Supported by NSF grants ECSE-8857642 and C...