Hierarchical RBF

In computer graphics, hierarchical RBF is an interpolation method based on radial basis functions (RBFs).

Hierarchical RBF interpolation has applications in treatment of results from a 3D scanner, terrain reconstruction, and the construction of shape models in 3D computer graphics (such as the Stanford bunny, a popular 3D model).

This problem is informally named as "large scattered data point set interpolation."

The steps of the interpolation method (in three dimensions) are as follows: As J. C. Carr et al. showed,[1] this function takes the form

is a radial basis function and

are the coefficients that are the solution of the following linear system of equations:

φ (

{\displaystyle {\begin{bmatrix}\varphi (c_{1},c_{1})&\varphi (c_{1},c_{2})&...&\varphi (c_{1},c_{N})\\\varphi (c_{2},c_{1})&\varphi (c_{2},c_{2})&...&\varphi (c_{2},c_{N})\\...&...&...&...\\\varphi (c_{N},c_{1})&\varphi (c_{N},c_{2})&...&\varphi (c_{N},c_{N})\end{bmatrix}}*{\begin{bmatrix}\lambda _{1}\\\lambda _{2}\\...\\\lambda _{N}\end{bmatrix}}={\begin{bmatrix}h_{1}\\h_{2}\\...\\h_{N}\end{bmatrix}}}

For determination of surface, it is necessary to estimate the value of function

in specific points x.

A lack of such method is a considerable complication on the order of

to calculate RBF, solve system, and determine surface.

[2] A heirarchical algorithm allows for an acceleration of calculations due to decomposition of intricate problems on the great number of simple (see picture).

In this case, hierarchical division of space contains points on elementary parts, and the system of small dimension solves for each.

The calculation of surface in this case is taken to the hierarchical (on the basis of tree-structure) calculation of interpolant.

A method for a 2D case is offered by Pouderoux J. et al.[3] For a 3D case, a method is used in the tasks of 3D graphics by W. Qiang et al.[4] and modified by Babkov V.[5]