Research On The Generation Algorithm Of Distance Fields For Deformable Objects In Collision Detection

In virtual environment, collision often occrues between objects because of the user interaction and objects movement. In order to keep the reality of environment, the collision must be detected in time and the corresponding collision response should be made, all of which will lead to update the drawing results. Atherwise, the penetrating phenomenon will happened, which can destroy the environment reality and user immersion. As a result, collision detection is very necessary for virtual environment. Different from rigid objects, deformable objects not only have a high degree of complexity, but also can make deformation under the external force, and what's more, topology may be changed in some situation. So a series of new challenges are brought for collsion detection problem. It has been the research focus that the collision detection of defomable object, especially the free-form collision detection algorithm based on distance fields.How to generate distance fields quickly and efficiently is the first importance issure for the free-form collision deteion algorithm based on distance fields. Two conditions need to be satisfied for a fast and efficient distance fields generation algorithm: one is a fast distance fields function, the other is a proper storage stucture. Compared with the existing generation algorithm of distance fields, the paper proposes a new generation algorithm of distance fields, which can significantly decreases the storage space, not impacting the running efficiency. New algorithm gives a great support to the updating algorithm of distance fields and free-form collision detection algorithm.A new and fast signed distance computaion algorithm from point to triangle is proposed. In order to overcome the complexity of the traditional distance computaion algorithm from point to triangle, the algorithm makes use of the parameters form of triangle, which converts the distance computaion problem of point-to-triangle into the the distance computaion problem of point-to-point. Actually, the problem is that solving the minum value of the dual function in the domain of triangle, which will significantly increase the computation efficiency.A new storage structure, named matrix octree, is given out. In the conventional octree, there are many points and the storage space is much wasted. Matrix octree not only can increase the visiting efficiency by making full use of the Morton properties, but also can save much storage space because of the matrix structure. Experiments have illutrated the storage saving under the premise of guaranteeing the excution efficiency of the algorithm.