Collaborative RUI: Quadrilateral Surface Meshes with Provable Quality Guarantees

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

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.