SGP11: Eurographics Symposium on Geometry Processinghttps://diglib.eg.org/handle/10.2312/4362024-10-05T23:11:35Z2024-10-05T23:11:35Z241Skeleton Computation of Orthogonal PolyhedraMartinez, JonasVigo, MarcPla-Garcia, Nuriahttps://diglib.eg.org/handle/10.1111/v30i5pp1573-15822022-03-28T09:09:48Z2011-01-01T00:00:00Zdc.title: Skeleton Computation of Orthogonal Polyhedra
dc.contributor.author: Martinez, Jonas; Vigo, Marc; Pla-Garcia, Nuria
dc.contributor.editor: Mario Botsch and Scott Schaefer
dc.description.abstract: 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://diglib.eg.org/handle/10.1111/v30i5pp1583-15922022-03-28T09:10:13Z2011-01-01T00:00:00Zdc.title: A Multiscale Approach to Optimal Transport
dc.contributor.author: Mérigot, Quentin
dc.contributor.editor: Mario Botsch and Scott Schaefer
dc.description.abstract: 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:00ZAn Optimal Transport Approach to Robust Reconstruction and Simplification of 2D ShapesGoes, Fernando deCohen-Steiner, DavidAlliez, PierreDesbrun, Mathieuhttps://diglib.eg.org/handle/10.1111/v30i5pp1593-16022022-03-28T09:10:30Z2011-01-01T00:00:00Zdc.title: An Optimal Transport Approach to Robust Reconstruction and Simplification of 2D Shapes
dc.contributor.author: Goes, Fernando de; Cohen-Steiner, David; Alliez, Pierre; Desbrun, Mathieu
dc.contributor.editor: Mario Botsch and Scott Schaefer
dc.description.abstract: 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:00ZVASE: Volume-Aware Surface Evolution for Surface Reconstruction from Incomplete Point CloudsTagliasacchi, AndreaOlson, MattZhang, HaoHamarneh, GhassanCohen-Or, Danielhttps://diglib.eg.org/handle/10.1111/v30i5pp1563-15712022-03-28T09:09:50Z2011-01-01T00:00:00Zdc.title: VASE: Volume-Aware Surface Evolution for Surface Reconstruction from Incomplete Point Clouds
dc.contributor.author: Tagliasacchi, Andrea; Olson, Matt; Zhang, Hao; Hamarneh, Ghassan; Cohen-Or, Daniel
dc.contributor.editor: Mario Botsch and Scott Schaefer
dc.description.abstract: 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:00ZOn the Shape of a Set of Points and Lines in the PlaneKreveld, Marc vanLankveld, Thijs vanVeltkamp, Remco C.https://diglib.eg.org/handle/10.1111/v30i5pp1553-15622022-03-28T09:10:25Z2011-01-01T00:00:00Zdc.title: On the Shape of a Set of Points and Lines in the Plane
dc.contributor.author: Kreveld, Marc van; Lankveld, Thijs van; Veltkamp, Remco C.
dc.contributor.editor: Mario Botsch and Scott Schaefer
dc.description.abstract: Detailed geometric models of the real world are in increasing demand. LiDAR data is appropriate to reconstruct urban models. In urban scenes, the individual surfaces can be reconstructed and connected to form the scene geometry. There are various methods for reconstructing the free-form shape of a point sample on a single surface. However, these methods do not take the context of the surface into account. We present the guided a-shape: an extension of the well known a-shape that uses lines (guides) to indicate preferred locations for the boundary of the shape. The guided a-shape uses (parts of) these lines as boundary where the points suggest that this is appropriate. We prove that the guided a-shape can be constructed in O((n+m) log(n+m)) time, from an input of n points and m guides. We apply guided a-shapes to urban reconstruction from LiDAR, where neighboring surfaces can be connected conveniently along their intersection lines into adjacent surfaces of a 3D model. We analyze guided a-shapes of both synthetic and real data and show they are consistently better than a-shapes for this application.
2011-01-01T00:00:00ZAs-Killing-As-Possible Vector Fields for Planar DeformationSolomon, JustinBen-Chen, MirelaButscher, AdrianGuibas, Leonidashttps://diglib.eg.org/handle/10.1111/v30i5pp1543-15522022-03-28T09:10:14Z2011-01-01T00:00:00Zdc.title: As-Killing-As-Possible Vector Fields for Planar Deformation
dc.contributor.author: Solomon, Justin; Ben-Chen, Mirela; Butscher, Adrian; Guibas, Leonidas
dc.contributor.editor: Mario Botsch and Scott Schaefer
dc.description.abstract: Cartoon animation, image warping, and several other tasks in two-dimensional computer graphics reduce to the formulation of a reasonable model for planar deformation. A deformation is a map from a given shape to a new one, and its quality is determined by the type of distortion it introduces. In many applications, a desirable map is as isometric as possible. Finding such deformations, however, is a nonlinear problem, and most of the existing solutions approach it by minimizing a nonlinear energy. Such methods are not guaranteed to converge to a global optimum and often suffer from robustness issues. We propose a new approach based on approximate Killing vector fields (AKVFs), first introduced in shape processing. AKVFs generate near-isometric deformations, which can be motivated as direction fields minimizing an as-rigid-as-possible (ARAP) energy to first order. We first solve for an AKVF on the domain given user constraints via a linear optimization problem and then use this AKVF as the initial velocity field of the deformation. In this way, we transfer the inherent nonlinearity of the deformation problem to finding trajectories for each point of the domain having the given initial velocities. We show that a specific class of trajectories - the set of logarithmic spirals - is especially suited for this task both in practice and through its relationship to linear holomorphic vector fields. We demonstrate the effectiveness of our method for planar deformation by comparing it with existing state-of-the-art deformation methods.
2011-01-01T00:00:00ZMultiscale Biharmonic KernelsRustamov, Raif M.https://diglib.eg.org/handle/10.1111/v30i5pp1521-15312022-03-28T09:10:10Z2011-01-01T00:00:00Zdc.title: Multiscale Biharmonic Kernels
dc.contributor.author: Rustamov, Raif M.
dc.contributor.editor: Mario Botsch and Scott Schaefer
dc.description.abstract: This paper introduces a general principle for constructing multiscale kernels on surface meshes, and presents a construction of the multiscale pre-biharmonic and multiscale biharmonic kernels. Our construction is based on an optimization problem that seeks to minimize a smoothness criterion, the Laplacian energy, subject to a sparsity inducing constraint. Namely, we use the lasso constraint, which sets an upper bound on the l1-norm of the solution, to obtain a family of solutions parametrized by this upper-bound parameter. The interplay between sparsity and smoothness results in smooth kernels that vanish away from the diagonal. We prove that the resulting kernels have gradually changing supports, consistent behavior over partial and complete meshes, and interesting limiting behaviors (e.g. in the limit of large scales, the multiscale biharmonic kernel converges to the Green's function of the biharmonic equation); in addition, these kernels are based on intrinsic quantities and so are insensitive to isometric deformations. We show empirically that our kernels are shape-aware, are robust to noise, tessellation, and partial object, and are fast to compute. Finally, we demonstrate that the new kernels can be useful for function interpolation and shape correspondence.
2011-01-01T00:00:00ZA Complex View of Barycentric MappingsWeber, OfirBen-Chen, MirelaGotsman, CraigHormann, Kaihttps://diglib.eg.org/handle/10.1111/v30i5pp1533-15422022-03-28T09:10:27Z2011-01-01T00:00:00Zdc.title: A Complex View of Barycentric Mappings
dc.contributor.author: Weber, Ofir; Ben-Chen, Mirela; Gotsman, Craig; Hormann, Kai
dc.contributor.editor: Mario Botsch and Scott Schaefer
dc.description.abstract: Barycentric coordinates are very popular for interpolating data values on polyhedral domains. It has been recently shown that expressing them as complex functions has various advantages when interpolating two-dimensional data in the plane, and in particular for holomorphic maps. We extend and generalize these results by investigating the complex representation of real-valued barycentric coordinates, when applied to planar domains. We show how the construction for generating real-valued barycentric coordinates from a given weight function can be applied to generating complex-valued coordinates, thus deriving complex expressions for the classical barycentric coordinates: Wachspress, mean value, and discrete harmonic. Furthermore, we show that a complex barycentric map admits the intuitive interpretation as a complex-weighted combination of edge-to-edge similarity transformations, allowing the design of home-made barycentric maps with desirable properties. Thus, using the tools of complex analysis, we provide a methodology for analyzing existing barycentric mappings, as well as designing new ones.
2011-01-01T00:00:00ZOn Approximation of the Laplace-Beltrami Operator and the Willmore Energy of SurfacesHildebrandt, KlausPolthier, Konradhttps://diglib.eg.org/handle/10.1111/v30i5pp1513-15202022-03-28T09:10:21Z2011-01-01T00:00:00Zdc.title: On Approximation of the Laplace-Beltrami Operator and the Willmore Energy of Surfaces
dc.contributor.author: Hildebrandt, Klaus; Polthier, Konrad
dc.contributor.editor: Mario Botsch and Scott Schaefer
dc.description.abstract: Discrete Laplace Beltrami operators on polyhedral surfaces play an important role for various applications in geometry processing and related areas like physical simulation or computer graphics. While discretizations of the weak Laplace Beltrami operator are well-studied, less is known about the strong form. We present a principle for constructing strongly consistent discrete Laplace Beltrami operators based on the cotan weights. The consistency order we obtain, improves previous results reported for the mesh Laplacian. Furthermore, we prove consistency of the discrete Willmore energies corresponding to the discrete Laplace Beltrami operators.
2011-01-01T00:00:00ZDeformable 3D Shape Registration Based on Local Similarity TransformsPapazov, ChavdarBurschka, Dariushttps://diglib.eg.org/handle/10.1111/v30i5pp1493-15022022-03-28T09:09:46Z2011-01-01T00:00:00Zdc.title: Deformable 3D Shape Registration Based on Local Similarity Transforms
dc.contributor.author: Papazov, Chavdar; Burschka, Darius
dc.contributor.editor: Mario Botsch and Scott Schaefer
dc.description.abstract: In this paper, a new method for deformable 3D shape registration is proposed. The algorithm computes shape transitions based on local similarity transforms which allows to model not only as-rigid-as-possible deformations but also local and global scale. We formulate an ordinary differential equation (ODE) which describes the transition of a source shape towards a target shape. We assume that both shapes are roughly pre-aligned (e.g., frames of a motion sequence). The ODE consists of two terms. The first one causes the deformation by pulling the source shape points towards corresponding points on the target shape. Initial correspondences are estimated by closestpoint search and then refined by an efficient smoothing scheme. The second term regularizes the deformation by drawing the points towards locally defined rest positions. These are given by the optimal similarity transform which matches the initial (undeformed) neighborhood of a source point to its current (deformed) neighborhood. The proposed ODE allows for a very efficient explicit numerical integration. This avoids the repeated solution of large linear systems usually done when solving the registration problem within general-purpose non-linear optimization frameworks. We experimentally validate the proposed method on a variety of real data and perform a comparison with several state-of-the-art approaches.
2011-01-01T00:00:00Z