SGP13: Eurographics Symposium on Geometry Processing (CGF 32-5)

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/14332

Browse

Now showing 1 - 20 of 24

Preface and Table of Contents
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Yaron Lipman and Hao Zhang
Consistent Shape Maps via Semidefinite Programming
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Huang, Qi-Xing; Guibas, Leonidas; Yaron Lipman and Hao Zhang
Recent advances in shape matching have shown that jointly optimizing the maps among the shapes in a collection can lead to significant improvements when compared to estimating maps between pairs of shapes in isolation. These methods typically invoke a cycle-consistency criterion - the fact that compositions of maps along a cycle of shapes should approximate the identity map. This condition regularizes the network and allows for the correction of errors and imperfections in individual maps. In particular, it encourages the estimation of maps between dissimilar shapes by compositions of maps along a path of more similar shapes. In this paper, we introduce a novel approach for obtaining consistent shape maps in a collection that formulates the cycle-consistency constraint as the solution to a semidefinite program (SDP). The proposed approach is based on the observation that, if the ground truth maps between the shapes are cycle-consistent, then the matrix that stores all pair-wise maps in blocks is low-rank and positive semidefinite. Motivated by recent advances in techniques for low-rank matrix recovery via semidefinite programming, we formulate the problem of estimating cycle-consistent maps as finding the closest positive semidefinite matrix to an input matrix that stores all the initial maps. By analyzing the Karush-Kuhn-Tucker (KKT) optimality condition of this program, we derive theoretical guarantees for the proposed algorithm, ensuring the correctness of the recovery when the errors in the inputs maps do not exceed certain thresholds. Besides this theoretical guarantee, experimental results on benchmark datasets show that the proposed approach outperforms state-of-the-art multiple shape matching methods.
Sparse Iterative Closest Point
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Bouaziz, Sofien; Tagliasacchi, Andrea; Pauly, Mark; Yaron Lipman and Hao Zhang
Rigid registration of two geometric data sets is essential in many applications, including robot navigation, surface reconstruction, and shape matching. Most commonly, variants of the Iterative Closest Point (ICP) algorithm are employed for this task. These methods alternate between closest point computations to establish correspondences between two data sets, and solving for the optimal transformation that brings these correspondences into alignment. A major difficulty for this approach is the sensitivity to outliers and missing data often observed in 3D scans. Most practical implementations of the ICP algorithm address this issue with a number of heuristics to prune or reweight correspondences. However, these heuristics can be unreliable and difficult to tune, which often requires substantial manual assistance. We propose a new formulation of the ICP algorithm that avoids these difficulties by formulating the registration optimization using sparsity inducing norms. Our new algorithm retains the simple structure of the ICP algorithm, while achieving superior registration results when dealing with outliers and incomplete data. The complete source code of our implementation is provided at http://lgg.epfl.ch/sparseicp.
Weak Convex Decomposition by Lines-of-sight
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Asafi, Shmuel; Goren, Avi; Cohen-Or, Daniel; Yaron Lipman and Hao Zhang
We define the convexity rank of a set of points to be the portion of mutually visible pairs of points out of the total number of pairs. Based on this definition of weak convexity, we introduce a spectral method that decomposes a given shape into weakly convex regions. The decomposition is applied without explicitly measuring the convexity rank. The method merely amounts to a spectral clustering of a matrix representing the all-pairs line of sight. Our method can be directly applied on an oriented point cloud and does not require any topological information, nor explicit concavity or convexity measures. We demonstrate the efficiency of our algorithm on a large number of examples and compare them qualitatively with competitive approaches.
Shape Matching via Quotient Spaces
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Ovsjanikov, Maks; Mérigot, Quentin; Patraucean, Viorica; Guibas, Leonidas; Yaron Lipman and Hao Zhang
We introduce a novel method for non-rigid shape matching, designed to address the symmetric ambiguity problem present when matching shapes with intrinsic symmetries. Unlike the majority of existing methods which try to overcome this ambiguity by sampling a set of landmark correspondences, we address this problem directly by performing shape matching in an appropriate quotient space, where the symmetry has been identified and factored out. This allows us to both simplify the shape matching problem by matching between subspaces, and to return multiple solutions with equally good dense correspondences. Remarkably, both symmetry detection and shape matching are done without establishing any landmark correspondences between either points or parts of the shapes. This allows us to avoid an expensive combinatorial search present in most intrinsic symmetry detection and shape matching methods. We compare our technique with state-of-the-art methods and show that superior performance can be achieved both when the symmetry on each shape is known and when it needs to be estimated.
Bijective Composite Mean Value Mappings
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Schneider, Teseo; Hormann, Kai; Floater, Michael S.; Yaron Lipman and Hao Zhang
We introduce the novel concept of composite barycentric mappings and give theoretical conditions under which they are guaranteed to be bijective. We then focus on mean value mappings and derive a simple procedure for computing their Jacobians, leading to an efficient GPU-assisted implementation for interactively designing composite mean value mappings which are bijective up to pixel resolution. We provide a number of examples of 2D image deformation and an example of 3D shape deformation based on a natural extension of the concept to spatial mappings.
Dynamic Maps for Exploring and Browsing Shapes
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Kleiman, Yanir; Fish, Noa; Lanir, Joel; Cohen-Or, Daniel; Yaron Lipman and Hao Zhang
Large datasets of 3D objects require an intuitive way to browse and quickly explore shapes from the collection. We present a dynamic map of shapes where similar shapes are placed next to each other. Similarity between 3D models exists in a high dimensional space which cannot be accurately expressed in a two dimensional map. We solve this discrepancy by providing a local map with pan capabilities and a user interface that resembles an online experience of navigating through geographical maps. As the user navigates through the map, new shapes appear which correspond to the specific navigation tendencies and interests of the user, while maintaining a continuous browsing experience. In contrast with state of the art methods which typically reduce the search space by selecting constraints or employing relevance feedback, our method enables exploration of large sets without constraining the search space, allowing the user greater creativity and serendipity. A user study evaluation showed a strong preference of users for our method over a standard relevance feedback method.
Practical Anisotropic Geodesy
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Campen, Marcel; Heistermann, Martin; Kobbelt, Leif; Yaron Lipman and Hao Zhang
The computation of intrinsic, geodesic distances and geodesic paths on surfaces is a fundamental low-level building block in countless Computer Graphics and Geometry Processing applications. This demand led to the development of numerous algorithms - some for the exact, others for the approximative computation, some focussing on speed, others providing strict guarantees. Most of these methods are designed for computing distances according to the standard Riemannian metric induced by the surface's embedding in Euclidean space. Generalization to other, especially anisotropic, metrics - which more recently gained interest in several application areas - is not rarely hampered by fundamental problems. We explore and discuss possibilities for the generalization and extension of well-known methods to the anisotropic case, evaluate their relative performance in terms of accuracy and speed, and propose a novel algorithm, the Short-Term Vector Dijkstra. This algorithm is strikingly simple to implement and proves to provide practical accuracy at a higher speed than generalized previous methods.
Locally Injective Mappings
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Schüller, Christian; Kavan, Ladislav; Panozzo, Daniele; Sorkine-Hornung, Olga; Yaron Lipman and Hao Zhang
Mappings and deformations are ubiquitous in geometry processing, shape modeling, and animation. Numerous deformation energies have been proposed to tackle problems like mesh parameterization and volumetric deformations. We present an algorithm that modifies any deformation energy to guarantee a locally injective mapping, i.e., without inverted elements. Our formulation can be used to compute continuous planar or volumetric piecewise-linear maps and it uses a barrier term to prevent inverted elements. Differently from previous methods, we carefully design both the barrier term and the associated numerical techniques to be able to provide immediate feedback to the user, enabling interactive manipulation of inversion-free mappings. Stress tests show that our method robustly handles extreme deformations where previous techniques converge very slowly or even fail. We demonstrate that enforcing local injectivity increases fidelity of the results in applications such as shape deformation and parameterization.
Consistent Volumetric Discretizations Inside Self-Intersecting Surfaces
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Sacht, Leonardo; Jacobson, Alec; Panozzo, Daniele; Schüller, Christian; Sorkine-Hornung, Olga; Yaron Lipman and Hao Zhang
Decades of research have culminated in a robust geometry processing pipeline for surfaces. Most steps in this pipeline, like deformation, smoothing, subdivision and decimation, may create self-intersections. Volumetric processing of solid shapes then becomes difficult, because obtaining a correct volumetric discretization is impossible: existing tet-meshing methods require watertight input. We propose an algorithm that produces a tetrahedral mesh that overlaps itself consistently with the self-intersections in the input surface. This enables volumetric processing on self-intersecting models. We leverage conformalized mean-curvature flow, which removes self-intersections, and define an intrinsically similar reverse flow, which prevents them. We tetrahedralize the resulting surface and map the mesh inside the original surface. We demonstrate the effectiveness of our method with applications to automatic skinning weight computation, physically based simulation and geodesic distance computation.
An Algorithm for Triangulating Multiple 3D Polygons
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Zou, Ming; Ju, Tao; Carr, Nathan; Yaron Lipman and Hao Zhang
We present an algorithm for obtaining a triangulation of multiple, non-planar 3D polygons. The output minimizes additive weights, such as the total triangle areas or the total dihedral angles between adjacent triangles. Our algorithm generalizes a classical method for optimally triangulating a single polygon. The key novelty is a mechanism for avoiding non-manifold outputs for two and more input polygons without compromising optimality. For better performance on real-world data, we also propose an approximate solution by feeding the algorithm with a reduced set of triangles. In particular, we demonstrate experimentally that the triangles in the Delaunay tetrahedralization of the polygon vertices offer a reasonable trade off between performance and optimality.
Noise-Adaptive Shape Reconstruction from Raw Point Sets
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Giraudot, Simon; Cohen-Steiner, David; Alliez, Pierre; Yaron Lipman and Hao Zhang
We propose a noise-adaptive shape reconstruction method specialized to smooth, closed shapes. Our algorithm takes as input a defect-laden point set with variable noise and outliers, and comprises three main steps. First, we compute a novel noise-adaptive distance function to the inferred shape, which relies on the assumption that the inferred shape is a smooth submanifold of known dimension. Second, we estimate the sign and confidence of the function at a set of seed points, through minimizing a quadratic energy expressed on the edges of a uniform random graph. Third, we compute a signed implicit function through a random walker approach with soft constraints chosen as the most confident seed points computed in previous step.
Dirichlet Energy for Analysis and Synthesis of Soft Maps
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Solomon, Justin; Guibas, Leonidas; Butscher, Adrian; Yaron Lipman and Hao Zhang
Soft maps taking points on one surface to probability distributions on another are attractive for representing surface mappings in the presence of symmetry, ambiguity, and combinatorial complexity. Few techniques, however, are available to measure their continuity and other properties. To this end, we introduce a novel Dirichlet energy for soft maps generalizing the classical map Dirichlet energy, which measures distortion by computing how soft maps transport probabilistic mass from one distribution to another. We formulate the computation of the Dirichlet energy in terms of a differential equation and provide a finite elements discretization that enables all of the quantities introduced to be computed. We demonstrate the effectiveness of our framework for understanding soft maps arising from various sources. Furthermore, we suggest how these energies can be applied to generate continuous soft or point-to-point maps.
Fitting Polynomial Volumes to Surface Meshes with Voronoï Squared Distance Minimization
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Paillé, Gilles-Philippe; Poulin, Pierre; Lévy, Bruno; Yaron Lipman and Hao Zhang
We propose a method for mapping polynomial volumes. Given a closed surface and an initial template volume grid, our method deforms the template grid by fitting its boundary to the input surface while minimizing a volume distortion criterion. The result is a point-to-point map distorting linear cells into curved ones. Our method is based on several extensions of Voronoi Squared Distance Minimization (VSDM) combined with a higher-order finite element formulation of the deformation energy. This allows us to globally optimize the mapping without prior parameterization. The anisotropic VSDM formulation allows for sharp and semi-sharp features to be implicitly preserved without tagging. We use a hierarchical finite element function basis that selectively adapts to the geometric details. This makes both the method more efficient and the representation more compact. We apply our method to geometric modeling applications in computer-aided design and computer graphics, including mixed-element meshing, mesh optimization, subdivision volume fitting, and shell meshing.
Semantizing Complex 3D Scenes using Constrained Attribute Grammars
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Boulch, Alexandre; Houllier, Simon; Marlet, Renaud; Tournaire, Olivier; Yaron Lipman and Hao Zhang
We propose a new approach to automatically semantize complex objects in a 3D scene. For this, we define an expressive formalism combining the power of both attribute grammars and constraint. It offers a practical conceptual interface, which is crucial to write large maintainable specifications. As recursion is inadequate to express large collections of items, we introduce maximal operators, that are essential to reduce the parsing search space. Given a grammar in this formalism and a 3D scene, we show how to automatically compute a shared parse forest of all interpretations - in practice, only a few, thanks to relevant constraints. We evaluate this technique for building model semantization using CAD model examples as well as photogrammetric and simulated LiDAR data.
Consolidation of Low-quality Point Clouds from Outdoor Scenes
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Wang, Jun; Xu, Kai; Liu, Ligang; Cao, Junjie; Liu, Shengjun; Yu, Zeyun; Gu, Xianfeng David; Yaron Lipman and Hao Zhang
The emergence of laser/LiDAR sensors, reliable multi-view stereo techniques and more recently consumer depth cameras have brought point clouds to the forefront as a data format useful for a number of applications. Unfortunately, the point data from those channels often incur imperfection, frequently contaminated with severe outliers and noise. This paper presents a robust consolidation algorithm for low-quality point data from outdoor scenes, which essentially consists of two steps: 1) outliers filtering and 2) noise smoothing. We first design a connectivitybased scheme to evaluate outlierness and thereby detect sparse outliers. Meanwhile, a clustering method is used to further remove small dense outliers. Both outlier removal methods are insensitive to the choice of the neighborhood size and the levels of outliers. Subsequently, we propose a novel approach to estimate normals for noisy points based on robust partial rankings, which is the basis of noise smoothing. Accordingly, a fast approach is exploited to smooth noise, while preserving sharp features. We evaluate the effectiveness of the proposed method on the point clouds from a variety of outdoor scenes.
An Operator Approach to Tangent Vector Field Processing
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Azencot, Omri; Ben-Chen, Mirela; Chazal, Frédéric; Ovsjanikov, Maks; Yaron Lipman and Hao Zhang
In this paper, we introduce a novel coordinate-free method for manipulating and analyzing vector fields on discrete surfaces. Unlike the commonly used representations of a vector field as an assignment of vectors to the faces of the mesh, or as real values on edges, we argue that vector fields can also be naturally viewed as operators whose domain and range are functions defined on the mesh. Although this point of view is common in differential geometry it has so far not been adopted in geometry processing applications. We recall the theoretical properties of vector fields represented as operators, and show that composition of vector fields with other functional operators is natural in this setup. This leads to the characterization of vector field properties through commutativity with other operators such as the Laplace-Beltrami and symmetry operators, as well as to a straight-forward definition of differential properties such as the Lie derivative. Finally, we demonstrate a range of applications, such as Killing vector field design, symmetric vector field estimation and joint design on multiple surfaces.
Connectivity Editing for Quad-Dominant Meshes
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Peng, Chi-Han; Wonka, Peter; Yaron Lipman and Hao Zhang
We propose a connectivity editing framework for quad-dominant meshes. In our framework, the user can edit the mesh connectivity to control the location, type, and number of irregular vertices (with more or fewer than four neighbors) and irregular faces (non-quads). We provide a theoretical analysis of the problem, discuss what edits are possible and impossible, and describe how to implement an editing framework that realizes all possible editing operations. In the results, we show example edits and illustrate the advantages and disadvantages of different strategies for quad-dominant mesh design.
PHOG: Photometric and Geometric Functions for Textured Shape Retrieval
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Biasotti, Silvia; Cerri, Andrea; Giorgi, Daniela; Spagnuolo, Michaela; Yaron Lipman and Hao Zhang
In this paper we target the problem of textured 3D object retrieval. As a first contribution, we show how to include photometric information in the persistence homology setting, also proposing a novel theoretical result about multidimensional persistence spaces. As a second contribution, we introduce a generalization of the integral geodesic distance which fuses shape and color properties. Finally, we adopt a purely geometric description based on the selection of geometric functions that are mutually independent. The photometric, hybrid and geometric descriptions are combined into a signature, whose performance is tested on a benchmark dataset.
Fast and Robust Approximation of Smallest Enclosing Balls in Arbitrary Dimensions
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Larsson, Thomas; Källberg, Linus; Yaron Lipman and Hao Zhang
In this paper, an algorithm is introduced that computes an arbitrarily fine approximation of the smallest enclosing ball of a point set in any dimension. This operation is important in, for example, classification, clustering, and data mining. The algorithm is very simple to implement, gives reliable results, and gracefully handles large problem instances in low and high dimensions, as confirmed by both theoretical arguments and empirical evaluation. For example, using a CPU with eight cores, it takes less than two seconds to compute a 1:001-approximation of the smallest enclosing ball of one million points uniformly distributed in a hypercube in dimension 200. Furthermore, the presented approach extends to a more general class of input objects, such as ball sets.

Browse

Browsing SGP13: Eurographics Symposium on Geometry Processing (CGF 32-5) by Issue Date

Results Per Page

Sort Options