A new material interface reconstruction method for volume fraction data is presented. Our method is comprised of two components: first, we generate initial interface topology; then, using a combination of smoothing and volumetric forces within an active interface model, we iteratively transform the initial material interfaces into high-quality surfaces that accurately approximate the problem's volume fractions. Unlike all previous work, our new method produces material interfaces that are smooth, continuous across cell boundaries, and segment cells into regions with proper volume. These properties are critical during visualization and analysis. Generating high-quality mesh representations of material interfaces is required for accurate calculations of interface statistics, and dramatically increases the utility of material boundary visualizations.

Abstract We present a dimension reduction and feature extraction method for the visualization and analysis of function field data. Function fields are a class of high‐dimensional, multi‐variate data in which data samples are one‐dimensional scalar functions. Our approach focuses upon the creation of high‐dimensional range‐space segmentations, from which we can generate meaningful visualizations and extract separating surfaces between features. We demonstrate our approach on high‐dimensional spectral imagery, and particulate pollution data from air quality simulations.

Abstract Material interface reconstruction (MIR) is the task of constructing boundary interfaces between regions of homogeneous material, while satisfying volume constraints, over a structured or unstructured spatial domain. In this paper, we present a discrete approach to MIR based upon optimizing the labeling of fractional volume elements within a discretization of the problem's original domain. We detail how to construct and initially label a discretization, and introduce a volume conservative swap move for optimization. Furthermore, we discuss methods for extracting and visualizing material interfaces from the discretization. Our technique has significant advantages over previous methods: we produce interfaces between multiple materials that are continuous across cell boundaries for time‐varying and static data in arbitrary dimension with bounded error.

We present interactive techniques for identifying and extracting features in function fields. Function fields map points in n-dimensional Euclidean space to 1-dimensional scalar functions. Visual feature identification is ac- complished by interactively rendering scalar distance fields, constructed by applying a function-space distance metric over the function field. Combining visual exploration with feature extraction queries, formulated as a set of function-space constraints, facilitates quantitative analysis and annotation. Numerous application domains give rise to function fields. We present results for two-dimensional hyperspectral images, and a simulated time-varying, three-dimensional air quality dataset.

Analysis of the results obtained from material simulations is important in the physical sciences. Our research was motivated by the need to investigate the properties of a simulated porous solid as it is hit by a projectile. This paper describes two techniques for the generation of distance fields containing a minimal number of topological features, and we use them to identify features of the material. We focus on distance fields defined on a volumetric domain considering the distance to a given surface embedded within the domain. Topological features of the field are characterized by its critical points. Our first method begins with a distance field that is computed using a standard approach, and simplifies this field using ideas from Morse theory. We present a procedure for identifying and extracting a feature set through analysis of the MS complex, and apply it to find the invariants in the clean distance field. Our second method proceeds by advancing a front, beginning at the surface, and locally controlling the creation of new critical points. We demonstrate the value of topologically clean distance fields for the analysis of filament structures in porous solids. Our methods produce a curved skeleton representation of the filaments that helps material scientists to perform a detailed qualitative and quantitative analysis of pores, and hence infer important material properties. Furthermore, we provide a set of criteria for finding the "difference" between two skeletal structures, and use this to examine how the structure of the porous solid changes over several timesteps in the simulation of the particle impact.

Summary form only given. We developed the piecewise-linear Haar (PLHaar) transform (Senecal, J.G. et al., Proc. 12th Pacific Conf. on Computer Graphics and Appl., p.371-80, 2004), an integer wavelet-like transform. PLHaar does not have dynamic range expansion, i.e., it is an n-bit to n-bit transform. To our knowledge, PLHaar is the only reversible n-bit to n-bit transform that is suitable for lossy and lossless coding. We are investigating PLHaar's use in lossy image coding. Preliminary results from thresholding transform coefficients show that PLHaar does not produce objectionable artifacts like previous n-bit to n-bit transforms, such as that of Honyang Chao et al. (CFH) (see Advances in Computational Mathematics, Lect. Notes In Pure and App. Math., vol.202, p.13-38, 1999). Also, at lower bitrates PLHaar images have increased contrast. For a given set of CFH and PLHaar coefficients with equal entropy, the PLHaar reconstruction is more appealing, although the PSNR may be lower.

