Vector field topology is one of the most powerful flow visualization tools, because it can break down huge amounts of data into a compact, sparse, and easy to read description with little information loss. It suffers from one main drawback though: The definition of critical points, which is the foundation of vector field topology, is highly dependent on the frame of reference. In this paper we propose to consider every point as a critical point and locally adjust the frame of reference to the most persistent ones, that means the extrema of the determinant of the Jacobian. The result is not the extraction of one well-suited frame of reference, but the simultaneous visualization of the dominating frames of reference in the different areas of the flow field. Each of them could individually be perceived by an observer traveling along these critical points. We show all important ones at once.

Advances in computational power now enable domain scientists to address conceptual and parametric uncertainty by running simulations multiple times in order to sufficiently sample the uncertain input space. While this approach helps address conceptual and parametric uncertainties, the ensemble datasets produced by this technique present a special challenge to visualization researchers as the ensemble dataset records a distribution of possible values for each location in the domain. Contemporary visualization approaches that rely solely on summary statistics (e.g., mean and variance) cannot convey the detailed information encoded in ensemble distributions that are paramount to ensemble analysis; summary statistics provide no information about modality classification and modality persistence. To address this problem, we propose a novel technique that classifies high-variance locations based on the modality of the distribution of ensemble predictions. Additionally, we develop a set of confidence metrics to inform the end-user of the quality of fit between the distribution at a given location and its assigned class. Finally, for the special application of evaluating the stability of bimodal regions, we develop local and regional metrics.

Visualization and analysis techniques play a key role in the discovery of relevant features in ensemble data. Trends, in the form of persisting commonalities or differences in time-varying ensemble datasets, constitute one of the most expressive feature types in ensemble analysis. We develop a flow-graph representation as the core of a system designed for the visual analysis of trends in time-varying ensembles. In our interactive analysis framework, this graph is linked to a representation of ensemble parameter-space and the ensemble itself. This facilitates a detailed examination of trends and their correlations to properties of input-space. We demonstrate the utility of the proposed trends analysis framework in several benchmark data sets, highlighting its capability to support goal-driven design of time-varying simulations.

Time surfaces are a versatile tool to visualise advection and deformation in flow fields. Due to complex flow behaviours involving stretching, shearing, and folding, straightforward mesh-based representations of these surfaces can develop artefacts and degenerate quickly. Common counter-measures rely on refinement and adaptive insertion of new particles which lead to an unpredictable increase in memory requirements. We propose a novel time surface extraction technique that keeps the number of required flow particles constant, while providing a high level of fidelity and enabling straightforward load balancing. Our solution implements a 2D particle relaxation procedure that makes use of local surface metric tensors to model surface deformations. We combine this with an accurate bicubic surface representation to provide an artefact-free surface visualisation. We demonstrate and evaluate benefits of the proposed method with respect to surface accuracy and computational efficiency.

Particle tracing in time-varying flow fields is traditionally performed by numerical integration of the underlying vector field. This procedure can become computationally expensive, especially in scattered, particle-based flow fields, which complicate interpolation due to the lack of an explicit neighborhood structure. If such a particle-based flow field allows for the identification of consecutive particle positions, an alternative approach to particle tracing can be employed: we substitute repeated numerical integration of vector data by geometric interpolation in the highly dynamic particle system as defined by the particle-based simulation. To allow for efficient and accurate location and interpolation of changing particle neighborhoods, we develop a modified k-d tree representation that is capable of creating a dynamic partitioning of even highly compressible data sets with strongly varying particle densities. With this representation we are able to efficiently perform pathline computation by identifying, tracking, and updating an enclosing, dynamic particle neighborhood as particles move overtime. We investigate and evaluate the complexity, accuracy, and robustness of this interpolation-based alternative approach to trajectory generation in compressible and incompressible particle systems generated by simulation techniques such as Smoothed Particle Hydrodynamics (SPH).

Effective display and visual analysis of complex 3D data is a challenging task. Occlusions, overlaps, and projective distortions-as frequently caused by typical 3D rendering techniques-can be major obstacles to unambiguous and robust data analysis. Slicing planes are a ubiquitous tool to resolve several of these issues. They act as simple clipping geometry to provide clear cut-away views of the data. We propose to enhance the visualization and analysis process by providing methods for automatic placement of such slicing planes based on local optimization of gradient vector flow. The final obtained slicing planes maximize the total amount of information displayed with respect to a pre-specified importance function. We demonstrate how such automated slicing plane placement is able to support and enrich 3D data visualization and analysis in multiple scenarios, such as volume or surface rendering, and evaluate its performance in several benchmark data sets.

A comprehensive uncertainty, baseline, and noise analysis in computing 3D points using a recent L1-based triangulation algorithm is presented. This method is shown to be not only faster and more accurate than its main competitor, linear triangulation, but also more stable under noise and baseline changes. A Monte Carlo analysis of covariance and a confidence ellipsoid analysis were performed over a large range of baselines and noise levels for different camera configurations, to compare performance between angular error-based and linear triangulation. Furthermore, the effect of baseline and noise was analyzed for true multi-view triangulation versus pair wise stereo fusion. Results on real and synthetic data show that L1 angular error-based triangulation has a positive effect on confidence ellipsoids, lowers covariance values and results in more-accurate pair wise and multi-view triangulation, for varying numbers of cameras and configurations.

