Programme INRIA "Equipes Associées"

Présentation détaillée de l'Équipe Associée

1. Scientific Scope and Goals

Research Area. While Computational Science is traditionally concerned with the discretization of existing differential mathematical models, the Computer Science community has mostly focused on processing purely discrete data. Unfortunately, little interchange occurred between these two worlds along the way; only recently did we witness a resounding change. For example, computational work using discrete harmonic functions discovered the need for constructing explicit representations of the co-/homology group of a surface; a discrete analog of Morse theory became an important computational tool in bio-medical computing; tools in graph theory have become critical in numerical optimization; learning theory helps discover non-linear manifold structures in our data.

These combined developments have often arisen by chance rather than from a broad, disciplined examination of the foundations of modeling in the context of computation and geometry. We argue that we need to develop discrete differential geometric modeling to bring synergy between Computer Science, Computational Geometry, Computational Science, and application areas, and to further develop our understanding of the geometric structures present in our scientific descriptions of the world. The term ``geometry'' is used here in the broad sense of –possibly high dimensional–manifolds and their structures. While there is still much mathematical developments needed to understand 4D and above structures (symplectic geometry being a classic example from mechanics), processing of discrete 2- and 3-manifolds (possibly varying in time) already requires serious advances in theoretical understanding and technical tools before it can fully impact applications areas such as CAGD, geophysics, or bioengineering.

The research goal we envision in this proposal is a continuation of our respective research efforts in geometry processing. Acknowledging that the passage from continuous differential modeling to discrete implementation lacks the necessary safeguards to guarantee the preservation of underlying structures in the resulting discrete algorithms, we wish to develop a discrete approach to handling differential models that also serves as a differential justification to discrete models—hence our use of the term discrete differential geometric modeling. As our goal is computation, it is natural to ask whether it would not be better to directly formulate the underlying models in a manner that allows computation without destroying important structures. Our mutual work in the past three or four years answers this question positively, but much work remains. Further developments should leverage the mature geometric understanding of calculus on manifolds (going back to Cartan, Lie, Hodge, de Rham and others) on which most physical theories are based, as well as tools from algebraic topology, graph theory, and algorithms.

Primary Goals. Although our goals are obviously in need of a long term effort, we have identified a series of initial milestones that can be achieved over the next year or so as described in the work plan in Section II. We believe that these short-term projects are crucial to robustly build the geometric processing tools necessary to develop our research theme further.

Relevance of proposal. Our research project will dovetail with ongoing activities between the parties involved in this proposal, further strengthening them, and in turn benefit from the synergies. The repeated previous collaborations between Dr Alliez, Dr Cohen-Steiner, Dr Yvinec and Prof Desbrun have already demonstrated success and complementarity of research skills and knowledge. We believe that with additional seed money provided by this program, we can develop much stronger and durable research efforts that will benefit not only the researchers involved, but the students of their respective teams. See the Impacts section below.

2. Partners

Coordinators

At the foreign partner: Mathieu Desbrun is an Associate Professor in the Computer Science Department at the California Institute of Technology (Caltech). His research focuses on geometry processing and physics-based simulation. He is the head of the Applied Geometry lab at Caltech, collaborating with and coadvising students in applied mathematics, mathematics, and dynamical systems. Prof. Desbrun completed his MSc, MEng, and PhD degrees at the Institut National Polytechnique de Grenoble in France in computer science. He has served on the organizational and programming committees of leading international conferences in computer graphics such as SIGGRAPH, EUROGRAPHICS, Viz, SGP, SCA, etc. He has also served as an associate editor for ACM Trans. on Graphics for the last five years. He received the ACM SIGGRAPH Significant New Researcher award in 2003.

At the INRIA partner: Pierre Alliez is a researcher at the GEOMETRICA project-team of INRIA Sophia Antipolis - Mediterranee, France. His research interests include various topics commonly referred to as geometry processing: Surface reconstruction, mesh generation, surface remeshing, mesh parameterization, mesh compression. He studied Image Processing, Computer Vision and Computational Geometry at the University of Nice Sophia-Antipolis, France, where he received his MS degree in 1997. He was awarded a Ph.D. in Image and Signal Processing in 2000 from the Ecole Nationale Superieure des Telecommunications, Paris. He then spent a year as a post-doctoral researcher at the University of Southern California with Mathieu Desbrun. Dr. Alliez has served on various program committees, including EUROGRAPHICS, SIGGRAPH and the Symposium on Geometry Processing. He was co-chair of the Symposium on Geometry Processing 2008. He received the EUROGRAPHICS Young Researcher award in 2005.

Existing collaboration

