IEEE Transactions on Visualization and Computer Graphics

PrePrint: A Visual Analytics Approach to Understanding Spatiotemporal Hotspots

As data sources become larger and more complex, the ability to effectively explore and analyze patterns amongst varying sources becomes a critical bottleneck in analytic reasoning. Incoming data contains multiple variables, high signal to noise ratio, and a degree of uncertainty, all of which hinder exploration, hypothesis testing, and decision making. To facilitate the exploration of such data, advanced tool sets are needed that allow the user to interact with their data in a visual environment that provides direct analytic capability for finding data aberrations or hotspots. In this paper, we present a suite of tools designed to facilitate the exploration of spatiotemporal datasets. Our system allows users to search for hotspots in both space and time, combining linked views and interactive filtering to provide users with contextual information about their data and allow the user to develop and explore their hypotheses. Statistical data models and alert detection algorithms are provided to help draw user attention to critical areas. Demographic filtering can then be further applied as hypotheses generated become fine tuned. This paper demonstrates the use of such tools on multiple geo-spatiotemporal datasets.

IEEE Transactions on Visualization and Computer Graphics - January/February 2010 (Vol. 16, No. 1)

PrePrint: Modeling Repetitive Motions Using Structured Light

Obtaining models of dynamic 3D objects is an important part of content generation for computer graphics. Numerous methods have been extended from static scenarios to model dynamic scenes. If the states or poses of the dynamic object repeat often during a sequence (but not necessarily periodically), we call such a repetitive motion. There are many objects, such as toys, machines, and humans, undergoing repetitive motions. Our key observation is that when a motion state repeats, we can sample the scene under the same motion state again but using a different set of parameters; thus providing more information of each motion state. This enables robustly acquiring dense 3D information difficult for objects with repetitive motions using only simple hardware. After the motion sequence, we group temporally disjoint observations of the same motion state together and produce a smooth space-time reconstruction of the scene. Effectively, the dynamic scene modeling problem is converted to a series of static scene reconstructions, which are easier to tackle. The varying sampling parameters can be, for example, structured-light patterns, illumination directions, and viewpoints resulting in different modeling techniques. Based on this observation, we present an image-based motion state framework and demonstrate our paradigm using either a synchronized or an unsynchronized structured-light acquisition method.

PrePrint: Topology-Aware Evenly-Spaced Streamline Placement

This paper presents a new streamline placement algorithm that produces evenly-spaced long streamlines while preserving topological features of a flow field. Singularities and separatrices are extracted to decompose the flow field into topological regions. In each region, a seeding path is selected from a set of streamlines integrated in the orthogonal flow field. The uniform sample points on this path are then used as seeds to generate streamlines in the original flow field. Additional seeds are placed where a large gap between adjacent streamlines occurs. The number of short streamlines is significantly reduced as evenly-spaced long streamlines spawned along the seeding paths can fill the topological regions very well. Several metrics for evaluating streamline placement quality are discussed and applied to our method as well as some other approaches. Compared to previous work in uniform streamline placement, our method is more effective in creating evenly-spaced long streamlines and preserving topological features. It has the potential to provide both intuitive perception of important flow characteristics and detail reconstruction across visually pleasing streamlines.

PrePrint: Unicube for Dynamic Environment Mapping

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 non-rectilinear 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 look-up vector before the conventional cube map look-up process. Hence, unicube mapping fully exploits the cube map hardware for real-time filtering and look-up. 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.

PrePrint: Sample-Based Surface Coloring

In this paper we present a sample-based approach for surface coloring, which is independent of the original surface resolution and representation. To achieve this, we introduce the Orthogonal Fragment Buffer (OFB)—an extension of the Layered Depth Cube—as a high-resolution view-independent surface representation. The OFB is a data structure that stores surface samples at a nearly uniform distribution over the surface, and it is specifically designed to support efficient random read/write access to these samples. The data access operations have a complexity that is logarithmic in the depth complexity of the surface. Thus, compared to data access operations in tree data structures like octrees, data-dependent memory access patterns are greatly reduced. Due to the particular sampling strategy that is employed to generate an OFB, it also maintains sample coherence and thus exhibits very good spatial access locality. Therefore, OFB-based surface coloring performs significantly faster than sample-based approaches using tree structures. In addition, since in an OFB the surface samples are internally stored in uniform 2D grids, OFB-based surface coloring can efficiently be realized on the GPU to enable interactive coloring of high-resolution surfaces. On the OFB we introduce novel algorithms for color painting using volumetric and surface-aligned brushes, and we present new approaches for particle-based color advection along surfaces in real-time.

