Modeling and Acquisitions
This theme gathers the research activity around the creation, the representation and the modification of 3D complex models. In the domain, two major goals are still challenging:
- facilitate the creation of 3D objects, notably by digitization;
- produce efficient models for objects at a chosen level of detail.
Designing 3D virtual worlds leads to high production costs which are proportional to the complexity of the scenes and to the need to hire teams of artists to generate content. Digitization allows to improve the production of contents in some cases, but they often impose high constraints and are not easily scalable.
First, our approach aims at developping new process to facilitate the design of 3D objects, which are static or dynamic and with or without rendering information. This works focus on the use of digitization (photographs, scans and motion capture) combined with specific processing.
Then, we also propose to study new combinatorial structure to represent geometric objects. These works take into acount combinatorial manifold and their multiresolution extensions; the modeling of cellular or simplicial complexes; encoding discrete topology; and describing algorithms using this topological structure for reconstruction or collision detection.
All our results are available for the scientific and industrial community via the development of two platforms: a topological geometric modeling platform CGoGN, which is an open source software platform under LGPL, and an hardware platform dedicated to Digitization.
Permanent participants
- 2 Professors: Dominique Bechmann et Jean-Michel Dischler
- 1 Associate researcher: Hyewon Seo
- 4 Assistant professors: Rémi Allègre, David Cazier, Pierre Kraemer et Basile Sauvage
- 2 Research engineers: Olivier Génevaux et Sylvain Thery
Others participants
- 1 Extern colloborator: Frédéric CORDIER (MC UHA Mulhouse, 09/2008-)
- 1 engineer: Cyril KERN (ANR VORTISS puis STREP PASSPORT 09/2007-05/2010)
- 4 Post-doctoral: Olivier GUILLOT (ATER, 09/2008-08/2009), Younis HIJAZI (STREP PASSPORT, 02/2009-12/2009), Thomas JUND (ATER, 10/2010-08/2011), Frédéric LARUE (Région Alsace, 12/2008-08/2009)
- 2 PhD candidate: Lionel UNTEREINER (Ministère, 10/2010-), Kenneth VANHOEY (Ministère, 10/2010-)
- 6 Former PhD candidates: Dobrina BOLTCHEVA (Région Alsace-IRCAD, 10/2003-10/2007), Marc FOURNIER (Canada grant, 10/2004-11/2008), Thomas JUND (Ministry of Research grant, 10/2007-09/2010), Pierre KRAEMER (Ministry of Research grant, 10/2005-11/2008), Frédéric LARUE (RIAM AMI3d, 10/2005-11/2008), Benjamin SCHWARZ (Contract, 10/2004-08/2009).
Acquisition of models: static geometrical representation and appearance
We developed process allowing to generate automatically and easily numerical models from reality (scans and photographs).
For this purpose, we specified a new protocol of digitization based on the projection of stripes (structured-light). This protocol is included in a complete framework we developed which includes every process from digitization to rendering. In this framework, we proposed solutions for registration, noise filtering and rendering of digitized surfaces 2-FDB07, 4-LAD07, 4-FDB06, 4-LD06. This activity lead to the creation of a digitization platform in the laboratory and to a transfer of technology to the CRITT HOLO3.
We also conceived and developed techniques allowing to design and edit complex virtual materials, based on a procedural representation 2-GD09, 2-GD10. The goal is to allow 3D content designers to reproduce reality with simple interactive manipulation, while insuring an artistic freedom unlike the digitization techniques, which only allows to create a copy. A part of these activities are supported by the ANR ATROCO in colaboration with the EPI ARTIS (Grenoble) and the LIRIS (Lyon).
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 using Dynamic Data
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. We have acquired subjects’ movement data and developed deformation analysis method so as to characterize dynamic features on them 5-KCWK105-COHK09.
We are currently devising a new registration technique that makes use of this rich set of information to guarantee reliable correspondence. This work is being pursued in the framework of the French national project SHARED (Shape Analysis and Registration of People using Dynamic Data).
Multiresolution combinatorial models
The interest in multiresolutions representation of geometric objects is increasing in many domain of computer graphics. In this context, the surface is not represented by a unique mesh, but with a set of interlinked meshes, representing different resolutions and with rules allowing to go from a resolution to an other. The representation is said to be adaptive is the maximum resolution is only present in some areas. Multi-resolution models find their applications in multiresolution analysis, for compressing or filtering meshes, progressive transmission or displays depending on the point of view.
Subdivision surfaces allows to build multiresolution surfaces. This models are usually quadtree forest directly derived from the used subdivision scheme (quadrangulation of faces). This structures are limites to triangular or quadrangular meshes and adjacency requests are executed with a O(log(n)) complexity which is a restriction for usual geometric algorithms.
Conversely, dense meshes resulting from 3D acquisition may have an irregular connectivity. In this context, progressive meshes build a natural hierarchy obtained by collapsing cells. These models do not make use of a multiresolution structure and must rebuilt meshes on the fly, to be able to apply previously mentionned algorithms.
We designed and implemented a new data structure, multiresolution maps or MR-maps 2-KCB09. It is based on combinatorial maps theory and inherit its formalisation, genericity and efficiency. The MR-maps model is also adaptative, meaning that it allows local subdivision at various depths of the represented object. Following the MR-maps definition, we also embedded them on subdivision surfaces 3-KCB07, 4-KCB07.
We demonstrated that the memory cost of MR-maps is similar to the quadtrees one in general adaptive case while the efficiency of the complexity in access at different level of details is highly improved and is in constant time regardless of the level of resolution used.
This new embedding kind, never proposed for combinatorial maps offers many advantages. MR-maps allows a large panel of subdivision schemes : primal schemes (cutting faces) or dual (splitting vertices), or even more original schemes not used with multiresolution such as the <math>\scriptstyle \sqrt{3}</math> scheme or the quad/triangle scheme 4-KCB07b.
Non-manifold combinatorial models
Most used models, like maps, allows to represent manifolds in any dimension in an efficient manner. However for some applications, representing non-manifolds objects is crucial. These models offers a wider representation domain, enabling singular vertices and allowing to represent cellular complexes combining sets of objects of varying dimensions, like curves, surfaces and solids.
The radial edges model, introduced in 1988 by Weiler, and the derived models are still in use, albeit their memory cost and their non-optimality for adjacency requests. Tetrahedral models, which are more restrained, are often prefered for their efficiency.
A new model has been developed by D. Cazier and P. Kraemer, which allows to represent any cellular complexes. We named it X-maps for extended maps. For this purpose, we extended the combinatorial maps with a new relation allowing to link vertices around singular vertices. The connected components of an X-maps without this relation for a (non unique) decomposition of complexes represented with a set of joint manifolds (curves, surfaces, volumes). We proposed, in 4-CK10, a dual implementation of this compact model (which divides by 4 the memory cost of radial edges). This model benefits from the efficiency and genericity of maps on the manifolds parts.
Collision detection
The detection of collisions between primitives in a scene depends quadratically on the number of primitives. Classical methods usually make use of bounding volumes hierarchy (AABB, OBB, k-DOP). The goals of this hierarchies is to reduce the complexity of this research to a logarithmic complexity. But usually, no special consideration is given to changes of topology in the scene (cuts, stitches,..)
We proposed a new collision detection system, allowing to follow any mesh (particles, curves or surfaces) within a complex deformable scene. The space surrounding the moving objects is subdivided in convex polyhedrons and represented with a 3-map. We thus obtain a volumic partition of the space which is naturally adapted to deformations or changes of topology which can occur during a real-time simulation.
We then perfected a forecast mechanism allowing to follow the displacements of vertices in the environment while making use of temporal and spatial consistency of the simulation. Its efficiency has been insured with the combinatorial structure of the 3-maps and their implicit decomposition in oriented tetrahedrons optimizing the number of geometric tests to perform 4-JCD09. This system allows naturally deformation of the environment and of the moving objects, and handles efficiently topology changes thanks to local controlled modifications.
Results have been extended to edge collision detection 4-JCD10, 4-JCD10b. Their displacements are decomposed in elementary displacements forming triangles which sweep space. Using geometric properties on convexity and displacements, it is possible to obtain precise edge collision detection, without too much overcost compared to particle collision detection. We thus implemented our system with two kinds of difficult real-time simulations : the insertion of a catheter in a deformable vascular network and the displacement of deformable moving objects in an environment whose topology and geometry changes through time.
See the video gallery for exemple of simulations.
Mesh reconstruction based on medical data
In the context of geometric reconstruction of human organs based on medical data (scanner, MRI), we worked, in collaboration with the IRCAD, to build combinatorial 2-manifolds or 3-manifolds from segmented voxels pictures.
A new algorithm 3-BBCK09, based on a discrete Voronoï diagram has been proposed. It allows the generation of a mesh representing perfectly the topology of organs considering adjacency, inclusions and intersections. During the PASSPORT european project, this algorithm has been implemented in its multi-organs version and integrated in the rendering software of medical data of the IRCAD. This work continue with the project IHU Mix-Surg.
We also proposed an algorithm to reconstruct tree structures such as vascular networks, where up to 7 blood vessels can rejoin.
Mesh generation adapted to vascular networks arises topological and geometrical problems.
Using the separation of the topology and the shape, an algorithm has been designed 4-HBCK10 using computational geometry to build automatically the topology of any kind of junction.
Perspectives
Acquisition and processing of large and detailed 3D models
3D model reconstruction from multiple data sources
We have designed an efficient 3D acquisition pipeline for constructing 3D geometric models from scanned objects, that reproduce both the shape and appearance of the objects at different levels of detail. Unfortunately, these techniques do not easily scale to hundreds of millions or billions of sample points. This is first due to the complexity of the algorithms and/or their memory consumption. Out-of-core and streaming techniques that operate on data-structures stored in mass storage memory are only suitable for localized treatments or processing at low scale, at the expense of a reduced robustness to defect-laden data incorporating noise or missing parts.
Another factor that hampers scalability is the frequency of user intervention throughout the 3D acquisition pipeline. Despite the significant advances regarding the automation of the algorithms, user interaction is still often required to fit parameters or to perform corrections. Sometimes it is required to restart the whole process from scratch, which is very penalizing when performing complex operations on large data sets. A major difficulty in reconstructing geometric models is the lack of prior information about the properties of the scanned objects: structure, global and local shape, components, etc. Only 3D-scanned data are generally taken into account by existing reconstruction algorithms at this step of the pipeline.
To overcome these issues, we aim at developing new techniques taking advantage of the complementarity of multiple data sources for the reconstruction of geometric models: scans, photographs, 3D models with similar shape and/or appearance, sketches, etc. Our goal is to devise integrated methods built on the analysis of these different kinds of data, making it possible to capture the main features of the scanned objects, that will then be used to localize and guide the reconstruction process with minimum user interaction.
3D model representation for real-time visualization
The huge size and complexity of models represented using standard triangle mesh data-structures involve numerous storage and visualization issues. In complementarity to multiscale representations, Our research includes development of alternative representations offering both compactness and suitability for real-time realistic rendering, as well as suitability for some edition operations (virtual sculpture, simulation of natural phenomena).
Representations based on the displacement mapping technique and hierarchical voxel grids efficiently take advantage of the computational power of current graphic processors. These data-structures both require large storage space in graphic memory for complex 3D models, that is not necessarily justified by the local geometry. In order to visualize complex models with limited memory resources, we are developing a new approach of procedural modeling for surfaces based on displacement maps and procedural generation techniques.
Digital human modeling
Taking a step beyond the existing methods that use static shape information for feature computation, we aim at investigating novel registration method that exploits large redundancy of information from dynamic or movement data. The main interest of the proposed approach is to preprocess the subjects’ movement data so as to characterize anatomical or functional landmarks, and devise a registration technique that makes use of this rich set of information to guarantee reliable correspondence. Appreciably, with the recent advances in imaging technologies we now have growing accessibility to capture the shape and motion of people with high frequency. For example, it is now not uncommon to track the locations of selected skin surfaces (markers) using a number of synchronized cameras. In cardiology, the usefulness of MR tagging to access regional myocardial deformation has been widely demonstrated.
Multiresolution and multiscale combinatorial models
Many works use simultaneously many representations of a unique object. These representations can correspond to different scales for rendering, but also to different type of use. For example, in simulation, a coarse volumic mesh can be used for numerical computation, while a more detailed surface mesh is used for realistic rendering. These multiscales representations are also used for segmentation, compression or mesh filtering. Also, many algorithms use hierarchical structures to speed up their computation, like raytracing or collision detection.
We would like to use multiresolution combinatorial structures to represent these objects and to handle consistently the set of the representations. It can mean, for example, to build a hierarchy and to apply cuts, simplifications, refinements or to perform efficient geometric requests.
These works focus on three problems :
Multiresolution combinatorial models. We will continue our works on combinatorial maps and their multiresolution extension, more precisely we aim at : the rendering of progressive volumic meshes, simplification and optimisation of meshes using multiscale representation. We also aim at the multiresolution analysis of volumic data for their sampling, compression and for numerical treatments.
Pictures or meshes segmentation. We used the discrete Voronoï diagram to generate surface or volumic mesh based on segmented data. We would like to extend this principle to allow the segmentation of meshes and treat in a new manner the problems linked to the simplification and the sampling of volumic meshes.
Space partition and topological structure. We proposed a particle forecast mechanism in deformable environment. It has been used for collision detection between a moving object and its surrounding for surgery simulation. We would like to use this space partition defined with our topological structure to treat more generally collision detection. Work is still to be done on self-collision and topological changes. More generally, our methods will allow us to study proximity queries in partitionned spaces.