Continuous Collision Detection Algorithm Based On Spatial Projection And Its Application In Cloth Simulation

Collision detection is an indispensable part of computational geometry,computer animation,2D/3D games and physical simulation.It has a high complexity and a large amount of computation,especially in high-precision models.Because of its wide application,it has attracted the attention of many researchers and become a hot research topic in computer graphics.In this paper,collision detection is systematically studied.Continuous collision detection algorithm is selected from discrete collision detection and continuous collision detection as the base for improvement.A two-phase collision algorithm framework is used in our algorithm to rapidly reduce the number of collision pairs requiring accurate collision detection through twolevel elimination of collision pairs.Because accurate collision detection takes a long time,the more non-collision pairs are removed,the less the total time spent in the whole collision detection phase.The bounding volume hierarchy(BVH)is used to cull collision pairs in the high level in this paper,and the discrete orientation polytopes(k-DOPs)is determined by the theoretical analysis of various bounding volumes such as spherical bounding volume and axially aligned bounding box.For k-DOPs bounding boxes,the tightness,construction difficulty and intersection test difficulty of bounding volumes with different k values are different.In this paper,26-DOPs is finally used as the bounding volume for high-level culling through experimental comparison.The culling efficiency of traditional BVH is not high,so this paper adds extra bounding volumes on the basis of traditional BVH,that is,constructing bounding volumes for edges and points.If a collision pair collide,the four vertices of the collision pair must be coplanar and the collision point is inside the plane graph formed by the four vertices.Therefore,the primitive test of each collision pair can be divided into coplanar test and internal test.In the low-level culling phase,this paper uses two continuous filters to eliminate the two parts of the primitive pair.Firstly,a non-penetrating filter(DNF)is used to remove the primitive pairs that do not meet the coplanar conditions,and then a spatial linear projection filter(SLPF)is used to remove the primitive pairs that do not meet the internal conditions.In spatial linear projection filters,the projection vectors used are calculated from the vertex positions of each collision pair,so that each projection vector is valid.Experimental results show that the proposed method removes more collision pairs than DNF and the combination of DNF and non-collinear filter(NCF),and the whole collision detection process takes less time.Finally,this method is applied to cloth simulation to verify the practicability of it.Cloth simulation includes modeling,numerical integration,collision processing(collision detection and collision response)and rendering.Considering the simulation effect and difficulty,the cloth simulation adopts the finite element model,after verlet numerical integration,and then uses the collision detection algorithm proposed in this paper,and after the collision response and simple rendering,the picture can be displayed normally and the simulation effect is realistic,without obvious lag and penetration phenomenon.