Data analytics is the best approach for extracting hidden patterns and trends from time series data. One strong limitation that restrains the use of the method is the difficulty in selecting the appropriate data when a large variety of records come from several providers. Domain ontologies can organize and offer a uniform view for data analysis without plastering the data in a rigid format. This work describes an innovative visualization platform for data analysis of petroleum production time series that allows the user to explore the semantics of the oil well data with the support of a well-founded domain ontology. The O3PO ontology represents a production plant’s installation assets, describing the equipment’s relevant properties, such as position, relationship with other assets, and sensor measurements. The visualization platform takes advantage of the ontology to assist the user in locating the installation component, equipment, and collected measurements, bringing the time series data to the analytic tool for analysis by various groups. The ontology provides a taxonomy for navigating between classes and subsequently selecting instances, components, and properties. We describe the use of the visualization tool in real-case data from an offshore oilfield in Brazilian Pre-salt. This work contributes to the conception of the next generation of digital twins for the oil and gas industry.

We demonstrate SHEVA, a System for Hypothesis Exploration with Visual Analytics. SHEVA adopts an Exploratory Data Analysis (EDA) approach to discovering statistically-sound insights from large datasets. The system addresses three longstanding challenges in Multiple Hypothesis Testing: (i) the likelihood of rejecting the null hypothesis by chance, (ii) the pitfall of not being representative of the input data, and (iii) the ability to navigate among many data regions while preserving the user's train of thought. To address (i) & (ii), SHEVA implements significance adjustment methods that account for data-informed properties such as coverage and novelty. To address (iii), SHEVA proposes to guide users by recommending one-sample and two-sample hypotheses in a stepwise fashion following a data hierarchy. Users may choose from a collection of pre-trained hypothesis exploration policies and let SHEVA guide them through the most significant hypotheses in the data, or intervene to override suggested hypotheses. Furthermore, SHEVA relies on data-to-visual element mappings to convey hypothesis testing results in an interpretable fashion, and allows hypothesis pipelines to be stored and retrieved later to be tested on new datasets.

Abstract Projections aim to convey the relationships and similarity of high‐dimensional data in a low‐dimensional representation. Most such techniques are designed for static data. When used for time‐dependent data, they usually fail to create a stable and suitable low dimensional representation. We propose two dynamic projection methods (PCD‐tSNE and LD‐tSNE) that use global guides to steer projection points. This avoids unstable movement that does not encode data dynamics while keeping t‐SNE's neighborhood preservation ability. PCD‐tSNE scores a good balance between stability, neighborhood preservation, and distance preservation, while LD‐tSNE allows creating stable and customizable projections. We compare our methods to 11 other techniques using quality metrics and datasets provided by a recent benchmark for dynamic projections.

Abstract Dimensionality reduction methods are an essential tool for multidimensional data analysis, and many interesting processes can be studied as time‐dependent multivariate datasets. There are, however, few studies and proposals that leverage on the concise power of expression of projections in the context of dynamic/temporal data. In this paper, we aim at providing an approach to assess projection techniques for dynamic data and understand the relationship between visual quality and stability. Our approach relies on an experimental setup that consists of existing techniques designed for time‐dependent data and new variations of static methods. To support the evaluation of these techniques, we provide a collection of datasets that has a wide variety of traits that encode dynamic patterns, as well as a set of spatial and temporal stability metrics that assess the quality of the layouts. We present an evaluation of 9 methods, 10 datasets, and 12 quality metrics, and elect the best‐suited methods for projecting time‐dependent multivariate data, exploring the design choices and characteristics of each method. Additional results can be found in the online benchmark repository. We designed our evaluation pipeline and benchmark specifically to be a live resource, open to all researchers who can further add their favorite datasets and techniques at any point in the future.

