39-Issue 5

Permanent URI for this collection

Geometry Processing 2020 - Symposium Proceedings
Utrecht, The Netherlands, July 6 – 8, 2020

Computational Geometry and Fabrication
Medial Axis Isoperimetric Profiles
Paul Zhang, Daryl DeFord, and Justin Solomon
Fabricable Unobtrusive 3D-QR-Codes with Directional Light
Hao Peng, Peiqing Liu, Lin Lu, Andrei Sharf, Lin Liu, Dani Lischinski, and Baoquan Chen
Approximating Isosurfaces by Guaranteed-quality Triangular Meshes
Joel Hass and Maria Trnkova
Discrete Differential Geometry
Interpolated Corrected Curvature Measures for Polygonal Surfaces
Jacques-Olivier Lachaud, Pascal Romon, Boris Thibert, and David Coeurjolly
Properties of Laplace Operators for Tetrahedral Meshes
Marc Alexa, Philipp Herholz, Max Kohlbrenner, and Olga Sorkine-Hornung
A Laplacian for Nonmanifold Triangle Meshes
Nicholas Sharp and Keenan Crane
A Simple Discretization of the Vector Dirichlet Energy
Oded Stein, Max Wardetzky, Alec Jacobson, and Eitan Grinspun
Deformation
Interactive Sculpting of Digital Faces Using an Anatomical Modeling Paradigm
Aurel Gruber, Marco Fratarcangeli, Gaspard Zoss, Roman Cattaneo, Thabo Beeler, Markus Gross, and Derek Bradley
A Parametric Analysis of Discrete Hamiltonian Functional Maps
Emilian Postolache, Marco Fumero, Luca Cosmo, and Emanuele Rodolà
Nonlinear Deformation Synthesis via Sparse Principal Geodesic Analysis
Josua Sassen, Klaus Hildebrandt, and Martin Rumpf
Meshing
Hexahedral Mesh Repair via Sum-of-Squares Relaxation
Zoë Marschner, David Palmer, Paul Zhang, and Justin Solomon
Integer-Grid Sketch Simplification and Vectorization
Tibor Stanko, Mikhail Bessmeltsev, David Bommes, and Adrien Bousseau
Cost Minimizing Local Anisotropic Quad Mesh Refinement
Max Lyon, David Bommes, and Leif Kobbelt
Surface Reconstruction
Poisson Surface Reconstruction with Envelope Constraints
Misha Kazhdan, Ming Chuang, Szymon Rusinkiewicz, and Hugues Hoppe
Learning Part Boundaries from 3D Point Clouds
Marios Loizou, Melinos Averkiou, and Evangelos Kalogerakis
Topology-Aware Surface Reconstruction for Point Clouds
Rickard Brüel-Gabrielsson, Vignesh Ganapathi-Subramanian, Primoz Skraba, and Leonidas J. Guibas
Optimization
EGGS: Sparsity-Specific Code Generation
Xuan Tang, Teseo Schneider, Shoaib Kamil, Aurojit Panda, Jinyang Li, and Daniele Panozzo
Anderson Acceleration for Nonconvex ADMM Based on Douglas-Rachford Splitting
Wenqing Ouyang, Yue Peng, Yuxin Yao, Juyong Zhang, and Bailin Deng
Machine Learning and Analysis
DFR: Differentiable Function Rendering for Learning 3D Generation from Images
Yunjie Wu and Zhengxing Sun
Generating Adversarial Surfaces via Band-Limited Perturbations
Giorgio Mariani, Luca Cosmo, Alex M. Bronstein, and Emanuele Rodolà
Consistent ZoomOut: Efficient Spectral Map Synchronization
Ruqi Huang, Jing Ren, Peter Wonka, and Maks Ovsjanikov

BibTeX (39-Issue 5)
                
@article{
10.1111:cgf.14064,
journal = {Computer Graphics Forum}, title = {{
Medial Axis Isoperimetric Profiles}},
author = {
Zhang, Paul
and
DeFord, Daryl
and
Solomon, Justin
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14064}
}
                
