Search

Histograms computed from local regions are commonly used in many visualization applications, and allowing the user to query histograms interactively in regions of arbitrary locations and sizes plays an important role in feature identification and tracking. Computing histograms in regions with arbitrary location and size, nevertheless, can be time consuming for large data sets since it involves expensive I/O and scan of data elements. To achieve both performance- and storage-efficient query of local histograms, we present a new algorithm called WaveletSAT, which utilizes integral histograms, an extension of the summed area tables (SAT), and discrete wavelet transform (DWT). Similar to SAT, an integral histogram is the histogram computed from the area between each grid point and the grid origin, which can be be pre-computed to support fast query. Nevertheless, because one histogram contains multiple bins, it will be very expensive to store one integral histogram at each grid point. To reduce the storage cost for large integral histograms, WaveletSAT treats the integral histograms of all grid points as multiple SATs, each of which can be converted into a sparse representation via DWT, allowing the reconstruction of axis-aligned region histograms of arbitrary sizes from a limited number of wavelet coefficients. Besides, we present an efficient wavelet transform algorithm for SATs that can operate on each grid point separately in logarithmic time complexity, which can be extended to parallel GPU-based implementation. With theoretical and empirical demonstration, we show that WaveletSAT can achieve fast preprocessing and smaller storage overhead than the conventional integral histogram approach with close query performance.

A 4D parametric motion graph representation is presented for interactive animation from actor performance capture in a multiple camera studio. The representation is based on a 4D model database of temporally aligned mesh sequence reconstructions for multiple motions. High-level movement controls such as speed and direction are achieved by blending multiple mesh sequences of related motions. A real-time mesh sequence blending approach is introduced, which combines the realistic deformation of previous nonlinear solutions with efficient online computation. Transitions between different parametric motion spaces are evaluated in real time based on surface shape and motion similarity. Four-dimensional parametric motion graphs allow real-time interactive character animation while preserving the natural dynamics of the captured performance.

We introduce an algorithm for construction of the Morse hierarchy, i.e., a hierarchy of Morse decompositions of a piecewise constant vector field on a surface driven by stability of the Morse sets with respect to perturbation of the vector field. Our approach builds upon earlier work on stable Morse decompositions, which can be used to obtain Morse sets of user-prescribed stability. More stable Morse decompositions are coarser, i.e., they consist of larger Morse sets. In this work, we develop an algorithm for tracking the growth of Morse sets and topological events (mergers) that they undergo as their stability is gradually increased. The resulting Morse hierarchy can be explored interactively. We provide examples demonstrating that it can provide a useful coarse overview of the vector field topology.

Displays remain flat and passive amidst the many changes in their fundamental technologies. One natural step ahead is to create displays that merge seamlessly in shape and appearance with one’s natural surroundings. In this paper, we present a system to design, render to, and build view-dependent multiplanar displays of arbitrary piecewise-planar shapes, built using polygonal facets. Our system provides high quality, interactive rendering of 3D environments to a head-tracked viewer on arbitrary multiplanar displays. We develop a novel rendering scheme that produces exact image and depth map at each facet, producing artifact-free images on and across facet boundaries. The system scales to a large number of display facets by rendering all facets in a single pass of rasterization. This is achieved using a parallel, perframe, view-dependent binning and prewarping of scene triangles. The display is driven using one or more target quilt images into which facet pixels are packed. Our method places no constraints on the scene or the display and allows for fully dynamic scenes to be rendered interactively at high resolutions. The steps of our system are implemented efficiently on commodity GPUs. We present a few prototype displays to establish the scalability of our system on different display shapes, form factors, and complexity: from a cube made out of LCD panels to spherical/cylindrical projected setups to arbitrary complex shapes in simulation. Performance of our system is demonstrated for both rendering quality and speed, for increasing scene and display facet sizes. A subjective user study is also presented to evaluate the user experience using a walk-around display compared to a flat panel for a game-like setting.

Direct projection of three-dimensional branching structures, such as networks of cables, blood vessels, or neurons onto a 2D image creates the illusion of intersecting structural parts and creates challenges for understanding and communication. We present a method for visualizing such structures, and demonstrate its utility in visualizing the abdominal aorta and its branches, whose tomographic images might be obtained by computed tomography or magnetic resonance angiography, in a single two-dimensional stylistic image, without overlaps among branches. The visualization method, termed uncluttered single-image visualization (USIV), involves optimization of geometry. This paper proposes a novel optimization technique that utilizes an interesting connection of the optimization problem regarding USIV to the protein structure prediction problem. Adopting the integer linear programming-based formulation for the protein structure prediction problem, we tested the proposed technique using 30 visualizations produced from five patient scans with representative anatomical variants in the abdominal aortic vessel tree. The novel technique can exploit commodity-level parallelism, enabling use of general-purpose graphics processing unit (GPGPU) technology that yields a significant speedup. Comparison of the results with the other optimization technique previously reported elsewhere suggests that, in most aspects, the quality of the visualization is comparable to that of the previous one, with a significant gain in the computation time of the algorithm.

