Abstract The goal of visual surface inspection is to analyze an object’s surface and detect defects by looking at it from different angles. Developments over the past years have made it possible to partially automate this process. Inspection systems use robots to move cameras and obtain pictures that are evaluated by image processing algorithms. Setting up these systems or adapting them to new models is primarily done manually. A key challenge is to define camera viewpoints from which the images are taken. The number of viewpoints should be as low as possible while still guaranteeing an inspection of the desired quality. System engineers define and evaluate configurations that are improved based on a time-consuming trial-and-error process leading to a sufficient, but not necessarily optimal, configuration. With the availability of 3D surface models defined by triangular meshes, this step can be done virtually. This paper presents a new scalable approach to determine a small number of well-placed camera viewpoints for optical surface inspection planning. The initial model is approximated by B-spline surfaces. A set of geometric feature functionals is defined and used for an adaptive, non-uniform surface sampling that is sparse in geometrically low-complexity areas and dense in regions of higher complexity. The presented approach is applicable to solid objects with a given 3D surface model. It makes camera viewpoint generation independent of the resolution of the triangle mesh, and it improves previous results considering number of viewpoints and their relevance.

Computer-aided cell nuclei segmentation in histology images is essential for image analysis. There is a demand for methods that accurately detect cell nuclei in large images. We introduce the FECS method for automatic cell nuclei segmentation in Hematoxylin and Eosin (H&E) stained histology images. Our method accurately segments cell nuclei, even in large images, efficiently. We use bimodal-like histograms to perform image binarization via the fast Otsu algorithm. We introduce a super-pixel based filter for cell nuclei boundary detection. A Gaussian blur filter allows us to identify cell nuclei centers, which are understood as local minima in the individual cell nuclei regions. We have evaluated our method for two publicly available datasets. Out tests have produced average Jaccard index values of 0.963 and 0.914, respectively, supporting a high degree of segmentation accuracy. We have compared our method against a state-of-the-art method; our method produced better results for both datasets. The average processing time of FECS was approximately just one second for images of 1k x 1k pixel resolution and about three minutes for larger images of 15k x 15k pixel resolution.

We introduce an interactive method for retina layer segmentation in gray-level and RGB images based on super-pixels, multi-level optimization of modularity, and boundary erosion. Our method produces highly accurate segmentation results and can segment very large images. We have evaluated our method with two datasets of 2D confocal microscopy (CM) images of a mammalian retina.We have obtained average Jaccard index values of 0.948 and 0.942 respectively, confirming the high-quality segmentation performance of our method relative to a known ground truth segmentation. Average processing time was two seconds.

Airway-centered Interstitial Fibrosis (ACIF) is a histological pattern of Interstitial lung diseases. Its diagnosis requires a multidisciplinary approach, in which diverse information, such as clinical data, computed tomography data, and lung biopsy data, is analyzed. Biopsy samples are digitized at high-resolution. Of crucial interest are broncho-and bronchiolocentric remodeling with extracellular matrix deposition. To analyze an image, specialists have to explore it at low microscope magnification, select a region of interest and export a smaller specified sub-image to be interpreted at higher magnification. This process is performed several times, requiring hours, becoming a tiresome task. We propose a method to support pathologists to identify specific patterns of ACIF in high-resolution images from lung biopsies. This can be done by a) automatic microscope magnification reduction; b) computing the probability of pixels belonging to high-density regions; c) extracting Local Binary Patterns (LBP) of the high-and low-density regions; and d) visualizing them in color. We have evaluated our method on nine high-resolution lung biopsies. We have tested the LBP features of high-and low-density regions with the kNN algorithm and obtained a classification accuracy of 94.4%, which is the highest one reported in the literature for this type of data.

Many applications are dealing with geometric data that are affected by uncertainty. This uncertainty is important to analyze, visualize, and understand. We present a methodology to model uncertain geometry based on multi-variate normal distributions. In addition, we propose a visualization technique to represent a hull for uncertain geometry capturing a user-defined percentage of the underlying uncertain geometry. To show the effectiveness of our approach, we have modeled and visualized uncertain datasets from different applications.

We describe a specialized methodology for segmenting 2D microscopy digital images of freshwater green microalgae. The goal is to obtain representative algae shapes to extract morphological features to be employed in a posterior step of taxonomical classification of the species. The proposed methodology relies on the seeded region growing principle and on a fine-tuned filtering preprocessing stage to smooth the input image. A contrast enhancement process then takes place to highlight algae regions on a binary pre-segmentation image. This binary image is also employed to determine where to place the seed points and to estimate the statistical probability distributions that characterize the target regions, i.e., the algae areas and the background, respectively. These preliminary stages produce the required information to set the homogeneity criterion for region growing. We evaluate the proposed methodology by comparing its resulting segmentations with a set of corresponding ground-truth segmentations (provided by an expert biologist) and also with segmentations obtained with existing strategies. The experimental results show that our solution achieves highly accurate segmentation rates with greater efficiency, as compared with the performance of standard segmentation approaches and with an alternative previous solution, based on level-sets, also specialized to handle this particular problem.

Memory performance is often a major bottleneck for high-performance computing (HPC) applications. Deepening memory hierarchies, complex memory management, and non-uniform access times have made memory performance behavior difficult to characterize, and users require novel, sophisticated tools to analyze and optimize this aspect of their codes. Existing tools target only specific factors of memory performance, such as hardware layout, allocations, or access instructions. However, today's tools do not suffice to characterize the complex relationships between these factors. Further, they require advanced expertise to be used effectively. We present MemAxes, a tool based on a novel approach for analytic-driven visualization of memory performance data. MemAxes uniquely allows users to analyze the different aspects related to memory performance by providing multiple visual contexts for a centralized dataset. We define mappings of sampled memory access data to new and existing visual metaphors, each of which enabling a user to perform different analysis tasks. We present methods to guide user interaction by scoring subsets of the data based on known performance problems. This scoring is used to provide visual cues and automatically extract clusters of interest. We designed MemAxes in collaboration with experts in HPC and demonstrate its effectiveness in case studies.

We introduce a new approach for performing image inpainting, by devising an integrative method based on the superpixel segmentation technique and considering minimal user input. Image inpainting methods are concerned with filling in missing or replacing undesired regions in an image. Typically, inpainting methods consider and extrapolate known image data. Superpixels in the immediate neighborhood of the in-painting region are computed and used as source image data to fill in (or replace) the inpainting area. A user provides additional information by specifying line segments in the image to assist the otherwise automatic inpainting process, to ensure that only desirable superpixels are utilized when copying them into the inpainting region. User interaction is minimal, as it is merely necessary to specify a small number of line segments that define image parts to be used as source data in distinct inpainting regions. We provide experimental results demonstrating that our method performs well when compared against other methods, especially concerning the preservation of edges and texture in the inpainted regions.

Modern HPC centers comprise clusters, storage, networks, power and cooling infrastructure, and more. Analyzing the efficiency of these complex facilities is a daunting task. Increasingly, facilities deploy sensors and monitoring tools, but with millions of instrumented components, analyzing collected data manually is intractable. Data from an HPC center comprises different formats, granularities, and semantics, and handwritten scripts no longer suffice to transform the data into a digestible form.

