11

PRISME

Géométrie, Algorithmes et Robotique

• Acteurs

• Contexte

• Projet scientifique

• Résultats marquants 1998-2002

• Perspectives

22

LES ACTEURS

Jean-Daniel Boissonnat Olivier Devillers Jean-Pierre Merlet Saga/Coprin (98) Monique Teillaud Galaad (01)Mariette Yvinec CNRS

Frédéric Cazals (98)Raphaëlle Chaine (MdC, 00)Pierre Alliez (01)

Anne Verroust (Rocquencourt)

33

CONTEXTE

• La révolution des objets géométriques

• L’importance des questions combinatoires et algorithmiques

• L’antagonisme fiabilité / performances

• L’émergence de nouveaux sujets d’étude : échantillonnage, approximation, compression

44

PROJET SCIENTIFIQUE

Développer le calcul géométrique

Algorithmique effective

Calcul géométrique fiable

Approximation géométrique

55

Algorithmique effective

* combinatoire dans des situations pratiques* analyses théoriques réalistes (e.g. randomisation)* expérimentations et optimisation des performances

Calcul géométrique fiable

* choix des prédicats et formulation algébrique* arithmétique exacte filtrée [S. Pion]* arrondis certifiés des opérations élémentaires [P. Guigue]Approximation géométrique

* triangulations et maillages [S. Balaven, D. Cohen-Steiner, D. Amar]* interpolation et reconstruction de surfaces [F. Da, J. Flöttoto]* compression de modèles géométriques [P-M. Gandoin]

66

CALCUL GEOMETRIQUE AVEC

Computational

http://www.cgal.org

Geometric Algorithms

A C++

Library

77

XYZ GeobenchPlageo

C++GALLEDA

Les précurseurs de CGAL

[Carleton]Workbench for CG Gems [Minneapolis]

ZurichUtrechtINRIASarrebrüken

2 projets Européens CGALNov97-Avr98

GALIANov98-Avr00

88

CGAL : Instrument logiciel

SUPPORT BIBLIOTHEQUEDE BASE

NOYAU

Arithmétiques

I/OVisu

STLext.

CartesplanairesArrangements

Triangulations

Env. ConvexeLP, QP solver

Structures derecherche

GISRobotique

OptimisationGéométrique

ReconstructionMaillage

99

Paramètrespar défaut

prédicats + constructeursAnalyse

Robustesse

Filtres

Arithmétiques exactes

Programmation générique classes de caractéristiquescombinatoire + géométrie

Flexibilitéprédicatsexacts

Efficacité

Simplicité

filtrés

prédicats + constructeursAnalyse

CGAL : Calcul géométrique générique et fiable

1010

Arithmétiques de CGAL Thèse de S. Pion

Random2M

Buddha0.5 M

Dryer0.05 M

double 177 50 loop

MP-Float 12500 3500 210

Interval + MP-Float 570 165 16

Static + Interval+ MP-Float 200 60 8

Shewchuk expansions 249 72 7

Temps en secondes (Pentium III 1Ghz)

Triangulation de points dans 3R

1111

Applications des triangulations de CGAL

S. Balaven

Synthèse d’images, GIS, dynamique des fluides, biologie...

Génération automatique de maillages hybrides (IFP)

Thèse de

1212

•Cgal : un mammouth…

– 1 200 classes C++– 273 000 lignes de code– 1 100 pages de doc– 40 années-hommes

•... sans graisse

Delaunay 3D CGAL PYRAMID

1 M Points 90 s 300 s

Points par seconde 10 000 3000

Pentium III 1Ghz

1313

• avenir de CGAL

Futur de CGAL

• des ”extension packages” :- reconstruction- maillage

• objets courbes ECG, Galaad

• impact de CGAL :- enseignement- recherche - industrie

1414

RECONSTRUCTION DE SURFACES

1515

• Modélisation géométrique (Reverse engineering)• Tomographie, imagerie médicale et microscopique• Maillage de surfaces• Codage de modèles géométriques

