Recherche:Outlook

Theme 1 : Modeling, construction and proofs in geometry

Geometric and topological modeling

Geometric modeling has been the core business of IGG research group for more than 20 years now. During this quadrennial we have relaunched these activities with success and we wish to intensify them during the next four-year by working on the fundamental aspects and applications.

Regarding the fundamental aspects, we want to pursue our research in topology-based geometric modeling, and particularly concerning the non-manifold, multi-resolution, multi-scale, adaptive and hierarchical models. The originality of our approach consists of topological basis in order to formalize these models and highlight their combinatorial properties.

We aim at defining and developing multi-resolution topological models in order to allow a more efficient representation of classical hierarchical structures used for surface simplification (edge collapse, vertex merge). These models need to be further extended to generalize simplification algorithms to non-manifold 2D objects or more generally simplicial complexes. Basile Sauvage, Asociate Professor hired in 2006, will specifically study the simplification of very large surface meshes for visualization related to the Operation 4. Indeed the meshes resulting from scanned objects reconstruction have nowadays a huge size. To visualize them we will work on their simplification and hierarchical organization. In particular it appears proper to combine several criteria (geometry, topology, texture, etc.) for the approximation measure and for the hierarchical organization.

In the scope of multi-resolution volume meshes we would like, from one side, to generalize the topological representations by combinatorial maps that we set up in dimension 2. From the other side, we would like to develop the underlying mathematical models and the associated embedding. Therefore we will take advantage of Basile Sauvage's (AP) integration in IGG and his expertise in wavelet-based multi-resolution models. A direct application would be the simplification and approximation of tetrahedral meshes for the visualization of scientific data.

In the field of collision detection and simulation, many spatial and hierarchical data structures are used for accelerating processing (octrees, kd-trees, hierarchy of bounding boxes or spheres). We wish to explore the usage of our hierarchical models to offer new acceleration structures or new algorithms.

Geometric modeling platform (CGoGN)

The main goal of CGoGN's development will now be to focus on the addition of high-level algorithms for volume models (primitives, meshes, simplification, ...). Also the development of surface patches will be followed by functions of higher level (handling of continuity, evaluation/visualization on the GPU) and the addition of new models.

The unification of CGoGN and the multi-resolution platform is another great yard that we need to consider. Indeed the 2 libraries are currently dissociated but we think that it will be possible to have a unique platform in which the user will be able to check (or uncheck) multi-resolution.

The distribution of CGoGN must be pursued. The established collaborations must obviously be maintained and consolidated and new trails could be explored. More precisely we refer to the integration of CGoGN in CGAL for which contacts have already been initiated with researchers from the project GEOMETRICA at INRIA Sophia Antipolis. Concerning our implication in SOFA, we will continue the development and the integration of combinatorial maps for medical simulation.

A last road of development to be explored is the creation of an abstract layer which will allow developers - who do not have specific knowledge about the underlying topological models - to use our platform.

On the long-term we will also study possible connections between CGoGN and the area of parallelization. Several channels could be explored from the use of multi-core processors to the implementation of highly parallel algorithms on the GPU.

Medical applications of geometric and topological modeling

The heteroclite abundance of representation models for virtual objects coming from various real data sources (voxel images issued from medical imaging or point clouds coming from scanners) and the many uses of these models (visualization or simulation) poses problems, particularly of compatibility or joint usage. We wish to highlight this current problem around the conversion of different representations without loss of information or model genericity at different scales in link with the applications.

Concerning the applications, they are particularly centered on the medical and therapeutic domain with our participation to the multi-labs program IRMC (Imaging and medical and surgical robotics) on themes from the world-class competitiveness pole «Innovations Thérapeutiques» (therapeutic innovations) from Alsace. Within the project ANR VORTISS, we study the possible benefits of topology-based modeling for the development of a platform of surgical operations simulation. The targeted applications are :

• The definition of topological models well-suited to organs modeling : volume models, multi-resolution, taking into account the physiological properties, inter-organs tissues and well-suited to the coupling with physical simulation engines.

• The reconstruction of organs from the human corps from MRI images by being as faithful as possible to the human anatomy. In the process of reconstruction (pass from voxel data to a multi-resolution surface and volume mesh), we will take into account the topological relations such as inclusions, intersections and adjacencies between anatomical structures.

• The reconstruction of vascular data such as blood vessels. We will try to solve the problem linked to the branchings modeling by relying on their topological modeling and our work on subdivision surfaces.

• About virtual navigation in organs and blood vessels, we would like to exploit our work on acceleration structures to allow real-time navigation in the reconstructed organs, and for simulating the interactions with mini-invasive surgery tools.

• For surgery planning, we will work on the description of a high-level user language to describe the art rules and the practitioner's expertise.

Solving of geometric constraints