BACKGROUND: There exists a need for effective and easy-to-use software tools supporting the analysis of complex Electrocorticography (ECoG) data. Understanding how epileptic seizures develop or identifying diagnostic indicators for neurological diseases require the in-depth analysis of neural activity data from ECoG. Such data is multi-scale and is of high spatio-temporal resolution. Comprehensive analysis of this data should be supported by interactive visual analysis methods that allow a scientist to understand functional patterns at varying levels of granularity and comprehend its time-varying behavior. RESULTS: We introduce a novel multi-scale visual analysis system, ECoG ClusterFlow, for the detailed exploration of ECoG data. Our system detects and visualizes dynamic high-level structures, such as communities, derived from the time-varying connectivity network. The system supports two major views: 1) an overview summarizing the evolution of clusters over time and 2) an electrode view using hierarchical glyph-based design to visualize the propagation of clusters in their spatial, anatomical context. We present case studies that were performed in collaboration with neuroscientists and neurosurgeons using simulated and recorded epileptic seizure data to demonstrate our system's effectiveness. CONCLUSION: ECoG ClusterFlow supports the comparison of spatio-temporal patterns for specific time intervals and allows a user to utilize various clustering algorithms. Neuroscientists can identify the site of seizure genesis and its spatial progression during various the stages of a seizure. Our system serves as a fast and powerful means for the generation of preliminary hypotheses that can be used as a basis for subsequent application of rigorous statistical methods, with the ultimate goal being the clinical treatment of epileptogenic zones.

We present Brain Modulyzer, an interactive visual exploration tool for functional magnetic resonance imaging (fMRI) brain scans, aimed at analyzing the correlation between different brain regions when resting or when performing mental tasks. Brain Modulyzer combines multiple coordinated views-such as heat maps, node link diagrams and anatomical views-using brushing and linking to provide an anatomical context for brain connectivity data. Integrating methods from graph theory and analysis, e.g., community detection and derived graph measures, makes it possible to explore the modular and hierarchical organization of functional brain networks. Providing immediate feedback by displaying analysis results instantaneously while changing parameters gives neuroscientists a powerful means to comprehend complex brain structure more effectively and efficiently and supports forming hypotheses that can then be validated via statistical analysis. To demonstrate the utility of our tool, we present two case studies-exploring progressive supranuclear palsy, as well as memory encoding and retrieval.

We present an analysis and visualization prototype using the concept of a flow topology graph (FTG) for characterization of flow in constrained networks, with a focus on discrete fracture networks (DFN), developed collaboratively by geoscientists and visualization scientists. Our method allows users to understand and evaluate flow and transport in DFN simulations by computing statistical distributions, segment paths of interest, and cluster particles based on their paths. The new approach enables domain scientists to evaluate the accuracy of the simulations, visualize features of interest, and compare multiple realizations over a specific domain of interest. Geoscientists can simulate complex transport phenomena modeling large sites for networks consisting of several thousand fractures without compromising the geometry of the network. However, few tools exist for performing higher-level analysis and visualization of simulated DFN data. The prototype system we present addresses this need. We demonstrate its effectiveness for increasingly complex examples of DFNs, covering two distinct use cases - hydrocarbon extraction from unconventional resources and transport of dissolved contaminant from a spent nuclear fuel repository.

Software-defined network/ing (SDN) is a novel configuration technique that has the potential to become the future backbone of computer networking. In contrast to conventional networking techniques, SDN utilizes controller elements to configure groups of networking nodes, resulting in a hierarchy. SDNs have to be simulated and analyzed to identify applicable configuration settings for real world applications. To determine the quality of a SDN configuration, its packet flow is an important indicator for the analysis. This work presents an interactive system for the analysis of SDN data. An intuitive overview of the SDN hierarchy and the underlying packet flow is provided. The ability to track packets through the SDN and to interlink multiple views of the SDN forms an interactive analysis tool that is successfully applied to a simulated SDN dataset.

Event traces are valuable for understanding the behavior of parallel programs. However, automatically analyzing a large parallel trace is difficult, especially without a specific objective. We aid this endeavor by extracting a trace's logical structure, an ordering of trace events derived from happened-before relationships, while taking into account developer intent. Using this structure, we can calculate an operation's delay relative to its peers on other processes. The logical structure also serves as a platform for comparing and clustering processes as well as highlighting communication patterns in a trace visualization. We present an algorithm for determining this idealized logical structure from traces of message passing programs, and we develop metrics to quantify delays and differences among processes. We implement our techniques in Ravel, a parallel trace visualization tool that displays both logical and physical timelines. Rather than showing the duration of each operation, we display where delays begin and end, and how they propagate. We apply our approach to the traces of several message passing applications, demonstrating the accuracy of our extracted structure and its utility in analyzing these codes.

Asynchrony and non-determinism in Charm++ programs present a significant challenge in analyzing their event traces. We present a new framework to organize event traces of parallel programs written in Charm++. Our reorganization allows one to more easily explore and analyze such traces by providing context through logical structure. We describe several heuristics to compensate for missing dependencies between events that currently cannot be easily recorded. We introduce a new task ordering that recovers logical structure from the non-deterministic execution order. Using the logical structure, we define several metrics to help guide developers to performance problems. We demonstrate our approach through two proxy applications written in Charm++. Finally, we discuss the applicability of this framework to other task-based runtimes and provide guidelines for tracing to support this form of analysis.

We introduce a new approach to automatically extract an idealized logical structure from a parallel execution trace. We use this structure to define intuitive metrics such as the lateness of a process involved in a parallel execution. By analyzing and illustrating traces in terms of logical steps, we leverage a developer's understanding of the happened-before relations in a parallel program. This technique can uncover dependency chains, elucidate communication patterns, and highlight sources and propagation of delays, all of which may be obscured in a traditional trace visualization.

Optimizing memory access is critical for performance and power efficiency. CPU manufacturers have developed sampling-based performance measurement units (PMUs) that report precise costs of memory accesses at specific addresses. However, this data is too low-level to be meaningfully interpreted and contains an excessive amount of irrelevant or uninteresting information. We have developed a method to gather fine-grained memory access performance data for specific data objects and regions of code with low overhead and attribute semantic information to the sampled memory accesses. This information provides the context necessary to more effectively interpret the data. We have developed a tool that performs this sampling and attribution and used the tool to discover and diagnose performance problems in real-world applications. Our techniques provide useful insight into the memory behaviour of applications and allow programmers to understand the performance ramifications of key design decisions: domain decomposition, multi-threading, and data motion within distributed memory systems.

With the continuous rise in complexity of modern supercomputers, optimizing the performance of large-scale parallel programs is becoming increasingly challenging. Simultaneously, the growth in scale magnifies the impact of even minor inefficiencies--potentially millions of compute hours and megawatts in power consumption can be wasted on avoidable mistakes or sub-optimal algorithms. This makes performance analysis and optimization critical elements in the software development process. One of the most common forms of performance analysis is to study execution traces, which record a history of per-process events and interprocess messages in a parallel application. Trace visualizations allow users to browse this event history and search for insights into the observed performance behavior. However, current visualizations are difficult to understand even for small process counts and do not scale gracefully beyond a few hundred processes. Organizing events in time leads to a virtually unintelligible conglomerate of interleaved events and moderately high process counts overtax even the largest display. As an alternative, we present a new trace visualization approach based on transforming the event history into logical time inferred directly from happened-before relationships. This emphasizes the code's structural behavior, which is much more familiar to the application developer. The original timing data, or other information, is then encoded through color, leading to a more intuitive visualization. Furthermore, we use the discrete nature of logical timelines to cluster processes according to their local behavior leading to a scalable visualization of even long traces on large process counts. We demonstrate our system using two case studies on large-scale parallel codes.