@article{
10.1111:cgf.14065,
journal = {Computer Graphics Forum}, title = {{
Fabricable Unobtrusive 3D-QR-Codes with Directional Light}},
author = {
Peng, Hao
and
Liu, Peiqing
and
Lu, Lin
and
Sharf, Andrei
and
Liu, Lin
and
Lischinski, Dani
and
Chen, Baoquan
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14065}
}
                
@article{
10.1111:cgf.14066,
journal = {Computer Graphics Forum}, title = {{
Approximating Isosurfaces by Guaranteed-quality Triangular Meshes}},
author = {
Hass, Joel
and
Trnkova, Maria
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14066}
}
                
@article{
10.1111:cgf.14067,
journal = {Computer Graphics Forum}, title = {{
Interpolated Corrected Curvature Measures for Polygonal Surfaces}},
author = {
Lachaud, Jacques-Olivier
and
Romon, Pascal
and
Thibert, Boris
and
Coeurjolly, David
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14067}
}
                
@article{
10.1111:cgf.14068,
journal = {Computer Graphics Forum}, title = {{
Properties of Laplace Operators for Tetrahedral Meshes}},
author = {
Alexa, Marc
and
Herholz, Philipp
and
Kohlbrenner, Max
and
Sorkine-Hornung, Olga
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14068}
}
                
@article{
10.1111:cgf.14069,
journal = {Computer Graphics Forum}, title = {{
A Laplacian for Nonmanifold Triangle Meshes}},
author = {
Sharp, Nicholas
and
Crane, Keenan
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14069}
}
                
@article{
10.1111:cgf.14070,
journal = {Computer Graphics Forum}, title = {{
A Simple Discretization of the Vector Dirichlet Energy}},
author = {
Stein, Oded
and
Wardetzky, Max
and
Jacobson, Alec
and
Grinspun, Eitan
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14070}
}
                
@article{
10.1111:cgf.14071,
journal = {Computer Graphics Forum}, title = {{
Interactive Sculpting of Digital Faces Using an Anatomical Modeling Paradigm}},
author = {
Gruber, Aurel
and
Fratarcangeli, Marco
and
Zoss, Gaspard
and
Cattaneo, Roman
and
Beeler, Thabo
and
Gross, Markus
and
Bradley, Derek
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14071}
}
                
@article{
10.1111:cgf.14072,
journal = {Computer Graphics Forum}, title = {{
A Parametric Analysis of Discrete Hamiltonian Functional Maps}},
author = {
Postolache, Emilian
and
Fumero, Marco
and
Cosmo, Luca
and
Rodolà, Emanuele
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14072}
}
                
@article{
10.1111:cgf.14073,
journal = {Computer Graphics Forum}, title = {{
Nonlinear Deformation Synthesis via Sparse Principal Geodesic Analysis}},
author = {
Sassen, Josua
and
Hildebrandt, Klaus
and
Rumpf, Martin
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14073}
}
                
@article{
10.1111:cgf.14074,
journal = {Computer Graphics Forum}, title = {{
Hexahedral Mesh Repair via Sum-of-Squares Relaxation}},
author = {
Marschner, Zoë
and
Palmer, David
and
Zhang, Paul
and
Solomon, Justin
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14074}
}
                
@article{
10.1111:cgf.14075,
journal = {Computer Graphics Forum}, title = {{
Integer-Grid Sketch Simplification and Vectorization}},
author = {
Stanko, Tibor
and
Bessmeltsev, Mikhail
and
Bommes, David
and
Bousseau, Adrien
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14075}
}
                
@article{
10.1111:cgf.14076,
journal = {Computer Graphics Forum}, title = {{
Cost Minimizing Local Anisotropic Quad Mesh Refinement}},
author = {
Lyon, Max
and
Bommes, David
and
Kobbelt, Leif
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14076}
}
                
@article{
10.1111:cgf.14077,
journal = {Computer Graphics Forum}, title = {{
Poisson Surface Reconstruction with Envelope Constraints}},
author = {
Kazhdan, Misha
and
Chuang, Ming
and
Rusinkiewicz, Szymon
and
Hoppe, Hugues
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14077}
}
                
@article{
10.1111:cgf.14078,
journal = {Computer Graphics Forum}, title = {{
Learning Part Boundaries from 3D Point Clouds}},
author = {
Loizou, Marios
and
Averkiou, Melinos
and
Kalogerakis, Evangelos
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14078}
}
                
