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.
buddaha
Alex
The mapping from the top row left frame to the top row right frame gives an area-preserving spherical parameterization.

Computational Process

input
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.
input
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.
input
Step Three Compute the generalized Legendre dual of the convex hull.
input
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 <taraget mesh> [option] the following options are supported:
-source <source mesh> the source convex planar domain
-target <target mesh> the target domain and the measure
-step_length <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.

Download and Instructions

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

For any further information, comments and criticisms, please contact David Gu.