This paper presents a framework for GPU-accelerated N-view triangulation in multi-view reconstruction that improves processing time and final reprojection error with respect to methods in the literature. The framework uses an algorithm based on optimizing an angular error-based L1cost function and it is shown how adaptive gradient descent can be applied for convergence. The triangulation algorithm is mapped onto the GPU and two approaches for parallelization are compared: one thread per track and one thread block per track. The better performing approach depends on the number of tracks and the lengths of the tracks in the dataset. Furthermore, the algorithm uses statistical sampling based on confidence levels to successfully reduce the quantity of feature track positions needed to triangulate an entire track. Sampling aids in load balancing for the GPU's SIMD architecture and for exploiting the GPU's memory hierarchy. When compared to a serial implementation, a typical performance increase of 3-4× can be achieved on a 4-core CPU. On a GPU, large track numbers are favorable and an increase of up to 40× can be achieved. Results on real and synthetic data prove that reprojection errors are similar to the best performing current triangulation methods but costing only a fraction of the computation time, allowing for efficient and accurate triangulation of large scenes.

This paper presents a framework for N-view triangulation of scene points, which improves processing time and final reprojection error with respect to standard methods, such as linear triangulation. The framework introduces an angular error-based cost function, which is robust to outliers and inexpensive to compute, and designed such that simple adaptive gradient descent can be applied for convergence. Our method also presents a statistical sampling component based on confidence levels, that reduces the number of rays to be used for triangulation of a given feature track. It is shown how the statistical component yields a meaningful yet much reduced set of representative rays for triangulation, and how the application of the cost function on the reduced sample can efficiently yield faster and more accurate solutions. Results are demonstrated on real and synthetic data, where it is proven to significantly increase the speed of triangulation and optimize reprojection error in most cases. This makes it especially attractive for efficient triangulation of large scenes given the speed and low memory requirements.

Numerical ensemble forecasting is a powerful tool that drives many risk analysis efforts and decision making tasks. These ensembles are composed of individual simulations that each uniquely model a possible outcome for a common event of interest: e.g., the direction and force of a hurricane, or the path of travel and mortality rate of a pandemic. This paper presents a new visual strategy to help quantify and characterize a numerical ensemble's predictive uncertainty: i.e., the ability for ensemble constituents to accurately and consistently predict an event of interest based on ground truth observations. Our strategy employs a Bayesian framework to first construct a statistical aggregate from the ensemble. We extend the information obtained from the aggregate with a visualization strategy that characterizes predictive uncertainty at two levels: at a global level, which assesses the ensemble as a whole, as well as a local level, which examines each of the ensemble's constituents. Through this approach, modelers are able to better assess the predictive strengths and weaknesses of the ensemble as a whole, as well as individual models. We apply our method to two datasets to demonstrate its broad applicability.

Sets of simulation runs based on parameter and model variation, so-called ensembles, are increasingly used to model physical behaviors whose parameter space is too large or complex to be explored automatically. Visualization plays a key role in conveying important properties in ensembles, such as the degree to which members of the ensemble agree or disagree in their behavior. For ensembles of time-varying vector fields, there are numerous challenges for providing an expressive comparative visualization, among which is the requirement to relate the effect of individual flow divergence to joint transport characteristics of the ensemble. Yet, techniques developed for scalar ensembles are of little use in this context, as the notion of transport induced by a vector field cannot be modeled using such tools. We develop a Lagrangian framework for the comparison of flow fields in an ensemble. Our techniques evaluate individual and joint transport variance and introduce a classification space that facilitates incorporation of these properties into a common ensemble visualization. Variances of Lagrangian neighborhoods are computed using pathline integration and Principal Components Analysis. This allows for an inclusion of uncertainty measurements into the visualization and analysis approach. Our results demonstrate the usefulness and expressiveness of the presented method on several practical examples.

Multifluid simulations often create volume fraction data, representing fluid volumes per region or cell of a fluid data set. Accurate and visually realistic extraction of fluid boundaries is a challenging and essential task for efficient analysis of multifluid data. In this work, we present a new material interface reconstruction method for such volume fraction data. Within each cell of the data set, our method utilizes a gradient field approximation based on trilinearly blended Coons-patches to generate a volume fraction function, representing the change in volume fractions over the cells. A continuously varying isovalue field is applied to this function to produce a smooth interface that preserves the given volume fractions well. Further, the method allows user-controlled balance between volume accuracy and physical plausibility of the interface. The method works on two- and three-dimensional Cartesian grids, and handles multiple materials. Calculations are performed locally and utilize only the one-ring of cells surrounding a given cell, allowing visualizations of the material interfaces to be easily generated on a GPU or in a large-scale distributed parallel environment. Our results demonstrate the robustness, accuracy, and flexibility of the developed algorithms.

