Search

We describe an algorithm which, for any piecewise linear complex (PLC) in 3D, builds a Delaunay triangulation conforming to this PLC. The algorithm has been implemented, and yields in practice a relatively small number of Steiner points due to the fact that it adapts to the local geometry of the PLC. It is, to our knowledge, the first practical algorithm devoted to this problem.

In this paper, we show that, amongst $n$ uniformly distributed unit balls in $\mathbb{R}^3$, the expected number of maximal nonoccluded line segments tangent to four balls is linear. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding the visibility information of a scene, providing evidence that the storage requirement for this data structure is not necessarily prohibitive. These results significantly improve the best previously known bounds of $O(n^{8/3})$ [F. Durand, G. Drettakis, and C. Puech, {ACM Transactions on Graphics}, 21 (2002), pp. 176--206]. Our results generalize in various directions. We show that the linear bound on the expected number of maximal nonoccluded line segments that are not too close to the boundary of the scene and tangent to four unit balls extends to balls of various but bounded radii, to polyhedra of bounded aspect ratio, and even to nonfat three-dimensional objects such as polygons of bounded aspect ratio. We also prove that our results extend to other distributions such as the Poisson distribution. Finally, we indicate how our probabilistic analysis provides new insight on the expected size of other global visibility data structures, notably the aspect graph.

We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganised sample points and normals. The method uses natural neighbour interpolation, works in any dimension and accommodates non-uniform samples. The reconstructed surface interpolates the data points and is implicitly represented as the zero set of some pseudo-distance function. It can be meshed so as to satisfy a user-defined error bound, which makes the method especially relevant for small point sets. Experimental results are presented for surfaces in R3.

The complexity of randomized incremental algorithms is analyzed with the assumption of a random order of the input. To guarantee this hypothesis, the n data have to be known in advance in order to be mixed what contradicts with the on-line nature of the algorithm. We present the shuffling buffer technique to introduce sufficient randomness to guarantee an improvement on the worst case complexity by knowing only k data in advance. Typically, an algorithm with O(n2) worst-case complexity and O(n) or O(n log n) randomized complexity has an [Formula: see text] complexity for the shuffling buffer. We illustrate this with binary search trees, the number of Delaunay triangles or the number of trapezoids in a trapezoidal map created during an incremental construction.

International audience; Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an exact and efficient method that determines the sign of a multivariate polynomial expression with rational coefficients. Exactness is achieved by using modular computation. Although this usually requires some multiprecision computation, our novel techniques of recursive relaxation of the moduli and their variants enable us to carry out sign determination and comparisons by using only single precision. Moreover, to exploit modern day hardware, we exclusively rely on floating point arithmetic, which leads us to a hybrid symbolic-numeric approach to exact arithmetic. We show how our method can be used to generate robust and efficient implementations of real algebraic and geometric algorithms including Sturm sequences, algebraic representation of points and curves, convex hull and Voronoi diagram computations and solid modeling. This method is highly parallelizable, easy to implement, and compares favorably with known multiprecision methods from a practical complexity point of view. We substantiate these claims by experimental results and comparisons to other existing approaches.

International audience; Suppose we are given n moving postmen described by their motion equations pi(t) = si + vi t, i=1, ... , n, where si belongs to R2 is the position of the i'th postman at time t=0, and vi in R2 is his velocity. The problem we address is how to preprocess the postmen data so as to be able to efficiently answer two types of nearest-neighbor queries. The first one asks ``who is the nearest postman at time tq to a dog located at point sq. In the second type a query dog is located at point sq at time tq, its speed is vq>|vi| (for all i=1, ... , n), and we want to know which postman the dog can catch first. The first type of query is relatively simple to address, the second type at first seems much more complicated. We show that the problems are very closely related, with efficient solutions to the first type of query leading to efficient solutions to the second. We then present two solutions to these problems, with tradeoff between preprocessing time and query time. Both solutions use deterministic data structures.

International audience; This paper is not a complete survey on randomized algorithms in computational geometry, but an introduction to this subject providing intuitions and references. In a first time, some basic ideas are illustrated by the sorting problem, and in a second time few results on computational geometry are briefly explained.

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle α centered around the specified direction. First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region R α (S) from where we can reach infinity with a directional uncertainty of α. We prove that the maximum complexity of R α (S) is O( n α 5 ) . Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k3m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of α. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.

http://www.springerlink.com/content/g22m7463281647rl/; Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the orderlek Voronoi diagrams, can be done in O(n logn+k 3n) expected time and O(k2n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k lceil(d+1)/2rceil+1 n lfloor(d+1)/2rfloor) and space complexityO(k lceil(d+1)/2rceil n lfloor(d+1)/2rfloor). The algorithm is simple and experimental results are given.

