Spline Approximation of General Volumetric Data

Abstract

We present an efficient algorithm for approximating huge general volumetric data sets, i.e. the data is given over arbitrarily shaped volumes and consists of up to millions of samples. The method is based on cubic trivariate splines, i.e. piecewise polynomials of total degree three defined w.r.t. uniform type-6 tetrahedral partitions of the volumetric domain. Similar as in the recent bivariate approximation approaches (cf. [10, 15]), the splines in three variables are automatically determined from the discrete data as a result of a two-step method (see [40]), where local discrete least squares polynomial approximations of varying degrees are extended by using natural conditions, i.e. the continuity and smoothness properties which determine the underlying spline space. The main advantages of this approach with linear algorithmic complexity are as follows: no tetrahedral partition of the volume data is needed, only small linear systems have to be solved, the local variation and distribution of the data is automatically adapted, Bernstein-Bézier techniques well-known in Computer Aided Geometric Design (CAGD) can be fully exploited, noisy data are automatically smoothed. Our numerical examples with huge data sets for synthetic data as well as some real-world data confirm the efficiency of the methods, show the high quality of the spline approximation, and illustrate that the rendered iso-surfaces inherit a visual smooth appearance from the volume approximating splines.