Mardi 14 Décembre 2004 à 14h00, salle S16 (Passage Saumon, niveau -1)
-
Orateur :
G. Vegter (University of Groningen, The Netherlands)
-
Titre :
Certified meshing of implicit surfaces
- Résumé :
In this talk we present our recent work on certified meshing of implicit
surfaces. These meshing algorithms generate piecewise linear approximations
of an implicit surface that are homeomorphic, and even isotopic to this
surface.
This guaranteed (certified) topology is a distinctive feature of our methods,
contrary to existing isosurface extraction algorithms, like the celebrated
marching cubes algorithm
Implicit surfaces are widely used to model geometric objects like
molecules in biomolecular modeling, smooth surfaces reconstructed from MRI-data
in
image-guided surgery, or car parts in CAD/CAM-systems.
The representation of a geometric object as an implicit surface, i.e.,
as an isosurface of a real-valued functions in three-space, may be
very convenient for such physical or technical applications.
However, for further geometry processing, like rendering the object on a
computer screen or performing numerical simulations, it may be more convenient
to have a piecewise linear (meshed) approximation of the object. Therefore,
fast and reliable meshing algorithms have immediate applications in these
practical situations.
All our algorithms compute a piecewise linear approximation of the implicit
surface by using special subdivisions of three-space,
adapted to the geometry of the object.
Different meshing methods are obtained by chosing different subdivisions.
The presentation is complemented by some demo's showing the feasibility of our
approach in practice.
This is a survey of joint work with Jean-Daniel Boissonnat (INRIA, Sophia
Antipolis, France), David Cohen-Steiner (Duke University, Durham, USA), Nico
Kruithof and Simon Plantinga (Groningen University).
Mardi 09 Novembre 2004 à 14h00, salle S16
(Passage Saumon, niveau -1)
- Orateur :
Frédéric Chazal - Institut de Mathématiques de Bourgogne
- Titre :
"Détermination de la topologie des solides de R^n à partir d'approximation"
- Résumé :
Le travail présenté dans cet exposé est motivé par la question suivante.
``Etant donné un solide dans R^n (i.e. un ouvert borné),
peut-on déterminer
sa topologie à partir d'une approximation (pour la distance de Hausdorff)
de son bord?''.
Par exemple, le solide peut être un objet dans R^3 et l'approximation de son
bord un nuage de points bruités prélevés sur sa surface à l'aide d'un scanner.
On introduit la notion de ``weak feature size (wfs)'' d'un ouvert qui généralise la notion de local feature size (lfs) introduite par N. Amenta et on donne
une réponse affirmative à la question précédente pour les ouverts dont le wfs est strictement positif. Le wfs d'un ouvert O est défini comme la distance du
bord de O à l'ensemble des points critiques de la fonction
``distance au bord de O''.
Contrairement au lfs qui est généralement nul pour les ouverts dont le bord
n'est pas une variété lisse, le wfs est strictement positif pour une classe assez large d'ouverts parmi lesquels on trouve les ouverts à bord polyédrique et
les ouverts à bord analytique par morceaux. Les techniques utilisées pour prouver les résultats présentés dans cet exposé reposent sur l'étude des fonctions
``distance à un fermé dans R^n'' et de leurs points critiques. Dans notre contexte, la notion de point critique est celle classiquement utilisée pour les
fonctions distance en géométrie riemannienne (Grove-Shiohama, Cheeger,...).
A titre d'application, on montrera comment nos résultats, combinés à des tehniques de persistance topologique (Edelsbrunner-Zomorodian) et à des résultats
sur la stabilité de l'axe médian (Chazal-Lieutier), permettent d'obtenir un algorithme de calcul des groupes d'homologie d'un ouvert borné à wfs>0 à partir
d'un nuage de points bruités échantillonné sur son bord.
Travail commun avec André Lieutier - Dassault Systèmes
Une version préliminaire de ce travail est accessible à
http://math.u-bourgogne.fr/topo/chazal/publications.htm
Mardi 26 octobre 2004 à 14h00, Salle S16
(Passage Saumon, niveau -1)
- Orateur: Jeff Erickson, University of Illinois at Urbana-Champaign
- Titre : "Optimal Homotopy and Homology Generators"
- Résumé :
Many geometric problems, such as texture mapping, remeshing, and
morphing, call for a topologically complex surface to be cut into one
or more topological disks. Any orientable surface of genus g can be
cut into a single topological disk by removing a so-called "system of
loops": a set of 2gs cycles sharing a common basepoint. I will
describe a simple greedy algorithm based on Dijkstra's shortest-path
algorithm that computes the shortest system of loops with a given
basepoint in O(n log n) time. This solves an open problem of Colin de
Verdière and Lazarus. In fact, our algorithm computes the shortest set
of loops that generate the fundamental group of the surface. It is
also possible to cut a surface into a single disk with a more general
graph, but finding such a cut graph with minimum total length is
NP-hard.
This is joint work with Kim Whittlesey, to appear at SODA 2005.
Our paper is available at
http://www.cs.uiuc.edu/~jeffe/pubs/gohog.html