In reverse engineering and computer-aided design (CAD) applications point cloud data is usually manually scanned, reconstructed, and post-processed in separated steps. When point cloud data resulting from a scanning process do not satisfy certain necessary reconstruction requirements, one must perform scanning again to enable proper reconstruction. On-line reconstruction of 3d geometry allows one to generate and update a CAD reconstruction on-line during the scanning process with an hand-held laser scanner. Thus, regions where the scanned data is insufficient for the reconstruction are detected on the fly to allow an immediate correction and improvement of the scanned data. This enables the operator to focus on critical regions in the scanned data to improve the reconstruction quality. We present an on-line segmentation and on-line reconstruction of basic geometric primitives. The presented methods allow for a real-time processing of a point stream. They utilize data structures that can be updated at any time when additional data from the stream has to be processed. This data is used to complete and improve the segmentation and reconstruction during the scanning process.

Abstract Analysis of chemical constituents from mass spectrometry of aerosols involves non‐negative matrix factorization, an approximation of high‐dimensional data in lower‐dimensional space. The associated optimization problem is non‐convex, resulting in crude approximation errors that are not accessible to scientists. To address this shortcoming, we introduce a new methodology for user‐guided error‐aware data factorization that entails an assessment of the amount of information contributed by each dimension of the approximation, an effective combination of visualization techniques to highlight, filter, and analyze error features, as well as a novel means to interactively refine factorizations. A case study and the domain‐expert feedback provided by the collaborating atmospheric scientists illustrate that our method effectively communicates errors of such numerical optimization results and facilitates the computation of high‐quality data factorizations in a simple and intuitive manner.

ABSTRACT Playing the piano requires one to precisely position one's hand in order to strike particular combinations of keys at specific moments in time. This paper presents the first system for automatically generating three‐dimensional animations of piano performance, given an input midi music file. A graph theory‐based motion planning method is used to decide which set of fingers should strike the piano keys for each chord. As the progression of the music is anticipated, the positions of unused fingers are calculated to make possible efficient fingering of future notes. Initial key poses of the hands, including those for complex piano techniques such as crossovers and arpeggio, are determined on the basis of the finger positions and piano theory. An optimization method is used to refine these poses, producing a natural and minimal energy pose sequence. Motion transitions between poses are generated using a combination of sampled piano playing motion and music features, allowing the system to support different playing styles. Our approach is validated through direct comparison with actual piano playing and simulation of a complete music piece requiring various playing skills. Extensions of our system are discussed. Copyright © 2012 John Wiley & Sons, Ltd.

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.

Progressive refinement is a methodology that makes it possible to elegantly integrate scalable data compression, access, and presentation into one approach. Specifically, this paper concerns the effective use of progressive parallel coordinates (PPCs), utilized routinely for high-dimensional data visualization. It discusses how the power of the typical stages of progressive data visualization can also be utilized fully for PPCs. Further, different implementations of the underlying methods and potential application domains are described. The paper also presents empirical results concerning the benefits of PPC with regard to efficient data management and improved presentation, indicating that the proposed approach is able to close the gap between data handling and visualization.

Performance analysis of parallel scientific codes is becoming increasingly difficult due to the rapidly growing complexity of applications and architectures. Existing tools fall short in providing intuitive views that facilitate the process of performance debugging and tuning. In this paper, we extend recent ideas of projecting and visualizing performance data for faster, more intuitive analysis of applications. We collect detailed per-level and per-phase measurements for a dynamically load-balanced, structured AMR library and project per-core data collected in the hardware domain on to the application's communication topology. We show how our projections and visualizations lead to a rapid diagnosis of and mitigation strategy for a previously elusive scaling bottleneck in the library that is hard to detect using conventional tools. Our new insights have resulted in a 22% performance improvement for a 65,536-core run of the AMR library on an IBM Blue Gene/P system.

The placement of tasks in a parallel application on specific nodes of a supercomputer can significantly impact performance. Traditionally, this task mapping has focused on reducing the distance between communicating tasks on the physical network. This minimizes the number of hops that point-to-point messages travel and thus reduces link sharing between messages and contention. However, for applications that use collectives over sub-communicators, this heuristic may not be optimal. Many collectives can benefit from an increase in bandwidth even at the cost of an increase in hop count, especially when sending large messages. For example, placing communicating tasks in a cube configuration rather than a plane or a line on a torus network increases the number of possible paths messages might take. This increases the available bandwidth which can lead to significant performance gains. We have developed Rubik, a tool that provides a simple and intuitive interface to create a wide variety of mappings for structured communication patterns. Rubik supports a number of elementary operations such as splits, tilts, or shifts, that can be combined into a large number of unique patterns. Each operation can be applied to disjoint groups of processes involved in collectives to increase the effective bandwidth. We demonstrate the use of Rubik for improving performance of two parallel codes, pF3D and Qbox, which use collectives over sub-communicators.

Abstract The ocean contains many large‐scale, long‐lived vortices, called mesoscale eddies, that are believed to have a role in the transport and redistribution of salt, heat, and nutrients throughout the ocean. Determining this role, however, has proven to be a challenge, since the mechanics of eddies are only partly understood; a standard definition for these ocean eddies does not exist and, therefore, scientifically meaningful, robust methods for eddy extraction, characterization, tracking and visualization remain a challenge. To shed light on the nature and potential roles of eddies, we extend our previous work on eddy identification and tracking to construct a new metric to characterize the transfer of water into and out of eddies across their boundary, and produce several visualizations of this new metric to provide clues about the role eddies play in the global ocean.

The study of aerosol composition for air quality research involves the analysis of high-dimensional single particle mass spectrometry data. We describe, apply, and evaluate a novel interactive visual framework for dimensionality reduction of such data. Our framework is based on non-negative matrix factorization with specifically defined regularization terms that aid in resolving mass spectrum ambiguity. Thereby, visualization assumes a key role in providing insight into and allowing to actively control a heretofore elusive data processing step, and thus enabling rapid analysis meaningful to domain scientists. In extending existing black box schemes, we explore design choices for visualizing, interacting with, and steering the factorization process to produce physically meaningful results. A domain-expert evaluation of our system performed by the air quality research experts involved in this effort has shown that our method and prototype admits the finding of unambiguous and physically correct lower-dimensional basis transformations of mass spectrometry data at significantly increased speed and a higher degree of ease.

Scientific data sets generated by numerical simulations or experimental measurements often contain a substantial amount of noise. Smoothing the data removes noise but can have potentially drastic effects on the qualitative nature of the data, thereby influencing its characterization and visualization via topological analysis, for example. We propose a method to track topological changes throughout the smoothing process. As a preprocessing step, we oversmooth the data and collect a list of topological events, specifically the creation and destruction of extremal points. During rendering, it is possible to select the number of topological events by interactively manipulating a merging parameter. The result that a specific amount of smoothing has on the topology of the data is illustrated using a topology-derived transfer function that relates region connectivity of the smoothed data to the original regions of the unsmoothed data. This approach enables visual as well as quantitative analysis of the topological effects of smoothing.

