**Abstract:** We present an efficient method to automatically compute
a smooth approximation of large functional scattered data sets given over
arbitrarily shaped planar domains. Our approach is based on the construction
of a $C^1$-continuous bivariate cubic spline and our method offers optimal
approximation order. Both local variation and non-uniform distribution
of the data are taken into account by using local polynomial least squares
approximations of varying degree. Since we only need to solve small linear
systems and no triangulation of the scattered data points is required,
the overall complexity of the algorithm is linear in the total number of
points. Numerical examples dealing with several real world scattered data
sets with up to millions of points demonstrate the efficiency of our method.
The resulting spline surface is of high visual quality and can be efficiently
evaluated for rendering and modeling. In our implementation we achieve
real-time frame rates for typical fly-through sequences and interactive
frame rates for recomputing and rendering a locally modified spline surface.

**Preprint version available:** pdf

Homepage