This paper deals with the approximation of the unfolding of a smooth globally developable surface (i.e. "isometric" to a domain of ${\Bbb E}^2$) with a triangulation. We prove the following result: let Tn be a sequence of globally developable triangulations which tends to a globally developable smooth surface S in the Hausdorff sense. If the normals of Tn tend to the normals of S, then the shape of the unfolding of Tn tends to the shape of the unfolding of S. We also provide several examples: first, we show globally developable triangulations whose vertices are close to globally developable smooth surfaces; we also build sequences of globally developable triangulations inscribed on a sphere, with a number of vertices and edges tending to infinity. Finally, we also give an example of a triangulation with strictly negative Gauss curvature at any interior point, inscribed in a smooth surface with a strictly positive Gauss curvature. The Gauss curvature of these triangulations becomes positive (at each interior vertex) only by switching some of their edges.

International audience; This paper proposes a new method for isotropic remeshing of tri- angulated surface meshes. Given a triangulated surface mesh to be resampled and a user-specified density function defined over it, we first distribute the desired number of samples by generalizing error diffusion, commonly used in image halftoning, to work directly on mesh triangles and feature edges. We then use the resulting sam- pling as an initial configuration for building a weighted centroidal Voronoi tessellation in a conformal parameter space, where the specified density function is used for weighting. We finally create the mesh by lifting the corresponding constrained Delaunay trian- gulation from parameter space. A precise control over the sampling is obtained through a flexible design of the density function, the latter being possibly low-pass filtered to obtain a smoother grada- tion. We demonstrate the versatility of our approach through vari- ous remeshing examples.

Surfaces and manifolds represented by a set of discrete points are encountered in various application areas. In this thesis, we define a coordinate system on the manifold associated to such a point set which is a generalization of Sibson's natural neighbor coordinates. We show its fundamental mathematical properties as well as its application to scattered data interpolation on manifolds. Furthermore, we introduce the notion of Voronoi atlas defined as a collection of Voronoi cells that approximate the Voronoi diagram restricted to the manifold. We describe its application in surface reconstruction and re-meshing. In addition, we show the basic properties of natural neighbor coordinates in power diagrams and we survey the interpolation methods based on natural neighbor coordinates. This survey details some proofs that are omitted in the original papers.; Dans de nombreux domaines d'applications, une variété plongée dans l'espace euclidien est souvent représentée par un échantillon de points. Nous définissons dans cette thèse un système de coordonnées associé à un tel échantillon sur la variété qui généralise les coordonnées naturelles définies par Sibson. Nous exhibons ses propriétés mathématiques fondamentales ainsi que son application à l'interpolation d'une fonction définie sur la variété. Nous introduisons la notion d'atlas de Voronoï, défini comme un ensemble de cellules approximant le diagramme de Voronoï restreint à la variété et montrons son application à la reconstruction de surface et au remaillage. Enfin, nous étendons les propriétés des coordonnées naturelles aux diagrammes de puissance et proposons une synthèse des méthodes d'interpolation par coordonnées naturelles. Cette dernière détaille des preuves omises dans les articles originaux.

This report deals with the approximation of a smooth surface M by a triangulated mesh T. We give an explicit bound on the difference of the curvature measures of M and the curvature measures of T, when T is close to M. The result is obtained by applying the theory of the normal cycle.

This paper addresses the point-wise estimation of differential properties of a smooth manifold $S$ ---a curve in the plane or a surface in $3D$--- assuming a point cloud sampled over $S$ is provided. The method consists of fitting the local representation of the manifold using a jet, and either interpolation or approximation. A jet is a truncated Taylor expansion, and the incentive for using jets is that they encode all local geometric quantities ---such as normal, curvatures, extrema of curvature. On the way to using jets, the question of estimating differential properties is recasted into the more general framework of multivariate interpolation / approximation, a well-studied problem in numerical analysis. On a theoretical perspective, we prove several convergence results when the samples get denser. For curves and surfaces, these results involve asymptotic estimates with convergence rates depending upon the degree of the jet used. For the particular case of curves, an error bound is also derived. To the best of our knowledge, these results are among the first ones providing accurate estimates for differential quantities of order three and more. On the algorithmic side, we solve the interpolation/approximation problem using Vandermonde systems. Experimental results for surfaces of $\Rn^3$ are reported. These experiments illustrate the asymptotic convergence results, but also the robustness of the methods on general Computer Graphics models.

