Collaborative RUI: Quadrilateral Surface Meshes with Provable Quality Guarantees

复杂三维物体的表示和重建在当今计算的广泛应用中至关重要。在计算机图形学和几何处理应用中，多边形网格已经成为表示具有高度复杂几何形状和任意亏格的曲面的工业标准。虽然三角形网格是最流行的曲面网格表示类型，但四边形网格比三角形网格更适合于若干应用，如角色动画，纹理映射，基于样条的曲面建模，网格压缩和一些特定的有限元分析应用。从参数函数、隐函数或点云给出的曲面生成三角形网格的算法已被证明是有效的。然而，算法来生成四边形网格与可证明的质量保证，这样的表面并不普遍，部分原因是从一个给定的表面生成一个四边形网格的问题本质上是比它的三角形对应更难。该项目的目标是开发各种表面表示的四边形网格的算法，并通过常用的度量（如角度边界或纵横比）和网格质量（通过网格大小或各向异性测量）对元素质量进行可证明的保证。将使用直接和间接方法（从三角形网格生成四边形网格）以及参数化引导方法。计算几何和图论的技术将在算法的设计和开发中发挥核心作用。自动生成可证明良好的四边形网格的表面是一个基本的问题，这是感兴趣的理论，因为它提出了几个几何，组合和图论的问题，以及实践中，从设计一个模型的表面的模拟或动画的最终阶段的计算流水线经常占主导地位的网格化过程。对这些问题的正式理解不仅对于自动网格生成的理论基础至关重要，而且对于在广泛的应用中利用网格的良好实践也至关重要。作为三所本科院校PI之间的合作努力，本科生参与研究项目是这个项目的一个组成部分。该项目的一个重要和特殊的目标是通过为所有三个机构的学生之间的合作和联合研究项目提供机会，为女性和少数民族本科计算机科学专业创建一个更大的同龄人群体。通过早期和积极参与该项目的本科生，PI还寻求创建一个管道的女性和少数民族学生在计算机科学研究生院的方向。

The representation and reconstruction of complex three-dimensional objects is critical in a wide range of applications in computing today. Polygonal meshes have become the industry standard for the representation of surfaces with highly complex geometry and arbitrary genus in computer graphics and geometry processing applications. While triangle meshes are the most popular type of mesh representation for surfaces, quadrilateral meshes are better suited than triangle meshes in several applications such as character animation, texture mapping, spline-based surface modeling, mesh compression, and some specific finite element analysis applications. Provably good algorithms for generating triangle meshes from surfaces given by parametric or implicit functions or as point point clouds are widely available. However, algorithms to generate quadrilateral meshes with provable quality guarantees for such surfaces are not as prevalent, in part because the problem of generating a quadrilateral mesh from a given surface is intrinsically harder than its triangular counterpart. The goal of this project is to develop algorithms for quadrilateral meshes for various surface representations with provable guarantees on element quality as measured by commonly used metrics such as angle bounds or aspect ratio, and mesh quality as measured by mesh size or anisotropy. Direct and indirect methods (which generate a quad mesh from a triangle mesh), as well as parameterization guided methods will be utilized. Techniques from computational geometry and graph theory will play a central role in the design and development of algorithms. The automated generation of provably good quadrilateral meshes for surfaces is a fundamental problem that is of interest both in theory, as it raises several geometric, combinatorial, and graph-theoretic questions, as well as practice, where the computational pipeline from designing a model for the surface to the end stage of simulation or animation is frequently dominated by the meshing process. A formal understanding of these questions is critical not only for the theoretical underpinnings of automated mesh generation, but also for the sound practice of utilizing the meshes in a wide range of applications. As a collaborative effort between PIs at three undergraduate institutions, involvement of undergraduate students in research projects is an integral part of this project. An important and particular goal for this project is the creation of a larger peer group for female and minority undergraduate Computer Science majors by providing opportunities for collaboration and joint research projects between students across all three institutions. Through early and active involvement of undergraduates in the project, the PIs also seek to create a pipeline of female and minority students bound for graduate school in Computer Science.