MSPA-MCS: Discrete Curvature Flows on Graphics and Visualization

该计划的重点是发展曲面上的离散曲率流的理论基础，利用这些流来研究曲面上的不同几何结构，并将其应用于几何建模，计算机图形学和可视化。形状分类与比较是计算机视觉和图形学中的基本问题。PI建议使用Teichmueller理论根据其共形结构对曲面进行分类。PI将开发实用算法，使用离散Ricci流计算Teichmueller空间坐标，并使用坐标索引大型几何数据库。与光滑曲面相比，离散曲面有一个额外的结构：组合结构。组合结构在离散几何中起着至关重要的作用。更好地理解组合结构所起的作用是一个基本问题。离散曲率流是研究这一问题的有力工具。PI计划基于离散变分原理开发相应的数学，以支持这些计算算法。数学研究是基于余弦定律，PI认为作为基本的度量曲率关系在离散设置。PI已经发现余弦定律的导数产生在所有常曲率空间中有效的惊人恒等式。这些身份产生的能量泛函，其中包括几乎所有已知的行动泛函在离散设置。这些新发现的变分原理在图形和可视化方面有着广泛的应用前景。这些算法可以通过几何结构系统地推广到弯曲空间。这为流形上的几何算法设计开辟了一个新的领域，通过解决平面上最简单的特殊情况，然后直接将解决方案推广到任意曲面。样条曲线在几何造型中起着最基本的作用。在飞机、汽车和许多其他工业中，几乎所有的设计都是通过计算机使用样条来辅助的。机械零件的形状具有高度复杂的拓扑和几何特征。不幸的是，当前样条线只能在平面上定义。如何在一般曲面上精确定义样条曲线一直是一个悬而未决的问题。PI计划通过引入新的算法来解决这个问题，以通过离散曲率流来构造脊和计算几何结构。曲面参数化是一种强大的技术，可以将3D曲面映射到平面上，并将3D几何问题转换为2D。在纹理映射中，为了增强视觉效果，将具有细微细节的图像粘贴到粗糙的多边形表面上。参数化的核心问题是控制变形，PI建议建立变形和曲率之间的关系，并寻求一种实用的方法来找到最佳的参数化。在当今的互联网上，存在着海量的几何信息。建立一个几何谷歌是几何学家和计算机科学家最迫切和最基本的问题。研究所计划采用建议书所发展的方法，建立这种几何搜索引擎。

This proposal focuses on developing theoretical foundations of discrete curvature flows on surfaces, studying different geometric structures on surfaces using the flows, and applying them to geometric modeling, computer graphics and visualization. Shape classification and comparison are fundamental problems in computer vision and graphics. The PIs propose to classify surfaces according to their conformal structure using Teichmueller theory. The PIs will develop practical algorithms to compute Teichmueller space coordinates using discrete Ricci flow and use the coordinates to index large scale geometric database. In contrast to smooth surfaces, discrete surfaces have an extra structure: combinatorial structure. Combinatorial structure plays crucial roles in discrete geometries. It is a fundamental problem to get better understanding of the roles played by combinatorial structures. Discrete curvature flow is a powerful tool to study this problem. The PIs plan to develop the corresponding mathematics based on discrete variational principle to support these computational algorithms. The mathematical study is based on the cosine law which the PI consider as the basic metric-curvature relation in the discrete setting. The PI have discovered that derivatives of the cosine law produce striking identities valid in all constant curvature spaces. These identities produce energy functionals which include almost all known action functionals in the discrete setting. The potential applications of these newly discovered variational principles in graphs and visualization seem to be abundant.Conventional computational geometry algorithms are mainly defined in flat spaces. These algorithms can be systematically generalized to curved spaces via geometric structures. This opens a new territory for geometric algorithmic design on manifolds by solving the easiest special case in the plane then directly generalizing the solution to arbitrary surfaces. Splines play the most fundamental role in geometric modeling. In aircraft, automobile and many other industries, almost all designs are aided by computer using splines. The shapes of mechanical parts have highly complicated topological and geometric features. Unfortunately, current splines can only be defined on the plane. It has been a long lasting open problem to find rigorous ways to define splines on general surfaces. The PIs plan to solve the problem by introducing novel algorithms to construct spines and calculate geometric structures via discrete curvature flow. Surface parameterization is a powerful technique to map surfaces in 3D onto the plane and convert 3D geometric problems to 2D. In texture mapping, in order to enhance the visual effects, images with subtle details are pasted onto the coarse polygonal surfaces. The central issue for parameterization is to control the distortion, the PIs propose to build the relation between distortion and the curvature and to seek a practical way to find the optimal parameterization. In today's Internet, there are huge amounts of geometric information. Building a geometry Google is the most urgent and fundamental problem for geometers and computer scientists. The PIs plan to build such geometric search engine using the methods developed in the proposal.