PrePrint: Visual Integration of Quantitative Proteomic Data, Pathways and Protein Interactions

We introduce several novel visualization and interaction paradigms for visual analysis of published protein-protein interaction networks, canonical signaling pathway models, and quantitative proteomic data. We evaluate them anecdotally with domain scientists to demonstrate their ability to accelerate the proteomic analysis process. Our results suggest that structuring protein interaction networks around canonical signaling pathway models, exploring pathways globally and locally at the same time, and driving the analysis primarily by the experimental data, all accelerate the understanding of protein pathways. Concrete proteomic discoveries within T-cells, mast cells, and the insulin signaling pathway validate the findings. The aim of the paper is to introduce novel protein network visualization paradigms and anecdotally asses the benefit of incorporating them into established proteomic applications. We also make available a prototype implementation of our methods, to be used and evaluated by the proteomic community.

PrePrint: A Comparison of Gradient Estimation Methods for Volume Rendering on Unstructured Meshes

This paper presents a study of gradient estimation methods for rendering unstructured-mesh volume data. Gradient estimation is necessary for rendering shaded isosurfaces and specular highlights, which provide important cues for shape and depth. Gradient estimation has been widely studied and deployed for regular-grid volume data to achieve local illumination effects, but has been otherwise for unstructured-mesh data. As a result, most of the unstructured-mesh volume visualizations made so far were unlit. In this paper, we present a comprehensive study of gradient estimation methods for unstructured meshes with respect to their cost and performance. Through a number of benchmarks, we discuss the effects of mesh quality and scalar function complexity in the accuracy of the reconstruction, and their impact in lighting-enabled volume rendering. Based on our study, we also propose two heuristic improvements to the gradient reconstruction process. The first heuristic improves the rendering quality with a hybrid algorithm that combines the results of the multiple reconstruction methods, based on the properties of a given mesh. The second heuristic improves the efficiency of its GPU implementation, by restricting the computation of the gradient on a fixed-size local neighborhood.

PrePrint: Principles and Tools for Collaborative Entity-Based Intelligence Analysis

Software tools that make it easier for analysts to collaborate as a natural part of their work will lead to better analysis that is informed by more perspectives. We are interested to know if software tools can be designed that support collaboration even as they allow analysts to find documents and organize information (including evidence, schemas, and hypotheses). We have modified the Entity Workspace system, described previously, to test such designs. We have evaluated the resulting design in both a laboratory study and a study where it is situated with an analysis team. In both cases, effects on collaboration appear to be positive. Key aspects of the design include an evidence notebook optimized for organizing entities (rather than text characters), information structures that can be collapsed and expanded, visualization of evidence that emphasizes events and documents (rather than emphasizing the entity graph), and a notification system that finds entities of mutual interest to multiple analysts. Long-term tests suggest that this approach can support both top-down and bottom-up styles of analysis.

PrePrint: A Level Set Formulation of Geodesic Curvature Flow on Simplicial Surfaces

Curvature flow (planar geometric heat flow) has been extensively applied to image processing, computer vision and material science. To extend the numerical schemes and algorithms of this flow on surfaces is very significant for corresponding motions of curves and images defined on surfaces. In this work, we are interested in the geodesic curvature flow over triangulated surfaces using a level set formulation. Firstly, we present the geodesic curvature flow equation on general smooth manifolds based on an energy minimization of curves. The equation is then discretized by a semi-implicit finite volume method (FVM). For convenience of description, we call the discretized geodesic curvature flow as \textit{dGCF}. The existence and uniqueness of dGCF are discussed. The regularization behavior of dGCF is also studied. Finally we apply our dGCF to three problems: the closed curve evolution on manifolds, the discrete scale-space construction, and the edge detection of images painted on triangulated surfaces. Our method works for compact triangular meshes of arbitrary geometry and topology, as long as there are no degenerate triangles. The implementation of the method is also simple.

PrePrint: Two Fast Methods for High-Quality Line Visibility