The real-time display of huge geometry and imagery databases involves view-dependent approximations, typically through the use of precomputed hierarchies that are selectively refined at runtime. A classic motivating problem is terrain visualization in which planetary databases involving billions of elevation and color values are displayed on PC graphics hardware at high frame rates. This paper introduces a new diamond data structure for the basic selective-refinement processing, which is a streamlined method of representing the well-known hierarchies of right triangles that have enjoyed much success in real-time, view-dependent terrain display. Regular-grid tiles are proposed as the payload data per diamond for both geometry and texture. The use of 4-8 grid refinement and coarsening schemes allows level-of-detail transitions that are twice as gradual as traditional quadtree-based hierarchies, as well as very high-quality low-pass filtering compared to subsampling-based hierarchies. An out-of-core storage organization is introduced based on Sierpinski indices per diamond, along with a tile preprocessing framework based on fine-to-coarse, same-level, and coarse-to-fine gathering operations. To attain optimal frame-to-frame coherence and processing-order priorities, dual split and merge queues are developed similar to the Realtime Optimally Adapting Meshes (ROAM) Algorithm, as well as an adaptation of the ROAM frustum culling technique. Example applications of lake-detection and procedural terrain generation demonstrate the flexibility of the tile processing framework.

Arithmetic coding achieves a superior coding rate when encoding a binary source, but its lack of speed makes it an inferior choice when true high-performance encoding is needed. This paper presents the practical implementation of fast entropy coders for binary messages utilizing only bit shifts and table lookups. To limit code table size the proposed code lengths is limited with a type of variable-to-variable (VV) length code created from source string merging. This is referred to as "merged codes". With merged codes it is possible to achieve a desired level of speed by adjusting the number of bits read from the source at each step. The most efficient merged codes yield a coder with a worst-case inefficiency of 0.4%, relative to the Shannon entropy. Using a hybrid Golomb-VV bin coder the compression ratio that is competitive with other state-of-the-art coders, at a superior throughput is achieved.

Methods of producing reversible n-bit to n-bit integer transforms is presented in this paper. Such methods are particularly suited for hardware-based implementations, as keeping the coefficients to n bits simplifies the design of custom hardware and makes it easier to use these approaches on preexisting hardware with limited channel width. One of our methods, called table-lookup Haar (TLHaar) is an approximation of the Haar integer wavelet transform (Haar IWT). The Haar IWT takes two integer data values A and B and using averaging and differencing produces a low-pass value L and a high-pass value H, both integers. The lookup tables are created by initializing each with an identity transform. TLHaar executes up to 44% faster. Compression results are mixed, and depend on the compression method used and the image type.

We introduce the piecewise-linear Haar (PLHaar) transform, a reversible n-bit to n-bit transform that is based on the Haar wavelet transform. PLHaar is continuous, while all current n-bit to n-bit methods are not, and is therefore uniquely usable with both lossy and lossless methods (e.g. image compression). PLHaar has both integer and continuous (i.e. non-discrete) forms. By keeping the coefficients to n bits PLHaar is particularly suited for use in hardware environments where channel width is limited, such as digital video channels and graphics hardware.

