Projet soutenu par le programme blanc 2007 de l' du 1er novembre 2007 au 31 mai 2011. ANR-07-BLAN-0319ANR-BLAN07-2_194137















Le rapport final du projet

Objectifs

Les triangulations sont essentielles par leurs applications notamment pour les maillages et la reconstruction de formes. Nous voulons développer et mettre à disposition des chercheurs académiques et industriels de nouveaux résultats. En particulier, concernant les triangulations de points en mouvement. Le but du projet est le développement d'algorithmes robustes et efficaces pour la manipulaion de grands ensembles de points, d'ensembles de points mobiles et de points dans des espaces non euclidiens tel que des espaces périodiques (tore, cylindre), des espaces projectifs, projectifs orientés ou hyperboliques. Les résultats obtenus seront implantés à l'aide de la bibliothèque CGAL et seront appliquées dans le domaine de la vision (enveloppes visuelles, calibration de caméra), de la dynamique des fluides, de l'astronomie, de l'infographie ou encore pour des applications dans le domaine médical.

Participants

Manuel Caroli (doctorant). Olivier Devillers (responsable). Hervé Guillard. Pedro Machado Manhães de Castro (doctorant cofinancé région PACA / ANR Triangles). Jean-Marie Morvan (collaborateur extérieur, Univ. Lyon 1). Sylvain Pion. Monique Teillaud.

