Sampling and Meshing Surfaces with Guarantees - Archive ouverte HAL Access content directly
Theses Year : 2005

Sampling and Meshing Surfaces with Guarantees

Échantillonnage et maillage de surfaces avec garanties

(1)
1
Steve Y. Oudot
  • Function : Author
  • PersonId : 845393

Abstract

In the last decade, a great deal of work has been devoted to the elaboration of a sampling theory for smooth surfaces. The goal was to work out sampling conditions that ensure a good reconstruction of a given smooth surface S from a finite subset E of S. Among these conditions, a prominent one is the e-sampling condition of Amenta and Bern, which states that every point p of S is closer to E than e times lfs(p), where lfs(p) is the distance of p to the medial axis of S. Amenta and Bern proved that it is possible to extract from the Delaunay triangulation of E a PL surface that approximates S both topologically and geometrically. Nevertheless, the important issues of checking whether a given point set is an e-sample, and constructing e-samples of a given smooth surface, have never been addressed. Moreover, the sampling conditions proposed so far offer guarantees only in the smooth setting, since lfs vanishes at points where the surface is not differentiable. In this thesis, we introduce the concept of loose e-sample, which can be viewed as a weak version of the notion of e-sample. The main advantage of loose e-samples over e-samples is that they are easier to check and to construct. Indeed, checking that a finite set of points is a loose e-sample reduces to checking whether a finite number of spheres have small enough radii. When the surface S is smooth, we prove that, for sufficiently small e, e-samples are loose e-samples and vice-versa. As a consequence, loose e-samples offer the same topological and geometric guarantees as e-samples. We further extend our results to the nonsmooth case by introducing a new measurable quantity, called the Lipschitz radius, which plays a role similar to that of lfs in the smooth setting, but which turns out to be well-defined and positive on a much larger class of shapes. Specifically, it characterizes the class of Lipschitz surfaces, which includes in particular all piecewise smooth surfaces such that the normal variation around singular points is not too large. Our main result is that, if S is a Lipschitz surface and E is a point sampling of S such that any point p of S has a distance to E that is less than a fraction of the Lipschitz radius of S, then we obtain similar guarantees as in the smooth setting. More precisely, we show that the Delaunay triangulation of E restricted to S is a 2-manifold isotopic to S lying at Hausdorff distance O(e) from S, provided that its facets are not too skinny. We also extend our previous results on loose samples. Furthermore, we are able to give tight bounds on the size of such samples. To show the practicality of the concept of loose e-sample, we present a simple algorithm that constructs provably good surface meshes. Given a compact Lipschitz surface S without boundary and a positive parameter e, the algorithm generates a sparse loose e-sample E and at the same time a triangular mesh extracted from the Delaunay triangulation of E. Taking advantage of our theoretical results on loose e-samples, we can guarantee that this triangular mesh is a good topological and geometric approximation of S, under mild assumptions on the input parameter e. A noticeable feature of the algorithm is that the input surface S needs only to be known through an oracle that, given a line segment, detects whether the segment intersects the surface and, in the affirmative, returns the intersection points. This makes the algorithm useful in a wide variety of contexts and for a large class of shapes. We illustrate the genericity of the approach through a series of applications: implicit surface meshing, polygonal surface remeshing, unknown surface probing, and volume meshing.
Cette dernière décennie a vu apparaître et se développer toute une théorie sur l'échantillonnage des surfaces lisses. L'objectif était de trouver des conditions d'échantillonnage qui assurent une bonne reconstruction d'une surface lisse S à partir d'un sous-ensemble fini E de points de S. Parmi ces conditions, l'une des plus importantes est sans conteste la condition d'e-échantillonnage, introduite par Amenta et Bern, qui stipule que tout point p de S doit être à distance de E au plus e fois lfs(p), où lfs(p) désigne la distance de p à l'axe médian de S. Amenta et Bern ont montré qu'il est possible d'extraire de la triangulation de Delaunay d'un e-échantillon E une surface affine par morceaux qui approxime S du point de vue topologique (isotopie) et géométrique (distance de Hausdorff). Néanmoins restaient ouvertes les questions cruciales de pouvoir vérifier si un ensemble de points donné est un e-échantillon d'une part, et de construire des e-échantillons d'une surface lisse donnée d'autre part. De plus, les conditions d'échantillonnage proposées jusque là n'offraient des garanties que dans le cas lisse, puisque lfs s'annule aux points où la surface n'est pas différentiable. Dans cette thèse, nous introduisons le concept d'e-échantillon lâche, qui peut être vu comme une version faible de la notion d'e-échantillon. L'avantage majeur des e-échantillons lâches sur les e-échantillons classiques est qu'ils sont plus faciles à vérifier et à construire. Plus précisément, vérifier si un ensemble fini de points est un e-échantillon lâche revient à regarder si les rayons d'un nombre fini de boules sont suffisamment petits. Quand la surface S est lisse, nous montrons que les e-échantillons sont des e-échantillons lâches et réciproquement, à condition que e soit suffisamment petit. Il s'ensuit que les e-échantillons lâches offrent les mêmes garanties topologiques et géométriques que les e-échantillons. Nous étendons ensuite nos résultats au cas où la surface échantillonnée est non lisse en introduisant une nouvelle grandeur, appelée rayon Lipschitzien, qui joue un rôle similaire à lfs dans le cas lisse, mais qui s'avère être bien défini et positif sur une plus large classe d'objets. Plus précisément, il caractérise la classe des surfaces Lipschitziennes, qui inclut entre autres toutes les surfaces lisses par morceaux pour lesquelles la variation des normales aux abords des points singuliers n'est pas trop forte. Notre résultat principal est que, si S est une surface Lipschitzienne et E un ensemble fini de points de S tel que tout point de S est à distance de E au plus une fraction du rayon Lipschitzien de S, alors nous obtenons le même type de garanties que dans le cas lisse, à savoir : la triangulation de Delaunay de E restreinte à S est une variété isotope à S et à distance de Hausdorff O(e) de S, à condition que ses facettes ne soient pas trop aplaties. Nous étendons également ce résultat aux échantillons lâches. Enfin, nous donnons des bornes optimales sur la taille de ces échantillons. Afin de montrer l'intérêt pratique des échantillons lâches, nous présentons ensuite un algorithme très simple capable de construire des maillages certifiés de surfaces. Etant donné une surface S compacte, Lipschitzienne et sans bord, et un paramètre positif e, l'algorithme génère un e-échantillon lâche E de S de taille optimale, ainsi qu'un maillage triangulaire extrait de la triangulation de Delaunay de E. Grâce à nos résultats théoriques, nous pouvons garantir que ce maillage triangulaire est une bonne approximation de S, tant sur le plan topologique que géométrique, et ce sous des hypothèses raisonnables sur le paramètre d'entrée e. Un aspect remarquable de l'algorithme est que S n'a besoin d'être connue qu'à travers un oracle capable de détecter les points d'intersection de n'importe quel segment avec la surface. Ceci rend l'algorithme assez générique pour être utilisé dans de nombreux contextes pratiques et sur une large gamme de surfaces. Nous illustrons cette généricité à travers une série d'applications : maillage de surfaces implicites, remaillage de polyèdres, sondage de surfaces inconnues, maillage de volumes.
Fichier principal
Vignette du fichier
thesis_Oudot.pdf (9.09 Mo) Télécharger le fichier
Loading...

Dates and versions

tel-00338378 , version 1 (13-11-2008)

Identifiers

  • HAL Id : tel-00338378 , version 1

Cite

Steve Y. Oudot. Sampling and Meshing Surfaces with Guarantees. Software Engineering [cs.SE]. Ecole Polytechnique X, 2005. English. ⟨NNT : ⟩. ⟨tel-00338378⟩
443 View
236 Download

Share

Gmail Facebook Twitter LinkedIn More