Volumetric Map Quantization for Structured Mesh Generation

• Applicant: Professor Dr. Marcel Campen
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2019 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 427469366

• Final Report Year: 2023

Final Report Abstract

Performing calculations on digital three-dimensional objects and in particular the simulation of their physical behavior often requires the representation of the objects as so-called meshes, consisting of small, simple building blocks. Of particular interest are hexahedral meshes, consisting of cube-shaped elements. The automatic generation of high quality hexahedral meshes proves difficult and constitutes a long-standing challenge. In particular, many mesh generation algorithms show weaknesses in terms of their reliability, due to, among other things, the complexity of three-dimensional geometry and topology. In this project, algorithmic methods and data structures were developed and investigated, which in combination systematically close one of two major reliability gaps in the modern hexahedral mesh generation strategy based on parameterization. Specifically, it revolves around the problem of quantization – essentially the question of how many hexahedra should come to lie in which spatial area of an object. Since these values are and must be discrete integers, this decision eludes the numerical optimization methods that are typically used to determine the hexahedra’s non-discrete properties like shape and orientation. Based on a newly developed method for the algorithmic virtual decomposition of the object into specially structured parts (the so-called ”motorcycle complex”), a mathematical problem could be formulated in such a way that these discrete decisions can be made algorithmically efficiently in such a way that a valid hexahedral mesh without holes or overlaps is implied. Together with other project results, such as eliminating numerical inaccuracies from the parameterization basis or reducing complex global bijection computation problems to simpler local problems, this not only increases reliability, but also offers greater flexibility in controlling the resulting meshes’ properties. This brings us a step further on the way to efficient automated processing and analysis, especially of large amounts of spatial data.

Publications

• Quad Layouts via Constrained T‐Mesh Quantization. Computer Graphics Forum, 40(2), 305-314.
  Lyon, M.; Campen, M. & Kobbelt, L.
  
• Simpler Quad Layouts using Relaxed Singularities. Computer Graphics Forum, 40(5), 169-180.
  Lyon, M.; Campen, M. & Kobbelt, L.
  
• Hex-Mesh Generation and Processing: A Survey. ACM Transactions on Graphics, 42(2), 1-44.
  Pietroni, Nico; Campen, Marcel; Sheffer, Alla; Cherchi, Gianmarco; Bommes, David; Gao, Xifeng; Scateni, Riccardo; Ledoux, Franck; Remacle, Jean & Livesu, Marco
  
• The 3D Motorcycle Complex for Structured Volume Decomposition. Computer Graphics Forum, 41(2), 221-235.
  Brückler, Hendrik; Gupta, Ojaswi; Mandad, Manish & Campen, Marcel
  
• Volume parametrization quantization for hexahedral meshing. ACM Transactions on Graphics, 41(4), 1-19.
  Brückler, Hendrik; Bommes, David & Campen, Marcel