This report deals with approximations of geometric data defined on a hypersurf- ace of the Euclidean space E^n. Using geometric measure theory, we evaluate an upper bound on the flat norm of the difference of the normal cycle of a compact subset of E^n whose boundary is a smooth (closed oriented embedded) hypersurface, and the normal cycle of a compact geometric subset of E^n "close to it". We deduce bounds between the difference of the curvature measures of the smooth hypersurface and the curvature measures of the geometric compact subset.

A general and simple algorithm is presented which computes the set FP of all free configurations for a polygonal object I (with m edges) which is free to translate and/or to rotate but not to intersect another polygonal object E. The worst-case time complexity of the algorithm is O(m/sup 3/n/sup 3/ log mn), which is close to optimal. FP is a three-dimensional curved object which can be used to find free motions within the same time bounds. Two types of motion have been studied in some detail. Motion in contact, where I remains in contact with E, is performed by moving along the faces of the boundary of FP. By partitioning FP into prisms, it is possible to compute motions when I never makes contact with E. In this case, the theoretical complexity does not exceed O(m/sup 6/n/sup 6/ alpha (mn)) but it is expected to be much smaller in practice. In both cases, pseudo-optimal motions can be obtained with a complexity increased by a factor log mn. >

SIGGRAPH 2003 Session : Surfaces. Article dans revue scientifique avec comité de lecture. internationale.; International audience; In this paper, we propose a novel polygonal remeshing technique that exploits a key aspect of surfaces: the intrinsic anisotropy of natural or man-made geometry. In particular, we use curvature directions to drive the remeshing process, mimicking the lines that artists themselves would use when creating 3D models from scratch. After extracting and smoothing the curvature tensor field of an input geometry patch, lines of minimum and maximum curvatures are used to determine appropriate edges for the remeshed version in anisotropic regions, while spherical regions are simply point-sampled since there is no natural direction of symmetry locally. As a result our technique generates polygon meshes mainly composed of quads in anisotropic regions, and of triangles in spherical regions. Our approach provides the flexibility to produce meshes ranging from isotropic to anisotropic, from coarse to dense, and from uniform to curvature adapted.

International audience; Given a triangulation T of n points in the plane, we are interested in the minimal set of edges in T such that T can be reconstructed from this set (and the vertices of T) using constrained Delaunay triangulation. We show that this minimal set is precisely the set of non locally Delaunay edges, and that its cardinality is less than or equal to n+i/2 (if i is the number of interior points in T), which is a tight bound.

Article dans revue scientifique avec comité de lecture.; International audience; In this paper, we consider the problem of computing shortest paths of bounded curvature amidst obstacles in the plane. More precisely, given two prescribed initial and final configurations (specifying the location and the direction of travel) and a set of obstacles in the plane, we want to compute a shortest $C^1$ path joining those two configurations, avoiding the obstacles, and with the further constraint that, on each $C^2$ piece, the radius of curvature is at least 1. In this paper, we consider the case of moderate obstacles (as introduced by Agarwal et al.) and present a polynomial-time exact algorithm to solve this problem.

International audience; A time efficient implementation of the exact computation paradigm relies on arithmetic filters which are used to speed up the exact computation of easy instances of the geometric predicates. Depending of what is called ``easy instances'', we usually classify filters as static or dynamic and also some in between categories often called semi-static. In this paper, we propose, in the context of three dimensional Delaunay triangulations: --- automatic tools for the writing of static and semi-static filters, --- a new semi-static level of filtering called translation filter, --- detailed benchmarks of the success rates of these filters and comparison with rounded arithmetic, long integer arithmetic and filters provided in Shewchuk's predicates. Our method is general and can be applied to all geometric predicates on points that can be expressed as signs of polynomial expressions. This work is applied in the CGAL library.

Studies the problem of computing the set F of accessible and stable placements of a spider robot. The body of this robot is a single point and the legs are line segments attached to the body. The robot can only put its feet on some regions, called the foothold regions. Moreover, the robot is subject to two constraints: each leg has a maximal extension R (accessibility constraint) and the body of the robot must lie above the convex hull of its feet (stability constraint). The authors present an efficient algorithm to compute F. If the foothold regions are polygons with n edges in total, the authors' algorithm computes F in O(n/sup 2/ log n) time and O(n/sup 2//spl alpha/(n)) space where /spl alpha/ is the inverse of Ackerman's function. /spl Omega/(n/sup 2/) is a lower bound for the size of F. >