Abstract Rectangular treemaps are often the method of choice to visualize large hierarchical datasets. Nowadays such datasets are available over time, hence there is a need for (a) treemaps that can handle time‐dependent data, and (b) corresponding quality criteria that cover both a treemap's visual quality and its stability over time. In recent years a wide variety of (stable) treemapping algorithms has been proposed, with various advantages and limitations. We aim to provide insights to researchers and practitioners to allow them to make an informed choice when selecting a treemapping algorithm for specific applications and data. To this end, we perform an extensive quantitative evaluation of rectangular treemaps for time‐dependent data. As part of this evaluation we propose a novel classification scheme for time‐dependent datasets. Specifically, we observe that the performance of treemapping algorithms depends on the characteristics of the datasets used. We identify four potential representative features that characterize time‐dependent hierarchical datasets and classify all datasets used in our experiments accordingly. We experimentally test the validity of this classification on more than 2000 datasets, and analyze the relative performance of 14 state‐of‐the‐art rectangular treemapping algorithms across varying features. Finally, we visually summarize our results with respect to both visual quality and stability to aid users in making an informed choice among treemapping algorithms. All datasets, metrics, and algorithms are openly available to facilitate reuse and further comparative studies.

In recent years sophisticated data structures based on datacubes have been proposed to perform interactive visual exploration of large datasets. While powerful, these approaches overlook the important fact that aggregations used to produce datacubes do not represent the actual distribution of the data being analyzed. As a result, these methods might produce biased results as well as hide important features in the data. In this paper, we introduce the Quantile Datacube Structure (QDS) that bridges this gap by supporting interactive visual exploration based on order statistics. To achieve this, QDS makes use of an efficient non-parametric distribution approximation scheme called p-digest and employs a novel datacube indexing scheme that reduces the memory usage of previous datacube methods. This enables interactive slicing and dicing while accurately approximating the distribution of quantitative variables of interest. We present two case studies that illustrate the ability of QDS to not only build order statistics based visualizations interactively but also to perform event detection on very large datasets. Finally, we present extensive experimental results that validate the effectiveness of QDS regarding memory usage and accuracy in the approximation of order statistics for real-world datasets.

Finding the ideal number of layers and size for each layer is a key challenge in deep neural network design. Two approaches for such networks exist: filter learning and architecture learning. While the first one starts with a given architecture and optimizes model weights, the second one aims to find the best architecture. Recently, several visual analytics (VA) techniques have been proposed to understand the behavior of a network, but few VA techniques support designers in architectural decisions. We propose a hybrid methodology based on VA to improve the architecture of a pre-trained network by reducing/increasing the size and number of layers. We introduce Activation Occurrence Maps that show how likely each image position of a convolutional kernel’s output activates for a given class, and Class Selectivity Maps, that show the selectiveness of different positions in a kernel’s output for a given label. Both maps help in the decision to drop kernels that do not significantly add to the network’s performance, increase the size of a layer having too few kernels, and add extra layers to the model. The user interacts from the first to the last layer, and the network is retrained after each layer modification. We validate our approach with experiments in models trained with two widely-known image classification datasets and show how our method helps to make design decisions to improve or to simplify the architectures of such models.

We demonstrate COVIZ, an interactive system to visually form and explore patient cohorts. COVIZ seamlessly integrates visual cohort formation and exploration, making it a single destination for hypothesis generation. COVIZ is easy to use by medical experts and offers many features: (1) It provides the ability to isolate patient demographics (e.g., their age group and location), health markers (e.g., their body mass index), and treatments (e.g., Ventilation for respiratory problems), and hence facilitates cohort formation; (2) It summarizes the evolution of treatments of a cohort into health trajectories, and lets medical experts explore those trajectories; (3) It guides them in examining different facets of a cohort and generating hypotheses for future analysis; (4) Finally, it provides the ability to compare the statistics and health trajectories of multiple cohorts at once. COVIZ relies on QDS, a novel data structure that encodes and indexes various data distributions to enable their efficient retrieval. Additionally, COVIZ visualizes air quality data in the regions where patients live to help with data interpretations. We demonstrate two key scenarios, ecological scenario and case cross-over scenario . A video demonstration of COVIZ is accessible via http://bit.ly/video-coviz.

