MSPA-MCS: Discrete Curvature Flows on Graphics and Visualization

本课题重点发展曲面上离散曲率流的理论基础，利用离散曲率流研究曲面上不同的几何结构，并将其应用于几何建模、计算机图形学和可视化。形状分类与比较是计算机视觉与图形学中的基本问题。pi建议使用Teichmueller理论根据它们的共形结构对表面进行分类。pi将开发实用的算法来计算使用离散Ricci流的Teichmueller空间坐标，并使用坐标来索引大型几何数据库。与光滑表面相比，离散表面有一个额外的结构：组合结构。组合结构在离散几何中起着至关重要的作用。如何更好地理解组合结构所扮演的角色是一个基本问题。离散曲率流是研究这一问题的有力工具。pi计划开发基于离散变分原理的相应数学来支持这些计算算法。数学研究基于余弦定律，PI将余弦定律视为离散情况下的基本度规曲率关系。PI已经发现余弦定律的导数产生了在所有常曲率空间中都有效的惊人恒等式。这些恒等式产生的能量泛函几乎包括了离散环境中所有已知的作用泛函。这些新发现的变分原理在图形和可视化中的潜在应用似乎是丰富的。传统的计算几何算法主要在平面空间中定义。这些算法可以通过几何结构系统地推广到弯曲空间。通过求解平面上最简单的特殊情况，然后将其直接推广到任意曲面，为流形的几何算法设计开辟了一个新的领域。样条曲线在几何建模中起着最基本的作用。在飞机、汽车和许多其他工业中，几乎所有的设计都是由使用样条的计算机辅助的。机械零件的形状具有高度复杂的拓扑和几何特征。不幸的是，当前的样条只能在平面上定义。寻找在一般曲面上定义样条的严格方法一直是一个悬而未决的问题。pi计划通过引入新的算法来构造棘和通过离散曲率流计算几何结构来解决这个问题。曲面参数化是一种将三维曲面映射到平面上并将三维几何问题转换为二维几何问题的强大技术。在纹理映射中，为了增强视觉效果，将带有细微细节的图像粘贴到粗糙的多边形表面上。参数化的核心问题是控制畸变，pi提出建立畸变与曲率之间的关系，并寻求一种实用的方法来找到最优的参数化。在今天的互联网上，有大量的几何信息。对于几何学家和计算机科学家来说，建立一个几何模型是最紧迫和最基本的问题。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.