Docking is the process by which two or several molecules form a complex. Docking involves the geometry of the molecular surfaces, as well as chemical and energetical considerations. In the mid-eighties, Connolly proposed a docking algorithm matching surface {\em knobs} with surface {\em depressions}. Knobs and depressions refer to the extrema of the {\em Connolly} function, which is defined as follows. Given a surface $\calM$ bounding a three-dimensional domain $X$, and a sphere $S$ centered at a point $p$ of $\calM$, the Connolly function is equal to the solid angle of the portion of $S$ containing within $X$. We recast the notions of knob and depression of the Connolly function in the framework of Morse theory for functions defined over two-dimensional manifolds. First, we study the critical points of the Connolly function for smooth surfaces. Second, we provide an efficient algorithm for computing the Connolly function over a triangulated surface. Third, we introduce a Morse-Smale decomposition based on Forman's discrete Morse theory, and provide an $O(n\log n)$ algorithm to construct it. This decomposition induces a partition of the surface into regions of homogeneous flow, and provides an elegant way to relate local quantities to global ones ---from critical points to Euler's characteristic of the surface. Fourth, we apply this Morse-Smale decomposition to the discrete gradient vector field induced by Connolly's function, and present experimental results for several mesh models.

Surface reconstruction algorithms produce piece-wise linear approximations of a surface S from a finite, sufficiently dense, subset of its points. In this paper, we present a fast algorithm for surface reconstruction from scattered data sets. This algorithm is inspired of an existing numerical convection scheme developed by Zhao, Osher and Fedkiw. Unlike this latter, the result of our algorithm does not depend on the precision of a (rectangular- ) grid. The reconstructed surface is simply a set of oriented faces located into the 3D Delaunay triangulation of the points. It is the result of the evolution of an oriented pseudo-surface. The representation of the evolving pseudo-surface uses an appropriate data structure together with operations that allow deformation and topological changes of it. The presented algorithm can handle complicated topologies and, unlike most of the others schemes, it involves no heuristic. The complexity of that method is that of the 3D Delaunay triangulation of the points. We present results of this algorithm which turned out to be efficient even in presence of noise.

International audience; The compression of geometric structures is a relatively new field of data compression. Since about 1995, several articles have dealt with the coding of meshes, using for most of them the following approach: the vertices of the mesh are coded in an order that partially contains the topology of the mesh. In the same time, some simple rules attempt to predict the position of each vertex from the positions of its neighbors that have been previously coded. In this article, we describe a compression algorithm whose principle is completely different: the coding order of the vertices is used to compress their coordinates, and then the topology of the mesh is reconstructed from the vertices. This algorithm achieves compression ratios that are slightly better than those of the currently available algorithms, and moreover, it allows progressive and interactive transmission of the meshes.

Let S be a smooth surface of E^3, p a point on S, k_m, k_M, k_G and k_H the maximum, minimum, Gauss and mean curvatures of S at p. Consider a set {p_ipp_(i+1)} i=1,...,n of n Euclidean triangles forming a piecewise linear approximation of S around p ---with p_(n+1)=p_1. For each triangle, let [gamma]_i be the angle /_ p_ipp_(i+1), and let the angular defect at p be 2[pi]-[SIGMA]_i[gamma- ]_i. This paper establishes, when the distances || pp_i || go to zero, that the angular defect is asymptotically equivalent to a homogeneous polynomial of degree two in the principal curvatures. For regular meshes, we provide closed forms expressions for the three coefficients of this polynomial. We show that vertices of valence four and six are the only ones where k_G can be inferred from the angular defect. At other vertices, we show that the principal curvatures can be derived from the angular defects of two independent triangulations. For irregular meshes, we show that the angular defect weighted by the so-called module of the mesh estimates k_G within an error bound depending upon k_m and k_M. Since meshes are so ubiquitous in Computer Graphics and Computer Aided Design, and Discrete Differential operators are so necessary to their processing, we believe these contributions are one step forward the intelligence of the geometry of meshes, whence one step forward more robust algorithms.

We present Angle-Analyzer, a new single-rate compression algorithm for triangle-quad hybrid meshes. Using a carefully-designed geometry-driven mesh traversal and an efficient encoding of intrinsic mesh properties, Angle-Analyzer produces compression ratios 40 better in connectivity and 20 better in geometry than the leading Touma and Gotsman technique for the same level of geometric distortion. The simplicity and performance of this new technique is demonstrated, and we provide extensive comparative tests to contrast our results with the current state-of-the-art techniques.

In this paper, we present a new greedy algorithm for surface reconstruction from unorganized point sets. Starting from a seed facet, a piecewise linear surface is grown by adding Delaunay triangles one by one. The most plausible triangles are added in the first place, in a way that prevents the appearance of topological singularities. The output is thus guaranteed to be a piecewise linear orientable manifold, possibly with boundary. Experiments show that this method is very fast, and achieves topologically correct reconstruction in most cases. Moreover, it can handle surfaces with complex topology, boundaries, and non uniform sampling.

