39-Issue 5

Permanent URI for this collection

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

Browse

Now showing 1 - 20 of 22

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.
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.
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.
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.
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.
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.
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.
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.
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.

Browse

Browsing 39-Issue 5 by Title

Results Per Page

Sort Options