|
|
|
Orateurs invités
"Edge flip for compact transformation and progressive compression of triangular meshes"
Abstract Hight quality meshes produced by 3D scanners are generally characterized by a high density of vertices over the surface. For compression purpose, the connectivity of such meshes can partly be retrieved from the proximity between geometric positions of the vertices. However, we need to investigate new tools to describe the difference between the target mesh and the connectivity deduced from the geometry. This presentation will describe the opportunities offered by edge flips for that task. New generation of algorithms for compressing meshes can be based on this operation, in the wake of the Iterative Parametric Refinement algorithm. A practical approach to turn a triangulated surface into an other one will be introduced. Its validity is bound to the fact that intermediate configurations can belong to a broader class than just manifold meshes. Finally, an original solution to the reduction of edge flip sequences will be presented, which amounts to tracking edges by label assignment.
"The Persistent Homology Pipleline: Shapes, Computations, and Applications"
Abstract Data analysis is the task of extracting relevant information from a possibly large and possibly noisy data collection. A commonly desired goal is to obtain global summaries of the data which help to understand the data on a high-level and simplify the exploration process. Interpreting data as geometric input, such summaries are provided by topological invariants, for instance the homology of spaces, which leads to the field of topological data analysis. The last 20 years have witnessed a boost of this research area, mostly due to the development of persistent homology. This is a theory to make topological invariants robust with respect to noise and yielding a topological multi-scale summary of data. The success of persistent homology has posed the challenge of computing persistence on large data sets. Typical questions in this context are: How can we efficiently build combinatorial cell complexes out of point cloud data? How can we compute the persistence summaries of very large cell complexes in a scalable way? Finally, how does the computed summary lead us to new insights into the considered application? My talk will introduce the theory of persistent homology on an informal level, discuss some recent algorithmic advances and survey some application areas of topological data analysis.
"Simple and Scalable Surface Reconstruction"
Abstract I present a new reconstruction algorithm that generates a surface triangulation from an input pointset. In the result, the input points appear as vertices of the generated triangulation. The algorithm has several interesting properties: it is very simple to implement, it is time and memory efficient, and it is trivially parallelized. On a standard hardware (core i7, 16Gb) it takes less than 10 seconds to reconstruct a surface from 1 million points, and scales-up to 60 million points (then it takes 300 seconds). On a telephone (ARMV7 Neon, quad core), it takes 100 seconds to reconstruct a surface from 1 million points. The algorithm computes the Delaunay triangulation of the input pointset restricted to a "thickening" of the pointset (similarly to several existing methods, like alpha-shapes, crust and co-cone). By considering the problem from the Voronoi point of view (rather than Delaunay), I make a simple observation (radius of security) that makes the problem simpler. The Delaunay triangulation data structure and associated algorithms are replaced by simpler ones (KD-Tree and convex clipping) while the same set of triangles is provably obtained. The restricted Delaunay triangulation can thus be computed by an algorithm that is not longer than 200 lines of code, memory efficient and parallel. The so-computed restricted Delaunay triangulation is finally post-processed to remove the non-manifold triangles that appear in zones where the sampling was not regular/dense enough (violations of Amenta and Bern's epsilon sampling condition). Sensitivity to outliers and noise is not addressed here. Noisy inputs need to be pre-processed with a pointset filtering method. In the presented experimental results, we are using two iterations of projection onto the best approximating plane of the 30 nearest neighbors (more sophisticated ones may be used if the input pointset has many outliers). The implementation will be made available in the GEOGRAM programming library (alice.loria.fr/software/geogram). This is common work with Dobrina Boltcheva and Maxence Reberol.
"Recursive structure of digital planes, a combinatorial approach based on continued fractions"Abstract The study of digital straightness has led to many tools in order to extract geometrical information from digital images. In particular, in dimension 2, the identification of digital straight segments on the border of a digital shape allows to determine properties such as local and global convexity, they are also used in geometric estimators for properties like length, tangent and curvature. Digital straight lines have been showed to have a recursive structure which is completely described by the continued fraction development of its slope. This allows to link the arithmetical properties of the slope to geometrical properties like local periodicity, self-symmetries and palindromicity. Even the Delaunay triangulation of a digital line is described by the continued fraction development of the slope. In this talk, I present a construction scheme that generalizes the construction of a digital line via the continued fraction development of its slope in order to build digital planes. We obtain a construction algorithm that is parametrized by a multidimensional continued fraction algorithm. Unlike in dimension 2, in dimension 3 and over, there is no canonical choice for such an algorithm. Under certain conditions, we are able to guaranty some geometrical properties of the output, but the general case is still an open question.
|
| Personnes connectées : 1 |
|
