This is the third history blog in a six part series – Modelling in full 3D. If you missed part two, Medicine, movies and outer space!, you can find it here.

In 1996 in pursuit of more mathematically robust meshes ARANZ rekindled their close collaboration with mathematician Rick Beatson. This motivated the extension of his fast RBF methods to modelling full 3D data and a new way of describing the surfaces of objects implicitly using a ‘signed-distance’ function.

Says ARANZ Geo founder Rick Fright, “Having got the scanner working, and gathered scattered point measurements from the surface of a 3D object, we realised we had an even bigger problem of reconstructing a complete and continuous surface model. So we got back in touch with Rick Beatson.”

The solution

Supported by a New Zealand Ministry of Research Grant that had been awarded to ARANZ, Rick Beatson and his students, Tim Mitchell and Jon Cherrie, came up with the following important solution.

– Reconstructing a surface of arbitrary (unconstrained) complexity in three dimensions was too difficult.
– They decided to solve another related , they knew how to do – model “density” data in three dimensions.
– They took the 3D surface points and “invented” notional (mathematically convenient) 3D density data – this is simply the signed distance (a computation) from the surface i.e. at any point in space outside the surface it is the distance to the closest point on the surface, and the same goes inside the surface, except the value there is negative – this is the 3D density data they modelled with RBFs.
– The desired surface can then be straightforwardly computed from the density RBF model using iso-value tracking algorithms.

The mathematics

Rick Beatson’s work is recognised as fundamental to ARANZ’s products, in fact Jonathan Carr, jokes that ‘RBF’ was known as Rick Beatson Functions! So the primary work behind Leapfrog was not the software, but the mathematics.

Rick Fright echoes these sentiments, “We really have Rick Beatson’s work to thank for this. We are engineers and we would have found a way if Rick hadn’t come along but things would have been different. He chose such a good method.”

Says Jonathan, “I think the collaboration between ARANZ and Rick Beatson actually produced new math in itself or at least refined the original theoretical work. There is great merit in the realisation that smoothing of an RBF could be achieved analytically by convolving the basis function with a smoothing kernel. This led to a digital approximation that we formulated in our 2002 Graphite paper†. I don’t think many people appreciate the significance and elegance of this approach.”

Smooth, continuous and closed

The laser scanner with radial basis function surface reconstruction was a winner, because it could generate models at the level of detail required for the task, and the surface was guaranteed to be smooth, continuous and closed (watertight) if required, and also guaranteed to contain no mistakes such as intersections. This is extremely important when machining something defined by the surface.

Continues Rick Fright, “Our problem was surface modelling but our solution was also capable of density modelling. So we wondered ‘what density modelling problems are out there that we could apply this to?’ This was when the opportunities with mining were identified.”

Next – our next blog in this series looking back at the history of Leapfrog examines the development of the Leapfrog engine Fast RBF™.

†J. C. Carr, R. K. Beatson, B. C. McCallum, W. R.Fright, T. J. McLennan, and T. J. Mitchell. Smooth surface reconstruction from noisy range data. In Proceedings of ACM Graphite 2003, pages 119–126. ACM Press, 2003.