Continuous collision detection method based on spatial subdivision and dynamic bounding box

Abstract

The invention discloses a continuous collision detection method based on spatial subdivision and a dynamic bounding box. The continuous collision detection method comprises the steps of constructing avirtual soft tissue model and a virtual instrument model used for collision detection; calculating the space occupied by the moving path of the detection object; constructing dynamic bounding boxes for the moving paths of the objects in the same space, and performing intersection testing on the bounding boxes; determining a position where collision may occur by using a bisection method, and retreating the to-be-detected object from an actual position to a primary collision occurrence position by using a backtracking technology; constructing a hierarchical bounding box for the possible contactobject set and executing bounding box intersection detection; and carrying out an accurate detection step for determining whether the characteristics contained in the child nodes collide. According to the method, the problems of penetration and missed detection of the discrete collision detection method in virtual operation application can be solved, and the calculation efficiency can be greatlyimproved on the premise of ensuring the accuracy.

Description

technical field [0001] The invention belongs to the technical field of collision detection and relates to the problem of collision detection between soft tissues and surgical instruments in virtual operation experiments. Background technique [0002] As an indispensable part in the field of computer graphics and physical simulation, collision detection is a problem that must be solved in the research process of virtual simulation, robot path planning and other topics. In recent years, with the continuous development of computer technology, collision detection has been widely used in computer games, virtual reality and other fields, and has become a hot issue that researchers pay attention to. In virtual surgery, the collision between virtual surgical instrument and human tissue is the basis of deformation calculation and the premise of cutting operation. In the process of deformation calculation and model cutting, the operator has high requirements for collision detection. ...

AI Technical Summary

Problems solved by technology

However, there are two unavoidable problems in discrete collision detection due to its detection mechanism: (1) When the time interval between two detections is too large, there is a penetration problem in the detection between objects, that is, objects penetrate each other within the detection time interval The transparent algorithm cannot detect the problem that the collision occurs

(2) If the moving speed of the object is fast or the thickness is thin, it may lead to the problem of missed detection, that is, the problem that the collision of the object occurs within the time interval and the problem cannot be detected

However, their scheme does not address the unavoidable time cost of bounding box updates due to mesh topology changes

Li.CQ et al. (A Surface Mass-Spring Model With New Flexion Springs and Collision Detection Algorithms Based on Volume Structure for Real-Time Soft-Tissue Deformation Interaction, IEEE ACCESS, 6, pp:75572-75597, 2018) perfected the traditional continuous Due to the time-consuming shortcomings of collision detection, a hybrid algorithm based on continuous interpolation technology and volume structure detection is proposed

However, the surgical instruments were simplified as spheres in their experiments, so their scheme was not validated in complex scenarios

Images