Geometric Modeling, Simulation and Interaction

Jump to: navigation, search

Back to home

Objectives / Challenges

The main objective is to improve the quality in terms of efficiency and robustness of geometric modeling and simulation operations. To achieve this goal, we operate our topological models based on combinatorial maps that facilitate the operations of geometric modeling design through their generic in terms of size and type of cell, and thanks also to the separation of the topology and the embedding of objects which is the basic concept.


  • Two Professors : Dominique Bechmann et David Cazier
  • One Senior Researcher : Stephane Cotin
  • Three Associate professors : Antonio Capobianco, Jérôme Grosjean et Pierre Kraemer
  • Two Research engineers : Thierry Blandet et Sylvain Thery
  • 5 PhD : Sabah Boustila (Project CIMBEES from Dec. 2012 to Sept. 2015 (PhD thesis defended on May 25, 2016)), Christoph Paulus (INRIA contract starting from January 2014), Thomas Pitiot (CNRS / Région Alsace doctoral contract from Oct. 2012 to Sept. 2015 (PhD thesis defended on December 17th, 2015)), Lionel Untereiner (UNISTRA doctoral contract from Oct. 2010 to Sept. 2013 (PhD thesis defended on November 8th, 2013)), Jonathan Wonner (Allocataire Normalien from January 2011 to Dec. 2013 (PhD thesis defended on October 8th, 2013)).


Adaptative and multiresolution volumic model

Automatic cell labeling to implicitly define a mesh hierarchy.

A strong trend in geometric modeling is to use multiresolution to represent objects at different scales. We proposed a model quite original, combinatorial maps multiresolution model based on combinatorial maps. This work was extended with the thesis of Lionel Untereiner [8-UNTE13] in any dimension of meshes. We defined topological and geometric operators to first work on dimension 3 tetrahedral and hexahedral meshes, and more generally on arbitrary topologies with a multi-scale approach [3-UCB12, 2-UCB13].

Volume subdivision of a torus with genus 3, modeled as a set of general polyhedra.

If multiresolution representations are studied for long time for surfaces, multiresolution models supporting volumetric representations or greater dimension are very rare and limited to very specific applications. The development of generic models with multiresolution simplification operators, subdivision and refinement both topological and geometrical is a major issue in geometric modeling. This work was implemented in the modeling platform CGoGN [4-KUJT13]. An implicit representation, more compact, also has been proposed [2-UKCB15].

Detecting collisions in dynamic environments

A crowd of autonomous agents moving around polygonal mobiles (red).

In the domain of animation and real-time simulation, our combinatorial models allow the structuration of the space in which objects evolve, offering new opportunities to address important problems in computational geometry, such as collision detection or search for nearest neighbors. We used this principle by exploiting a topological subdivision of the environment particularly adapted to the context of crowd simulation. Our models allow the subdivision on the fly of the cells when the density of agents increases. Conversely, when it decreases, the cells are simplified. This approach allowed us to get proximity queries executed in constant time regardless of the density of the simulated scene [2-JKC12].

Initially limited to specific agents, this work has been extended with the thesis of Thomas Pitiot [8-PITI15] to polygonal deformable agents [2-PCJH14], then used in medical applications to track the movements of a needle within tissues and anatomical structures.

Real time simulation of cuts and tearing

As part of the thesis of Christoph Paulus, we exploited our combinatorial models for the simulation of cutting and tearing of deformable objects [2-PUCC15]. In particular, we have developed local remeshing operators allowing to approximate a separation surface while ensuring that the number of nodes and elements added is kept as small as possible. This last point is essential to ensure computation times compatible with real-time simulations.

An augmented elastic object undergoing large deformations and topological changes.

This work was used for the automatic detection and tracking of cuts and tears in videos [4-PHCC15a]. An analysis of the feature points (selected in the images) trajectories is coupled to the combinatorial structure of our model to reproduce the observed tearing on the virtual models which allows their use in the context of augmented reality application. The latest publications in the medical computing community demonstrate the benefits of this approach [4-PHCC15, 2-PHKSxx].

Separation of degrees of freedom for manipulating objects

Our interaction concern is to improve the creation and interactive manipulation of digital objects. The hopes raised by the virtual reality in the beginning, was that the immersive environment would be likely to improve the perception of 3D objects. In fact, if stereoscopic vision provides a feeling of 3D, it makes them less accurate direct manipulation. Our goal has been to offer solutions that leverage these immersive environments.