We demonstrate VEXUS, an interactive visualization framework for exploring user data to fulfill tasks such as finding a set of experts, forming discussion groups and analyzing collective behaviors. User data is characterized by a combination of demographics like age and occupation, and actions such as rating a movie, writing a paper or following a medical treatment. The ubiquity of user data requires tools that help explorers, be they specialists or novice users, acquire new insights. VEXUS lets explorers interact with user data via visual primitives and builds an exploration profile to recommend the next exploration steps. VEXUS combines state-of-the-art visualization techniques with appropriate indexing of user data to provide fast and relevant exploration.

Dynamic treemaps are one of the methods of choice for displaying large hierarchies that change over time, such as those encoding the structure of evolving software systems. While quality criteria (and algorithms that optimize for them) are known for static trees, far less has been studied for treemapping dynamic trees. We address this gap by proposing a methodology and associated quality metrics to measure the quality of dynamic treemaps for the specific use-case and context of software evolution visualization. We apply our methodology on a benchmark containing a wide range of real-world software repositories and 12 well-known treemap algorithms. Based on our findings, we discuss the observed advantages and limitations of various treemapping algorithms for visualizing software structure evolution, and propose ways for users to choose the most suitable treemap algorithm based on the targeted criteria of interest.

Machine learning algorithms can be expensive to deploy, in particular, those used in robotics applications that perform many variations of the same task. Solutions to one variation of a task may be found via Reinforcement Learning algorithms, and are typically modeled as a vector of N parameters encoding the robot's behavior policy. When N is large or executing robot trials is time-consuming, searching in the space of solutions becomes prohibitively expensive. In this paper, we introduce a method that allows robots to generalize behaviors by analyzing solutions to a small number of previously-trained related tasks. This allows for approximate policies for novel tasks to be rapidly estimated. We present a method that achieves this type of generalization by performing nonlinear regression directly on the policy manifold — i.e., the solution space spanned as we change the parameters describing tasks. Because tasks are typically described by few parameters, the corresponding policy manifold has few degrees of freedom, which leads to low-dimensional surfaces. We exploit this property to construct a function that maps task parameters to policy parameters (a parameterized skill). Our method uses manifold clustering techniques to deal with discontinuous manifolds, a challenging situation arising from physical obstacles or robot constraints. We evaluate our method on a set of robot manipulation tasks and show that it can efficiently estimate policies for novel tasks from a small number of training examples.

We propose Hashedcubes, a data structure that enables real-time visual exploration of large datasets that improves the state of the art by virtue of its low memory requirements, low query latencies, and implementation simplicity. In some instances, Hashedcubes notably requires two orders of magnitude less space than recent data cube visualization proposals. In this paper, we describe the algorithms to build and query Hashedcubes, and how it can drive well-known interactive visualizations such as binned scatterplots, linked histograms and heatmaps. We report memory usage, build time and query latencies for a variety of synthetic and real-world datasets, and find that although sometimes Hashedcubes offers slightly slower querying times to the state of the art, the typical query is answered fast enough to easily sustain a interaction. In datasets with hundreds of millions of elements, only about 2% of the queries take longer than 40ms. Finally, we discuss the limitations of data structure, potential spacetime tradeoffs, and future research directions.

PhenoVis is framework for the visual phenological analysis of forest ecosystems. It contains the chronological percentage maps (CPM), a novel representation that is capable of discovering additional patterns by encoding percentage distributions of the data. Two types of masks are used in PhenoVis: a community mask , which considers all plant species in the image; and a species mask , associated with a given plant species. Among the several images taken at different times of the day, the image taken at noon is preferred for the analysis because it minimizes shadow effects. Therefore, only one image per day is used. The analysis considers the chromatic co- efficients associated with each pixel in the image. In PhenoVis we associate different colors with each bucket of the percentage histogram. The histogram granularity defines the size of a given bucket of the percentage distribution. The number of buckets is given by the number of colors available, and the range of the distribution is given by the IOI. The percentage map of a single input image consists of a normalized stacked bar chart. The chronological percentage map consists of a sequence of percentage maps stacked in chronological order, from top to bottom (portrait) or left to right (landscape).

