Browsing by Author "Bommes, David"

Now showing 1 - 7 of 7
  • Thumbnail Image
    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.
  • Thumbnail Image
    Item
    Geodesic Distance Computation via Virtual Source Propagation
    (The Eurographics Association and John Wiley & Sons Ltd., 2021) Trettner, Philip; Bommes, David; Kobbelt, Leif; Digne, Julie and Crane, Keenan
    We present a highly practical, efficient, and versatile approach for computing approximate geodesic distances. The method is designed to operate on triangle meshes and a set of point sources on the surface. We also show extensions for all kinds of geometric input including inconsistent triangle soups and point clouds, as well as other source types, such as lines. The algorithm is based on the propagation of virtual sources and hence easy to implement. We extensively evaluate our method on about 10000 meshes taken from the Thingi10k and the Tet Meshing in theWild data sets. Our approach clearly outperforms previous approximate methods in terms of runtime efficiency and accuracy. Through careful implementation and cache optimization, we achieve runtimes comparable to other elementary mesh operations (e.g. smoothing, curvature estimation) such that geodesic distances become a ''first-class citizen'' in the toolbox of geometric operations. Our method can be parallelized and we observe up to 6x speed-up on the CPU and 20x on the GPU. We present a number of mesh processing tasks easily implemented on the basis of fast geodesic distances. The source code of our method is provided as a C++ library under the MIT license.
  • 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
    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.
  • Thumbnail Image
    Item
    Symposium on Geometry Processing 2019 - CGF38-5: Frontmatter
    (The Eurographics Association and John Wiley & Sons Ltd., 2019) Bommes, David; Huang, Hui; Bommes, David and Huang, Hui
  • Thumbnail Image
    Item
    Symposium on Geometry Processing 2019 – Posters: Frontmatter
    (Eurographics Association, 2019) Bommes, David; Huang, Hui; Bommes, David and Huang, Hui
  • 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.