Planetary topography is the result of complex interactions between geological processes, of which faulting is a prominent component. Surface-rupturing earthquakes cut and move landforms which develop across active faults, producing characteristic surface displacements across the fault. Geometric models of faults and their associated surface displacements are commonly applied to reconstruct these offsets to enable interpretation of the observed topography. However, current 2D techniques are limited in their capability to convey both the three-dimensional kinematics of faulting and the incremental sequence of events required by a given reconstruction. Here we present a real-time system for interactive retro-deformation of faulted topography to enable reconstruction of fault displacement within a high-resolution (sub 1m/pixel) 3D terrain visualization. We employ geometry shaders on the GPU to intersect the surface mesh with fault-segments interactively specified by the user and transform the resulting surface blocks in realtime according to a kinematic model of fault motion. Our method facilitates a human-in-the-loop approach to reconstruction of fault displacements by providing instant visual feedback while exploring the parameter space. Thus, scientists can evaluate the validity of traditional point-to-point reconstructions by visually examining a smooth interpolation of the displacement in 3D. We show the efficacy of our approach by using it to reconstruct segments of the San Andreas fault, California as well as a graben structure in the Noctis Labyrinthus region on Mars.

Gene expression and in vivo DNA binding data provide important information for understanding gene regulatory networks: in vivo DNA binding data indicate genomic regions where transcription factors are bound, and expression data show the output resulting from this binding. Thus, there must be functional relationships between these two types of data. While visualization and data analysis tools exist for each data type alone, there is a lack of tools that can easily explore the relationship between them. We propose an approach that uses the average expression driven by multiple of cis-control regions to visually relate gene expression and in vivo DNA binding data. We demonstrate the utility of this tool with examples from the network controlling early Drosophila development. The results obtained support the idea that the level of occupancy of a transcription factor on DNA strongly determines the degree to which the factor regulates a target gene, and in some cases also controls whether the regulation is positive or negative.

Abstract Studying transformation in a chemical system by considering its energy as a function of coordinates of the system's components provides insight and changes our understanding of this process. Currently, a lack of effective visualization techniques for high‐dimensional energy functions limits chemists to plot energy with respect to one or two coordinates at a time. In some complex systems, developing a comprehensive understanding requires new visualization techniques that show relationships between all coordinates at the same time. We propose a new visualization technique that combines concepts from topological analysis, multi‐dimensional scaling, and graph layout to enable the analysis of energy functions for a wide range of molecular structures. We demonstrate our technique by studying the energy function of a dimer of formic and acetic acids and a LTA zeolite structure, in which we consider diffusion of methane.

Abstract Researchers and analysts in modern industrial and academic environments are faced with a daunting amount of multi‐dimensional data. While there has been significant development in the areas of data mining and knowledge discovery, there is still the need for improved visualizations and generic solutions. The state‐of‐the‐art in visual analytics and exploratory data visualization is to incorporate more profound analysis methods while focusing on fast interactive abilities. The common trend in these scenarios is to either visualize an abstraction of the data set or to better utilize screen‐space. This paper presents a novel technique that combines clustering, dimension reduction and multi‐dimensional data representation to form a multivariate data visualization that incorporates both detail and overview. This amalgamation counters the individual drawbacks of common projection and multi‐dimensional data visualization techniques, namely ambiguity and clutter. A specific clustering criterion is used to decompose a multi‐dimensional data set into a hierarchical tree structure. This decomposition is embedded in a novel Dimensional Anchor visualization through the use of a weighted linear dimension reduction technique. The resulting Structural Decomposition Tree (SDT) provides not only an insight of the data set's inherent structure, but also conveys detailed coordinate value information. Further, fast and intuitive interaction techniques are explored in order to guide the user in highlighting, brushing, and filtering of the data.

Abstract The evolution of strain and development of material anisotropy in models of the Earth’s mantle flow convey important information about how to interpret the geometric relationship between observation of seismic anisotropy and the actual mantle flow field. By combining feature extraction techniques such as path line integration and tensor accumulation, we compute time‐varying strain vector fields that build the foundation for a number of feature extraction and visualization techniques. The proposed field segmentation, clustering, histograms and multi‐volume visualization techniques facilitate an intuitive understanding of three‐dimensional strain in such flow fields, overcoming limitations of previous methods such as 2‐D line plots and slicing. We present applications of our approach to an artificial time varying flow data set and a real world example of stationary flow in a subduction zone and discuss the challenges of processing these geophysical data sets as well as the insights gained.

Abstract We present analysis and visualization of flow data from a high‐resolution simulation of the dynamical behavior of the global ocean. Of particular scientific interest are coherent vortical features called mesoscale eddies. We first extract high‐vorticity features using a metric from the oceanography community called the Okubo‐Weiss parameter. We then use a new circularity criterion to differentiate eddies from other non‐eddy features like meanders in strong background currents. From these data, we generate visualizations showing the three‐dimensional structure and distribution of ocean eddies. Additionally, the characteristics of each eddy are recorded to form an eddy census that can be used to investigate correlations among variables such as eddy thickness, depth, and location. From these analyses, we gain insight into the role eddies play in large‐scale ocean circulation.

We consider the problem of extracting discrete two-dimensional vortices from a turbulent flow. In our approach we use a reference model describing the expected physics and geometry of an idealized vortex. The model allows us to derive a novel correlation between the size of the vortex and its strength, measured as the square of its strain minus the square of its vorticity. For vortex detection in real models we use the strength parameter to locate potential vortex cores, then measure the similarity of our ideal analytical vortex and the real vortex core for different strength thresholds. This approach provides a metric for how well a vortex core is modeled by an ideal vortex. Moreover, this provides insight into the problem of choosing the thresholds that identify a vortex. By selecting a target coefficient of determination (i.e., statistical confidence), we determine on a per-vortex basis what threshold of the strength parameter would be required to extract that vortex at the chosen confidence. We validate our approach on real data from a global ocean simulation and derive from it a map of expected vortex strengths over the global ocean.

Though the quality of imaging devices, the accuracy of algorithms that construct 3D data, and the hardware available to render such data have all improved, the algorithms available to calibrate, reconstruct, and then visualize such data are difficult to use, extremely noise sensitive, and unreasonably slow. In this paper, we describe a multi-camera system that creates a highly accurate (on the order of a centimeter), 3D reconstruction of an environment in real time (under 30 ms) that allows for remote interaction between users. The paper addresses the aforementioned deficiencies by featuring an overview of the technology and algorithms used to calibrate, reconstruct, and render objects in the system. The algorithm produces partial 3D meshes, instead of dense point clouds, which are combined on the renderer to create a unified model of the environment. The chosen representation of the data allows for high compression ratios for transfer to remote sites. We demonstrate the accuracy and speed of our results on a variety of benchmarks and data collected from our own system.

Abstract We present an adaptive subdivision scheme for unstructured tetrahedral meshes inspired by the ‐subdivision scheme for triangular meshes. Existing tetrahedral subdivision schemes do not support adaptive refinement and have traditionally been driven by the need to generate smooth three‐dimensional deformations of solids. These schemes use edge bisections to subdivide tetrahedra, which generates octahedra in addition to tetrahedra. To split octahedra into tetrahedra one routinely chooses a direction for the diagonals for the subdivision step. We propose a new topology‐based refinement operator that generates only tetrahedra and supports adaptive refinement. Our tetrahedral subdivision algorithm is motivated by the need to have one representation for the modeling, the simulation and the visualization and so to bridge the gap between CAD and CAE. Our subdivision algorithm design emphasizes on geometric quality of the tetrahedral meshes, local and adaptive refinement operations, and preservation of sharp geometric features on the boundary and in the interior of the physical domain.