Coordinate systems associated to a finite set of sample points have been extensively studied, especially in the context of interpolation of multivariate scattered data. Notably, Sibson proposed the so-called natural neighbor coordinates that are defined from the Voronoi diagram of the sample points. A drawback of those coordinate systems is that their definition domain is restricted to the convex hull of the sample points. This makes them difficult to use when the sample points belong to a surface. To overcome this difficulty, we propose a new system of coordinates. Given a closed surface $S$, i.e. a $(d-1)$-manifold of $\mathbb{R} ^d$, the coordinate system is defined everywhere on the surface, is continuous, and is local even if the sampling density is finite. Moreover, it is inherently $(d-1)$-dimensional while the previous systems are $d$-dimensional. No assumption is made about the ordering, the connectivity or topology of the sample points nor of the surface. We illustrate our results with an application to interpolation over a surface.

In this paper we show an equivalence relationship between additively weighted Voronoi cells in R [power d], power diagrams in R [power d] and convex hulls of spheres in R [power d]. An immediate consequence of this equivalence relationship is a tight bound on the complexity of : (1) a single additively weighted Voronoi cell in dimension d ; (2) the convex hull of a set of d-dimensional spheres. In particular, given a set of n spheres in dimension d, we show that the worst case complexity of both a single additively weighted Voronoi cell and the convex hull of the set of spheres is [THÊTA](n[power d/2]). The equivalence between additively weighted Voronoi cells and convex hulls of spheres permits us to compute a single additively weighted Voronoi cell in dimension d in worst case optimal time [OMICRON](n log n + n[power d/2]).

In this paper, we compare the normal vector field of a compact (oriented) smooth surface S with the normals of a triangulated mesh T whose vertices belong to S. As a corollary, we deduce an approximation of the area of S by the area of T. We apply this result to the restricted Delaunay triangulation obtained with a sample of S. Using Chew's algorithm, we build sequences of triangulations inscribed on S, whose curvature measures tend to the curvature measures of S.

This paper presents a new method for computing whether or not two triangles in three dimensions intersect. The code is very efficient and requires minimum arithmetic precision. Indeed, all branching decisions are carried out by evaluating the signs of degree three polynomials. In addition, an efficient test is proposed for the two-dimensional case.

In this paper we present a dynamic algorithm for the construction of the additively weighted Voronoi diagram of a set of weighted points on the plane. The novelty in our approach is that we use the dual of the additively weighted Voronoi diagram to represent it. This permits us to perform both insertions and deletions of sites easily. Given a set of n sites, among which h sites have non-empty Voronoi cell, our algorithm constructs the additively weighted Voronoi diagram of in O(n T(h) + h h) expected time, where T(k) is the time to locate the nearest neighbor of a query site within a set of k sites with non-empty Voronoi cell. Deletions can be performed for all sites whether or not their Voronoi cell is empty. The space requiremen- ts for the presented algorithm is O(n). Our algorithm is simple to implement and experimental results suggest an O(n h) behavior.

Encoders for triangle mesh connectivity based on enumeration of vertex valences are among the best reported to date. They are both simple to implement and report the best compressed file sizes for a large corpus of test models. Additionally they have recently been shown to be near-optimal since they realize the Tutte entropy bound for all planar triangulations. In this paper we introduce a connectivity encoding method which extends these ideas to 2-manifold meshes consisting of faces with arbitrary degree. The encoding algorithm exploits duality by applying valence enumeration to both the primal and the dual mesh in a symmetric fashion. It generates two sequences of symbols, vertex valences, and face degrees, and encodes them separately using two context-based arithmetic coders. This allows us to exploit vertex or face regularity if present. When the mesh exhibits perfect face regularity (e.g., a pure triangle or quad mesh) or perfect vertex regularity (valence six or four respectively) the corresponding bit rate vanishes to zero asymptotically. For triangle meshes, our technique is equivalent to earlier valence-driven approaches. We report compression results for a corpus of standard meshes. In all cases we are able to show coding gains over earlier coders, sometimes as large as 50%. Remarkably, we even slightly gain over coders specialized to triangle or quad meshes. A theoretical analysis reveals that our approach is near-optimal as we achieve the Tutte entropy bound for arbitrary planar graphs of two bits per edge in the worst case.

Delaunay triangulations and Voronoi diagrams have found numerous applications in surface modeling, surface mesh generation, deformable surface modeling and surface reconstruction. Many algorithms in these applications begin by constructing the three-dimensional Delaunay triangulation of a finite set of points scattered over a surface. Their running-time therefore depends on the complexity of the Delaunay triangulation of such point sets. Although the Delaunay triangulation of points in ^3 can be quadratic in the worst-case, we show that, under some mild sampling condition, the complexity of the 3D Delaunay triangulation of points distributed on a fixed number of facets of ^3 (e.g. the facets of a polyhedron) is linear. Our bound is deterministic and the constants are explicitly given.