We address the texture level-of-detail problem for extremely large surfaces such as terrain during realtime, view-dependent rendering. A novel texture hierarchy is introduced based on 4-8 refinements of raster tiles, in which the texture grids in effect rotate 45 degrees for each level of refinement. This hierarchy provides twice as many levels of detail as conventional quadtree-style refinement schemes such as mipmaps, and thus provides per-pixel view-dependent filtering that is twice as close to the ideal cutoff frequency for an average pixel. Because of this more gradual change in low-pass filtering, and due to the more precise emulation of the ideal cutoff frequency, we find in practice that the transitions between texture levels of detail are not perceptible. This allows rendering systems to avoid the complexity and performance costs of per-pixel blending between texture levels of detail. The 4-8 texturing scheme is integrated into a variant of the real-time optimally adapting meshes (ROAM) algorithm for view-dependent multiresolution mesh generation. Improvements to ROAM included here are: the diamond data structure as a streamlined replacement for the triangle bintree elements, the use of low-pass-filtered geometry patches in place of individual triangles, integration of 4-8 textures, and a simple out-of-core data access mechanism for texture and geometry tiles.

We present a new construction of lifted biorthogonal wavelets on surfaces of arbitrary two-manifold topology for compression and multiresolution representation. Our method combines three approaches: subdivision surfaces of arbitrary topology, B-spline wavelets, and the lifting scheme for biorthogonal wavelet construction. The simple building blocks of our wavelet transform are local lifting operations performed on polygonal meshes with subdivision hierarchy. Starting with a coarse, irregular polyhedral base mesh, our transform creates a subdivision hierarchy of meshes converging to a smooth limit surface. At every subdivision level, geometric detail can be expanded from wavelet coefficients and added to the surface. We present wavelet constructions for bilinear, bicubic, and biquintic B-Spline subdivision. While the bilinear and bicubic constructions perform well in numerical experiments, the biquintic construction turns out to be unstable. For lossless compression, our transform can be computed in integer arithmetic, mapping integer coordinates of control points to integer wavelet coefficients. Our approach provides a highly efficient and progressive representation for complex geometries of arbitrary topology.

We present an algorithm for adaptively extracting and rendering isosurfaces from compressed time-varying volume data sets. Tetrahedral meshes defined by longest edge bisection are used to create a multiresolution representation of the volume in the spatial domain that is adapted over time to approximate the time-varying volume. The reextraction of the isosurface at each time step is accelerated with the vertex programming capabilities of modern graphics hardware. A data layout scheme which follows the access pattern indicated by mesh refinement is used to access the volume in a spatially and temporally coherent manner. This data layout scheme allows our algorithm to be used for out-of-core visualization.

The paper presents an algorithm for material interface reconstruction for data sets where fractional material information is given as a percentage for each element of the underlying grid. The reconstruction problem is transformed to a problem that analyzes a dual grid, where each vertex in the dual grid has an associated barycentric coordinate tuple that represents the fraction of each material present. Material boundaries are constructed by analyzing the barycentric coordinate tuples of a tetrahedron in material space and calculating intersections with Voronoi cells that represent the regions where one material dominates. These intersections are used to calculate intersections in the Euclidean coordinates of the tetrahedron. By triangulating these intersection points, one creates the material boundary. The algorithm can treat data sets containing any number of materials. The algorithm can also create nonmanifold boundary surfaces if necessary. By clipping the generated material boundaries against the original cells, one can examine the error in the algorithm. Error analysis shows that the algorithm preserves volume fractions within an error range of 0.5 percent per material.

Multiresolution methods for representing data at multiple levels of detail are widely used for large-scale two- and three-dimensional data sets. We present a four-dimensional multiresolution approach for time-varying volume data. This approach supports a hierarchy with spatial and temporal scalability. The hierarchical data organization is based on /sup 4//spl radic/2 subdivision. The /sup n//spl radic/2-subdivision scheme only doubles the overall number of grid points in each subdivision step. This fact leads to fine granularity and high adaptivity, which is especially desirable in the spatial dimensions. For high-quality data approximation on each level of detail, we use quadrilinear B-spline wavelets. We present a linear B-spline wavelet lifting scheme based on /sup n//spl radic/2 subdivision to obtain narrow masks for the update rules. Narrow masks provide a basis for out-of-core data exploration techniques and view-dependent visualization of sequences of time steps.

