Research On The Collision Detection In Virtual Reality Based On Particle Swarm Optimization

Collision detection has been researched in many fields such as robot motion planning and computer graphics for a long time. 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.This paper takes the virtual campus roaming as its application background, and the main contribution is selecting an object with a simpler bounding volume that is a little bigger than other objects, to approximately describe the structure of the complex geometry objects, and gradually approach the objective object's specific characteristics via respectively organizing the hierarchical structure for each detecting objective's own bounding volume. Firstly, use the top-down method, recursively divide the fixed direction hull and calculate each division result, and finally build the hierarchical bounding volume tree according to the pre-defined rules to gradually approach the objective object's geometry model. During the process of traversing the hierarchical bounding volume tree, it carry on a rapid intersection test between the bounding volumes to prune away the primitive pairs which will not intersected as early as possible.A traversal tracing strategy is proposed that it base on the temporal-spatial coherence in the virtual environment. Through tracing the traverse process in previous time, the required traverse path in current time can be successfully obtained. This is a heuristic strategy and should be implemented in a traversal way. The experiments results shows that tracing strategy can reduce the intersection tests time and enhanced efficiency. The correctness and validity of collision detection can be guaranteed by maintaining the tracing list, and the algorithm's time complexity is also can be much decreased.At the end, we take the algorithm of particle swarm optimization to detect primitive pairs which will be collision. The algorithm samples primitive pairs within the models to construct a discrete binary search space for PSO, by which user can balance performance and detection quality. The algorithm is also very general that makes no assumption about the input model, which can be without topology information. It doesn't need to store additional data structures either, so the memory cost is relative low.It has been illustrated by experiment results and concrete application that the method combining particle swarm optimization algorithm and fixed direction hull can resolve collision detection between complex solid objects.