Variational BVH Construction Method In Collide Detection

Real time collision detection is one of the most important problems in the fields of robotics, computer animation, and virtual reality, etc. Its fundamental task is to detect whether there are contacts or penetrations between two or among multiple objects. Indeed, there have been many research achievements on solving the problem of collision detection, this problem, however, is yet to be solved with the emergence of such burgeoning techniques as virtual reality, and the demands of real time interactivity and realistic simulation of motions of virtual objects thereafter.Bounding volume hierarchy provides an effective method to resolve the intrinsic time complexity in collision detection. The idea behind it is to approximate the object with a simpler bounding volume that is a little bigger than the object. In building hierarchies on object, one can obtain increasingly more accurate approximations of the objects. So during traversing bounding volume hierarchy, it speeds up collision detection by prune away primitive pairs, which will not intersect clearly though rapid intersection test between bounding volumes and just deal with those whose bounding volume is intersected. The choice of bounding volume is the basic and key problem of this approach.In this article we raise the new method base on Lloyd cluster variational approximation for constructing bounding volume hierarchy, our new method takes outside volume of bounding volume as the cost function; uses the mesh partition method to construct the bounding volume hierarchy (BVH), and make many steps overall iterations to construct a better BVH, in the real collision detection platform we prove our method has the bounding volume more similar to original object and produce higher efficiency in collision detection.