Abstract The traffic infrastructure greatly impacts the quality of life in urban environments. To optimize this infrastructure, engineers and decision makers need to explore traffic data. In doing so, they face two important challenges: the sparseness of speed sensors that cover only a limited number of road segments, and the complexity of traffic patterns they need to analyze. In this paper we take a first step at addressing these challenges. We use New York City (NYC) taxi trips as sensors to capture traffic information. While taxis provide substantial coverage of the city, the data captured about taxi trips contain neither the location of taxis at frequent intervals nor their routes. We propose an efficient traffic model to derive speed and direction information from these data, and show that it provides reliable estimates. Using these estimates, we define a time‐varying vector‐valued function on a directed graph representing the road network, and adapt techniques used for vector fields to visualize the traffic dynamics. We demonstrate the utility of our technique in several case studies that reveal interesting mobility patterns in NYC's traffic. These patterns were validated by experts from NYC's Department of Transportation and the NYC Taxi & Limousine Commission, who also provided interesting insights into these results.

Abstract Simplicial meshes are useful as discrete approximations of continuous spaces in numerical simulations. In some applications, however, meshes need to be modified over time. Mesh update operations are often expensive and brittle, making the simulations unstable. In this paper we propose a framework for updating simplicial meshes that undergo geometric and topological changes. Instead of explicitly maintaining connectivity information, we keep a collection of weights associated with mesh vertices, using a Weighted Delaunay Triangulation (WDT). These weights implicitly define mesh connectivity and allow direct merging of triangulations. We propose two formulations for computing the weights, and two techniques for merging triangulations, and finally illustrate our results with examples in two and three dimensions.

We propose an approach for verification of volume rendering correctness based on an analysis of the volume rendering integral, the basis of most DVR algorithms. With respect to the most common discretization of this continuous model (Riemann summation), we make assumptions about the impact of parameter changes on the rendered results and derive convergence curves describing the expected behavior. Specifically, we progressively refine the number of samples along the ray, the grid size, and the pixel size, and evaluate how the errors observed during refinement compare against the expected approximation errors. We derive the theoretical foundations of our verification approach, explain how to realize it in practice, and discuss its limitations. We also report the errors identified by our approach when applied to two publicly available volume rendering packages.

Hybrid transparency is an approach for real-time approximation of order-independent transparency. Our hybrid approach combines an accurate compositing, of a few core transparent layers, with a quick approximation, for the remaining layers. Its main advantage, the ability to operate in bounded memory without noticeable artifacts, enables its usage with high scene complexity and image resolution, which other approaches fail to handle. Hybrid transparency is suitable for highly-parallel execution, can be implemented in current GPUs and further improved, with minimal architecture changes. We present quality, memory, and performance analysis and comparisons which demonstrate that hybrid transparency is able to generate high-quality images at competitive frames rates and with the lowest memory consumption among comparable OIT techniques.

Image population analysis is the class of statistical methods that plays a central role in understanding the development, evolution, and disease of a population. However, these techniques often require excessive computational power and memory that are compounded with a large number of volumetric inputs. Restricted access to supercomputing power limits its influence in general research and practical applications. In this paper we introduce ISP, an Image-Set Processing streaming framework that harnesses the processing power of commodity heterogeneous CPU/GPU systems and attempts to solve this computational problem. In ISP, we introduce specially designed streaming algorithms and data structures that provide an optimal solution for out-of-core multiimage processing problems both in terms of memory usage and computational efficiency. ISP makes use of the asynchronous execution mechanism supported by parallel heterogeneous systems to efficiently hide the inherent latency of the processing pipeline of out-of-core approaches. Consequently, with computationally intensive problems, the ISP out-of-core solution can achieve the same performance as the in-core solution. We demonstrate the efficiency of the ISP framework on synthetic and real datasets.