Cube mapping is widely used in many graphics applications due to the availability of hardware support. However, it does not sample the spherical surface evenly. Recently, a uniform spherical mapping, isocube mapping, was proposed. It exploits the six-face structure used in cube mapping and samples the spherical surface evenly. Unfortunately, some texels in isocube mapping are not rectilinear. This nonrectilinear property may degrade the filtering quality. This paper proposes a novel spherical mapping, namely unicube mapping. It has the advantages of cube mapping (exploitation of hardware and rectilinear structure) and isocube mapping (evenly sampling pattern). In the implementation, unicube mapping uses a simple function to modify the lookup vector before the conventional cube map lookup process. Hence, unicube mapping fully exploits the cube map hardware for real-time filtering and lookup. More importantly, its rectilinear partition structure allows a direct and real-time acquisition of the texture environment. This property facilitates dynamic environment mapping in a real time manner.

Human motion indexing and retrieval are important for animators due to the need to search for motions in the database which can be blended and concatenated. Most of the previous researches of human motion indexing and retrieval compute the Euclidean distance of joint angles or joint positions. Such approaches are difficult to apply for cases in which multiple characters are closely interacting with each other, as the relationships of the characters are not encoded in the representation. In this research, we propose a topology-based approach to index the motions of two human characters in close contact. We compute and encode how the two bodies are tangled based on the concept of rational tangles. The encoded relationships, which we define as TangleList, are used to determine the similarity of the pairs of postures. Using our method, we can index and retrieve motions such as one person piggy-backing another, one person assisting another in walking, and two persons dancing / wrestling. Our method is useful to manage a motion database of multiple characters. We can also produce motion graph structures of two characters closely interacting with each other by interpolating and concatenating topologically similar postures and motion clips, which are applicable to 3D computer games and computer animation.

This paper presents an algorithm for drawing a sequence of graphs online. The algorithm strives to maintain the global structure of the graph and, thus, the user's mental map while allowing arbitrary modifications between consecutive layouts. The algorithm works online and uses various execution culling methods in order to reduce the layout time and handle large dynamic graphs. Techniques for representing graphs on the GPU allow a speedup by a factor of up to 17 compared to the CPU implementation. The scalability of the algorithm across GPU generations is demonstrated. Applications of the algorithm to the visualization of discussion threads in Internet sites and to the visualization of social networks are provided.

Existing topology-based vector field analysis techniques rely on the ability to extract the individual trajectories such as fixed points, periodic orbits, and separatrices that are sensitive to noise and errors introduced by simulation and interpolation. This can make such vector field analysis unsuitable for rigorous interpretations. We advocate the use of Morse decompositions, which are robust with respect to perturbations, to encode the topological structures of a vector field in the form of a directed graph, called a Morse connection graph (MCG). While an MCG exists for every vector field, it need not be unique. Previous techniques for computing MCG's, while fast, are overly conservative and usually results in MCG's that are too coarse to be useful for the applications. To address this issue, we present a new technique for performing Morse decomposition based on the concept of tau-maps, which typically provides finer MCG's than existing techniques. Furthermore, the choice of tau provides a natural tradeoff between the fineness of the MCG's and the computational costs. We provide efficient implementations of Morse decomposition based on tau-maps, which include the use of forward and backward mapping techniques and an adaptive approach in constructing better approximations of the images of the triangles in the meshes used for simulation.. Furthermore, we propose the use of spatial tau-maps in addition to the original temporal tau-maps. These techniques provide additional trade-offs between the quality of the MCGs and the speed of computation. We demonstrate the utility of our technique with various examples in the plane and on surfaces including engine simulation data sets.

Computing smooth and optimal one-to-one maps between surfaces of same topology is a fundamental problem in graphics and such a method provides us a ubiquitous tool for geometric modeling and data visualization. Its vast variety of applications includes shape registration/matching, shape blending, material/data transfer, data fusion, information reuse, etc. The mapping quality is typically measured in terms of angular distortions among different shapes. This paper proposes and develops a novel quasi-conformal surface mapping framework to globally minimize the stretching energy inevitably introduced between two different shapes. The existing state-of-the-art intersurface mapping techniques only afford local optimization either on surface patches via boundary cutting or on the simplified base domain, lacking rigorous mathematical foundation and analysis. We design and articulate an automatic variational algorithm that can reach the global distortion minimum for surface mapping between shapes of arbitrary topology, and our algorithm is solely founded upon the intrinsic geometry structure of surfaces. To our best knowledge, this is the first attempt toward rigorously and numerically computing globally optimal maps. Consequently, we demonstrate our mapping framework, offers a powerful computational tool for graphics and visualization tasks such as data and texture transfer, shape morphing, and shape matching.

The present paper addresses real-time simulation of cables for virtual environments. A faithful physical model based on constrained rigid bodies is introduced and discretized. The performance and stability of the numerical method are analyzed in details and found to meet the requirements of interactive heavy hoisting simulations. The physical model is well behaved in the limit of infinite stiffness as well as in the elastic regime, and the tuning parameters correspond directly to conventional material constants. The integration scheme mixes the well known Störmer-Verlet method for the dynamics equations with the linearly implicit Euler method for the constraint equations and enables physical constraint relaxation and stabilization terms. The technique is shown to have superior numerical stability properties in comparison with either chain link systems, or spring and damper models. Experimental results are presented to show that the method results in stable, real-time simulations. Stability persists for moderately large fixed integration step of Delta t = 1/60 s, with hoisting loads of up to 10(5) times heavier than the elements of the cable. Further numerical experiments validating the physical model are also presented.