We compare the area of a smooth surface S with the area of a surface M which is close to it, in terms of the local structure of S and the distance between S and M. We obtain convergence results, in particular when the surface approaching S is the restricted Delaunay complex associated to an epsilon-sample S of S.

Colloque avec actes sans comité de lecture. internationale.; International audience; We prove that, under a certain general position assumption, the number of lines tangent to four bounded disjoint convex polyhedra in $\Real^3$ with a total of $n$ edges is $O(n^2)$. Under the same assumption, we show that a set of $k$ bounded disjoint convex polyhedra has at most $O(n^2k^2)$ lines, possibly occluded, that are tangent to four of these polyhedra.

Let S be a point set in the plane in general position, such that its elements are partitioned into k classes or colors. In this paper we study several variants on problems related to the Erdös-Szekeres Theorem about subsets of S in convex position, when additional chromatic constraints are considered.

Numerical simulations take a bigger importance in medical activity as they allow to obtain information non-invasively. To take into account individual variability, we propose numerical simula- tions in geometries reconstructed from medical images. We present the necessary treatment of images of diseased vessels, to provide a computational mesh of an anatomical model of the subject. First a faceted surface is extracted from the images. Then this surface is transformed into a geometrical model to be finally remeshed for a finite element use. Resume .L es simulations numeriques ayant trait au biomedical prennent de plus en plus d'importance car elles permettent d'obtenir de nouvelles informations impossiblesmesurer de maniere non-invasive chez les patients. Pour prendre en compte la variabilite inter-sujet, nous proposons des simulations numeriques dans des getries reconstruitespartir de l'imagerie medicale. Dans la suite, nous presentons le traitement d'images de vaisseaux malades, necessairel'obtention d'un maillage de calcul du modele anatomique du patient. En premier lieu, on extrait des images un ensemble de facettes representant une surface. Puis cette surface est transformee en un modele geometrique qui est finalement remaille pour satisfaire les contraintes d'un maillageements finis.

We present a novel technique, both flexible and efficient, for interactive remeshing of irregular geometry. First, the original (arbitrary genus) mesh is substituted by a series of 2D maps in parameter space. Using these maps, our algorithm is then able to take advantage of established signal processing and halftoning tools that offer real-time interaction and intricate control. The user can easily combine these maps to create a control map -- a map which controls the sampling density over the surface patch. This map is then near-optimally sampled at interactive rates allowing the user to interactively design a tailored resampling. Once this sampling is complete, a Delaunay triangulation and fast optimization are performed to perfect the final mesh. As a result, our remeshing technique is extremely versatile and general being able to produce arbitrarily complex meshes with a variety of properties including: uniformity, regularity, semi-regularity, curvature sensitive resampling, and feature preservation. We provide a high level of control over the sampling distribution allowing the user to interactively custom design the mesh based on their requirements thereby increasing their productivity in creating a wide variety of meshes.

Given a finite set of points [Formula: see text] in ℝd, the diameter of [Formula: see text] is defined as the maximum distance between two points of [Formula: see text]. We propose a very simple algorithm to compute the diameter of a finite set of points. Although the algorithm is not worst-case optimal, an extensive experimental study has shown that it is extremely fast for a large variety of point distributions. In addition, we propose a comparison with the recent approach of Har-Peled5 and derive hybrid algorithms to combine advantages of both approaches.

In this paper, we show that, amongst n uniformly distributed unit balls in R^3, the expected number of maximal non-occluded line segments tangent to four balls is linear, considerably improving the previously known upper bound. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding the visibility information of a scene, providing evidence that the storage requirement for this data structure is not necessarily prohibitive. Our results generalize in various directions. We show that the linear bound on the expected number of maximal non-occluded line segments that are not too close to the boundary of the scene and tangent to four unit balls extends to balls of various but bounded radii, to polyhedra of bounded aspect ratio, and even to non-fat 3D objects such as polygons of bounded aspect ratio. We also prove that our results extend to other distributions such as the Poisson distribution. Finally, we indicate how our probabilistic analysis provides new insight on the expected size of other global visibility data structures, notably the aspect graph.