Lines drawn over or in place of shaded 3D models can often provide greater comprehensibility and stylistic freedom than shading alone. A substantial challenge for making stylized line drawings from 3D models is the visibility computation. Current algorithms for computing line visibility in models of moderate complexity are either too slow for interactive rendering, or too brittle for coherent animation. We introduce two methods that exploit graphics hardware to provide fast and robust line visibility. First we present a simple shader that performs a visibility test for high-quality, simple lines drawn with the conventional implementation. Next we offer a full optimized pipeline that supports line visibility and a broad range of stylization options.

PrePrint: Real Time Detection and Tracking for Augmented Reality on Mobile Phones

In this paper we present three techniques for 6DOF natural feature tracking in real-time on mobile phones. We achieve interactive frame rates of up to 30Hz for natural feature tracking from textured planar targets on current-generation phones. We use an approach based on heavily modified state-of-the-art feature descriptors, namely SIFT and Ferns plus a template matching -based tracker. While SIFT is known to be a strong, but computationally expensive feature descriptor, Ferns classification is fast, but requires large amounts of memory. This renders both original designs unsuitable for mobile phones. We give detailed descriptions on how we modified both approaches to make them suitable for mobile phones. The template-based tracker further increases the performance and robustness of the SIFT and Ferns based approaches. We present evaluations on robustness and performance and discuss their appropriateness for Augmented Reality applications.

PrePrint: Representation-Independent In-Place Magnification with Sigma Lenses

Focus+context interaction techniques based on the metaphor of lenses are used to navigate and interact with objects in large information spaces. They provide in-place magnification of a region of the display without requiring users to zoom into the representation and consequently lose context. In order to avoid occlusion of its immediate surroundings, the magnified region is often integrated in the context using smooth transitions based on spatial distortion. Such lenses have been developed for various types of representations using techniques often tightly coupled with the underlying graphics framework. We describe a representation-independent solution that can be implemented with minimal effort in different graphics frameworks, ranging from 3D graphics to rich multi-scale 2D graphics combining text, bitmaps and vector graphics. Our solution is not limited to spatial distortion and provides a unified model that makes it possible to define new focus+context interaction techniques based on lenses whose transition is defined by a combination of dynamic displacement and compositing functions. We present the results of a series of user evaluations that show that one such new lens, the speed-coupled blending lens, significantly outperforms all others.

PrePrint: Interactive Indirect Illumination Using Adaptive Multiresolution Splatting

Global illumination provides a visual richness not achievable with the direct illumination models used by most interactive applications. To generate global effects, numerous approximations attempt to reduce global illumination costs to levels feasible in interactive contexts. One such approximation, reflective shadow maps, samples a shadow map to identify secondary light sources whose contributions are splatted into eye-space. This splatting introduces significant overdraw that is usually reduced by artificially shrinking each splat's radius of influence. This paper introduces a new, multi-resolution approach for interactively splatting indirect illumination. Instead of reducing GPU fill rate by reducing splat size, we reduce fill rate by rendering splats into a multi-resolution buffer. This takes advantage of the low-frequency nature of diffuse and glossy indirect lighting, allowing rendering of indirect contributions at low resolution where lighting changes slowly and at high resolution near discontinuities. Because this multi-resolution rendering occurs on a per-splat basis, we can significantly reduce fill rate without arbitrarily clipping splat contributions below a given threshold - those regions simply are rendered at a coarse resolution.

PrePrint: Almost Isometric Mesh Parameterization through Abstract Domains

In this paper we propose a robust, automatic technique to build a global hi-quality parameterization of a two-manifold triangular mesh. An adaptively chosen 2D domain of the parameterization is built as part of the process. The produced parameterization exhibits very low isometric distortion, because it is globally optimized to preserve both areas and angles. The domain is a collection of equilateral triangular 2D regions enriched with explicit adjacency relationships (it is abstract in the sense that no 3D embedding is necessary). It is tailored to minimize isometric distortion, resulting in excellent parameterization qualities, even when meshes with complex shape and topology are mapped into domains composed of a small number of large continuous regions. Moreover, this domain is in turn remapped into a collection of 2D square regions, unlocking many advantages found in quad-based domains (e.g. ease of packing). The technique is tested on a variety of cases, including challenging ones, and compares very favorably with known approaches. An open source implementation is made available.

PrePrint: A Novel Prototype for an Optical See-Through Head-Mounted Display with Addressable Focus Cues

