Parallel machines are becoming more complex with increasing core counts and more heterogeneous architectures. However, the commonly used parallel programming models, C/C++ with MPI and/or OpenMP, make it difficult to write source code that is easily tuned for many targets. Newer language approaches attempt to ease this burden by providing optimization features such as automatic load balancing, overlap of computation and communication, message-driven execution, and implicit data layout optimizations. In this paper, we compare several implementations of LULESH, a proxy application for shock hydrodynamics, to determine strengths and weaknesses of different programming models for parallel computation. We focus on four traditional (OpenMP, MPI, MPI+OpenMP, CUDA) and four emerging (Chapel, Charm++, Liszt, Loci) programming models. In evaluating these models, we focus on programmer productivity, performance and ease of applying optimizations.

We present a streaming geometry compression codec for multiresolution, uniformly-gridded, triangular terrain patches that supports very fast decompression. Our method is based on linear prediction and residual coding for lossless compression of the full-resolution data. As simplified patches on coarser levels in the hierarchy already incur some data loss, we optionally allow further quantization for more lossy compression. The quantization levels are adaptive on a per-patch basis, while still permitting seamless, adaptive tessellations of the terrain. Our geometry compression on such a hierarchy achieves compression ratios of 3:1 to 12:1.

Previous algorithms for view-dependent level of detail provide local mesh refinements either at the finest granularity or at a fixed, coarse granularity. The former provides triangle-level adaptation, often at the expense of heavy CPU usage and low triangle rendering throughput; the latter improves CPU usage and rendering throughput by operating on groups of triangles.

Most streamline generation algorithms either provide a particular density of streamlines across the domain or explicitly detect features, such as critical points, and follow customized rules to emphasize those features. However, the former generally includes many redundant streamlines, and the latter requires Boolean decisions on which points are features (and may thus suffer from robustness problems for real-world data). We take a new approach to adaptive streamline placement for steady vector fields in 2D and 3D. We define a metric for local similarity among streamlines and use this metric to grow streamlines from a dense set of candidate seed points. The metric considers not only Euclidean distance, but also a simple statistical measure of shape and directional similarity. Without explicit feature detection, our method produces streamlines that naturally accentuate regions of geometric interest. In conjunction with this method, we also propose a quantitative error metric for evaluating a streamline representation based on how well it preserves the information from the original vector field. This error metric reconstructs a vector field from points on the streamline representation and computes a difference of the reconstruction from the original vector field.

Today's PCs incorporate multiple CPUs and GPUs and are easily arranged in clusters for high-performance, interactive graphics. We present an approach based on hierarchical, screen-space tiles to parallelizing rendering with level of detail. Adapttiles, render tiles, and machine tiles are associated with CPUs, GPUs, and PCs, respectively, to efficiently parallelize the workload with good resource utilization. Adaptive tile sizes provide load balancing while our level of detail system allows total and independent management of the load on CPUs and GPUs. We demonstrate our approach on parallel configurations consisting of both single PCs and a cluster of PCs

This paper presents a novel method for volume rendering of unstructured grids. Previously, we introduced an algorithm for perspective-correct interpolation of barycentric coordinates and computing polynomial attenuation integrals for a projected tetrahedron using graphics hardware. Here, we enhance the algorithm by providing a simple and efficient method to compute the projected shape (silhouette) and tessellation of a tetrahedron, in perspective and orthographic projection models. Our tessellation algorithm is published here for the first time. Compared with works of other groups on rendering unstructured grids, the main contributions of this work are: 1) A new algorithm for finding the silhouette of a projected tetrahedron. 2) A method for interpolating barycentric coordinates and thickness on the faces of the tetrahedron. 3) Visualizing higher-order attenuation functions using GPU without preintegration. 4) Capability of applying shape deformations to a rendered tetrahedral mesh without significant performance loss. Our visualization model is independent of depth-sorting of the cells. We present imaging and timing results of our implementation, and an application in time-critical "2D-3D" deformable registration of anatomical models. We discuss the impact of using higher-order functions on quality and performance.

This paper presents a novel method for computing simulated x-ray images, or DRRs (digitally reconstructed radiographs), of tetrahedral meshes with higher-order attenuation functions. DRRs are commonly used in computer assisted surgery (CAS), with the attenuation function consisting of a voxelized CT study, which is viewed from different directions. Our application of DRRs is in intra-operative "2D-3D" registration, i.e., finding the pose of the CT dataset given a small number of patient radiographs. We register 2D patient images with a statistical tetrahedral model, which encodes the CT intensity numbers as Bernstein polynomials, and includes knowledge about typical shape variation modes. The unstructured grid is more suitable for applying deformations than a rectilinear grid, and the higher-order polynomials provide a better approximation of the actual density than constant or linear models. The infra-operative environment demands a fast method for creating the DRRs, which we present here. We demonstrate this application through the creation and use of a deformable atlas of human pelvis bones. Compared with other works on rendering unstructured grids, the main contributions of this work are: 1) Simple and perspective-correct interpolation of the thickness of a tetrahedral cell. 2) Simple and perspective-correct interpolation of front and back barycentric coordinates with respect to the cell. 3) Computing line integrals of higher-order functions. 4) Capability of applying shape deformations and variations in the attenuation function without significant performance loss. The method does not depend on for pre-integration, and does not require depth-sorting of the visualized cells. We present imaging and timing results of implementing the algorithm, and discuss the impact of using higher-order functions on the quality of the result and the performance.

