A Time-Budgeted Collision Detection Method
Yu-Te Lin
Collision detection is a critical module in many applications such as computer graphics, robot motion planning, physical simulation, CAD/CAM, and molecular modeling. Many efficient algorithms have been proposed to solve the collision detection problem, and most of them use some sort of hierarchical bounding volume to speed up the time-consuming process. In this research, we focus on a special situation for applications such as interactive virtual environment, where accuracy may not be crucial but the available time for performing the check is limited. We will describe our findings on the inherencies of bounding volume traverse trees (BVTT). Based on this observation, we will propose a time-budgeted collision detection method that can traverse the critical regions of BVTT earlier if the time budget is limited. Preliminary experimental results are also reported, and a new strategy is suggested based on the concept of confidence value.
Category: Collision Detection