We present the design and implementation of an optical see-through head mounted display (HMD) with addressable focus cues utilizing a liquid lens. We implemented a monocular bench prototype capable of addressing the focal distance of the display from infinity to as close as 8 diopters. Two operation modes of the system were demonstrated: a vari-focal plane mode in which the accommodation cue is addressable, and a time-multiplexed multi-focal plane mode in which both the accommodation and retinal blur cues can be rendered. We further performed experiments to assess the depth perception and eye accommodative response of the system operated in a vari-focal plane mode. Both subjective and objective measurements suggest that the perceived depths and accommodative responses of the user match with the rendered depths of the virtual display with addressable accommodation cues, approximating the real-world 3-D viewing condition.

PrePrint: Cross-Filtered Views for Multidimensional Visual Analysis

Analysis of multidimensional data often requires careful examination of relationships across dimensions. Coordinated multiple view approaches have become commonplace in visual analysis tools because they directly support expression of complex multidimensional queries using simple interactions. However, generating such tools remains difficult because of the need to map domain-specific data structures and semantics into the idiosyncratic combinations of interdependent data and visual abstractions needed to reveal particular patterns and distributions in cross-dimensional relationships. This paper describes: (1) a method for interactively expressing sequences of multidimensional set queries by cross-filtering data values across pairs of views, and (2) design strategies for constructing coordinated multiple view interfaces for cross-filtered visual analysis of multidimensional data sets. Using examples of cross-filtered visualizations of data from several different domains, we describe how cross-filtering can be modularized and reused across designs, flexibly customized with respect to data types across multiple dimensions, and incorporated into more wide-ranging multiple view designs. We also identify several important limitations of the approach. The demonstrated analytic utility of these examples suggest that cross-filtering is a suitable design pattern for instantiation in a wide variety of visual analysis tools.

PrePrint: Evaluation of the Cognitive Effects of Travel Technique in Complex Real and Virtual Environments

We report a series of experiments conducted to investigate the effects of travel technique on information gathering and cognition in complex virtual environments. In the first experiment, participants completed a non-branching multi-level 3D maze at their own pace using either real walking or one of two virtual travel techniques. In the second experiment, we constructed a real world maze with branching pathways and modeled an identical virtual environment. Participants explored either the real or virtual maze for a predetermined amount of time using real walking or a virtual travel technique. Our results across experiments suggest that for complex environments requiring a large a number of turns, virtual travel is an acceptable substitute for real walking if the goal of the application involves learning or reasoning based on information presented in the virtual world. However, for applications that require fast, efficient navigation or travel that closely resembles real world behavior, real walking has advantages over common joystick-based virtual travel techniques.

PrePrint: Globally Optimized Linear Windowed Tone-Mapping

This paper introduces a new tone-mapping operator that performs local linear adjustments on small overlapping windows over the entire input image. While each window applies a local linear adjustment that preserves the monotonicity of the radiance values, the problem is implicitly cast as one of global optimization that satisfies the local constraints defined on each of the overlapping windows. Local constraints take the form of a guidance map that can be used to effectively suppress local high contrast while preserving details. Using this method, image structures can be preserved even in challenging high dynamic range (HDR) images that contain either abrupt radiance change, or relatively smooth but salient transitions. Another benefit of our formulation is that it can be used to synthesis HDR images from low dynamic range (LDR) images.

PrePrint: Scalable L-infinite Coding of Meshes

The paper investigates the novel concept of local error control in mesh geometry encoding. In contrast to traditional mesh coding systems that use the mean-square error as target distortion metric, this paper proposes a new L-infinite mesh coding approach, for which the target distortion metric is the L-infinite distortion. In this context, a novel wavelet-based L-infinite-constrained coding approach for meshes is proposed, which ensures that the maximum error between the vertex positions in the original and decoded meshes is lower than a given upper-bound. Furthermore, the proposed system achieves scalability in L-infinite sense, that is, any decoding of the input stream will correspond to a perfectly predictable L-infinite distortion upper-bound. An instantiation of the proposed L-infinite coding approach is demonstrated for MESHGRID, which is a scalable 3D object encoding system, part of MPEG-4 AFX. In this context, the advantages of scalable L-infinite coding over L-2-oriented coding are experimentally demonstrated. One concludes that the proposed L-infinite mesh coding approach guarantees an upper-bound on the local error in the decoded mesh, it enables a fast real-time implementation of the rate-allocation, and it preserves all the scalability features and animation capabilities of the employed scalable mesh codec.

PrePrint: Real-Time Rendering Method and Performance Evaluation of Composable 3D Lenses for Interactive VR

