Physical Based Deformable Object Simulation And Collision Detection

Computer three-dimensional animation and virtual reality are important appli-cations of computer graphics. By supporting all these applications, realistic physi-cally based simulation technology draws more and more attention in the research area, meanwhile its computational complexity and developing graphics hardware introduced many challenges.Deformable objects, such as cloth, hair and muscle, appear in almost all physi-cal simulation environments. Deformable objects have their own structure and dy-namics characteristics, therefore significantly impact on the result of realistic simu-lation. In the simulation system including deformable objects, modeling and colli-sion detecting are bottleneck, which account for50to90percent of computation.This thesis designs and implements a simulation and collision detection system of deformable objects on GPU, in which new methods and improvements are pre-sented. The simulation system is built on graphics hardware using parallel algorithm with OpenCL.In this thesis, a new bounding volume hierarchy (abbr. BVH) is presented, which is based on complete binary tree. It’s a space-saving and memory-friendly structure on GPU. Based on this data structure, the BVH construction algorithm on CPU is given, with a relatively low complexity. Moreover, the update algorithm as well as collision detection algorithm on GPU are presented, which largely broaden the bottleneck. On the other side, an improvement on merging algorithm of normal cone is put forward. By optimizing the merging problem between angles on plane, this solution makes self-collision culling of deformable objects more efficient and accurate.The experimental result shows that the entire system accelerates about3times than CPU solution. Separately, the collision detection module accelerates about2.6times and the other modules accelerate more than3times.