Abstract The parallel vectors (PV) operator is a feature extraction approach for defining line‐type features such as creases (ridges and valleys) in scalar fields, as well as separation, attachment, and vortex core lines in vector fields. In this work, we extend PV feature extraction to higher‐order data represented by piecewise analytical functions defined over grid cells. The extraction uses PV in two distinct stages. First, seed points on the feature lines are placed by evaluating the inclusion form of the PV criterion with reduced affine arithmetic. Second, a feature flow field is derived from the higher‐order PV expression where the features can be extracted as streamlines starting at the seeds. Our approach allows for guaranteed bounds regarding accuracy with respect to existence, position, and topology of the features obtained. The method is suitable for parallel implementation and we present results obtained with our GPU‐based prototype. We apply our method to higher‐order data obtained from discontinuous Galerkin fluid simulations.

THIS special section on Parallel Graphics and Visualization features extended versions of three selected papers from the Eurographics Symposium on Parallel Graphics and Visualization (EGPGV) in 2009. EGPGV 2009 was held in Munich, Germany, from 29-30 March 2009. It was the ninth event of this successful series of symposia, and was colocated with the Eurographics Annual Conference, which took place from 30 March to 3 April 2009. More information on EGPGV and its supporting Eurographics Working Group on Parallel Graphics can be found at http:// www.egpgv.org. EGPGV 2009 received 27 full paper submissions, which were reviewed by an International Program Committee with 23 members and by the three editors of the symposium proceedings (the symposium chair and the two paper cochairs). Each submission received three or more reviews, culminating with a final program that contained 14 papers, for an acceptance rate just short of 52 percent. Accepted papers for EGPGV 2009 covered a healthy range of topics from the fields of both computer graphics and visualization. The topics included simulation, global illumination, rendering, visualization, and general purpose computing on graphics processing units (GPUs), covering a wide variety of parallel computing platforms ranging from multicore to grid computing. Based on the reviewers’ comments and scoring as well as the quality of the oral presentations at EGPGV 2009, a committee that consisted of the proceedings editors and additional members selected three papers to be invited for submission to this special section of the IEEE Transactions on Visualization and Computer Graphics (TVCG). The authors extended their papers to include new additional material. The extended paper then underwent a full journal review process, including multiple cycles of editing and reviewing. The paper “GPU-Based Multilevel Clustering” by Iurie Chiosa and Andreas Kolb addresses the problem of mesh and data clustering. They present an efficient parallel algorithm for multilevel clustering, specifically designed for fast execution on GPUs. They demonstrate that their clustering method is useful for mesh clustering and general data clustering alike. “Parallel Iteration to the Radiative Transport in Inhomogeneous Media with Bootstrapping” by Laszlo SzirmayKalos, Gabor Liktor, Tamas Umenhoffer, Balazs Toth, Shree Kumar, and Glenn Lupton presents a method to solve the radiative transport equation in inhomogeneous participating media. The proposed solution involves running a multiple-scattering solver in parallel on the GPU or across different nodes in a cluster. “Efficient Rasterization for Outdoor Radio Wave Propagation” by Arne Schmitz, Tobias Rick, Thomas Karolski, Torsten Kuhlen, and Leif Kobbelt considers the problem of simulating and propagating radio waves, which is more complex than the analogous light transport problem due to the fact that waves bend around corners because of diffraction. In this work, the authors present a parallel beam tracing solution to this problem. We would like to thank all members of the International Program Committee of EGPGV 2009, the external reviewers for EGPGV 2009, and the reviewers for the extended papers for TVCG for their help. We would also like to take this opportunity to thank Kurt Debattista for his great work as symposium chair and his support and help during the reviewing process of EGPGV 2009, as well as all of the people from the University of Warwick who designed and hosted the symposium Web pages. Finally, we thank the local organizers of the Eurographics Conference, Rudiger Westermann and Joachim Georgii, who were very supportive of local arrangements for EGPGV 2009.

