Volumetric Map Quantization for Structured Mesh Generation

在计算机图形学、工程、设计等领域中，为了计算目的而要表示三维物体时，一种非常常见的选择是通过网格表示——如果表面的表示足够，则使用二维多边形面的网格，如果表面包围的整个空间（这里也称为体积）要表示或离散化，则使用三维多面体单元的网格，如经常需要，例如，用于精确的物理模拟。在各种情况下，人们更倾向于这种网格的所谓半结构化变体，由四边形或六面体（立方体）元素组成，几乎在任何地方形成结构规则的网格。基于参数化的方法是一种灵活的方法，可以自动或交互地生成这种半结构化网格。它们是基于在规则欧几里得网格中找到对象的映射，这样逆映射就会为对象诱导出半结构化网格。近年来，它们已被证明能够产生高质量的结果-在表面情况下。第一个推广到六面体体网格情况的结果已经被报道，但是一个关键的组成部分完全缺失：一个可靠的方法来量化底层映射。物体的某些点需要映射到网格节点或边缘上；量化是指确定每个点的节点或边的过程。这个决定是至关重要的：它不仅直接限制了可以实现的质量，它甚至决定了是否可以获得任何一致的网格。对于表面情况的量化问题，主要研究者提供了可靠的解决方案。该项目的核心目标是为重要的体网格情况找到并评估类似的解决方案。主要的挑战有待克服，因为许多基础技术不是与维度无关的，因此不能推广到体积情况。具体来说，已经确定了四个耦合问题，这是本项目需要研究的。他们的解决方案将结合成一种可靠的体积网格量化方法。除了网格生成之外，它们在许多领域都有各自的价值。为解决这四个问题所面临的挑战如下。1)所谓的摩托车图的三维泛化，建立一个对象的结构化初步分区。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.