41-Issue 5

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/2633204
Geometry Processing 2022 - Symposium Proceedings
Remote via Internet | July 04 – 06, 2022
Issue Information
Modeling and Mapping
Harmonic Shape Interpolation on Multiply-connected Planar Domains
[full paper Image] [meta data Image]
Dongbo Shi and Renjie Chen
Localized Shape Modelling with Global Coherence: An Inverse Spectral Approach
[full paper Image] [meta data Image]
Marco Pegoraro, Simone Melzi, Umberto Castellani, Riccardo Marin, and Emanuele Rodolà
Curves and Features
Smooth Interpolating Curves with Local Control and Monotone Alternating Curvature
[full paper Image] [meta data Image]
Alexandre Binninger and Olga Sorkine-Hornung
Learning and Creating
PriFit: Learning to Fit Primitives Improves Few Shot Point Cloud Segmentation
[full paper Image] [meta data Image]
Gopal Sharma, Bidya Dash, Aruni RoyChowdhury, Matheus Gadelha, Marios Loizou, Liangliang Cao, Rui Wang, Erik G. Learned-Miller, Subhransu Maji, and Evangelos Kalogerakis
SDF-StyleGAN: Implicit SDF-Based StyleGAN for 3D Shape Generation
[full paper Image] [meta data Image]
Xinyang Zheng, Yang Liu, Pengshuai Wang, and Xin Tong
MendNet: Restoration of Fractured Shapes Using Learned Occupancy Functions
[full paper Image] [meta data Image]
Nikolas Lamb, Sean Banerjee, and Natasha K. Banerjee
Meshes and Partitions
Precise High-order Meshing of 2D Domains with Rational Bézier Curves
[full paper Image] [meta data Image]
Jinlin Yang, Shibo Liu, Shuangming Chai, Ligang Liu, and Xiao-Ming Fu
Rational Bézier Guarding
[full paper Image] [meta data Image]
Payam Khanteimouri, Manish Mandad, and Marcel Campen
Tools and Data
Deterministic Linear Time for Maximal Poisson-Disk Sampling using Chocks without Rejection or Approximation
[full paper Image] [meta data Image]
Scott A. Mitchell
TinyAD: Automatic Differentiation in Geometry Processing Made Simple
[full paper Image] [meta data Image]
Patrick Schmidt, Janis Born, David Bommes, Marcel Campen, and Leif Kobbelt
Hex Me If You Can
[full paper Image] [meta data Image]
Pierre-Alexandre Beaufort, Maxence Reberol, Denis Kalmykov, Heng Liu, Franck Ledoux, and David Bommes
Tiling and Nesting
Constructing L∞ Voronoi Diagrams in 2D and 3D
[full paper Image] [meta data Image]
Dennis R. Bukenberger, Kevin Buchin, and Mario Botsch
Fabricable Multi-Scale Wang Tiles
[full paper Image] [meta data Image]
Xiaokang Liu, Chenran Li, Lin Lu, Oliver Deussen, and Changhe Tu
Topological Simplification of Nested Shapes
[full paper Image] [meta data Image]
Dan Zeng, Erin Chambers, David Letscher, and Tao Ju

BibTeX (41-Issue 5)
                
@article{
10.1111:cgf.14612,

journal = {Computer Graphics Forum},
title = {{
SGP 2022 CGF 41-5: Frontmatter}},

author = {
Campen, Marcel
 and 
Spagnuolo, Michela
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14612}

}
                
@article{
10.1111:cgf.14599,

journal = {Computer Graphics Forum},
title = {{
Localized Shape Modelling with Global Coherence: An Inverse Spectral Approach}},

author = {
Pegoraro, Marco
 and 
Melzi, Simone
 and 
Castellani, Umberto
 and 
Marin, Riccardo
 and 
Rodolà, Emanuele
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14599}

}
                
@article{
10.1111:cgf.14598,

journal = {Computer Graphics Forum},
title = {{
Harmonic Shape Interpolation on Multiply-connected Planar Domains}},

author = {
Shi, Dongbo
 and 
Chen, Renjie
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14598}

}
                
@article{
10.1111:cgf.14600,

journal = {Computer Graphics Forum},
title = {{
Smooth Interpolating Curves with Local Control and Monotone Alternating Curvature}},

author = {
Binninger, Alexandre
 and 
Sorkine-Hornung, Olga
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14600}

}
                
@article{
10.1111:cgf.14601,

journal = {Computer Graphics Forum},
title = {{
PriFit: Learning to Fit Primitives Improves Few Shot Point Cloud Segmentation}},

author = {
Sharma, Gopal
 and 
Dash, Bidya
 and 
RoyChowdhury, Aruni
 and 
Gadelha, Matheus
 and 
Loizou, Marios
 and 
Cao, Liangliang
 and 
Wang, Rui
 and 
Learned-Miller, Erik G.
 and 
Maji, Subhransu
 and 
Kalogerakis, Evangelos
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14601}

}
                
