Research On Collision Detection In Virtual Evironment

Collision detection has been researched in many fields such as robot motion planning and computer graphics for a long time. In the later years, with the rising of virtual reality and distributed interactive simulation, many researches focus on collision detection, especially collision detection with flexible objects . Efficient and Exact collision detection is very important to improve reality and enhance immersion for virtual environment, and the complexity and real-time of virtual environment bring new requirement to collision detection.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.With the background of surgery simulation, this paper proposes a collision detection method based on fixed direction hull bounding volume tree. Fixed direction hulls is a special convex hull, whose outward normal of facets comes from a fixed direction set. It overcome limitations of other bounding volumes and makes a promise between tightness and simpleness. Based on researching and developing intrinsic character of fixed direction hulls, this paper develops and proves the property which make it can be apply to collision detection in complex environment and resolves the problems about intersection tests between bounding volumes, updating bounding volumes after rotation and updating bounding volume hierarchy after deformation.This paper brings forward and proves a rapid interval test for resolving intersection tests between bounding volumes. It determine two bounding volume do not overlap by checking if one of their bound intervals on direction axis defined by the fix direction set does not overlap. Thus the intersection test between two bounding volumes need only at most k comparisons, (k is the size of fixed direction set.)Updating bounding volumes after rotation is an important problem of hierarchical bounding volume approach. An updating algorithm based on linear programming isproposed 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.Deformation of object is a difficulty in collision detection. This paper analysis three kinds of deformations and propose resolving method respectively. A bottom-up updating method is propose especially which can compute the bounding volume of parent node through bounding volumes of the two children by k comparison.Furthermore, a traverse tracing strategy that can speed up collision detection is proposed in this paper based on developing and utilizing temporal-spatial coherence in virtual environment. This is a heuristic strategy. It can reduce the intersection tests need to be computed between bounding volumes by tracing the traverse process in previous time to gain traverse path in current time. The correctness and validity of collision detection can be guaranteed by maintaining the tracing list.It has been illustrated by experiment results and concrete application that the method based on bounding volume hierarchy of fixed direction hull can not only resolve collision detection between solid objects, but also provide an reliable and efficient way to resolve and deal with collision detection in flexible environment. The research in this paper provides great theoretical value and practical meaning to collision detection in large-scale complex environme...