Transport_program

How to program your own semi-discrete optimal transport at home

Prerequisites

Before starting, if you do not have it already, you will need to install the Graphite software (and its WarpDrive plugin, that is included in the distribution):

• if you are under Windows, install pre-compiled package (instructions here)
• if you are under Linux or MacOS, install Graphite from sources ([instructions here)[https://github.com/BrunoLevy/GraphiteThree/wiki#installing])

Programming with Graphite

In this tutorial, we will use the LUA programming language. LUA is a scripting language similar to Python, if you know Python already you will (nearly) find yourself at home. More information about LUA here.

Why LUA rather than Python ?

• LUA is smaller/faster/more elegantly designed (in my own opinion). It is directly included in Graphite (nothing to install).
• If you really prefer Python (that is much more popular than LUA and that has many existing packages), there will be a Python version of this tutorial soon (Graphite also supports Python through the "gompy" plugin).

Now you can take a quick look at the Scripting Graphite tutorial to see how the editor works (see in particular automatic completion and help bubbles that can save you some time).

Step 1: Laguerre diagram

We shall now see how to create a Laguerre diagram in Graphite and how to visualize it.

Create a square

The first thing we need to do is defining the domain. We create a unit square, using the create_square() method of the Shapes interface. Then we need to triangulate the domain (this will simply split the square into two triangles in our case).

scene_graph.clear()
Omega = scene_graph.create_object('OGF::MeshGrob')
Omega.rename('Omega')
Omega.I.Shapes.create_square()
Omega.I.Surface.triangulate()
Omega.visible = false

Sample it with random points

Now we create a point set. In this example, we will use a set of N=100 points picked randomly in our unit square:

N = 100 -- Number of points
Omega.I.Points.sample_surface(
   {nb_points=N,Lloyd_iter=0,Newton_iter=0}
)
points = scene_graph.objects.points

Compute Laguerre diagram

And finally, we can compute the Laguerre diagram (restricted to the domain). We first create a new mesh to store it. Laguerre diagrams are defined from a pointset and a vector of "weights". Here we use (for now) a vector of weights with all weights set to 0 (default value set by NL.create_vector()).

RVD = scene_graph.create_object('OGF::MeshGrob','RVD')
weight   = NL.create_vector(N)

Then we can compute the Laguerre diagram. The WarpDrive plugin adds a special Transport interface solely designed for scripting (it does not appear in the menus). It has a function to compute the Laguerre diagram:

points.I.Transport.compute_Laguerre_diagram(
   Omega, weight, RVD, 'EULER_2D'
)

Display the cells in different colors

And finally, we can set the graphic attributes of the computed Laguerre diagram to display the cells in different colors:

RVD.shader.painting='ATTRIBUTE'
RVD.shader.attribute='facets.chart'
RVD.shader.colormap = 'plasma;false;732;false;false;;'
RVD.shader.autorange() 

The complete program is available here. You can also load it from the Examples... menu of the text editor (Examples.../WarpDrive/advanced/Transport_2d_01.lua).

Change the weight of a cell in a Laguerre diagram

Let us now see what happens when we change the weight of one cell in the Laguerre diagram. For that, we write a function compute(), at the beginning of our file as follows:

function compute()
   weight[0] = weight[0] + 0.01
   OT.compute_Laguerre_diagram(Omega, weight, RVD, 'EULER_2D')   
   RVD.shader.autorange()
   RVD.update()
end

Now we want to create a button that will call our function compute() each time we push it. At the end of our file, we add:

OT_dialog = {} 
OT_dialog.visible = true
OT_dialog.name = 'Transport' 
OT_dialog.x = 100
OT_dialog.y = 400
OT_dialog.w = 150
OT_dialog.h = 200
OT_dialog.width = 400

function OT_dialog.draw_window()
   if imgui.Button('Compute',-1,-1) then
      compute()
   end
end

graphite_main_window.add_module(OT_dialog)

This declares a new Module to the graphic user interface of Graphite. See the Scripting Graphite tutorial for more details. Each time the Compute button is pressed, our function compute() is called. It increases a bit the weight of one of the points and recomputes the Laguerre diagram, so that you can see the impact of modifying the weight of a single point.

The complete program is available here. You can also load it from the Examples... menu of the text editor (Examples.../WarpDrive/advanced/Transport_2d_02.lua).

Translating a Laguerre diagram by just changing the weight

Now you may think about a Laguerre diagram as a Voronoi diagram plus tuning buttons (the weights). By changing the tuning buttons, one may increase or decrease the size of the associated Laguerre cells. In fact there is more: did you know that you can translate a Laguerre diagram by an arbitrary vector just by changing the weights ?

The Laguerre cell associated with a point is defined by: ![f1]

[f1]: http://chart.apis.google.com/chart?cht=tx&chl=Lag_i = { {\bf x} | | {\bf x} - {\bf x}_i |^2 - w_i < | {\bf x} - {\bf x}_j |^2 - w_j \forall j \neq i }