Collision detection with improved algorithm based on k-dop

In this thesis, a new k-dop-based algorithm is presented to detect collisions between two flying objects in virtual environment (VE). The core of our algorithm is that, we build environment bounding volume tree (BVT) for each leaf nodes of flying BVT. When checking for overlaps between two leaf nodes N_A and N_B of two flying BVTs, we perform the overlap test between N_B and the environment BVT of N_A with the popular k-dop-based but updated algorithm at first. With the test, a set T of triangles intersecting with the bounding volume of N_A is setup quickly, these triangles are all from N_B. Then check the overlap pairs between triangles in N_A and triangles in set T with triangle-triangle overlap test. Comparing with the method directly using triangle-triangle overlap test for two flying leaf nodes, our algorithm can fast exclude the non-overlap triangles. With the new algorithm, fast and exact collision detection in VE consisting of multi flying objects has also been implemented.