This paper introduces orthogonal vector field visualization on 2D manifolds: a representation by lines that are perpendicular to the input vector field. Line patterns are generated by line integral convolution (LIC). This visualization is combined with animation based on motion along the vector field. This decoupling of the line direction from the direction of animation allows us to choose the spatial frequencies along the direction of motion independently from the length scales along the LIC line patterns. Vision research indicates that local motion detectors are tuned to certain spatial frequencies of textures, and the above decoupling enables us to generate spatial frequencies optimized for motion perception. Furthermore, we introduce a combined visualization that employs orthogonal LIC patterns together with conventional, tangential streamline LIC patterns in order to benefit from the advantages of these two visualization approaches; the combination of orthogonal and tangential LIC is achieved by two novel image-space compositing schemes. In addition, a filtering process is described to achieve a consistent and temporally coherent animation of orthogonal vector field visualization. Different filter kernels and filter methods are compared and discussed in terms of visualization quality and speed. We present respective visualization algorithms for 2D planar vector fields and tangential vector fields on curved surfaces and demonstrate that those algorithms lend themselves to efficient and interactive GPU implementations.

In computer graphics, triangular mesh representations of surfaces have become very popular. Compared with parametric and implicit forms of surfaces, triangular mesh surfaces have many advantages such as being easy to render, being convenient to store, and having the ability to model geometric objects with arbitrary topology. In this paper, we are interested in data processing over triangular mesh surfaces through partial differential equations (PDEs). We study several diffusion equations over triangular mesh surfaces and present corresponding numerical schemes to solve them. Our methods work for triangular mesh surfaces with arbitrary geometry (the angles of each triangle are arbitrary) and topology (open meshes or closed meshes of arbitrary genus). Besides the flexibility, our methods are efficient due to the implicit/semi-implicit time discretization. We finally apply our methods to several filtering and texture applications such as image processing, texture generation, and regularization of harmonic maps over triangular mesh surfaces. The results demonstrate the flexibility and effectiveness of our methods.

Curved Planar Reformation (CPR) has proved to be a practical and widely used tool for the visualization of curved tubular structures within the human body. It has been useful in medical procedures involving the examination of blood vessels and the spine. However, it is more difficult to use it for large, tubular, structures such as the trachea and the colon because abnormalities may be smaller relative to the size of the structure and may not have such distinct density and shape characteristics. Our new approach improves on this situation by using volume rendering for hollow regions and standard CPR for the surrounding tissue. This effectively combines gray scale contextual information with detailed color information from the area of interest. The approach is successfully used with each of the standard CPR types and the resulting images are promising as an alternative to virtual endoscopy. Because the CPR and the volume rendering are tightly coupled, the projection method used has a significant effect on properties of the volume renderer, such as distortion and isometry. We describe and compare the different CPR projection methods and how they affect the volume rendering process. A version of the algorithm is also presented which makes use of importance driven techniques; this ensures the users attention is always focused on the area of interest and also improves the speed of the algorithm.

Two methods have been used extensively to model resting contact for rigid-body simulation. The first approach, the penalty method, applies virtual springs to surfaces in contact to minimize interpenetration. This method, as typically implemented, results in oscillatory behavior and considerable penetration. The second approach, based on formulating resting contact as a linear complementarity problem, determines the resting contact forces analytically to prevent interpenetration. The analytical method exhibits an expected-case polynomial complexity in the number of contact points and may fail to find a solution in polynomial time when friction is modeled. We present a fast penalty method that minimizes oscillatory behavior and leads to little penetration during resting contact; our method compares favorably to the analytical method with regard to these two measures while exhibiting much faster performance both asymptotically and empirically.

This survey reviews the recent advances in linear variational mesh deformation techniques. These methods were developed for editing detailed high-resolution meshes, like those produced by scanning real-world objects. The challenge of manipulating such complex surfaces is three-fold: the deformation technique has to be sufficiently fast, robust, and intuitive and easy to control to be useful for interactive applications. An intuitive, and thus predictable, deformation tool should provide physically plausible and aesthetically pleasing surface deformations, which in particular requires its geometric details to be preserved. The methods we survey generally formulate surface deformation as a global variational optimization problem that addresses the differential properties of the edited surface. Efficiency and robustness are achieved by linearizing the underlying objective functional, such that the global optimization amounts to solving a sparse linear system of equations. We review the different deformation energies and detail preservation techniques that were proposed in the recent years, together with the various techniques to rectify the linearization artifacts. Our goal is to provide the reader with a systematic classification and comparative description of the different techniques, revealing the strengths and weaknesses of each approach in common editing scenarios.