Path planning is an active topic in the literature, and efficient navigation over non-planar surfaces is an open research question. In this work we present a novel technique for navigation of multiple agents over arbitrary triangular domains. The proposed solution uses a fast hierarchical computation of geodesic distances over triangular meshes to allow interactive frame rates, and a GPU-based collision avoidance technique to guide individual agents. Unlike most previous work, the method imposes no limitations on the surface over which the agents are moving, and can naturally deal with non-planar meshes of arbitrary genus and curvature. Moreover, the implementation is a hybrid CPU/GPU algorithm that explores the current trend of increasing the number of CPU cores and GPU programmability. This approach exploits the best qualities in each processor, thus achieving very high performance.

Abstract Interactive isosurface extraction has recently become possible through successful efforts to map algorithms such as Marching Cubes (MC) and Marching Tetrahedra (MT) to modern Graphics Processing Unit (GPU) architectures. Other isosurfacing algorithms, however, are not so easily portable to GPUs, either because they involve more complex operations or because they are not based on discrete case tables, as is the case with most marching techniques. In this paper, we revisit the Dual Contouring (MC) and Macet isosurface extraction algorithms and propose, respectively: (i) a novel, efficient and parallelizable version of Dual Contouring and (ii) a set of GPU modules which extend the original Marching Cubes algorithm. Similar to marching methods, our novel technique is based on a case table, which allows for a very efficient GPU implementation. In addition, we enumerate and evaluate several alternatives to implement efficient contouring algorithms on the GPU, and present trade‐offs among all approaches. Finally, we validate the efficiency and quality of the tessellations produced in all these alternatives.

Abstract We propose a new framework design for exploiting multi‐core architectures in the context of visualization dataflow systems. Recent hardware advancements have greatly increased the levels of parallelism available with all indications showing this trend will continue in the future. Existing visualization dataflow systems have attempted to take advantage of these new resources, though they still have a number of limitations when deployed on shared memory multi‐core architectures. Ideally, visualization systems should be built on top of a parallel dataflow scheme that can optimally utilize CPUs and assign resources adaptively to pipeline elements. We propose the design of a flexible dataflow architecture aimed at addressing many of the shortcomings of existing systems including a unified execution model for both demand‐driven and event‐driven models; a resource scheduler that can automatically make decisions on how to allocate computing resources; and support for more general streaming data structures which include unstructured elements. We have implemented our system on top of VTK with backward compatibility. In this paper, we provide evidence of performance improvements on a number of applications.

In this paper, we propose an experimental study of an inexpensive off-the-shelf sort-last volume visualization architecture based upon multiple GPUs and a single CPU.We show how to efficiently make use of this architecture to achieve high performance sort-last volume visualization of large datasets.We analyze the bottlenecks of this architecture.We compare this architecture to a classical sort-last visualization system using a cluster of commodity machines interconnected by a gigabit Ethernet network.Based on extensive experiments, we show that this solution competes very well with a mid-sized PC cluster, while it significantly improves performance compared to a single standard PC.

Abstract There is a vast number of applications that require distance field computation over triangular meshes. State‐of‐the‐art algorithms have quadratic or sub‐quadratic worst‐case complexity, making them impractical for interactive applications. While most of the research on this subject has been focused on reducing the computation complexity of the algorithms, in this work we propose an approximate algorithm that achieves similar results working in lower resolutions of the input meshes. The creation of lower resolution meshes is the essence of our proposal. The idea is to identify regions on the input mesh that can be unfolded into planar regions with minimal area distortion (i.e. quasi‐developable charts). Once charts are computed, their interior is re‐triangulated to reduce the number of triangles, which results in a collection of simplified charts that we call a base mesh. Due to the properties of quasi‐developable regions, we are able to compute distance fields over the base mesh instead of over the input mesh. This reduces the memory footprint and data processed for distance computations, which is the bottleneck of these algorithms. We present results that are one order of magnitude faster than current exact solutions, with low approximation errors.