@article{
10.1111:cgf.14079,
journal = {Computer Graphics Forum}, title = {{
Topology-Aware Surface Reconstruction for Point Clouds}},
author = {
Brüel-Gabrielsson, Rickard
and
Ganapathi-Subramanian, Vignesh
and
Skraba, Primoz
and
Guibas, Leonidas J.
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14079}
}
                
@article{
10.1111:cgf.14080,
journal = {Computer Graphics Forum}, title = {{
EGGS: Sparsity-Specific Code Generation}},
author = {
Tang, Xuan
and
Schneider, Teseo
and
Kamil, Shoaib
and
Panda, Aurojit
and
Li, Jinyang
and
Panozzo, Daniele
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14080}
}
                
@article{
10.1111:cgf.14081,
journal = {Computer Graphics Forum}, title = {{
Anderson Acceleration for Nonconvex ADMM Based on Douglas-Rachford Splitting}},
author = {
Ouyang, Wenqing
and
Peng, Yue
and
Yao, Yuxin
and
Zhang, Juyong
and
Deng, Bailin
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14081}
}
                
@article{
10.1111:cgf.14082,
journal = {Computer Graphics Forum}, title = {{
DFR: Differentiable Function Rendering for Learning 3D Generation from Images}},
author = {
Wu, Yunjie
and
Sun, Zhengxing
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14082}
}
                
@article{
10.1111:cgf.14083,
journal = {Computer Graphics Forum}, title = {{
Generating Adversarial Surfaces via Band-Limited Perturbations}},
author = {
Mariani, Giorgio
and
Cosmo, Luca
and
Bronstein, Alex M.
and
Rodolà, Emanuele
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14083}
}
                
@article{
10.1111:cgf.14084,
journal = {Computer Graphics Forum}, title = {{
Consistent ZoomOut: Efficient Spectral Map Synchronization}},
author = {
Huang, Ruqi
and
Ren, Jing
and
Wonka, Peter
and
Ovsjanikov, Maks
}, year = {
2020},
publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {
10.1111/cgf.14084}
}

Browse

Recent Submissions

