A time-budgeted collision detection method

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 describe our findings on the inherencies of bounding volume traverse trees (BVTT). Based on this observation, we 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