We present a new, unified approach to debugging graphics software. We propose a representation of all graphics state over the course of program execution as a relational database, and produce a query-based framework for extracting, manipulating, and visualizing data from all stages of the graphics pipeline. Using an SQL-based query language, the programmer can establish functional relationships among all the data, linking OpenGL state to primitives to vertices to fragments to pixels. Based on the Chromium library, our approach requires no modification to or recompilation of the program to be debugged, and forms a superset of many existing techniques for debugging graphics software.

We present visibility computation and data organization algorithms that enable high-fidelity walkthroughs of large 3D geometric data sets. A novel feature of our walkthrough system is that it performs work proportional only to the required detail in visible geometry at the rendering time. To accomplish this, we use a precomputation phase that efficiently generates per cell vLOD: the geometry visible from a view-region at the right level of detail. We encode changes between neighboring cells' vLODs, which are not required to be memory resident. At the rendering time, we incrementally construct the vLOD for the current view-cell and render it. We have a small CPU and memory requirement for rendering and are able to display models with tens of millions of polygons at interactive frame rates with less than one pixel screen-space deviation and accurate visibility.

We present a novel scheme to interactively visualize time-varying scalar fields defined on a structured grid. The underlying approach is to maximize the use of current graphics hardware by using 3D texture mapping. This approach commonly suffers from an expensive voxelization of each time-step as well as from large size of the voxel array approximating each step. Hence, in our scheme, instead of explicitly voxelizing each scalar field, we directly store each time-step as a three dimensional texture in its native form. We create the function that warps a voxel grid into the given structured grid. At rendering time, we reconstruct the function at each pixel using hardware-based trilinear interpolation. The resulting coordinates allow us to compute the scalar value at this pixel using a second texture lookup. For fixed grids, the function remains constant across time-steps and only the scalar field table needs to be re-loaded as a texture. Our new approach achieves excellent performance with relatively low texture memory requirements and low approximation error.

We present a new algorithm for best-effort simplification of polygonal meshes based on principles of visual perception. Building on previous work, we use a simple model of low-level human vision to estimate the perceptibility of local simplification operations in a view-dependent Multi-Triangulation structure. Our algorithm improves on prior perceptual simplification approaches by accounting for textured models and dynamic lighting effects. We also model more accurately the scale of visual changes resulting from simplification, using parametric texture deviation to bound the size (represented as spatial frequency) of features destroyed, created, or altered by simplifying the mesh. The resulting algorithm displays many desirable properties: it is view-dependent, sensitive to silhouettes, sensitive to underlying texture content, and sensitive to illumination (for example, preserving detail near highlight and shadow boundaries, while aggressively simplifying washed-out regions). Using a unified perceptual model to evaluate these effects automatically accounts for their relative importance and balances between them, overcoming the need for ad hoc or hand-tuned heuristics.

No abstract available.

Multi-resolution hierarchies of polygons and more recently of points are familiar and useful tools for achieving interactive rendering rates. We present an algorithm for tightly integrating the two into a single hierarchical data structure. The trade-off between rendering portions of a model with points or with polygons is made automatically. Our approach to this problem is to apply a bottom-up simplification process involving not only polygon simplification operations, but point replacement and point simplification operations as well. Given one or more surface meshes, our algorithm produces a hybrid hierarchy comprising both polygon and point primitives. This hierarchy may be optimized according to the relative performance characteristics of these primitive types on the intended rendering platform. We also provide a range of aggressiveness for performing point replacement operations. The most conservative approach produces a hierarchy that is better than a purely polygonal hierarchy in some places, and roughly equal in others. A less conservative approach can trade reduced complexity at the far viewing ranges for some increased complexity at the near viewing ranges. We demonstrate our approach on a number of input models, achieving primitive counts that are 1.3 to 4.7 times smaller than those of triangle-only simplification.

Discusses the concept of uniform frequency images, which exhibit uniform local frequency properties. Such images make optimal use of space when sampled close to their Nyquist limit. A warping function may be applied to an arbitrary image to redistribute its local frequency content, reducing its highest frequencies and increasing its lowest frequencies in order to approach this uniform frequency ideal. The warped image may then be downsampled according to its new, reduced Nyquist limit, thereby reducing its storage requirements. To reconstruct the original image, the inverse warp is applied. We present a general, top-down algorithm to automatically generate a piecewise-linear warping function with this frequency balancing property for a given input image. The image size is reduced by applying the warp and then downsampling. We store this warped, downsampled image plus a small number of polygons with texture coordinates to describe the inverse warp. The original image is later reconstructed by rendering the associated polygons with the warped image applied as a texture map, a process which is easily accelerated by current graphics hardware. As compared to previous image compression techniques, we generate a similar graceful space-quality tradeoff with the advantage of being able to "uncompress" images during rendering. We report results for several images with sizes ranging from 15,000 to 300,000 pixels, achieving reduction rates of 70-90% with improved quality over downsampling alone.

