Research On Some Key Techologies For Continuous Colision Detection Between Deformable Models

Collision detection (CCD) has a long research history and important research significance in physically-based simulation, computer games, and robot motion planning. With the comtinuous development of computer graphics and the emergence of emerging field including virtual reality, the request for real-time and accuracy is increasingly high.This paper mainly concentrates on deformable models composed of triangles. We use an interpolating motion between the discrete instances to depict the vertex motion trajectory, and check whether collisions occur during the motion. The research content includes CCD accelerated algorithms and its applications in finite element simulation and fluid/cloth coupling. The main contributions can be summarized as follows:(1) After analyzing the key factors for parallel collision detection, we present a parallel collision detection algorithm based on data partitioning. The algorithm is divided into two phases. In the initial phase, the scene data is partitioned from the view of space. In the collision detection phase, each data block is processed by one processor to update bounding volume parallel, while a static and dynamic task allocation strategy is adopted to make collision detection parallel. Compared with previous algorithms under16and24cores, it is shown that the algorithm can improve the efficiency of collision detection with good compatibility.(2) Based on the parallel algorithm, we present a novel culling algorithm that uses deforming non-collinear filters (NCF) to improve the performance of continuous collision detection algorithms. The underlying idea is to use simple and effective filters, NCFs, which reduce the number of false positives between the primitives. These filters are derived from the collinear conditions and can be easily combined with other culling methods. We have tested its performance on several benchmarks. Compared with previous methods, we can reduce the number of false positives significantly and improve the overall performance of CCD algorithms, especially for simulations with large time steps.(3) We design a dilated continuous collision detection algorithm which is capable of detecting collisions between fluid and cloth accurately without missing any penetrations. Then we present a simple collision response force to untangle each collision pair using the normal vector and the relative velocity. Compared with previous contact force methods, we observe reduction in jitter and constraint violation, as well as improved stability.(4) Collision detection is a very important aspect of the finite element analysis. Prior collision detection methods can only check collisions between the surface finite elements. We import CCD to finite element to solve the problem that prior methods cannot detect collisions between the internal mesh elements.With the help of the above technologies, we integrated the parallel collision detection algorithm into a robot operation system (ROS), and then integrated the collision response algorithms into open source finite element simulation platforms (Impact and Opentissue). It is shown that the algorithms can achieve good results in these systems.