Research On Collision Detection For Deformable Objects Based On Triangle Mesh

Benefited from the rapid development of computer graphics, the 3D world presents us is more and more reality. But the development of technology not only brings pretty scenes, but also the real feeling. As a main part of computer graphics, physically based simulation plays an important role in movie production and computer games. It releases our imagination and brings us much more interactive feelings than before. As an important part of physically based simulation, collision detection is more and more attracted by people, especially the collision detection for deformable objects. Collision detection for deformable objects has been a major interest of the research of computer graphics recently, and it plays an important role in cloth simulation and surgery simulation. This thesis discusses two kinds of classical algorithms in the area of deformable collision detection faced to the cloth simulation.The computational burden of collision detection is very heavy and it is always the bottle-neck of the physically based simulation. Compared to collision detection for rigid objects, collision detection for deformable objects introduces additional challenging problems: we can't do efficient pre-process; self collision has to be considered; how to acquire precise collision information and etc. In interactive or real-time applications such as virtual surgery and computer games, the efficiency of collision detection algorithms for deformable objects is especially important.This thesis discusses two kinds of collision detection algorithms for deformable objects, and describes all kinds of problems in the algorithms. Specifically, we make the following contributions and innovations:1. Introducing the bottom to up algorithm based on the connectivity of elements to create the BVH. Also we can collect the adjacency information during this process.2. Modifying the up to bottom algorithm to updating the BVH.3. Introducing the "Tandem" algorithm in self collision detection to eliminate the reduplicate query.4. Modifying the elements based spatial hashing so as to use "vertex-triangle" algorithm other than "vertex-tetrahedron" which is for volume model.The remainder of the thesis is organized as follows. Chapter 1 introduces the backgrounds and the state of the art of collision detection algorithms for deformable objects. Also it introduces the main content in the thesis. Chapter 2 introduces the collision detection algorithms for elements which will be used for deformable objects and some modified algorithms for some special application. Chapter 3 and Chapter 4 introduce the Bounding Volume Hierarchies and Spatial Subdivision. We discuss all-kinds of problems in the algorithms, and also give the pseudo code for some key problems and indigestible problems. Chapter 5 introduces the design, implement and application of the CDKit which contains our all implement for the algorithms. Chapter 6 concludes this thesis and discusses some future work.