Characterizing the interplay between the vortices and forces acting on a wind turbine's blades in a qualitative and quantitative way holds the potential for significantly improving large wind turbine design. This paper introduces an integrated pipeline for highly effective wind and force field analysis and visualization. We extract vortices induced by a turbine's rotation in a wind field, and characterize vortices in conjunction with numerically simulated forces on the blade surfaces as these vortices strike another turbine's blades downstream. The scientifically relevant issue to be studied is the relationship between the extracted, approximate locations on the blades where vortices strike the blades and the forces that exist in those locations. This integrated approach is used to detect and analyze turbulent flow that causes local impact on the wind turbine blade structure. The results that we present are based on analyzing the wind and force field data sets generated by numerical simulations, and allow domain scientists to relate vortex-blade interactions with power output loss in turbines and turbine life expectancy. Our methods have the potential to improve turbine design to save costs related to turbine operation and maintenance.

Material interfaces and free surfaces are a topic of increasing interest in the field of computational fluid dynamics. In parts, reconstructed interfaces from such multi-fluid simulations behave like classic integral surfaces as known in the visualization community, while other regions of the surface undergo topological changes or behave orthogonally to what is expected by the underlying flow field. Thus, the analysis of the flow field in connection with material interface shape and topology is a challenging task. We develop a technique that facilitates visualization and analysis of such complex material interface behavior over time. For this matter, we track a surface parametrization of time-varying material interfaces and identify locations of interaction between material interfaces and fluid particles. Splatting and surface visualization techniques produce an intuitive representation of the derived interface stability. Our results demonstrate, how the interaction of the flow field with the material interface can be highlighted by appropriate extraction and visualization techniques and how the developed techniques can aid analysis of mixing and material interface consistency.

Many flow visualization techniques, especially integration-based methods, are problematic when the measured data exhibit noise and discretization issues. Particularly, this is the case for flow-sensitive phase-contrast magnetic resonance imaging (PC-MRI) data sets which not only record anatomic information, but also time-varying flow information. We propose a novel approach for the visualization of such data sets using integration-based methods. Our ideas are based upon finite-time Lyapunov exponents (FTLE) and enable identification of vessel boundaries in the data as high regions of separation. This allows us to correctly restrict integration-based visualization to blood vessels. We validate our technique by comparing our approach to existing anatomy-based methods as well as addressing the benefits and limitations of using FTLE to restrict flow. We also discuss the importance of parameters, i.e., advection length and data resolution, in establishing a well-defined vessel boundary. We extract appropriate flow lines and surfaces that enable the visualization of blood flow within the vessels. We further enhance the visualization by analyzing flow behavior in the seeded region and generating simplified depictions.

Integral flow surfaces constitute a widely used flow visualization tool due to their capability to convey important flow information such as fluid transport, mixing, and domain segmentation. Current flow surface rendering techniques limit their expressiveness, however, by focusing virtually exclusively on displacement visualization, visually neglecting the more complex notion of deformation such as shearing and stretching that is central to the field of continuum mechanics. To incorporate this information into the flow surface visualization and analysis process, we derive a metric tensor field that encodes local surface deformations as induced by the velocity gradient of the underlying flow field. We demonstrate how properties of the resulting metric tensor field are capable of enhancing present surface visualization and generation methods and develop novel surface querying, sampling, and visualization techniques. The provided results show how this step towards unifying classic flow visualization and more advanced concepts from continuum mechanics enables more detailed and improved flow analysis.

A fundamental characteristic of fluid flow is that it causes mixing: introduce a dye into a flow, and it will disperse. Mixing can be used as a method to visualize and characterize flow. Because mixing is a process that occurs over time, it is a 4D problem that presents a challenge for computation, visualization, and analysis. Motivated by a mixing problem in geophysics, we introduce a combination of methods to analyze, transform, and finally visualize mixing in simulations of convection in a self-gravitating 3D spherical shell representing convection in the Earth's mantle. Geophysicists use tools such as the finite element model CitcomS to simulate convection, and introduce massless, passive tracers to model mixing. The output of geophysical flow simulation is hard to analyze for domain experts because of overall data size and complexity. In addition, information overload and occlusion are problems when visualizing a whole-earth model. To address the large size of the data, we rearrange the simulation data using intelligent indexing for fast file access and efficient caching. To address information overload and interpret mixing, we compute tracer concentration statistics, which are used to characterize mixing in mantle convection models. Our visualization uses a specially tailored version of Direct Volume Rendering. The most important adjustment is the use of constant opacity. Because of this special area of application, i. e. the rendering of a spherical shell, many computations for volume rendering can be optimized. These optimizations are essential to a smooth animation of the time-dependent simulation data. Our results show how our system can be used to quickly assess the simulation output and test hypotheses regarding Earth's mantle convection. The integrated processing pipeline helps geoscientists to focus on their main task of analyzing mantle homogenization.