Topological methods give concise and expressive visual representations of flow fields. The present work suggests a comparable method for the visualization of human brain diffusion MRI data. We explore existing techniques for the topological analysis of generic tensor fields, but find them inappropriate for diffusion MRI data. Thus, we propose a novel approach that considers the asymptotic behavior of a probabilistic fiber tracking method and define analogs of the basic concepts of flow topology, like critical points, basins, and faces, with interpretations in terms of brain anatomy. The resulting features are fuzzy, reflecting the uncertainty inherent in any connectivity estimate from diffusion imaging. We describe an algorithm to extract the new type of features, demonstrate its robustness under noise, and present results for two regions in a diffusion MRI dataset to illustrate that the method allows a meaningful visual analysis of probabilistic fiber tracking results.

Remote visualization is an enabling technology aiming to resolve the barrier of physical distance. Although many researchers have developed innovative algorithms for remote visualization, previous work has focused little on systematically investigating optimal configurations of remote visualization architectures. In this paper, we study caching and prefetching, an important aspect of such architecture design, in order to optimize the fetch time in a remote visualization system. Unlike a processor cache or Web cache, caching for remote visualization is unique and complex. Through actual experimentation and numerical simulation, we have discovered ways to systematically evaluate and search for optimal configurations of remote visualization caches under various scenarios, such as different network speeds, sizes of data for user requests, prefetch schemes, cache depletion schemes, etc. We have also designed a practical infrastructure software to adaptively optimize the caching architecture of general remote visualization systems, when a different application is started or the network condition varies. The lower bound of achievable latency discovered with our approach can aid the design of remote visualization algorithms and the selection of suitable network layouts for a remote visualization system.

This paper presents a modular framework to efficiently apply the bidirectional texture functions (BTF) onto object surfaces. The basic building blocks are the BTF tiles. By constructing one set of BTF tiles, a wide variety of objects can be textured seamlessly without resynthesizing the BTF. The proposed framework nicely decouples the surface appearance from the geometry. With this appearance-geometry decoupling, one can build a library of BTF tile sets to instantaneously dress and render various objects under variable lighting and viewing conditions. The core of our framework is a novel method for synthesizing seamless high-dimensional BTF tiles, which are difficult for existing synthesis techniques. Its key is to shorten the cutting paths and broaden the choices of samples so as to increase the chance of synthesizing seamless BTF tiles. To tackle the enormous data, the tile synthesis process is performed in a compressed domain. This not only allows the handling of large BTF data during the synthesis, but also facilitates the compact storage of the BTF in a GPU memory during the rendering.

Direct volume rendered images (DVRIs) have been widely used to reveal structures in volumetric data. However, DVRIs generated by many volume visualization techniques can only partially satisfy users' demands. In this paper, we propose a framework for editing DVRIs, which can also be used for interactive transfer function (TF) design. Our approach allows users to fuse multiple features in distinct DVRIs into a comprehensive one, to blend two DVRIs, and/or to delete features in a DVRI. We further present how these editing operations can generate smooth animations for focus + context visualization. Experimental results on some real volumetric data demonstrate the effectiveness of our method.

Visualization has become an important component of the simulation pipeline, providing scientists and engineers a visual intuition of their models. Simulations that make use of the high-order finite element method for spatial subdivision, however, present a challenge to conventional isosurface visualization techniques. High-order finite element isosurfaces are often defined by basis functions in reference space, which give rise to a world-space solution through a coordinate transformation, which does not necessarily have a closed-form inverse. Therefore, world-space isosurface rendering methods such as marching cubes and ray tracing must perform a nested root finding, which is computationally expensive. We thus propose visualizing these isosurfaces with a particle system. We present a framework that allows particles to sample an isosurface in reference space, avoiding the costly inverse mapping of positions from world space when evaluating the basis functions. The distribution of particles across the reference space isosurface is controlled by geometric information from the world-space isosurface such as the surface gradient and curvature. The resulting particle distributions can be distributed evenly or adapted to accommodate world-space surface features. This provides compact, efficient, and accurate isosurface representations of these challenging data sets.

Orthopedists invest significant amounts of effort and time trying to understand the biomechanics of arthrodial (gliding) joints. Although new image acquisition and processing methods currently generate richer-than-ever geometry and kinematic data sets that are individual specific, the computational and visualization tools needed to enable the comparative analysis and exploration of these data sets lag behind. In this paper, we present a framework that enables the cross-data-set visual exploration and analysis of arthrodial joint biomechanics. Central to our approach is a computer-vision-inspired markerless method for establishing pairwise correspondences between individual-specific geometry. Manifold models are subsequently defined and deformed from one individual-specific geometry to another such that the markerless correspondences are preserved while minimizing model distortion. The resulting mutually consistent parameterization and visualization allow the users to explore the similarities and differences between two data sets and to define meaningful quantitative measures. We present two applications of this framework to human-wrist data: articular cartilage transfer from cadaver data to in vivo data and cross-data-set kinematics analysis. The method allows our users to combine complementary geometries acquired through different modalities and thus overcome current imaging limitations. The results demonstrate that the technique is useful in the study of normal and injured anatomy and kinematics of arthrodial joints. In principle, the pairwise cross-parameterization method applies to all spherical topology data from the same class and should be particularly beneficial in instances where identifying salient object features is a nontrivial task.

