FastRBFTM Theory

The following papers and FAQ describe the Radial Basis Function (RBF) techniques that underly our surface modelling and scattered data modelling software.

Radial Basis Function FAQs

You can find out more about some of the aspects of our approach to data modelling below.

Code

Papers

The paper that we presented at GRAPHITE 2003 is now available for download. The abstract is below.

Smooth surface reconstruction from noisy range data
J. C. Carr, R. K. Beatson, B. C. McCallum, W. R. Fright, T. J. McLennan and T. J. Mitchell
ACM GRAPHITE 2003, Melbourne, Australia, pp119-126, 11-19 February 2003.

This paper shows that scattered range data can be smoothed at low cost by fitting a Radial Basis Function (RBF) to the data and convolving with a smoothing kernel (low pass filtering). The RBF exactly describes the range data and interpolates across holes and gaps. The data is smoothed during evaluation of the RBF by simply changing the basic function. The amount of smoothing can be varied as required without having to fit a new RBF to the data. The key feature of our approach is that it avoids resampling the RBF on a fine grid or performing a numerical convolution. Furthermore, the computation required is independent of the extent of the smoothing kernel, i.e., the amount of smoothing. We show that particular smoothing kernels result in the applicability of fast numerical methods. We also discuss an alternative approach in which a discrete approximation to the smoothing kernel achieves similar results by adding new centres to the original RBF during evaluation. This approach allows arbitrary filter kernels, including anisotropic and spatially varying filters, to be applied while also using established fast evaluation methods. We illustrate both techniques with LIDAR laser scan data and noisy synthetic data.
  • Download [1.6 MB]

    The paper that we presented at SIGGRAPH 2001 is now available for download. The abstract is below.

    Reconstruction and Representation of 3D Objects with Radial Basis Functions
    J. C. Carr, R. K. Beatson, J.B. Cherrie, T. J. Mitchell, W. R. Fright, B. C. McCallum and T. R. Evans
    ACM SIGGRAPH 2001, Los Angeles, CA, pp67-76, 12-17 August 2001.

    We use polyharmonic Radial Basis Functions (RBFs) to reconstruct smooth, manifold surfaces from point-cloud data and to repair incomplete meshes. An object’s surface is defined implicitly as the zero set of an RBF fitted to the given surface data. Fast methods for fitting and evaluating RBFs allow us to model large data sets, consisting of millions of surface points, by a single RBF — previously an impossible task. A greedy algorithm in the fitting process reduces the number of RBF centres required to represent a surface and results in significant compression and further computational advantages. The energy-minimisation characterisation of polyharmonic splines result in a “smoothest” interpolant. This scale-independent characterisation is well-suited to reconstructing surfaces from non-uniformly sampled data. Holes are smoothly filled and surfaces smoothly extrapolated. We use a non-interpolating approximation when the data is noisy. The functional representation is in effect a solid model, which means that gradients and surface normals can be determined analytically. This helps generate uniform meshes and we show that the RBF representation has advantages for mesh simplification and re-meshing applications. Results are presented for real-world rangefinder data.
  • Download [1.3 MB]
  • Read the paper's bibliography

    You can also download an earlier paper on medical imaging.

    Surface Interpolation with Radial Basis Functions for Medical Imaging
    J. C. Carr, W. R. Fright and R. K. Beatson
    IEEE Transactions on Medical Imaging, Vol. 16, No 1, pp 96-107, February 1997.

    Radial basis functions are presented as a practical solution to the problem of interpolating incomplete surfaces derived from three-dimensional (3D) medical graphics. The specific application considered is the design of cranial implants for the repair of defects, usually holes, in the skull.

    Radial basis functions impose few restrictions on the geometry of the interpolation centers and are suited to problems where the interpolation centers do not form a regular grid. However, their high computational requirements have previously limited their use to problems where the number of interpolation centers is small (<300). Recently developed fast evaluation techniques have overcome these limitations and made radial basis interpolation a practical approach for larger data sets.

    In this paper radial basis functions are fitted to depth-maps of the skull's surface, obtained from X-ray CT data using ray-tracing techniques. They are used to smoothly interpolate the surface of the skull across defect regions. The resulting mathematical description of the skull's surface can be evaluated at any desired resolution to be rendered on a graphics workstation, or to generate instructions for operating a CNC mill.
  • Download (gzipped postscript) [1.27 MB]

    •