We follow two research directions :

• The generalization of our approach by taking advantage of the invariance by certain groups of geometric transformations to local-action groups by developing an algebra of elementary transformation groups.

• The re-parameterization, by studying numerical methods well-suited to the problem and links between the re-parameterization and the decomposition of constraint systems exploiting the invariance.

Formalization of the geometry

Many basic questions concerning geometry, and particularly proofs in geometry, underlie the solving of geometric constraints. We looked from a quite pragmatic point of view to the proof of forced incidences in configurations of constraint systems through the usage of Pascal's theorem or calculus of matroid rank (see [2-MS06]). We plan to continue in this direction by re-studying the basics of incidence geometry via the prover Coq. The objectives are multiple, we wish to

• Develop efficient algorithms and that are certified for forced incidence proofs ;
• Build constructions using only incidence constraints (to construct "witnesses" according to the terminology of D. Michelucci) ;
• Extend the geometric framework of incidence to guarantee robustness of the formal geometric solving methods.

Specifications and proofs in geometry

Previous experiences are the premises of an original enterprise of large scale which we intend to conduct at LSIIT. Indeed we form today a coherent group around Coq to approach the geometry, after the hiring of Nicolas Magaud and Julien Narboux, experts in assisted proofs, both having experience in specification and problem solving. Nicolas Magaud worked on the arithmetic and changes of representation, areas that are useful for geoemtric modeling and approximation in computational geometry (INRIA-Sophia, team of Yves Bertot). Julien Narboux formalized the axiomatic of Tarski's geometry, the methods of Gao and Chou's areas and designed a complete system of geoemtric construction support and interactive proof for teaching (LIX, team of Hugo Herbelin, 2006, TU Munich, team of Tobias Nipkow, 2007). We also have in our possession all the topological basis to model and prove the properties of subdivision surfaces.

Until 2011 in the project ANR white Galapagos, and further, our work will increase in several directions mixing specification, conception, proof and certification of algorithms :

Combinatorial topology : investigation of certain properties and proofs of other great results. The prototype was Jordan discrete theorem, that we have re-explored in a more realistic fashion than in the thesis of Puitg, without calling observational point of views, and by cutting a given hyper-map according to a ring of darts. We will work in a more general fashion on orbits of hyper-maps and define higher-level operations, such as Split and Merge, which will free us from certain artifacts linked to inductive specifications. We are thinking of transferring, at this level, al the results on the degree, genus and planarity obtained for low-level operations. These operations will allow us to work more flexibly on computational geometry. Thus we have in mind the definition and manipulation of triangulated surfaces, basis of numerous geometric algorithms.

Geometric modeling : pass in 3D, and even nD, with hyper-maps of dimension n, allowing to subdivide n-dimensional spaces. We will also explore other models of combinatorial nature. Thus, the simplicial sets or complexes are good candidates as a first functional specification was realized during the master's thesis of Jean-Baptiste Surgant in 2002. We also think that we could approach the specification of adaptive or hierarchical subdivisions, which are being heavily studied in the operation 1.

Computational geometry : revision of the notions and basic algorithms, particularly the ones implying subdivisions. After the proof of our incremental algorithm of convex hull with maps in Coq, we will try to formalize and certify the algorithms of Jarvis and Graham to extend the results of Bertot-Pichardie and Fleuriot-Meckle. The classical plan problems that we are interested in include line matching, close to map's co-refinement, for which a correction proof remains to produce. Still with our techniques we obviously particularly target the construction of Delaunay and Voronoi diagrams and their countless variants. Thus we wil specify the triangulations and their conservative operations, particularly the operation Flip which flips to edges and the operation Istar which adds a site in a triangulation and reconstructs it. It is clear that, during these operations, the triangulation is deteriorated in a more general subdivision, which requires the knowledge of how to manipulate such objects. We will then try to specify and formally prove Delaunay triangulation algorithms, which hasn't been done before. The termination assisted proof of this kind of algorithms demands to consider suites of finite sets of hyper-maps produced by a set of darts, which poses many technical problems in Coq. Also we will need to highlight good criteria to ensure the partial correction. Finally, the inherent questions to numerical approximations will not be directly treated but bypassed by using decidable predicates such as the orientation tests of Knuth, based on triplets of points. This kind of study is already largely covered by various french research groups.

