Data Visualization 2001

Point-based models are ideally suited to acquire, transmit, and display complex, real-life three dimensional objects as efficiently as possible. Our objective is to develop 3D graphics technology for cell phones or PDAs, eCommerce, and 3D games.

In this paper, we report our ongoing research into multi-sensory investigation of geoscientific data. Our Geoscientific Data Investigation System (GDIS) integrates three-dimensional, interactive computer graphics, touch (haptics) and real-time sonification into a multi-sensory Virtual Environment. GDIS has been used to investigate geological structures on the high-resolution bathymetry data from the Mid-Atlantic Ridge. Haptic force feedback was used to precisely digitize line features on threedimensional morphology and to feel surface properties via varying friction settings; additional, overlapping data can be perceived via sound (sonification). We also report on the results of a psycho-acoustic study about the absolute recognition of sound signals, and on the actual feedback that we have received from a number of geoscientists during a recent major geoscience conference.

This paper investigates the integrated acquisition, organization, and display of data from disparate sources, including the display of data acquired in real-time. In this case real-time acquisition and display refers to the capture and visualization of data as they are being produced. The particular application investigated is 3D dynamic atmospheric data on terrain, but key elements presented here are applicable more generally to other types of real-time data. 3D Doppler radar data are acquired and visualized with global, high resolution terrain. This is the first time such data have been displayed together in a real-time environment and provides the potential for new vistas in forecasting and analysis. Associated data such as buildings and maps are displayed along with the weather data and the terrain. A global hierarchical structure makes these disparate data available for integrated visualization in real-time. Requirements for effective 3D visualization for decision-making are identified, and it is shown that the applications presented meet most of these requirements.

Adaptive mesh refinement (AMR) is a numerical simulation technique used in computational fluid dynamics (CFD). It permits the efficient simulation of phenomena characterized by substantially varying scales in complexity of local behavior of certain variables. By using a set of nested grids at different resolutions, AMR combines the simplicity of structured rectilinear grids with the possibility to adapt to local changes in complexity and spatial resolution. Hierarchical representations of scientific data pose challenges when isosurfaces are extracted. Cracks can arise at the boundaries between regions represented at different resolutions. We present a method for the extraction of isosurfaces from AMR data that avoids cracks at the boundaries between levels of different resolution.

In this paper, we present a multiresolution algorithm which is capable to render multiple transparent isosurfaces under real-time constraints. To this end, the underlying 3D data set is covered with a hierarchical tetrahedral grid. The multiresolution extraction algorithm is then based on an adaptive traversal of the tetrahedral grid with the help of error indicators. The display of transparent isosurfaces using alpha blending requires a back-to-front rendering of the isosurface triangles. This is achieved by a hierarchical sorting procedure of the tetrahedra and the hierarchical computation of data gradients. We will also comment on the automated selection of suitable isovalues for visualization applications.

We propose a multiresolution representation for maximum intensity projection (MIP) volume rendering, based on morphological pyramids which allow progressive refinement and have the property of perfect reconstruction. The pyramidal analysis and synthesis operators are composed of morphological erosion and dilation, combined with dyadic downsampling for analysis and dyadic upsampling for synthesis. The structure of the multiresolution MIP representation is very similar to wavelet splatting, the main differences being that (i) linear summation of voxel values is replaced by maximum computation, and (ii) linear wavelet filters are replaced by (nonlinear) morphological filters.

We propose a modified Loop subdivision surface scheme for the approximation of scattered data in the plane. Starting with a triangulated set of scattered data with associated function values, our scheme applies linear, stationary subdivision rules resulting in a hierarchy of triangulations that converge rapidly to a smooth limit surface. The novelty of our scheme is that it applies subdivision only to the ordinates of control points, whereas the triangulated mesh in the plane is fixed. Our subdivision scheme defines locally supported, bivariate basis functions and provides multiple levels of approximation with triangles. We use our subdivision scheme for terrain modeling.

In this paper we propose a technique for resampling scalar fields given on unstructured tetrahedral grids. This technique takes advantage of hardware accelerated polygon rendering and 2D texture mapping and thus avoids any sorting of the tetrahedral elements. Using this technique, we have built a visualization tool that enables us to either resample the data onto arbitrarily sized Cartesian grids, or to directly render the data on a slice-by-slice basis. Since our approach does not rely on any pre-processing of the data, it can be utilized efficiently for the display of time-dependent unstructured grids where geometry as well as topology change over time.