Domaines d’applications :

1616

Historique

eighties graphes géométriques pour les nuages de points

1984 Delaunay pour la reconstruction de surfaces [JDB]

1992 Approche fonctionnelle [Hoppe et al.]

1998 Premier algorithme certifié en 3D (crust) [Amenta & Bern]

2000 Trois autres algorithmes certifiés Cocone [Dey et

al.]Power crust [Amenta et al.]Natural neighbour interpolation

Passage à l’échelle, produits commerciauxRaindrop Geomagic, Dassault Systèmes, projet

Michelangelo

1717

Reconstruction de surfaces quelques résultats

• Diagrammes de Voronoï de surfaces échantillonnées

• Interpolation de données non structurées• Combinatoire et algorithmique

1818

Voisinages

Del (E) est un polyèdre homéomorphe à S [Edelsbrunner & Shah]

Estimation des normales [Amenta & Bern] d’autres invariants de S

Approximation du squelette

|S

Diagrammes de Voronoï de surfaces échantillonnées

1919

Interpolation par les voisins naturels

[Sibson 80]

iεrx,B i i p xσ x

Interpolation :

•La distance de Hausdorff entre S et S tend vers 0 avec

•Reconstruction exacte de quadriques

xh xh(x) ii σ 0hS 1~ EDelS

S|~ˆ

ii i p x x σ

Si E est un échantillon de S

2020

Combinatoire et algorithmique

Surfaces polyédriques bien échantillonnées: borne linéaire

Borne supérieure quadratique

Performances : 3 temps de Delaunay200 000 points/mn

Localisation : jump & walk (skip lists)

Algorithme dynamique, randomisé

Mise à jour adaptative (idem calcul des coordonnées naturelles)

2121Dassault Systèmes

2222

2323

Surfaces non lisses

à bord

données bruitées

Echantillonnage et maillages de surfaces

Développements futurs et questions ouvertes

Interpolation sur des surfaces

2424

CODAGE / COMPRESSION

2525

Applications

Médical

Histoire de l'art

Visites virtuelles

CAO / Simulation

Topographie

Internet

Objet 3D

Modèle 3D

Flux ~ progressivitéVisualisation / simulation

2626

1 Parcours canonique du graphe2 Codage efficace de la connectivité3 Compression des positions des sommets dans l’ordre imposé par le codage

Pivot courant

Liste activeRégion conquise

Région libre

Etat de l’art

Compression de surfaces triangulées

2727

* Compression des positions* Codage (optionnel) de la connectivité* Généralisation aux maillages 3D

Approche originale: Thèse P.M. Gandoin

2828

• Algorithme compétitif pour les surfaces• Sans équivalent pour les données non structurées.

2% 23%7%4% (Sans perte)

2929

2% 20%15%6%

Sans perte

3030

3131

GAIN THEORIQUE

• hypothèse de distribution uniforme• coût du codage brut par point:• phase de séparation :

• phase de localisation :• gain par point : bits• borne inférieure (cas le pire)• information d’ordre sur les points

3232

Optimisation du rapport compression/distorsion

(lien avec l’approximation)

Optimalité du taux de compression sans perte

(surfaces/volumes)

Objectifs scientifiques en compression

3333

PERSPECTIVES I

* poursuite du développement de CGAL

* transmission et compression des objets géométriques

ARC TéléGéo

Thèmes prioritaires

* géométrie algorithmique effective pour les objets courbes

Projet IST ECG

Collaboration privilégiée avec Galaad

3434

PERSPECTIVES II

Maillages et calcul scientifique :

ARC VitesV, Color TechMesh, IFP

Ouverture vers de nouvelles applications

Réseaux

ARC TéléGéo

Modélisation géométrique en biologie

Journées Biogeo 19-20 mars

3535

PERSPECTIVES III

Un nouveau projet : Géométrica

commun avec l’ENS Ulm et I3S

(M. Pocchiola)