Marching Cubes is a popular choice for isosurface extraction from regular grids due to its simplicity, robustness, and efficiency. One of the key shortcomings of this approach is the quality of the resulting meshes, which tend to have many poorly shaped and degenerate triangles. This issue is often addressed through post processing operations such as smoothing. As we demonstrate in experiments with several datasets, while these improve the mesh, they do not remove all degeneracies, and incur an increased and unbounded error between the resulting mesh and the original isosurface. Rather than modifying the resulting mesh, we propose a method to modify the grid on which Marching Cubes operates. This modification greatly increases the quality of the extracted mesh. In our experiments, our method did not create a single degenerate triangle, unlike any other method we experimented with. Our method incurs minimal computational overhead, requiring at most twice the execution time of the original Marching Cubes algorithm in our experiments. Most importantly, it can be readily integrated in existing Marching Cubes implementations, and is orthogonal to many Marching Cubes enhancements (particularly, performance enhancements such as out-of-core and acceleration structures).

Marching Cubes is the most popular isosurface extraction algorithm due to its simplicity, efficiency and robustness. It has been widely studied, improved, and extended. While much early work was concerned with efficiency and correctness issues, lately there has been a push to improve the quality of Marching Cubes meshes so that they can be used in computational codes. In this work we present a new classification of MC cases that we call Edge Groups, which helps elucidate the issues that impact the triangle quality of the meshes that the method generates. This formulation allows a more systematic way to bound the triangle quality, and is general enough to extend to other polyhedral cell shapes used in other polygonization algorithms. Using this analysis, we also discuss ways to improve the quality of the resulting triangle mesh, including some that require only minor modifications of the original algorithm.

Many interactive rendering algorithms require operations on multiple fragments (i.e., ray intersections) at the same pixel location: however, current Graphics Processing Units (GPUs) capture only a single fragment per pixel. Example effects include transparency, translucency, constructive solid geometry, depth-of-field, direct volume rendering, and isosurface visualization. With current GPUs, programmers implement these effects using multiple passes over the scene geometry, often substantially limiting performance. This paper introduces a generalization of the Z-buffer, called the k-buffer, that makes it possible to efficiently implement such algorithms with only a single geometry pass, yet requires only a small, fixed amount of additional memory. The k-buffer uses framebuffer memory as a read-modify-write (RMW) pool of k entries whose use is programmatically defined by a small k-buffer program. We present two proposals for adding k-buffer support to future GPUs and demonstrate numerous multiple-fragment, single-pass graphics algorithms running on both a software-simulated k-buffer and a k-buffer implemented with current GPUs. The goal of this work is to demonstrate the large number of graphics algorithms that the k-buffer enables and that the efficiency is superior to current multipass approaches.

This paper presents a query optimizer module based on cost estimation that chooses the best filtering step algorithm to perform a specific spatial join operation. A set of expressions to predict the number of I/O operations and the response time of each algorithm is first presented and later refined considering a given hardware configuration. The query optimizer chooses the algorithm that returns the smaller estimated response time. In order to evaluate the query optimizer, we carried out a set of tests with synthetic and real data sets, in a significant number of different scenarios. The query optimizer correctly chooses the fastest algorithm in almost 90% of submitted operations, with minimal overhead.

The broad-phase step of collision detection in scenes composed of n moving objects is a challenging problem because enumerating collision pairs has an inherent O(n2) complexity. Spatial data structures are designed to accelerate this process, but often their static nature makes it difficult to handle dynamic scenes. In this work we propose a new structure called Semi-Adjusting BSP-tree for representing scenes composed of thousands of moving objects. An scheduling algorithm evaluates locations where the BSP-tree becomes unbalanced, uses several strategies to alter cutting planes, and defer updates based on their re-structuring cost. We show that the tree does not require a complete re-structuring even in highly dynamic scenes, but adjusts itself while maintaining desirable balancing and height properties.

