36-Issue 5

Permanent URI for this collection

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

Browse

Now showing 1 - 18 of 18

Adjoint Map Representation for Shape Analysis and Matching
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Huang, Ruqi; Ovsjanikov, Maks; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
In this paper, we propose to consider the adjoint operators of functional maps, and demonstrate their utility in several tasks in geometry processing. Unlike a functional map, which represents a correspondence simply using the pull-back of function values, the adjoint operator reflects both the map and its distortion with respect to given inner products. We argue that this property of adjoint operators and especially their relation to the map inverse under the choice of different inner products, can be useful in applications including bi-directional shape matching, shape exploration, and pointwise map recovery among others. In particular, in this paper, we show that the adjoint operators can be used within the cycle-consistency framework to encode and reveal the presence or lack of consistency between distortions in a collection, in a way that is complementary to the previously used purely map-based consistency measures.We also show how the adjoint can be used for matching pairs of shapes, by accounting for maps in both directions, can help in recovering point-to-point maps from their functional counterparts, and describe how it can shed light on the role of functional basis selection.
A Constrained Resampling Strategy for Mesh Improvement
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Abdelkader, Ahmed; Mahmoud, Ahmed H.; Rushdi, Ahmad A.; Mitchell, Scott A.; Owens, John D.; Ebeida, Mohamed S.; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
In many geometry processing applications, it is required to improve an initial mesh in terms of multiple quality objectives. Despite the availability of several mesh generation algorithms with provable guarantees, such generated meshes may only satisfy a subset of the objectives. The conflicting nature of such objectives makes it challenging to establish similar guarantees for each combination, e.g., angle bounds and vertex count. In this paper, we describe a versatile strategy for mesh improvement by interpreting quality objectives as spatial constraints on resampling and develop a toolbox of local operators to improve the mesh while preserving desirable properties. Our strategy judiciously combines smoothing and transformation techniques allowing increased flexibility to practically achieve multiple objectives simultaneously. We apply our strategy to both planar and surface meshes demonstrating how to simplify Delaunay meshes while preserving element quality, eliminate all obtuse angles in a complex mesh, and maximize the shortest edge length in a Voronoi tessellation far better than the state-of-the-art.
Deblurring and Denoising of Maps between Shapes
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Ezuz, Danielle; Ben-Chen, Mirela; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
Shape correspondence is an important and challenging problem in geometry processing. Generalized map representations, such as functional maps, have been recently suggested as an approach for handling difficult mapping problems, such as partial matching and matching shapes with high genus, within a generic framework. While this idea was shown to be useful in various scenarios, such maps only provide low frequency information on the correspondence. In many applications, such as texture transfer and shape interpolation, a high quality pointwise map that can transport high frequency data between the shapes is required. We name this problem map deblurring and propose a robust method, based on a smoothness assumption, for its solution. Our approach is suitable for non-isometric shapes, is robust to mesh tessellation and accurately recovers vertex-to-point, or precise, maps. Using the same framework we can also handle map denoising, namely improvement of given pointwise maps from various sources. We demonstrate that our approach outperforms the state-of-the-art for both deblurring and denoising of maps on benchmarks of non-isometric shapes, and show an application to high quality intrinsic symmetry computation.
A Dirac Operator for Extrinsic Shape Analysis
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Liu, Hsueh-Ti Derek; Jacobson, Alec; Crane, Keenan; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
The eigenfunctions and eigenvalues of the Laplace-Beltrami operator have proven to be a powerful tool for digital geometry processing, providing a description of geometry that is essentially independent of coordinates or the choice of discretization. However, since Laplace-Beltrami is purely intrinsic it struggles to capture important phenomena such as extrinsic bending, sharp edges, and fine surface texture. We introduce a new extrinsic differential operator called the relative Dirac operator, leading to a family of operators with a continuous trade-off between intrinsic and extrinsic features. Previous operators are either fully or partially intrinsic. In contrast, the proposed family spans the entire spectrum: from completely intrinsic (depending only on the metric) to completely extrinsic (depending only on the Gauss map). By adding an infinite potential well to this (or any) operator we can also robustly handle surface patches with irregular boundary. We explore use of these operators for a variety of shape analysis tasks, and study their performance relative to operators previously found in the geometry processing literature.
Evaluating Hex-mesh Quality Metrics via Correlation Analysis
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Gao, Xifeng; Huang, Jin; Xu, Kaoji; Pan, Zherong; Deng, Zhigang; Chen, Guoning; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
Hexahedral (hex-) meshes are important for solving partial differential equations (PDEs) in applications of scientific computing and mechanical engineering. Many methods have been proposed aiming to generate hex-meshes with high scaled Jacobians. While it is well established that a hex-mesh should be inversion-free (i.e. have a positive Jacobian measured at every corner of its hexahedron), it is not well-studied that whether the scaled Jacobian is the most effective indicator of the quality of simulations performed on inversion-free hex-meshes given the existing dozens of quality metrics for hex-meshes. Due to the challenge of precisely defining the relations among metrics, studying the correlations among different quality metrics and their correlations with the stability and accuracy of the simulations is a first and effective approach to address the above question. In this work, we propose a correlation analysis framework to systematically study these correlations. Specifically, given a large hex-mesh dataset, we classify the existing quality metrics into groups based on their correlations, which characterizes their similarity in measuring the quality of hex-elements. In addition, we rank the individual metrics based on their correlations with the accuracy and stability metrics for simulations that solve a number of elliptic PDE problems. Our preliminary experiments suggest that metrics that assess the conditioning of the elements are more correlated to the quality of solving elliptic PDEs than the others. Furthermore, an inversion-free hex-mesh with higher average quality (measured by any quality metrics) usually leads to a more accurate and stable computation of elliptic PDEs. To support our correlation study and address the lack of a publicly available large hex-mesh dataset with sufficiently varying quality metric values, we also propose a two-level perturbation strategy to generate the desired dataset from a small number of meshes to exclude the influences of element numbers, vertex connectivity, and volume sizes to our study.
Fast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshes
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Qin, Yipeng; Yu, Hongchuan; Zhang, Jiangjun; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
Geodesic based Voronoi diagrams play an important role in many applications of computer graphics. Constructing such Voronoi diagrams usually resorts to exact geodesics. However, exact geodesic computation always consumes lots of time and memory, which has become the bottleneck of constructing geodesic based Voronoi diagrams. In this paper, we propose the window-VTP algorithm, which can effectively reduce redundant computation and save memory. As a result, constructing Voronoi diagrams using the proposed window-VTP algorithm runs 3-8 times faster than Liu et al.'s method [LCT11], 1.2 times faster than its FWP-MMP variant and more importantly uses 10-70 times less memory than both of them.
Fast Planar Harmonic Deformations with Alternating Tangential Projections
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Hefetz, Eden Fedida; Chien, Edward; Weber, Ofir; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
We present a planar harmonic cage-based deformation method with local injectivity and bounded distortion guarantees, that is significantly faster than state-of-the-art methods with similar guarantees, and allows for real-time interaction. With a convex proxy for a near-convex characterization of the bounded distortion harmonic mapping space from [LW16], we utilize a modified alternating projection method (referred to as ATP) to project to this proxy. ATP draws inspiration from [KABL15] and restricts every other projection to lie in a tangential hyperplane. In contrast to [KABL15], our convex setting allows us to show that ATP is provably convergent (and is locally injective). Compared to the standard alternating projection method, it demonstrates superior convergence in fewer iterations, and it is also embarrassingly parallel, allowing for straightforward GPU implementation. Both of these factors combine to result in unprecedented speed. The convergence proof generalizes to arbitrary pairs of intersecting convex sets, suggesting potential use in other applications. Additional theoretical results sharpen the near-convex characterization that we use and demonstrate that it is homeomorphic to the bounded distortion harmonic mapping space (instead of merely being bijective).
Generalized Matryoshka: Computational Design of Nesting Objects
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Jacobson, Alec; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
This paper generalizes the self-similar nesting of Matryoshka dolls (''Russian nesting dolls'') to arbitrary solid objects. We introduce the problem of finding the largest scale replica of an object that nests inside itself. Not only should the nesting object fit inside the larger copy without interpenetration, but also it should be possible to cut the larger copy in two and remove the smaller object without collisions. We present a GPU-accelerated evaluation of nesting feasibility. This test can be conducted at interactive rates, providing feedback during manual design. Further, we may optimize for some or all of the nesting degrees of freedom (e.g., rigid motion of smaller object, cut orientation) to maximize the smaller object's scale while maintaining a feasible nesting. Our formulation and tools robustly handle imperfect geometric representations and generalize to the nesting of dissimilar objects in one another. We explore a variety of applications to aesthetic and functional shape design.
GWCNN: A Metric Alignment Layer for Deep Shape Analysis
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Ezuz, Danielle; Solomon, Justin; Kim, Vladimir G.; Ben-Chen, Mirela; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
Deep neural networks provide a promising tool for incorporating semantic information in geometry processing applications. Unlike image and video processing, however, geometry processing requires handling unstructured geometric data, and thus data representation becomes an important challenge in this framework. Existing approaches tackle this challenge by converting point clouds, meshes, or polygon soups into regular representations using, e.g., multi-view images, volumetric grids or planar parameterizations. In each of these cases, geometric data representation is treated as a fixed pre-process that is largely disconnected from the machine learning tool. In contrast, we propose to optimize for the geometric representation during the network learning process using a novel metric alignment layer. Our approach maps unstructured geometric data to a regular domain by minimizing the metric distortion of the map using the regularized Gromov-Wasserstein objective. This objective is parameterized by the metric of the target domain and is differentiable; thus, it can be easily incorporated into a deep network framework. Furthermore, the objective aims to align the metrics of the input and output domains, promoting consistent output for similar shapes. We show the effectiveness of our layer within a deep network trained for shape classification, demonstrating state-of-the-art performance for nonrigid shapes.
Isometry-Aware Preconditioning for Mesh Parameterization
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Claici, Sebastian; Bessmeltsev, Mikhail; Schaefer, Scott; Solomon, Justin; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
This paper presents a new preconditioning technique for large-scale geometric optimization problems, inspired by applications in mesh parameterization. Our positive (semi-)definite preconditioner acts on the gradients of optimization problems whose variables are positions of the vertices of a triangle mesh in R2 or of a tetrahedral mesh in R3, converting localized distortion gradients into the velocity of a globally near-rigid motion via a linear solve. We pose our preconditioning tool in terms of the Killing energy of a deformation field and provide new efficient formulas for constructing Killing operators on triangle and tetrahedral meshes. We demonstrate that our method is competitive with state-of-the-art algorithms for locally injective parameterization using a variety of optimization objectives and show applications to two- and three-dimensional mesh deformation.
Modeling and Exploring Co-variations in the Geometry and Configuration of Man-made 3D Shape Families
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Laga, Hamid; Tabia, Hedi; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
We introduce co-variation analysis as a tool for modeling the way part geometries and configurations co-vary across a family of man-made 3D shapes. While man-made 3D objects exhibit large geometric and structural variations, the geometry, structure, and configuration of their individual components usually do not vary independently from each other but in a correlated fashion. The size of the body of an airplane, for example, constrains the range of deformations its wings can undergo to ensure that the entire object remains a functionally-valid airplane. These co-variation constraints, which are often non-linear, can be either physical, and thus they can be explicitly enumerated, or implicit to the design and style of the shape family. In this article, we propose a data-driven approach, which takes pre-segmented 3D shapes with known component-wise correspondences and learns how various geometric and structural properties of their components co-vary across the set. We demonstrate, using a variety of 3D shape families, the utility of the proposed co-variation analysis in various applications including 3D shape repositories exploration and shape editing where the propagation of deformations is guided by the co-variation analysis. We also show that the framework can be used for context-guided orientation of objects in 3D scenes.
A Parallel Approach to Compression and Decompression of Triangle Meshes using the GPU
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Jakob, Johannes; Buchenau, Christoph; Guthe, Michael; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
Most state-of-the-art compression algorithms use complex connectivity traversal and prediction schemes, which are not efficient enough for online compression of large meshes. In this paper we propose a scalable massively parallel approach for compression and decompression of large triangle meshes using the GPU. Our method traverses the input mesh in a parallel breadth-first manner and encodes the connectivity data similarly to the well known cut-border machine. Geometry data is compressed using a local prediction strategy. In contrast to the original cut-border machine, we can additionally handle triangle meshes with inconsistently oriented faces. Our approach is more than one order of magnitude faster than currently used methods and achieves competitive compression rates.
Restricting Voronoi Diagrams to Meshes Using Corner Validation
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Sainlot, Maxime; Nivoliers, Vincent; Attali, Dominique; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
Restricted Voronoi diagrams are a fundamental geometric structure used in many applications such as surface reconstruction from point sets or optimal transport. Given a set of sites V and a mesh X with vertices in Rd connected by triangles, the restricted Voronoi diagram partitions X by computing for each site the portion of X for which the site is the nearest. The restricted Voronoi diagram is the intersection between the regular Voronoi diagram and the mesh. Depending on the site distribution or the ambient space dimension computing the regular Voronoi diagram may not be feasible using classical algorithms. In this paper, we extend Lévy and Bonneel's approach [LB12] based on nearest neighbor queries. We show that their method is limited when the sites are not located on X. We propose a new algorithm for computing restricted Voronoi which reduces the number of sites considered for each triangle of the mesh and scales smoothly when the sites are far from the surface.
The Shape Variational Autoencoder: A Deep Generative Model of Part-segmented 3D Objects
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Nash, Charlie; Williams, Chris K. I.; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
We introduce a generative model of part-segmented 3D objects: the shape variational auto-encoder (ShapeVAE). The ShapeVAE describes a joint distribution over the existence of object parts, the locations of a dense set of surface points, and over surface normals associated with these points. Our model makes use of a deep encoder-decoder architecture that leverages the partdecomposability of 3D objects to embed high-dimensional shape representations and sample novel instances. Given an input collection of part-segmented objects with dense point correspondences the ShapeVAE is capable of synthesizing novel, realistic shapes, and by performing conditional inference enables imputation of missing parts or surface normals. In addition, by generating both points and surface normals, our model allows for the use of powerful surface-reconstruction methods for mesh synthesis. We provide a quantitative evaluation of the ShapeVAE on shape-completion and test-set log-likelihood tasks and demonstrate that the model performs favourably against strong baselines. We demonstrate qualitatively that the ShapeVAE produces plausible shape samples, and that it captures a semantically meaningful shape-embedding. In addition we show that the ShapeVAE facilitates mesh reconstruction by sampling consistent surface normals.
Spectral Affine-Kernel Embeddings
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Budninskiy, Max; Liu, Beibei; Tong, Yiying; Desbrun, Mathieu; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
In this paper, we propose a controllable embedding method for high- and low-dimensional geometry processing through sparse matrix eigenanalysis. Our approach is equally suitable to perform non-linear dimensionality reduction on big data, or to offer non-linear shape editing of 3D meshes and pointsets. At the core of our approach is the construction of a multi-Laplacian quadratic form that is assembled from local operators whose kernels only contain locally-affine functions. Minimizing this quadratic form provides an embedding that best preserves all relative coordinates of points within their local neighborhoods. We demonstrate the improvements that our approach brings over existing nonlinear dimensionality reduction methods on a number of datasets, and formulate the first eigen-based as-rigid-as-possible shape deformation technique by applying our affine-kernel embedding approach to 3D data augmented with user-imposed constraints on select vertices.
Stochastic Heat Kernel Estimation on Sampled Manifolds
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Aumentado-Armstrong, Tristan; Siddiqi, Kaleem; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
The heat kernel is a fundamental geometric object associated to every Riemannian manifold, used across applications in computer vision, graphics, and machine learning. In this article, we propose a novel computational approach to estimating the heat kernel of a statistically sampled manifold (e.g. meshes or point clouds), using its representation as the transition density function of Brownian motion on the manifold. Our approach first constructs a set of local approximations to the manifold via moving least squares. We then simulate Brownian motion on the manifold by stochastic numerical integration of the associated Ito diffusion system. By accumulating a number of these trajectories, a kernel density estimation method can then be used to approximate the transition density function of the diffusion process, which is equivalent to the heat kernel. We analyse our algorithm on the 2-sphere, as well as on shapes in 3D. Our approach is readily parallelizable and can handle manifold samples of large size as well as surfaces of high co-dimension, since all the computations are local. We relate our method to the standard approaches in diffusion geometry and discuss directions for future work.
Symposium on Geometry Processing 2017: Frontmatter
(Eurographics Association, 2017) Bærentzen, Jakob Andreas; Hildebrandt, Klaus; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
Ternary Sparse Matrix Representation for Volumetric Mesh Subdivision and Processing on GPUs
(The Eurographics Association and John Wiley & Sons Ltd., 2017) Mueller-Roemer, Johannes Sebastian; Altenhofen, Christian; Stork, André; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
In this paper, we present a novel volumetric mesh representation suited for parallel computing on modern GPU architectures. The data structure is based on a compact, ternary sparse matrix storage of boundary operators. Boundary operators correspond to the first-order top-down relations of k-faces to their (k-1)-face facets. The compact, ternary matrix storage format is based on compressed sparse row matrices with signed indices and allows for efficient parallel computation of indirect and bottomup relations. This representation is then used in the implementation of several parallel volumetric mesh algorithms including Laplacian smoothing and volumetric Catmull-Clark subdivision. We compare these algorithms with their counterparts based on OpenVolumeMesh and achieve speedups from 3x to 531x, for sufficiently large meshes, while reducing memory consumption by up to 36%.

Browse

Browsing 36-Issue 5 by Title

Results Per Page

Sort Options