THEME 1 OPERATION1

Operation 1: Geometric and topological modeling

Head : Dominique Bechmann PR1 and David Cazier AP.

Participants : Rémi Allègre AP, Dominique Bechmann PR1, David Cazier AP, Jean-Michel Dischler PR1, Basile Sauvage AP, Hyewon Seo CR1 CNRS, Sylvain Thery RI.

Ph.D. candidate : Thomas Jund.

Postdoc : Younis Hijazi.

Engineer (on contract) : Cyril Kern.

Presentation

Due to the increasing number of object representation models, from the structural or geometric point of view, our main goal is the design and study of models that are well-suited for specific applications [1-CM07]. These models must accurately reflect the structure and the intrinsic properties of the concerned objects. We aim at describing them in a formal way adapted to analysis, proofs and specifications by answering at best to the practical uses that will be applied. One fundamental concept is the separation of the structure (or topology) and the shape of the objects in order to minimize the intrinsic difficulties coming from geometry.

Geometric modeling platform (CGoGN)

The first business of this operation is a transversal activity that integrates research conducted over the whole team, around geometric modeling. It deals with the definition of a geometric modeling platform CGoGN whose goal is to offer a general framework for the definition of combinatorial-based topological models permitting to represent the topology of subdivisions of arbitrarily-dimensioned geometrical spaces.

This work The07 consists of a capitalization of research in geometrical modeling conducted since around twenty years at IGG and initiated by Jean Françon and Jean-François Dufourd. The conception and development of this software platform are headed by Sylvain Thery (research engineer) and David Cazier (associate professor), together with the participation of any person implicated in theme 1 of IGG.

Several versions have been developed and thanks to user feedback (intern or extern to the team) we have now reached a stability that allows us to highlight the following developments :

A generic topological model, flexible and adaptable :

• Generic maps
• Dual and primal maps of dimension 1, 2, 3, ..., N (optimized until dimension 3)
• Generalized maps of dimension 1, 2, 3, ..., N (optimized until dimension 3)
• Hyper-maps of arbitrary dimension
• Multi-resolution maps (mainly used for surfaces)

Cell embedding (vertices and faces) :

• Simple 3D Point
• With information of valence
• With information of colorimetry, frequence
• With texture parameters
• Bézier / Gregory Bézier patches

Several algorithms which apply to all the models :

• Mesh simplification (parameterable Edge-Collapse)
• Subdivision surfaces (Loop / Catmull-Clark)
• Classical primitives (2D/3D grid, cone, torus, sphere)
• Extrusion of surfaces and revolution surfaces
• Various OpenGL rendering (surface, topology, with shaders)
• Cell selection
• Optimization of combinatorial maps (read-only) by re-ordering of darts
• Import /Export of several file formats (ply, off, obj, trian)
• Iso-surface extraction (Marching Cube)
• Implicit surfaces

Note that these algorithms have been developed independently from the underlying model. Thus they can be employed with all the models compatible with the data to be treated.

The library CGoGN has been made available to the community and a software support is provided to the labs that use it, including: the LE2i in Dijon, the Alcove projet (INRIA) and Graphix team in Lille, the Sic XLI in Poitiers, and the INRIA project GEOMETRICA in Sophia Antipolis.

Bridges to other libraries and platforms have been initiated. The most advanced is with SOFA, a development platform of real-time medical simulation. We have included in it our topological models which can be used by certain simulators from now on. The other more ambitious bridge is the use of CGoGN models within the well-known computational geometry library CGAL.

Towards new object representation models

The second business aims at offering new topology-based models extending the combinatorial maps historically studied in Strasbourg with the purpose of extending their representation domain and improve their efficiency in terms of memory cost and operability.

Non-manifold models

Thus a first extension, the <math>\theta</math>-maps, enabling to model non-manifold objects of dimension 2 (i.e. 2D simplicial complexes), has been designed. The <math>\theta</math>-maps are being integrated in the geometric modeling platform. They allow the representation of surface meshes, with or without border, manifold or non-manifold and being composed of cells of different dimensions (isolated vertices, broken edges, surfaces, volumes). Based on the maps, this arranged model has the same benefits and, in particular, uses only one type of input (the darts) to model complex objects. This largely eases the development. Moreover, we have demonstrated that the memory cost of this structure is reduced (by a factor 2) compared to the existing equivalent models (Radial Edge, Partial Entity Structure and derivatives). This work is being submitted to a journal.

