The differential geometry theory of surfaces asserts that given the first fundamental form (Riemannian metric) and the second fundamental form of a surface, the embedding of the surface in a three-dimensional Euclidean space is determined (differing by a rigid body transformation). For closed convex surfaces, the Riemannian metric can determine the shape of the surface. However, there has been no mature algorithm for how to calculate the shape of a convex surface from the Riemannian metric. To this end, we arranged an assignment to implement an algorithm for reconstructing convex surfaces from Gaussian curvature.
Figure 1. Convex surface reconstruction from Gaussian curvature.
Minkowski problem
From this, we can calculate the corresponding Riemannian metric for a given Gaussian curvature. However, the Riemannian metric is given abstractly here, and there is no specific embedded information of the surface in the three-dimensional space. If we want to further obtain the embedding of the surface, we need to solve the Minkowski problem. The Minkowski problem is formulated as follows: given a convex region, its boundary is a convex surface, and its polar coordinates are expressed as,
That is, any point on the surface is expressed as the product of the polar radius vector and the polar radius length. The Gaussian curvature function is a positive function defined on the sphere, and the Gaussian curvature at a point is. In short, the Minkowski problem is to find back from the given. We define normal mapping. For any point on the convex surface,
Gauss Mapping is defined as, Gauss mapping induces Gauss measure on the sphere. For any Borel set,
Here H is the Hausdorff measure. Minkowski problem: Given the Borel measure on the unit sphere, find the convex region such that . Minkowski proved the existence and uniqueness of understanding.
Spherical optimal transmission
Figure 2: Generalized Legendre transformation.
Examining a support plane of a convex surface, the normal vector is and the height is, then the height satisfies the equation:
On the contrary, a convex surface can be regarded as the inner envelope of all its supporting planes,
We define, , the transmission cost function as
From this, we define the generalized Legendre transform (c-transform),
Then we have, and. Then the Minkowski problem can be transformed into an optimal transmission problem: given the Hausdorff measure and Gaussian measure of the sphere, find a transmission mapping from the sphere to itself, map the Hausdorff measure to the Gaussian measure, and at the same time minimize the transmission cost among all measure-preserving mappings,
Here the transfer map is given by the Gaussian map of the convex surface. By Kantorovich theory, this is equivalent to optimizing the following functional:
From the optimal transmission theory, we can get the existence and uniqueness of the solution.
Discrete sphere optimal transmission mapping
Figure 3. Discrete optimal transmission mapping.
In the discrete case, we are given a set of discrete points on the unit sphere, and the radial length to be found is recorded as, the convex surface is the convex hull
It can be proved that the plane dual to each vertex is,
The Legendre dual of a convex surface is the envelope of the supporting plane,
The normal mapping of the convex hull induces a cell decomposition of the sphere, which is equivalent to the projection of the Legendre dual to the center of the sphere,
|
|
|
Figure 5: Hessian matrix of optimal transmission mapping energy on a sphere.
The core of the algorithm is to optimize the following convex energy,
The energy gradient is
The Hessian matrix of energy is
The diagonal elements of the Hessian matrix are:
We can use Newton's method for optimization, but during the optimization process we should always pay attention that each optimization step is performed in the admissible solution space.
Algorithm design
Discrete convex surfaces are represented by triangular meshes, stored as half-edge data structures, and are also used to represent Legendre dual surfaces. The convex hull algorithm can use the traditional incremental algorithm (incremental convex hull) or the Lawson Edge Flip algorithm. In practice, the incremental algorithm is relatively stable, but the calculation is time-consuming, while the edge conversion algorithm is more time-saving, but the numerical stability is inferior.
Figure 6. Input triangle mesh, Planck head.
The input is a triangular mesh and a closed surface with zero genus. The data format is a common three-dimensional data format, such as obj, mesh files.
Figure 7. Image of spherical harmonic mapping.
We first use spherical harmonic mapping to map the triangular mesh onto the unit sphere, and then the image of each vertex under the harmonic mapping is used as a spherical sampling point, and the area sum of the adjacent faces of each vertex is used as the target measure corresponding to this sampling point.
Figure 8. Spherical cell cavity decomposition.
The Delaunay triangulation and cell decomposition of the sphere are represented by the same triangular mesh, and the vertices, edges, and faces of the triangulation are even to the faces, edges, and vertices of the cell decomposition.
Figure 9. Solution to Minkowski problem, convex surface determined by curvature.
The optimization is implemented using Newton's method. In order to ensure that the intermediate optimization processes are carried out in the admissible space, we use the damping method. In each cycle of the optimization process, if a certain cell of the spherical cavity decomposition disappears after the polar radius is updated, we will halve the step size and recalculate the polar radius. This cycle continues until the cell decomposition induced by the temporary solution satisfies the condition that each cavity is non-empty.
Figure 10. Legendre dual surface.
The convex hull surface we obtain in this way is the solution to the Minkowski problem, and the discrete Gaussian curvature of the vertices is equal to the given target measure. The calculation results include both the Minkowski convex surface and the Legendre dual surface. This pair of surfaces are dual to each other and determine each other.
Figure 11. Cerebral cortex surface. Figure 12. Spherical harmonic mapping of the cerebral cortex surface. Figure 13. Geodesic cell cavity decomposition on a sphere. Figure 14. Solution to the Minkowski problem. Figure 15. Legendre dual surface of the Minkowski convex surface.
Software usage and download
After unzipping the demo program, double-click the bat file to automatically demonstrate. The source code of the program can be generated with CMake and then compiled with a compiler such as Visual Studio. We also provide test data in a common obj file format.
The theoretical basis of the algorithm comes from the theory of the Monge-Ampère equation by Mr. Qiu Chengtong and Professor Zheng Shaoyuan. The geometric variation principle we proposed [4] also referred to Professor Wang Xujia's spherical optimal transmission theory [5], and proposed a spherical optimal transmission mapping algorithm based on geometric variation [3]. We received suggestions and help from Dr. Sihang, Professor Wang Xujia, Professor Luo Feng, Professor Cui Li, and Professor Su Kehua, and Professor Lei Na provided specific guidance. The main members of the development team include Qi Xin, Chen Wei, Antonsheng An, Guo Yang, Zhao Tong, Wen Chengfeng, Zhang Min, Zeng Wei and other doctors and postdoctoral fellows.
In the future, we will further announce and develop more general computing tools, such as optimal transmission mapping for high-dimensional and general density functions, and we also welcome more students to join the development team. I hope everyone will find loopholes in the algorithm and propose ways to improve it. In-depth academic discussions, valuable suggestions and criticisms are more welcome!
【1】https://www3.cs.stonybrook.edu/~gu/software/SOT/index.html
【2】Na Lei, Dongsheng An, Yang Guo, Kehua Su, Shixia Liu, Zhongxuan Luo, Shing-Tung Yau and Xianfeng Gu, "Geometric Understanding of Deep Learning", Journal of Engineering, 2020.
【3】Li Cui, Xin Qi, Chengfeng Wen, Na Lei, Xinyuan Li, Min Zhang and Xianfeng Gu, Spherical Optimal Transportation", Computer-Aided Design (CAD), Volume 119, Pages 181-193, 2019.
【4】Xianfeng Gu, Feng Luo, Jian Sun and Shing-Tung Yau, "Variational Principles for Minkowski Type Problems, Discrete Optimal Transport, and Discrete Monge-Ampere Equations", AJM 20(2), 383-398, 2016.
【5】Xu-Jia Wang, "On the design of a reflector antenna II", Calc Var Partial Differential Equations, 20(3), pp. 329-341, 2004.
Machine-translated from the Chinese original 球面最优传输映射的C++实现 (published 2021-01-12). WeChat original ↗