Article dans revue scientifique avec comité de lecture.; International audience; In this paper, we study the collision-free path planning problem for a point robot, whose path is of {\em bounded curvature} (i.e., constrained to have curvature at most 1), moving in the plane inside an $n$-sided simple polygon $P$. Given two points $s$ and $t$ inside $P$ and two directions of travel, one at $s$ and one at $t$, the problem is to compute a convex and simple path of bounded curvature inside $P$ from $s$ to $t$ consisting of straight-line segments and circular arcs such that (i) the radius of each circular arc is at least 1, (ii) each segment on the path is the tangent between the two consecutive circular arcs on the path, (iii) the given initial direction at $s$ is tangent to the path at $s$ and (iv) the given final direction at $t$ is tangent to the path at $t$. We propose an $O(n^4)$ time algorithm for this problem. Using the notion of complete visibility, $P$ is pruned to another polygon $P'$ such that any convex and simple path from $s$ to $t$ inside $P$ also remains inside $P'$. Then our algorithm constructs the locus of center of a circle of unit radius translating along the boundary of $P'$ and using this locus, the algorithm constructs a convex and simple path of bounded curvature. Our algorithm is based on the relationship between the Euclidean shortest path, link paths and paths of bounded curvature, and uses several properties derived here on convex and simple paths of bounded curvature. We also show that the path computed by our algorithm can be transformed in $O(n)$ time to a {\it minimal} convex and simple path of bounded curvature. Using this transformation and two necessary conditions proposed here for the shortest convex and simple path of bounded curvature, a {\it minimal} bounded curvature path is located in $O(n^4)$ time whose length, except in special situations involving arcs of length greater than $\pi$, is at most twice the length of a shortest convex and simple path of bounded curvature.

For a few years, meshes have been conquering a predominant status amongst the different types of computer data structure for geometric objects. More precisely, the meshes composed of simplices -- triangles for the modeling of surfaces embedded in 3D, tetrahedra for the modeling of volumes -- seem to be the most widespread at the present time. The rapid growth of applications using these geometric structures in such various fields as finite elements computing, simulation of surgery, or video games has quickly raised the problem of an efficient coding, well suited for storage or visualization. The advent of the World Wide Web, which needs a compact and progressive representation of the data in order to guarantee the user-friendliness of the exchanges and communications, increases this need. Therefore, since 1995, a large number of algorithms have been proposed for the compression of triangular meshes, using for most of them the following approach: the vertices of the mesh are coded in an order such that it contains partially the topology of the mesh. In the same time, some simple rules attempt to predict the position of the current vertex from the positions of its neighbors that have been previously coded. In this thesis, we have chosen to give the priority to the compression of the vertex positions rather than their connectivity. We describe a set of coding methods which are progressive, lossless, adapted to arbitrary meshes (non necessarily triangular nor manifold, with arbitrary genus), and generalizable to any dimension. Our results are competitive with regards to the best current progressive methods: for instance, for the particular case of triangular surface meshes, about 3.6 bits per vertex are necessary on average to code the connectivity of usual models.; En quelques années, les maillages ont conquis une position prédominante parmi les différents modes de représentation informatique d'objets géométriques. Plus particulièrement, les maillages à base de simplexes -- les triangles pour la représentation de surfaces plongées en 3D, les tétraèdres pour la représentation de volumes -- semblent être actuellement les plus répandus. Le développe- ment rapide des applications manipulant ces structures géométriques dans des domaines aussi divers que le calcul par éléments finis, la simulation chirurgi- cale, ou les jeux vidéo a très vite soulevé le problème d'un codage efficace et adapté à la visualisation. L'expansion du World Wide Web, qui nécessite une représentation compacte et progressive des données pour garantir la convivial- ité de l'interface homme-machine, a fini de conférer à ce problème une place centrale dans la recherche en informatique. Ainsi, depuis 1995, de nombreux algorithmes ont été proposés pour la com- pression de maillages triangulaires, en utilisant le plus souvent l'approche suiv- ante : les sommets du maillage sont codés dans un ordre établi pour contenir par- tiellement la topologie (ou connectivité) du maillage. Parallèlement, quelques règles simples permettent de prédire la position du sommet courant à partir des positions de ses voisins qui ont déjà été codés. Dans ce mémoire, nous avons choisi de donner plutôt la priorité à la compression des positions des sommets. Nous décrivons un ensemble de méthodes de codage progressif, sans perte d'information, adaptées à une large classe de structures géométriques (non nécessairement triangulaires ni manifold, de genre quelconque), et généralisables à n'importe quelle dimension. Les taux de compression obtenus se positionnent avantageusement par rapport aux méthodes progressives actuelles les plus ef- ficaces : par exemple, pour le cas particulier des maillages triangulaires sur- faciques, des taux moyens autour de 3,6 bits par sommet sont atteints sur des modèles usuels pour le codage de la connectivité.

