Class email list:
cs395t-rtds[@]lists[.]cc[.]utexas[.]edu
Anyone in the class can post to the list. All students,
instructors, and auditors are on the list. Students are
encouraged to use the list for class-related discussions; for
example discussions about the software used in the class.
Lecture Topics and Readings
Class 1 (Aug 28) - Introduction
Read: None
Class 2 (Sep 2) - Basic graphics and raytracing;
LRT overview
Read: Chapter 1 from Glassner, "An Introduction to Ray Tracing"
Hand out Assignment #1
Background reading (optional):
Class 3 (Sep 4) - Acceleration structures
Read: pp. 345--368 from Moller & Haines, Real-Time Rendering, 2nd ed.
Class 4 (Sep 9) - Culling strategies; ray classification
Read: Fast ray tracing by ray classification, James Arvo and David Kirk, August 1987. Summary: Rays are considered to reside in a 5D space (3 for x,y,z
of origin, plus 2 for direction). The system lazily builds a
hierarchical 5D spatial data structure. At each leaf (representing
part of the 5D space), the system maintains a sorted (based on
distance from origin) list of objects. Rays are tested against
the list from the appropriate leaf element.
Class 5 (Sept 11) -- Scene graphs; Overview of challenges and approaches to rendering dynamic scenes
Read: Chapter 4 (pp.142-167) from Eberly, 3D Game Engine Design. You can skip (or just skim) the sections covering details of merging and culling for different bounding volumes.
Class 6 (Sep 16) -- Skinning, Displacement Mapping and Intro to Procedural Models Due (at start of class):Assignment #1.
Read: Animation of Characters, Chapter 9 from Eberly, 3D Game Engine Design. [section 9.3 discusses skinning]
Computing Dynamic Changes to BSP Trees, Chrysanthou and Slater, Eurographics 1992. Summary: Explains how to delete a polygon from the BSP tree by filtering the smaller subtree of the deleted polygon into the larger subtree.
Class 10 (Sept 30) -- Real-Time Systems I: Utah
Presenter: Peter Djeu
Read:
Interactive Ray Tracing, Parker, Martin, Sloan, Shirley,
Smitts, and Hansen, I3D 1999. Summary: A brute-force interactive raytracer implemented on
a shared-memory parallel machine, mostly for static scenes.
Class 11 (Oct 2) -- Summary of recent real-time raytracing research
Presenter: Vinay Siddhavanahalli
Read:
Realtime Ray Tracing and its use for Interactive Global
Illumination, Wald, Purcell, Schmittler, Benthin and
Slusallek, Eurographics 2003. Summary: A great survey of the latest work and open
problems in real-time ray tracing, for both static and dynamic
scenes.
Class 12 (Oct 7) -- Real-Time Systems II: Saarbrucken
Presenter: Paul Navratil (slides: [PDF][PPT])
Read:
A Scalable Approach to Interactive Global Illumination,
Benthin, Wald, and Slusallek, Eurographics 2003. Summary: This paper uses a variant of Keller's instant radiosity
to efficiently render static scenes with diffuse surfaces using
a ray tracer. To
achieve high performance, the system is parallelized across a cluster,
groups rays for cache coherence, and uses float-4 SIMD
instructions.
Class 13 (Oct 9) -- Effective BSP/Kd Tree Building
Presenter: Jun Li (slides: [PDF][PPT])
Read: On Improving KD-Trees for Ray Shooting, Havran and Bittner, WSCG 2002.
Background reading (optional):
Summary: By estimating the proability of a ray entering a portion
of the spatial data structure and estimating the average cost of the
intersection and/or traversal computations that follow such an
entrance, it is possible to build BSP trees with low expected
traversal costs.
Class 14 (Oct 14) -- Evaluation of Spatial Data Structures
Presenter: Chris Burns (slides: [PDF])
Read: Factors Affecting Performance of Ray Tracing
Hierarchies, Subramanian and Fussell, UTCS Tech Report, 1990. Summary: This paper evaluates a variety of spatial data structures
(space filling and non-space-filling) and discusses the factors that
influence their traversal performance.
Background reading (optional):
Automatic creation of object hierarchies for ray tracing, J Goldsmith and J Salmon, IEEE Computer Graphics and Applications, 7(5):14--20, 1984. Summary: Uses bounding-volume surface area as a heuristic to guide automatic construction of efficient bounding volume hierarchies.
Class 15 (Oct 16) -- Dynamic Systems I: Utah
Presenter: Greg Johnson (slides: [PDF])
Read:
Dynamic Acceleration Structures for Interactive Ray Tracing,
Reinhard, E., Smits, B., and Hansen, C.,
in Proc. Eurographics Workshop on Rendering, pp. 299-306,
June 2000. Summary: This system uses a grid data structure, allowing
dyanamic objects to be easily inserted or removed. The grid
is tiled in space (i.e. it wraps around) to avoid problems with
fixed boundaries. They also implement a hiearchical grid with
data in both internal and leaf nodes; objects are inserted into
the optimal level.
Class 16 (Oct 21) -- Dynamic Systems II: Chalmers
Presenter: Rajeev Sudhakar
Read:
Towards Rapid Reconstruction for Animated Ray Tracing,
Lext and Akenine-Moller, Eurographics 2001. Summary: Each rigid dynamic object gets its own grid acceleration structure, and rays are transformed into this local coordinate system. Surprisingly, they show that this scheme is not a big win for simple scenes, because in simple scenes it is possible to completely rebuild the grid each frame using only about a quarter of the runtime. But, this would probably not be true for a k-d or BSP tree.
Class 17 (Oct 23) -- Dynamic Systems III: Saarbrucken
Presenter: Michael Bond
Read:
Distributed Interactive Ray Tracing of Dynamic Scenes,
Wald, Benthin, and Slusallek,
Proc. IEEE Symp. on Parallel and Large-Data Visualization
and Graphics (PVG), 2003. Summary: This system uses ray transformation (into object coordinate system) for rigid movement, and BSP rebuild for unstructured movement. A top-level BSP tree is rebuilt every frame to hold bounding volumes for the moving objects. Performance is still an issue for unstructured movement.
Class 18 (Oct 28) -- Performance Tuning for Modern CPUs
Presenter: Jason Dale
Class 19 (Oct 30) -- Discussion of Assignment #2
Each group will briefly give a whiteboard presentation
describing their strategy for assignment #2. In particular,
each group should describe their strategy for choosing K-d
split planes and for handling BVH nodes that intersect
the split plane. Also each group should discuss their
'ikd' performance.
We will also use this class to choose the last round of
presentation topics and dates, and to discuss the final
project.
Class 21 (Nov 6) -- Spatial locality in a Z-buffer system
Presenter: Rajeev Sudhakar
Read:
The Reyes image rendering architecture,
Cook, Carpenter and Catmull,
SIGGRAPH 1987.
Class 22 (Nov 11) -- On-demand geometry creation and caching
Presenter: Chris Burns (slides: [PDF])
Read:
Geometry Caching for Ray-Tracing Displacement Maps,
Pharr and Hanrahan,
Proc. 1996 Eurographics Workshop on Rendering.
Background reading (optional):
Class 23 (Nov 13) -- A two-topic, two-presenter class Topic #1: Adaptive BSP tree construction
Presenter: Greg Johnson
Read: Deferred, self-organizing BSP trees, Ar, Montag, and Tal, Eurographics 2002.
Background readings (optional):
Summary of first paper: This system dynamically creates lower levels of the acceleration octree on demand, to reduce memory consumed by the octree and to reduce the time needed to create the octree. Initially, the octree can have "fat" leaf nodes, each of which has a list of many primitives. If one of these nodes is visited, the corresponding subtree is built one level at a time. Summary of second paper: This system builds a BSP tree incrementally. Unbuilt (fat) leaf nodes keep a list of polygons, with a hit count for each polygon. When the decision is made to increase the tree depth by creating a new split plane, the polygon with the highest hit count is used as the split plane. Topic #2: Intel's real-time ray tracer
Presenter: Peter Djeu (slides: [PDF])
Read: Fast Ray Tracing for Modern General Purpose CPU, Hurley, Kapustin, Reshetov, and Soupikov, Graphicon 2002.
Class 24 (Nov 18) -- Invertible spatial deformations
Presenter: Vinay Siddhavanahalli
Read: Interactive Space Deformation with Hardware Assisted Rendering, IEEE Computer Graphics and Applications, Vol 17, no 6, 1997, pp. 66-77. Summary: Instead of deforming objects directly, this system deforms the space in which they reside (using 1-to-1 deformations). During raytracing, the rays are deformed into the object space instead of deforming the objects into the ray space. However, the resulting deformed rays are no longer straight, so they must be discretized into short line segments to perform the actual ray-object intersection tests.
Chapter 4 of Pharr and Humphreys [Creation and traversal of hierarchical grids and kd-trees; with example code and tricky cases]
pp. 67-74 of book "Realistic Image Synthesis Using Photon Mapping", Henrik Wann Jensen [Creation and balancing of kd-trees]
Efficiency Issues for Ray Tracing, Brian Smitts, JGT Vol 3, #2, 1998. [Describes which efficiency optimizations work best in practice for bounding volume hierarchies].
Simple and Efficient Traversal Methods for Quadtrees and Octrees, Frisken and Pettry, JGT, 7(3), 2002.
The Ray Tracing Kernel, by David Kirk and James Arvo. In Proceedings of Ausgraph `88, Melbourne, Australia, July 1988. [explains how to use object-oriented techniques to allow arbitrary nesting of different acceleration data structures].
Ray Tracing with the BSP Tree, Sung and Shirley, Graphics Gems III, edited by Kirk, pp. 271--274.
Additional readings listed at end of Chapter 4 of Pharr and Humphreys