Raphaëlle Chaine (responsable locale). Pierre-Marie Gandoin. Clément Jamin (doctorant). Lucian Stanculescu (doctorant, financé par l'ANR Triangles). Jean-Michel Moreau.

Département d'informatique de l' Éric Colin de Verdière. Jean Ponce (responsable local).

Logiciels

• Manuel Caroli and Monique Teillaud. 3D Periodic Triangulations. In CGAL Editorial Board, editor, CGAL User and Reference Manual. 3.5 and 3.6 edition, 2009 and 2010.

Thèses

• Abdelkrim Mebarki, Implantation des structures de données compactes pour les triangulations, Université de Nice-Sophia Antipolis, 15 avril 2008.
• Clément Jamin, Algorithmes et structures de données compactes pour la visualisation interactive d'objets 3D volumineux, Université de Lyon, 25 septembre 2009.
• Pedro Machado Manhães de Castro, Practical Ways to Accelerate Delaunay Triangulations, Université de Nice-Sophia Antipolis, 25 octobre 2010.
• Manuel Caroli, Triangulating Point Sets in Orbit Spaces, Université de Nice-Sophia Antipolis, 10 décembre 2010.

Publications

• Yasutaka Furukawa and Jean Ponce. Accurate, Dense, and Robust Multi-View Stereopsis. submitted to IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009.
• Jean-Marie Morvan. On exteriorly orthogonal forms. soumis a SIGMA (volume à la mémoire d' E. Cartan).
• Manuel Caroli and Monique Teillaud. Delaunay triangulations of point sets in closed Euclidean d-manifolds. Proceedings 27th Annual Symposium on Computational Geometry (SoCG), June 2011.
• Éric Colin de Verdière. Shortest cut graph of a surface with prescribed vertex set. Proc. European Symposium on Algorithms (ESA), 2010, vol. 2, p. 100-111.
• Manuel Caroli, Vissarion Fisikopoulos, and Monique Teillaud. Meshing of Triply-Periodic Surfaces in CGAL. In Seventh International Conference on Curves and Surfaces, 2010. Poster presentation.
• Manuel Caroli, Pedro M. M. de Castro, Sébastien Loriot, Olivier Rouiller, Monique Teillaud, and Camille Wormser. Robust and Efficient Delaunay Triangulations of Points on or Close to a Sphere. In 9th International Symposium on Experimental Algorithms, 2010. Also Research Report 7004, INRIA, 2009.
• Manuel Caroli and Monique Teillaud. Delaunay triangulations of point sets in closed Euclidean d-manifolds. In Abstracts 26th European Workshop on Computational Geometry, 2010. Long version available as Research Report 7352, INRIA, 2010.
• Yasutaka Furukawa and Jean Ponce. Dense 3D Motion Capture for Human Faces. In IEEE Conference on Computer Vision and Pattern Recognition, 2009.
• Jean Ponce, What is a camera? Proc. IEEE Conf. on Computer Vision and Pattern Recognition, 2009
• Pedro Machado Manhães de Castro, Olivier Devillers, Jane Tournois, and Pierre Alliez. Filtering relocations on a Delaunay triangulation. Symposium on Geometry Processing, Berlin 2009.
• Manuel Caroli and Monique Teillaud. Computing 3D Periodic Triangulations. 17th European Symposium on Algorithms (ESA'09), volume 5757 of Lecture Notes in Computer Science, pages 37-48, Copenhagen 2009. Also Research Report 6823, INRIA, 2009.
  Monique Teillaud. Talk at the Mittagsseminar, Institute of Theoretical Computer Science, ETH Zurich, September 2009.
  Manuel Caroli. Talk at the Workshop Subdivide and Tile: Triangulating spaces for understanding the world, Lorentz Center, Leiden, November 2009.
• Clément Jamin, Pierre-Marie Gandoin, Samir Akkouche. CHuMI Viewer: Compressive Huge Mesh Interactive Viewer. Computer & Graphics. 2009
• Clément Jamin, Pierre-Marie Gandoin, Samir Akkouche. Compression out-of-core pour la visualisation interactive de maillages volumineux. REFIG (Revue Électronique Francophone d'Informatique Graphique). 2009
• Yasutaka Furukawa and Jean Ponce. Accurate Camera Calibration from Multi-View Stereo and Bundle Adjustment. International Journal of Computer Vision, 2009.
• Vicente H. F. Batista, David L. Millman, Sylvain Pion, and Johannes Singler. Parallel Geometric Algorithms for Multi-Core Computers. 25th Symposium on Computational Geometry, Aarhus, June 2009.
• Raphaëlle Chaine, Pierre-Marie Gandoin, Céline Roudet. Reconstruction Algorithms as a Suitable Basis for Mesh Connectivity Compression. IEEE Transactions on Automation Science and Engineering, 2009.
• Clément Jamin, Pierre-Marie Gandoin, Samir Akkouche. A Compact Data Structure For The Navigation Into Arbitrary Meshes. Rapport de recherche RR-LIRIS-2008-014, 2008.
• Pedro Machado Manhães De Castro and Olivier Devillers. Delaunay Triangulations for Moving Points. Research Report 6750, INRIA, 2008.
• Vicente H. F. Batista, David L. Millman, Sylvain Pion and Johannes Singler. Parallel Geometric Algorithms for Multi-Core Computers. Research Report 6749, INRIA, 2008.
• Olivier Devillers and Pedro Machado Manhães De Castro. State of the Art: Updating Delaunay Triangulations for Moving Points. Research Report 6665, INRIA, 2008.
• Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus and Shripad Thite. Walking your dog in the woods in polynomial time. Proc. 24th Annual Symposium on Computational Geometry (SoCG'08), juin 2008.
• Manuel Caroli and Monique Teillaud. Video: On the Computation of 3D Periodic Triangulations. In Proc. 24th Annual Symposium on Computational Geometry (SoCG'08), 2008. Video available on the Computational Geometry Web Pages.
• Manuel Caroli, Nico Kruithof, and Monique Teillaud. Triangulating the 3D periodic space. In 24th European Workshop on Computational Geometry (EuroCG'08), 2008.
• Manuel Caroli, Nico Kruithof, and Monique Teillaud. Decoupling the CGAL 3D Triangulations from the Underlying Space. In Workshop on Algorithm Engineering and Experiments (ALENEX'08), pages 101-108, 2008.
• Yasutaka Furukawa and Jean Ponce. Accurate Camera Calibration from Multi-View Stereo and Bundle Adjustment. CVPR, 2008.
• Yasutaka Furukawa and Jean Ponce. Dense 3D Motion Capture from Synchronized Video Streams. CVPR, 2008.
• Nina Amenta, Dominique Attali, and Olivier Devillers. A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron. Research Report 6522, INRIA, 2008.
• Mridul Aanjaneya and Monique Teillaud. Triangulating the Real Projective Plane. In Mathematical Aspects of Computer and Information Sciences (MACIS'07), 2007.

Réunions

Workshop de clôture en collaboration avec OrbiCG, INRIA-Sophia-Antipolis, 8-10 Décembre 2010.

Quatrième réunion le 24 septembre 2009 au LIRIS batiment Nautibus, salle de réunion, 2ème étage. Liste d'hôtels.

• programme
• ..9h30 Accueil, Introduction
• 09h40 Jean-Marie Morvan : Plan projectif.
• 10h20 Manuel Caroli : Triangulations périodiques.
• 11h00 pause et discussions sur les espaces non euclidiens:
• 11h40 Jean Ponce : Beyond space carving.
• 12h20 repas :
• 14h00 Olivier Devillers : Optimisation de la suppression d'un sommet dans Delaunay 2D.
• 14h40 Raphaëlle Chaine, Sébastien Valette : Progressive Lossless Mesh Compression Via Incremental Parametric Refinement (sous reserves)
• 15h20 Lucian Stanculescu : Triangulation de surface en mouvement et application à la modélisation interactive 3D (sous reserves)
• 16h00 Discussion scientifique et d'organisation (budget, prochaine réunion...)
• 17h20 fin. train des sophopolitains à 18h03 à Part-Dieu
• 25 septembre 2009,
• 14h00 Soutenance de thèse de Clément Jamin : Algorithmes et structures de données compactes pour la visualisation interactive d'objets 3D volumineux.
  Jury : Olivier Devillers, Dominique Michelucci, Bruno Lévy, Jean Séqueira, Samir Akkouche, Pierre Marie Gandoin.
  

Troisième réunion le 23 janvier 2009 au Département d'informatique de l' ENS Aile Rataud, passage saumon, salle S16. .

Liste d'hôtels pas trop chers dans les environs (sans aucune garantie -- les prix peuvent avoir changé) :
• Hôtel Pierre Nicole ** 65 Euros 39 rue Pierre Nicole 75005 Paris Métro : Port Royal tél. 33 1 43 54 76 86
• Hôtel de l'Espérance ** 79 Euros 15 rue Pascal 75005 Paris Métro : Les Gobelins tél. 33 1 47 07 10 99 fax : 01 43 37 56 19
• Hôtel Sunny 60 Euros 48 Boulevard de Port Royal 75005 Paris Métro : Port Royal tél. 33 1 43 31 79 86 fax 33 1 43 31 36 02
• Hôtel de France ** 65 Euros 108 rue Monge 75005 Paris Métro : Censier Daubenton tél. 33 1 47 07 19 04 fax 33 1 43 36 62 34
• Hôtel Diana 68 Euros 73 rue St Jacques, 75005 Paris tél. 33.1.42 54 92 55 www.hotel-diana-paris.com
• Hôtel Gay Lussac 65 Euros 29 rue Gay Lussac, 75005 Paris tél. 33.1.43 54 23 96 fax 33.1.40 51 79 49

• programme
• ..9h30 Accueil
• 09h45 Olivier Devillers : Introduction
• 09h50 Jean Ponce : Comment modéliser "toutes les caméras possibles" par des complexes de lignes droites
• 10h40 Pedro Machado Manhães de Castro : Mise à jour de triangulation de points mobiles.
• 11h30 Clément Jamin: Compression et visualisation de très gros maillages
• 14h00 Jean-Marie Morvan : Triangulation et plan projectif. (annulé)
• 14h00 Sylvain Pion : Geometric Algorithms for Multi-Core Computers
• 15h00 Discussion scientifique
• 16h30 Organisation (budget, prochaine réunion...)

Workshop (avec le soutien de Triangles) CGAL Prospective Workshop on Geometric Computing in Periodic Spaces , INRIA-Sophia-Antipolis, 20 Octobre 2008.

Seconde réunion le 14 avril 2008 au CRISAM salle Byron beige (avec prolongations le 15 pour certains).

• programme
• 14 avril 2008
• ..9h30 Accueil
• 10h00 Olivier Devillers : Introduction
• 10h10 Pedro Machado Manhães de Castro : Mise à jour de triangulation de points mobiles.
• 10h50 Sylvain Pion : Triangulation de Delaunay en parallèle.
• 11h20 pause
• 11h40 Manuel Caroli : Triangulations périodiques, démo.
• 12h10 Clément Jamin : Visualisation de triangulations volumineuses
• 13h00 Repas
• 14h00 Discussion scientifique
• 15h30 Organisation (budget, prochaine réunion...)
• 16h00 Monique Teillaud : Compte-rendu de l'article: Voronoi diagrams on orbifolds (M. Mazon, T. Recio, CGTA 1997)
• 16h30 le thé
• 17h?? Fin
• 15 avril 2008, amphi Kahn
• 10h00 Soutenance de thèse d'Abdelkrim Mebarki : Implantation des structures de données compactes pour les triangulations.
  Jury : Luca Castelli Aleardi, Olivier Devillers, Jérôme Galtier, André Lieutier, Jean-Michel Moreau.
  La modélisation des objets géométriques est incontournable dans de nombreuses disciplines et applications. L'évolution des moyens d'acquisition et de stockage a produit une hausse énorme des volumes utilisés pour stocker ces objets. La réduction des tailles de ces volumes fait l'objet de plusieurs domaines de recherches ; comme la compression, qui vise à comprimer le volume au maximum, et l'élaboration de structures théoriques compactes qui minimise la taille nécessaire à la représentation. Le but de cette thèse est de concevoir, et d'évaluer des solutions pratiques et exploitables pour représenter de façon compacte les triangulations. Pour ce faire, deux issues sont explorées: modifier la représentation interne en mémoire des objets géométriques, et redéfinir les types abstraits des objets géométriques correspondants. Une première solution consiste à utiliser des numéros sur une taille arbitraire de bits, au lieu des références absolues. Les gains dépendent de la taille de la triangulation, et aussi de la taille du mot mémoire de la machine. Le handicap majeur est le coût élevé de la méthode en termes de temps d'execution. Une deuxième piste consiste à utiliser des catalogues stables. L'idée consiste à regrouper les triangles dans des paquets, et de représenter la triangulation comme un ensemble de ces paquets. Le nombre des références multiples vers les sommets, et des références réciproques entre voisins est alors nettement réduit. Les résultats sont prometteurs, sachant que le temps d'execution n'est pas dramatiquement altéré par la modification des méthodes d'accès aux triangles. Une troisième solution consiste à décomposer la triangulation en plusieurs sous-triangulations permettant ainsi de coder les références dans une sous-triangulation sur un nombre réduit de bits par rapport aux références absolues. Les résultats de cette techniques sont encourageants, et peuvent être amplifiés par d'autres techniques comme le codage relatif des références, ou le partage des sommets sur les bords entre les différentes sous-triangulations. L'élaboration de structures compactes nécessite encore plus d'intérêts, et plusieurs pistes sont à explorer pour pouvoir arriver à des solutions plus économiques en termes d'espace mémoire.

Première réunion le 6 décembre 2007 au LIRIS batiment Nautibus, salle de réunion, 2ème étage. Liste d'hotels.

• ..9h30 Accueil
• 10h00 Olivier Devillers : Introduction
• 10h10 Raphaëlle Chaine : Delaunay tetraheadralization of a deforming surface.
• 10h40 Monique Teillaud : Triangulations in the projective plane.
• 11h10 Jean Ponce : Reconstruction de surfaces stereo et triangulations.
• 11h40 Manuel Caroli : Triangulations in 3D periodic spaces.
• 12h10 Repas
• 14h00 Discussion scientifique
• 16h30 Organisation (budget, prochaine réunion...)
• 17h00 Fin