A practical guide to radial basis functions (2007) [pdf](num.math.uni-goettingen.de)
num.math.uni-goettingen.de
A practical guide to radial basis functions (2007) [pdf]
http://num.math.uni-goettingen.de/schaback/teaching/sc.pdf
4 comments
I first heard about them at Siggraph 2001. This paper https://dl.acm.org/doi/10.1145/383259.383266 by an acquaintance described a way of fitting RBFs to very large point clouds. The trick was to use Fast Multipole Methods, which are a bit like treecodes for n-body problems: https://en.wikipedia.org/wiki/Barnes%E2%80%93Hut_simulation
Fitting an RBF naively involves inverting a matrix as big as the number of points, but the FMM techniques use approximation to make the task practical.
JP Lewis has some course notes which explain the basics of RBF techniques well: http://scribblethink.org/Courses/ScatteredInterpolation/scat...
For a slightly more technical account, try Sage Shaw's excellent contribution to this Wikipedia page: https://en.wikipedia.org/wiki/Radial_basis_function_interpol...
Fitting an RBF naively involves inverting a matrix as big as the number of points, but the FMM techniques use approximation to make the task practical.
JP Lewis has some course notes which explain the basics of RBF techniques well: http://scribblethink.org/Courses/ScatteredInterpolation/scat...
For a slightly more technical account, try Sage Shaw's excellent contribution to this Wikipedia page: https://en.wikipedia.org/wiki/Radial_basis_function_interpol...
Yes, I'm familiar with that paper. It's very complicated to implement - back when I was researching I didn't encounter any papers by others who had replicated it, and citations often mentioned its complexity. There are simpler ways to scale RBFs. I did it piecewise, using overlapping subdomains (each with ~200 points, so a small linear system) blended with partition of unity, and it scaled to millions of points in an embarrassingly parallelisable way. Here's a result I've linked on HN before, filling a hole in a point cloud (a small one, ~24000 points): https://imgur.com/a/k6AQi
Those course notes have some interesting stuff in them, thanks!
Those course notes have some interesting stuff in them, thanks!
A Rust implementation, with visuals and pointers to other resources: https://crates.io/crates/rbf-interp
They also made a good well-obfuscated "peak hello world" attempt: https://news.ycombinator.com/item?id=23211972
That fits a multiquadric RBF (p2) (with linear terms, because it's conditionally positive definite; p5-6) to some carefully chosen data, then evaluates it (at the same points again, because I was in a hurry...) and converts to characters.