GEOMETRICA and Caltech have a long, steady history of collaborations, dating back to the postdoctoral position that Dr Alliez held in Prof Desbrun's research lab. Since then, a regular stream of collaborations have happened with Pierre Alliez, David Cohen-Steiner and Mariette Yvinec, resulting in publications in premier venues such as SIGGRAPH, EUROGRAPHICS and Symposium on Geometry Processing. Prof. Desbrun has visited Sophia-Antipolis nearly once a year since 2001, staying 3 or 4 days at a time. Prof Peter Schröder, head of the Multires Modeling Group at Caltech, spent five weeks as invited professor at GEOMETRICA in the summer of 2005. Last summer, Patrick Mullen (a student of Prof Desbrun) spent two months to start a collaboration with Dr Alliez. Finally, Jean-Philippe Pons (a post-doc student of Dr. Boissonnat) spent two months in the Applied Geometry lab at Caltech. Despite these constant interactions, most of the collaborations were restricted to short-term projects that did not involve graduate students. This proposal reflects a common effort to intensify and solidify our collaborations.

Personnel and Webpages.

At Caltech the people interested by the collaborations are:
- M. Desbrun (head)
- P. Schröder (Professor)
- J. Marsden (Professor)
- L. Kharevych (student)
- P. Mullen (student)
- K. Crane (student)
- D. Pavlov (student)
- A. Stern (student).
Publications and people involved on the Caltech side can be found at: http://www.geometry.caltech.edu/

At INRIA the people are:
- P. Alliez (researcher, coordinator of the proposal)
- M Yvinec (researcher)
- D. Cohen-Steiner (researcher)
- J. Tournois (student)
- N. Salman(student)

3. Potential Impacts

On students. Closer links between our two teams will foster international experience of our graduate students, an increasingly important part of research training nowadays. Later, offering postdoctoral positions for these students will be another added benefit. Finally, cross-pollination of our respective teams' style and expertise will offer a stimulating research environment, enhancing the graduate experience of our students and thus making our respective labs more attractive to prospective graduate students.

On CGAL. We also expect positive impact on the CGAL project, as both teams are fervent adept of the library: This enhanced collaboration will produce added distribution (in academia and industry) of the library in the US. We plan on co-teaching courses in premier venues using CGAL as a basic framework for learning and exploring to further publicize the library and the new tools we will add on.

On our community. Our presence in France and in the USA gives us the opportunity to help coordinate international workshops and symposia. In particular, both of our teams have been heavily involved in the Symposium of Geometry Processing (as paper chairs and organizer) and we wish to continue this important endeavor to further develop and grow our community. Discussions about Lyon as the location of SGP 2010 have started, and both our teams are involved in helping the coordination of this event. Smaller, more focused events could be held in future years at Caltech and Sophia-Antipolis, and our ties will guarantee a good representation of both European and American partners.

Others. Finally, we believe that the experience of the Caltech team in exploiting geometric tools for computational science applications in mechanics, fluids, and E&M as well as the multiple industrial collaborations that GEOMETRICA has developed over the years will further leverage the results of this research effort.

For 2009 we intend to carry on research along three main directions:

• Fast, Scalable Methods for Parameterization: P. Mullen, M. Desbrun, P. Alliez, in collaboration with Christian Mercat from Université de Montpellier. Our goal is to obtain a more expressive formulation for conformal parameterizations than current linear methods, using a dual / primal approach introduced by C. Mercat. Such a method is key to maintain low computational cost (to handle larger and larger meshes) while avoiding the rank-deficiency of current fast methods, in order to produce a fast yet cheap and controllable tool for mesh parameterization.
• Robust Tetrahedral meshing (M. Desbrun, J. Tournois, P. Alliez, M. Yvinec): We wish to bootstrap our existing mesh optimization techniques using the refinement-based versatile framework introduced by Yvinec and co-workers. Automatic generation of high quality isotropic tetrahedral meshes through interleaving Delaunay refinement and mesh optimization is sought for spatial domains bounded by point set surfaces, implicit functions, polyhedral surfaces and isosurfaces in 3D images.
• Universal Error-bounded Simplification of Discrete Geometric Data (D. Cohen-Steiner, P. Mullen, M. Desbrun, P. Alliez): The goal is to simplify and/or repair a large variety of inputs (point sets, triangle soup, multiple reconstructions of the same object), with guaranteed error bounds. Such a processing is a necessary first step in a multitude of problems in reverse engineering. Emphasis will be put on the error metric (notion of tolerance envelope, symmetric vs one-sided Hausdorff distance, etc) and on the robustness of the method.
• Hexahedral meshing (P. Mullen, M. Desbrun, D. Cohen-Steiner, P. Alliez): Building upon our experience in generation of surface quadrangle tilings with harmonic one-forms, we intend to start developing an automatic technique for generating isotropic hexahedral meshes, for which a control on the valence irregularities is offered to the user.
  
  
• In addition, we intend to submit a course at SIGGRAPH or EUROGRAPHICS (the precise content will depend on our current research progress).