Collision detection is considered as a major computational bottleneck of physically-based animation systems. The problem is still more difficult to solve when the simulated objects are non-convex and when they deform over time. This paper focuses on the specific case of collision detection for a surgery simulator aimed at training surgeons at minimally invasive techniques (ie. laparoscopy).
Non-invasive surgery is rapidly expending, since it greatly reduces operating time and morbidity. In particular, hepatic laparoscopy consists in introducing several tools and an optic fiber supporting a micro-camera through small openings cut into the patient's abdomen. The surgeon, who has to cut and to remove the pathologic regions of the liver, only visualizes the operation onto a screen. Learning to coordinate the motion of the tools in these conditions is a very difficult task. Figure 1 shows a typical tool used for laparoscopic surgery and a view of the control screen during an operation.
The aim of surgery simulators is to offer a platform enabling the surgeons to practice on virtual patients, thus getting rid of financial and ethical problems risen by training on living animals or on cadavers.
Virtual surgery brings a number of difficulties: It requires both the abilities to interact in real-time with the virtual organs through a force-feedback device and to perform a real-time visualization of the deformations. Moreover, the computed images should include as much visual realism as possible (texture of the organs, specular effects due to the optic fiber light, etc). In this context, the time that remains for performing collision detection at each simulation step is extremely small. The remainder of this paper focuses on this specific aspect of the problem. This work is a part of a wider project1 that studies all the aspects of the problem, including real-time deformable models devoted to the physically-based simulation of the organs [3].
Due to its wide range of applications, collision detection between geometric models have been studied for years in various fields such as CAD/CAM, manufacturing, robotics, simulation, and computer animation. The solutions vary according to the geometric representation of the colliding objects and to the type of query the algorithm should support. For instance, softwares that maintain the minimal Euclidean distance between the models are often required in motion planning application.
In our background of a surgery simulator, we are interested into methods that detect interpenetrations between polygonal models, since the latter are the most convenient for real-time rendering. We do not need to know the Euclidean distance between non-colliding objects. However, when a collision occurs, the precise knowledge of the intersection region is needed, since it will allow a precise computation of subsequent deformations and of response forces.
Most of the previous work in collision detection between polygonal models has focused on algorithms for convex polyhedra [1,8]. These algorithms, based on specific data-structures for finding the closest features of a pair of polyhedra, exploit temporal and geometrical coherence during an animation. They are very efficient: the algorithm in [8] runs in roughly constant time even when the closest features change. However, they are not applicable in the case of a surgery simulator, since organs are generally non-convex, and deform over time.
Among the collision detection methods that are applicable to more general polygonal models [10,2,12,4,11,13,5,7], almost all of the optimizations rely on a pre-computed hierarchy of bounding volumes. The solutions range from axis-aligned box trees, sphere trees [12,11,7], or BSP trees, to more specific data structures [2]. All these techniques, which perform very efficient rejection tests, may considerably slow down when objects are very close, ie. when the bounding volumes have multiple intersections. Among the recent approaches for finding bounding volumes that tighter fit the object's geometry, Gottschalk [5] obtains very good results by using hierarchies of oriented bounding boxes instead of axis-aligned boxes. Section 5 will compare our new method with the public domain software package RAPID that implements this technique.
A last issue in collision detection is the ability to perform dynamic rather than static detection [10,4]: moving objects may interpenetrate between consecutive time steps, so the intersections should be computed between the 4D volumes that represent the solids' trajectories during a time step rather than between static instances of the solids. In the context of a large environment with lots of moving objects, using space-time bounds on the object's motion may lead to the quick rejection of a number of intersection tests [9,6,7].
In previous works on laparoscopic surgery [3], a dynamic collision detection was performed by testing for an intersection between the segment traversed by the tool extremity during a time step and the polygonal mesh representing the organ. A bucket data-structure discretizing the organ's bounding box, and storing local lists of polygons, was used to optimize this test. Real-time performances were obtained with a scene consisting in an organ and two tools, when no update of the bucket data-structure was needed. However, each tool was modeled as a single point, which resulted into possible penetrations of the body of the tools into the organ when an unexperimented user was trying to position them. Moreover, considering no update of the bucket structure was very restrictive concerning the possible deformations of the organ.
In the context of surgery simulation, the collision detection problem is enhanced by the non-convexity of most of the organs, and by the fact they deform over time. These deformations are far from negligible : laparoscopy typically involves large scale deformations and even topological changes in the structure of the liver since some parts are cut down and removed. In this context, spending time for pre-computing complex bounding volumes does not seem adequate, since this computation will need to be redone at each time step. A second point is that, even if the number of colliding objects remains small (usually: an organ of interest and few surgical tools), objects usually stay in very close configurations. Collisions or contacts may occur at almost each time step, since the surgeon uses the tools to manipulate the virtual organ. Basically, whatever the method, an intersection test between each tool and the organ will be needed at each time step.
Thirdly, collisions need to be detected even during a fast motion of the tools, otherwise incorrect response forces would fed back to the user. So using dynamic detection, at least for the tools motion seems indispensable. Fortunately, the sum of features of the problem ease its resolution: only one of the objects (the organ) has a complex shape since the tools used in non-invasive surgery can be represented by thin and long cylinders (see Figure 1(a)). Moreover, the tools have a constrained motion since they enter into the patient's abdomen through small circular openings. These two properties enable us to take benefits of the graphics hardware for detecting collisions in real time.
The remainder of this paper develops as follows: Section 2 explains how the graphics hardware may bring a solution to our problem. Section 3 gives a method for performing static collision detection between a tool and the polygonal model of an organ. This method is extended in Section 4 in order to take the dynamic motion of the tool into account. Section 5 presents our results, including a numerical comparison of computational times with the public domain software RAPID.