Multiscale methods have proved to be successful tools in image denoising, edge enhancement and shape recovery. They are based on the numerical solution of a nonlinear diffusion problem where a noisy or damaged image which has to be smoothed or restorated is considered as initial data. Here a novel approach is presented which will soon be capable to ensure real time performance of these methods. It is based on an implementation of a corresponding finite element scheme in texture hardware of modern graphics engines. The method regards vectors as textures and represents linear algebra operations as texture processing operations. Thus, the resulting performance can profit from the superior bandwidth and the build in parallelism of the graphics hardware. Here the concept of this approach is introduced and perspectives are outlined picking up the basic Perona Malik model on 2D images.

We present Voxel Column Culling, an occlusion culling algorithm for real-time rendering of large terrain models. This technique can greatly reduce the number of polygons that must be rendered every frame, allowing a larger piece of terrain to be rendered at an interactive frame-rate. This is accomplished by using a form of 3D cell-based occlusion culling. A visibility table for the terrain model is precomputed and stored on disk. This table is then used to quickly bypass portions of the model that are not visible due to self-occlusion of the terrain model. This technique improves performance of real-time terrain simulations by reducing the number of polygons to be rendered.

A istream surface in a steady-state three-dimensional fluid flow vector field is a surface across which there is no flow. Stream surfaces can be useful for visualization because the amount of data presented in one visualization can be confined to a manageable quantity in a physically meaningful way.This paper describes a method for generation of stream surfaces, given a threedimensional vector field defined on a curvilinear grid. The method can be characterized as semi-global; that is, it tries to find a surface that satisfies constraints over a region, expressed as integrals (actually sums, due to discreteness), rather than locally propagating the solution of a differential equation.The solution is formulated as a series of quadratic minimization problems in n variables, where nis the cross-wind resolution of the grid. An efficient solution method is developed that exploits the fact that the matrix of each quadratic form is tridiagonal and symmetric. Significant numerical issues are addressed, including degeneracies in the tridiagonal matrix and degeneracies in the grid, both of which are typical for the applications envisioned.

Topology-based visualization of planar turbulent flows results in visual clutter due to the presence of numerous features of very small scale. In this paper, we attack this problem with a topology simplification method for vector and tensor fields defined on irregular grids. This is the generalization of previous work dealing with structured grids. The method works for all interpolation schemes.

Topology-based methods have been successfully applied to the visualization of instantaneous planar vector fields. In this paper, we present the topology-based visualization of time-dependent 2D flows. Our method tracks critical points over time precisely. The detection and classification of bifurcations delivers the topological structure of time dependent vector fields. This offers a general framework for the qualitative analysis and visualization of parameter dependent 2D vector fields.

We present a new method to visualize virtual endoscopic views. We propose to flatten the organ by the direct projection of the surface onto a set of cylinders. Two sampling strategies are presented and the introduced distortions are studied. A non-photorealistic technique is presented to enhance the perception of the images. Finally, an approximate but real-time endoscopic fly-through is possible by using the data obtained by the projection technique.

Virtual colonoscopy (VC) is a patient-friendly alternative for colorectal endoscopic examination. We explore visualization aspects of VC such as surface in view, navigation and communication of a diagnosis. A series of unfolded cubes presents an animated full 360-degree omnidirectional field-of-view to the physician, to facilitate thorough and rapid inspection. For communication between physicians a tool has been designed that uses image-based rendering. Clinical evaluation has shown a reduction in inspection time from 19 minutes to 7 minutes without loss of sensitivity. With current virtual colonoscopy using a 2-sided view only 94% of the surface is available for exploration. In our approach the surface in view is increased to potentially 100%. Thus, the entire colon can be explored with better confidence that no regions are missed.

We present a prototype interactive application for the direct analysis in three dimensions of the cerebral cortex in primates. The paper provides an overview of the current prototype system and presents the techniques used for reconstructing the cortex shape from data derived from histological sections as well as for rendering it at interactive rates. Results are evaluated by discussing the analysis of the right hemisphere of the brain of a macaque monkey used for neuroanatomical tract-tracing experiments.

Based on the VIVENDI-framework for virtual endoscopy, we present a system for the interactive and multi-modal representation of important anatomical structures for neuroendoscopic interventions. A serious problem of neuroendoscopic interventions is the possibility of injuring a blood vessel while performing endoscopic surgery inside the human brain. Besides the sudden loss of optical visibility due to the red-out of the injured vessel, a potential lethal mass bleeding can be the fatal outcome of the intervention. To avoid accidental lesions, we represent the relevant information using multiple volumetric MRI-based representations of the respective organs. Keywords: Virtual Environments, Magnetic-Resonance-Imaging, MR Angiography, Virtual Neuroendoscopy, Computer Assisted Diagnosis.