This paper presents a technique for mixed media nonphotorealistic painting and portraiture. The goal of this work is to transform digital images into renderings that approximate the appearance of mixed-media artwork, which incorporates two or more traditional visual media. We achieve this by first separating an input image into distinct regions based on the degree of local detail present in the image. Each region is then processed independently with a user-selected nonphotorealistic rendering (NPR) filter. This allows the user to treat highly detailed regions differently from regions of low-frequency content. The separately processed regions are then smoothly fused in the gradient domain. In addition, we extend our work to the rendering of mixed-media portraits. Portraits pose unique challenges that we address with our method of segmentation, which is based on a composite of face detection and image detail. Our approach offers the user a great deal of flexibility over the end result, while at the same time requiring very little input. This input takes the form of a few simple and discrete choices. The results demonstrate an impressive array of transformational possibilities.

To eliminate the need to evaluate the intersection curves in explicit representations of surface cutouts or of trimmed faces in BReps of CSG solids, we advocate using Constructive Solid Trimming (CST). A CST face is the intersection of a surface with a Blist representation of a trimming CSG volume. We propose a new GPU-based CSG rendering algorithm that trims the boundary of each primitive using a Blist of its active zone. This approach is faster than the previously reported Blister approach, eliminates occasional speckles of wrongly colored pixels, and provides additional capabilities: painting on surfaces, rendering semitransparent CSG models, and highlighting selected features in the BReps of CSG models.

In this paper, we propose a novel framework called space-time light field rendering, which allows continuous exploration of a dynamic scene in both space and time. Compared to existing light field capture/rendering systems, it offers the capability of using unsynchronized video inputs and the added freedom of controlling the visualization in the temporal domain, such as smooth slow motion and temporal integration. In order to synthesize novel views from any viewpoint at any time instant, we develop a two-stage rendering algorithm. We first interpolate in the temporal domain to generate globally synchronized images using a robust spatial-temporal image registration algorithm followed by edge-preserving image morphing. We then interpolate these software-synchronized images in the spatial domain to synthesize the final view. In addition, we introduce a very accurate and robust algorithm to estimate subframe temporal offsets among input video sequences. Experimental results from unsynchronized videos with or without time stamps show that our approach is capable of maintaining photorealistic quality from a variety of real scenes.

This paper proposes a novel six-face spherical map, isocube, that fully utilizes the cubemap hardware built in most GPUs. Unlike the cubemap, the proposed isocube uniformly samples the unit sphere (uniformly distributed), and all samples span the same solid angle (equally important). Its mapping computation contains only a small overhead. By feeding the cubemap hardware with the six-face isocube map, the isocube can exploit all built-in texturing operators tailored for the cubemap and achieve a very high frame rate. In addition, we develop an anisotropic filtering that compensates aliasing artifacts due to texture magnification. This filtering technique extends the existing hardware anisotropic filtering and can be applied not only to the proposed isocube, but also to other texture mapping applications.

This paper presents an automatic and robust approach to synthesize stereoscopic videos from ordinary monocular videos acquired by commodity video cameras. Instead of recovering the depth map, the proposed method synthesizes the binocular parallax in stereoscopic video directly from the motion parallax in monocular video. The synthesis is formulated as an optimization problem via introducing a cost function of the stereoscopic effects, the similarity, and the smoothness constraints. The optimization selects the most suitable frames in the input video for generating the stereoscopic video frames. With the optimized selection, convincing and smooth stereoscopic video can be synthesized even by simple constant-depth warping. No user interaction is required. We demonstrate the visually plausible results obtained given the input clips acquired by ordinary handheld video camera.

Human grasps, especially whole-hand grasps, are difficult to animate because of the high number of degrees of freedom of the hand and the need for the hand to conform naturally to the object surface. Captured human motion data provides us with a rich source of examples of natural grasps. However, for each new object, we are faced with the problem of selecting the best grasp from the database and adapting it to that object. This paper presents a data-driven approach to grasp synthesis. We begin with a database of captured human grasps. To identify candidate grasps for a new object, we introduce a novel shape matching algorithm that matches hand shape to object shape by identifying collections of features having similar relative placements and surface normals. This step returns many grasp candidates, which are clustered and pruned by choosing the grasp best suited for the intended task. For pruning undesirable grasps, we develop an anatomically-based grasp quality measure specific to the human hand. Examples of grasp synthesis are shown for a variety of objects not present in the original database. This algorithm should be useful both as an animator tool for posing the hand and for automatic grasp synthesis in virtual environments.

We present an efficient point-based isosurface exploration system with high quality rendering. Our system incorporates two point-based isosurface extraction and visualization methods: edge splatting and the edge kernel method. In a volume, two neighboring voxels define an edge. The intersection points between the active edges and the isosurface are used for exact isosurface representation. The point generation is incorporated in the GPU-based hardware-accelerated rendering, thus avoiding any overhead when changing the isovalue in the exploration. We call this method edge splatting. In order to generate high quality isosurface rendering regardless of the volume resolution and the view, we introduce an edge kernel method. The edge kernel upsamples the isosurface by subdividing every active cell of the volume data. Enough sample points are generated to preserve the exact shape of the isosurface defined by the trilinear interpolation of the volume data. By employing these two methods, we can achieve interactive isosurface exploration with high quality rendering.