We present and evaluate a new approach for real-time rendering of composable 3D lenses for polygonal scenes. Although composition of 2D lenses is well known, 3D composition was long considered infeasible due to both geometric and semantic complexity. Nonetheless, for a scene with multiple interactive 3D lenses, the problem of intersecting lenses must be considered. Intersecting 3D lenses in meaningful ways supports new interfaces such as hierarchical 3D windows, 3D lenses for managing and composing visualization options, or interactive shader development by direct manipulation of lenses providing component effects. Our 3D volumetric lens approach differs fundamentally from others and is one of the first to address efficient composition. It is well-suited to head-tracked VR because it requires no view-dependent generation of extra data structures, allowing caching and reuse of full or partial results. A Shader Factory module composes shader programs for rendering composite visual styles and geometry of intersection regions. Geometry is handled by Boolean combinations of region tests in fragment shaders, which allows both convex and non-convex CSG volumes for lens shape. Efficiency is further addressed by a Region Analyzer module and by broad-phase culling. Finally, we consider the handling of order effects for composed 3D lenses.

PrePrint: A Point Cloud Based Multi-View Stereo Algorithm for Free-Viewpoint Video

This paper presents a robust multi-view stereo (MVS) algorithm for free-viewpoint video. Our MVS scheme is totally point cloud based, and consists of three stages: point cloud extraction, merging and meshing. To guarantee reconstruction accuracy, point clouds are first extracted according to a stereo matching metric which is robust to noise, occlusion and lack of texture. Visual hull information, frontier points and implicit points are then detected and fused with point fidelity information in the merging and meshing steps. All aspects of our method are designed to counteract potential challenges in MVS datasets for accurate and complete model reconstruction. Experimental results demonstrate that, our technique produces the most competent performance among current algorithms under sparse viewpoint setups according to both static and motion MVS datasets.

PrePrint: An Evaluation of Prefiltered B-Spline Reconstruction for Quasi-Interpolation on the Body-Centered Cubic Lattice

In this paper, we demonstrate that quasi-interpolation of orders two and four can be efficiently implemented on the Body-Centered Cubic (BCC) lattice by using tensor-product B-splines combined with appropriate discrete prefilters. Unlike the non-separable box-spline reconstruction previously proposed for the BCC lattice, the prefiltered B-spline reconstruction can utilize the fast trilinear texture-fetching capability of the recent graphics cards. Therefore it can be applied for rendering BCC-sampled volumetric data interactively. Furthermore, we show that a separable B-spline filter can suppress the postaliasing effect much more isotropically than a non-separable box-spline filter of the same approximation power. Although prefilters that make the B-splines interpolating on the BCC lattice do not exist, we demonstrate that quasi-interpolating prefiltered linear and cubic B-spline reconstructions can still provide higher image quality than the interpolating linear box-spline and prefiltered quintic box-spline reconstructions respectively.

PrePrint: Mélange: Space Folding for Visual Exploration

Navigating in large geometric spaces—such as maps, social networks, or long documents—typically require a sequence of pan and zoom actions. However, this strategy is often ineffective and cumbersome, especially when trying to study and compare several distant objects. We propose a new distortion technique that folds the intervening space to guarantee visibility of multiple focus regions. The folds themselves show contextual information and support unfolding and paging interactions. We conducted a study comparing the space-folding technique to existing approaches, and found that participants performed significantly better with the new technique. We also describe how to implement this distortion technique, and give an in-depth case study on how to apply it to the visualization of large-scale 1D time-series data.

PrePrint: Evolving Mazes from Images

We propose a novel reaction diffusion (RD) simulator to evolve image-resembling mazes. The evolved mazes faithfully preserve the salient interior structures in the source images. As it is difficult to control the generation of desired patterns with traditional reaction diffusion, we develop our RD-simulator using a different computational platform, cellular neural networks. Based on the proposed simulator, we can generate mazes that exhibit both regular and organic look or range from uniform to spatial-varying appearance. Our simulator also provides high controllability of maze appearance. Users can directly and intuitively "paint" the desired appearance of mazes in a spatial-varying manner via a set of brushes. In addition, the evolution nature of our method naturally generates mazes without any obvious seams even though the image is a composite of multiple sources. We validate our method by evolving several interesting mazes from different source images.

PrePrint: Hierarchical Aggregation for Information Visualization: Overview, Techniques and Design Guidelines