Streamline computation in a very large vector field data set represents a significant challenge due to the nonlocal and data-dependent nature of streamline integration. In this paper, we conduct a study of the performance characteristics of hybrid parallel programming and execution as applied to streamline integration on a large, multicore platform. With multicore processors now prevalent in clusters and supercomputers, there is a need to understand the impact of these hybrid systems in order to make the best implementation choice. We use two MPI-based distribution approaches based on established parallelization paradigms, parallelize over seeds and parallelize over blocks, and present a novel MPI-hybrid algorithm for each approach to compute streamlines. Our findings indicate that the work sharing between cores in the proposed MPI-hybrid parallel implementation results in much improved performance and consumes less communication and I/O bandwidth than a traditional, nonhybrid distributed implementation.

Driven by the ability to generate ever-larger, increasingly complex data, there is an urgent need in the scientific community for scalable analysis methods that can rapidly identify salient trends in scientific data. Query-Driven Visualization (QDV) strategies are among the small subset of techniques that can address both large and highly complex data sets. This paper extends the utility of QDV strategies with a statistics-based framework that integrates nonparametric distribution estimation techniques with a new segmentation strategy to visually identify statistically significant trends and features within the solution space of a query. In this framework, query distribution estimates help users to interactively explore their query's solution and visually identify the regions where the combined behavior of constrained variables is most important, statistically, to their inquiry. Our new segmentation strategy extends the distribution estimation analysis by visually conveying the individual importance of each variable to these regions of high statistical significance. We demonstrate the analysis benefits these two strategies provide and show how they maybe used to facilitate the refinement of constraints over variables expressed in a user's query. We apply our method to data sets from two different scientific domains to demonstrate its broad applicability.

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.

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.

Integral surfaces are ideal tools to illustrate vector fields and fluid flow structures. However, these surfaces can be visually complex and exhibit difficult geometric properties, owing to strong stretching, shearing and folding of the flow from which they are derived. Many techniques for non-photorealistic rendering have been presented previously. It is, however, unclear how these techniques can be applied to integral surfaces. In this paper, we examine how transparency and texturing techniques can be used with integral surfaces to convey both shape and directional information. We present a rendering pipeline that combines these techniques aimed at faithfully and accurately representing integral surfaces while improving visualization insight. The presented pipeline is implemented directly on the GPU, providing real-time interaction for all rendering modes, and does not require expensive preprocessing of integral surfaces after computation.

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 We present a software system that enables path‐traced rendering of complex scenes. The system consists of two primary components: an application layer that implements the basic rendering algorithm, and an out‐of‐core scheduling and data‐management layer designed to assist the application layer in exploiting hybrid computational resources (e.g., CPUs and GPUs) simultaneously. We describe the basic system architecture, discuss design decisions of the system's data‐management layer, and outline an efficient implementation of a path tracer application, where GPUs perform functions such as ray tracing, shadow tracing, importance‐driven light sampling, and surface shading. The use of GPUs speeds up the runtime of these components by factors ranging from two to twenty, resulting in a substantial overall increase in rendering speed. The path tracer scales well with respect to CPUs, GPUs and memory per node as well as scaling with the number of nodes. The result is a system that can render large complex scenes with strong performance and scalability.

Time and streak surfaces are ideal tools to illustrate time-varying vector fields since they directly appeal to the intuition about coherently moving particles. However, efficient generation of high-quality time and streak surfaces for complex, large and time-varying vector field data has been elusive due to the computational effort involved. In this work, we propose a novel algorithm for computing such surfaces. Our approach is based on a decoupling of surface advection and surface adaptation and yields improved efficiency over other surface tracking methods, and allows us to leverage inherent parallelization opportunities in the surface advection, resulting in more rapid parallel computation. Moreover, we obtain as a result of our algorithm the entire evolution of a time or streak surface in a compact representation, allowing for interactive, high-quality rendering, visualization and exploration of the evolving surface. Finally, we discuss a number of ways to improve surface depiction through advanced rendering and texturing, while preserving interactivity, and provide a number of examples for real-world datasets and analyze the behavior of our algorithm on them.

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.

Abstract We present an unbiased method for generating caustic lighting using importance sampled Path Tracing with Caustic Forecasting. Our technique is part of a straightforward rendering scheme which extends the Illumination by Weak Singularities method to allow for fully unbiased global illumination with rapid convergence. A photon shooting preprocess, similar to that used in Photon Mapping, generates photons that interact with specular geometry. These photons are then clustered, effectively dividing the scene into regions which will contribute similar amounts of caustic lighting to the image. Finally, the photons are stored into spatial data structures associated with each cluster, and the clusters themselves are organized into a spatial data structure for fast searching. During rendering we use clusters to decide the caustic energy importance of a region, and use the local photons to aid in importance sampling, effectively reducing the number of samples required to capture caustic lighting.

Abstract The notions of Finite‐Time Lyapunov Exponent (FTLE) and Lagrangian Coherent Structures provide a strong framework for the analysis and visualization of complex technical flows. Their definition is simple and intuitive, and they are built on a deep theoretical foundation. We apply these concepts to enable the analysis of flows in the immediate vicinity of the boundaries of flow‐embedded objects by limiting the Lagrangian analysis to surfaces closely neighboring these boundaries. To this purpose, we present an approach to approximate FTLE fields over such surfaces. Furthermore, we achieve an effective depiction of boundary‐related flow structures such as separation and attachment over object boundaries and specific insight into the surrounding flow using several specifically chosen visualization techniques. We document the applicability of our methods by presenting a number of application examples.