Modern graphics cards are equipped with a vertex cache to reduce the amount of data needing to be transmitted to the graphics pipeline during rendering. To make effective use of the cache and facilitate rendering, it is key to represent a mesh in a manner that maximizes the cache hit rate. In this paper, we propose a simple yet effective algorithm for generating a sequence for efficient rendering of 3D polygonal meshes based on greedy optimization. The algorithm outperforms the current state-of-the-art algorithms in terms of rendering efficiency of the resultant sequence. We also adapt it for the rendering of progressive meshes. For any simplified version of the original mesh, the rendering sequence is generated by adaptively updating the reordered sequence at full resolution. The resultant rendering sequence is cheap to compute and has reasonably good rendering performance, which is desirable to many complex rendering environments involving continuous rendering of meshes at various level of details. The experimental results on a collection of 3D meshes are provided.

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.

In this paper, we describe a novel multifocal projection concept that applies conventional video projectors and camera feedback. Multiple projectors with differently adjusted focal planes, but overlapping image areas are used. They can be either differently positioned in the environment or can be integrated into a single projection unit. The defocus created on an arbitrary surface is estimated automatically for each projector pixel. If this is known, a final image with minimal defocus can be composed in real-time from individual pixel contributions of all projectors. Our technique is independent of the surfaces' geometry, color and texture, the environment light, as well as of the projectors' position, orientation, luminance, and chrominance.

A variety of computer graphics applications sample surfaces of 3D shapes in a regular grid without making the sampling rate adaptive to the surface curvature or sharp features. Triangular meshes that interpolate or approximate these samples usually exhibit relatively big error around the insensitive sampled sharp features. This paper presents a robust general approach conducting bilateral filters to recover sharp edges on such insensitive sampled triangular meshes. Motivated by the impressive results of bilateral filtering for mesh smoothing and denoising, we adopt it to govern the sharpening of triangular meshes. After recognizing the regions that embed sharp features, we recover the sharpness geometry through bilateral filtering, followed by iteratively modifying the given mesh's connectivity to form single-wide sharp edges that can be easily detected by their dihedral angles. We show that the proposed method can robustly reconstruct sharp edges on feature-insensitive sampled meshes.

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 three-dimensional interpolation(3D) with computation times of a few seconds.

We review schemes for dividing cubic cells into simplices (tetrahedra) for interpolating from sampled data to R/sup 3/, present visual and geometric artifacts generated in isosurfaces and volume renderings, and discuss how these artifacts relate to the filter kernels corresponding to the subdivision schemes.

Scaled teleoperation is increasingly prevalent in medicine, as well as in other applications of robotics. Visual feedback in such systems is essential and should make maximal use of natural hand-eye coordination. This paper describes a new method of visual feedback for scaled teleoperation in which the operator manipulates the handle of a remote tool in the presence of a registered virtual image of the target in real time. The method adapts a concept already used successfully in a new medical device called the Sonic Flashlight, which permits direct in situ visualization of ultrasound during invasive procedures. The Sonic Flashlight uses a flat-panel monitor and a half-silvered mirror to merge the visual outer surface of a patient with a simultaneous ultrasound scan of the patient's interior. Adapting the concept to scaled teleoperation involves removing the imaging device and the target to a remote location and adding a master-slave control device. This permits the operator to see his hands, along with what appears to be the tool, and the target, merged in a workspace that preserves natural hand-eye coordination. Three functioning prototypes are described, one based on ultrasound and two on light microscopy. The limitations and potential of the new approach are discussed.

True real-time animation of complex hairstyles on animated characters is the goal of this work, and the challenge is to build a mechanical model of the hairstyle which is sufficiently fast for real-time performance while preserving the particular behavior of the hair medium and maintaining sufficient versatility for simulating any kind of complex hairstyles. Rather than building a complex mechanical model directly related to the structure of the hair strands, we take advantage of a volume free-form deformation scheme. We detail the construction of an efficient lattice mechanical deformation model which represents the volume behavior of the hair strands. The lattice is deformed as a particle system using state-of-the-art numerical methods, and animates the hairs using quadratic B-Spline interpolation. The hairstyle reacts to the body skin through collisions with a metaball-based approximation. The model is highly scalable and allows hairstyles of any complexity to be simulated in any rendering context with the appropriate trade off between accuracy and computation speed, fitting the need of Level-of-Detail optimization schemes.

A crucial step in volume rendering is the design of transfer functions that will highlight those aspects of the volume data that are of interest to the user. For many applications, boundaries carry most of the relevant information. Reliable detection of boundaries is often hampered by limitations of the imaging process, such as blurring and noise. We present a method to identify the materials that form the boundaries. These materials are then used in a new domain that facilitates interactive and semiautomatic design of appropriate transfer functions. We also show how the obtained boundary information can be used in region-growing-based segmentation.

