We present a segmentation approach to scientific visualization that combines the definition of higher-level data, the efficient extraction of meaningful derived feature-like data from defined properties, and the effective visual representation of the extracted data. Our framework is aimed at multi-valued time-varying data sets, where, for example, grid vertices might have a multitude of associated scalar, vector and tensor quantities. This segmentation approach to massive data set exploration allows the user to focus upon regions, and interactively explore these regions efficiently. The challenge is to generate this segmented data from existing multi-valued data sets, store this data in an efficient scheme, generate the boundaries of each region, and display these boundaries to the user. We present an integrated scheme that allows a common representation for segmentation, allows it to be applied to a number of data types, and allows derived representations to be calculated. We illustrate this framework with examples from scalar-and vector-field visualization.

We present a simple and output optimal algorithm for accelerated isosurface extraction from volumetric data sets. Output optimal extraction algorithms perform an amount of work dominated by the size of the (output) isosurface rather than the size of the (input) data set. While several optimal methods have been proposed to accelerate isosurface extraction, these algorithms are relatively complicated to implement or require quantized values as input. Our method is based on a straightforward array data structure that only requires an auxiliary sorting routine for construction. The method works equally well for floating point data as it does for quantized data sets. We demonstrate how the data structure can exploit coherence between isosurfaces by performing searches incrementally. We show results for real application data validating the method's optimality.

B-Spline curves and surfaces can be de(r)ned by a set of control points and a set of refinement rules. These rules act on the defining mesh of control points to create a new refined mesh. Repeated application of the rules generates a sequence of meshes that converge to the curve or surface. In the surface case, Catmull and Clark extended the refinement rules for the rectangular topological meshes of the B-spline form to meshes that have an arbitrary topological structure. In much the same way, the refinement rules for a trivariate B-spline solid can be extended from those that apply to the regular hexahedral topological lattices of the B-spline form to lattices that have an arbitrary topological structure. We present a uniform development of the refinement rules for trivariate B-spline solids and extend the rules to apply to solid lattices of arbitrary topology.

The trivariate tensor-product B-spline solid is a direct extension of the B-spline patch and has been shown to be useful in the creation and visualization of free-form geometric solids. Visualizing these solid objects requires the determination of the boundary surface of the solid, which is a combination of parametric and implicit surfaces. This paper presents a method that determines the implicit boundary surface by examination of the Jacobian determinant of the defining B-spline function. Using an approximation to this determinant, the domain space is adaptively subdivided until a mesh can be determined such that the boundary surface is close to linear in the cells of the mesh. A variation of the marching cubes algorithm is then used to draw the surface. Interval approximation techniques are used to approximate the Jacobian determinant and to approximate the Jacobian determinant gradient for use in the adaptive subdivision methods. This technique can be used to create free-form solid objects, useful in geometric modeling applications.

Applying certain visualization techniques to datasets described on unstructured grids requires the interpolation of variables of interest at arbitrary locations within the dataset's domain of definition. Typical solutions to the problem of finding the grid element enclosing a given interpolation point make use of a variety of spatial subdivision schemes. However, existing solutions are memory-intensive, do not scale well to large grids, or do not work reliably on grids describing complex geometries. In this paper, we propose a data structure and associated construction algorithm for fast cell location in unstructured grids, and apply it to the interpolation problem. Based on the concept of bounding interval hierarchies, the proposed approach is memory-efficient, fast and numerically robust. We examine the performance characteristics of the proposed approach and compare it to existing approaches using a number of benchmark problems related to vector field visualization. Furthermore, we demonstrate that our approach can successfully accommodate large datasets, and discuss application to visualization on both CPUs and GPUs.

Consider a triangulation of the xy plane, and a general surface z = f (xy). The points of the triangle, when lifted to the surface, form a linear spline approximation to the surface. We are interested in the error between the surface and the linear approximant. In fact, we are interested in building triangulations in the plane such that the induced linear approximant is near-optimal with respect to a given error. Here we describe a new method, which iteratively adds points to a ''Delaunay-like'' triangulation of the plane. We locally approximate f by a quadratic surface and utilize this quadrilateral that enables us to minimize the error between the surface and the triangulation.

We present a method for calculating the envelope of the swept surface of a solid along a path in three-dimensional space. The generator of the swept surface is a trivariate tensorproduct B`ezier solid and the path is a non-uniform rational B-spline curve. The boundary surface of the solid is the combination of parametric surfaces and an implicit surface where the determinant of the Jacobian of the defining function is zero. We define methods to calculate the envelope for each type of boundary surface, defining characteristic curves on the envelope and connecting them with triangle strips. The envelope of the swept solid is then calculated by taking the union of the envelopes of the family of boundary surfaces, defined by the surface of the solid in motion along the path.

We present a method for calculating the envelope surface of a parametric solid object swept along a path in three dimensional space. The boundary surface of the solid is the combination of parametric surfaces and an implicit surface where the Jacobian of the defining function has a rankdeficiency condition. Using this condition, we determine a set of square sub-Jacobian determinants that must all vanish simultaneously on the implicit surface. When the generator of the swept surface is a trivariate tensor-product B-spline solid and the path is a B-spline curve, we can give a robust algorithm to determine the implicit surface. This algorithm is based upon the marching tetrahedra method, which is adapted to work on 4-simplices. The envelope of the swept solid is given by the union of the parametric and implicit surfaces.

We present a flow visualization technique based on rendering geometry in a dense, uniform distribution. Flow is integrated using particle advection. By adopting ideas from texture-based techniques and taking advantage of parallelism and programmability of contemporary graphics hardware, we generate streamlines and pathlines addressing both steady and unsteady flow. Pipelining is used to manage seeding, advection, and expiration of streamlines/pathlines with constant lifetime. We achieve high numerical accuracy by enforcing short particle lifetimes and employing a fourth-order integration method. The occlusion problem inherent to dense volumetric representations is addressed by applying multi-dimensional transfer functions (MDTFs), restricting particle attenuation to regions of certain physical behavior, or features. Geometry is rendered in graphics hardware using techniques such as depth sorting, illumination, haloing, flow orientation, and depth-based color attenuation to enhance visual perception. We achieve dense geometric three-dimensional flow visualization with interactive frame rates.

This paper presents a new algorithm for the calculation of stream surfaces for tetrahedral grids. It propagates the surface through the tetrahedra, one at a time, calculating the intersections with the tetrahedral faces. The method allows us to incorporate topological information from the cells, e.g., critical points. The calculations are based on barycentric coordinates, since this simplifies theory and algorithm. The stream surfaces are ruled surfaces inside each cell, and their construction is started with line segments on the faces. Our method supports the analysis of velocity fields resulting from computational fluid dynamics (CFD) simulations.