### Minkowski Problem

Given a closed convex surface, with origin inside, the surface is represented using polar coordinates. The Gaussian curvature of the surface is a positive function defined on the sphere. Minkowski asks the following problem: given the Gaussian curvature function, can one reconstruct the original convex surface? Minkowski proved the existence and the uniqueness (upto scaling) of the solution to the Minkowski problem. Minkowski problem can be solved using spherical optimal transportation theory, with the cost of logorithm of the cosine of geodesic distance between two points on the sphere. Spherical optimal mass transportation map transforms one spherical measure to the other in the most economic way. It has broad applications in deep learning, computer graphics, computer vision, medical imaging and geometric modeling. In 2013, We developed a variational theoretic framework for semi-discrete optimal mass transportation, which converts solving the optimal mass transportation problem to the optimization of a convex energy, furthermore it gives the explicit geometric interpretation to the convex energy, and the geometric interpretation to the Hessian matrix. This theoretic article can be found here . The method has been generalized to the spherical optimal transportation, the article can be found here.

### Spherical Optimal Transportation Map

A genus zero closed surfaces is conformally mapped on the unit sphere by a harmonic map, then the conformal factor (area distortion factor)is treated as a probability density function defined on the sphere. The spherical optimal transportation map from the uniform distribution to the conformal factor distribution is calculated using the spherical OT algorithm. In the top row, the left frame is the original 3D surface, the middle frame is the spherical harmonic mapping image, the right frame is the spherical optimal transportation map, each cell is mapped to a vertex, which is a spherical power diagram; In the bottom row, the left is the convex surface whose Gaussian curvature equals to the conformal factor function, the middle frame is the Legendre dual of the left, the right frame is the spherical weighted Delaunay triangulation dual to the spherical power diagram. The mapping from the top row left frame to the top row right frame gives an area-preserving spherical parameterization.

### Computational Process

Step One The input is a genus zero closed surface. It is conformally mapped onto the unit sphere by a spherical harmonic map. The images of vertices are the sample points on the sphere. The harmonic map pushes forward the surface area element to the sphere. We use the push-forwarded measure as the target measure. In practice, users and define the vertex target measure in different ways.
Step Two Compute the convex hull, or equivalently compute the spherical power Delaunay triangulation using Lawson's edge flip algorithm. If there is an edge, which is not local power Delaunay, but not flippable, then it means some samples are not on the convex hull, hence the algorithm exceeds the admissible space.
Step Three Compute the generalized Legendre dual of the convex hull.
Step Four Central project the Legendral dual surface onto the unit sphere to obtain the spherical power diagram. If some power cells are empty, then the algorithm exceeds the admissible space, then we reduce the step length by half. Compupte the power cell areas, which give the gradient of the energy. Compute the power Delaunay edge lengths and the power Vornoi edge lengths, which gives the Hessian matrix of the energy. Use Newton's method to compute the update direction for the vertex powers. Repeat step two through five, until the gradient is close to zero.

### Comannd Line

 OT.exe -source < source mesh > -target [option] the following options are supported: -source the source convex planar domain -target the target domain and the measure -step_length set the step length, ie 0.05 -help show the help message!

Examples: OT.exe -source brain.obj -target brain.sphere.obj

### Hot Keys

 OT.exe hot keys the following options are supported: '!' Use Newton's method to update one step 'd' show convex hull or upper envelope, Delaunay triangulation or Power Diagram 'g' show 3D shape view or spherical view 'l' show power cell boundaries 'c' show power cell centers 'e' show edges 'o' take a snapshot 'L' change light source position '?' Help information 'W' output the Legendre dual mesh and the optimal transportation map mesh

The viewer uses arcball interface, press the left mouse button and drag for rotation, press the right mouse button and drag for zoom in or out, press the middle mouse button and drag for translation.

• The C++ source code package for spherical optimal transportation map from a uniform distribution on the unit sphere to the summation of Dirac measures can be downloaded from here .
• The binary demo (Windows X64) can be downloaded from here . Double click on view_mesh.bat to view all the meshes, click on "OT_demo.bat" to see the computation of optimal transportation map.
• The testing data set can be downloaded from here . The source folder contains the source meshes, the target folder contains the target meshes.

### Environment and Dependencies

1. The OT mapper is developed using generic C++ language on Windows Visual Studio. It has been tested on Linux platforms as well.
2. It uses freeglut for 3D rendering and GUI.
3. It uses Eigen for numerical computation;
4. It uses Shewchuk's adaptive robust predicates package for computational geometry.
5. You can use cmake for compilation.

### References

• The theories behind the algorithm is proved by Gu-Luo-Sun-Yau in the article, "Variational Principles for Minkowski Type Problems, Discrete Optimal Transport, and Discrete Monge-Ampere Equations", published in AJM 20(2), 383-398. The article can be accessed here.
• The method has been generalized to spherical optimal transportation, "Spherical Optimal Transportation", Computer-Aided Design (CAD), Volume 119, Pages 181-193, 2019. The article can be accessed here.
• The geometric optimal transportaiton method has been applied for deep learning, such as the geometric GAN model, "Geometric Understanding of Deep Learning", Journal of Engineering, 2020. The article can be access here.