It is well known that the complexity of the Delaunay triangulation of $n$ points in $R ^d$, i.e. the number of its simplices, can be $\Omega (n^\lceil \frac{d{2}\rceil })$. In particular, in $R ^3$, the number of tetrahedra can be quadratic. Differently, if the points are uniformly distributed in a cube or a ball, the expected complexity of the Delaunay triangulation is only linear. The case of points distributed on a surface is of great practical importance in reverse engineering since most surface reconstruction algorithms first construct the Delaunay triangulation of a set of points measured on a surface. In this paper, we bound the complexity of the Delaunay triangulation of points distributed on the boundary of a given polyhedron. Under a mild uniform sampling condition, we provide deterministic asymptotic bounds on the complexity of the 3D Delaunay triangula- tion of the points when the sampling density increases. More precisely, we show that the complexity is $O(n^1.8)$ for general polyhedral surfaces and $O(n\sqrtn)$ for convex polyhedral surfaces. Our proof uses a geometric result of independent interest that states that the medial axis of a surface is well approximated by a subset of the Voronoi vertices of the sample points. The proof extends easily to higher dimensions, leading to the first non trivial bounds for the problem when $d>3$.

We are interested in computing effectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a fix radius and with extremal radius. For these different problems, we give bounds on the number of solutions and exemples show that these bounds are optimal. Finally, we describe two algebraic methods which can be used here to solve efficiently these problems and some experimentation results.

En quelques années, les maillages ont conquis une position prédominante parmi les différents modes de représentation informatique d'objets géométrique- s. Plus particulièrement, les maillages à base de simplexes - les triangles pour la représentation de surfaces plongées en 3D, les tétraèdres pour la représentation de volumes - semblent être actuellement les plus répandus. Le développement rapide des applications manipulant ces structures géométrique- s dans des domaines aussi divers que le calcul par éléments finis ou les jeux vidéo a très vite soulevé le problème d'un codage efficace et adapté à la visualisation. L'expansion du World Wide Web, qui nécessite une représent- ation compacte et progressive des données pour garantir la convivialité de l'interface homme/machine, a conféré à ce problème une place centrale dans la recherche informatique. Ainsi, depuis 1995, de nombreux algorithmes ont été proposés pour la compression de maillages triangulaires. Dans ce rapport, nous décrivons une méthode de codage progressive, sans perte d'information, adaptée à des maillages triangulaires arbitraires (non nécessairement manifold, de genre quelconque), et généralisable à n'importe quelle dimension. Pour le cas particulier de maillages triangulaires surfaciqu- es, des taux moyens autour de 3,6 bits par sommet sont atteints sur des modèles usuels pour le codage de la connectivité.

Roundness and cylindricity evaluations are among the most important problems in computational metrology, and are based on sets of surface measurements (input data points). A recent approach to such evaluations is based on a linear-programming approach yielding a rapidly converging solution. Such solution is determined by a fixed-size subset of a large input set. In the intent to simplify the main computational task, it appears desirable to cull from the input any point that cannot provably define the solution. In this note we present an analysis and an efficient solution to the problem of culling the input set.

Given a triangulation $T$ of $n$ points in the plane, we are interested in the minimal set of edges in $T$ such that $T$ can be reconstructed from this set (and the vertices of $T$) using constrained Delaunay triangulati- on. We show that this minimal set consists of the non locally Delaunay edges of $T$, and that its cardinality is less than or equal to $n+i/2$ (if $i$ is the number of interior points in $T$), which is a tight bound.

International audience; The purpose of this paper is to present a new method to de- sign exact geometric predicates in algorithms dealing with curved objects such as circular arcs. We focus on the com- parison of the abscissae of two intersection points of circle arcs, which is known to be a difficult predicate involved in the computation of arrangements of circle arcs. We present an algorithm for deciding the x-order of intersections from the signs of the coefficients of a polynomial, obtained by a general approach based on resultants. This method allows the use of efficient arithmetic and filtering techniques lead- ing to fast implementation as shown by the experimental results.

International audience; The minimum zone cylinder of a set of points in three dimensions is the cylindric crown defined by a pair of coaxial cylinders with minimal radial separation (width). In the context of tolerancing metrology, the set of points is nominally cylindrical, i.e., the points are known to lie in close proximity of a known reference cylinder. Using approximations which are valid only in the neighborhood of the reference cylinder, we can get a very good approximation of the minimum zone cylinder. The process provides successive approximations, and each iteration involves the solution of a linear programming problem in six dimensions. The error between the approximation and the optimal solution converges very rapidly (typically in three iterations in practice) down to a limit error of (8 omega^2)/R ( where omega is the width and R is the external radius of the zone cylinder).