Voronoi diagrams are an important data structure in computer science. However well studied mathematically, understanding such diagrams for different metrics, orders, and site shapes is a complex task. We propose a new method to visualize k-order diagrams and give an efficient adaptive implementation for this method. The algorithm is easy to customize for different metrics and site shapes. Its real-time performance makes it suitable for interactive planning and analysis of complex Voronoi configurations in 2D. We illustrate the method for different combinations of metrics and site shapes.

First we introduce the concept of graph animations as a sequence of evolving graphs and a generic algorithm which computes a Foresighted Layout for dynamically drawing these graphs while preserving the mental map. The algorithm is generic in the sense that it takes a static graph drawing algorithm as a parameter. In other words, trees can be animated with a static tree layouter, graphs with a static Sugiyama-style layouter or a spring embedder, etc. Second we discuss applications of Foresighted Layout in algorithm animation and visualization of navigation behaviour.

Many real-world e-commerce applications require the mining of large volumes of transaction data to extract marketing and sales information. This paper describes the Directed Association Visualization (DAV) system that visually associates product affinities and relationships for large volumes of e-commerce transaction data. DAV maps transaction data items and their relationships to vertices, edges, and positions on a visual spherical surface. DAV encompasses several innovative techniques (1) items are positioned according to their associations to show the strength of their relationships; (2) edges with arrows are used to represent the implication directions; (3) a mass-spring engine is integrated into a visual data mining platform to provide a self-organized graph. We have applied this system successfully to market basket analysis and e-customer profiling Internet applications.

In this paper we present a compression technique for efficiently representing boundary objects from volumetric data-sets. Exploiting spatial coherency within object contours, we are able to reduce the size of the volumetric boundary down to the size of just a few images. Allowing for direct volume rendering of the down-scaled data in addition to compression ratios up to 250:1, interactive volume visualization becomes possible, even over the Internet and on low-end hardware.

We introduce a novel method for identification of objects of interest in volume data. Our approach conveys the information contained in two essentially different concepts, the object’s boundaries and the narrow solid structures, in an easy and uniform way. The second order derivative operators in directions reaching minimal response are employed for this task. To show the superior performance of our method, we provide a comparison with its main competitor—surface extraction from areas of maximal gradient magnitude. We show that our approach provides the possibility to represent volume data by a subset of a nominal size.

We present an adaptive signed distance transform algorithm for curves in the plane. A hierarchy of bounding boxes is required for the input curves. We demonstrate the algorithm on the isocontours of a turbulence simulation. The algorithm provides guaranteed error bounds with a selective refinement approach. The domain over which the signed distance function is desired is adaptively triangulated and piecewise discontinuous linear approximations are constructed within each triangle. The resulting transform performs work only were requested and does not rely on a preset sampling rate or other constraints.

This paper proposes a new isosurface extraction algorithm that extracts portions of the isosurface in a view-dependent manner by ray casting and propagation. The algorithm casts rays through a volume to find visible active cells as seeds and then propagates their polygonal isosurface into the neighboring cells. Small pieces of the isosurface are generated by distance-limited propagation and joined together to form the final surface. We demonstrate that this progressive algorithm generates an approximate result quickly and refines it to the final correct image over time. In addition, the algorithm scales with the resolution of the display and supports adaptive-resolution visualization.

We propose a hardware-assisted visibility ordering algorithm. From a given viewpoint, a (back-to-front) visibility ordering of a set of objects is a partial order on the objects such that if object A obstructs object B, then A precedes A in the ordering. Such orderings are useful because they are the building blocks of other rendering algorithms such as direct volume rendering of unstructured grids. The traditional way to compute the visibility order is to build a set of visibility relations (e.g. A), and then run a topological sort on the set of relations to actually get the partial ordering. Our technique instead works by assigning a layer number to each primitive, which directly determines the visibility ordering. Objects that have the same layer number are independent, and have no obstruction between each other. We use a simple technique which exploits a combination of the z- and stencil buffers to compute the layer number of each primitive. One application of our technique is to obtain a fast unstructured volume rendering algorithm. In this paper, we present our technique and its implementation in OpenGL. We also discuss its performance and some optimizations on some recent graphics hardware architectures.

This paper explores two general methods for incorporating volumetric uncertainty information in direct volume rendering. The goal is to produce volume rendered images that depict regions of high (or low) uncertainty in the data. The first method involves incorporating the uncertainty information directly into the volume rendering equation. The second method involves post-processing information of volume rendered images to composite uncertainty information. We present some initial findings on what mappings provide qualitatively satisfactory results and what mappings do not. Results are considered satisfactory if the user can identify regions of high or low uncertainty in the rendered image. We also discuss the advantages and disadvantages of both approaches.

