Research On Collision Detection Algorithm For Moving Objects

Collision detection technology is widely used in the fields of virtual reality,robot,computer animation and game.It is mainly used to detect whether collisions occur between objects.This technology is critical to the sense of reality in the virtual scene.There has been a lot of research on the current collision detection algorithms,and the existing algorithms are just for each object to use the unified bounding box structure or solve the problem of discrete collision problem,however in reality most objects are all different shapes,and the same bounding box structure is difficult to adapt to all objects,and now the collision detection algorithm needs to solve the problem of continuous collision,thus causing the algorithm the efficiency is low and can not meet the real-time continuous collision detection with complexity environment requirements.In concern of the problem of the single structure of bounding box,this paper considers the difference of the shape of each object,and proposes an improved collision detection algorithm based on shape classification to construct the balance binary bounding box tree.Taking into account the bounding box tightness and intersection test complexity,if the object is similar to the sphere,it will use the sphere bounding box,and the object with large difference in shape from the sphere,will use a OBB bounding box,which will make each object construct a composite bounding box with balanced binary tree structure.The experimental results show that this structure not only ensures the tightness of the bounding box,but also to take into account the complexity of the problem of collision detection test,and significantly accelerate the efficiency of collision detection.For the problem of real-time continuous collision,a fast collision reduction algorithm based on GJK algorithm is proposed in this thesis.Firstly,the algorithm reduces the dimensionality of the continuous collision detection problem to the dimensionality of the static collision detection problem,and then uses the GJK algorithm to detect the collision.If the collision is detected,the specific location of the collision is further obtained by the intersection method of the directed line segment and the convex body.The experiment proves that the algorithm has good real-time performance.