We present a practical approach to generate stochastic anisotropic samples with Poisson-disk characteristic over a two-dimensional domain. In contrast to isotropic samples, we understand anisotropic samples as non-overlapping ellipses whose size and density match a given anisotropic metric. Anisotropic noise samples are useful for many visualization and graphics applications. The spot samples can be used as input for texture generation, e.g., line integral convolution (LIC), but can also be used directly for visualization. The definition of the spot samples using a metric tensor makes them especially suitable for the visualization of tensor fields that can be translated into a metric. Our work combines ideas from sampling theory and mesh generation. To generate these samples with the desired properties we construct a first set of non-overlapping ellipses whose distribution closely matches the underlying metric. This set of samples is used as input for a generalized anisotropic Lloyd relaxation to distribute noise samples more evenly. Instead of computing the Voronoi tessellation explicitly, we introduce a discrete approach which combines the Voronoi cell and centroid computation in one step. Our method supports automatic packing of the elliptical samples, resulting in textures similar to those generated by anisotropic reaction-diffusion methods. We use Fourier analysis tools for quality measurement of uniformly distributed samples. The resulting samples have nice sampling properties, for example, they satisfy a blue noise property where low frequencies in the power spectrum are reduced to a minimum.

We present a novel approach for the direct computation of integral surfaces in time-dependent vector fields. As opposed to previous work, which we analyze in detail, our approach is based on a separation of integral surface computation into two stages: surface approximation and generation of a graphical representation. This allows us to overcome several limitations of existing techniques. We first describe an algorithm for surface integration that approximates a series of time lines using iterative refinement and computes a skeleton of the integral surface. In a second step, we generate a well-conditioned triangulation. Our approach allows a highly accurate treatment of very large time-varying vector fields in an efficient, streaming fashion. We examine the properties of the presented methods on several example datasets and perform a numerical study of its correctness and accuracy. Finally, we investigate some visualization aspects of integral surfaces.

The visualization and analysis of AMR-based simulations is integral to the process of obtaining new insight in scientific research. We present a new method for performing query-driven visualization and analysis on AMR data, with specific emphasis on time-varying AMR data. Our work introduces a new method that directly addresses the dynamic spatial and temporal properties of AMR grids that challenge many existing visualization techniques. Further, we present the first implementation of query-driven visualization on the GPU that uses a GPU-based indexing structure to both answer queries and efficiently utilize GPU memory. We apply our method to two different science domains to demonstrate its broad applicability.

We consider the problem of generating a map between two triangulated meshes, M and M', with arbitrary and possibly differing genus. This problem has rarely been tackled in its generality. Early schemes considered only topological spheres. Recent algorithms allow inputs with an arbitrary number of tunnels but require M and M' to have equal genus, mapping tunnel to tunnel. Other schemes which allow more general inputs are not guaranteed to work and the authors do not provide a characterization of the input meshes that can be processed successfully. Moreover, the techniques have difficulty dealing with coarse meshes with many tunnels. In this paper we present the first robust approach to build a map between two meshes of arbitrary unequal genus. We also provide a simplified method for setting the initial alignment between M and M', reducing reliance on landmarks and allowing the user to select "landmark tunnels" in addition to the standard landmark vertices. After computing the map, we automatically derive a continuous deformation from M to M' using a variational implicit approach to describe the evolution of non-landmark tunnels. Overall, we achieve a cross parameterization scheme that is provably robust in the sense that it can mapM toM' without constraints on their relative genus or on the density of the triangulation with respect to the number of tunnels. To demonstrate the practical effectiveness of our scheme we provide a number of examples of inter-surface parameterizations between meshes of different genus and shape.

We present a method for generating procedural volumetric fire in real time. By combining curve-based volumetric free-form deformation, hardware-accelerated volumetric rendering and Improved Perlin Noise or M-Noise we are able to render a vibrant and uniquely animated volumetric fire that supports bi-directional environmental macro-level interactivity. Our system is easily customizable by content artists. The fire is animated both on the macro and micro levels. Macro changes are controlled either by a prescripted sequence of movements, or by a realistic particle simulation that takes into account movement, wind, high-energy particle dispersion and thermal buoyancy. Micro fire effects such as individual flame shape, location, and flicker are generated in a pixel shader using three- to four-dimensional Improved Perlin Noise or M-Noise (depending on hardware limitations and performance requirements). Our method supports efficient collision detection, which, when combined with a sufficiently intelligent particle simulation, enables real-time bi-directional interaction between the fire and its environment. The result is a three-dimensional procedural fire that is easily designed and animated by content artists, supports dynamic interaction, and can be rendered in real time.

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.

