Volumetric Map Quantization for Structured Mesh Generation

点击翻译按钮获取中文摘要

When three-dimensional objects are to be represented for computational purposes in computer graphics, engineering, design, etc., a very common choice is representation by a mesh – a mesh of 2D polygonal facets if representation of the surface is sufficient, a mesh of 3D polyhedral cells in case the entire space (here also called volume) enclosed by the surface is to be represented, or discretized, explicitly, as often required, e.g., for precise physical simulations. In a variety of scenarios there is a profound preference for so-called semi-structured variants of such meshes, consisting of quadrilateral or hexahedral (cubical) elements forming a structurally regular grid almost everywhere.Parametrization-based methods are a flexible approach to automatically or interactively generate such semi-structured meshes. They are based on finding a map of the object into the regular Euclidean grid, such that the inverse map induces a semi-structured mesh for the object. They have in recent years proven to enable yielding high-quality results – in the surface case. First results of the endeavor to generalize to the hexahedral volume mesh case have been reported, yet one key component is missing entirely: a reliable method to quantize the underlying map. Certain points of the object need to be mapped specifically onto grid nodes or edges; quantization refers to the process of deciding, for each point, which node or edge. This decision is crucial: it not only directly limits the quality that can be achieved, it even determines whether any consistent mesh will be obtainable at all. The principal investigator has provided reliable solutions to this quantization question for the surface case. The core goal of this project is to find and evaluate a similar solution for the important volume mesh case. Major challenges are to be overcome, as many of the foundational techniques are not dimension-independent, thus do not generalize to the volume case. Concretely, four coupled problems have been identified, which shall be investigated in this project. Their solutions will combine to a reliable quantization method for volume meshes. They will furthermore be of value individually in a number of areas besides mesh generation.The challenges that will be addressed to provide solutions to these four problems are as follows. 1) 3D generalization of the so-called motorcycle graph, to establish structured preliminary partitions of an object. 2) Optimization operators for this type of partition. 3) Combinatorial methods to find generalized cycles in the volumetric partition graph, such that valid quantizations can be expressed as linear combinations thereof. 4) A constrained volume mapping technique to construct the desired map in accordance with the determined valid quantization.In essence, this project will thereby provide the missing piece to enable the map-based approach to, as in the surface case, make an impact in the field of structured volume mesh generation.