We present a model for building, visualizing, and interacting with multiscale representations of information visualization techniques using hierarchical aggregation. The motivation for this work is to make visual representations more visually scalable and less cluttered. The model allows for augmenting existing techniques with multiscale functionality, as well as for designing new visualization and interaction techniques that conform to this new class of visual representations. We give some examples of how to use the model for standard information visualization techniques such as scatterplots, parallel coordinates, and node-link diagrams, and discuss existing techniques that are based on hierarchical aggregation. This yields a set of design guidelines for aggregated visualizations. We also present a basic vocabulary of interaction techniques suitable for navigating these multiscale visualizations.

PrePrint: Real-Time Physics-Based 3D Biped Character Animation Using an Inverted Pendulum Model

We present a physics-based approach to generate 3D biped character animation that can react to dynamical environments in real-time. Our approach utilizes an inverted pendulum model to online adjust the desired motion trajectory from the input motion capture data. This on-line adjustment produces a physically-plausible motion trajectory adapted to dynamic environments, which is then used as the desired motion for the motion controllers to track in dynamics simulation. Rather than using Proportional-Derivative controllers whose parameters usually cannot be easily set, our motion tracking adopts a velocity-driven method which computes joint torques based on the desired joint angular velocities. Physically-correct full body motion of the 3D character is computed in dynamics simulation using the computed torques and dynamical model of the character. Our experiments demonstrate that tracking motion capture data with real-time response animation can be achieved easily. In addition, physically-plausible motion style editing, automatic motion transition, and motion adaptation to different limb sizes can also be generated without difficulty.

PrePrint: Enhanced Voxelization and Representation of Objects with Sharp Details in Truncated Distance Fields

We present a new method for voxelization of solid objects containing sharp details. Voxelization is a sampling process which transforms a continuously defined object into a discrete one represented as a voxel field. The latter can be used for rendering or other purposes which often involve a reconstruction of a continuous approximation of the original object. The objects to be voxelized have to fulfill certain representability conditions for the later reconstruction to be as good as possible. Otherwise, disturbing reconstruction artifacts appear. Our method extends the traditional distance-based voxelization by an a-priori detection of sharp object details and their subsequent modification in such a way that the resulting object to be voxelized fulfills the representability conditions. We represent the resulting discrete objects by means of truncated (i.e. narrow-band) distance fields which provide for reduction of memory requirements and allow for further processing by level-set techniques. This approach is exemplified with two classes of solid objects frequently containing such sharp details: implicit solids and solids resulting from CSG operations. In both cases the sharp details are rounded to a specific curvature determined by the sampling distance.

PrePrint: Yet Faster Ray-Triangle Intersection (Using SSE4)

Ray-triangle intersection is an important algorithm, not only in the field of realistic rendering (based on ray tracing), but also in physics simulation, collision detection, modelling, etc. Obviously, the speed of this well-defined algorithm's implementations is important because calls to such a routine are numerous in rendering and simulation applications. Contemporary fast intersection algorithms, which use SIMD instructions, focus on the intersection of ray packets against triangles. For intersection between single rays and triangles, operations such as horizontal addition or dot product are required. The SSE4 instruction set adds the dot product instruction which can be used for this purpose. This article presents a new modification of the fast ray-triangle intersection algorithms commonly used, which – when implemented on SSE4 – outperforms the current state-of-the-art algorithms. It also allows both a single ray and ray packet intersection calculation with the same precomputed data. The speed gain measurements are described and discussed in the article.

PrePrint: RACBVHs: Random-Accessible Compressed Bounding Volume Hierarchies

We present a novel compressed bounding volume hierarchy (BVH) representation, random-accessible compressed bounding volume hierarchies (RACBVHs), for various applications requiring random access on BVHs of massive models. Our RACBVH representation is compact and transparently supports random access on the compressed BVHs without decompressing the whole BVH. We provide the general BVH access API to transparently access our RACBVH representation. At runtime, our decompression framework is guaranteed to provide correct BV nodes without decompressing the whole BVH. Also, our method is extended to support parallel random access that can utilize the multi-core CPU architecture. Our method can achieve up to a 12:1 compression ratio and, more importantly, can decompress 4.2M BV nodes (= 135 MB) per second by using a single CPU-core. To highlight the benefits of our approach, we apply our method to two different applications: ray tracing and collision detection. We can improve the runtime performance by more than a factor of 4 as compared to using the uncompressed original data. This improvement is a result of the fast decompression performance and reduced data access time by selectively fetching and decompressing small regions of the compressed BVHs requested by applications.