This paper presents a technique for mapping relief textures onto arbitrary polygonal models in real time. In this approach, the mapping of the relief data is done in tangent space. As a result, it can be applied to polygonal representations of curved surfaces producing correct self-occlusions, interpenetrations, shadows and per-pixel lighting effects. The approach can be used to consistently add surface details to geometric models undergoing deformations, such as in the case of animated characters commonly found in games. The technique uses an inverse formulation (i.e., pixel driven) based on an efficient ray-height-field intersection algorithm implemented on the GPU. It supports extreme close-up views of the surfaces, mip mapping and anisotropic texture filtering. Also, contrary to high-dimensional representations of surface details, the low memory requirements of the proposed technique do not restrict its use to tiled textures.

We describe a new dynamic level-of-detail (LOD) technique that allows real-time rendering of large tetrahedral meshes. Unlike approaches that require hierarchies of tetrahedra, our approach uses a subset of the faces that compose the mesh. No connectivity is used for these faces so our technique eliminates the need for topological information and hierarchical data structures. By operating on a simple set of triangular faces, our algorithm allows a robust and straightforward graphics hardware (GPU) implementation. Because the subset of faces processed can be constrained to arbitrary size, interactive rendering is possible for a wide range of data sets and hardware configurations.

Abstract The explosive growth in integration technology and the parallel nature of rasterization‐based graphics APIs (Application Programming Interface) changed the panorama of consumer‐level graphics: today, GPUs (Graphics Processing Units) are cheap, fast and ubiquitous. We show how to harness the computational power of GPUs and solve the incompressible Navier‐Stokes fluid equations significantly faster (more than one order of magnitude in average) than on CPU solvers of comparable cost. While past approaches typically used Stam's implicit solver, we use a variation of SMAC (Simplified Marker and Cell). SMAC is widely used in engineering applications, where experimental reproducibility is essential. Thus, we show that the GPU is a viable and affordable processor for scientific applications. Our solver works with general rectangular domains (possibly with obstacles), implements a variety of boundary conditions and incorporates energy transport through the traditional Boussinesq approximation. Finally, we discuss the implications of our solver in light of future GPU features, and possible extensions such as three‐dimensional domains and free‐boundary problems.

We present a technique for mapping relief textures onto arbitrary polygonal models in real time, producing correct self-occlusions, interpenetrations, shadows and per-pixel lighting. The technique uses a pixel-driven formulation based on an efficient ray-height-field intersection implemented on the GPU. It has very low memory requirements, supports extreme close-up views of the surfaces and can be applicable to surfaces undergoing deformation.

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 anew technique to maintain a BSP for a set of n moving disj oint segments in the plane. Our kinetic BSP uses O(n log n) storage and it undergoes O(n 2 ) changes in the worst case, assuming that the endpoints of the segments move along bounded-degree algebraically dened trajecto- ries. The response time (the time needed to update the BSP when it undergoes a change) is O(log 2 n). A random- ized variant achieves O(log n) expected response time, while the worst-case response time remains O(log 2 n).

No abstract available.

Direct volume rendering based on projective methods works by projecting, in visibility order, the polyhedral cells of a mesh onto the image plane, and incrementally compositing the cell’s color and opacity into the final image. Crucial to this method is the computation of a visibility ordering of the cells. If the mesh is “well‐behaved” (acyclic and convex), then the MPVO method of Williams provides a very fast sorting algorithm; however, this method only computes an approximate ordering in general datasets, resulting in visual artifacts when rendered. A recent method of Silva et al. removed the assumption that the mesh is convex, by means of a sweep algorithm used in conjunction with the MPVO method; their algorithm is substantially faster than previous exact methods for general meshes. In this paper we propose a new technique, which we call BSP‐XMPVO, which is based on a fast and simple way of using binary space partitions on the boundary elements of the mesh to augment the ordering produced by MPVO. Our results are shown to be orders of magnitude better than previous exact methods of sorting cells.