REAL-TIME COLLISION DETECTION ON GPU by Hong Yang Thesis Supervisor: Prof. Wu Wen Software Engineering Master The goal of collision detection is to determine if any collisions occur between geometric models. For most simulation environments, for example, in motion planning, physics simulation and games, the final results are significantly influenced by the measurement of collision detection. In complex simulation scenarios, collision detection is always considered as the major computational bottleneck. Different from rigid bodies, the deformation of objects causes the change of the bounding volumes and sometimes leads to the self-collision problem. Therefore, it is more challenge to deal with the collision detection for deformable objects. In this thesis, the GPU-based collision detection methods for rigid-rigid objects and deformable objects are proposed, respectively. A front-based BVH method to detect the collision of the rigid-rigid bodies is presented and implemented in dental occlusion determination system. A novel two-level spatial hashing collision detection method is presented for real-time collision detection of deformable bodies based on modern GPU architecture. The second-level of spatial hashing is used to improve the culling efficiency. Moreover, a novel encoding method on GPU is proposed to compensate the inflexibility of the GPU memory system. Based on the two-level spatial hashing method, a continuous collision detection method is presented to detect the self-collisions of the deformable objects. The proposed methods can efficiently determine the colliding pairs of primitives between rigid-rigid bodies and deformable objects, respectively. The experimental results show that the proposed methods can perform high culling efficiency with low memory cost.