**Abstract:** We present a new scattered data fitting method, where
local approximating polynomials are directly extended to smooth ($C^1$
or $C^2$) splines on a uniform triangulation $\Delta$ (the four directional
mesh). The method is based on designing appropriate minimal determining
sets consisting of whole triangles of domain points for a uniformly distributed
subset of $\tri$. This construction allows to use discrete polynomial least
squares approximations to the local portions of the data directly as parts
of the approximating spline. The remaining Bernstein-\bez\ coefficients
are efficiently computed by extension, \ie~using the smoothness conditions.
To obtain high quality local polynomial approximations even for difficult
point constellations (\eg\ with voids, clusters, tracks), we adaptively
choose the polynomial degrees by controlling the smallest singular value
of the local collocation matrices. The computational complexity of the
method grows linearly with the number of data points, which facilitates
its application to large data sets. Numerical tests involving standard
benchmarks as well as real world scattered data sets illustrate the approximation
power of the method, its efficiency and ability to produce surfaces of
high visual quality, to deal with noisy data, and to be used for surface
compression.

**Preprint version available:** pdf

Homepage