The trend in science and engineering applications has been to produce larger data sets, since computers and imaging technology are getting faster and storage space is increasing. Large amounts of data are difficult to visualize, and it is impossible to directly visualize them on inexpensive computers. Many visualization techniques exist that visualize certain types of large data. However, a general solution does not exist. A hierarchical method provides the foundation for a solution. Linear and quadratic decomposition elements can be used to form an approximation hierarchy representing large data; a user can then visualize this hierarchy on low-end machines. A hierarchical approximation method is described that uses linear, quadratic, and curved-quadratic decompositional elements. Linear element approximation and visualization has been studied extensively in the past. Higher-order element approximation and visualization is not nearly as developed as that for linear elements, thus, more research is needed. Fundamental visualization techniques--such as isosurfacing, ray casting, and cutting planes--for quadratic elements are described.

We present a method for the construction of hierarchies of single-valued functions in one, two, and three variables. The input to our method is a coarse decomposition of the compact domain of a function in the form of an interval (univariate case), triangles (bivariate case), or tetrahedra (trivariate case). We compute the best linear spline approximations, understood in an integral least squares sense, for functions defined over such triangulations and refine triangulations using repeated bisection. This requires the identification of the interval (triangle, tetrahedron) with largest error and splitting it into two intervals (triangles, tetrahedra). Each bisection step requires the re-computation of all spline coefficients due to the global nature of the best approximation problem. Nevertheless, this can be done efficiently by bisecting multiple intervals (triangles, tetrahedra) in one step and by reducing the bandwidths of the matrices resulting from the normal equations.

We present a method for the hierarchical approximation of functions in one, two, or three variables based on the finite element method (Ritz approximation). Starting with a set of data sites with associated function, we first determine a smooth (scattered-data) interpolant. Next, we construct an initial triangulation by triangulating the region bounded by the minimal subset of data sites defining the convex hull of all sites. We insert only original data sites, thus reducing storage requirements. For each triangulation we solve a minimization problem: computing the best linear spline approximation of the interpolant of all data, based on a functional involving function values and first derivatives. The error of a best linear spline approximation is computed in a Sobolev-like norm, leading to element-specific error values. We use these interval-/triangle-/tetrahedron-specific values to identify the element to subdivide next. The subdivision of an element with largest error value requires the re-computation of all spline coefficients due to the global nature of the problem. We improve efficiency by (i) subdividing multiple elements simultaneously and (ii) by using a sparse-matrix representation and system solver.

We present a method for the construction of multiple levels of tetrahedral meshes approximating a trivariate function at different levels of detail. Starting with an initial, high-resolution triangulation of a three-dimensional region, we construct coarser representation levels by collapsing tetrahedra. Each triangulation defines a linear spline function, where the function values associated with the vertices are the spline coefficients. Based on predicted errors, we collapse tetrahedron in the grid that do not cause the maximum error to exceed a use-specified threshold. Bounds are stored for individual tetrahedra and are updated as the mesh is simplified. We continue the simplification process until a certain error is reached. The result is a hierarchical data description suited for the efficient visualization of large data sets at varying levels of detail.

We discuss spline refinement methods that approximate multi-valued data defined over one, two, and three dimensions. The input to our method is a coarse decomposition of the compact domain of the function to be approximated consisting of intervals (univariate case), triangles (bivariate case), and tetrahedra (trivariate case). We first describe a best linear spline approximation scheme, understood in a least squares sense, and refine on initial mesh using repeated bisection of simplices (intervals, triangles, or tetrahedra) of maximal error. We discuss three enhancements that improve the performance and quality of our basic bisection ap- proach. The enhancements we discuss are: (i) using a -nite element approach that only considers original data sites during subdivision, (ii) including -rst-derivative information in the error functional and spline-coe+-cient computations, and (iii) using quadratic (deformed, \curved'') rather than linear simplices to better ap- proximate bivariate and trivariate data. We improve e+-ciency of our re-nement algorithms by subdividing multiple simplices simultaneously and by using a sparse- matrix representation and system solver.

We show how to extract a contour line (or isosurface) from quadratic elements--specifically from quadratic triangles and tetrahedra. We also devise how to transform the resulting contour line (or surface) into a quartic curve (or surface) based on a curved-triangle (curved-tetrahedron) mapping. A contour in a bivariate quadratic function defined over a triangle in parameter space is a conic section and can be represented by a rational-quadratic function, while in physical space it is a rational quartic. An isosurface in the trivariate case is represented as a rational-quadratic patch in parameter space and a rational-quartic patch in physical space. The resulting contour surfaces can be rendered efficiently in hardware.

We discuss spline refinement methods that approximate multi-valued data defined over one, two, and three dimensions. The input to our method is a coarse decomposition of the compact domain of the function to be approximated consisting of intervals (univariate case), triangles (bivariate case), and tetrahedra (trivariate case). We first describe a best linear spline approximation scheme, understood in a least squares sense, and refine on initial mesh using repeated bisection of simplices (intervals, triangles, or tetrahedra) of maximal error. We discuss three enhancements that improve the performance and quality of our basic bisection approach. The enhancements we discuss are: (i) using a finite element approach that only considers original data sites during subdivision, (ii) including first-derivative information in the error functional and spline-coefficient computations, and (iii) using quadratic (deformed, ''curved'') rather than linear simplices to better approximate bivariate and trivariate data. We improve efficiency of our refinement algorithms by subdividing multiple simplices simultaneously and by using a sparse- matrix representation and system solver.

We present a method for ray casting curved-quadratic elements in 3D. The advantages of this approach is that a curved element can be directly visualized. Conventionally, higher-order elements are tessellated with several linear elements so that standard visualization techniques can be applied to the linear elements. Our method primarily focuses on how to find an approximation to the intersection between a ray and a curved-quadratic element. Once this approximation is found, conventional accumulation and color mapping techniques can be applied to the approximation to produce a volumetric visualization of the element. A cutting plane implementation is also shown that leverages the ray casting technique.