Classical geometry and math teaching : axiomatization of classical geometries in Coq, following the work already performed here on the geometry of Hilbert (master's thesis of Christophe Dehlinger), or the work from LIX on the geometry of Tarski (thesis of Julien Narboux). The goal is to offer elaboration and program certification tools for geometric constructions, with various toolboxes. The prototype is the problem of construction by ruler and compass. In this topic we would be very close to certain research works of operation 2.

Theme 2 : Visualization and interaction

Acquisition, analysis, synthesis and texture representation

The digitization of appearance and more generally of a certain material generates tedious manipulations and requires a very accurate control of lighting conditions. The number of images that must be captured is extremely high. Beyond these important manipulations and strong constraints, the generated data load often exceeds very largely the capacities of the graphic cards. This day, there is no satisfactory technique of material acquisition that is both simple - from the manipulation point of view (few shootings with a non-totally controlled lighting)-, compact and correct in the sense of the error coming from the restitution on the display. We then wish to continue along this axis by proposing simple acquisition techniques, multi-scale representation models and data structures well-suited to real-time rendering.

Visualization of scientific volume data and coupling

Concerning the visualization of volume scientific data we would like to concentrate our business on the expressivity of the obtained results, especially by using more sophisticated lighting techniques (e.g. ambient occlusion). We would also like to pursue our collaboration with the ICPS particularly in terms of multi-GPU handling. This work has started with the thesis of Alexandre Ancel.

Interacting with objects

We will continue our research on 3D interaction in link with geometric modeling and medical applications. Our approach will consist in offering multi-modal solutions to enrich and ease interaction with the virtual environment by coupling visual information and haptic information especially by using force feedback and bimanual interaction. These are some already engaged outlooks around deformations in geometric modeling.

New exploration modalities.

The addition of new exploration modalities will also be studied. Thus the "potter metaphor" will allow to rapidly evaluate, and without effort, the results of deformations realized by turning the object by simple hand movement on the horizontal display of the workbench.

Augmented visualization modes.

The perception of the relative positioning of geometric forms in the environment can sometimes be problematic, due to the employed visualization techniques, and the difficulty posed by simply changing the user's point of view in relation to the application. The usage of "augmented" visualization modes (e.g. the objects shadows) will provide the user important visual indices for the perception of depth information. Other visualization modes, such as the surface coloration of the constraint area by a realized deformation will give the user a real-time feedback on the status of the interaction.

Gesture-assisted techniques.

The lack of accuracy of the utilized peripheral devices (especially data gloves) will be compensated by a support technique for the selection of application point of the initial constraint and the control of the deformation gesture. An idea is e.g. to help the user in inputing local maxima by the implementation of a metaphor of type "potential wells". The deformation gesture can be imprecise and therefore we are working on the correction of the manipulation errors thanks to parasite movements smoothing algorithms and/or correction of the trajectory according to the features of the deformation constraint.

Materialization of properties using haptic feedback.

We will study the materialization of some properties in tactile form with the purpose of reduction of visual overcharge. We improve the gesture control with the introduction of force feedback in particular in applications of geometric modeling and surgery gestures simulations.

Virtual reality platform

We offer to share our main results with the community, particularly in the form of a software platform around a virtual interaction toolbox in link with the IRMC platform. We also jointly work on the VR platform set up by the Alsace region in 2007 (Iconoval and Holo3). Our CNRS research engineer heads this project in collaboration, from one side, with the head of the VR platform of Alsace region, Silvère Besse,and from the other side in coherence with the IRMC platform within the world-class pole of competitiveness "Innovations Thérapeutiques" (therapeutic innovations).

We will integrate in this VR platform interaction techniques for the selection, manipulation and edition of huge sets of objects in 3D complex scenes. This work will be applied to the modeling and editing of details in natural scenes and to the processing and interactive visualization of large and complex data coming from numerical simulation (ANR Masse de données DNA et MASSIM).

Medical applications and VR

Concerning the applications, they will principally be centered on the medical and therapeutic domain, with our participation to the multi-labs program IRMC (Imagerie et Robotique Médicale et Chirurgicale) on themes of the world-class pole of competitiveness "Innovations Thérapeutiques" from Alsace region.

Manipulation, visualization and virtual navigation in the human body.

A first medical application will intend to elaborate methods and specific and ergonomic tools for realistic simulation of surgical gesture. Thus we will develop virtual navigation and manipulation techniques in a model of the human corps (abdomen) with palpation and insertion of a needle for radio-frequency and virtual endoscopy in the blood vessels.

Treatment of psychiatric troubles using VR.

A second medical application will study the impact of VR on psychiatric treatments of phobia or obsessional and compulsive troubles (OCT) by behavioral and cognitive therapies (BCT). The immersion of a sick person in a virtual environment will put him/her in situation in a gradual fashion and will allow the exploration of the effect of the variation of new parameters on the apprehension of the patient. The interaction with the virtual environment will offer a realistic immersive simulation of a real anxiety-provoking situation. The alimentary troubles will be studied in collaboration with the LINK (Céline Clément) and a psychiatric (Marc Villard). The schizophrenia could also be studied in collaboration with Professor Danion from the Hôpitaux Universitaires de Strasbourg (University Hospitals of Strasbourg).