Continuous Collision Detection Algorithm For Large Scale Deformable Models

Collision Detection (CD) is a vital task and also one of the most computationallyexpensive tasks in almost all forms of computer animation and physical simulation.Collision detection of deformable models, especially consisting of more than tens orhundreds of thousands of triangles, has been a main interest in recent researches. Inspite of the rapid progress in the performances of CPUs and GPUs, performingcollision detection between large scaled deformable models still remains a challenge.Our research is aiming at continuous collsion detection for large-scaledeformable models. A two-level collision detection algorithm is used to reduce thenumber of collision tests as many as possible, in order to achieving a high interactiverate.In broad phase, we constructed a k-DOP BVH (bounding volume hierarchy).According to the experiment results, we choose26-DOP as the bounding volume. Weconstructed BV (bounding box) for each object and used BV tests to culling theprimitive pairs that clearly not collide. In narrow phase, we combined representativetriangle and orphan set, to cull dumplicate and unnecessary elementary tests.A filter level was added on the basis of two-phase algorithm. We first used DNFto cull several tests. And then we described the drwaback of NCF (Non-CollinearFilter) and provide a solution. In addition, a new filter named DCF (deformingconditional filter) was proposed. DCF was used after DNF and NCF to lower thenumber of elementary tests.We have implemented our algorithms on a desktop PC. We observe obviousimprovements on performance showing that our algorithms are more effective thanprevious approaches.