Our ability to generate ever-larger, increasingly-complex data, has established the need for scalable methods that identify, and provide insight into, important variable trends and interactions. Query-driven methods are among the small subset of techniques that are able to address both large and highly complex datasets. This paper presents a new method that increases the utility of query-driven techniques by visually conveying statistical information about the trends that exist between variables in a query. In this method, correlation fields, created between pairs of variables, are used with the cumulative distribution functions of variables expressed in a user's query. This integrated use of cumulative distribution functions and correlation fields visually reveals, with respect to the solution space of the query, statistically important interactions between any three variables, and allows for trends between these variables to be readily identified. We demonstrate our method by analyzing interactions between variables in two flame-front simulations.

We present a novel approach to out-of-core time-varying isosurface visualization. We attempt to interactively visualize time-varying datasets which are too large to fit into main memory using a technique which is dramatically different from existing algorithms. Inspired by video encoding techniques, we examine the data differences between time steps to extract isosurface information. We exploit span space extraction techniques to retrieve operations necessary to update isosurface geometry from neighboring time steps. Because only the changes between time steps need to be retrieved from disk, I/O bandwidth requirements are minimized. We apply temporal compression to further reduce disk access and employ a point-based previewing technique that is refined in idle interaction cycles. Our experiments on computational simulation data indicate that this method is an extremely viable solution to large time-varying isosurface visualization. Our work advances the state-of-the-art by enabling all isosurfaces to be represented by a compact set of operations.

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.

In this work, we visualize high-dimensional particle simulation data using a suite of scatterplot-based visualizations coupled with interactive selection tools. We use traditional 2D and 3D projection scatterplots as well as a novel oriented-disk rendering style to convey various information about the data. Interactive selection tools allow physicists to manually classify "interesting" sets of particles that are highlighted across multiple, linked views of the data. The power of our application is the ability to correspond new visual representations of the simulation data with traditional, well understood visualizations. This approach supports the interactive exploration of the high-dimensional space while promoting discovery of new particle behavior.

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.

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.

We present a higher-order approach to the extraction of isosurfaces from unstructured meshes. Existing methods use linear interpolation along each mesh edge to find isosurface intersections. In contrast, our method determines intersections by performing barycentric interpolation over diamonds formed by the tetrahedra incident to each edge. Our method produces smoother, more accurate isosurfaces. Additionally, interpolating over diamonds, rather than linearly interpolating edge endpoints. enables us to identify up to two isosurface intersections per edge. This paper details how our new technique extracts isopoints, and presents a simple connection strategy for forming a triangle mesh isosurface.

A shell map is a bijective mapping between shell space and texture space that can be used to generate small-scale features on surfaces using a variety of modeling techniques. The method is based upon the generation of an offset surface and the construction of a tetrahedral mesh that fills the space between the base surface and its offset. By identifying a corresponding tetrahedral mesh in texture space, the shell map can be implemented through a straightforward barycentric-coordinate map between corresponding tetrahedra. The generality of shell maps allows texture space to contain geometric objects, procedural volume textures, scalar fields, or other shell-mapped objects.

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.

Transfer functions are a standard technique used in volume rendering to assign color and opacity to a volume of a scalar field. Multidimensional transfer functions (MDTFs) have proven to be an effective way to extract specific features with subtle properties. As 3D texture-based methods gain widespread popularity for the visualization of steady and unsteady flow field data, there is a need to define and apply similar MDTFs to interactive 3D flow visualization. We exploit flow field properties such as velocity, gradient, curl, helicity, and divergence using vector calculus methods to define an MDTF that can be used to extract and track features in a flow field. We show how the defined MDTF can be applied to interactive 3D flow visualization by combining them with state-of-the-art texture-based flow visualization of steady and unsteady fields. We demonstrate that MDTFs can be used to help alleviate the problem of occlusion, which is one of the main inherent drawbacks of 3D texture-based flow visualization techniques. In our implementation, we make use of current graphics hardware to obtain interactive frame rates.

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.

The physical interpretation of mathematical features of tensor fields is highly application-specific. Existing visualization methods for tensor fields only cover a fraction of the broad application areas. We present a visualization method tailored specifically to the class of tensor field exhibiting properties similar to stress and strain tensors, which are commonly encountered in geomechanics. Our technique is a global method that represents the physical meaning of these tensor fields with their central features: regions of compression or expansion. The method is based on two steps: first, we define a positive definite metric, with the same topological structure as the tensor field; second, we visualize the resulting metric. The eigenvector fields are represented using a texture-based approach resembling line integral convolution (LIC) methods. The eigenvalues of the metric are encoded in free parameters of the texture definition. Our method supports an intuitive distinction between positive and negative eigenvalues. We have applied our method to synthetic and some standard data sets, and "real" data from earth science and mechanical engineering application.

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.

We present a new method for topological segmentation in steady three-dimensional vector fields. Depending on desired properties, the algorithm replaces the original vector field by a derived segmented data set, which is utilized to produce separating surfaces in the vector field. We define the concept of a segmented data set, develop methods that produce the segmented data by sampling the vector field with streamlines, and describe algorithms that generate the separating surfaces. This method is applied to generate local separatrices in the field, defined by a movable boundary region placed in the field. The resulting partitions can be visualized using standard techniques for a visualization of a vector field at a higher level of abstraction.