Abstract We present a volumetric iso‐geometric finite element analysis based on Catmull‐Clark solids. This concept allows one to use the same representation for the modeling, the physical simulation, and the visualization, which optimizes the design process and narrows the gap between CAD and CAE. In our method the boundary of the solid model is a Catmull‐Clark surface with optional corners and creases to support the modeling phase. The crucial point in the simulation phase is the need to perform efficient integration for the elements. We propose a method similar to the standard subdivision surface evaluation technique, such that numerical quadrature can be used. Experiments show that our approach converges faster than methods based on tri‐linear and tri‐quadratic elements. However, the topological structure of Catmull‐Clark elements is as simple as the structure of linear elements. Furthermore, the Catmull‐Clark elements we use are C2‐continuous on the boundary and in the interior except for irregular vertices and edges.

The recent development of methods for extracting precise measurements of spatial gene expression patterns from three-dimensional (3D) image data opens the way for new analyses of the complex gene regulatory networks controlling animal development. We present an integrated visualization and analysis framework that supports user-guided data clustering to aid exploration of these new complex data sets. The interplay of data visualization and clustering-based data classification leads to improved visualization and enables a more detailed analysis than previously possible. We discuss 1) the integration of data clustering and visualization into one framework, 2) the application of data clustering to 3D gene expression data, 3) the evaluation of the number of clusters k in the context of 3D gene expression clustering, and 4) the improvement of overall analysis quality via dedicated postprocessing of clustering results based on visualization. We discuss the use of this framework to objectively define spatial pattern boundaries and temporal profiles of genes and to analyze how mRNA patterns are controlled by their regulatory transcription factors.

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.

During animal development, complex patterns of gene expression provide positional information within the embryo. To better understand the underlying gene regulatory networks, the Berkeley Drosophila Transcription Network Project (BDTNP) has developed methods that support quantitative computational analysis of three-dimensional (3D) gene expression in early Drosophila embryos at cellular resolution. We introduce PointCloudXplore (PCX), an interactive visualization tool that supports visual exploration of relationships between different genes' expression using a combination of established visualization techniques. Two aspects of gene expression are of particular interest: 1) gene expression patterns defined by the spatial locations of cells expressing a gene and 2) relationships between the expression levels of multiple genes. PCX provides users with two corresponding classes of data views: 1) Physical Views based on the spatial relationships of cells in the embryo and 2) Abstract Views that discard spatial information and plot expression levels of multiple genes with respect to each other. Cell Selectors highlight data associated with subsets of embryo cells within a View. Using linking, these selected cells can be viewed in multiple representations. We describe PCX as a 3D gene expression visualization tool and provide examples of how it has been used by BDTNP biologists to generate new hypotheses.

Laser wakefield particle accelerators have shown the potential to generate electric fields thousands of times higher than those of conventional accelerators. The resulting extremely short particle acceleration distance could yield a potential new compact source of energetic electrons and radiation, with wide applications from medicine to physics. Physicists investigate laser-plasma internal dynamics by running particle-in-cell simulations; however, this generates a large dataset that requires time-consuming, manual inspection by experts in order to detect key features such as beam formation. This paper describes a framework to automate the data analysis and classification of simulation data. First, we propose a new method to identify locations with high density of particles in the space-time domain, based on maximum extremum point detection on the particle distribution. We analyze high density electron regions using a lifetime diagram by organizing and pruning the maximum extrema as nodes in a minimum spanning tree. Second, we partition the multivariate data using fuzzy clustering to detect time steps in a experiment that may contain a high quality electron beam. Finally, we combine results from fuzzy clustering and bunch lifetime analysis to estimate spatially confined beams. We demonstrate our algorithms successfully on four different simulation datasets.

We present a novel user interface in the form of a complementary virtual environment for managing personal document archives, i.e., for document filing and retrieval. Our implementation of a spatial medium for document interaction, exploratory search and active navigation plays to the strengths of human visual information processing and further stimulates it.

One of the central challenges in modern science is the need to quickly derive knowledge and understanding from large, complex collections of data. We present a new approach that deals with this challenge by combining and extending techniques from high performance visual data analysis and scientific data management. This approach is demonstrated within the context of gaining insight from complex, time-varying datasets produced by a laser wakefield accelerator simulation. Our approach leverages histogram-based parallel coordinates for both visual information display as well as a vehicle for guiding a data mining operation. Data extraction and subsetting are implemented with state-of-the-art index/query technology. This approach, while applied here to accelerator science, is generally applicable to a broad set of science applications, and is implemented in a production-quality visual data analysis infrastructure. We conduct a detailed performance analysis and demonstrate good scalability on a distributed memory Cray XT4 system.

Abstract We present a reverse engineering method for constructing a surface approximation scheme whose input is a set of unorganized noisy points in space and whose output is a set of quadric patches. The local surface properties, necessary for the subsequent segmentation, are estimated directly from the data using a simple and efficient data structure—the neighborhood graph. Our segmentation scheme, based on principal curvatures, constructs initial point subsets, which may be enlarged or further subdivided based on associated approximation error estimates obtained through approximation of the initial segments by quadric surfaces. Our method is highly efficient and produces a high‐quality piecewise quadric surface approximation of engineering objects, which we demonstrate for several simple and complex example data sets.

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.

The Morse-Smale (MS) complex has proven to be a useful tool in extracting and visualizing features from scalar-valued data. However, efficient computation of the MS complex for large scale data remains a challenging problem. We describe a new algorithm and easily extensible framework for computing MS complexes for large scale data of any dimension where scalar values are given at the vertices of a closure-finite and weak topology (CW) complex, therefore enabling computation on a wide variety of meshes such as regular grids, simplicial meshes, and adaptive multiresolution (AMR) meshes. A new divide-and-conquer strategy allows for memory-efficient computation of the MS complex and simplification on-the-fly to control the size of the output. In addition to being able to handle various data formats, the framework supports implementation-specific optimizations, for example, for regular data. We present the complete characterization of critical point cancellations in all dimensions. This technique enables the topology based analysis of large data on off-the-shelf computers. In particular we demonstrate the first full computation of the MS complex for a 1 billion/1024(3) node grid on a laptop computer with 2Gb memory.

The amino acid sequence of a protein is the key to understanding its structure and ultimately its function in the cell. This paper addresses the fundamental issue of encoding amino acids in ways that the visualization of protein sequences facilitates the decoding of its information content. We show that a feature-based representation in a three-dimensional (3D) space derived from substitution matrices provides an adequate representation from which the domain content of a protein can be predicted. In addition, we show that each dimension of the feature space can be related to a physical property of the amino acids.

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.

Flow vector fields contain a wealth of information that needs to be visualized. As an extension of the well-known streamline technique, we have developed a context-based method for visualizing steady flow vector fields in two and three dimensions. We call our method "Priority Streamlines". In our approach, the density of the streamlines is controlled by a scalar function that can be user-defined, or be given by additional information (e.g., temperature, pressure, vorticity, velocity) considering the underlying flow vector field. In regions, which are interesting the streamlines are drawn with increased density, while less interesting regions are drawn sparsely. Since streamlines in the most important regions are drawn first, we can use thresholding to obtain a streamline representation highlighting essential features. Color-mapping and transparency can be used for visualizing other information hidden in the flow vector field.

