Collision detection with improved algorithm based on k-dop
Mingxiang Gao, Dingfang Chen · 2009
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 NAand NBof two flying BVTs, we perform the overlap test between NBand the environment BVT of NAwith the popular k-dop-based but updated algorithm at first. With the test, a set T of triangles intersecting with the bounding volume of NAis setup quickly, these triangles are all from NB. Then check the overlap pairs between triangles in NAand 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.