We present a new approach to isosurface visualization that we call "iso-splatting." We use point primitives for representing and rendering isosurfaces. The method consists of two steps. In the first step, point samples are generated throughout the volumetric domain of a scalar function. In the second step, these points are projected onto the isosurface of interest. We render the resulting point set using a surface splatting algorithm. The method can be extended to out-of-core or parallel environments. Our results show that this method can offer much greater time and space efficiency when compared with standard triangle-based methods, thereby supporting higher levels of interactivity. Parts of the algorithm can be accelerated using graphics hardware. One key advantage of this approach is that, since extraction computations are divided into two smaller phases, work can be distributed to exploit all available resources.

We present a method to represent unstructured scalar fields at multiple levels of detail. Using a parallelizable classification algorithm to build a cluster hierarchy, we generate a multiresolution representation of a given volumetric scalar data set. The method uses principal component analysis (PCA) for cluster generation and a fitting technique based on radial basis functions (RBFs). Once the cluster hierarchy has been generated, we utilize a variety of techniques for extracting different levels of detail. The main strength of this work is its generality. Regardless of grid type, this method can be applied to any discrete scalar field representation, even one given as a "point cloud".

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.

Volume visualization of large data sets suffers from the same problem that many other visualization modalities suffer from: either one can visualize the entire data set and lose small details or visualize a small region and lose the context. The authors we present a magnification lens technique for volume visualization. While the notion of a magnification-lens is not new, and other techniques attempt to simulate the physical properties of a magnifying lens, our contribution is in developing a magnification lens that is fast, can be implemented using a fairly small software overhead, and has a natural, intuitive appearance. The issue with magnification lens is the border, or transition region. The lens center and exterior have a constant zoom factor, and are simple to render. It is the border region that blends between the external and interior magnification, and has a nonconstant magnification. We use the "perspective-correct textures" capability, available in most current graphics systems, to produce a lens with a tessellated border region that approximates linear compression with respect to the radius of the magnification lens. We discuss how a "cubic" border can mitigate the discontinuities resulting from the use of a linear function, without significant performance loss. We discuss various issues concerning development of a three-dimensional magnification lens.

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.

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 the theory and the algorithm. The stream surfaces are ruled surfaces inside each cell, and their construction starts with line segments on the faces. Our method supports the analysis of velocity fields resulting from computational fluid dynamics (CFD) simulations.

Real-time visualization of particle traces in virtual environments can aid in the exploration and analysis of complex three dimensional vector fields. This paper introduces a scalable method suitable for the interactive visualization of large time-varying vector fields on commodity hardware. A real-time data streaming and visualization approach and its out-of-core scheme for the pre-processing and rendering of data are described. The presented approach yields low-latency application start-up times and small memory footprints. A proof of concept systems was implemented on a low-cost Linux workstation equipped with spatial tracking hardware, data gloves and shutter glasses. The system was used to implement a virtual wind tunnel in which a volumetric particle injector can introduce up to 60000 particles into the flow field while an interactive rendering performance of 60 frames per second is maintained.

We present a new approach for reconstructing a smooth surface from a set of scattered points in 3D space. Our algorithm first decomposes a given point set into a quadtree-like data structure known as a strip tree. The strip tree is used to fit a set of least squares quadratic surfaces to the data points. These quadratic surfaces are then degree-elevated to bi-cubic surfaces and blended together to form a set of B-spline surfaces that approximates the given point set.

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 rank deficiency 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 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.

Consider a triangulation of the xy plane, and a general surface z=f(x, y). 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. 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 surface to establish an edge-flipping criterion for a convex quadrilateral that enables us to minimize the error between the surface and the triangulation.

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.

Presents a method for the hierarchical representation of vector fields. Our approach is based on iterative refinement using clustering and principal component analysis. The input to our algorithm is a discrete set of points with associated vectors. The algorithm generates a top-down segmentation of the discrete field by splitting clusters of points. We measure the error of the various approximation levels by measuring the discrepancy between streamlines generated by the original discrete field and its approximations based on much smaller discrete data sets. Our method assumes no particular structure of the field, nor does it require any topological connectivity information. It is possible to generate multi-resolution representations of vector fields using this approach.

We present a multiresolution technique for interactive texture-based volume visualization of very large data sets. This method uses an adaptive scheme that renders the volume in a region-of-interest at a high resolution and the volume away from this region at progressively lower resolutions. The algorithm is based on the segmentation of texture space into an octree, where the leaves of the tree define the original data and the internal nodes define lower-resolution versions. Rendering is done adaptively by selecting high-resolution cells close to a center of attention and low-resolution cells away from this area. We limit the artifacts introduced by this method by modifying the transfer functions in the lower-resolution data sets and utilizing spherical shells as a proxy geometry. It is possible to use this technique to produce viewpoint-dependent renderings of very large data sets.