UNLABELLED: We describe a general multiplatform exploratory tool called TreeQ-Vista, designed for presenting functional annotations in a phylogenetic context. Traits, such as phenotypic and genomic properties, are interactively queried from a user-provided relational database with a user-friendly interface which provides a set of tools for users with or without SQL knowledge. The query results are projected onto a phylogenetic tree and can be displayed in multiple color groups. A rich set of browsing, grouping and query tools are provided to facilitate trait exploration, comparison and analysis. AVAILABILITY: The program, detailed tutorial and examples are available online (http:/genome.lbl.gov/vista/TreeQVista).

We present a method for extracting boundary surfaces from segmented cross-section image data. We use a constrained Potts model to interpolate an arbitrary number of region boundaries between segmented images. This produces a segmented volume from which we extract a triangulated boundary surface using well-known marching tetrahedra methods. This surface contains staircase-like artifacts and an abundance of unnecessary triangles. We describe an approach that addresses these problems with a voxel-accurate simplification algorithm that reduces surface complexity by an order of magnitude. Our boundary interpolation and simplification methods are novel contributions to the study of surface extraction from segmented cross-sections. We have applied our method to construct polycrystal grain boundary surfaces from micrographs of a sample of the metal tantalum.

We have combined methods from volume visualization and data analysis to support better diagnosis and treatment of human retinal diseases. Many diseases can be identified by abnormalities in the thicknesses of various retinal layers captured using optical coherence tomography (OCT). We used a support vector machine (SVM) to perform semi-automatic segmentation of retinal layers for subsequent analysis including a comparison of layer thicknesses to known healthy parameters. We have extended and generalized an older SVM approach to support better performance in a clinical setting through performance enhancements and graceful handling of inherent noise in OCT data by considering statistical characteristics at multiple levels of resolution. The addition of the multi-resolution hierarchy extends the SVM to have "global awareness." A feature, such as a retinal layer, can therefore be modeled.

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.

The Morse-Smale complex is an efficient representation of the gradient behavior of a scalar function, and critical points paired by the complex identify topological features and their importance. We present an algorithm that constructs the Morse-Smale complex in a series of sweeps through the data, identifying various components of the complex in a consistent manner. All components of the complex, both geometric and topological, are computed, providing a complete decomposition of the domain. Efficiency is maintained by representing the geometry of the complex in terms of point sets.

We present a novel approach for analyzing two-dimensional (2D) flow field data based on the idea of invariant moments. Moment invariants have traditionally been used in computer vision applications, and we have adapted them for the purpose of interactive exploration of flow field data. The new class of moment invariants we have developed allows us to extract and visualize 2D flow patterns, invariant under translation, scaling, and rotation. With our approach one can study arbitrary flow patterns by searching a given 2D flow data set for any type of pattern as specified by a user. Further, our approach supports the computation of moments at multiple scales, facilitating fast pattern extraction and recognition. This can be done for critical point classification, but also for patterns with greater complexity. This multi-scale moment representation is also valuable for the comparative visualization of flow field data. The specific novel contributions of the work presented are the mathematical derivation of the new class of moment invariants, their analysis regarding critical point features, the efficient computation of a novel feature space representation, and based upon this the development of a fast pattern recognition algorithm for complex flow structures.

Topology provides a foundation for the development of mathematically sound tools for processing and exploration of scalar fields. Existing topology-based methods can be used to identify interesting features in volumetric data sets, to find seed sets for accelerated isosurface extraction, or to treat individual connected components as distinct entities for isosurfacing or interval volume rendering. We describe a framework for direct volume rendering based on segmenting a volume into regions of equivalent contour topology and applying separate transfer functions to each region. Each region corresponds to a branch of a hierarchical contour tree decomposition, and a separate transfer function can be defined for it. The novel contributions of our work are 1) a volume rendering framework and interface where a unique transfer function can be assigned to each subvolume corresponding to a branch of the contour tree, 2) a runtime method for adjusting data values to reflect contour tree simplifications, 3) an efficient way of mapping a spatial location into the contour tree to determine the applicable transfer function, and 4) an algorithm for hardware-accelerated direct volume rendering that visualizes the contour tree-based segmentation at interactive frame rates using graphics processing units (GPUs) that support loops and conditional branches in fragment programs.

Extracting features from point sets is becoming increasingly important for purposes like model classification, matching, and exploration. We introduce a technique for segmenting a point-sampled surface into distinct features without explicit construction of a mesh or other surface representation. Our approach achieves computational efficiency through a three-phase segmentation process. The first phase of the process uses a topological approach to define features and coarsens the input, resulting in a set of supernodes, each one representing a collection of input points. A graph cut is employed in the second phase to bisect the set of supernodes. Similarity between supernodes is computed as a weighted combination of geodesic distances and connectivity. Repeated application of the graph cut results in a hierarchical segmentation of the point input. In the last phase, a segmentation of the original point set is constructed by refining the segmentation of the supernodes based on their associated feature sizes.We apply our segmentation algorithm on laser-scanned models to evaluate its ability to capture geometric features in complex data sets.

Although the processing of data streams has been the focus of many research efforts in several areas, the case of remotely sensed streams in scientific contexts has received little attention. We present an extensible architecture to compose streaming image processing pipelines spanning multiple nodes on a network using a scientific workflow approach. This architecture includes (i) a mechanism for stream query dispatching so new streams can be dynamically generated from within individual processing nodes as a result of local or remote requests, and (ii) a mechanism for making the resulting streams externally available. As complete processing image pipelines can be cascaded across multiple interconnected nodes in a dynamic, scientist-driven way, the approach facilitates the reuse of data and the scalability of computations. We demonstrate the advantages of our infrastructure with a toolset of stream operators acting on remotely sensed data streams for realtime change detection

Vector field visualization approaches can broadly be categorized into approaches that directly visualize local or integrated flow and approaches that analyze the topological structure and visualize extracted features. Our goal was to come up with a method that falls into the first category, yet reveals structural information. We have developed a dense flow visualization method that shows the overall flow behavior while accentuating structural information without performing a topological analysis. Our method is based on a geometry-based flow integration step and a texture-based visual exploration step. The flow integration step generates a density field, which is written into a texture. The density field is generated by tracing particles under the influence of the underlying vector field. When using a quasi-random seeding strategy for initialization, the resulting density is high in attracting regions and low in repelling regions. Density is measured by the number of particles per region accumulated over time. We generate one density field using forward and one using backward propagation. The density fields are explored using texture-based rendering techniques. We generate the two output images separately and blend the results, which allows us to distinguish between inflow and outflow regions. We obtained dense flow visualizations that display the overall flow behavior, emphasize critical and separating regions, and indicate flow direction in the neighborhood of these regions. We have test our method for isolated first-order singularities and real data sets.

To allow a more rigorous understanding of animal gene regulatory networks, the Berkeley Drosophila Transcription Network Project (BDTNP) has developed a suite of methods that support quantitative, computational analysis of three-dimensional (3D) gene expression patterns with cellular resolution in early Drosophila embryos. Here we report the first components of a visualization tool, PointCloudXplore, that allows the relationships between different gene’s expression to be analyzed using the BDTNP’s datasets. PointCloudXplore uses the established visualization techniques of multiple views, brushing, and linking to support the analysis of high-dimensional datasets that describe many genes’ expression. Each of the views in PointCloud- Xplore shows a different gene expression data property. Brushing is used to select and emphasize data associated with defined subsets of embryo cells within a view. Linking is used to show in additional views the expression data for a group of cells that have first been highlighted as a brush in a single view, allowing further data subset properties to be determined. In PointCloudXplore, physical views of the data are linked to parallel coordinates. Physical views show the spatial relationships between different genes’ expression patterns within the embryo. Parallel coordinates, on the other hand, show only some features of each gene’s expression, but allow simultaneous analysis of data for many more genes than would be possible in a physical view. We have developed several extensions to standard parallel coordinates to facilitate brushing the visualization of 3D gene expression data.