High-throughput experiments, such as gene expression microarrays in the life sciences, result in very large data sets. In response, a wide variety of visualization tools have been created to facilitate data analysis. A primary purpose of these tools is to provide biologically relevant insight into the data. Typically, visualizations are evaluated in controlled studies that measure user performance on predetermined tasks or using heuristics and expert reviews. To evaluate and rank bioinformatics visualizations based on real-world data analysis scenarios, we developed a more relevant evaluation method that focuses on data insight. This paper presents several characteristics of insight that enabled us to recognize and quantify it in open-ended user tests. Using these characteristics, we evaluated five microarray visualization tools on the amount and types of insight they provide and the time it takes to acquire it. The results of the study guide biologists in selecting a visualization tool based on the type of their microarray data, visualization designers on the key role of user interaction techniques, and evaluators on a new approach for evaluating the effectiveness of visualizations for providing insight. Though we used the method to analyze bioinformatics visualizations, it can be applied to other domains.

Diffusion Tensor Imaging (DTI) is a magnetic resonance imaging method that can be used to measure local information about the structure of white matter within the human brain. Combining DTI data with the computational methods of MR tractography, neuroscientists can estimate the locations and sizes of nerve bundles (white matter pathways) that course through the human brain. Neuroscientists have used visualization techniques to better understand tractography data, but they often struggle with the abundance and complexity of the pathways. In this paper, we describe a novel set of interaction techniques that make it easier to explore and interpret such pathways. Specifically, our application allows neuroscientists to place and interactively manipulate box or ellipsoid-shaped regions to selectively display pathways that pass through specific anatomical areas. These regions can be used in coordination with a simple and flexible query language which allows for arbitrary combinations of these queries using Boolean logic operators. A representation of the cortical surface is provided for specifying queries of pathways that may be relevant to gray matter structures and for displaying activation information obtained from functional magnetic resonance imaging. By precomputing the pathways and their statistical properties, we obtain the speed necessary for interactive question-and-answer sessions with brain researchers. We survey some questions that researchers have been asking about tractography data and show how our system can be used to answer these questions efficiently.

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

In AR systems, registration is one of the most difficult problems currently limiting their application. In this paper, we propose a simple registration method using projective reconstruction. This method consists of two steps: embedding and tracking. Embedding involves specifying four points to build the world coordinate system on which a virtual object will be superimposed. In tracking, a projective reconstruction technique is used to track these four specified points to compute the model view transformation for augmentation. This method is simple, as only four points need to be specified at the embedding stage and the virtual object can then be easily augmented onto a real scene from a video sequence. In addition, it can be extended to a scenario using the projective matrix that has been obtained from previous registration results using the same AR system. The proposed method has three advantages: 1) It is fast because the linear least square method can be used to estimate the related matrix in the algorithm and it is not necessary to calculate the fundamental matrix in the extended case. 2) A virtual object can still be superimposed on a related area even if some parts of the specified area are occluded during the whole process. 3) This method is robust because it remains effective even when not all the reference points are detected during the whole process, as long as at least six pairs of related reference points correspondences can be found. Some experiments have been conducted to validate the performance of the proposed method.

We present a new algorithm for view-dependent level-of-detail rendering of meshes. Not only can it effectively resolve complex geometry features similar to edge collapse-based schemes, but it also produces meshes that modern graphics hardware can render efficiently. This is accomplished through a novel hybrid approach: For each frame, we view-dependently refine the progressive mesh (PM) representation of the original mesh and use the output as the base domain of uniform regular refinements. The algorithm exploits frame-to-frame coherence and only updates portions of the output mesh corresponding to modified domain triangles. The PM representation is built using a custom volume preservation-based error function. A simple k-d tree enhanced jump-and-walk scheme is used to quickly map from the dynamic base domain to the original mesh during regular refinements. In practice, the PM refinement provides a view-optimized base domain for later regular refinements. The regular refinements ensure almost-everywhere regularity of output meshes, allowing optimization for vertex cache coherence and caching of geometry data in high-performance graphics memory. Combined, they also have the effect of allowing our algorithm to operate on uniform clusters of triangles instead of individual ones, reducing CPU workload.

In this paper, we present an image-based framework that acquires the reflectance properties of a human face. A range scan of the face is not required. Based on a morphable face model, the system estimates the 3D shape and establishes point-to-point correspondence across images taken from different viewpoints and across different individuals' faces. This provides a common parameterization of all reconstructed surfaces that can be used to compare and transfer BRDF data between different faces. Shape estimation from images compensates deformations of the face during the measurement process, such as facial expressions. In the common parameterization, regions of homogeneous materials on the face surface can be defined a priori. We apply analytical BRDF models to express the reflectance properties of each region and we estimate their parameters in a least-squares fit from the image data. For each of the surface points, the diffuse component of the BRDF is locally refined, which provides high detail. We present results for multiple analytical BRDF models, rendered at novel orientations and lighting conditions.

Harvesting the power of modern graphics hardware to solve the complex problem of real-time rendering of large unstructured meshes is a major research goal in the volume visualization community. While, for regular grids, texture-based techniques are well-suited for current GPUs, the steps necessary for rendering unstructured meshes are not so easily mapped to current hardware. We propose a novel volume rendering technique that simplifies the CPU-based processing and shifts much of the sorting burden to the GPU, where it can be performed more efficiently. Our hardware-assisted visibility sorting algorithm is a hybrid technique that operates in both object-space and image-space. In object-space, the algorithm performs a partial sort of the 3D primitives in preparation for rasterization. The goal of the partial sort is to create a list of primitives that generate fragments in nearly sorted order. In image-space, the fragment stream is incrementally sorted using a fixed-depth sorting network. In our algorithm, the object-space work is performed by the CPU and the fragment-level sorting is done completely on the GPU. A prototype implementation of the algorithm demonstrates that the fragment-level sorting achieves rendering rates of between one and six million tetrahedral cells per second on an ATI Radeon 9800.