PrePrint: Robust Feature-Preserving Mesh Denoising Based on Consistent Sub-Neighborhoods

In this paper, we introduce a feature-preserving denoising algorithm. It is built on the premise that the underlying surface of a noisy mesh is piecewise smooth, and a sharp feature lies on the intersection of multiple smooth surface regions. A vertex close to a sharp feature is likely to have a neighborhood that includes distinct smooth segments. By defining the consistent sub-neighborhood as the segment whose geometry and normal orientation most consistent with those of the vertex, we can completely remove the influence from neighbors lying on other segments during denoising. Our method identifies piecewise smooth sub-neighborhoods using a robust density-based clustering algorithm based on shared nearest neighbors. In our method, we obtain an initial estimate of vertex normals and curvature tensors by robustly fitting a local quadric model. An anisotropic filter based on optimal estimation theory is further applied to smooth the normal field and the curvature tensor field. This is followed by second-order bilateral filtering, which better preserves curvature details and alleviates volume shrinkage during denoising. The support of these filters is defined by the consistent sub-neighborhood of a vertex. We have applied this algorithm to both generic and CAD models, and sharp features, such as edges and corners, are very well preserved.

PrePrint: Analyzing and Tracking Burning Structures in Lean Premixed Hydrogen Flames

This paper presents topology-based methods to robustly extract, analyze, and track features defined as subsets of isosurfaces. First, we demonstrate how features identified by thresholding isosurfaces can be defined in terms of the Morse complex. Second, we present a specialized hierarchy that encodes the feature segmentation independent of the threshold while still providing a flexible multi-resolution representation. Third, for a given parameter selection we create detailed tracking graphs representing the complete evolution of all features in a combustion simulation over several hundred time steps. Finally, we discuss a user interface that correlates the tracking information with interactive rendering of the segmented isosurfaces enabling an in-depth analysis of the temporal behavior.

PrePrint: Placegram: A Diagrammatic Map for Personal Geotagged Data Browsing

Geotagging personal data such as photos and videos is continuously becoming easier and more popular. Nevertheless, browsing such data on general purpose maps can be difficult, due to the frequent zoom and pan operations as well as extraneous information. This paper presents Placegram, a compact diagrammatic map visualization for personal geotagged data browsing based on cognitive map theories. An evaluation using real-life datasets shows that the speed of finding and pointing to places from the participants' own data increased by a factor of 2.1 to 2.9, and the number of interesting places discovered from others' data within a time limit increased by 48.8% in Placegram compared to a general purpose map. Placegram was even slightly faster than a simple text list, while at the same time preserving the geographic senses of direction and location. Subjective ratings and comments from participants support these results, indicating that Placegram is significantly preferred over both a general map and a text list.

PrePrint: Origamizing Polyhedral Surfaces

This paper presents the first practical method for "origamizing" or obtaining the folding pattern that folds a single sheet of material into a given polyhedral surface without any cut. The basic idea is to tuck fold a planar paper to form a three-dimensional shape. The main contribution is to solve the inverse problem; the input is an arbitrary polyhedral surface and the output is the folding pattern. Our approach is to convert this problem into a problem of laying out the polygons of the surface on a planar paper by introducing the concept of tucking molecules. We investigate the equality and inequality conditions required for constructing a valid crease pattern. We propose an algorithm based on two-step mapping and edge splitting to solve these conditions. The two-step mapping precalculates linear equalities and separates them from other conditions. This allows an interactive manipulation of the crease pattern in the system implementation. We present the first system for designing three-dimensional origami, enabling a user to interactively design complex spatial origami models that have not been realizable thus far.

PrePrint: Route Visualization Using Detail Lenses

We present a method designed to address some limitations of typical route map displays of driving directions. The main goal of our system is to generate a printable version of a route map that shows the overview and detail views of the route within a single, consistent visual frame. Our proposed visualization provides a more intuitive spatial context than a simple list of turns. We present a novel multi-focus technique to achieve this goal, where the foci are defined by points-of-interest (POI) along the route. A detail lens that encapsulates the POI at a finer geospatial scale is created for each focus. The lenses are laid out on the map to avoid occlusion with the route and each other, and to optimally utilize the free space around the route. We define a set of layout metrics to evaluate the quality of a lens layout for a given route map visualization. We compare standard lens layout methods to our proposed method and demonstrate the effectiveness of our method in generating aesthetically pleasing layouts. Finally, we perform a user study to evaluate the effectiveness of our layout choices.

