Research On Key Technology Of Collision Detection In Virtual Reality

Collision Detection, also called Interference Detection or Contact Detection, is a fundamental operation used in a variety of areas such as computer graphics, computational geometry, robot path planning, computer animation, visualization and more. Its fundamental task is to detect whether there are contacts or penetrations between two or among multiple objects and return the corresponding collision information. So far, collision detection methods have been extensively developed. However, with the development of computer hardware and software, as well as virtual reality technologies, the demands of real time interactivity and accuracy of collision detection have become more sophisticated. Therefore, more general, accurate and faster collision detection algorithms need to be designed according to the actual needs.Based on a intensive survey and comprehensive analyses of various approaches of collision detection in virtual reality, several algorithms have been designed, implemented and verified to explore the possibility of speeding up and perfecting the process of collision detection and response, from the perspectives of using Machine Learning, Data Mining, Artificial Intelligent techniques and the high computing power of graphics hardware.1. Bounding volumes are the most renowned and useful data structures, which have provided an effective way to resolve the intrinsic time complexity in the collision detection problem. And by utilizing simple volumes to contain more complex objects, the efficiency of geometrical operations has been improved. The common types of bounding volume are spheres, axis-aligned bounding boxes (AABBs), oriented bounding boxes (OBBs), discrete-oriented polytopes (k-DOPs) and ellipsoids. In practice, models are checked in pairs, so that the tightness with respect to the closest direction between two models has great effect on the efficiency of the collision detection and proximity queries. However, none of the above bounding volume types has considered that aspect, so they are not applicable to the exact collision detection. Therefore, they usually resort to utilize a certain hierarchy (BVHs) to obtain more accurate approximation of the object. However, these hierarchies may not be able to perform significant culling, and they can not judge and give the depth and other important information in deep puncture case and also not suitable for large-scale deformable objects either.A new bounding volume type is proposed: Approximate Separating Bounding Volumes (ASBVs). ASBVs'positions and shapes are determined by the optimum separating hyper plane of two models. ASBVs are the tightest volumes in the optimum separating direction of two models, so that they can help achieve high culling efficiency in collision detection process. We also present an algorithm (called CASBV) to compute ASBVs for non-convex models by using linear Support Vector machines (SVM). When we take all the vertices of two objects as training data, the cost seems too large in real-time simulations, besides they are not definitely linear separating. Therefore, the idea of CASBV is to train the linear separating vertices in the convex hulls of two models to get an approximate separating hyper plane of two models. Considering ASBV can be regarded as AABB in the local coordinate, we take support vertices of two models with respect to six orientations of their AABBs as initial input data, and then in the following time steps train the support vectors of ASBVs to reduce the errors. The calculation process of ASBVs also can be seen as the initial detection process.And we also present a fast method (called ASBVCD) for determining the collision or proximity information for 3D models using ASBVs. Firstly, we transfer models to a local separating coordinate, and then find all the collided pairs by adopting a Scan-Line Similar Algorithm (SLSA). The experiments illustrate that ASBVCD is applicable to exact collision detection for 3D models even without topologies and achieves more efficient and balanced performances in separating and colliding cases.2. With aims to accelerate the speed and universality of collision detection, we introduce genetic algorithm(GA) and particle swarm optimization(PSO) algorithm into the collision detection field. In order to utilize intelligent optimization algorithms to collision detection problem, we firstly need to know the essence of intelligent optimization algorithms, then understand and analysis the specific collision problem, lastly combine optimization algorithms with the existing collision detection technologyies, improving the accuracy and efficiency of collision detection process.Firstly a method (called GASP) based on genetic algorithm for searching an optimal separating hyperplane is proposed. GASP uses binary code strategy to encode the hyperplane coefficients. Set each vector made by an L-bit binary number, so we get a (2×N)×L random matrix with one each row representing a hyper plane. The fitness function is based on the objective function of the linear SVM and added a slack variable and punishment factors. In literations, every new group is evalued, selected, crossovered, and variated until the optimal fitness of the individual reaches a certain threshold or the best individual of groups or the average fitness of groups is no longer improved. Experiments show this method improves the accuracy and speed for the computation for optimal separating hyperplane of the intersecting models. In addition, the paper compared the GASP algorithm with CASVM algorithm. CASVM runs faster with the linear training data, especially in the separating cases. However, in the case of the intersection, many important feature points are omitted by CASVM, so it is very difficult to guarantee high accuracy. On the contrary, the GASP algorithm can ensure high accuracy and computing time is also acceptable in the case of the intersection under a certain sampling rate.Then we present a novel method (called DB-RFPSO) for collision detection by using PSO algorithm. If take two models as two feature point sets, then the collision detection problem can be converted to the problem that wether there exists at least a pair of points the distance between them is less then the collision threshold. Here we use PSO to settle this problem. In the preprocess stage, the algorithm adopts an adjacency-list L structure to store topological information. In detail detection, the entire optimization process is divided into two phases: (1) From the first time step, a density-based clustering PSO is find optimal or near-optimal solutions parallelly by sub-swarms. (2) Then in the following steps, add an active pairs searching process, searching around the local minima for more solutions according to spatial coherence. At the same time, determine whether the environment changes and update the particle swarm accordingly, maintaining the diversity of swarms to discover new solutions. Besides, in order to confine particles flying within the surface of meshes, we also propose a constrain strategy and perform it during every iteration. At last with BVHs, our method can achieve high detection ratio and balanced performances for collision and self-collision for complex models (e.g. clothing) at interactive rates.3. Image-based collision detection algorithms use graphics hardware's (GPU) programmable ability to conduct general computation to reduce CPU's computing load and improve the efficiency of collision detection. The methods generally project three-dimensional geometric objects to two-dimensional image-plane through graphics hardware. And then in the image space, they query and analysis various types of information stored in caches to detect objects'interference. Based on a broad research on limitations of adaptability and accuracy of image based collision detection algorithms, we combine geometric space collision detection algorithms, artificial intelligence optimization techniques and image space collision detection algorithms more reasonable to improve efficiency and accuracy of collision detection.Firstly, a method (called PSOO) to find an optimal viewpoint for the minimal storge for Layered Depth Images (LDIs) is proposed. At beginning, LDIs are stored into a 2D texture array and then the algorithm converts the minimal storge problem to an optimization problem in view space and then utilizes PSO to minimize the number of useful voxel, consequently minimize the memory cost.Secondly, a fast collision detection algorithm (LDICD) in image space based on LDIs is presented. LDICD maps the geometry computation between two arbitrary objects'LDIs into programmable GPUs, matching the parallel architecture of graphics hardware, and produces the collision detection results via real time rendering. The algorithm is divided into three steps: (1) Make ASBVs for two models and use their positions to determine the relationship between the models and calculate the intersection of the key areas (VoI). (2) Use GPU and CPU to compute LDIs within the VoI parallelly, discarding the part outside VoI. (3) Conduct collision queries between LDIs parallelly. The experimental results show that compared with ASBVCD algorithm proposed above, LDICD algorithm can make full use of graphics hardware with high efficiency, and at the same time to a large extent, can alleviate the burden of CPU. LDICD algorithm has the more obvious advantage in improving detection speed in more complex scenes.4.After the collision detection, collision response is also an important issue in virtual reality. The main task of the collision response is to modify objects'motion equations to determine the damage and deformation, when a collision is detected in virtual environment.In this paper a new efficient collision response algorithm is proposed in the image space. It is a common fact that, when the two objects collided, in most cases, there must be repulsive forces between them to make them separated. Assuming that the forces are to reduce the volume of penetration zone, we can compute volume and the potential energy by LDIs and then compute the response forces. Then update verteices'positions via Verlet integration method. After all the vertices'movement had been updated, the triangles also finished transformations. The strategy that converts collsion response to particles'response has greatly increased the versatility of the algorithm. The experimental results prove that LDIs based collision algorithm and collision response algorithm can get real-time both for volume simple and complex objects, especially useful for very large rigid models.In addition, a hybrid collision response method using dual penalty function method and the friction force method is proposed. The experimental results show this method is easy to implement and has great adaptability.In summary, the results of research in this article enrich the collision detection technology in virtual reality and the proposed algorithms have a certain theoretical significance and application value for the collision detection problems.