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.