Now showing 1 - 22 of 22
  • Item
    Geometry Processing 2020 CGF 39-5: Frontmatter
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Jacobson, Alec; Huang, Qixing; Jacobson, Alec and Huang, Qixing
  • Item
    Medial Axis Isoperimetric Profiles
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Zhang, Paul; DeFord, Daryl; Solomon, Justin; Jacobson, Alec and Huang, Qixing
    Recently proposed as a stable means of evaluating geometric compactness, the isoperimetric profile of a planar domain measures the minimum perimeter needed to inscribe a shape with prescribed area varying from 0 to the area of the domain. While this profile has proven valuable for evaluating properties of geographic partitions, existing algorithms for its computation rely on aggressive approximations and are still computationally expensive. In this paper, we propose a practical means of approximating the isoperimetric profile and show that for domains satisfying a ''thick neck'' condition, our approximation is exact. For more general domains, we show that our bound is still exact within a conservative regime and is otherwise an upper bound. Our method is based on a traversal of the medial axis which produces efficient and robust results. We compare our technique with the state-of-the-art approximation to the isoperimetric profile on a variety of domains and show significantly tighter bounds than were previously achievable.
  • Item
    Fabricable Unobtrusive 3D-QR-Codes with Directional Light
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Peng, Hao; Liu, Peiqing; Lu, Lin; Sharf, Andrei; Liu, Lin; Lischinski, Dani; Chen, Baoquan; Jacobson, Alec and Huang, Qixing
    QR code is a 2D matrix barcode widely used for product tracking, identification, document management and general marketing. Recently, there have been various attempts to utilize QR codes in 3D manufacturing by carving QR codes on the surface of the printed 3D shape. Nevertheless, significant shape editing and modulation may be required to allow readability of the embedded 3D-QR-codes with good decoding accuracy. In this paper, we introduce a novel QR code 3D fabrication framework aimed at unobtrusive embedding of 3D-QR-codes in the shape hence introducing minimal shape modulation. Essentially, our method computes bi-directional carvings in the 3D shape surface to obtain the black-and-white QR pattern. By using a directional light source, the black-and-white QR pattern emerges as lighted and shadow casted blocks on the shape respectively. To account for minimal modulation and elusiveness, we optimize the QR code carving w.r.t. shape geometry, visual disparity and light source position. Our technique employs a simulation of lighting phenomena through carved modules on the shape to ensure adequate contrast of the printed 3D-QR-code.
  • Item
    Approximating Isosurfaces by Guaranteed-quality Triangular Meshes
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Hass, Joel; Trnkova, Maria; Jacobson, Alec and Huang, Qixing
    We describe a new method for approximating an implicit surface F by a piecewise-flat triangulated surface whose triangles are as close as possible to equilateral. The main advantage is improved mesh quality which is guaranteed for smooth surfaces. The GradNormal algorithm generates a triangular mesh that gives a piecewise-differentiable approximation of F, with angles between 35.2 and 101.5 degrees. As the mesh size approaches 0, the mesh converges to F through surfaces that are isotopic to F.
  • Item
    Interpolated Corrected Curvature Measures for Polygonal Surfaces
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Lachaud, Jacques-Olivier; Romon, Pascal; Thibert, Boris; Coeurjolly, David; Jacobson, Alec and Huang, Qixing
    A consistent and yet practically accurate definition of curvature onto polyhedral meshes remains an open problem. We propose a new framework to define curvature measures, based on the Corrected Normal Current, which generalizes the normal cycle: it uncouples the positional information of the polyhedral mesh from its geometric normal vector field, and the user can freely choose the corrected normal vector field at vertices for curvature computations. A smooth surface is then built in the Grassmannian R3xS2 by simply interpolating the given normal vector field. Curvature measures are then computed using the usual Lipschitz-Killing forms, and we provide closed-form formulas per triangle. We prove a stability result with respect to perturbations of positions and normals. Our approach provides a natural scale-space for all curvature estimations, where the scale is given by the radius of the measuring ball. We show on experiments how this method outperforms state-of-the-art methods on clean and noisy data, and even achieves pointwise convergence on difficult polyhedral meshes like digital surfaces. The framework is also well suited to curvature computations using normal map information.
  • Item
    Properties of Laplace Operators for Tetrahedral Meshes
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Alexa, Marc; Herholz, Philipp; Kohlbrenner, Max; Sorkine-Hornung, Olga; Jacobson, Alec and Huang, Qixing
    Discrete Laplacians for triangle meshes are a fundamental tool in geometry processing. The so-called cotan Laplacian is widely used since it preserves several important properties of its smooth counterpart. It can be derived from different principles: either considering the piecewise linear nature of the primal elements or associating values to the dual vertices. Both approaches lead to the same operator in the two-dimensional setting. In contrast, for tetrahedral meshes, only the primal construction is reminiscent of the cotan weights, involving dihedral angles.We provide explicit formulas for the lesser-known dual construction. In both cases, the weights can be computed by adding the contributions of individual tetrahedra to an edge. The resulting two different discrete Laplacians for tetrahedral meshes only retain some of the properties of their two-dimensional counterpart. In particular, while both constructions have linear precision, only the primal construction is positive semi-definite and only the dual construction generates positive weights and provides a maximum principle for Delaunay meshes. We perform a range of numerical experiments that highlight the benefits and limitations of the two constructions for different problems and meshes.
  • Item
    A Laplacian for Nonmanifold Triangle Meshes
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Sharp, Nicholas; Crane, Keenan; Jacobson, Alec and Huang, Qixing
    We describe a discrete Laplacian suitable for any triangle mesh, including those that are nonmanifold or nonorientable (with or without boundary). Our Laplacian is a robust drop-in replacement for the usual cotan matrix, and is guaranteed to have nonnegative edge weights on both interior and boundary edges, even for extremely poor-quality meshes. The key idea is to build what we call a ''tufted cover'' over the input domain, which has nonmanifold vertices but manifold edges. Since all edges are manifold, we can flip to an intrinsic Delaunay triangulation; our Laplacian is then the cotan Laplacian of this new triangulation. This construction also provides a high-quality point cloud Laplacian, via a nonmanifold triangulation of the point set. We validate our Laplacian on a variety of challenging examples (including all models from Thingi10k), and a variety of standard tasks including geodesic distance computation, surface deformation, parameterization, and computing minimal surfaces.
  • Item
    A Simple Discretization of the Vector Dirichlet Energy
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Stein, Oded; Wardetzky, Max; Jacobson, Alec; Grinspun, Eitan; Jacobson, Alec and Huang, Qixing
    We present a simple and concise discretization of the covariant derivative vector Dirichlet energy for triangle meshes in 3D using Crouzeix-Raviart finite elements. The discretization is based on linear discontinuous Galerkin elements, and is simple to implement, without compromising on quality: there are two degrees of freedom for each mesh edge, and the sparse Dirichlet energy matrix can be constructed in a single pass over all triangles using a short formula that only depends on the edge lengths, reminiscent of the scalar cotangent Laplacian. Our vector Dirichlet energy discretization can be used in a variety of applications, such as the calculation of Killing fields, parallel transport of vectors, and smooth vector field design. Experiments suggest convergence and suitability for applications similar to other discretizations of the vector Dirichlet energy.
  • Item
    Interactive Sculpting of Digital Faces Using an Anatomical Modeling Paradigm
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Gruber, Aurel; Fratarcangeli, Marco; Zoss, Gaspard; Cattaneo, Roman; Beeler, Thabo; Gross, Markus; Bradley, Derek; Jacobson, Alec and Huang, Qixing
    Digitally sculpting 3D human faces is a very challenging task. It typically requires either 1) highly-skilled artists using complex software packages for high quality results, or 2) highly-constrained simple interfaces for consumer-level avatar creation, such as in game engines. We propose a novel interactive method for the creation of digital faces that is simple and intuitive to use, even for novice users, while consistently producing plausible 3D face geometry, and allowing editing freedom beyond traditional video game avatar creation. At the core of our system lies a specialized anatomical local face model (ALM), which is constructed from a dataset of several hundred 3D face scans. User edits are propagated to constraints for an optimization of our data-driven ALM model, ensuring the resulting face remains plausible even for simple edits like clicking and dragging surface points. We show how several natural interaction methods can be implemented in our framework, including direct control of the surface, indirect control of semantic features like age, ethnicity, gender, and BMI, as well as indirect control through manipulating the underlying bony structures. The result is a simple new method for creating digital human faces, for artists and novice users alike. Our method is attractive for low-budget VFX and animation productions, and our anatomical modeling paradigm can complement traditional game engine avatar design packages.
  • Item
    A Parametric Analysis of Discrete Hamiltonian Functional Maps
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Postolache, Emilian; Fumero, Marco; Cosmo, Luca; Rodolà, Emanuele; Jacobson, Alec and Huang, Qixing
    In this paper we develop an in-depth theoretical investigation of the discrete Hamiltonian eigenbasis, which remains quite unexplored in the geometry processing community. This choice is supported by the fact that Dirichlet eigenfunctions can be equivalently computed by defining a Hamiltonian operator, whose potential energy and localization region can be controlled with ease. We vary with continuity the potential energy and study the relationship between the Dirichlet Laplacian and the Hamiltonian eigenbases with the functional map formalism. We develop a global analysis to capture the asymptotic behavior of the eigenpairs. We then focus on their local interactions, namely the veering patterns that arise between proximal eigenvalues. Armed with this knowledge, we are able to track the eigenfunctions in all possible configurations, shedding light on the nature of the functional maps. We exploit the Hamiltonian-Dirichlet connection in a partial shape matching problem, obtaining state of the art results, and provide directions where our theoretical findings could be applied in future research.
  • Item
    Nonlinear Deformation Synthesis via Sparse Principal Geodesic Analysis
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Sassen, Josua; Hildebrandt, Klaus; Rumpf, Martin; Jacobson, Alec and Huang, Qixing
    This paper introduces the construction of a low-dimensional nonlinear space capturing the variability of a non-rigid shape from a data set of example poses. The core of the approach is a Sparse Principal Geodesic Analysis (SPGA) on the Riemannian manifold of discrete shells, in which a pose of a non-rigid shape is a point. The SPGA is invariant to rigid body motions of the poses and supports large deformation. Since the Riemannian metric measures the membrane and bending distortions of the shells, the sparsity term forces the modes to describe largely decoupled and localized deformations. This property facilitates the analysis of articulated shapes. The modes often represent characteristic articulations of the shape and usually come with a decomposing of the spanned subspace into low-dimensional widely decoupled subspaces. For example, for human models, one expects distinct, localized modes for the bending of elbow or knee whereas some more modes are required to represent shoulder articulation. The decoupling property can be used to construct useful starting points for the computation of the nonlinear deformations via a superposition of shape submanifolds resulting from the decoupling. In a preprocessing stage, samples of the individual subspaces are computed, and, in an online phase, these are interpolated multilinearly. This accelerates the construction of nonlinear deformations and makes the method applicable for interactive applications. The method is compared to alternative approaches and the benefits are demonstrated on different kinds of input data.
  • Item
    Hexahedral Mesh Repair via Sum-of-Squares Relaxation
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Marschner, Zoë; Palmer, David; Zhang, Paul; Solomon, Justin; Jacobson, Alec and Huang, Qixing
    The validity of trilinear hexahedral (hex) mesh elements is a prerequisite for many applications of hex meshes, such as finite element analysis. A commonly used check for hex mesh validity evaluates mesh quality on the corners of the parameter domain of each hex, an insufficient condition that neglects invalidity elsewhere in the element, but is straightforward to compute. Hex mesh quality optimizations using this validity criterion suffer by being unable to detect invalidities in a hex mesh reliably, let alone fix them. We rectify these challenges by leveraging sum-of-squares relaxations to pinpoint invalidities in a hex mesh efficiently and robustly. Furthermore, we design a hex mesh repair algorithm that can certify validity of the entire hex mesh. We demonstrate our hex mesh repair algorithm on a dataset of meshes that include hexes with both corner and face-interior invalidities and demonstrate that where naïve algorithms would fail to even detect invalidities, we are able to repair them. Our novel methodology also introduces the general machinery of sum-of-squares relaxation to geometry processing, where it has the potential to solve related problems.
  • Item
    Integer-Grid Sketch Simplification and Vectorization
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Stanko, Tibor; Bessmeltsev, Mikhail; Bommes, David; Bousseau, Adrien; Jacobson, Alec and Huang, Qixing
    A major challenge in line drawing vectorization is segmenting the input bitmap into separate curves. This segmentation is especially problematic for rough sketches, where curves are depicted using multiple overdrawn strokes. Inspired by featurealigned mesh quadrangulation methods in geometry processing, we propose to extract vector curve networks by parametrizing the image with local drawing-aligned integer grids. The regular structure of the grid facilitates the extraction of clean line junctions; due to the grid's discrete nature, nearby strokes are implicitly grouped together. We demonstrate that our method successfully vectorizes both clean and rough line drawings, whereas previous methods focused on only one of those drawing types.
  • Item
    Cost Minimizing Local Anisotropic Quad Mesh Refinement
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Lyon, Max; Bommes, David; Kobbelt, Leif; Jacobson, Alec and Huang, Qixing
    Quad meshes as a surface representation have many conceptual advantages over triangle meshes. Their edges can naturally be aligned to principal curvatures of the underlying surface and they have the flexibility to create strongly anisotropic cells without causing excessively small inner angles. While in recent years a lot of progress has been made towards generating high quality uniform quad meshes for arbitrary shapes, their adaptive and anisotropic refinement remains difficult since a single edge split might propagate across the entire surface in order to maintain consistency. In this paper we present a novel refinement technique which finds the optimal trade-off between number of resulting elements and inserted singularities according to a user prescribed weighting. Our algorithm takes as input a quad mesh with those edges tagged that are prescribed to be refined. It then formulates a binary optimization problem that minimizes the number of additional edges which need to be split in order to maintain consistency. Valence 3 and 5 singularities have to be introduced in the transition region between refined and unrefined regions of the mesh. The optimization hence computes the optimal trade-off and places singularities strategically in order to minimize the number of consistency splits —- or avoids singularities where this causes only a small number of additional splits. When applying the refinement scheme iteratively, we extend our binary optimization formulation such that previous splits can be undone if this prevents degenerate cells with small inner angles that otherwise might occur in anisotropic regions or in the vicinity of singularities. We demonstrate on a number of challenging examples that the algorithm performs well in practice.
  • Item
    Poisson Surface Reconstruction with Envelope Constraints
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Kazhdan, Misha; Chuang, Ming; Rusinkiewicz, Szymon; Hoppe, Hugues; Jacobson, Alec and Huang, Qixing
    Reconstructing surfaces from scanned 3D points has been an important research area for several decades. One common approach that has proven efficient and robust to noise is implicit surface reconstruction, i.e. fitting to the points a 3D scalar function (such as an indicator function or signed-distance field) and then extracting an isosurface. Though many techniques fall within this category, existing methods either impose no boundary constraints or impose Dirichlet/Neumann conditions on the surface of a bounding box containing the scanned data. In this work, we demonstrate the benefit of supporting Dirichlet constraints on a general boundary. To this end, we adapt the Screened Poisson Reconstruction algorithm to input a constraint envelope in addition to the oriented point cloud. We impose Dirichlet boundary conditions, forcing the reconstructed implicit function to be zero outside this constraint surface. Using a visual hull and/or depth hull derived from RGB-D scans to define the constraint envelope, we obtain substantially improved surface reconstructions in regions of missing data.
  • Item
    Learning Part Boundaries from 3D Point Clouds
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Loizou, Marios; Averkiou, Melinos; Kalogerakis, Evangelos; Jacobson, Alec and Huang, Qixing
    We present a method that detects boundaries of parts in 3D shapes represented as point clouds. Our method is based on a graph convolutional network architecture that outputs a probability for a point to lie in an area that separates two or more parts in a 3D shape. Our boundary detector is quite generic: it can be trained to localize boundaries of semantic parts or geometric primitives commonly used in 3D modeling. Our experiments demonstrate that our method can extract more accurate boundaries that are closer to ground-truth ones compared to alternatives. We also demonstrate an application of our network to fine-grained semantic shape segmentation, where we also show improvements in terms of part labeling performance.
  • Item
    Topology-Aware Surface Reconstruction for Point Clouds
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Brüel-Gabrielsson, Rickard; Ganapathi-Subramanian, Vignesh; Skraba, Primoz; Guibas, Leonidas J.; Jacobson, Alec and Huang, Qixing
    We present an approach to incorporate topological priors in the reconstruction of a surface from a point scan. We base the reconstruction on basis functions which are optimized to provide a good fit to the point scan while satisfying predefined topological constraints. We optimize the parameters of a model to obtain a likelihood function over the reconstruction domain. The topological constraints are captured by persistence diagrams which are incorporated within the optimization algorithm to promote the correct topology. The result is a novel topology-aware technique which can (i) weed out topological noise from point scans, and (ii) capture certain nuanced properties of the underlying shape which could otherwise be lost while performing surface reconstruction. We show results reconstructing shapes with multiple potential topologies, compare to other classical surface construction techniques, and show the completion of real scan data.
  • Item
    EGGS: Sparsity-Specific Code Generation
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Tang, Xuan; Schneider, Teseo; Kamil, Shoaib; Panda, Aurojit; Li, Jinyang; Panozzo, Daniele; Jacobson, Alec and Huang, Qixing
    Sparse matrix computations are among the most important computational patterns, commonly used in geometry processing, physical simulation, graph algorithms, and other situations where sparse data arises. In many cases, the structure of a sparse matrix is known a priori, but the values may change or depend on inputs to the algorithm. We propose a new methodology for compile-time specialization of algorithms relying on mixing sparse and dense linear algebra operations, using an extension to the widely-used open source Eigen package. In contrast to library approaches optimizing individual building blocks of a computation (such as sparse matrix product), we generate reusable sparsity-specific implementations for a given algorithm, utilizing vector intrinsics and reducing unnecessary scanning through matrix structures. We demonstrate the effectiveness of our technique on a benchmark of artificial expressions to quantitatively evaluate the benefit of our approach over the state-ofthe- art library Intel MKL. To further demonstrate the practical applicability of our technique we show that our technique can improve performance, with minimal code changes, for mesh smoothing, mesh parametrization, volumetric deformation, optical flow, and computation of the Laplace operator.
  • Item
    Anderson Acceleration for Nonconvex ADMM Based on Douglas-Rachford Splitting
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Ouyang, Wenqing; Peng, Yue; Yao, Yuxin; Zhang, Juyong; Deng, Bailin; Jacobson, Alec and Huang, Qixing
    The alternating direction multiplier method (ADMM) is widely used in computer graphics for solving optimization problems that can be nonsmooth and nonconvex. It converges quickly to an approximate solution, but can take a long time to converge to a solution of high-accuracy. Previously, Anderson acceleration has been applied to ADMM, by treating it as a fixed-point iteration for the concatenation of the dual variables and a subset of the primal variables. In this paper, we note that the equivalence between ADMM and Douglas-Rachford splitting reveals that ADMM is in fact a fixed-point iteration in a lower-dimensional space. By applying Anderson acceleration to such lower-dimensional fixed-point iteration, we obtain a more effective approach for accelerating ADMM. We analyze the convergence of the proposed acceleration method on nonconvex problems, and verify its effectiveness on a variety of computer graphics including geometry processing and physical simulation.
  • Item
    DFR: Differentiable Function Rendering for Learning 3D Generation from Images
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Wu, Yunjie; Sun, Zhengxing; Jacobson, Alec and Huang, Qixing
    Learning-based 3D generation is a popular research field in computer graphics. Recently, some works adapted implicit function defined by a neural network to represent 3D objects and have become the current state-of-the-art. However, training the network requires precise ground truth 3D data and heavy pre-processing, which is unrealistic. To tackle this problem, we propose the DFR, a differentiable process for rendering implicit function representation of 3D objects into 2D images. Briefly, our method is to simulate the physical imaging process by casting multiple rays through the image plane to the function space, aggregating all information along with each ray, and performing a differentiable shading according to every ray's state. Some strategies are also proposed to optimize the rendering pipeline, making it efficient both in time and memory to support training a network. With DFR, we can perform many 3D modeling tasks with only 2D supervision. We conduct several experiments for various applications. The quantitative and qualitative evaluations both demonstrate the effectiveness of our method.
  • Item
    Generating Adversarial Surfaces via Band-Limited Perturbations
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Mariani, Giorgio; Cosmo, Luca; Bronstein, Alex M.; Rodolà, Emanuele; Jacobson, Alec and Huang, Qixing
    Adversarial attacks have demonstrated remarkable efficacy in altering the output of a learning model by applying a minimal perturbation to the input data. While increasing attention has been placed on the image domain, however, the study of adversarial perturbations for geometric data has been notably lagging behind. In this paper, we show that effective adversarial attacks can be concocted for surfaces embedded in 3D, under weak smoothness assumptions on the perceptibility of the attack. We address the case of deformable 3D shapes in particular, and introduce a general model that is not tailored to any specific surface representation, nor does it assume access to a parametric description of the 3D object. In this context, we consider targeted and untargeted variants of the attack, demonstrating compelling results in either case. We further show how discovering adversarial examples, and then using them for adversarial training, leads to an increase in both robustness and accuracy. Our findings are confirmed empirically over multiple datasets spanning different semantic classes and deformations.
  • Item
    Consistent ZoomOut: Efficient Spectral Map Synchronization
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Huang, Ruqi; Ren, Jing; Wonka, Peter; Ovsjanikov, Maks; Jacobson, Alec and Huang, Qixing
    In this paper, we propose a novel method, which we call CONSISTENT ZOOMOUT, for efficiently refining correspondences among deformable 3D shape collections, while promoting the resulting map consistency. Our formulation is closely related to a recent unidirectional spectral refinement framework, but naturally integrates map consistency constraints into the refinement. Beyond that, we show further that our formulation can be adapted to recover the underlying isometry among near-isometric shape collections with a theoretical guarantee, which is absent in the other spectral map synchronization frameworks. We demonstrate that our method improves the accuracy compared to the competing methods when synchronizing correspondences in both near-isometric and heterogeneous shape collections, but also significantly outperforms the baselines in terms of map consistency.