We introduce a system that adds a foveal inset to large-scale projection displays. The effective resolution of the foveal inset projection is higher than the original display resolution, allowing the user to see more details and finer features in large data sets. The foveal inset is generated by projecting a high-resolution image onto a mirror mounted on a pan-tilt unit (PTU) that is controlled by the user with a laser pointer. Our implementation is based on Chromium and supports many OpenGL applications without modifications.

This paper describes an efficient combinatorial method for simplification of topological features in a 3D scalar function. The Morse-Smale complex, which provides a succinct representation of a function's associated gradient flow field, is used to identify topological features and their significance. The simplification process, guided by the Morse-Smale complex, proceeds by repeatedly applying two atomic operations that each remove a pair of critical points from the complex. Efficient storage of the complex results in execution of these atomic operations at interactive rates. Visualization of the simplified complex shows that the simplification preserves significant topological features while removing small features and noise.

Natural-neighbor interpolation methods, such as Sibson's method, are well-known schemes for multivariate data fitting and reconstruction. Despite its many desirable properties, Sibson's method is computationally expensive and difficult to implement, especially when applied to higher-dimensional data. The main reason for both problems is the method's implementation based on a Voronoi diagram of all data points. We describe a discrete approach to evaluating Sibson's interpolant on a regular grid, based solely on finding nearest neighbors and rendering and blending d-dimensional spheres. Our approach does not require us to construct an explicit Voronoi diagram, is easily implemented using commodity three-dimensional graphics hardware, leads to a significant speed increase compared to traditional approaches, and generalizes easily to higher dimensions. For large scattered data sets, we achieve two-dimensional (2D) interpolation at interactive rates and 3D interpolation (3D) with computation times of a few seconds.

