Thursday, December 14, 2017

RBF Node: Interpolate all the things


Ever since I saw RBF I wanted to at least be able to understand it. I actually invested quite a lot of time into this and sort of had this on the backlog for a while to write about. This node is basically interpolating between a range of values, based on a range of other values.

A python dictionary is actually quite a good way to explain the core concept. There are keys and values, for instance lets say our keys are numbers from 1 to 5, and our values are 11-15.




keys
1
2
3
4
5
values 11 12 13 14 15

Notice how they match in length. Now how can we interpolate the keys based on the values? For example whats the the value 13 interpolated on the keys? Quite easy as its literally just sliding upwards to the keys and seeing the number 3. This could work for any range, all we have to do is remap the values right? So if keys are 0-1 and values are 100-200 then it should look like this:

keys
0.0
0.25
0.5
0.75
1.0
values 100 125 150 175 200

To find the interpolated key value of 0.375 on our values we just remap this and we should get 137.5.  What we have done here mathematically is we checked the distance between each of the keys and remapped that to the values. That is a super simplified example based on 1D input data. The distance data is what really drives everything here and this can be applied to any dataset, as long as we have a valid distance function.



For 1D data the "distance" is basically one negated by the other but how about we want interpolate
3d positions based on 3d rotations? As example we have 3 rotations and 3 positions. 

rotations
90.0, 0.0, 0.0
0.0, 90.00.0
0.0, 0.0, 90.0
positions -1.0, 0.0, 1.0 1.0, 0.0-1.0 1.0, 0.0, 1.0

How can we find the interpolated rotation of the position [ -0.5, 0.0, 0.5
If we try and calculate it with just standard arithmetic and as the input data gets increasingly complex you will see that there are in fact multiple solutions possible, there isn't just a single one. We do want to have a single solution though, the best possible interpolation between any number of elements. What if we have 500 rotations and 500 positions? 

To find a single solution we now build matrices of the distances between all of our keys and build a  linear equation to solve this against our values. Since we have 3 values in each, we will create a 3x3 matrix which will have the euclidean distance from each position to all the other positions.

The distance between two points in 3D is done by taking the sum of point 1 - point 2 squared and taking the square root. In python this may look like so:



For our given positions this is what the distance matrix looks like. Note how the values diagonally from top left to bottom right are all 0. This is because these represent the distances to themselves.

0.0 2.8 2.0
2.8 0.0 2.0
2.0 2.0 0.0

We will then build another 3x3 matrix of the rotations and solve the linear equation Ax=B where A is the matrix of position distances and B is the matrix of rotations. We are looking to find x here which is basically the weight of A elements contributing to form B and our ultimate solution.

There are many python packages to solve linear equations out there and to be completely honest I haven't fully understood the math behind it, it is actually quite complicated but if you want to read up more about it then you can find plenty of information online about solving linear equations using LU Decomposition.

In my case I used the mpmath library which also comes with its own matrix class and lu decomposition solve and a couple of other useful functions.



Now we end up with the following calculation where we have to find x

0.0 2.8 2.0
2.8 0.0 2.0
2.0 2.0 0.0
⋅ X =
90.0 0.0 0.0
0.0 90.0 0.0
0.0 0.0 90.0

Solving this equation will give us back a "weight matrix"

x =
-32.1 0.0 45.0
32.1 0.0 0.0
45.0 45.0 -63.0

All we have to do now is to get the distances from our interpolation probe point to all input positions and multiply them with their according weight.

So for our interpolation point p at [ -0.5, 0.0, 0.5 ] the distances to all input positions will return us

[ 54.578, 32.604, 90.15 ]

Now we simply iterate through this distance list and multiply it by its total weight. For instance the first item would be multiplied with the sum of the first column of the weight matrix and so on. We are then left with, our ultimate solution

40.22, 30.58, -30.65


You can also solve those linear equations online here. The distance matrix A can also be filtered through a basis function before we solve the equation and there are plenty of functions to choose from, eg. "linear", "gaussian" or "multiquadric" just to get some interesting interpolation effects for different datatypes.

I made a quick video to demonstrate this node, written in Python. Towards the end of the video you can see the clavicle joint rotation driving some blend shapes. Hope you enjoy!


1 comment:

  1. Hi, I used the website "Linear Equations Solver" to solve the equation in this post, but I get the value of X is [-16.071 16.071 22.500
    16.071 -16.071 22.500
    22.500 22.500 -31.500]. Did I miss somehing?

    ReplyDelete