Volumetric Map Quantization for Structured Mesh Generation

当为了计算机图形学、工程、设计等中的计算目的而表示三维对象时，非常常见的选择是通过网格来表示--如果表面的表示是充分的，则是2D多边形面的网格，如果要显式地表示或离散由表面包围的整个空间(这里也称为体积)，则由3D多面体单元组成的网格，例如对于精确的物理模拟通常需要。在各种情况下，人们都倾向于这种网格的所谓半结构变体，这种网格由四边形或六面体(立方体)单元组成，几乎处处形成结构规则的网格。基于参数化的方法是一种灵活的方法，可以自动或交互地生成这种半结构网格。它们的基础是在规则欧几里德网格中找到对象的映射，从而逆映射为对象引入半结构化网格。近年来，它们已被证明能够产生高质量的结果--从表面上看。推广到六面体网格情况的努力的第一个结果已经报道，然而完全缺少一个关键组件：量化底层地图的可靠方法。对象的某些点需要具体地映射到网格节点或边上；量化是指为每个点确定哪个节点或边的过程。这一决定至关重要：它不仅直接限制了可以实现的质量，甚至还决定了是否可以获得任何一致的网格。首席调查员为表面情况下的这个量化问题提供了可靠的解决方案。这个项目的核心目标是为重要的体积网格情况寻找和评估类似的解决方案。需要克服重大挑战，因为许多基本技术不是独立于维度的，因此不能推广到卷的情况。具体地说，已经确定了四个耦合问题，将在本项目中进行研究。他们的解决方案将结合成一种可靠的体网格量化方法。此外，它们还将在网格生成之外的许多领域具有单独的价值。为解决这四个问题而需要解决的挑战如下。1)所谓摩托车图的3D概括，以建立对象的结构化初步划分。2)这类分区的优化算子。3)在体积分割图中寻找广义圈的组合方法，使得有效量化可以表示为它们的线性组合。4)一种约束体映射技术，根据确定的有效量化来构建期望的映射。本质上，该项目将由此提供缺失的部分，从而使得基于映射的方法能够像在表面情况下一样，在结构化的体网格生成领域产生影响。

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.