Interactive Ray Tracing  
In recent years, there has been a renewed interest in real-time ray tracing for interactive applications. This is due to many factors: firstly, processor speed has continued to rise at exponential rates as predicted by Moore's Law and is approaching the raw computational power needed for interactive ray tracing. Secondly, ray tracing algorithms can be highly parallelized on shared memory and distributed memory systems. Therefore, the current hardware trend towards desktop systems with multi-core CPUs and programmable GPUs can be used to accelerate ray tracing. Finally, recent algorithmic improvements that exploit ray coherence can achieve a significant improvement in rendering time.
We have active research projects in the area of interactive ray tracing dealing with problems such as ray tracing massive datasets and deformable models.
Dynamic Scene Benchmarks
The dynamic scenes used in our projects are available.
Project website...
SATO: Surface-Area Traversal Order for Shadow Ray Tracing
Jae-Ho Nah and Dinesh Manocha
We present the surface-area traversal order (SATO) metric to accelerate shadow ray traversal. Our formulation uses the surface area of each child node to compute the traversal order. In this metric, we give a traversal priority to the child node with the larger surface area to quickly find occluders. Our algorithm reduces the preprocessing overhead significantly, and is much faster than other metrics. Overall, the SATO is useful for ray tracing large and complex dynamic scenes (e.g. a few million triangles) with shadows.
Project website...
RayCore: RayCore: A ray-tracing hardware architecture for mobile devices
We present RayCore, a mobile ray-tracing hardware architecture. RayCore
facilitates high-quality rendering effects, such as reflection, refraction, and
shadows, on mobile devices by performing real-time Whitted ray tracing.
RayCore consists of two major components: ray-tracing units (RTUs) based
on a unified traversal and intersection pipeline and a tree-building unit
(TBU) for dynamic scenes. The overall RayCore architecture offers consid-
erable benefits in terms of die area, memory access, and power consump-
tion. We have evaluated our architecture based on FPGA and ASIC evalua-
tions and demonstrate its performance on different benchmarks. According
to the results, our architecture demonstrates high performance per unit area
and unit energy, making it highly suitable for use in mobile devices.
Project paper
HART: A Hybrid Architecture for Ray Tracing Animated Scenes
We present a hybrid architecture, inspired by asynchronous BVH construction, for ray tracing animated scenes. Our hybrid architecture utilizes heterogeneous hardware resources: dedicated ray-tracing hardware for BVH updates and ray traversal and a CPU for BVH reconstruction. We also present a traversal scheme using a primitive’s axis-aligned bounding box (PrimAABB). This scheme reduces ray-primitive intersection tests by reusing existing BVH traversal units and the primAABB data for tree updates; it enables the use of shallow trees to reduce tree build times, tree sizes, and bus bandwidth requirements. Furthermore, we present a cache scheme that exploits consecutive memory access by reusing data in an L1 cache block. We perform cycle-accurate simulations to verify our architecture, and the simulation results indicate that the proposed architecture can achieve real-time Whitted ray tracing animated scenes at 1920x1200 resolution. This result comes from our high-performance hardware architecture and minimized resource requirements for tree updates.
Project website
Selective Ray Tracing for Interactive High-quality Shadows
Christian Lauterbach, Qi Mo, and Dinesh Manocha
We present novel algorithms to achieve interactive high-quality illumination with hard and soft shadows in complex models. Our approach combines the efficiency of rasterization-based approaches with the accuracy of a ray tracer. We use conservative image-space bounds to identify only a small subset of the pixels in the rasterized image and perform selective ray tracing on those pixels. The algorithm can handle moving light sources as well as dynamic scenes. In practice, our approach is able to generate high quality hard and
soft shadows on complex models with millions of triangles at almost interactive rates on current high-end GPUs.
Project website...
Fast BVH Construction on GPUs
Christian Lauterbach and Dinesh Manocha
We present two novel parallel algorithms for rapidly constructing bounding volume hierarchies on many-core GPUs. The first uses a linear ordering derived from spatial Morton codes to build hierarchies extremely quickly and with high parallel scalability. The second is a top-down approach that uses the surface area heuristic (SAH) to build hierarchies optimized for fast ray tracing. Both algorithms are combined into a hybrid algorithm that removes existing bottlenecks in the algorithm for GPU construction performance and scalability leading to significantly decreased build time. The resulting hierarchies are close in to optimized SAH hierarchies, but the construction process is substantially faster, leading to a significant net benefit when both construction and traversal cost are accounted for. Our preliminary results show that current GPU architectures can compete with CPU implementations of hierarchy construction running on multicore systems. In practice, we can construct hierarchies of models with up to several million triangles and use them for fast ray tracing or other applications.
Project website...
ReduceM: Interactive and Memory Efficient Ray Tracing of Large Models
Christian Lauterbach, Sung-Eui Yoon, Ming Tang, and Dinesh Manocha
We present a novel representation and algorithm, ReduceM, for memory efficient ray tracing of large scenes. ReduceM exploits the connectivity between triangles and decomposes the model into triangle strips. We also describe a novel stripification algorithm, Strip-RT, that can generate long strips with high spatial coherence optimized for ray tracing. We use a two-level traversal algorithm for ray-primitive intersection. In practice, ReduceM can significantly reduce the storage overhead and ray trace massive models with a hundreds of millions of triangles at interactive rates on desktop PCs with 4-8GB of main memory.
Project website...
AD-Frustum: Adaptive Frustum Tracing for Interactive Sound Propagation
Anish Chandak, Christian Lauterbach, Micah Taylor, Zhimin Ren, and Dinesh Manocha
We present an interactive algorithm to compute sound propagation paths for transmission, specular refection and edge diffraction in complex scenes. Our formulation uses an adaptive frustum representation that is automatically sub-divided to accurately compute intersections with the scene primitives. We describe a simple and fast algorithm to approximate the visible surface for each frustum and generate new frusta based on specular refection and edge diffraction. Our approach is applicable to all triangulated models and we demonstrate its performance on architectural and outdoor models with tens or hundreds of thousands of triangles and moving objects. In practice, our algorithm can perform geometric sound propagation in complex scenes at 4-20 frames per second on a multi-core PC.
Paper... (IEEE Visualization, 2008)
Ray-strips: A Compact Mesh Representation for Interactive Ray Tracing
Christian Lauterbach, Sung-Eui Yoon, and Dinesh Manocha
We present a novel hierarchical representation, Ray-Strips, for interactive ray tracing of complex triangle meshes. Prior optimized algorithms for ray tracing explicitly store each triangle in the input model. Instead, a Ray-Strip takes advantage of mesh connectivity for compact storage, efficient traversal and ray intersections. As a result, we considerably reduce the memory overhead of the original model and the hierarchical representation. We also present efficient algorithms for single ray and ray packet traversal using Ray-Strips. Furthermore, we demonstrate an additional benefit of our representation, maintaining utilization of the SIMD capabilities of current
CPUs for incoherent ray packets and single rays. We show the benefit of Ray-Strips on models with tens of thousands to tens of millions of triangles. In practice, our approach can reduce the storage overhead of interactive ray tracing algorithms by up to five times compared to standard interactive approaches while even improving runtime performance for large models.
Paper... (Interactive Ray Tracing Symposium, 2007)
Ray Tracing Dynamic Scenes Using Selective Restructuring
Sung-Eui Yoon, Sean Curtis, and Dinesh Manocha
We present a novel algorithm to selectively restructure bounding volume hierarchies (BVHs) for ray tracing dynamic scenes. We derive two new metrics to evaluate the culling efficiency and restructuring benefit of any BVH. Based on these metrics, we perform selective restructuring operations that efficiently reconstruct small portions of a BVH instead of the entire BVH. Our approach is general and applicable to complex and dynamic scenes, including topological changes. We apply our selective restructuring algorithm to improve the performance of ray tracing dynamic scenes that consist of hundreds of thousands of triangles. In our benchmarks, we observe up to an order of magnitude improvement over prior BVH-based ray tracing algorithms.
Project website...
Interactive Sound Propagation in Dynamic Scenes Using Frustum Tracing
Christian Lauterbach, Anish Chandak, Micah Taylor, Zhimin Ren, and Dinesh Manocha
We present a new approach for simulating real-time sound propagation in complex, virtual scenes with dynamic sources and objects. Our approach combines the efficiency of interactive ray tracing with the accuracy of tracing a volumetric representation. We use a four-sided convex frustum and perform clipping and intersection tests using ray packet tracing. A simple and efficient formulation is used to compute secondary frusta and perform hierarchical traversal. We demonstrate the performance of our algorithm in an interactive system for game-like environments and architectural models with tens or hundreds of thousands of triangles. Our algorithm can simulate and render sounds at interactive rates on a high-end PC.
Project website...
R-LODs for Ray Tracing Massive Models
Sung-Eui Yoon, Christian Lauterbach, and Dinesh Manocha
We present a novel level-of-detail (LOD) algorithm to accelerate ray tracing of massive models. Our approach computes drastic simplifications of the model and integrates the LODs directly with the kd-tree data structure. We introduce a simple and efficient LOD metric to bound the error for primary and secondary rays. The LOD representation has small runtime overhead and our algorithm can be combined with ray coherence techniques and cache-coherent layouts to improve the performance. In practice, the use of LODs can alleviate aliasing artifacts and improve memory coherence. We implement our algorithm on both 32-bit and 64-bit machines and achieve up to 2-20 times improvement
in frame rate while rendering models consisting of tens or hundreds of millions of triangles with little loss in image quality.
Project website...
Interactive Ray Tracing of Deformable Models Using BVHs
Christian Lauterbach, Sung-Eui Yoon, David Tuft, and Dinesh Manocha
We present an efficient approach for interactive ray tracing of deformable or animated models. Unlike many of the recent approaches for ray tracing static scenes, we use bounding volume hierarchies (BVHs) instead of kd-trees as the underlying acceleration structure. Our algorithm makes no assumptions about the simulation or the motion of objects in the scene and dynamically updates or recomputes the BVHs. We also describe a method to detect BVH quality degradation during the simulation in order to determine when the hierarchy needs to be rebuilt. Furthermore, we show that the ray coherence techniques introduced for kd-trees can be naturally extended to BVHs and yield similar improvements. Our algorithm has been applied to different scenarios composed of tens of thousands to a million triangles arising in animation and simulation. In practice, our algorithm can ray trace these models at 4-20 frames a second on a dual-core Xeon PC.
Project website...
Cache-efficient Layouts of Bounding Volume Hierarchies
Sung-Eui Yoon and Dinesh Manocha
We present a novel algorithm to compute cache-efficient layouts of bounding volume hierarchies (BVHs) of polygonal models. We does not make any assumptions about the cache parameters or block sizes of the memory hierarchy. We introduce a new probabilistic model to predict the runtime access patterns of a BVH. Our layout computation algorithm utilizes parent-child and spatial localities between the accessed nodes
to reduce both the number of cache misses and the size of working set. Also, our algorithm works well with spatial partitioning hierarchies including kd-trees. We use our algorithm to compute layouts of BVHs and spatial partitioning hierarchies of large models composed of millions of triangles. We compare our cache-efficient layouts with other layouts in the context of collision detection and ray tracing. In our benchmarks, our layouts consistently show better performance over other layouts and improve the performance of these applications by 26-2600% without any modification of the underlying algorithms or runtime applications.
Project website...
Principal Investigators
Research Sponsors
|
Current Members
Past Members
- Anish Chandak
- Christian Lauterbach
- Ming Tang
- David Tuft
- Sung-Eui Yoon
|
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
|
