Matthieu Nesme
email: matthieu.nesme@imag.fr

Franc ¸ois Faure
email: francois.faure@imag.fr

Yohan Payan
email: yohan.payan@imag.fr

Hierarchical Multi-Resolution Finite Element Model for Soft Body Simulation

The complexity of most surgical models has not allowed interactive simulations on standard computers. We propose a new framework to finely control the resolution of the models. This allows us to dynamically concentrate the computational force where it is most needed.

Given the geometrical model of an object to simulate, we first compute a bounding box and then recursively subdivide it where needed. The cells of this octree structure are labelled with mechanical properties based on material parameters and fill rate. An efficient physical simulation is then performed using hierarchical hexaedral finite elements. The object surface is used for rendering and to apply boundary conditions.

Compared with traditional finite element approaches, our method dramatically simplifies the task of volume meshing and increases the propagation of the deformations.

Introduction 1.Context

Soft body simulation is a growing research domain, for communities such as Computer Aided Surgery, Virtual Reality or Computer Graphics. Computer aided surgery (CAS) aims at assisting surgeons for the realization of diagnostic and therapeutic gestures in a rational and quantitative way in order to increase safety and accuracy [START_REF] Taylor | Computer integrated surgery: Technology and clinical applications[END_REF]. While the first designed systems focused on orthopaedics, researchers addressed more recently anatomical structures that cannot be considered as "rigid" as they are mainly composed of biological soft tissues. The corresponding CAS systems therefore need to take into account the displacements of the structures as well as their deformations. In most cases, authors propose to build biomechanical models of the anatomical structures and use these models to predict, in the most accurate way, the tissue deformations induced by the surgical gesture.

Virtual Reality (VR), in its interactions with the Medical community, has recently provided surgical simulation systems [START_REF] Cotin | Volumetric deformable models for simulation of laparoscopic surgery[END_REF]. As for the flight simulators used to train pilots, the idea is that these surgical VR systems could be a great help in the learning and training processes, allowing the surgeon to acquire, for example, some difficult hand-eye coordinations, to repeat several times the most difficult gestures or to choose the best surgical procedure for a given pathological case. As for the CAS systems, deformable models have been included into the simulators, with constraints in term of robustness and computation times.

Computer Graphics (CG) has developped methods for the visually plausible animation of complex physical objects such as clothes and hairs. Considerable speedups have been obtained for stiff flexible bodies using implicit time integration, which allows arbitrary time steps to be performed. Significant advances have also been made using hierarchical modeling and the control of levels of detail.

These three communities now converge towards the same needs, in terms of soft body modelling: accuracy, robustness and interactivity (i.e. fast computation times). Indeed, from one side the CAS community is now looking for models that could be per-operatively used, with possible real-time re-planning of the surgical gesture. From the other side, the VR and CG communities now focus on the accuracy of the deformations, in order to be as realistic as possible, in comparison with real data. In this framework, some recent works, coming from these communities, try to provide mechanical models with innovative implementations that preserve a continuous modelling context (with, for most of the works, a numerical resolution through the Finite Element Method) while proposing improvements, in terms of robustness and computation times. In addition, models built in the CAS or VR contexts need to be adapted to each patient anatomy. This point is particularly challenging (and time consuming) when a patient-specific Finite Element mesh needs to be defined.

Next part tries to summarize all of these recent works (part 1.2), while a new modelling approach is introduced in part 2. An example of implementation is presented in part 3 before providing some results (part 4).

Related Work

Deformable Models

In order to improve the computational efficiency of continuous biomechanical models, researchers have proposed new approaches concerning (1) the Finite Element discretization, (2) the dynamical integration and (3) the numerical resolution methods.

Because of the need for speed, the first interactive methods were based on precomputed matrix inversion [START_REF] Cotin | Volumetric deformable models for simulation of laparoscopic surgery[END_REF]]. To extend these methods to large deformations frameworks, a non-linear computation of the strains is used in [START_REF] Debunne | Dynamic real-time deformations using space and time adaptive sampling[END_REF][START_REF] Picinbono | Non-linear anisotropic elasticity for real-time surgery simulation[END_REF]. Recently proposed methods favor a new approach based on the decomposition of the displacement of each element into a rigid motion and a pure deformation tractable linearly in the local frame [Etzmuß et al. 2003;Hauth and Straßer 2004;[START_REF] Üller | Interactive virtual materials[END_REF][START_REF] Nesme | Efficient, physically plausible finite elements[END_REF]]. These methods allow a large displacements and rotations framework.

In the animation community, implicit integration methods have become popular, thanks to the iterative solution based on conjugate gradient presented by [START_REF] Baraff | Large steps in cloth simulation[END_REF]. Although these methods permit large time step, they become "expensive" when a fast propagation of the deformation is suited, since they require a lot of iterations to solve the system accurately. On the contrary, explicit integrations do not use iterations but require small time steps to maintain stability. Therefore, if a fast propagation of the deformations is needed, both implicit and explicit integration schemes remain computationally expensive. To face this problem, hierarchical methods have been proposed, providing an improvement of the propagation of the deformations (see for example the hierarchi-cal solvers proposed by [START_REF] Terzopoulos | Modeling inelastic deformation: viscolelasticity, plasticity, fracture[END_REF][START_REF] Wu | Multigrid integration for interactive deformable body simulation[END_REF]).

In order to adapt the numerical solution schemes to the adequate level of details, authors have proposed to adapt the Finite Element (FE) mesh according to the actual state of the model (in terms of displacement, strain or stress). They propose therefore a multiresolution FE approach ( [START_REF] Debunne | Interactive multiresolution animation of deformable models[END_REF][START_REF] Debunne | Dynamic real-time deformations using space and time adaptive sampling[END_REF][START_REF] Wu | Adaptive nonlinear finite elements for deformable body simulation using dynamic progressive meshe[END_REF]). The idea is for example to define, for a given anatomical structure, different FE meshes, from a very coarse one to a full refined one. If boundary conditions induce small deformations inside the structure, the coarse mesh is sufficient for providing accurate FE discretization. On the contrary, a dense mesh is used where the deformation is high.

Patient Specific Models

Building a patient specific FE mesh is usually a delicate and time consuming task. From imaging exams such as Computed Tomography or Magnetic Resonance, data can be collected through image segmentation, providing for example the external contour of an organ as well as intrinsic sub-structures. From these geometrical data, 2D or 3D FE meshes are built and used to discretize the mechanical formulation. Arguing against the time consuming component of this patient-specific FE mesh elaboration, authors have proposed use a reference FE mesh (an "atlas", built once from a reference patient geometry) and to match this mesh to each new patient morphology ( [START_REF] Couteau | The mesh-matching algorithm: an automatic 3d mesh generator for finite element structures[END_REF][START_REF] Castellano-Smith | Constructing patient specific models for correcting intraoperative brain deformation[END_REF][START_REF] Clatz | Realistic simulation of the 3d growth of brain tumors in mr images including diffusion and mass effect[END_REF]). These methods reduce the time needed to build the patient-specific FE models, but they are still very specific and may alter the quality of the elements during the registration phase.

Contribution

Our approach proposes to merge a multi-resolution description with a Hierarchical FE integration. It is supposed to provide a numerical scheme that can be used for any type of mechanical description, from a small deformation framework to hyperelasticity. The objective is only to gather some methods already proposed in the literature in order to improve the propagation of the deformations as well as the efficiency of the computation according to the mechanical and geometrical state of the soft body. The specificity of the method is that a global 3D mesh is defined from a classical octree division of a bounding box including the soft body. Therefore, no FE mesh is needed to specificaly model the 2D or 3D geometry of the body. Indeed, the FE computations are applied to the 3D mesh defined by the octree. To improve the propagation of the deformations, a hierarchical basis is defined to interpolate the FE computations, from the global parent cell defined by the bounding box to each child cell of the octree. Moreover, the multi-resolution scheme is used to decide, for a given state of the body, which levels of the octree should serve as basis for (1) FE computation and (2) 3D rendering: for example, only regions with high strains level should use a dense octree level for FE computation, while regions that are not displayed on the screen because they are not seen by the camera should use a coarse octree mesh level for the 3D rendering.

Octree Mesh and Multi-resolution

The first step consists in defining the complete 3D octree mesh as presented in figure 1-a. Starting from a cubic bounding box of the body, an iterative algorithm is used to divide each "parent" cube in order to generate eight "child" cubes. The cubes that do not contain any part of the body are removed from the octree mesh. The remaining cubes are again divided, so that each of them will generate 8 new cubes. A maximal level of division N max is defined once, leading to the "maximal density" octree mesh (figure 1-a). Using this octree mesh architecture as a baseline, two intermediate resolutions will be defined at each time step of the global computation of the system, namely the octree resolution N FE used for the FE mesh interpolation (figure 1-b) and the octree resolution N Rend used for the rendering display (figure 1-c). These two resolutions can change during the solving of the system, according to the changes in the boundary conditions as well as the location of the camera that looks at the scene. For example, one condition to define whether a given level of the octree mesh is suitable for a given point of the body consists in looking at the strain rate. If it is sufficiently low, this means that the current resolution is sufficient. On the contrary, if a high strain variation is observed, a denser mesh is preferable around this region of the body leading to the use of the child cells of the actual octree element. Once the N FE level is reached, the corresponding octree 3D mesh is used for the FE computation. In order to limit the influence of cells that would contain a small amount of the body (cells located at the surface of the body), it is proposed to ponderate the rheology of these cells by their filling ratio as illustrated in figure 4.

Hierarchical FE Bases