PrePrint: Texture Mapping via Optimal Mass Transport

In this paper, we present a novel method for texture mapping of closed surfaces. Our method is based on the technique of optimal mass transport (also known as the "earth-mover's metric"). This is a classical problem which concerns determining the optimal way, in the sense of minimal transportation cost, of moving a pile of soil from one site to another. In our context, the resulting mapping is area preserving and minimizes angle distortion in the optimal mass sense. Indeed, we first begin with an angle-preserving mapping (which may greatly distort area), and then correct it using the mass transport procedure derived via a certain gradient flow. In order to obtain fast convergence to the optimal mapping we incorporate a multiresolution scheme into our flow. We also use ideas from discrete exterior calculus in our computations.

PrePrint: Meshless Helmholtz-Hodge Decomposition

Vector fields analysis traditionally distinguishes conservative (curl-free) from mass preserving (divergence-free) components. The Helmholtz-Hodge decomposition allows separating any vector field into the sum of three uniquely defined components: curl-free, divergence-free and harmonic. This decomposition is usually achieved by using mesh-based methods such as finite differences or finite elements. This work presents a new meshless approach to the Helmholtz-Hodge decomposition for the analysis of 2D discrete vector fields. It embedds into the SPH particle-based framework. The proposed method is effficient and can be applied to extract features from a 2D discrete vector field and to multiphase fluid flow simulation to ensure incompressibility.

PrePrint: Local Ambient Occlusion in Direct Volume Rendering

This paper presents a novel technique to efficiently compute illumination for Direct Volume Rendering using a local approximation of ambient occlusion to integrate the intensity of incident light for each voxel. An advantage with this local approach is that fully shadowed regions are avoided which is desired in many applications of volume rendering, such as medical visualization. Additional transfer function interactions are also presented, for instance to highlight specific structures with luminous tissue effects and to create an improved context for semi-transparent tissues with a separate absorption control for the illumination settings. Multi-resolution volume management and GPU-based computation are used to accelerate the calculations and to support large data sets. The scheme yields interactive frame rates with an adaptive sampling approach for incrementally refined illumination under arbitrary transfer function changes. The illumination effects can give a better understanding of the shape and density of tissues and so has the potential to increase the diagnostic value of medical volume rendering. Since the proposed method is gradient-free it is especially beneficial at the borders of clip planes, where gradients are undefined, and for noisy datasets.

PrePrint: Real-Time Ray Tracing of Implicit Surfaces on the GPU

Compact representation of geometry using a suitable procedural or mathematical model and a ray-tracing mode of rendering fit the programmable graphics processor units (GPUs) well. Several such representations including parametric and subdivision surfaces have been explored in recent research. The important and widely applicable category of the general implicit surface has received less attention. In this paper, we present a ray-tracing procedure to render general implicit surfaces efficiently on the GPU. Though only the fourth or lower order surfaces can be rendered using analytical roots, our adaptive marching points algorithm can ray-trace arbitrary implicit surfaces without multiple roots, by sampling the ray at selected points till a root is found. Adapting the sampling step size based on a proximity measure and a horizon measure delivers high speed. The sign-test can handle any surface without multiple roots. The Taylor-test that uses ideas from interval analysis can ray-trace many surfaces with complex roots. Overall, a simple algorithm that fits the SIMD architecture of the GPU results in high performance. We demonstrate the ray-tracing of algebraic surfaces up to order 50 and non-algebraic surfaces including a Blinn's blobby with 75 spheres at better than interactive frame rates.

PrePrint: Subdivision Analysis of the Trilinear Interpolant

Isosurfaces are fundamental volumetric visualization tools, and are generated by the well-known Marching Cubes cases that approximate contours of trilinearly-interpolated scalar fields. While a complete set of cases has recently been published by Nielson, the formal proof that these cases are the only ones possible and that they are topologically correct is difficult to follow. We present a more straightforward proof of the correctness and completeness of these cases based on a variation of the Dividing Cubes algorithm. Since this proof is based on topological arguments and a divide-and-conquer approach, this also sets the stage for developing tessellation cases for higher-order interpolants and for the quadrilinear interpolant in four dimensions. We also demonstrate that, apart from degenerate cases, Nielson's cases are in fact subsets of two basic configurations of the trilinear interpolant.