We present a system for rendering very complex 3D models at interactive rates.We select a subset of the model as preferred viewpoints and partition the space into virtual cells.Each cell contains near geometry, rendered using levels of detail and visibility culling, and far geometry, rendered as a textured depth mesh.Our system automatically balances the screen-space errors resulting from geometric simplification with those from textureddepth-mesh distortion.We describe our prefetching and data management schemes, both crucial for models significantly larger than available system memory.We have successfully used our system to accelerate walkthroughs of a 13 million triangle model of a large coal-fired power plant and of a 1.7 million triangle architectural model.We demonstrate the walkthrough of a 1.3 GB power plant model with a 140 MB cache footprint.

25th International Conference on Computer Graphics and Interactive Techniques, July 19-24, 1998, Orlando, Florida, USA

: Many applications in computer graphics and virtual environments need to render datasets with large numbers of primitives and high depth complexityatinteractive rates. However, standard techniques like view frustum culling and a hardware z-bu#er are unable to display datasets composed of hundred of thousands of polygons at interactive frame rates on current high-end graphics systems. We add a #conservative" visibility culling stage to the rendering pipeline, attempting to identify and avoid processing of occluded polygons. Given a moving viewpoint, the algorithm dynamically chooses a set of occluders. Each occluder is used to compute a shadow frustum, and all primitives contained within this frustum are culled. The algorithm hierarchicallytraverses the model, culling out parts not visible from the current viewpoint using e#cient, robust, and in some cases specialized interference detection algorithms. The algorithm's performance varies with the location of the viewpoint and the depth...

We present the use of mapping functions to automatically generate levels of detail with known error bounds for polygonal models. We develop a piece-wise linear mapping function for each simplification operation and use this function to measure deviation of the new surface from both the previous level of detail and from the original surface. In addition, we use the mapping function to compute appropriate texture coordinates if the original map has texture coordinates at its vertices. Our overall algorithm uses edge collapse operations. We present rigorous procedures for the generation of local planar projections as well as for the selection of a new vertex position for the edge collapse operation. As compared to earlier methods, our algorithm is able to compute tight error bounds on surface deviation and produce an entire continuum of levels of detail with mappings between them. We demonstrate the effectiveness of our algorithm on several models: a Ford Bronco consisting of over 300 parts and 70,000 triangles, a textured lion model consisting of 49 parts and 86,000 triangles, and a textured, wrinkled torus consisting of 79,000 triangles.

We propose the idea of simplification envelopes for generating a hierarchy of level-of-detail approximations for a given polygonal model.Our approach guarantees that all points of an approximation are within a user-specifiable distance from the original model and that all points of the original model are within a distance from the approximation.Simplification envelopes provide a general framework within which a large collection of existing simplification algorithms can run.We demonstrate this technique in conjunction with two algorithms, one local, the other global.The local algorithm provides a fast method for generating approximations to large input meshes (at least hundreds of thousands of triangles).The global algorithm provides the opportunity to avoid local "minima" and possibly achieve better simplifications as a result.Each approximation attempts to minimize the total number of polygons required to satisfy the above constraint.The key advantages of our approach are: General technique providing guaranteed error bounds for genus-preserving simplification Automation of both the simplification process and the selection of appropriate viewing distances Prevention of self-intersection Preservation of sharp features Allows variation of approximation distance across different portions of a model CR Categories and Subject Descriptors: I.3.

we present an exact and interactive collision detection system, I-COLLIDE, for large-scale environments. Such environments are characterized by the number of objects undergoing rigid motion and the complexity of the models. The algorithm does not assume the objects' motions can be expressed as a closed form function of time. The collision detection system is general and can be easily interfaced with a variety of applications. The algorithm uses a two-level approach based on pruning multiple-object pairs using bounding boxes and performing exact collision detection between selected pairs of polyhedral models. We demonstrate the performance of the system in walkthrough and simulation environments consisting of a large number of moving objects. In particular, the system takes less than 1/20 of a second to determine all the collisions and contacts in an environment consisting of more than 1000 moving polytopes, each consisting of more than 50 faces on an HP-9000/750.

Latency or lag in an interactive graphics system is the delay between user input and displayed output. We have found latency and the apparent bobbing and swimming of objects that it produces to be a serious problem for head-mounted display (HMD) and augmented reality applications. At UNC, we have been investigating a number of ways to reduce latency; we present two of these. Slats is an experimental rendering system for our Pixel-Planes 5 graphics machine guaranteeing a constant single NTSC field of latency. This guaranteed response is especially important for predictive tracking. Just-in-time pixels is an attempt to compensate for rendering latency by rendering the pixels in a scanned display based on their position in the scan.

No abstract available.