A function decomposed in a hierarchical basis is modeled using a rough approximation based on a few broad-range sample points, along with a number of recursively narrower-range sample points encoding local detail added to the approximation. Each value of the function is thus the sum of shape functions with various radius of influence. This approach allows one to easily control the level of detail by simply inserting or dropping control values where desired [START_REF] Stollnitz | Wavelets for Computer Graphics: Theory and Applications[END_REF]. Another nice feature of this approach is to considerably speed up the convergence of shape optimization, as shown in geometric modeling [START_REF] Gortler | Hierarchical and variational geometric modeling with wavelets[END_REF]. It has been successfully applied to finite element methods [START_REF] Grinspun | Charms: a simple framework for adaptive simulation[END_REF][START_REF] Capell | A multiresolution framework for dynamic deformations[END_REF]. In the case of the octree mesh introduced above, the position stored for each vertex is relative from its parents position. Therefore, only vertices from the root cell (i.e. the cubic bounding box that includes the body) have real position in the 3D space. At start, all others child cells have a null relative position which only depends on their parents. Figure 2 illustrates the FE interpolation that will be provided with hierarchical linear functions.

An Implementation

This section proposes an example of the implementation of the previously presented hierarchical approach. This implementation uses the Cauchy's deformation tensor and a viscoelastic material, and is therefore valid only for small displacements and small deformations.

Shape functions

The fundamental principle of finite element is to interpolate desired values u(p) using values u i defined at the nodes of the elements:

u(p) = ∑ i H i (p)u i (1)
with H i (p) the interpolation matrix for vertex p concerning the element node number i.

To simplify computations, interpolations are done in natural coordinates in a local frame (r, s,t) ∈ [-1, 1] 3 . To adapt computations in the global frame, the Jacobian operator J which relates the natural coordinate derivatives to the local coordinate derivatives is needed.

∂ h ∂ r = J ∂ h ∂ x .
As exprimed below, the interpolation matrix H depends on the position of the lattice vertices influencing on the interpolated object vertex. Eight types of interpolation matrices exists, one for each node position in a cell:

H i =   h i 0 0 0 h i 0 0 0 h i   , h i (r, s,t) = 1 8 (1 ± r)(1 ± s)(1 ± t)
3.2 Mechanics

Equations of Motion

The dynamic evolution of the deformations is modeled as the classical system of secondary order ordinary differential equation:

M ü + C u + Ku = f
To build matrices M, D, K and vector f, the standard method used to simulate viscoelastic is A classical approximation for the damping matrix D is to use D = αK + β M. External forces are computed as

f = V H T f dV
For example the gravity is applied like f gravity = V H T ρg dV , with ρ material density and g the acceleration field. To integtrate the volume over the natural coordinates the volume differential dV must be written in natural coordinate: dV = detJ dr ds dt

Our approach induces differences with classical formulation concerning the displacement u which is not defined in global space coordinates, but is defined hierarchically. Only displacements of the vertices of the root cell are in space coordinates. The displacement of others vertices is relative from their parents. To build the mass matrix M and the stiffness matrix K, not only finest elements are considered. Indeed, for each elements along the hierarchy we take into account all nodal functions that influence the considered element as exprimed in algorithms 1 and 2. C is the stress-strain matrix relating the material properties and the strain-displacement matrix B i is obtained by differentiation of h i with respect to local coordinate and premultiplying the result by the inverse of the Jacobian operator:

B i = J -1           ∂ h i ∂ r 0 0 0 ∂ h i ∂ s 0 0 0 ∂ h i ∂t ∂ h i ∂ s ∂ h i ∂ r 0 ∂ h i ∂t ∂ h i ∂ s ∂ h i ∂t ∂ h i ∂t 0          Algorithm 1 BUILD K AND M
for each cell do for each vertex i defined at level of cell do

INTEGRATE(B i , B i , H i , H i , C cell , J cell ) for each vertex j = i defined at level of cell do INTEGRATE(B i , B j , H i , H j , C cell , J cell ) end for
for each ancestor of cell do for each vertex j defined at level of ancestor do take function h j between range of cell in ancestor // detail in section 3.2.2

INTEGRATE(B i , B j , H i , H j , C cell , J cell ) INTEGRATE(B j , B i , H j , H i , C cell , J cell
) end for end for end for end for // Note that some computations can be omitted in considering the symetric aspect of matrices K and M: K i, j = K T j,i and

M i, j = M T j,i Algorithm 2 INTEGRATE(B i , B j , H i , H j , C, J) K i, j = 1 -1 1 -1 1 -1 B T i CB j detJ dr ds dt M i, j = 1 -1 1 -1 1 -1
H T i H j detJ dr ds dt

Range Definition of the Interpolation Function

Using natural coordinates, all integrations are performed between -1 and 1, corresponding to the range of the current cell. However the functions based on ancestor cells have an influence radius higher than the size of the child cells. We thus have to use a modified version of ancestor functions, such as h j illustrated in 1D in figure 3. ). Table 1 compares the number of iterations necessary to converge using the nodal approach (i.e. the classical non-hierarchical one) against the hierarchical approach. Two examples are considered for several numbers of elements, the first one consists in a cubic fixed beam subject to gravity, while in the second a force is applied to a corner of the beam. As expected, the convergence is faster using the hierarchical approach. When the corner is pulled, the other end moves directly, whereas in the nodal model it is necessary to propagate the deformation along all elements. This faster propagation is useful in case of real-time simulation when only few iterations can be performed at each step. Using hierarchy, a small number of iterations (approximately ten) provides a much more accurate result, as illustrated in figure 5 that plots the convergence speed of the second example of table 1.

Conclusion

We proposed in this paper a hierarchical multiresolution technique to animate soft bobies. This new approach based on a octree mesh permits to work on various geometrical representations of an object without needing to provide a volumetric mesh of this object. Using the hierarchical approach improves the propagation and permits to simulate more rigid materials. Despite it, we do not yet obtain better results in terms of computation time because an optimized structure is difficult to set up. To make this work usable, it will be necessary to integrate criteria of adaptivity (automatic definition of N FE and N Rend values), and to take into account effective boundary conditions.

Figure 1 :

 1 Figure 1: An exemple of adaptativity. (a) leaves of the octree mesh = the finest level of details. (b) mechanical leaves = the finest mechanical level. (c) geometric leaves = the finest geometric level.

Figure 2 :

 2 Figure 2: Illustrations of the finite element (top-left), basis function (top-right) and hierarchical basis function (bottom) points of view with linear interpolation. In the basis function point of view, the solution corresponds to a combinaison of functions associated with the nodes. In the hierarchical point of view, the influence support of these functions varies.

