Research On Distance Fields And Its Application In Collision Detection

Collision Detection is a fundamental operation used in a variety of areas such as computer graphics, computer animation, robotics, computational geometry, visualization and more. Efficient and exact collision detection is very important to improve reality and enhance immersion for virtual environment, because most often collision detection is performed in real-time environments that require an interaction with users. Frequently, the models that are used consist of very large geometric primitives that consume a lot of time to process, which often becomes the neck of bottle in the whole application. So how to improve the efficiency and accuracy is the main task to all researchers in this area.Intense research over the last decade has provided many algorithms for particular applications. Rigid objects which are moving in a static environment are an example for the most common scenario. In this case, hierarchical collision detection algorithms provide exact and fast solutions. A bounding volume hierarchy is built for each object and during collision detection the hierarchies are tested recursively against each other for overlap. Since these overlap tests are highly efficient and the number of tests with geometric primitives is usually small, the overall performance allows interactive applications.But in the case that one of the objects is not rigid anymore things become worse. Just imagine a piece of cloth dragged around in virtual environment. Now it is possible that the whole surface of the deformable object is in contact with another object. In this case the collision detection performance of a bounding volume hierarchy drops considerably. Although the hierarchy is still able to report nearby triangles very efficiently, the number of primitive overlap tests increases to a maximum, since all geometric primitives of the deformable object have to be tested with primitives of the other object. In many applications this means that you have to check lots of pairs of triangles against each other. Clearly, this approach is prohibitive for interactive applications. In particular, if the application has to resolve not only collisions but also response which solve differential equations for dynamic motion.In order to overcome this performance problem, we use distance fields as a basis for proximity queries for rapid collision detective between deformable and rigid objects. A distance field is a vector field and is a representation where at each point within the field we know the distance from that point to the closest point on any object within the domain. In addition to distance, other properties may be derived from the distance field, such as the direction to the surface, and when the distance field is singed, we may also determine if the point is internal or external to objects within the domain (positive number means external and negative number means internal). The distance field information is computed in the pretreatment part, which makes the computation doesn't affected the simulation of our virtual environment. In the kinetic simulator, through constructs the good distance field information, we may get the distance of a spot to an object fast, and does not need to test all geometric primitives. This kind of algorithm, carries on the massive calculations in the pretreatment part and preserves the related information, is a typical technology which use the spatial receiving in exchange for time, this method is very useful for the collision detection research between deformable object and the rigid body.In this paper, we research in the distance field technology which used in the collision detection, and conducted the research in the following aspect. After that we proposed the corresponding algorithm's improvement, and applied finally from the field information to simulate the real-time collision detection and collision response.Firstly, When we use the approximate template method to build up the distance field information, we need to change the triangle grid object to voxels, and then. Construct a three dimensional matrix to save these distance information. In order to build up the distance fields, this article improved the triangle grid expression object voxel method. Regarding the triangle grid expression's object, makes the vertex and the triangle mesh be voxels, then uses the 3-SEDT algorithm, disseminates in the three-dimensional body bounding volume the distance information, thus gained the distance field information.Secondly, Regarding the three-dimensional body, we carry on the use from the distance information the collision detection, generally only needs nearby the three-dimensional body in certain distance scope spot information, regarding is away from the three-dimensional body quite far voxel, we are insensitive regarding his distance information. Based on this, we use precise Euclidean distance to be away from the computational method, proposes one kind of fast partial distance field computation algorithm. Three-dimensional model's raw material was still the triangle grid, but we need to know the triangle sheet's normal direction. Our algorithm's main idea is carries on the computation of the distance information to all triangle mesh's small bounding volume. Uses this algorithm, we may have a very fast method to construct model surface nearby distance field information. Like this, we increased computational accuracy, while reduced the computation complexity.Thirdly, We use the calculated distance field information, carried on the simple circumstance between a particle and rigid body to simulate the collision detection and the collision response. As for the single particle, we simply compute the new position and the speed changed under the exogenic forces process. As the collision occurs, we made the position adjusted. In order to increase the simulation effect, we increased the friction effect. The experiment indicated that our method may achieve the request of real-time animation. Fourthly, we constructed a cloth module to our system. The cloth material has used based on the Mass-Spring model, and calculates the cloth material using the VERLET integral the kinetic simulator. This method simplified the computation of the cloth material simulation in each time step. After that, we carried on the kinetic simulator which the cloth material and the rigid body the collision detection and the collision response. We test all the"particle"of the cloth material to determine the collision occurs or not. After the collision occurs, we made the position adjusted, and deal with a special situation which particles trapped by a concavities body. The experiment indicated that we calculate the distance field information may have a very good performance to build up a real-time kinetic simulator.In conclusion, the results of our research results enrich the approaches to collision detection technology and the applications of objects. We investigated the precision and efficiency evaluation about the algorithm and found that it might be a reasonable choice for complex component. We hope that intensive and further research will be aroused through our research, and facilitate the development of relative technology in future.