@article{
10.1111:cgf.14602,

journal = {Computer Graphics Forum},
title = {{
SDF-StyleGAN: Implicit SDF-Based StyleGAN for 3D Shape Generation}},

author = {
Zheng, Xinyang
 and 
Liu, Yang
 and 
Wang, Pengshuai
 and 
Tong, Xin
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14602}

}
                
@article{
10.1111:cgf.14603,

journal = {Computer Graphics Forum},
title = {{
MendNet: Restoration of Fractured Shapes Using Learned Occupancy Functions}},

author = {
Lamb, Nikolas
 and 
Banerjee, Sean
 and 
Banerjee, Natasha K.
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14603}

}
                
@article{
10.1111:cgf.14605,

journal = {Computer Graphics Forum},
title = {{
Rational Bézier Guarding}},

author = {
Khanteimouri, Payam
 and 
Mandad, Manish
 and 
Campen, Marcel
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14605}

}
                
@article{
10.1111:cgf.14607,

journal = {Computer Graphics Forum},
title = {{
TinyAD: Automatic Differentiation in Geometry Processing Made Simple}},

author = {
Schmidt, Patrick
 and 
Born, Janis
 and 
Bommes, David
 and 
Campen, Marcel
 and 
Kobbelt, Leif
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14607}

}
                
@article{
10.1111:cgf.14606,

journal = {Computer Graphics Forum},
title = {{
Deterministic Linear Time for Maximal Poisson-Disk Sampling using Chocks without Rejection or Approximation}},

author = {
Mitchell, Scott A.
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14606}

}
                
@article{
10.1111:cgf.14604,

journal = {Computer Graphics Forum},
title = {{
Precise High-order Meshing of 2D Domains with Rational Bézier Curves}},

author = {
Yang, Jinlin
 and 
Liu, Shibo
 and 
Chai, Shuangming
 and 
Liu, Ligang
 and 
Fu, Xiao-Ming
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14604}

}
                
@article{
10.1111:cgf.14608,

journal = {Computer Graphics Forum},
title = {{
Hex Me If You Can}},

author = {
Beaufort, Pierre-Alexandre
 and 
Reberol, Maxence
 and 
Kalmykov, Denis
 and 
Liu, Heng
 and 
Ledoux, Franck
 and 
Bommes, David
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14608}

}
                
@article{
10.1111:cgf.14609,

journal = {Computer Graphics Forum},
title = {{
Constructing L∞ Voronoi Diagrams in 2D and 3D}},

author = {
Bukenberger, Dennis R.
 and 
Buchin, Kevin
 and 
Botsch, Mario
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14609}

}
                
@article{
10.1111:cgf.14611,

journal = {Computer Graphics Forum},
title = {{
Topological Simplification of Nested Shapes}},

author = {
Zeng, Dan
 and 
Chambers, Erin
 and 
Letscher, David
 and 
Ju, Tao
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14611}

}
                
@article{
10.1111:cgf.14610,

journal = {Computer Graphics Forum},
title = {{
Fabricable Multi-Scale Wang Tiles}},

author = {
Liu, Xiaokang
 and 
Li, Chenran
 and 
Lu, Lin
 and 
Deussen, Oliver
 and 
Tu, Changhe
},
year = {
2022},

publisher = {
The Eurographics Association and John Wiley & Sons Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/cgf.14610}

}

Browse

Recent Submissions

Now showing 1 - 15 of 15
  • Thumbnail Image
    Item
    SGP 2022 CGF 41-5: Frontmatter
    (The Eurographics Association and John Wiley & Sons Ltd., 2022) Campen, Marcel; Spagnuolo, Michela; Campen, Marcel; Spagnuolo, Michela
  • Thumbnail Image
    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, Michela
    Many 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.
  • Thumbnail Image
    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, Michela
    Shape 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.
  • Thumbnail Image
    Item
    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, Michela
    We 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.
  • Thumbnail Image
    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, Michela
    We 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.
  • Thumbnail Image
    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, Michela
    We 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.
  • Thumbnail Image
    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, Michela
    We 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.
  • Thumbnail Image
    Item
    Rational Bézier Guarding
    (The Eurographics Association and John Wiley & Sons Ltd., 2022) Khanteimouri, Payam; Mandad, Manish; Campen, Marcel; Campen, Marcel; Spagnuolo, Michela
    We 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.
  • Thumbnail Image
    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, Michela
    Non-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.
  • Thumbnail Image
    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, Michela
    We 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.
  • Thumbnail Image
    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, Michela
    We 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.
  • Thumbnail Image
    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, Michela
    HexMe 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.
  • Thumbnail Image
    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, Michela
    Voronoi 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.
  • Thumbnail Image
    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, Michela
    We 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.
  • Thumbnail Image
    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, Michela
    Wang 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".