Research And Implementation Of High-level Culling Algorithm For Self-collision Detection

Collision detection plays an important role in physical simulation,virtual reality and robot path planning,and attracts broad attention in recent years.As the rise of flexible body simulation,self-collision detection takes more and more time in the whole process.Traditional methods,such as bounding volume technology and spatial partitioning algorithm,are not able to accelerate the pro-cess.In this paper,we firstly research traditional self-collision detection approaches systematically,and find the performance bottleneck in the process of self-collision detection through experiments.Then we modify previous algorithm to tackle the bottleneck,and propose a new high-level culling algorithm.The main contents of this paper are summarized as follows:1.We conclude the general collision detection pipeline and analyze the algorithm in the process.Simultaneously,we construct the experiment system and find out the bottleneck of the process clearly through experiment analysis.We present a pipeline of experiment and an optimized direction for following algorithms.2.We propose the normal cone guided BVTT(bounding volume traversal tree)front tracking algorithm.Our algorithm absorbs both the advantage of curvature-heuristic algorithm for high-level culling ability and the benefit of BVTT front algorithm for reducing the number of bounding volume test.Therefore,we get a faster collecting process of collision pair.The detection process can be quickly parallelized by using the BVTT front.The final experiment results show that the overall speed of accelerated self-collision detection gets up to 8 times faster.3.We present a rapid deformation energy calculation algorithm.The energy based method is used to solve the problem that the normal cone algorithm cannot eliminate the non-flat region.The culling process is optimized by rapid deformation energy calculation.The final experiment results show that the running speed of energy calculation process is increased by 2 times,and the overall performance of collision detection is improved by 1.3 times.