This paper presents an automatic error tolerance specification system to control the performance of hierarchical volume rendering. Rather than requiring the user to provide an explicit error tolerance numerically, we let the user to specify only the target rendering speed. Our system can then calculate an appropriate error tolerance adaptively to satisfy the user’s performance goal. The system is realized using fuzzy logic control, which enables run-time adaptation based on iterative feedback control and knowledge acquired from past experience. We describe the process of constructing the fuzzy logic control system, and show that the system can successfully steer the performance of volume rendering.

Most existing volume rendering algorithms assume that data sets are memory-resident and thus ignore the performance overhead of disk I/O. While this assumption may be true for high-performance graphics machines, it does not hold for most desktop personal workstations. To minimize the end-to-end volume rendering time, this work re-examines implementation strategies of the ray casting algorithm, taking into account both computation and I/O overhead-s. Specifically, we developed a data-driven execution model for ray casting that achieves the maximum overlap between rendering computation and disk I/O. Together with other performance optimizations, on a 300-MHz Pentium-II machine, without directional shading, our implementation is able to render a 128x128 grey-scale image from a 128x128x128 data set with an average end-to-end delay of 1 second, which is very close to the memory-resident rendering time. With a little modification, this work can also be extended to do out-of-core visualization as well.

Virtual Environment technology enables new styles of user interfaces that provide multi-sensory interactions. For example, interfaces can be designed which immerse the user in a 3D space and provide multi-sensory feedback. Many information spaces are multivariate, large and abstract in nature. It has been a goal of Virtual Environments to widen the human to computer bandwidth and so assist in the interpretation of these spaces by providing models that allow the user to interact ’naturally’. One goal for this interaction may be to uncover useful patterns within the data. This paper describes a Virtual Environment system called the “Workbench” and explains three models of stock market data that have been developed for this environment. The aim of this work is to provide models that allow analysts to explore for new trading patterns in the stock market data. Some early results of this work are discussed.

We describe our efforts to analyze network intrusion detection data using information retrieval and visualization tools. By regarding Telnet sessions as documents, which may or may not include attacks, a session that contains a certain type of attack can be used as a query, allowing us to search the data for other instances of that same type of attack. The use of information visualization techniques allows us to quickly and clearly find the attacks and also find similar, potentially new types of attacks.

In this paper we present DDDiver, a tool for the interactive visualization and editing of Object-Oriented databases. It was developed to visualize and manipulate large loosely-structured data sets with multiple relation types. This makes the tool especially useful in application areas that involve product data models, design information systems, and semantic networks. DDDiver can visualize such relational data sets in a 3d graph. The layout mechanism used for the graph is not based on a deterministic mathematical algorithm, but on the distinction between a number of relation kinds, and on user interaction. The intuitiveness and quickness of the visualization tool was further improved by adding animated visual feedback effects.

A predictive system of thermal flow with quick turnaround time in a passenger compartment has been developed. An efficient method based on the Cartesian mesh system was used to reduce the period of analysis. The computed temperature in an automotive cabin was visualized by volume rendering techniques using an RVS LIB software library developed by NEC. Consecutive images of the flow were converted into MPEG1 movies, which gave us an overall understanding of the flow. The visualization results indicate that the present system is capable to sufficiently predict the thermal environment in a vehicle cabin at early stage of vehicle development.

In the automotive industry Lattice-Boltzmann type flow solvers like PowerFlow from Exa Corporation are becoming increasingly important. In contrast to the traditional finite volume approach PowerFlow utilizes a hierachical cartesian grid for flow simulation. In this case study we show how to take advantage of these hierarchical grids in order to extend an existing Lattice-Boltzmann CFD environment with an automotive soiling simulation system. To achieve this, we chose to constantly generate a huge number of massive particles in user manipulable particle emitters. The process of tracing these particles step by step thus creates evolving particle streams, which can be displayed interactively by our visualization system. Each particle is created with stochastically varying diameter, specific mass and initial velocity, whereas already existing particles may decay because of aging, when leaving the simulation domain or when colliding with the vehicle’s surface. On the one hand the display of these animated particles is a very natural and intuitive way to explore a CFD data set. On the other hand animated massive particles can be easily utilized for driving an automotive soiling simulation just by coloring the particles’ hit points on the vehicle’s surface.

Since crash-worthiness simulations get more and more important as part of the car development process in order to reduce the cost of development, enhance the product quality, and minimize the time-to-market, the reliability of the simulation results plays a decisive role concerning their significance. Recently the simulation departments of several automotive companies started investigating the quantity and reason for deviations during a number of simulation runs on the same input model.In this case study we discuss different measurements for instability and present a texture-based visualization method which allows the engineers to efficiently explore the simulation results by interactively hiding finite element structures with nearly constant crash performance. Furthermore, we describe those parts of our prototype which use a CORBA layer for providing the same view on a set of simulation results and allowing the visual comparison by using the marker functionality.