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.