1.0 Scientific Objectives

2.0 Organization of the Action

• 2.1 Cut out automatic grid and interactions
• 2.2 Implicit Models
• 2.3 Volumetric Spring-Masses Models
• 2.4 Hybrid Models Finite Elements/Springs Masses
• 2.5 Finite Elements Models
• 2.6 Visual Realism
• 2.7 Non-linear biomechanical modeling
• 2.8 Numerical analysis and parallel/distributed computation

1.0 Scientific Objectives

In this action, one will carry out a certain number of studies aiming at proposing improvements on several aspects of the modeling of anatomical bodies from three-dimensional medical images, and more particularly on the prototype of simulator developed in the Epidaure project in collaboration with the IRCAD institute. For that, one will call upon the experiment of several teams of the INRIA in various scientific disciplines in order to approach the following directions of search: study of a finer biomechanical modeling of the bodies considered, taking into account of deformations and operations of cutting in real time, interaction between close bodies, made realistic and study of several optimized and parallelized algorithms of numerical resolution.

The medical and biomechanical expertise necessary to the evaluation of the algorithms will be carried out by external collaborators.

The scientific objectives associated with this joined action are multiple and multi-field since they gather work on the medical image processing, numerical calculation, parallel data processing and the synthesis of image. More precisely, the studies considered will relate to the following issues~:

• biomechanical modeling of anatomical structures : a first objective is to validate laws of realistic biomechanical behavior possibly introducing constraints of incompressibility, non-linearity and viscoelasticity. These laws of behavior will be deduced from rheologic curves provided by external collaborators. A second objective is to allow the validation and the improvement of models of real-time deformations.
• cutting of realistic real-time deformable models : an important component of a surgery simulator is to take into account in real time, the action of a scalpel on a finite elements model of a given anatomical structure. The difficulty of modeling consists in obtaining a model authorizing at the same time a realistic and fast deformation with a modification of its topology (cutting).
• interaction between deformable and rigid bodies :the goal is here to model the interaction between a solid body (for example a surgical instrument) and a deformable body (a soft body) but also the interaction between two soft bodies. The modeling of the interaction must take into account the collision detection and the deformations induced.
• visual realism : to obtain a visual realism of simulation, it is necessary to apply surface and volumetric textures on geometrical models. Moreover, these textures must be modified in the course of time in order to take into account the topological changes of the model (cutting) as well as effects physiological (bleeding, coagulation)...
• numerical analysis : this part relates to the improvement of the processing of finite elements models and in particular the effectiveness and robustness of the linear equations resolution. This is crucial in particular for taking into account more complex biomechanical models. With this intention, our attention will go on two classes of modern methods of resolution: domain decomposition methods and multigrid methods.
• parallel and distributed computation : the realism of the surgery simulation is strongly dependent on the real-time reaction to the external events occuring on the anatomical model. Therefore, the adaptation of the software on a parallel/distributed platform will contribute to reduce in a consequent way these response times. This adaptation would relate above all to the most expensive parts: construction of the finite elements model, resolution of the linear systems and adaptation of the volumetric meshes.

2.0 Organization of the action

The studies suggested must be seen as a preparatory phase (the joined action suggested here) to an industrial valorization dedicated to the development of an operational version of the existing simulator. Nevertheless, the developments of new functionalities realized within the framework of these studies will be integrated in order to allow a total evaluation of the approaches considered. The action breaks up into four complementary tasks. Within a same task, one will be able to consider several approaches to carry out a same functionality. These approaches will be compared at the time of the seminars of end of 1st and 2nd year.

2.1 Cutting and interaction between bodies (Projects Epidaure, Imagis, Sharp, Sinus)

The operations of suture and cutting modify the topology of the subjacent grid and do not allow any more the use of precalculations ensuring real-time simulation.

The object of this part of the study is thus, to propose and evaluate various strategies having for goal on the one hand, the modification of grid topology in the course of simulation, and on the other hand, the biomechanical modifications related to the operations of cutting and suture. We propose to study several approaches allowing to carry out the cutting/suture of deformable models. This part requires a close cooperation between the projects Epidaure, Imagis , Sharp and Sinus.

2.2 Implicit Models (Imagis Project)

The studies will relate to the following points~:

• Collisions Detection : with traditional surface modeling (triangulated objects), the detection of a collision between two rigid or deformable bodies is quadratic compared to the number of nodes on their surface. To have an implicit representation for one at least of these bodies would make it possible to carry out this operation of detection in linear time.
• Effective modeling of the neighboring bodies deformation : Implicit surfaces allow an effective approximate modeling of the contacts between deformable objects and the local deformations which result from it. Indeed, instead of simulating the process of deformation being iteratively propagated through the nodes of a grid, they make it possible to compute the local deformation and the forces resulting on surface from contact in only one stage. This implicit model, whose precision may not be well suited for biomechanical modelling of a given organ, should on the other hand allow a particularly effective modeling of the deformable bodies that are in close contact with that organ. Lastly, the implicit surfaces generated by points called "squeletons" are particularly appropriate to the modeling of bodies which can change topology (in particular, that are cut out in several components) under the action of external forces, exerted for example by surgical tools. According to whether the cuttable body to model is structured or not, the "squeletons" can be carried either by a springs-mass representation whose connections could be modified in the course of time, or by a particles system governed by attractive/repulsive forces. This two layers model (skeletons and implicit surface) could be explored within the framework of the simulation of cutting/suture.