Multi-resolution models

In the seeking of new models a current tendency is to use multi-resolution representations to represent objects at different scales, form coarse to fine. The data structures usually implementing these models are based on quad-trees of faces or vertices. The problems commonly raising from these models are, from one side, the prohibitive memory cost, and from the other side the complexity of the update operations or object modifications. An original data structure, the multi-resolution maps or MR-maps, has been created (thesis of Pierre Kraemer). It is based on combinatorial maps and inherits from their formalization, generality and efficiency.

The MR-maps model is also adaptive, in the sense that it allows a refinement at a varying depth according to the areas of the modeled object. In the tree structures commonly used in this context (quad-trees), the adaptivity produces topological holes which are avoided in the MR-maps. With the MR-maps the topological consistency is always maintained. We have demonstrated that the memory cost is similar to quad-trees in the general case, and adaptive. But the efficiency of the different resolution levels' traversals has been greatly improved. For instance the adjacency operations are performed in constant time for MR-maps, compared to O(log(n)) for quad-trees (of height n).

Subdivision surfaces

An embedding which associates a geometry to the cells of the topological model (set of darts) defines the form of the object. We have experimented various types of embedding in IGG's research group from LSIIT. Thus the embedding by Bézier surfaces, which have proven their efficiency, are being implemented in the geometric modeling platform. Following the definition of MR-maps we have proposed their embedding over subdivision surfaces KCB07, KCB07b. This gave us the necessary basis for the multi-resolution analysis and deformation techniques such as multi-resolution editing.

This new kind of embedding, never proposed for combinatorial maps, has in this context many benefits. The MR-maps support a large panel of subdivision schemes : the primal schemes (splitting the faces) or dual (vertex collapse) and even more original schemes which have not yet been used in multi-resolution such as the <math>\sqrt(3)</math> scheme or quad/triangle KCB07a (mixing triangular and rectangular facets). We think that we are able to use this genericity to offer new subdivision schemes, in particular by mixing classical schemes.

Conversions between several geometric representations

The third business of this operation has the goal of offering several methods for switching from one object representation model to another. It is indeed delusive to think that a unique model could optimally answer to all applications of geometric modeling. Thus geometric modeling is characterized by a heteroclite abundance of models. We are working on the conversion of one representation to the other more often to a topological model.

Organs reconstruction and meshing

Within the framework of reconstruction of organs of the human corps from medical imaging data (CT scan, MRI), we focused, in collaboration with the IRCAD, on the pass from segmented voxel images to combinatorial 2-manifolds. This mesh perfectly reflects the topology of the organs in terms of adjacency (between organs), inclusion (tumors) or intersection (vessel-organs). An innovative algorithm BBT07, based on a discrete Delaunay technique, has been designed (thesis of Dobrina Boltcheva). Following this work, a generalization of the very well-known and very utilized algorithm of Marching Cubes is being validated for discrete 18 and 26 connected objects.

Blood vessels modeling

In the same context we are currently looking at the reconstruction of blood vessels of the human body which, due to their geometry, set other difficulties than the organs which are homeomorphic to spheres, as the liver. An algorithm which solves the major problem of multi-branching reconstruction in vascular trees (human corps or other) is under validation. Based on our approach of separation of topology and form/geometry, the algorithm uses techniques of computational geometry, in particular the convex hull in order to reconstruct simply and automatically the topology of any branching. Indeed in the human body, up to 7 branches can meet. This first step has been done; we still need to map the geometry to the data. The outcome will be a beautiful theoretical result with many practical applications.

Modeling of cavities in molecules

In collaboration, this time with researchers from the IGBMC, we attacked (thesis of Benjamin Schwarz) the problem of detection and characterization of cavities formed by biological molecules. We would like to model the surface of these molecules and more particularly the surface of their cavities using a parameterized surface. This model will be used in biology for the visualization and the search of features such as the area or volume value, or plasticity of cavities. This information are of great importance in the comprehension of biological phenomena and find a direct application in the research and design of new drugs.

Vector field distance transform