We present an approach to hierarchically encode the topology of functions over triangulated surfaces. Its Morse-Smale complex, a well known structure in computational topology, describes the topology of a function. Following concepts of Morse theory, a Morse-Smale complex (and therefore a function's topology) can be simplified by successively canceling pairs of critical points. We demonstrate how cancellations can be effectively encoded to produce a highly adaptive topology-based multi-resolution representation of a given function. Contrary to the approach, we avoid encoding the complete complex in a traditional mesh hierarchy. Instead, the information is split into a new structure we call a cancellation forest and a traditional dependency graph. The combination of this new structure with a traditional mesh hierarchy proofs to be significantly more flexible than the one previously reported. In particular, we can create hierarchies that are guaranteed to be of logarithmic height.

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.

The Berkeley DrosophilaTranscription Network Project (BDTNP) is developing a suite of methods that will allow a quantitative description and analysis of three dimensional (3D) gene expression patterns in an animal with cel- lular resolution. An important component of this approach are algorithms that segment 3D images of an organism into individual nuclei and cells and measure relative levels of gene expression. As part of the BDTNP, we are devel- oping tools for interactive visualization, control, and verification of these algorithms. Here we present a volume visualization prototype system that, combined with user interaction tools, supports validation and quantitative determination of the accuracy of nuclear segmentation. Visualizations of nuclei are combined with information obtained from a nuclear segmentation mask, supporting the comparison of raw data and its segmentation. It is possible to select individual nuclei interactively in a volume rendered image and identify incorrectly segmented objects. Integration with segmentation algorithms, implemented in MATLAB, makes it possible to modify a segmentation based on visual examination and obtain additional information about incorrectly segmented objects. This work has already led to significant improvements in segmentation accuracy and opens the way to enhanced analysis of images of complex animal morphologies.

In this paper, we present a topological approach for simplifying continuous functions defined on volumetric domains. We introduce two atomic operations that remove pairs of critical points of the function and design a combinatorial algorithm that simplifies the Morse-Smale complex by repeated application of these operations. The Morse-Smale complex is a topological data structure that provides a compact representation of gradient flow between critical points of a function. Critical points paired by the Morse-Smale complex identify topological features and their importance. The simplification procedure leaves important critical points untouched, and is therefore useful for extracting desirable features. We also present a visualization of the simplified topology.

We introduce the 3D warp brush, a method for interactive shape modeling in a immersive virtual reality environment. 3D warp brushes are implicitly-defined tools that operate on triangle meshes. We combine the efficiency of explicit mesh representations with implicit modeling operators. The area of influence of a 3D warp brush can be of arbitrary shape since it has an associated distance field. We define different warp functions including drag, explode, and whittle. A unique feature of our framework is the ability to convert meshes into 3D warp brushes at run time. The use of a Responsive Workbench and two-handed interaction allows the user to exploit the full potential of the modeling system by intuitive and easy modification of a base surface into a desired shape. We present models, which have been created and modified using 3D warp brushes, to demonstrate the usefulness of our framework.

Much work has been done on the development of laser pointers as interaction devices. Typically a camera captures images of a display surface and extracts a laser pointer dot location. This location is processed and used as a cursor position. While the current literature well explains such a system, we feel that some important practical concerns have gone unaddressed. We discuss the design of such a tracking system, focusing on key practical implementation details. In particular we present a robust and efficient dot detection algorithm that allows us to use our system under a variety lighting conditions, and allows us to reduce the amount of image parsing required to find a laser position by an order of magnitude.

BACKGROUND: Recent advances in sequencing technologies promise to provide a better understanding of the genetics of human disease as well as the evolution of microbial populations. Single Nucleotide Polymorphisms (SNPs) are established genetic markers that aid in the identification of loci affecting quantitative traits and/or disease in a wide variety of eukaryotic species. With today's technological capabilities, it has become possible to re-sequence a large set of appropriate candidate genes in individuals with a given disease in an attempt to identify causative mutations. In addition, SNPs have been used extensively in efforts to study the evolution of microbial populations, and the recent application of random shotgun sequencing to environmental samples enables more extensive SNP analysis of co-occurring and co-evolving microbial populations. The program is available at http://genome.lbl.gov/vista/snpvista1. RESULTS: We have developed and present two modifications of an interactive visualization tool, SNP-VISTA, to aid in the analyses of the following types of data: A. Large-scale re-sequence data of disease-related genes for discovery of associated and/or causative alleles (GeneSNP-VISTA). B. Massive amounts of ecogenomics data for studying homologous recombination in microbial populations (EcoSNP-VISTA). The main features and capabilities of SNP-VISTA are: 1) mapping of SNPs to gene structure; 2) classification of SNPs, based on their location in the gene, frequency of occurrence in samples and allele composition; 3) clustering, based on user-defined subsets of SNPs, highlighting haplotypes as well as recombinant sequences; 4) integration of protein evolutionary conservation visualization; and 5) display of automatically calculated recombination points that are user-editable. CONCLUSION: The main strength of SNP-VISTA is its graphical interface and use of visual representations, which support interactive exploration and hence better understanding of large-scale SNP data by the user.

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.

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.

MOTIVATION: The power of multi-sequence comparison for biological discovery is well established. The need for new capabilities to visualize and compare cross-species alignment data is intensified by the growing number of genomic sequence datasets being generated for an ever-increasing number of organisms. To be efficient these visualization algorithms must support the ability to accommodate consistently a wide range of evolutionary distances in a comparison framework based upon phylogenetic relationships. RESULTS: We have developed Phylo-VISTA, an interactive tool for analyzing multiple alignments by visualizing a similarity measure for multiple DNA sequences. The complexity of visual presentation is effectively organized using a framework based upon interspecies phylogenetic relationships. The phylogenetic organization supports rapid, user-guided interspecies comparison. To aid in navigation through large sequence datasets, Phylo-VISTA leverages concepts from VISTA that provide a user with the ability to select and view data at varying resolutions. The combination of multiresolution data visualization and analysis, combined with the phylogenetic framework for interspecies comparison, produces a highly flexible and powerful tool for visual data analysis of multiple sequence alignments. AVAILABILITY: Phylo-VISTA is available at http://www-gsd.lbl.gov/phylovista. It requires an Internet browser with Java Plug-in 1.4.2 and it is integrated into the global alignment program LAGAN at http://lagan.stanford.edu

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 combine topological and geometric methods to construct a multiresolution representation for a function over a two-dimensional domain. In a preprocessing stage, we create the Morse-Smale complex of the function and progressively simplify its topology by cancelling pairs of critical points. Based on a simple notion of dependency among these cancellations, we construct a hierarchical data structure supporting traversal and reconstruction operations similarly to traditional geometry-based representations. We use this data structure to extract topologically valid approximations that satisfy error bounds provided at runtime.

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

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 combine topological and geometric methods to construct a multi-resolution data structure for functions over two-dimensional domains. Starting with the Morse-Smale complex, we construct a topological hierarchy by progressively canceling critical points in pairs. Concurrently, we create a geometric hierarchy by adapting the geometry to the changes in topology. The data structure supports mesh traversal operations similarly to traditional multi-resolution representations.

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".

We describe an interactive visualization and modeling program for the creation of protein structures "from scratch." The input to our program is an amino acid sequence - decoded from a gene - and a sequence of predicted secondary structure types for each amino acid - provided by external structure prediction programs. Our program can be used in the set-up phase of a protein structure prediction process; the structures created with it serve as input for a subsequent global internal energy minimization, or another method of protein structure prediction. Our program supports basic visualization methods for protein structures, interactive manipulation based on inverse kinematics, and visualization guides to aid a user in creating "good" initial structures.

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.

Isosurfaces are commonly used to visualize scalar fields. Critical isovalues indicate isosurface topology changes: the creation of new surface components, merging of surface components or the formation of holes in a surface component. Therefore, they highlight interesting isosurface behavior and are helpful in exploration of large trivariate data sets. We present a method that detects critical isovalues in a scalar field defined by piecewise trilinear interpolation over a rectilinear grid and describe how to use them when examining volume data. We further review varieties of the marching cubes (MC) algorithm, with the intention of preserving topology of the trilinear interpolant when extracting an isosurface. We combine and extend two approaches in such a way that it is possible to extract meaningful isosurfaces even when a critical value is chosen as the isovalue.

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 describe a method to create optimal linear spline approximations to arbitrary functions of one or two variables, given as scattered data without known connectivity. We start with an initial approximation consisting of a fixed number of vertices and improve this approximation by choosing different vertices, governed by a simulated annealing algorithm. In the case of one variable, the approximation is defined by line segments; in the case of two variables, the vertices are connected to define a Delaunay triangulation of the selected subset of sites in the plane. In a second version of this algorithm, specifically designed for the bivariate case, we choose vertex sets and also change the triangulation to achieve both optimal vertex placement and optimal triangulation. We then create a hierarchy of linear spline approximations, each one being a superset of all lower-resolution ones.

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

We present a new technique for surface reconstruction of digitized models in three dimensions. Concerning this problem, we are given a data set in three-dimensional space, represented as a set of points without connectivity information, and the goal is to find, for a fixed number of vertices, a set of approximating triangles which minimize the error measured by the displacement from the given points. Our method creates near-optimal linear spline approximations, using an iterative optimization scheme based on simulated annealing. The algorithm adopts the mesh to the data set and moves the triangles to enhance feature lines. At the end, we can use the approach to create a hierarchy of different resolutions for the model.

A first step towards a semi-immersive virtual reality (VR) interface for finite element analysis (FEA) is presented in this paper. During recent years, user interfaces of FEA solvers have matured from character-based command-line driven implementations into easy-to-use graphical user interfaces (GUIs). This new generation of GUIs provides access to intuitive and productive tools for the management and analysis of structural problems. Many pre- and post-processors have been implemented targeting the simplification of the man-machine interface in order to increase the ease of use and provide better visual analysis of FEA solver results. Nevertheless, none of these packages provides a real 3D-enabled interface. The main objective of this project is to join state-of-the-art visualization technology, VR devices, and FEA solvers into the integrated development environment VRFEA.

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.

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

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.

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.

Given a three dimensional (3D) array of function values F/sub i,j,k/ on a rectilinear grid, the marching cubes (MC) method is the most common technique used for computing a surface triangulation T approximating a contour (isosurface) F(x, y, z)=T. We describe the construction of a C/sup 0/ continuous surface consisting of rational quadratic surface patches interpolating the triangles in T. We determine the Bezier control points of a single rational quadratic surface patch based on the coordinates of the vertices of the underlying triangle and the gradients and Hessians associated with the vertices.

Sampling and analysis of subsurface contaminants comprise the first steps toward environmental remediation of hazardous spills. We have developed software tools to support the analysis phase, using three different schemes for interpolating scattered 3D soil-quality data onto a grid suitable for viewing in an interactive visualization system. A good interpolation scheme is one that respects the distribution of the original data. We find that the original data can be decimated by up to seventy percent while exhibiting graceful degradation in quality. A prototype software system is being deployed to allow technicians to visually determine, while in the field with their monitoring equipment, where the highest concentrations of contaminants lie. The system is now in use by the U.S. Army Corps of Engineers.

We discuss a visualization system for the comparison of simulated and measured water quality. The system extends SCIRT (Site Characterization Interactive Research Toolkit), an interactive system originally developed at the NSF Engineering Research Center for Computational Field Simulation at Mississippi State University. The ongoing study of the Chesapeake Bay presents research in 3D visualization of model-data comparisons.

Particle path computation in unsteady 3D vector fields given in discrete, structured form (i.e., as a hexahedral curvilinear grid) requires the local approximation of the vector field and the path. Quadrilinear interpolation and Bernstein-Bezier polynomials are used for the local vector field and path approximation. The next point in a sequence of points on a particle path is computed using this local approximation. Bernstein-Bezier polynomials are primarily used in geometric modeling, and their properties allow direct computation of points on a particle path.>

A method for computing isovalue or contour surfaces of a trivariate function is discussed. The input data are values of the trivariate function, F/sub ijk/, at the cuberille grid points (x/sub i/, y/sub j/, z/sub k/), and the output of a collection of triangles representing the surface consisting of all points where F(x,y,z) is a constant value. The method is a modification that is intended to correct a problem with a previous method.>

Some ideas and techniques for visualizing volumetric data are introduced. The methods presented are different from both the volume rendering techniques and surface contour methods. Volumetric data is data with a domain of three independent variables. The independent variables do not have to indicate a position in space and can be abstract in the sense that they can represent any quantity. The authors cover only the case where the dependent data is a single scalar. The authors describe a collection of techniques and ideas for graphing cuberille grid data. All of these techniques are quite simple and rather easy to implement. During the development of these techniques, the authors were particularly concerned with allowing the user to interact with the system in order to interrogate and analyze the relationships indicated by the volumetric data.>