Displacement Interpolation Using Lagrangian Mass Transport

ACM Transactions on Graphics (Proceedings of SIGGRAPH ASIA 2011, to appear)
Nicolas Bonneel, Michiel van de Panne, Sylvain Paris, Wolfgang Heidrich

PDF (14.2 Mb)
Supplemental material PDF (154 Kb)
Divx demo - 54 Mb

bibtex Bibtex

Scroll down for the C++ code!.


(a) BRDF A (anisotropic angle = 0°) (b) BRDF B (anisotropic angle = 45°) (c) naive linear interpolation
(unrealistic double highlight)
(d) ground truth
(single highlight at 22.5°)
(e) our interpolation
Examples of interpolation between two anisotropic sampled BRDFs (a,b). Naive linear interpolation generates an unrealistic double highlight (c). Since
we used a parametric BRDF model, we can compute the ground-truth in-between BRDF by interpolating the parameters~(d). Our approach has no knowledge of the parametric BRDF representation but is nonetheless able to produce a similar output (e).


Interpolation between pairs of values, typically vectors, is a fundamental operation in many computer graphics applications. In some cases simple linear interpolation yields meaningful results without requiring domain knowledge. However, interpolation between pairs of distributions or pairs of functions often demands more care because features may exhibit translational motion between exemplars. This property is not captured by linear interpolation. This paper develops the use of displacement interpolation for this class of problem, which provides a generic method for interpolating between distributions or functions based on advection instead of blending. The functions can be non-uniformly sampled, high-dimensional, and defined on non-Euclidean manifolds, e.g., spheres and tori. Our method decomposes distributions or functions into sums of radial basis functions (RBFs). We solve a mass transport problem to pair the RBFs and apply partial transport to obtain the interpolated function. We describe practical methods for computing the RBF decomposition and solving the transport problem. We demonstrate the interpolation approach on synthetic examples, BRDFs,
color distributions, environment maps, stipple patterns, and value

Source code:
The source code only consists in an "Interpolator" class in a single header file. However, it requires 2 dependencies : LEMON (a graph library) and nnls.c (non negative least square) provided here.
- Ready to compile with an example and a Visual Studio 2008 solution, and a script for GG++/GCC.
- just the "Interpolator" class , nnls.c, nnls.h, the LEMON library, two required files that are speeding up LEMON : network_simplex_simple.h and full_bipartitegraph.h and an illustrating toy example (2D square to disk morphing).
- Check the Copyright.txt and Install.txt

You can find the precompiled LEMON :
- For Visual Studio 2008, x86, Release here
- For Visual Studio 2010, x64, Release here
The code should be compliant with Visual Studio Express (multi-threading using Windows API rather than OpenMP), and should work fine on Linux (although multi-threading will be deactivated).

The code has been tested and runs properly on Visual Studio 2008, 2010, and now compiles and runs properly with G++/GCC as well.



[DEPRECATED] University of British Columbia, Technical Report TR-2011-02

Technical Report : pdf - 15.6 Mb