Improvement Of The Collision Detection Algorithm Based On K-dops's

Real-time collision detection is considered as a major computational bottleneck in achieving interactive simulation for complex environment. It has been studied in many fields including robotics, computer graphics, computer-aided design, and computational geometry. The goal of collision detection is to automatically report geometric contact when it is about to occur or has actually occurred. There are many algorithms of collision detection using in virtual reality technology. Hierarchical bounding volume algorithm has been used widely, which idea is to approximate the object with a simpler bounding volume that is a little bigger than the object, by building hierarchies on object, one can obtain increasingly more accurate approximations of the objects. So during traversing hierarchical bounding volume, it speeds up collision detection by getting rid of primitive pairs, which will not intersect clearly through rapid intersection test between bounding volumes and just deal with those whose bounding volume is intersected.In this paper, we analyze a method, based on K-dops "K-discrete orientation polytopes" bounding volume, a convex polytope whose facets are determined by halfspaces whose outward normals come from a small fixed set of k orientations. K-dops can be seen as an extension of AABB, it inherits not only the tightness of convex hull, but also the simpleness of AABB. It overcome limitations of other bounding volumes through adjusting the fixed set of k orientations and makes a promise between tightness and simpleness.Updating bounding volumes after rotation is an important problem of hierarchical bounding volume approach. An updating algorithm based on linear programming is proposed in this paper based on the definition and property of fixed direction hulls. This method need not add any additional computation and memory during building bounding volume hierarchies. It can update a bounding volume through 3k multiplication.