Animation and visualization of rectilinear data require interpolation schemes for smooth image generation. Piecewise trilinear interpolation, the de facto standard for interpolating rectilinear data, usually leads to significant visual artifacts in the resulting imagery. These artifacts reduce the confidence in the resulting visualization and may even lead to false interpretations of the data. This paper is concerned with the generation of smooth isosurface image sequences, obtained by casting rays through the image plane and computing their intersections with an isosurface. We describe a novel solution to this problem: we replace trilinear interpolation by tricubic interpolation, smoothing out the artifacts in the images; and we simplify the ray–isosurface intersection calculations by rotating and resampling the original rectilinear data in a second rectilinear grid—a grid with one family of grid planes parallel to the image plane. Our solution significantly reduces artifacts in individual images and leads to smooth animations. Copyright © 1999 John Wiley & Sons, Ltd.

Presents a method for the construction of multiple levels of tetrahedral meshes approximating a trivariate scalar-valued function at different levels of detail. Starting with an initial, high-resolution triangulation of a 3D region, we construct coarser representation levels by collapsing edges of the mesh. Each triangulation defines a linear spline function, where the function values associated with the vertices are the spline coefficients. Error bounds are stored for individual tetrahedra and are updated as the mesh is simplified. Two algorithms are presented that simplify the mesh within prescribed error bounds. Each algorithm treats simplification on the mesh boundary. The result is a hierarchical data description that is suited for the efficient visualization of large data sets at varying levels of detail.

The authors investigate methods by which successive approximations to a sphere can be generated from polyhedra. Each approximation can be obtained by bevel-cutting each edge of the previous approximation with a plane tangent to the sphere. They show that each member of the sequence of polyhedra can be associated with a Voronoi tessellation of the sphere. Under this formulation, the bevel-cutting operation can be defined by the insertion of points into the Voronoi tessellation. The algorithm is defined such that affine combinations of the polyhedra will converge to affine operations of the sphere. The method is useful as a modeling operation and as a level-of-detail representation for a sphere.

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 present a method to produce a hierarchy of triangle meshes that can be used to blend different levels of detail in a smooth fashion. The algorithm produces a sequence of meshes M/sub 0/, M/sub 1/, M/sub 2/..., M/sub n/, where each mesh M/sub i/ can be transformed to mesh M/sub i+1/ through a set of triangle-collapse operations. For each triangle, a function is generated that approximates the underlying surface in the area of the triangle, and this function serves as a basis for assigning a weight to the triangle in the ordering operation and for supplying the points to which the triangles are collapsed. The algorithm produces a limited number of intermediate meshes by selecting, at each step, a number of triangles that can be collapsed simultaneously. This technique allows us to view a triangulated surface model at varying levels of detail while insuring that the simplified mesh approximates the original surface well.

Presents a new method to produce a hierarchical set of triangle meshes that can be used to blend different levels of detail in a smooth fashion. The algorithm produces a sequence of meshes /spl Mscr//sub 0/, /spl Mscr//sub 1/, /spl Mscr//sub 2/..., /spl Mscr//sub n/, where each mesh /spl Mscr//sub i/ can be transformed to mesh /spl Mscr//sub i+1/ through a set of triangle-collapse operations. For each triangle, a function is generated that approximates the underlying surface in the area of the triangle, and this function serves as a basis for assigning a weight to the triangle in the ordering operation, and for supplying the point to which the triangles are collapsed. This technique allows us to view a triangulated surface model at varying levels of detail while insuring that the simplified mesh approximates the original surface well.

Article Free Access Share on Free-form deformations with lattices of arbitrary topology Authors: Ron MacCracken Computer Graphics Research Laboratory, Department of Computer Science, University of California, Davis CA Computer Graphics Research Laboratory, Department of Computer Science, University of California, Davis CAView Profile , Kenneth I. Joy Computer Graphics Research Laboratory, Department of Computer Science, University of California, Davis CA Computer Graphics Research Laboratory, Department of Computer Science, University of California, Davis CAView Profile Authors Info & Claims SIGGRAPH '96: Proceedings of the 23rd annual conference on Computer graphics and interactive techniquesAugust 1996 Pages 181–188https://doi.org/10.1145/237170.237247Published:01 August 1996Publication History 259citation2,604DownloadsMetricsTotal Citations259Total Downloads2,604Last 12 Months124Last 6 weeks32 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper describes a graphical interface for application programs. The interface is based on the notion of a control panel. A control panel contains a browsable list of an application's parameters and a set of functions to control the application's execution. A variety of graphical knobs and gauges may be associated with any or all of the parameters to permit fine-grain execution control, including animation of an application's output. The control panel interface is integrated into the framework of an interactive programming environment for graphics and image processing applications. This integration is an important feature of the overall interface design.

A new algorithm for ray tracing parametric surface patches is presented. The method uses quasi-Newton iteration to solve for the ray/surface intersection and utilizes ray-to-ray coherence by using numerical information from adjoining rays as initial approximations to the quasi-Newton algorithm. Techniques based upon object space subdivision are used to insure convergence to the correct interesection point. Examples are given of the use of the algorithm in scenes containing Bézier surface patches. Results show that a significant number of ray/surface intersections on these parametric surface patches can be found using very few iterations, giving a significant computational savings.