Virtual Environment Variable Body Collision Detection Algorithm

Collision detection between geometric models is one of the key problems of virtual reality, such as cloth simulation, computer animation, robotics, CAD/CAM and virtual surgery. Real-time and accurate collision detection is indispensable to enhancing the sense of reality of virtual environment, especially for virtual environment with haptic sensing. In simulation of virtual environment, collision detection always is the bottleneck of compute efficiency. Now research of collision detection for rigid objects tends to be perfect, but research of collision detection for deformable objects is scarce. For interactive objects in virtual environment such as virtual surgery training and cloth simulation and computer animation, deformable object is more universal than rigid object.This paper takes the cloth simulation application for example, according to sequencing in the simulation process, researches the key problem of collision detection for deformable object from physical model of cloth to broad phase and narrow phase.The paper mainly includes the following aspects:1. This paper compares the modeling method for deformable object, mass-spring model is adopted to modeling for deformable object. Then the dynamics of mass-spring model is analyzed, a modified strategy on variable time step of adapted Runge-Kutta method is proposed in order to trade off between accuracy and compute efficiency of cloth simulation system.2. This paper discusses the hierarchies bounding volume method on broad detection phase, include the kind of bounding volume, pre-process, update and intersection test of k-DOPs. The update of hierarchies bounding volume tree is researched and a method to compute fastest when "climbing method" and "approximate method" together is proposed. binary tree is replaced by quad tree to improve compute efficiency to meet the application of deformable object. In addition, self-collision detection method based on curvature was adopted to ensure the realistic of cloth.3. This paper analyzes and discusses the collision detection of primitive geometric element that required on exact detection phase: Moller algorithm, Held algorithm and Devillers algorithm. A modified Devillers algorithm is proposed to improve compute efficiency. The detailed collision point is used for collision response to adjust movement of cloth in time and ensure the realistic of the simulation process.4. As the implementation of above method, the experiment on collision detection between cloth and sphere achieves accurate and fast collision detection, the feasibility of improved algorithm in this paper is testified, moreover, the efficiency and accuracy of collision detection are enhanced.