We present an algorithm for interactively extracting and rendering isosurfaces of large volume datasets in a view-dependent fashion. A recursive tetrahedral mesh refinement scheme, based on longest edge bisection, is used to hierarchically decompose the data into a multiresolution structure. This data structure allows fast extraction of arbitrary isosurfaces to within user specified view-dependent error bounds. A data layout scheme based on hierarchical space filling curves provides access to the data in a cache coherent manner that follows the data access pattern indicated by the mesh refinement.

We present a new wavelet compression and multiresolution modeling approach for sets of contours (level sets). In contrast to previous wavelet schemes, our algorithm creates a parametrization of a scalar field induced by its contours and compactly stores this parametrization rather than function values sampled on a regular grid. Our representation is based on hierarchical polygon meshes with subdivision connectivity whose vertices are transformed into wavelet coefficients. From this sparse set of coefficients, every set of contours can be efficiently reconstructed at multiple levels of resolution. When applying lossy compression, introducing high quantization errors, our method preserves contour topology, in contrast to compression methods applied to the corresponding field function. We provide numerical results for scalar fields defined on planar domains. Our approach generalizes to volumetric domains, time-varying contours, and level sets of vector fields.

We introduce a new subdivision-surface wavelet transform for arbitrary two-manifolds with boundary that is the first to use simple lifting-style filtering operations with bicubic precision. We also describe a conversion process for re-mapping large-scale isosurfaces to have subdivision connectivity and fair parameterizations so that the new wavelet transform can be used for compression and visualization. The main idea enabling our wavelet transform is the circular symmetrization of the filters in irregular neighborhoods, which replaces the traditional separation of filters into two 1-D passes. Our wavelet transform uses polygonal base meshes to represent surface topology, from which a Catmull-Clark-style subdivision hierarchy is generated. The details between these levels of resolution are quickly computed and compactly stored as wavelet coefficients. The isosurface conversion process begins with a contour triangulation computed using conventional techniques, which we subsequently simplify with a variant edge-collapse procedure, followed by an edge-removal process. This provides a coarse initial base mesh, which is subsequently refined, relaxed and attracted in phases to converge to the contour. The conversion is designed to produce smooth, untangled and minimally-skewed parameterizations, which improves the subsequent compression after applying the transform. We have demonstrated our conversion and transform for an isosurface obtained from a high-resolution turbulent-mixing hydrodynamics simulation, showing the potential for compression and level-of-detail visualization.

We present a new algorithm for material boundary interface reconstruction from data sets containing volume fractions. We transform the reconstruction problem to a problem that analyzes the dual data set, where each vertex in the dual mesh has an associated barycentric coordinate tuple that represents the fraction of each material present. After constructing the dual tetrahedral mesh from the original mesh, we construct material boundaries by mapping a tetrahedron into barycentric space and calculating the intersections with Voronoi cells in barycentric space. These intersections are mapped back to the original physical space and triangulated to form the boundary surface approximation. This algorithm can be applied to any grid structure and can treat any number of materials per element/vertex.

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.

Terrain visualization is a difficult problem for applications requiring accurate images of large datasets at high frame rates, such as flight simulation and ground-based aircraft testing using synthetic sensor simulation. On current graphics hardware, the problem is to maintain dynamic, view-dependent triangle meshes and texture maps that produce good images at the required frame rate. We present an algorithm for constructing triangle meshes that optimizes flexible view-dependent error metrics, produces guaranteed error bounds, achieves specified triangle counts directly and uses frame-to-frame coherence to operate at high frame rates for thousands of triangles per frame. Our method, dubbed Real-time Optimally Adapting Meshes (ROAM), uses two priority queues to drive split and merge operations that maintain continuous triangulations built from pre-processed bintree triangles. We introduce two additional performance optimizations: incremental triangle stripping and priority-computation deferral lists. ROAM's execution time is proportional to the number of triangle changes per frame, which is typically a few percent of the output mesh size; hence ROAM's performance is insensitive to the resolution and extent of the input terrain. Dynamic terrain and simple vertex morphing are supported.