Figure 3 :

 3 Figure 3: In the local frame of the red element, we must consider functions h i (r) and h j ( (1-x)r min +(1+x)rmax 2

Figure 4

 4 Figure4shows an octree mesh for a surfacic liver model.

Figure 4 :

 4 Figure 4: A multiresolution octree-mesh for a liver: the entire mechanical hierarchy and the density of mechanical leaves.

Figure 5 :

 5 Figure 5: Convergence speed.

Table 1 :

 1 Number of CG iterations until convergence, on two examples on a cubical fixed beam.

	Number of elements		1	8	64 512
	example 1	nodal	1 13 55 146
	(gravity)	hierarchical 1 11 27	47
	example 2	nodal	8 50 87 198
	(boundary force)	hierarchical 6 24 37	52


M Teschner

S Kimmerle

B Heidelberger

G Zachmann

L Raghupathi

A Fuhrmann

M.-P Cani

F Faure

N Magnenat-Thalmann

W Strasser

P Volino

Collision Detection for Deformable Objects

Keywords: (according to ACM CCS): I, 3, 5 [Computer Graphics]: Computational Geometry and Object Modeling I, 3, 7 [Computer Graphics]: Three-Dimensional Graphics and Realism

Interactive environments for dynamically deforming objects play an important role in surgery simulation and entertainment technology. These environments require fast deformable models and very efficient collision handling techniques. While collision detection for rigid bodies is well-investigated, collision detection for deformable objects introduces additional challenging problems. This paper focuses on these aspects and summarizes recent research in the area of deformable collision detection. Various approaches based on bounding volume hierarchies,

distance fields, and spatial partitioning are discussed. Further, image-space techniques and stochastic methods are considered. Applications in cloth modeling and surgical simulation are presented.

Introduction

For many years, collision detection has been of major interest in computer graphics. Numerous approaches have been investigated to detect interfering objects in applications such as robotics, computational biology, games, surgery simulation, and cloth simulation. While many of the original collision detection methods primarily address the problem of rigid bodies, recent approaches have started focusing on deformable objects.

Deformable collision detection is an essential component in interactive physically-based simulation and animation which is a rapidly growing research area with an increasing number of interesting applications. Fig. 1 illustrates one of the major applications for deformable collision detection, namely cloth simulation. In cloth simulation, approaches to dynamically deforming clothes have to be combined with efficient algorithms that handle self-collisions of cloth as well as the interaction of cloth with animated avatars. Such applications require collision detection algo- rithms that are appropriate for deformable and animated objects.

Surgery simulation illustrated in Fig. 2 is a second major application area for deformable collision detection. In such environments, collisions among deformable organs have to be detected and resolved. Furthermore, collisions between surgical tools and deformable tissue have to be processed. In the case of topological changes due to cutting, self-collisions of tissue can occur and have to be handled. Since interactive behavior of surgery simulation environments is essential, efficient algorithms for deformable collision detection are required.

Figure 2: Interactive environments for surgery simulation are one of the major application areas for deformable collision detection.

In addition to cloth and surgery simulation, deformable collision detection methods are useful in environments with animated objects. Fig. 3 illustrates a sequence of two animated objects. In this example, specific collision detection algorithms for deformable objects can be used to detect interferences of both objects at interactive rates. Furthermore, the intersection volume of both objects can be computed if their surfaces are closed.

Figure 3: A sequence of two animated objects: Santa and Rabbit. Specific deformable collision detection algorithms can be used to compute the intersection volume of both objects at interactive rates. The intersection volume is shown in red.

If compared to collision detection approaches for rigid bodies, there are various aspects that complicate the problem for deformable objects.

Collisions and Self-collisions:

In order to realistically simulate interactions between deformable objects, all contact points including those due to self-collisions have to be considered. This is in contrast to rigid body collision detection, where self-collisions are commonly neglected. Depending on the applications, rigid body approaches can further be accelerated by only detecting one contact point.

Pre-processing: Efficient collision detection algorithms are accelerated by spatial data structures including bounding-volume hierarchies, distance fields, or alternative ways of spatial partitioning. Such object representations are commonly built in a pre-processing stage and perform very well for rigid objects. However, in the case of deforming objects these pre-processed data structures have to be updated frequently. Therefore, pre-processed data structures are less efficient for deforming objects and their practicality has to be examined very carefully.

Collision Information: Collision detection algorithms for deformable objects have to consider, that a realistic collision response requires appropriate information. Therefore, it is not sufficient to just detect the interference of objects. Instead, precise information such as penetration depth of objects is desired.

Performance: In interactive applications, such as surgery simulation, games, and cloth simulation, the efficiency of collision detection algorithms for deformable modeling environments is particularly important. Interactivity is a key characteristics in these applications, resulting in high demands for computing efficiency of collision detection algorithms.

In this paper, we discuss collision detection approaches that address the above-mentioned problems in order to meet the requirements of animation and simulation environments with dynamically deforming objects. Although all discussed algorithms are appropriate for deformable objects, they are not restricted to deformable objects, but also work with rigid bodies.

The remainder of the paper is organized as follows. Sec. 2 discusses bounding volume hierarchies. Special emphasis is placed on generating and updating the hierarchy. These aspects have to be optimized for deforming objects which require frequent hierarchy updates. In Sec. 3, stochastic methods are presented. These approaches are appropriate for interactive simulation environments, since they allow for balancing accuracy and performance. Sec. 4 describes the usage of distance fields for deformable collision detection. These approaches inherently provide information on the penetration depth of colliding objects which is important to compute a realistic collision response in physically-based simulations. Sec. 5 shows, how spatial subdivision can be employed for deformable collision detection. In these approaches, efficient data structures for representing 3D grids are important. Sec. 6 discusses recent image-space approaches. These methods commonly process projections of objects. Thus, they can be accelerated with graphics hardware. Sec. 7 presents applications in cloth modeling and surgery simulation. Finally, Sec. 8 summarizes advantages and drawbacks of the presented algorithms for deformable collision detection.

Bounding Volume Hierarchies

Bounding-volume hierarchies (BVHs) have proven to be among the most efficient data structures for collision detection. Mostly, they have been applied to rigid body collision detection.

Usually, a BVH is constructed for each object in a preprocessing step. The idea of BVHs is to partition the set of object primitives recursively until some leaf criterion is met. Most often, each leaf contains a single primitive, but one could as well stop when a node contains less than a fixed number of primitives. Here, primitives are the entities which make up the graphical objects, which can be polygons, NURBS patches, etc.

In general, BVHs are defined as follows: Each node in the tree is associated with a subset of the primitives of the object, together with a BV that encloses this subset with a smallest containing instance of some specified class of shapes. See [START_REF] Zachmann | Geometric data structures for computer graphics[END_REF] for a thorough discussion of BVHs in general.

One of the design choices with BV trees is the type of BV. In the past, a wealth of BV types has been explored, such as spheres [START_REF] Hubbard | Approximating polyhedra with spheres for time-critical collision detection[END_REF][START_REF] Palmer | Collision detection for animation using spheretrees[END_REF], OBBs [START_REF] Gottschalk | OBB-Tree: A hierarchical structure for rapid interference detection[END_REF], DOPs [KHM * 98, Zac98], Boxtrees [Zac02, AdG * 02], AABBs [START_REF] Van Den | Efficient collision detection of complex deformable models using AABB trees[END_REF][START_REF] Larsson | Collision detection for continuously deforming bodies[END_REF], spherical shells [KGL * 98], and convex hulls [START_REF] Ehmann | Accurate and fast proximity queries between polyhedra using convex surface decomposition[END_REF].

Although a variety of BVs has been proposed (see Fig. 4), two types deserve special mention: OBBs and k-DOPs. Note, that AABBs are a special case of k-DOPs with k = 6. OBBs have the nice property that, under certain assumptions, their tightness increases linearly as the number of polygons decreases [START_REF] Gottschalk | OBB-Tree: A hierarchical structure for rapid interference detection[END_REF]. k-DOPs, on the other hand, can be made to approximate the convex hull arbitrarily by increasing k. In addition, special k-DOPs such as the 26-DOP can be constructed and updated very efficiently, which is important for deformable geometry.

Hierarchy Traversal

For the collision test of two objects or the self collision test of one object the BVHs are traversed top-down and pairs of tree nodes are recursively tested for overlap. If the overlapping nodes are leaves then the enclosed primitives are tested for intersection. If one node is a leaf while the other one is an internal node, the leaf node is tested against each of the children of the internal node. If, however, both of the nodes are internal nodes, it is tried to minimize the probability of intersection as fast as possible. Therefore, [vdB97] tests the node with the smaller volume against the children of the node with the larger volume (Fig. 6).

For two given objects with the BVHs A and B, most collision detection algorithms implement the following general algorithm scheme: This algorithm quickly zooms in on pairs of nearby polygons. Note, that mixed cases where one node is a leaf and the other is an inner node are omitted. The characteristics of different hierarchical collision detection algorithms lie in the type of BV used, the overlap test for a pair of nodes, and the algorithm for construction of the BV trees.

Construction of Bounding Volume Hierarchies

For rigid bodies, the goal is to construct BVHs such that all subsequent collision detection queries can be answered as fast as possible on average. Such BVHs are called good in the context of collision detection.

With deformable objects, the main goal is to develop algorithms that can quickly update or refit the BVHs after a deformation has taken place. At the beginning of a simulation, a good BVH is constructed for the undeformed object just like for rigid bodies. Then, during the simulation, the structure of the tree is usually kept, and only the extents of the BVs are updated. Since DOPs are generally faster to update for deformable objects † they are preferred over OBBs.

Since the construction of a good initial BVH is important for deformable collision detection, we will discuss some of the issues in the following, while efficient ways of updating the hierarchy are discussed in Sec. 2.3.

There exist three different strategies to build BVHs, namely top-down, bottom-up [START_REF] Roussopoulos | Direct spatial search on pictorial databases using packed R-trees[END_REF], and insertion [START_REF] Goldsmith | Automatic creation of object hierarchies for ray tracing[END_REF]. However, the top-down strategy is most commonly used for collision detection.

The idea of top-down construction is to recursively split a set of object primitives until a threshold is reached. The splitting is guided by a user-specified criterion or heuristic that will yield good BVHs with respect to the chosen criterion.

A very simple splitting heuristic is the following. [START_REF] Gottschalk | OBB-Tree: A hierarchical structure for rapid interference detection[END_REF] approximates each polygon by its center. Then, for a given set B of such points, compute its principal components (the eigenvectors of the covariance matrix); choose the largest of them (i.e., the one exhibiting the largest variance); † In particular, special DOPs where all orientation vectors consists only of elements from {+1, -1, 0}. place a plane orthogonal to that principal axis and through the barycenter of all points in B; this splits B into two subsets. Alternatively, the splitting plane can be placed through the median of all points. This leads to a balanced tree. However, it is unclear, whether balanced trees provide improved efficiency of collision queries.

Fig. 5 shows two hierarchy levels for the 18-DOPhierarchy of an avatar, that was created top-down [START_REF] Mezger | Hierarchical Techniques in Collision Detection for Cloth Animation[END_REF].

For AABBs, it can be shown that any splitting heuristic should try to minimize the volumes of the children to achieve good BVHs [START_REF] Zachmann | Minimal hierarchical collision detection[END_REF]. Using Minkowski sums of BVs, one can estimate the geometric probability of an overlap of a pair of BVs (A i , B j ) by

P(A i , B j ) ≈ Vol(A i ) + Vol(B j ) Vol(A) + Vol(B)
in the case of AABBs, where the pair (A, B) are the parents and are known to overlap. Thus, the probability of an overlap can be minimized by minimizing Vol(A i ) + Vol(B j ). The same strategy seems reasonable for other BV types.

Volino and Magnenat-Thalmann [VMT94, VMT95] as well as Provot [START_REF] Provot | Collision and Self-Collision Handling in Cloth Model Dedicated to Design Garments[END_REF] use a fairly different approach for deformable objects. In this method, the hierarchy is strictly oriented on the mesh topology of the object, assuming that topology does not change during the simulation. [VMT94, VMT95] use a region-merge algorithm to build the hierarchy bottom-up, while [START_REF] Provot | Collision and Self-Collision Handling in Cloth Model Dedicated to Design Garments[END_REF] uses a top-down algorithm that recursively divides the object in zones imbricating each other. These approaches have the advantage, that they avoid clustering of faces in the hierarchy that are very close in the initial state, although they are not close at all based on the connectivity. This connectivity-based approach also yields advantages in speeding-up self-collision detection as described in subsection 2.4.

Another crucial point is the arity of the BVH, i.e., the number of children per node. For rigid objects, binary trees are commonly chosen. In contrast, 4-ary trees or 8-ary trees have shown better performance for deformable objects [START_REF] Larsson | Collision detection for continuously deforming bodies[END_REF][START_REF] Mezger | Hierarchical Techniques in Collision Detection for Cloth Animation[END_REF]. This is mainly due to the fact that fewer nodes need to be updated and the total update costs are lower. Additionally, the recursion depth during overlap tests is lower and therefore the memory requirements on the stack are lower. Fig. 6 shows the reduction of recursion depth for detecting two overlapping leaves by equivalent 4-ary trees instead of binary trees.

c The Eurographics Association and Blackwell Publishing 2005.

Teschner et al. / Collision Detection for Deformable Objects

Hierarchy Update

In contrast to hierarchies for rigid objects, hierarchies for deformable objects need to be updated in each time step. Principally, there are two possibilities: updating or rebuilding. Refitting is much faster than rebuilding, but for large deformations, the BVs usually are less tight and have larger overlap volumes. Nevertheless, van den Bergen [vdB97] has found that refitting is about ten times faster compared to a complete rebuild of an AABB hierarchy. Further, as long as the topology of the object is conserved there is no significant performance loss in the actual collision query compared to rebuilding.

General updating

Different strategies have been proposed not only for building a hierarchy but also for the hierarchy update. Larsson and Akenine-Möller [LAM01] compared bottom-up and topdown strategies. They found that if in a collision detection process many deep nodes are reached the bottom-up strategy performs better, while if only some deep nodes are reached the top-down approach is faster. Therefore they proposed a hybrid method, that updates the top half of the tree bottomup and only if non-updated nodes are reached these are updated top-down. Using this method they reduce the number of unnecessarily updated nodes with the drawback of higher memory requirement because they have to store the leaf information about vertices or faces also in the internal nodes.

Other approaches have been proposed by Mezger et al. [START_REF] Mezger | Hierarchical Techniques in Collision Detection for Cloth Animation[END_REF] to further accelerate the hierarchy update by omitting or simplifying the update process for several time steps.

For this purpose the bounding volumes can generally be inflated by a certain distance. Then the hierarchy update is not needed as long as the enclosed primitives did not move farther than that distance.

Refitting for Bounded Deformations

If the deformations of the object are superpositions of displacement fields, then the update can be performed at very little extra costs [START_REF] James | BD-Tree: Outputsensitive collision detection for reduced deformable models[END_REF].

In that case, the deformed geometry is given by p ′ = p + Uq, where p ′ , p are the deformed and undeformed geometry, respectively, U contains the displacement fields, and q the reduced deformation vector.

If spheres, represented by center c, and radius r, are used as BVs, then conservative BVs for the deformed geometry can be computed by c ′ = c + Ūq and r ′ = r + R T q abs , where Ū is an average of the displacement fields, R T is a radius increment derived from the displacement fields, and q abs contains the Euclidean norms of q.

This method can be applied to AABBs and DOPs. It can also be used with OBBs, although the computational effort might be larger.

The advantage of this method is that the computation of the BVs for the deformed tree can be performed during the actual traversal for the collision detection. Another nice property of this method is that the BVs tend to be not larger than those obtained by refitting the hierarchy bottomup. However, the deformations must have the special form shown above. This is, for instance, true for compressed animations [START_REF] Müller | Representing animations by principal components[END_REF], pose space deformations [START_REF] Lewis | Pose space deformations: A unified approach to shape interpolation a nd skeleton-driven deformation[END_REF], or modal deformations [START_REF] James | DyRT: dynamic response textures for real time deformation simulation with graphics hardware[END_REF].

Refitting for Morphing Objects

An important case of deformation occurs in animation systems, where objects are deformed by morphing or blending. Here, in-between objects are constructed by interpolating between two or more morph targets. Actually, this method is a special case of the one described in Section 2.3.2.

t 1 t 2 t 2 t 2 t 1 t 1

Figure 7: If the deformation is a predefined morph, then a BVH for in-between objects can be constructed by morphing the BVs.

The idea of [START_REF] Larsson | Efficient collision detection for models deformed by morphing[END_REF] is to construct one BVH for one of the morph targets and fit this to the other morph targets, such that corresponding nodes contain exactly the same vertices. With each node of the BVH, all corresponding BVs are c The Eurographics Association and Blackwell Publishing 2005. stored, i.e., one from each morph target (see Fig. 7). During runtime, a BVH can be constructed for the morphed object just by considering the original BVH and interpolating the BVs. Assume, n morph targets O i are given, each with vertices v i j and weight vectors w i . Then, each vertex v j of the morphed object is an affine combination

v j = n ∑ i=1 w i j v i j , with n ∑ i=1 w i j = 1. (1)
Let D i be the n BVs of the corresponding nodes in the BVHs of the O i (i.e., all D i contain the same vertices, albeit at different positions). A DOP is denoted by

D i = (S i 1 , . . . , S i k )
, where S i j = (s j , e j ), s j ≤ e j , is one interval of the DOP. Now, a new DOP D = ( S1 , . . . , Sk ) with S j = ( s j , ē j ) can be interpolated from these n DOPs by

s j = n ∑ i=1 w i s i j , ē j = n ∑ i=1 w i e i j .
(2)

This interpolated DOP D will enclose all the interpolated vertices beneath its node. It is easy to verify that all s j are lower bounds for all v j . This works just the same for AABBs, since AABBs are a special case of DOPs, and a similar approach works for sphere trees.

Overall, we can utilize existing top-down BVH traversal algorithms for collision detection. The only additional work that must be done is the interpolation, i. e., morphing of the BVs, just before they are checked for overlap. The exact positions of the morphed vertices enclosed by a BV are not needed. This deformable collision detection algorithm seems to be faster in practical cases, and its performance depends much less on the polygon count, than the more general method presented in [START_REF] Larsson | Collision detection for continuously deforming bodies[END_REF].

The method has a few drawbacks. One must find a BVH that yields good performance for all in-between models and it works only for morphing schemes which allow only one weight per morph target.

Self-Collision Detection

BVHs can be easily employed to accelerate self-collisions. As already mentioned in Sec. 1, this is particularly important for deformable objects, such as cloth. In general, collisions and self-collisions are performed the same way using BVHs. If several objects are tested for collisions, the respective BVHs are checked against each other. Analogously, self-collisions of an object are detected by testing one BVH against itself.

However, it has to be noted, that BVs of neighboring regions can overlap, even though there are no self-collisions. To eliminate such cases efficiently, different heuristics have been presented. Volino and Magnenat-Thalmann [START_REF] Volino | Efficient Self-Collision Detection on Smoothly Discretized Surface Animations using Geometrical Shape Regularity[END_REF] proposed an exact method to avoid unnecessary selfintersection tests between certain BVs. The idea is based on the fact, that regions with sufficiently low curvature can not self-intersect, assuming they are convex. Therefore, a vector with positive dot product with all face normals of the region is searched. If such a vector exists and the projection of the region onto a plane in direction of the vector does not self-intersect, the region cannot self-intersect. A very similar approach is used by Provot [START_REF] Provot | Collision and Self-Collision Handling in Cloth Model Dedicated to Design Garments[END_REF] who uses normal cones, which are calculated for each convex region. These cones represent a superset of the normal directions. They are built using the hierarchy and updated during the hierarchy update. The apex angle α of the cone represents the curvature, indicating possible intersections if α ≥ π.

Continuous Collision Detection

BVHs are also used to accelerate continuous collision detection, i. e., to detect the exact contact of dynamically simulated objects within two successive time steps. Therefore, BVs do not only cover object primitives at a certain time step. Instead, the volume described by the linear movement of a primitive within two successive time steps is enclosed by the BVs [Hub95, BFA02, RKC02]. In [START_REF] Bridson R | Robust treatment of collisions, contact and friction for cloth animation[END_REF], this technique is employed for cloth simulation. In this scenario, continuous collision detection also prevents self-intersections (see Fig. 8 and9). In multi-body systems, the number of collisions at a single time step can increase significantly, causing simple sign checking methods to fail. Therefore, [START_REF] Grabner | Reliable multibody collison detection using rungekutta integration polynomials[END_REF] developed a reliable method that adjusts the step size of the integration by including the event functions in the system of differential equations, and by robust root detection.

Finding the first point of contact basically corresponds to finding roots of polynomials that describe the distance between the basic geometric entities, i. e., all face/vertex and all edge/edge pairs [START_REF] Eberly | 3D Game Engine Design : A Practical Approach to Real-Time Computer Graphics[END_REF]. These polynomials are easier to process if the motion of objects is a screw motion. Thus, [START_REF] Rossignac | Collision prediction for polyhedra under screw motions[END_REF][START_REF] Redon | Fast continuous collision detection between rigid bodies[END_REF] approximate the general motion by a sequence of screw motions.

In order to quickly eliminate possible collisions of groups of polygons that are part of deformable objects, [START_REF] Mezger | Hierarchical Techniques in Collision Detection for Cloth Animation[END_REF] construct so-called velocity cones throughout their BVHs. A simple way to augment traditional, static BVH traversals is proposed in [START_REF] Eckstein | Dynamic collision detection in virtual reality applications[END_REF]. During the traversals, for each node a new BV is computed that encloses the static BV of the node at times t 0 and t 1 (and possibly several t i in-between). Other approaches utilize quaternion calculus to formulate the equations of motion [START_REF] Schömer | Exact geometric collision detection[END_REF][START_REF] Canny | Collision detection for moving polyhedra[END_REF].

Conclusion

In BVH approaches, the efficiency of the basic BV has to be investigated very carefully. This is due to the fact, that deforming objects require frequent updates of the hierarchy. So far, it has been shown that AABBs should be preferred to other BVs, such as OBBs. Although OBBs approximate objects tighter than AABBs, AABBs can be updated or refit very efficiently. Additionally, 4-ary or 8-ary trees have shown a better overall performance compared to binary trees.

Although deformable modeling environments require frequent updates of BVHs, BVHs are nevertheless well-suited for animations or interactive applications, since updating or refitting of these hierarchies can be done very efficiently. If the deformations are known in advance, this can even be done in an output-sensitive manner. Furthermore, BVHs can be employed to detect self-collisions while applying additional heuristics to accelerate this process. Also, BVHs work with triangles and tetrahedrons as object primitives, which allows for a more sophisticated collision response compared to a pure vertex-based response.

Stochastic Methods

Recently, "inexact" methods have become a focus in collision detection research. This idea is motivated by several observations. First, polygonal models are just an approximation of the true geometry. Second, the perceived quality of most interactive 3D applications does not depend on exact simulation, but rather on real-time response to collisions [START_REF] Uno | The sensitivity of presence to collision response[END_REF]. At the same time, humans cannot distinguish between physically-correct and physically-plausible behavior of objects [START_REF] Barzel R | Plausible motion simulation for computer graphics animation[END_REF]. Therefore, it can be tolerated to improve the performance of collision detection, while degrading its precision.

Figure 10: Illustration of stochastic collision detection between two volumetric bodies: Pairs of features (depicted by lines) across different resolutions (different colored points) being tracked as the objects approach each other.

In the following, two of these "inexact" methods will be presented in detail. The two methods use probabilistic principles in fairly different ways. The first one uses probabilistic methods to estimate the possibility of a collision with respect to a given quality criterion. With this method the "quality" of the collision detection can be specified by the user directly, thus ensuring more control. The second method initially "guesses" colliding pairs by a stochastic sampling within the colliding bodies. The exact colliding regions are then narrowed down by using this principle in conjunction with temporal and spatial coherence. In this case, the user has a more indirect control over the quality of collision detection.

An Average-Case Approach

Conceptually, the main idea of this algorithm is to consider sets of polygons at inner nodes of the BVH. During traversal, pairs of these sets of polygons are checked [START_REF] Klein | Adb-trees: Controlling the error of time-critical collision detection[END_REF]. However, pairs of polygons are never explicitly checked. Therefore, there is no polygon information stored with the nodes of the BVH. Instead, the probability of the existence of a pair of intersecting polygons is estimated. This has two advantages. First, the algorithm is truly timecritical. The application can control the runtime of the algorithm by specifying the desired quality of the collision detection. Second, the probabilities can guide the algorithm to those parts of the BV hierarchies that allow for faster convergence of the estimate.

In contrast to traditional traversal schemes, the algorithm is guided by the probability that a pair of BVs contains intersecting polygons. Omitting the details, the algorithm works as follows:

traverse(A, B) while q is not empty do A, B ← q.pop for all children A i and

B j do p ← Pr(A i , B j ) if Pr(A i , B j ) is large enough then return "collision" else if Pr(A i , B j ) > 0 then q.insert(A i , B j , Pr(A i , B j )) end if end for end while
where q is a priority queue, which is initialized with the top BV pair (A, B). Pr(A i , B j ) denotes the probability of a collision between polygons under nodes A i and B j . Note, that it is not possible to compute Pr(A, B) exactly. Instead, it is estimated from the distribution of the polygons inside a grid, and combinatorial reasoning about the probability that a cell contains "many" polygons from both A and B (see Fig. 11).

Note, that this approach is a general framework that can be applied to many BVHs utilizing different types of BVs. The BVH has to be augmented by a single number: the number of cells in each node that contain many polygons. In addition, if one never wants to perform exact collision detection, then the polygons do not even have to be stored in the BVH.

Stochastic Collision Detection Based on Randomly Selected Primitives

A naïve approach to stochastic collision detection consists of selecting random pairs of colliding features as an initial

A B

Figure 11: Conceptually, the idea of the average-case approach is to determine the number of cells of a grid covering A ∩ B that contain "many" polygons from both A and B.

guess of the potential intersecting regions. This method can be further augmented by ensuring that the sampling covers features from the entire body and that the features are already close enough. However, this is not sufficient to identify the colliding regions when the object moves or deforms.

The solution is to consider temporal coherence proposed by Lin and Canny [START_REF] Lin | Efficient Collision Detection for Animation[END_REF]. If a pair of features is close enough at a time step, it may still be interesting in the next one. This allows to track colliding regions over subsequent time steps as the objects are animated. Further, these pairs are made to converge to the local minima of the distance to efficiently identify collisions.

In addition, spatial coherence is also applied by keeping track of this local minimum over the neighborhood features. Each pair is locally updated at a time step, in order to track the local distance variations when the objects move or deform (see Fig. 12 (b)). These pairs are called active pairs. When two initially distant active pairs converge to the same local minimum, one of them is suppressed. A pair is also suppressed if the associated distance is larger than a given threshold. The above process tracks the existing regions of interest but does not detect new ones. This is a serious problem for non-convex object deformations where even a small motion can significantly alter the closest distance location.

Therefore, in addition to the update of the currently active pairs, n additional random pairs are added to the list of active pairs at a time step. The update of these extra active pairs is again similar to the update of the existing ones. The complexity of the detection process thus linearly varies with the user-defined parameter n. At each time step, collision detection consists of selecting among the currently active pairs, the pairs which are closer than the sum of their radii. Reaction forces can then be generated between them.

The general, the stochastic approach described above can be applied to several collision detection problems which are explained in Sec. 3.2.1 and Sec. 3.2.2. c The Eurographics Association and Blackwell Publishing 2005.

Volumetric Elastic Bodies

Multiresolution methods have proven to be efficient for the real-time simulation of deformable bodies. In such an environment, Debunne and Guy [START_REF] Debunne | Monte-Carlo collision detection[END_REF] applied a multiresolution, physically-based animation model [START_REF] Debunne | Dynamic real-time deformations using space and time adaptive sampling[END_REF] in conjunction with the aforementioned approach to help accelerate collision detection. Here, they start by tracking pairs of features at a coarser level when they are initially far apart and then refine to a finer level as they move closer. The switching between resolutions is done by evaluating a distance metric between pairs and applying spatial coherence between features at different resolutions. Fig. 10 illustrates this concept. If objects approach each other, the collision regions are tracked at different resolutions before it converges to the exact vertices of collisions.

Thin Self-colliding Structures

As already mentioned, highly flexible structures, such as strands and cloth, have the possibility of self-colliding at multiple places (see Fig. 12 (a)). The general stochastic collision approach was adapted in [RGF * 04] to detect collisions and self-collisions for such objects. The proposed method utilizes two optimizations. First, a two-step update method for computing the local distance minima for surface structures is used. This reduces the complexity from O(nm) to O(n + m), where n and m are the numbers of neighboring primitives. Second, in order to provide a robust collision response, collisions are propagated from the collision point. When a collision occurs, a recursive algorithm searches the neighborhood for possible collisions and a unique response can be applied.

Conclusion

Though the two discussed stochastic methods are principally different, they both have common characteristics. The most important one is the possibility to balance the quality of the collision detection or the collision ratio against computation time. It has been shown that stochastic approaches are applicable for real-time applications. However, it has to be considered, that no exact or physically-correct simulation is possible.

The first approach works on BVHs and can therefore extend many of the methods described in section 2. The second one is independent of any hierarchy and is directly employed to pairs of primitives which simplifies the collision response scheme.

Distance Fields

Distance fields specify the minimum distance to a closed surface for all points in the field. The distance may be signed in order to distinguish between inside and outside. Representing a closed surface by a distance field is advantageous because there are no restrictions about topology. Further, the evaluation of distances and normals needed for collision detection and response is extremely fast and independent of the geometric complexity of the object. representations is still a topic and some techniques are presented in the following section. In section 4.2, we discuss how distance fields can be used for collision detection between deformable objects. We also show, that distance fields are particularly suitable for representing rigid objects in an environment. Then, collision detection between deformable and rigid objects can be carried out very efficiently without updating the distance fields.

Distance Field Generation

Different data structures for representing distance fields have been proposed in the literature: Uniform 3D grids, octrees and BSP-trees. When using uniform grids, distance values are computed for each grid point and intermediate values are reconstructed by trilinear interpolation. This data structure is easy to implement and distance queries can be computed in constant time. The later is important for real-time applications. Also, smooth objects can be represented quite well since a uniform grid provides C 0 continuity between different cells and the trilinear interpolation reconstructs curved surfaces inside each cell with a small approximation error. Most collision response schemes also need normals which can be computed by normalizing the analytic gradient of the trilinear interpolation [START_REF] Frisken | Adaptively sampled distance fields: A general representation of shape for computer graphics[END_REF]. The drawbacks of uniform grids are the huge memory requirements and the limited resolution when representing objects with sharp features.

In order to overcome these problems, [START_REF] Frisken | Adaptively sampled distance fields: A general representation of shape for computer graphics[END_REF] proposed to use adaptively sampled distance fields (ADFs). The data is stored in a hierarchy which is able to increase the sampling rate in regions of fine detail. Although various spatial data structures are suitable in general, ADFs are usually stored in an octree. During construction of an ADF, each cell is subdivided as long as the result of the trilinear interpolation does not properly approximate the original distance field. This subdivision rule differs from standard 3-color octrees where each cell, which is not completely inside or outside, is subdivided. This subdivision stops when a maximum tree depth is reached. Compared to uniform grids ADFs provide a good compression ratio. For collision detection purposes, special care has to be taken in order to guarantee continuity between different levels of the tree [START_REF] Bridson R | Simulation of clothing with folds and wrinkles[END_REF]. Whenever a cell is adjacent to a coarser cell, its corner values have to be changed to match those of the interpolated values at the coarser cell [START_REF] Westermann R | Real-time exploration of regular volume data by adaptive reconstruction of isosurfaces[END_REF].

When using a BSP-tree, memory consumption can be reduced even further [START_REF] Wu | Piecewise linear approximation of signed distance fields[END_REF]. This is achieved by using a piecewise linear approximation of the distance field, which is not necessarily continuous. In [START_REF] Wu | Piecewise linear approximation of signed distance fields[END_REF], several algorithms for selecting appropriate splitting planes of the tree are provided and it is shown that the BSP representation is very compact. Unfortunately, the construction of the BSP-tree is computationally expensive. Another problem may arise from discontinuities between cells since these cracks are not as easily resolved as for ADFs.

In most applications, the surface of a collision object is given as a triangular mesh, possibly deforming over time. For collision detection, it is sufficient to compute distance values only in a small band near the surface. Clearly, this reduces the computational effort considerably. Essentially, there are three different approaches for the efficient computation of a distance field: Methods based on Voronoi diagrams, propagation methods and methods using trees. When distances of each grid point are evaluated independently, a tree data structure can be used to cull away distant triangles to speed up computations. An early work of [START_REF] Payne | Distance field manipulation of surface models[END_REF] applies BVHs. Later, octrees have been used [START_REF] Jones | Using distance fields for object representation and rendering[END_REF]. However, these approaches have shown not to be competitive compared to other methods since the computing times are in the order of minutes.

Propagation methods start with a narrow band of distances computed near the triangular surface. This initial information is distributed over the whole volume. Fast marching methods [START_REF] Sethian | A fast marching level set method for monotonically advancing fronts[END_REF] and distance transforms are two examples of propagation methods. In [START_REF] Jones | Using distance fields for object representation and rendering[END_REF], different types of distance transforms are compared. However, fast distance transforms are not very accurate.

In [HKL * 99], the usage of graphics hardware for computing generalized 2D and 3D Voronoi diagrams is proposed. This technique builds distance meshes for each Voronoi site. In 2D, a simple rendering of these meshes for all sites yields an unsigned distance field in the depth buffer of the graphics hardware. In 3D, the distance meshes are quite complex and the algorithm has to proceed slice by slice. Thus, a huge number of triangles has to be rendered, slowing down this method considerably.

An algorithm with linear complexity is described in [START_REF] Breen | 3d metamorphosis between different types of geometric models[END_REF]. This method utilizes the Voronoi diagram for faces, edges and vertices of the mesh. Each Voronoi region is represented by a bounding polyhedron. The polyhedrons are cut into slices along grid rows and the resulting polygons are scan-converted in order to determine which grid points lie inside. The distance for inner grid points is easily computed as the distance to the Voronoi site. The orientation of the triangle mesh provides the correct sign for each region. If a grid point is scan-converted several times, the smallest distance is considered. Recently, [START_REF] Sigg | Signed distance transform using graphics hardware[END_REF] improved on this algorithm by using graphics hardware to scan-convert the polyhedrons. Further, the authors show how to replace polyhedrons for faces, edges and vertices by constructing only one polyhedron per face. This reduces the number of polyhedra which have to be scan-converted by a factor of three. The authors demonstrated, that it is possible to compute the distance field for the Stanford Bunny, consisting of 69K triangles, within 3.7 seconds. The grid resolution was 256 3 and the band width was 10% of the model extent.

In some cases, triangular meshes are stored without any adjacency information. Since these are needed for computing Voronoi regions, [START_REF] Fuhrmann | Distance fields for rapid collision detection in physically based modeling[END_REF] propose an algorithm which computes distance values independently for each triangle.

Except for some sign errors, due to the lack of adjacency information, this technique is able to compute distance fields for finely tessellated objects very fast. It is shown that it takes only about 14 seconds to compute the distance field for the Happy Buddha model (1.1M triangles) on a 167 × 167 × 400 grid.

Distance Field Collision Detection

Collision detection between different objects is carried out point-wise when using distance fields. If both deformable objects are volumetric, vertices on the surface of one object are compared against the distance field of the other object and vice versa. A collision has occurred if D(p) < 0. When animating deformable surfaces over more or less rigid bodies, distance fields are particularly suitable. In this case, only the vertices of the deformable surface have to be tested for collisions. In order to avoid artifacts during collision response, it is necessary to offset the vertices from the zero isosurface by a predefined ε (see Fig. 14). In this case, a vertex is marked as collided when D(p) < ε. This ε-offset depends on the sampling density of the deformable objects. Note, that distance fields do not only report collisions, but also compute the penetration depth at the same. This is required for a proper collision response algorithm. Deformed distance fields have been used to estimate the penetration depth of elastic polyhedral objects [START_REF] Fisher | Deformed distance fields for simulation of non-penetrating flexible bodies[END_REF]. In this method, an internal distance field is created by a fast marching level set method, propagating distance information only inside the objects. In order to take deformations of the objects into account, the distance fields are updated before each time step. The actual collision detection is carried out by a hierarchical method. During collision response the distance fields are deformed due to the geometry and used for an approximation of the penetration depth. This method is able to handle self-collisions and collisions. The approach is well-suited for volumetric objects, because thin objects like cloth are not well represented by internal distance fields. Although the distance field is only partially updated in deforming regions of the object, experiments show that this method is not intended for real-time applications.

[BMF03] suggests the use of ADFs for detecting collisions between clothing and animated characters. Since the surface deforms over time due to skin and muscle simulation, the authors propose to pre-calculate a distance field at each time step using a fast marching method [START_REF] Sethian | A fast marching level set method for monotonically advancing fronts[END_REF]. This can be used for multiple cloth simulations. In order to handle cloth with several intersecting character geometries, a distance field for each body part is created. Thus, cloth vertices, which are inside of two or more distance fields, can be detected and handled properly. For a more thorough analysis of pinched clothing see [START_REF] Baraff | Untangling cloth[END_REF]. No timings were given in the paper, but the necessity of pre-calculation of the distance fields indicates that the proposed approach is tailored for film making.

In [START_REF] Fuhrmann | Distance fields for rapid collision detection in physically based modeling[END_REF], the problem of rapid distance computation between rigid and deformable objects is addressed. Rigid objects are represented by distance fields, which are stored in a uniform grid to maximize query performance. Vertices of a deformable object, which penetrate an object, are quickly determined by evaluating the distance field. Additionally, the center of each edge in the deforming mesh is tested in order to improve the precision of collision detection. Since updates of the distance field were considered too costly, the authors also propose to combine multiple rigid bodies for animation-similar to the method of [START_REF] Bridson R | Simulation of clothing with folds and wrinkles[END_REF]. Experiments suggest, that this technique is able to animate cloth at interactive rates (see Fig. 15). Collisions with complex nonconvex objects are resolved accurately. The self-collisions of the cloth are detected by using a bounding volume hierarchy.

Updates of a distance field are a common bottleneck of all methods described above. To accelerate theses updates, [START_REF] Vassilev | Fast Cloth Animation on Walking Avatars[END_REF] proposed an image-based approach for computing distance values. Rendering hardware is used for constructing two depth and normal maps of the object, one map for the back of the object and one map for its front. These maps are used for distance calculations and collision response. This algorithm is restricted to convex shapes or appropriate mapping directions in the case of animated characters. In [START_REF] Hoff | Fast and simple 2d geometric proximity queries using graphics hardware[END_REF], another image-based approach is proposed that uses the technique described in [HKL * 99] to create a 2D distance field using graphics hardware. This 2D distance field is used for collision response. The authors report interactive frame rates for non-convex rigid bodies and also for deformable bodies. The method is applicable to 2D problems.

Conclusion

Distance fields have been employed to detect collisions and even self-collisions in non-interactive applications. Although efficient algorithms for computing distance fields have been proposed recently, this generation is still not fast enough for interactive applications, where distance fields have to be updated during run-time due to deforming geometry. However, distance fields provide a highly robust collision detection, since they divide space strictly into inside and outside. For interactive applications, distance fields can be used to represent all rigid objects contained within the environment. Since distance fields yield not only the penetration depth but also normals needed for collision response at interactive rates, collision detection between deformable objects and the rigid objects is carried out very efficiently. In order to decrease storage requirements or generation time, it is possibly to reduce the resolution of the distance field, which results in lowered accuracy. Thus, distance field approaches can balance performance and accuracy.

Spatial Subdivision

Early spatial subdivision approaches have been proposed for neighborhood queries, e. g. in molecular dynamics. In [START_REF] Levinthal | Molecular model-building by computer[END_REF], the computation of molecular atom interaction is accelerated with a neighborhood search based on a uniform 3D grid. Another related approach is presented in [START_REF] Rabin | Probabilistic algorithms[END_REF], where a hash map is used to represent the 3D grid.

There exist various approaches that propose spatial subdivision for collision detection of rigid objects. These algorithms employ uniform grids [START_REF] Turk | Interactive collision detection for molecular graphics[END_REF], [START_REF] Ganovelli | Buckettree: Improving collision detection between deformable objects[END_REF], [START_REF] Zhang | Collision detection for clothed human animation[END_REF], octrees [START_REF] Bandi | An adaptive spatial subdivision of the object space for fast collision detection of animating rigid bodies[END_REF] or BSP trees [START_REF] Melax | Dynamic plane shifting bsp traversal[END_REF]. In [START_REF] Turk | Interactive collision detection for molecular graphics[END_REF], spatial hashing has been applied to collision detection for the first time. In [START_REF] Lin | H-COLLIDE: A Framework for Fast and Accurate Collision Detection for Haptic Interaction[END_REF], a hybrid approach has been presented which combines spatial and object subdivision. In [START_REF] Mirtich | Efficient algorithms for twophase collision detection[END_REF], a hierarchical spatial hashing approach is presented as part of a robot motion planning algorithm, which is restricted to rigid bodies.

In general, BSP trees, octrees or kd-trees are objectdependent. In contrast, spatial subdivision with a uniform grid is independent of the object which makes it particularly interesting for deformable objects.

In [THM * 03], spatial hashing with a uniform grid is employed for the detection of collisions and self-collisions for deformable tetrahedral meshes. Tetrahedral meshes are commonly used in medical simulations, but can also be employed in any physically-based environment for deformable objects that are based on FEM, mass-spring, or similar meshbased approaches (see Fig. 16). This algorithm implicitly subdivides R 3 into small grid cells. Instead of using complex 3D data structures, such as octrees or BSP trees, the approach employs a hash function to map 3D grid cells to a hash table. This is not only memory efficient, but also provides flexibility, since this allows for handling potentially infinite regular spatial grids with a non-uniform or sparse distribution of object primitives. Information about the global bounding box of the environment is not required and 3D data structures are avoided.

The algorithm, presented in [THM * 03], proceeds in three stages. In a first pass, the information on the implicit 3D grid cells of all vertices are mapped to the hash table. The second pass considers all tetrahedrons of the environment. It maps information on all grid cells touched by a tetrahedron to the hash table. Now, the third stage checks vertices and tetrahedrons within a hash table entry for intersections. If a vertex penetrates a tetrahedron, a collision is detected. If both, the vertex and the tetrahedron belong to the same object, a selfintersection is detected.

In order to investigate the performance of the spatial hashing approach, it has been combined with a deformable modeling framework [START_REF] Teschner | A versatile and robust model for geometrically complex deformable solids[END_REF] with integrated deformable collision response [HTK * 04]. Using this environment, experiments with various setups of interacting deformable objects have been performed. These experiments indicate, that the detection of all collisions and self-collisions for dynamically deforming objects can be performed at 15 Hz with up to 20k tetrahedrons and 6k vertices on a standard PC. The performance is independent of the number of objects. It only depends on the number of object primitives. Therefore, the approach can also be applied to n-body environments. The performance varies slightly during simulations due to the changing number of hash collisions and a varying distribution of hash table elements.

The performance of the spatial hashing approach is dependent on various parameters, such as the shape of a grid cell, the size of a grid cell, the hash function, and the size c The Eurographics Association and Blackwell Publishing 2005. of the hash table. It is obvious, that a smaller hash table increases the chance of hash collisions which degrades the performance. The hash function affects the number of hash collisions, too. While [THM * 03] do not consider various grid cell shapes, the authors discuss the optimal grid cell size. Experiments suggest that the optimal cell size is about the same as that of the bounding box for a single object primitive, which confirms a similar result that has been presented in [START_REF] Bentley | The complexity of fixed-radius near neighbor searching[END_REF].

Conclusion

Spatial subdivision is a simple and fast technique to accelerate collision detection in case of moving and deforming objects. Spatial subdivision can be used to detect collisions and self-collisions. Algorithms based on spatial subdivision are independent of topology changes of objects. They are not restricted to triangles as basic object primitive, but also work with other object primitives if an appropriate intersection test is implemented.

The main difficulty in spatial subdivision is the choice of the data structure that is used to represent the 3D space. This data structure has to be flexible and efficient with respect to computational time and memory. In [THM * 03], a hash table is used which has shown to be very efficient in physically-based simulation environments with dynamically changing spatial distributions of object primitives.

Image-Space Techniques

Recently, several image-space techniques have been proposed for collision detection [START_REF] Myszkowski | Fast collision detection between complex solids using rasterizing graphics hardware[END_REF], [START_REF] Baciu | RECODE: an image-based collision detection algorithm[END_REF], [START_REF] Baciu | Hardwareassisted self-collision for deformable surfaces[END_REF], [START_REF] Hoff | Fast and simple 2d geometric proximity queries using graphics hardware[END_REF], [START_REF] Otaduy | MANOCHA c The Eurographics Association and[END_REF], [START_REF] Heidelberger | Real-time volumetric intersections of deforming objects[END_REF], [START_REF] Knott | Cinder: Collision and interference detection in real-time using graphics hardware[END_REF], [START_REF] Govindaraju | Cullide: Interactive collision detection between complex models in large environments using graphics hardware[END_REF]. These approaches commonly process projections of objects to accelerate collision queries. Since they do not require any pre-processing , they are especially appropriate for environments with dynamically deforming objects. Furthermore, image-space techniques can commonly be implemented using graphics hardware.

An early approach to image-space collision detection of convex objects has been outlined in [START_REF] Shinya | Interference detection through rasterization[END_REF]. In this method, the two depth layers of convex objects are rendered into two depth buffers. Now, the interval from the smaller depth value to the larger depth value at each pixel approximately represents the object and is efficiently used for interference checking. A similar approach has been presented in [START_REF] Baciu | RECODE: an image-based collision detection algorithm[END_REF]. Both methods are restricted to convex objects, do not consider self-collisions, and have not explicitly been applied to deforming objects.

In [START_REF] Myszkowski | Fast collision detection between complex solids using rasterizing graphics hardware[END_REF], an image-space technique is presented which detects collisions for arbitrarily-shaped objects. In contrast to [START_REF] Shinya | Interference detection through rasterization[END_REF] and [START_REF] Baciu | RECODE: an image-based collision detection algorithm[END_REF], this approach can also process concave objects. However, the maximum depth complexity is still limited. Additionally, object primitives have to be pre-sorted. Due to the required pre-processing, this method cannot efficiently work with deforming objects. Self-collisions are not detected.

A first application of image-space collision detection to dynamic cloth simulation has been presented in [START_REF] Vassilev | Fast Cloth Animation on Walking Avatars[END_REF]. In this approach, an avatar is rendered from a front and a back view to generate an approximate representation of its volume. This volume is used to detect penetrating cloth particles. A first image-space approach to collision detection in medical applications is presented in [START_REF] Lombardo | Real-time Collision Detection for Virtual Surgery[END_REF], where intersections of a surgical tool with deformable tissue are detected by rendering the interior of the tool.

In [START_REF] Hoff | Fast and simple 2d geometric proximity queries using graphics hardware[END_REF], an image-space method is not only employed for collision detection, but also for proximity tests. This method is restricted to 2D objects. In [START_REF] Otaduy | MANOCHA c The Eurographics Association and[END_REF] and [START_REF] Kim | Closest point query among the union of convex polytopes using rasterization hardware[END_REF], closest-point queries are performed using bounding-volume hierarchies along with a multipassrendering approach. In [START_REF] Knott | Cinder: Collision and interference detection in real-time using graphics hardware[END_REF], edge intersections with surfaces can be detected in multi-body environments. This approach is very efficient. However, it is not robust in case of occluded edges. In [START_REF] Govindaraju | Cullide: Interactive collision detection between complex models in large environments using graphics hardware[END_REF], several image-space methods are combined for object and sub-object pruning in collision detection. The approach can handle objects with changing topology. The setup is comparatively complex and selfcollisions are not considered. In [START_REF] Heidelberger | Real-time volumetric intersections of deforming objects[END_REF], an image-space technique is used for collision detection of arbitrarily-shaped, deformable objects. This approach computes a Layered Depth Image LDI [START_REF] Shade | The Eurographics Association and[END_REF] for an object to approximately represent its volume. This approach is similar to [START_REF] Shinya | Interference detection through rasterization[END_REF], but not restricted to convex objects. a closed surface is required in order to have a defined object volume.

The algorithm presented in [START_REF] Heidelberger | Real-time volumetric intersections of deforming objects[END_REF] proceeds in three stages. First, the intersection of axis-aligned bounding boxes of pairs of objects is calculated. If an intersection is nonempty, a second stage computes an LDI representation of each object within the bounding-box intersection. Finally, two volumetric collision queries can be applied. The first query detects intersecting volumes of two objects, while the second query detects vertices or other object primitives that penetrate another object. Self-collisions cannot be found. Fig. 19 illustrates the three stages of the algorithm.

In [START_REF] Heidelberger | Detection of collisions and self-collisions using image-space techniques[END_REF], an improved algorithm is presented. In contrast to existing approaches that do not consider selfcollisions, this approach combines the image-space object representation with information on face orientation to overcome this limitation.

LDIs are the basic data structure in many image-space col- lision detection approaches. Therefore, it is very important to optimize their computation and [HTG04] provides a comparison of three different implementations for LDI generation. Two implementations based on graphics hardware and one software solutions have been compared. Results suggest, that graphics hardware accelerates image-space collision detection in geometrically complex environments, while CPUbased implementations provide more flexibility and better performance in case of small environments.

In Fig. 17, collisions and self-collisions are computed using a software implementation. Computing times are 8-11 ms using a standard PC. In this environment with low geometric complexity, a CPU-based implementation for LDI generation is more efficient compared to a GPU-based implementation. In contrast, Fig. 18 illustrates an environwith 500k faces and 100k particles. In this case, the GPU-based implementation for detecting penetrating particles outperforms the CPU-based implementation. Thorough comparisons can be found in [START_REF] Heidelberger | Detection of collisions and self-collisions using image-space techniques[END_REF].

Conclusion

In contrast to other collision detection methods, image-space techniques do not require time-consuming pre-processing. This makes them especially appropriate for dynamically deforming objects. They can be used to detect collisions and self-collisions. Image-space techniques usually work with triangulated surfaces. However, they could also be used for other object primitives as long as these primitives can be rendered. Topology changes of objects do not cause any problems.

Since image-space techniques work with discretized representations of objects, they do not provide exact collision information. The accuracy of the collision detection depends on the discretization error. Thus, accuracy and performance can be balanced in a certain range by changing the resolution of the rendering process.

Image-space techniques can be accelerated with graphics hardware. However, due to buffer read-back delays and the limited flexibility of programmable graphics hardware, it is not always guaranteed that implementations on graphics hardware are faster than software solutions in all cases (see [START_REF] Heidelberger | Detection of collisions and self-collisions using image-space techniques[END_REF]). As a rule of thumb, graphics hardware should only be used for geometrically complex environments.

While image-space techniques efficiently detect collisions, they are limited in providing information that can be used for collision response in physically-based simulation environments. In many approaches, further post-processing of the provided result is required to compute or to approximate information such as the penetration depth of colliding objects.

Applications

This section summarizes various applications of deformable collision detection algorithms in cloth modeling and surgery simulation.

Cloth Simulation

For the simulation of cloth, Mezger et al. [START_REF] Mezger | Hierarchical Techniques in Collision Detection for Cloth Animation[END_REF] used a BVH with a bottom-up update of the hierarchy. This approach is used for various applications such as a virtual tryon scenario (see Fig. 20), where a 3D body scan of a real person is virtually dressed with clothing, made of digitalized cloth patterns.

Figure 20: Efficient collision and self-collision detection and handling for cloth objects. Image generated in the context of the Virtual Try-On project (www.virtualtryon.de).

Impressive results for virtual clothing have been presented over the last decade by the MiraLab, where many algorithms for versatile cloth simulations have been developed. These algorithms are used in a wide variety of applications such as textile design software and results are illustrated in awardwinning movies (see Fig. 21 and22). The algorithms enable the user to design cloth in 2D and interactively simulate the interaction of the cloth model with an avatar. It allows a rapid prototyping of cloth without actually producing the garment.

Virtual Liver Surgery

One important task in surgical simulation is the handling of the interaction of a virtual surgical tool and a deformable organ. The collision detection has to be fast enough to allow for an interactive response thus avoiding any undesirable tool-organ interpenetration. Lombardo et al. [START_REF] Lombardo | Real-time Collision Detection for Virtual Surgery[END_REF] has addressed this problem by developing a GPU-based method for collision detection. In this approach, a surgical tool is modeled as an orthographic or perspective viewing volume with clipping planes. Thus, by rendering in feedback mode, the triangles of the organ that are "visible" to this volume are identified as colliding ones. This static static approach is also adapted to detect collisions in case of dynamically moving instruments (Fig. 23). This method can be extended to many cases of a deformable object colliding with a rigid one whose shape can be approximated with an OpenGL viewing volume.

Collision Detection Between Virtual Organs

Debunne and Guy [START_REF] Debunne | Monte-Carlo collision detection[END_REF] applied their multiresolution technique (Sec. 3.2.1) to the collision detection between two volumetric elastic organs manipulated by a rigid tool in a surgical simulation environment (see Fig. 24). Experiments show favorable performances when compared with OBBs for rigid bodies and with AABBs for deformable bodies.

Virtual Intestinal Surgery

Raghupathi et al. [RGF * 04] adapted the stochastic technique (Sec. 3.2.2) to detect the collisions occurring in the intestinal region when a surgeon manipulates the small intestine. Both, the self-collisions within the intestine and the collisions with a thin membrane (mesentery) were handled in this application. For a model with 300 animated segments and the possibility of a few hundred collisions, the system achieved real-time performances on a standard PC (Fig. 25).

Summary

In this paper, a variety of deformable collision detection approaches has been presented. The discussed approaches are based on bounding volume hierarchies, distance fields, or spatial partitioning. Further, image-space techniques and Approaches based on bounding volume hierarchies have shown to be very efficient. In these methods, the basic bounding volume and the strategy for generating and updating the hierarchy have to be chosen very carefully in order to handle frequent update requests in simulation environments with deformable objects. Stochastic methods are a promising approach to time-critical applications, since they allow for balancing performance and accuracy.

Distance fields are especially appropriate for collision detection between rigid and deformable objects. In this case, pre-computed distance fields do not only detect collisions, but also provide the penetration depth which is essential for a physically-correct collision response. Collision detection based on spatial subdivision has also shown to be very efficient in deformable simulation environments. In these approaches, research is mainly focused on efficient data structures.

Further interesting approaches to deformable collision detection are based on image-space techniques. These algorithms are commonly accelerated with graphics hardware. This makes them especially appropriate for environments with geometrically complex objects and promising results have been presented. While all approaches provide promising solutions to certain aspects in deformable collision detection, there exist no general or optimal approach. Further, it is not the intention of this survey to provide a consistent comparison of all approaches. This is not possible due to several reasons. First, the approaches require different input data, e. g., some approaches only work with closed surface meshes. Second, the approaches provide different collision information. They detect interfering surfaces or estimate penetration depth information. Some algorithms provide accurate collision information, stochastic or image-space methods only compute approximate collision information. Some approaches are optimized for two-body collision tests, other methods, such as spatial subdivision, can handle n-body environments. Further, there exist very specialized solutions that are restricted to certain applications. Therefore, all approaches have their benefits, drawbacks, and restrictions in terms of a specific application.

Figure 1 :

 1 Figure 1: In interactive cloth simulation, efficient deformable collision detection is a key component.

Figure 4 :

 4 Figure 4: A variety of bounding volumes has been proposed for hierarchy-based collision detection.

Figure 5 :

 5 Figure 5: Three levels of an 18-DOP-hierarchy created by splitting the parent DOPs along the longest axis.

Figure 6 :

 6 Figure 6: Recursion using binary trees (a) and 4-ary trees (b).

Figure 8 :

 8 Figure 8: BVHs are employed for continuous collision detection in cloth simulation. Image courtesy of Robert Bridson, UBC.

c

  The Eurographics Association and Blackwell Publishing 2005.Another technique sorts the vertices radially and checks the outer ones first[START_REF]Efficient timeinterrupted and time-continuous collision detection among polyhedral objects in arbitrary motion[END_REF].

Figure 9 :

 9 Figure 9: Continuous collision detection prevents selfintersections in cloth simulation. Image courtesy of Robert Bridson, UBC.

Figure 12 :

 12 Figure 12: (a) Detecting collisions or self-collisions between different folds of thin objects. (b) Tracking the local minima of the distance (shown by the dark dash line) by performing distance computations between neighboring pairs (shown by lighter dash line).

  Besides collision detection, distance fields have a wide range of applications. They have been used for morphing [BMWM01, COSL98], volumetric modeling [FPRJ00, BPK * 02], motion planning [HKL * 99] and recently for the animation of fire [ZWF * 03]. Distance fields are sometimes called distance volumes [BMWM01] or distance functions [BMF03].

Figure 13 :

 13 Figure 13: Happy Buddha and three color-mapped distance field slices. Since the distance field is only valid within a band near the surface, the mapping is faded out at larger distance. Blue maps to close distances, whereas red indicates medium distances.

Figure 14 :

 14 Figure 14: (a) Without offsetting the vertices interpenetration artifacts may occur during collision detection. (b) Introducing an ε-offset solves the problem.

c

  The Eurographics Association and Blackwell Publishing 2005.

Figure 15 :

 15 Figure 15: Interactive animation of cloth in a complex collision environment.

Figure 16 :

 16 Figure 16: Interactive environment with dynamically deforming objects and collision handling. Surface with high geometric complexity and the underlying tetrahedral mesh are shown.

Figure 17 :

 17 Figure 17: Left: Collisions (red) and self-collisions (green) of the hand are detected. Middle: Self-collisions (green) are detected. Right: LDI representation with a resolution of 64x64. Collisions and self-collisions are detected in 8-11 ms using a standard PC.

Figure 18 :

 18 Figure 18: Left: Dragon with 500k faces. Middle: LDI representation with a resolution of 64x64. Right: Particles penetrating the volume of the dragon are detected. In this environment with 500k faces, 100k particles can be tested for penetration in 225 ms using a standard PC.

Figure 19 :

 19 Figure 19: Image-space collision detection. Left: AABB intersection. Middle: LDI generation within the VoI. Right: Computation of the intersection volume.

Figure 21 :

 21 Figure 21: Catwalk scene showing a big variety of clothing presented by virtual characters.

Figure 22 :

 22 Figure 22: Well-known falling ribbon showing the power of collision response algorithms.

Figure 23 :

 23 Figure 23: Illustration of a fast, OpenGL clipping-based collision detection method in virtual liver surgery using a standard PC. (a) Collision detected (the dark patch) at a given time step when the tool is static. (b) Dynamic collision detection by sweeping the viewing volume over subsequent time steps as the tool probes the organ. (c) Dynamic simulation with input from the collision response driving a physically-based model.

Figure 24 :

 24 Figure 24: Collision detection during virtual surgery between liver, prostate (shown as a dark-colored organ) and a rigid tool.

Figure 25 :

 25 Figure 25: Real-time treatment of collisions between intestine and mesentery (shown as a light-colored, thin membrane beneath the intestine) and self-collisions in intestineduring virtual intestinal surgery in a standard PC. The organs are manipulated using a virtual probe (shown as a tiny red sphere) as in a real surgery.

c The Eurographics Association and Blackwell Publishing 2005.