We present an image-based method for propagating area light illumination through a Layered Depth Image (LDI) to generate soft shadows from opaque and nonrefractive transparent objects. In our approach, using the depth peeling technique, we render an LDI from a reference light sample on a planar light source. Light illumination of all pixels in an LDI is then determined for all the other sample points via warping, an image-based rendering technique, which approximates ray tracing in our method. We use an image-warping equation and McMillan's warp ordering algorithm to find the intersections between rays and polygons and to find the order of intersections. Experiments for opaque and nonrefractive transparent objects are presented. Results indicate our approach generates soft shadows fast and effectively. Advantages and disadvantages of the proposed method are also discussed.

Unsteady flow line integral convolution (UFLIC) is a texture synthesis technique for visualizing unsteady flows with high temporal-spatial coherence. Unfortunately, UFLIC requires considerable time to generate each frame due to the huge amount of pathline integration that is computed for particle value scattering. This paper presents Accelerated UFLIC (AUFLIC) for near interactive (1 frame/second) visualization with 160,000 particles per frame. AUFLIC reuses pathlines in the value scattering process to reduce computationally expensive pathline integration. A flow-driven seeding strategy is employed to distribute seeds such that only a few of them need pathline integration while most seeds are placed along the pathlines advected at earlier times by other seeds upstream and, therefore, the known pathlines can be reused for fast value scattering. To maintain a dense scattering coverage to convey high temporal-spatial coherence while keeping the expense of pathline integration low, a dynamic seeding controller is designed to decide whether to advect, copy, or reuse a pathline. At a negligible memory cost, AUFLIC is 9 times faster than UFLIC with comparable image quality.

Various acquisition, analysis, visualization, and compression approaches sample surfaces of 3D shapes in a uniform fashion without any attempt to align the samples with sharp edges or to adapt the sampling density to the surface curvature. Consequently, triangle meshes that interpolate these samples usually chamfer sharp features and exhibit a relatively large error in their vicinity. We present two new filters that improve the quality of these resampled models. EdgeSharpener restores the sharp edges by splitting the chamfer edges and forcing the new vertices to lie on intersections of planes extending the smooth surfaces incident upon these chamfers. Bender refines the resulting triangle mesh using an interpolating subdivision scheme that preserves the sharpness of the recovered sharp edges while bending their polyline approximations into smooth curves. A combined Sharpen&Bend postprocessing significantly reduces the error produced by feature-insensitive sampling processes. For example, we have observed that the mean-squared distortion introduced by the SwingWrapper remeshing-based compressor can often be reduced by 80 percent executing EdgeSharpener alone after decompression. For models with curved regions, this error may be further reduced by an additional 60 percent if we follow the EdgeSharpening phase by Bender.

Multiprojector, large-scale displays are used in scientific visualization, virtual reality, and other visually intensive applications. In recent years, a number of camera-based computer vision techniques have been proposed to register the geometry and color of tiled projection-based display. These automated techniques use cameras to "calibrate" display geometry and photometry, computing per-projector corrective warps and intensity corrections that are necessary to produce seamless imagery across projector mosaics. These techniques replace the traditional labor-intensive manual alignment and maintenance steps, making such displays cost-effective, flexible, and accessible. In this paper, we present a survey of different camera-based geometric and photometric registration techniques reported in the literature to date. We discuss several techniques that have been proposed and demonstrated, each addressing particular display configurations and modes of operation. We overview each of these approaches and discuss their advantages and disadvantages. We examine techniques that address registration on both planar (video walls) and arbitrary display surfaces and photometric correction for different kinds of display surfaces. We conclude with a discussion of the remaining challenges and research opportunities for multiprojector displays.

To make a spectral representation of color practicable for volume rendering, a new low-dimensional subspace method is used to act as the carrier of spectral information. With that model, spectral light material interaction can be integrated into existing volume rendering methods at almost no penalty. In addition, slow rendering methods can profit from the new technique of postillumination-generating spectral images in real-time for arbitrary light spectra under a fixed viewpoint. Thus, the capability of spectral rendering to create distinct impressions of a scene under different lighting conditions is established as a method of real-time interaction. Although we use an achromatic opacity in our rendering, we show how spectral rendering permits different data set features to be emphasized or hidden as long as they have not been entirely obscured. The use of postillumination is an order of magnitude faster than changing the transfer function and repeating the projection step. To put the user in control of the spectral visualization, we devise a new widget, a "light-dial," for interactively changing the illumination and include a usability study of this new light space exploration tool. Applied to spectral transfer functions, different lights bring out or hide specific qualities of the data. In conjunction with postillumination, this provides a new means for preparing data for visualization and forms a new degree of freedom for guided exploration of volumetric data sets.