2.3 Volumetric Spring-Masses Models (Sharp Project)

The model developed within the Sharp project combines a geometrical representation and a network of viscoelastic spring/masses for dynamics. The geometrical model makes it possible to discretize the anatomical body as a set of tetrahedra. A network of viscoelastic springs is then associated with the tetrahedra in order to determine their dynamic behavior. This approach makes it possible to treat in a standardized way the interaction between solid and deformable bodies. The different related issues are:

• Discretization of volume. We developed homogeneous semi-automatic algorithms for usual volumes.
• The idendification of the parameters of the viscoelastic connections. Currently, we use a genetic algorithm tested for the modeling of the cross ligaments of the knee. We would like to validate this method on other examples.
• Interactions. For the collision detection between deformable objects, therefore potentially concave, we use a method derived from the algorithm of Guilbert from complexity O(n). To determine the forces of contact, we use a viscoelastic model which makes it possible to estimate the contact between deformable objects while following the law of Poisson for the impacts.

Within the framework of this action, we wish to work on the one hand on the identification of parameters necessary to a realistic modeling and on the other hand on the cutting of deformable objects in an interactive manner.

• the modeling of the objects starting from deformable or rigid volumes,
• the computation of the distances between objects in linear time O(n),
• the modeling of contact forces via a nonlinear viscoelastic model.

2.4Hybrid Models Finite Elements/Springs Masses (Epidaure Project)

We propose to improve the already existing simulator within the Epidaure project which is based on precalculated linear elastic finite elements. This model does not authorize change of topology because of the precalculations. The superposition with the model of finite elements of dynamic deformable models such as the mass-springs make it possible to consider a real time modeling of soft tissue cutting. An efficient method for collision detection with deformable models must be developed to simulate the interaction with several instruments.

2.5 Finite Elements Models (Sinus Project)

In a first stage, we propose to study the adaptation of algorithms for surface grid adaptation, previously developed within the Sinus project, in order to take into account the interaction with a cutting tool. A simplified approach could consist in analyzing the intersection between a line is a triangulation of surface; the line defines a separating line and the problem arising is then that of the generation of a new triangulation based on the intersection points between the line and the cut edges. The solution suggested must be computationnally efficient in order to allow a repeated cutting application simulating the effect of in-depth incision . The second stage relates to the modification of the subjacent volumetric mesh either by local mending of meshes or by complete mending of meshes.

2.6 Visual Realism (Imagis Project)

One of the fundamental goals of the simulator is to offer a real time visualization of the virtual operation while ensuring a visual realism as large as possible. For that, an exploratory research carried out within the Imagis project will make it possible to improve the two following problems:

• the modeling of materials and textures for the various involved bodies. The case of very deformable and cuttable bodies makes this problem much more complex: this is the case, for instance, of semi-translucent and very streaked nature meniscus for the arthroscopy of the knee, or the problems of bleeding and coagulation at the time of a cutting for the endoscopy of the liver.
• the modeling of lighting} produced by optical fibre. For that, one will take into account the position and the optical characteristics of the camera. In particular, the deformations related to the large viewing angle will have to be simulated.

2.7 Non-linear biomechanical modeling (Mostra/M3N Projects)

The current model of elastic tissues must be refined by the introduction of more complex biomechanical behavior, for instance by including the influence of vascular structures and certain pathologies (tumors, necrosis...). Moreover, it is important to include in the subjacent biomechanical model, a viscoelastic, and possibly incompressible behavior; this study will be undertaken within the framework of a common contribution of the Mostra and M3N projects on the basis of recent work on the numerical modeling of the contact eye-trepan. The geometrical model of the body as well as the boundary conditions of deformations will be provided by the Epidaure project in collaboration with medical experts and biomechanicians. The results of the calculation of the deformations will be then communicated to the teams working on the models of deformation ( Epidaure, Sharp, Imagis and Sinus) in order to validate the various approaches (as described in the preceding paragraph).

2.8 Numerical analysis and parallel/distributed computation (Sinus Projects and Epidaure)

We want to optimize the current model by integrating the most recent tools in scientific computation. Indeed, the precalculation requires the resolution (for each nonconstrained node of the surface of the body), of a linear system including Lagrange multipliers (for the constrained nodes). Currently, this inversion uses of a non-preconditionned conjugated gradient (CG) that is not very effective which makes the precalculation stage very expensive. The improvement of this component of the simulator will be the subject of the following points (various strategies will be evaluated): introduction of a technique of preconditioning based on the principle of domain decomposition (algorithm of type Schwarz additive) while preserving the current iterative method (GC), study of an algorithm of resolution by sub-domain of type Schur (in this case, we bring back the resolution of a linear system linear to that of the system interface; we will be able in particular to evaluate the methods developed with the projects Mostra et M3N as well as the FETI method developped by C. Farhat and F.-X. Roux at the university of Colorado at Boulder) and study a multigrid method (there are several approaches possible). For each algorithm, the adaptation to parallel/distributed platforms will be taken into account at the first stages of conception. The possible experimental parallel/distributed platforms will be the platforms existing at the INRIA Sophia-Antipolis research center (a cluster of Dec Alpha 500/333 Mhz with a 100 Mbit/s network and a cluster of P6/200 Mhz with a 600 Mbit/s myrinet network).

This research topic will be carried out with a close collaboration between the Epidaure and Sinus projects.