We got convincing results for positioning and orientation tasks of an object through the separation of degrees of freedom (DOF) and the use of proprioception (awareness that one has to position its own body). We have shown that, contrary to the approach generally operated, based on maximum integration of the different DOF for such type of tasks, it is preferable to isolate the control of the dimensions if we require a significant level of accuracy in the final phase of the task. In consecration of this work, we have obtained a publication in the best international conference IEEE Virtual Reality VR'2011 [4-VCB11] where this year it was to be the only long accepted paper from a French laboratory.

Aids for selection of targets in immersive environements

As part of the thesis of Jonathan Wonner [8-Wonn13], we proposed three areas for improvement and help in the selection of immersive targets.

1. To locate a target with an indication of its orientation, the challenge is to give the user 3D direction information without visual overload. The original idea is to use a series of circles around an axis indicating a direction with a simple color code, the red-green direction giving the right direction. These circles are positioned on the surface of a sphere and thus seen as ellipses, depending on the orientation of the sphere and the point of view of the user. Integrated with a spherical pointer whose radius adapts to reach the nearest object, the analysis of experimental results showed that this selection technique [4-WGCB13] offers a credible alternative to the best technical support of the state of the art (3D arrow) for the localisation.

2. For selecting a target in dense environment, the key idea of an original technique of guidance, also coupled to the spherical pointer, is to offer dynamic branches along segments connecting the pointer to potential targets. The preset target is performed by applying multiple filters: distance filter, angular filter, the maximum number of target. The highlight of the Starfish [4-WGCB12] which clearly shows the interest and relevance of the method is that the error rate remains stable when increasing the density of the target in the immersive environment.

3. Finally, a new method of estimating the target based on the movement of the hand and specifically the control phase of the movement after the peak speed of movement of the hand, led to a prediction of the target, from the user selection gesture [5-WGCB11].

Distances perception factor in virtual environments

Several studies have shown that the estimation of distances in a virtual environment is different from estimate real environment. Even with the use of stereoscopy, distances are difficult to grasp in a virtual environment. Multiple factors can cause this problem, such as the display device, the limited field of vision, graphical quality, etc. Despite the different studies on this issue, the causes of this phenomenon are diverse and poorly identified.

Our work is part of an architectural project (CIMBEES) whose objective is to provide a tool for project review, allowing the virtual tour in digital models at real scale. In the evaluation phase of our navigation tool in immersive environment, we identified three important factors of depth perception. A protocol for testing whether browsing speed, furnishing houses or cognitive profile of users can have a positive impact on the perception of distances and volumes (habitable) in immersive environment was conducted as part of the thesis Sabah Boustila.

Through this assessment published in IHM [5-BBC15] and ACM VRST CORE Rank A [4-BCB15 4-BCB15], we sought the appropriate settings. Among the many recommendations, the three most significant are that slow browsing speed (two times slower than normal walking) is most suited to immersive virtual tours of a house, that furnished homes offer a better understanding of space, and finally, the lack of display device on the floor is problematic because the user does not perceive its near space. To counter the latter, a new kind of 3D projection was tried to expand the vertical field of view without altering the perception of volumes [[4- BCB16a] 4-BCB16b]. Among the many perspectives of this work, it seemed relevant to examine the effect of adding indications that the cognitive profile of the user to improve virtual tours and perception of distances and volumes.


Many works simultaneously use several representations of the same object. They can correspond to different levels of visualization or different levels of detail of the same 3D object, but also different kinds of models. Thus, in simulation, it is not uncommon to use a coarse volume mesh for numerical calculations, in which a finer surface mesh is associated to a realistic rendering. Multiscale representations are also used to image segmentation, compression or filtering meshes. Finally many algorithms rely on hierarchical structures to speed up treatment, such as ray tracing and collision detection.

We want to offer combinatorial structures for the representation of such multiresolution objects and equip the multi-scale topological operators to consistently manage and controlled the interdependencies between representations. This is for example to build such hierarchies, manipulate, apply cutouts of it, simplifications, refinements or to make effective geometric queries.

We will continue our work on combinatorial maps and their multiresolutions extensions, especially for volume meshes, aiming coupling with interpolating subdivision surfaces with a fine representation of the surface and coarse volume by a single mesh allowing for easier tracking at an operations simulation (cutting or contact).