Optimal Transport for Interactive Interpolation Problems in Computer Graphics

Abstract

Modern computer graphics require realistic surface materials and geometries for generating convincing imagery. Both types of data are inherently complex for most applications. To obtain them, measurement of real-world samples is a widespread method. A frequently required editing operation in computer graphics is the creation of intermediate states of measured assets. In the case of complex assets such as highly-detailed surface materials or complicated geometries, this is a difficult task. <br /> For the purpose of interpolating this type of data, the theory of optimal transport is applied in this thesis. In general, this theory deals with the optimal allocation of resources. Mathematically speaking, it aims to warp one probability measure onto another at minimum cost. The common theme and overarching question of this thesis is how measured input data can be processed and represented in such a way that an optimal transport problem can be set up and how its solution can provide a meaningful result. This allows achieving results of a visual quality that was impossible to obtain before. <br /> Overall the proposed approach consists of the following key steps. The first step is to represent the input data as probability measures. Then, a cost measure that suits the needs of the problem at hand has to be chosen. The next step is to set up the optimal transport problem in a computationally manageable way and to solve it. The final step comprises interpreting the problem's solution in a way that is useful for our purpose, for instance, to produce meaningful, visually appealing results. <br /> The proposed approach is applied here in two areas of computer graphics for which satisfactory solutions have not yet been found. This thesis first focuses on representing the sparkling effect of metallic car paints as measured bidirectional texture functions (BTFs). It explains how to represent these in a novel, memory-efficient statistical way that is also suitable for real-time rendering. Having obtained this statistical representation, it is described how to set up and solve an optimal transport problem between two such representations. The interpolation of the metallic paint BTFs is then performed using the solution of the optimal transport problem in real-time, allowing for an interactive application. <br /> Following this, the temporal upsampling of time series of 3D point clouds obtained from 3D scans of plants is addressed. The first step of the developed solution is to represent the point clouds as hierarchies of point cloud clusters that correspond to the natural segments of the plant. Then, a matching of the hierarchically organized clusters using the optimal transport-based Wasserstein distance is to be found. A solution to the optimal transport problem between all matched pairs of clusters is computed. The information gained through the optimal transport solution is then used to generate an arbitrary number of intermediate states between two consecutive scans of a time series, which allows us to generate a temporal upsampling of the whole sequence, resulting in smooth animations for temporally sparse 3D scans. <br /> In summary, the methods proposed in this thesis solve the problem of generating interpolations of measured data that were previously hard or impossible to generate. The methods provide realistic interpolations, using optimal transport theory as a basis, underlining its usefulness in computer graphics applications. The findings can be used for artistic applications in the field of rendering as well as for scientific applications in the field of plant growth visualization.