41-Issue 5
Permanent URI for this collection
Browse
Browsing 41-Issue 5 by Title
Now showing 1 - 15 of 15
Results Per Page
Sort Options
Item Constructing L∞ Voronoi Diagrams in 2D and 3D(The Eurographics Association and John Wiley & Sons Ltd., 2022) Bukenberger, Dennis R.; Buchin, Kevin; Botsch, Mario; Campen, Marcel; Spagnuolo, MichelaVoronoi diagrams and their computation are well known in the Euclidean L2 space. They are easy to sample and render in generalized Lp spaces but nontrivial to construct geometrically. Especially the limit of this norm with p -> ∞ lends itself to many quad- and hex-meshing related applications as the level-set in this space is a hypercube. Many application scenarios circumvent the actual computation of L∞ diagrams altogether as known concepts for these diagrams are limited to 2D, uniformly weighted and axis-aligned sites. Our novel algorithm allows for the construction of generalized L∞ Voronoi diagrams. Although parts of the developed concept theoretically extend to higher dimensions it is herein presented and evaluated for the 2D and 3D case. It further supports individually oriented sites and allows for generating weighted diagrams with anisotropic weight vectors for individual sites. The algorithm is designed around individual sites, and initializes their cells with a simple meshed representation of a site's level-set. Hyperplanes between adjacent cells cut the initialization geometry into convex polyhedra. Non-cell geometry is filtered out based on the L∞ Voronoi criterion, leaving only the non-convex cell geometry. Eventually we conclude with discussions on the algorithms complexity, numerical precision and analyze the applicability of our generalized L∞ diagrams for the construction of Centroidal Voronoi Tessellations (CVT) using Lloyd's algorithm.Item Deterministic Linear Time for Maximal Poisson-Disk Sampling using Chocks without Rejection or Approximation(The Eurographics Association and John Wiley & Sons Ltd., 2022) Mitchell, Scott A.; Campen, Marcel; Spagnuolo, MichelaWe show how to sample uniformly within the three-sided region bounded by a circle, a radial ray, and a tangent, called a ''chock.'' By dividing a 2D planar rectangle into a background grid, and subtracting Poisson disks from grid squares, we are able to represent the available region for samples exactly using triangles and chocks. Uniform random samples are generated from chock areas precisely without rejection sampling. This provides the first implemented algorithm for precise maximal Poisson-disk sampling in deterministic linear time. We prove O(n.M(b) log b); where n is the number of samples, b is the bits of numerical precision and M is the cost of multiplication. Prior methods have higher time complexity, take expected time, are non-maximal, and/or are not Poisson-disk distributions in the most precise mathematical sense. We fill this theoretical lacuna.Item Fabricable Multi-Scale Wang Tiles(The Eurographics Association and John Wiley & Sons Ltd., 2022) Liu, Xiaokang; Li, Chenran; Lu, Lin; Deussen, Oliver; Tu, Changhe; Campen, Marcel; Spagnuolo, MichelaWang tiles, also known as Wang dominoes, are a jigsaw puzzle system with matching edges. Due to their compactness and expressiveness in representing variations, they have become a popular tool in the procedural synthesis of textures, height fields, 3D printing and representing other large and non-repetitive data. Multi-scale tiles created from low-level tiles allow for a higher tiling efficiency, although they face the problem of combinatorial explosion. In this paper, we propose a generation method for multi-scale Wang tiles that aims at minimizing the amount of needed tiles while still resembling a tiling appearance similar to low-level tiles. Based on a set of representative multi-scale Wang tiles, we use a dynamic generation algorithm for this purpose. Our method can be used for rapid texture synthesis and image halftoning. Respecting physical constraints, our tiles are connected, lightweight, independent of the fabrication scale, able to tile larger areas with image contents and contribute to "mass customization".Item Harmonic Shape Interpolation on Multiply-connected Planar Domains(The Eurographics Association and John Wiley & Sons Ltd., 2022) Shi, Dongbo; Chen, Renjie; Campen, Marcel; Spagnuolo, MichelaShape interpolation is a fundamental problem in computer graphics. Recently, there have been some interpolation methods developed which guarantee that the results are of bounded amount of geometric distortion, hence ensure high quality interpolation. However, none of these methods is applicable to shapes within the multiply-connected domains. In this work, we develop an interpolation scheme for harmonic mappings, that specifically addresses this limitation. We opt to interpolate the pullback metric of the input harmonic maps as proposed by Chen et al. [CWKBC13]. However, the interpolated metric does not correspond to any planar mapping, which is the main challenge in the interpolation problem for multiply-connected domains. We propose to solve this by projecting the interpolated metric into the planar harmonic mapping space. Specifically, we develop a Newton iteration to minimize the isometric distortion of the intermediate mapping, with respect to the interpolated metric. For more efficient Newton iteration, we further derived a simple analytic formula for the positive semidefinite (PSD) projection of the Hessian matrix of our distortion energy. Through extensive experiments and comparisons with the state-of-the-art, we demonstrate the efficacy and robustness of our method for various inputs.Item Hex Me If You Can(The Eurographics Association and John Wiley & Sons Ltd., 2022) Beaufort, Pierre-Alexandre; Reberol, Maxence; Kalmykov, Denis; Liu, Heng; Ledoux, Franck; Bommes, David; Campen, Marcel; Spagnuolo, MichelaHexMe consists of 189 tetrahedral meshes with tagged features and a workflow to generate them. The primary purpose of HexMe meshes is to enable consistent and practically meaningful evaluation of hexahedral meshing algorithms and related techniques, specifically regarding the correct meshing of specified feature points, curves, and surfaces. The tetrahedral meshes have been generated with Gmsh, starting from 63 computer-aided design (CAD) models from various databases. To highlight and label the diverse and challenging aspects of hexahedral mesh generation, the CAD models are classified into three categories: simple, nasty, and industrial. For each CAD model, we provide three kinds of tetrahedral meshes (uniform, curvature-adapted, and box-embedded). The mesh generation pipeline is defined with the help of Snakemake, a modern workflow management system, which allows us to specify a fully automated, extensible, and sustainable workflow. It is possible to download the whole dataset or select individual meshes by browsing the online catalog. The HexMe dataset is built with evolution in mind and prepared for future developments. A public GitHub repository hosts the HexMe workflow, where external contributions and future releases are possible and encouraged. We demonstrate the value of HexMe by exploring the robustness limitations of state-of-the-art frame-field-based hexahedral meshing algorithm. Only for 19 of 189 tagged tetrahedral inputs all feature entities are meshed correctly, while the average success rates are 70.9% / 48.5% / 34.6% for feature points/curves/surfaces.Item Localized Shape Modelling with Global Coherence: An Inverse Spectral Approach(The Eurographics Association and John Wiley & Sons Ltd., 2022) Pegoraro, Marco; Melzi, Simone; Castellani, Umberto; Marin, Riccardo; Rodolà , Emanuele; Campen, Marcel; Spagnuolo, MichelaMany natural shapes have most of their characterizing features concentrated over a few regions in space. For example, humans and animals have distinctive head shapes, while inorganic objects like chairs and airplanes are made of well-localized functional parts with specific geometric features. Often, these features are strongly correlated - a modification of facial traits in a quadruped should induce changes to the body structure. However, in shape modelling applications, these types of edits are among the hardest ones; they require high precision, but also a global awareness of the entire shape. Even in the deep learning era, obtaining manipulable representations that satisfy such requirements is an open problem posing significant constraints. In this work, we address this problem by defining a data-driven model upon a family of linear operators (variants of the mesh Laplacian), whose spectra capture global and local geometric properties of the shape at hand. Modifications to these spectra are translated to semantically valid deformations of the corresponding surface. By explicitly decoupling the global from the local surface features, our pipeline allows to perform local edits while simultaneously maintaining a global stylistic coherence. We empirically demonstrate how our learning-based model generalizes to shape representations not seen at training time, and we systematically analyze different choices of local operators over diverse shape categories.Item MendNet: Restoration of Fractured Shapes Using Learned Occupancy Functions(The Eurographics Association and John Wiley & Sons Ltd., 2022) Lamb, Nikolas; Banerjee, Sean; Banerjee, Natasha K.; Campen, Marcel; Spagnuolo, MichelaWe provide a novel approach to perform fully automated generation of restorations for fractured shapes using learned implicit shape representations in the form of occupancy functions. Our approach lays the groundwork to perform automated object repair via additive manufacturing. Existing approaches for restoration of fractured shapes either require prior knowledge of object structure such as symmetries between the restoration and the fractured object, or predict restorations as voxel outputs that are impractical for repair at current resolutions. By leveraging learned occupancy functions for restoration prediction, our approach overcomes the curse of dimensionality with voxel approaches, while providing plausible restorations. Given a fractured shape, we fit a function to occupancy samples from the shape to infer a latent code. We apply a learned transformation to the fractured shape code to predict a corresponding code for restoration generation. To ensure physical validity and well-constrained shape estimation, we contribute a loss that models feasible occupancy values for fractured shapes, restorations, and complete shapes obtained by joining fractured and restoration shapes. Our work overcomes deficiencies of shape completion approaches adapted for repair, and enables consumer-driven object repair and cultural heritage object restoration. We share our code and a synthetic dataset of fractured meshes from 8 ShapeNet classes at: https://github.com/Terascale-All-sensing-Research-Studio/MendNet.Item Precise High-order Meshing of 2D Domains with Rational Bézier Curves(The Eurographics Association and John Wiley & Sons Ltd., 2022) Yang, Jinlin; Liu, Shibo; Chai, Shuangming; Liu, Ligang; Fu, Xiao-Ming; Campen, Marcel; Spagnuolo, MichelaWe propose a novel method to generate a high-order triangular mesh for an input 2D domain with two key characteristics: (1) the mesh precisely conforms to a set of input piecewise rational domain curves, and (2) the geometric map on each curved triangle is injective. Central to the algorithm is a new sufficient condition for placing control points of a rational Bézier triangle to guarantee that the conformance and injectivity constraints are theoretically satisfied. Taking advantage of this condition, we provide an explicit construct that robustly creates higher-order 2D meshes satisfying the two characteristics. We demonstrate the robustness and effectiveness of our algorithm over a data set containing 2200 examples.Item PriFit: Learning to Fit Primitives Improves Few Shot Point Cloud Segmentation(The Eurographics Association and John Wiley & Sons Ltd., 2022) Sharma, Gopal; Dash, Bidya; RoyChowdhury, Aruni; Gadelha, Matheus; Loizou, Marios; Cao, Liangliang; Wang, Rui; Learned-Miller, Erik G.; Maji, Subhransu; Kalogerakis, Evangelos; Campen, Marcel; Spagnuolo, MichelaWe present PRIFIT, a semi-supervised approach for label-efficient learning of 3D point cloud segmentation networks. PRIFIT combines geometric primitive fitting with point-based representation learning. Its key idea is to learn point representations whose clustering reveals shape regions that can be approximated well by basic geometric primitives, such as cuboids and ellipsoids. The learned point representations can then be re-used in existing network architectures for 3D point cloud segmentation, and improves their performance in the few-shot setting. According to our experiments on the widely used ShapeNet and PartNet benchmarks, PRIFIT outperforms several state-of-the-art methods in this setting, suggesting that decomposability into primitives is a useful prior for learning representations predictive of semantic parts. We present a number of ablative experiments varying the choice of geometric primitives and downstream tasks to demonstrate the effectiveness of the method.Item Rational Bézier Guarding(The Eurographics Association and John Wiley & Sons Ltd., 2022) Khanteimouri, Payam; Mandad, Manish; Campen, Marcel; Campen, Marcel; Spagnuolo, MichelaWe present a reliable method to generate planar meshes of nonlinear rational triangular elements. The elements are guaranteed to be valid, i.e. defined by injective rational functions. The mesh is guaranteed to conform exactly, without geometric error, to arbitrary rational domain boundary and feature curves. The method generalizes the recent Bézier Guarding technique, which is applicable only to polynomial curves and elements. This generalization enables the accurate handling of practically important cases involving, for instance, circular or elliptic arcs and NURBS curves, which cannot be matched by polynomial elements. Furthermore, although many practical scenarios are concerned with rational functions of quadratic and cubic degree only, our method is fully general and supports arbitrary degree. We demonstrate the method on a variety of test cases.Item SDF-StyleGAN: Implicit SDF-Based StyleGAN for 3D Shape Generation(The Eurographics Association and John Wiley & Sons Ltd., 2022) Zheng, Xinyang; Liu, Yang; Wang, Pengshuai; Tong, Xin; Campen, Marcel; Spagnuolo, MichelaWe present a StyleGAN2-based deep learning approach for 3D shape generation, called SDF-StyleGAN, with the aim of reducing visual and geometric dissimilarity between generated shapes and a shape collection. We extend StyleGAN2 to 3D generation and utilize the implicit signed distance function (SDF) as the 3D shape representation, and introduce two novel global and local shape discriminators that distinguish real and fake SDF values and gradients to significantly improve shape geometry and visual quality. We further complement the evaluation metrics of 3D generative models with the shading-image-based Fréchet inception distance (FID) scores to better assess visual quality and shape distribution of the generated shapes. Experiments on shape generation demonstrate the superior performance of SDF-StyleGAN over the state-of-the-art. We further demonstrate the efficacy of SDFStyleGAN in various tasks based on GAN inversion, including shape reconstruction, shape completion from partial point clouds, single-view image-based shape generation, and shape style editing. Extensive ablation studies justify the efficacy of our framework design. Our code and trained models are available at https://github.com/Zhengxinyang/SDF-StyleGAN.Item SGP 2022 CGF 41-5: Frontmatter(The Eurographics Association and John Wiley & Sons Ltd., 2022) Campen, Marcel; Spagnuolo, Michela; Campen, Marcel; Spagnuolo, MichelaItem Smooth Interpolating Curves with Local Control and Monotone Alternating Curvature(The Eurographics Association and John Wiley & Sons Ltd., 2022) Binninger, Alexandre; Sorkine-Hornung, Olga; Campen, Marcel; Spagnuolo, MichelaWe propose a method for the construction of a planar curve based on piecewise clothoids and straight lines that intuitively interpolates a given sequence of control points. Our method has several desirable properties that are not simultaneously fulfilled by previous approaches: Our interpolating curves are C2 continuous, their computation does not rely on global optimization and has local support, enabling fast evaluation for interactive modeling. Further, the sign of the curvature at control points is consistent with the control polygon; the curvature attains its extrema at control points and is monotone between consecutive control points of opposite curvature signs. In addition, we can ensure that the curve has self-intersections only when the control polygon also self-intersects between the same control points. For more fine-grained control, the user can specify the desired curvature and tangent values at certain control points, though it is not required by our method. Our local optimization can lead to discontinuity w.r.t. the locations of control points, although the problem is limited by its locality. We demonstrate the utility of our approach in generating various curves and provide a comparison with the state of the art.Item TinyAD: Automatic Differentiation in Geometry Processing Made Simple(The Eurographics Association and John Wiley & Sons Ltd., 2022) Schmidt, Patrick; Born, Janis; Bommes, David; Campen, Marcel; Kobbelt, Leif; Campen, Marcel; Spagnuolo, MichelaNon-linear optimization is essential to many areas of geometry processing research. However, when experimenting with different problem formulations or when prototyping new algorithms, a major practical obstacle is the need to figure out derivatives of objective functions, especially when second-order derivatives are required. Deriving and manually implementing gradients and Hessians is both time-consuming and error-prone. Automatic differentiation techniques address this problem, but can introduce a diverse set of obstacles themselves, e.g. limiting the set of supported language features, imposing restrictions on a program's control flow, incurring a significant run time overhead, or making it hard to exploit sparsity patterns common in geometry processing. We show that for many geometric problems, in particular on meshes, the simplest form of forward-mode automatic differentiation is not only the most flexible, but also actually the most efficient choice. We introduce TinyAD: a lightweight C++ library that automatically computes gradients and Hessians, in particular of sparse problems, by differentiating small (tiny) sub-problems. Its simplicity enables easy integration; no restrictions on, e.g., looping and branching are imposed. TinyAD provides the basic ingredients to quickly implement first and second order Newton-style solvers, allowing for flexible adjustment of both problem formulations and solver details. By showcasing compact implementations of methods from parametrization, deformation, and direction field design, we demonstrate how TinyAD lowers the barrier to exploring non-linear optimization techniques. This enables not only fast prototyping of new research ideas, but also improves replicability of existing algorithms in geometry processing. TinyAD is available to the community as an open source library.Item Topological Simplification of Nested Shapes(The Eurographics Association and John Wiley & Sons Ltd., 2022) Zeng, Dan; Chambers, Erin; Letscher, David; Ju, Tao; Campen, Marcel; Spagnuolo, MichelaWe present a method for removing unwanted topological features (e.g., islands, handles, cavities) from a sequence of shapes where each shape is nested in the next. Such sequences can be found in nature, such as a multi-layered material or a growing plant root. Existing topology simplification methods are designed for single shapes, and applying them independently to shapes in a sequence may lose the nesting property. We formulate the nesting-constrained simplification task as an optimal labelling problem on a set of candidate shape deletions (''cuts'') and additions (''fills''). We explored several optimization strategies, including a greedy heuristic that sequentially propagates labels, a state-space search algorithm that is provably optimal, and a beam-search variant with controllable complexity. Evaluation on synthetic and real-world data shows that our method is as effective as single-shape simplification methods in reducing topological complexity and minimizing geometric changes, and it additionally ensures nesting. Also, the beam-search strategy is found to strike the best balance between optimality and efficiency.