30-Issue 5Geometry Processing 2011 - Special Issuehttps://dlold.eg.org:443/handle/10.2312/1652024-09-20T20:21:43Z2024-09-20T20:21:43ZAn Optimal Transport Approach to Robust Reconstruction and Simplification of 2D ShapesGoes, Fernando deCohen-Steiner, DavidAlliez, PierreDesbrun, Mathieuhttps://dlold.eg.org:443/handle/10.1111/v30i5pp1593-16022022-03-28T09:10:30Z2011-01-01T00:00:00ZAn Optimal Transport Approach to Robust Reconstruction and Simplification of 2D Shapes
Goes, Fernando de; Cohen-Steiner, David; Alliez, Pierre; Desbrun, Mathieu
Mario Botsch and Scott Schaefer
We propose a robust 2D shape reconstruction and simplification algorithm which takes as input a defect-laden point set with noise and outliers. We introduce an optimal-transport driven approach where the input point set, considered as a sum of Dirac measures, is approximated by a simplicial complex considered as a sum of uniform measures on 0- and 1-simplices. A fine-to-coarse scheme is devised to construct the resulting simplicial complex through greedy decimation of a Delaunay triangulation of the input point set. Our method performs well on a variety of examples ranging from line drawings to grayscale images, with or without noise, features, and boundaries.
2011-01-01T00:00:00ZSkeleton Computation of Orthogonal PolyhedraMartinez, JonasVigo, MarcPla-Garcia, Nuriahttps://dlold.eg.org:443/handle/10.1111/v30i5pp1573-15822022-03-28T09:09:48Z2011-01-01T00:00:00ZSkeleton Computation of Orthogonal Polyhedra
Martinez, Jonas; Vigo, Marc; Pla-Garcia, Nuria
Mario Botsch and Scott Schaefer
Skeletons are powerful geometric abstractions that provide useful representations for a number of geometric operations. The straight skeleton has a lower combinatorial complexity compared with the medial axis. Moreover, while the medial axis of a polyhedron is composed of quadric surfaces the straight skeleton just consist of planar faces. Although there exist several methods to compute the straight skeleton of a polygon, the straight skeleton of polyhedra has been paid much less attention. We require to compute the skeleton of very large datasets storing orthogonal polyhedra. Furthermore, we need to treat geometric degeneracies that usually arise when dealing with orthogonal polyhedra. We present a new approach so as to robustly compute the straight skeleton of orthogonal polyhedra. We follow a geometric technique that works directly with the boundary of an orthogonal polyhedron. Our approach is output sensitive with respect to the number of vertices of the skeleton and solves geometric degeneracies. Unlike the existing straight skeleton algorithms that shrink the object boundary to obtain the skeleton, our algorithm relies on the plane sweep paradigm. The resulting skeleton is only composed of axis-aligned and 45 rotated planar faces and edges.
2011-01-01T00:00:00ZA Multiscale Approach to Optimal TransportMérigot, Quentinhttps://dlold.eg.org:443/handle/10.1111/v30i5pp1583-15922022-03-28T09:10:13Z2011-01-01T00:00:00ZA Multiscale Approach to Optimal Transport
Mérigot, Quentin
Mario Botsch and Scott Schaefer
In this paper, we propose an improvement of an algorithm of Aurenhammer, Hoffmann and Aronov to find a least square matching between a probability density and finite set of sites with mass constraints, in the Euclidean plane. Our algorithm exploits the multiscale nature of this optimal transport problem. We iteratively simplify the target using Lloyd's algorithm, and use the solution of the simplified problem as a rough initial solution to the more complex one. This approach allows for fast estimation of distances between measures related to optimal transport (known as Earth-mover or Wasserstein distances). We also discuss the implementation of these algorithms, and compare the original one to its multiscale counterpart.
2011-01-01T00:00:00ZVASE: Volume-Aware Surface Evolution for Surface Reconstruction from Incomplete Point CloudsTagliasacchi, AndreaOlson, MattZhang, HaoHamarneh, GhassanCohen-Or, Danielhttps://dlold.eg.org:443/handle/10.1111/v30i5pp1563-15712022-03-28T09:09:50Z2011-01-01T00:00:00ZVASE: Volume-Aware Surface Evolution for Surface Reconstruction from Incomplete Point Clouds
Tagliasacchi, Andrea; Olson, Matt; Zhang, Hao; Hamarneh, Ghassan; Cohen-Or, Daniel
Mario Botsch and Scott Schaefer
Objects with many concavities are difficult to acquire using laser scanners. The highly concave areas are hard to access by a scanner due to occlusions by other components of the object. The resulting point scan typically suffers from large amounts of missing data. Methods that use surface-based priors rely on local surface estimates and perform well only when filling small holes. When the holes become large, the reconstruction problem becomes severely under-constrained, which necessitates the use of additional reconstruction priors. In this paper, we introduce weak volumetric priors which assume that the volume of a shape varies smoothly and that each point cloud sample is visible from outside the shape. Specifically, the union of view-rays given by the scanner implicitly carves the exterior volume, while volumetric smoothness regularizes the internal volume. We incorporate these priors into a surface evolution framework where a new energy term defined by volumetric smoothness is introduced to handle large amount of missing data. We demonstrate the effectiveness of our method on objects exhibiting deep concavities, and show its general applicability over a broader spectrum of geometric scenario.
2011-01-01T00:00:00Z