MSPA-MCS: Discrete Curvature Flows on Graphics and Visualization

点击翻译按钮获取中文摘要

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.