Finally, the last but not least application is the reconstruction of laser-scanned objects (thesis of Marc Fournier).

At the origin, geometric modeling wished to offer tools such that any real object could be manufactured in softwares called modelers thanks to effective operations. The current tendency is to base on real data, coming e.g. from scanners, to model the objects. The storing of works of art is the targeted application in the context of the project RIAM AMI3d.

We are interested here in the choice of a good data representation in order to then merge them to reconstruct the object seen from various point of views or smooth them to correct the noise coming from scanners. A new representation, the vector field distance transform, has been tested and proves its efficiency compared to existing methods [2-FDB07, 4-FDB07, 4-FDB06].

Collision detection

The fourth business of the operation 1 is the exploitation of the topological structures developed in the team for the improvement of geometric algorithms. In particular we think that the strong structuring of objects, provided by their topology, can avoid (or make more competitive) many geometric computations. These ideas are currently applied to algorithms of collision detection.

The detection of collisions between a mobile and its environment is crucial in the context of applications of physical animation. Many methods have been proposed for accelerating this detection in a complex scene to respect the constraint of interactivity. Nevertheless, when the environment becomes deformable, the optimizations of these structures based on the use of hierarchical structures find their limits at the level of update time.

We work, in the context of Thomas Jund's thesis, on these methods providing a volume subdivision of the environment coupled to a prediction mechanism. The environment is subdivided in a set of convex cells enriched by a strong topological structure allowing optimal neighbor requests. This prediction system uses the temporal coherence and the cells properties to optimize the number of intersection tests to perform at each time step.

Trajectory of a mobile in 3 dimensions

This principle has been experimented on the animation of particles, displacement of solids in deformable environments. See videos in the video gallery or at the following link : video on Youtube.

Digital human modeling

Manufacturers that design products today base their size related decisions mostly on 1-dimensional anthropometric data. This method is not precise enough and not suited for the mass production, nor for customized design. If digital human modeling techniques are to be meaningful in this context, they must be able to produce correctly sized 3-dimensional body models and be efficient enough to be used in an interactive runtime setting with minimum user intervention. Computer aided modeling of human body that satisfies such requirements is a difficult task, even with the most sophisticated software available.

One of the most challenging research areas in this context is in developing a robust methodology on automatically building realistic 3D human models that satisfy given size or attribute-related constraints in real-time performance.

Parametrically controllable shape and motion

With the above mentioned target applications considered, the main goal of this research is to develop methods to create desired models on the fly through a set of user-controllable parameters. At this time, a variety of 3D reconstruction methodologies are available that can capture shapes that exist in the real world. Our initial models or examples rely on the 3D shape capture technology. The initial models from capture technology are then organized to serve as input into the shape interpolator. Each example body scans are converted into a morphable and animatable model through the conformation of a template model. By builing statistically learning models between the control parameters and the target geometry, we obtain highly controllable yet realistic digital human models.

We focus on : (1) The development of a method for accurately learning the variation from dataset, especially to handle multiple modalities such as morphologidal identity, and poses or dynamic variability. Given sufficiently large datasets, the model will capture both static (identity-dependent) and dynamic (movement-dependent) shape variation in a correlated fashion, enabling a continuous range of evaluation. (2) The extension of the parametric deformation model to the motion data. The goal is to generate desired motion through multi-way blending of realistic motion from motion capture data.

Registration

Registration, or optimal alignment of two shapes in arbitrary configurations, is a fundamental problem in shape acquisition and modeling. Given two shapes, often called model and data, the goal is to determine a transformation that optimally aligns the model with data. This process is necessary in order to be able to compare or integrate the data obtained from different measurements. Measurement data from human, the most frequently observed subject of imaging devices, set several technical challenges: (1) Reliable correspondence computation becomes a complex problem to solve. It is quite obvious that the difference between geometric features as well as shapes could be far too large due to the inherently large variation among different individuals. (2) Human bodies are not only just flexible but also highly mobile, to drastically change their spatial arrangement or pose.

Taking a step beyond the existing methods that use static shape information for feature computation, we aim for novel approaches by exploiting large redundancy of information that resides in dynamic or movement data. Such redundancy may be particularly advantageous for characterizing underlying anatomical structure on the surface, allowing to obtain better accuracy and reliable correspondence.