______________________________________________________________________________ FAQ for realtime raytracing ______________________________________________________________________________ This is the official FAQ for the realtime raytracing mailinglist and the RTRT Realm web page. The faq and the mailinglist are about speed optimization for raytracing, NOT about raytracing in general. For information about raytracing look at the comp.graphics.algorithms FAQ and newsgroup (http://www.faqs.org/faqs/graphics/algorithms-faq/), the ray tracing FAQ (http://www.faqs.org/faqs/graphics/raytrace-faq/), and the Ray Tracing News (http://www.raytracingnews.org/). ______________________________________________________________________________ Version 0.04b - 30/11/2000 Mantainer: wally@italymail.com ______________________________________________________________________________ ______________________________________________________________________________ SUMMARY ______________________________________________________________________________ ------- GENERAL QUESTIONS ------- Q: What are the resources available on the net for realtime raytracing? Q: Is there any newsgroup about RTRT? Q: What papers and projects are about RTRT? Q: What papers are there on efficiency in general raytracing? Q: Is there any hardware providing realtime raytracing? Q: What are the main differences between realtime and normal raytracing? Q: Is there any difference between realtime and interactive raytracing? Q: What RTRT demos can I download for my PC? ------- CODING QUESTIONS ------- Q: Where can I find source code for realtime raytracing? Q: What is first hit optimization? Q: What is hybrid raytracing? Q: What is subsampling? Q: What's the best spatial partitioning scheme to use? Q: What's 3DDDA? Q: How can temporal coherence be exploited? Q: What are shadow buffers? Q: What are algorithms for volumetric light scattering in a realtime setting? ------- ACKNOWLEDGMENTS ------- ______________________________________________________________________________ GENERAL QUESTIONS ______________________________________________________________________________ Q: What are the resources available on the net for realtime raytracing? A: - A page collecting demos running on PC under MSDOS or Windows is at http://www.acm.org/tog/resources/RTNews/demos/overview.html - A mailinglist exists, subscription at: http://www.egroups.com/subscribe/realtime_raytracing - No IRC channel on RTRT is stable. Usually people meet on IRCnet europe on #coders. ______________________________________________________________________________ Q: Is there any newsgroup about RTRT? A: No newsgroup yet. The community now gathers itself on the mailinglist mentioned above. As we reach a significant number and level of activity a newsgroup might be created. ______________________________________________________________________________ Q: What papers and projects are about RTRT? A: - "Towards realtime raytracing of combinatorial solid geometry" available at http://ftp.arl.mil/~mike/papers/95cadsymp/realtime.html - Research at Utah University: http://www.cs.utah.edu/vissim/projects/raytracing/ - "Interactive ray tracing," Parker, Martin, Sloan, Shirley, Smits, Hansen. http://www.cs.utah.edu/vissim/projects/raytracing/ - "Interactive ray tracing for isourface rendering," Parker, Shirley, Livnat, Hansen, Sloan. http://www.cs.utah.edu/vissim/projects/raytracing/ - "Dynamic acceleration structures for interactive raytracing," Reinhard, Smits, Hansen. http://www.cs.utah.edu/vissim/projects/raytracing/ - "The Ups and Downs of Multithreaded Ray Tracing and Optimization", John Stone, http://www.acm.org/pubs/tog/resources/RTNews/html/rtnv12n2.html#art3 - "Interactive ray tracing on a virtual shared-memory parallel computer," M.J. Keates and R.J.Hubbold, in Computer Graphics Forum, Vol.14 No.4, 1995. - "Interactive realism for visualization using ray tracing," R.A. Cross, in Proceeding of the 1995 IEEE Visualization Conference, Atlanta, GA. Also related are: - "Interactive ray tracing of VRML scenes in Java," Brandon C. Glaser 1999 - Master thesis Project page: http://graphics.lcs.mit.edu/vrmlTracer/index.html - "Interactive rendering using the render cache," by Bruce Walter, George Drettakis and Steven Parker, EG Workshop on Rendering 99, 1999. http://www-imagis.imag.fr/~George.Drettakis/ - "Interactive ray-traced scene editing using ray segment trees," by Kavita Bala, Julie Dorsey, Seth Teller 1999, Eurographics Workshop on Rendering '99, 1999. http://www.graphics.cornell.edu/~kb/publications.html - "Stochastic raytracing using SIMD processor arrays," by T.T.Y. Lin and M. Slater, in The Visual Computer, Vol.7 No.4, 1991 - "VLSI for ray tracing," by Kenneth Cameron et al in the RTN http://www.acm.org/pubs/tog/resources/RTNews/html/rtnv5n2.html#art18 includes references to some papers on the subject, among these: - "Ray Tracing on Distributed Memory Parallel Computers: Strategies for Distributing Computation and Data," in "Parallel Algorithms and architectures for 3D Image Generation", ACM SIGGRAPH '90 Course 28 ______________________________________________________________________________ Q: What papers are there on efficiency in general raytracing? A: There are a huge number of papers on the topic. See the book "An Introduction to Ray Tracing", by Glassner et al.; Arvo and Kirk's chapter has a good (though somewhat dated) overview of the various schemes used and references to papers. See the ray tracing bibliography for a list of papers: http://www.acm.org/tog/resources/bib/ Some papers we have found to be useful: - "A faster voxel traversal algorithm for ray tracing", John Amanatides and Andrew Woo, Eurographics '87, 1987, p. 3-10. Explanation of 3D grid traversal - "Efficiency issues for raytracing" Brian Smits, journal of graphics tools. http://www.cs.utah.edu/~bes/papers/fastRT/ - "A search structure based on k-d trees for efficient ray tracing" K.R. Subramanian, Donald S. Fussell http://www.cs.uncc.edu/~krs/publ.html _______________________________________________________________________________ Q: Is there any hardware providing realtime raytracing? A: One manufacturer offering hardware raytracing systems is ART technology (http://www.art-render.com). Its solutions aren't targeting interactive use, though. A presentation is available at: http://www.merl.com/hwws99/presentations/ar250/index.htm "The VolumePro Real-Time Ray-Casting System", detailed in http://www.graphics.lcs.mit.edu/~fredo/Book/Stuff/volumePro.pdf discusses MERL's approach to volume rendering. More at: http://www.merl.com/projects/render/index.html There are rumours about ongoing R&D for low-end hardware, but so far these are just rumours. ______________________________________________________________________________ Q: What are the main differences between realtime and normal raytracing? A: A RTRTracer focusses on speed, not on quality. Whereas a normal raytracer is usually general purpose, a realtime raytracing demonstration can assume simplifications and special cases in both the scene being rendered and the algorithms used. So, often a realtime raytracer can use axis aligned primitives, no antialiasing, static lights, shadows cast on part of the scene, a sphereflake primitive, red, green or blue only lights... the more spectacular the result the better. In a demoscene context even fakes are welcome, like environment mapping, which is usually avoided in serious products. ______________________________________________________________________________ Q: Is there any difference between realtime and interactive raytracing? A: While interactive raytracing must clearly be realtime by virtue, the reverse is not a must. Therefore, a realtime raytracing demonstration could use data related to future frames to exploit temporal coherence, where interactive raytracing cannot exactly predict the contents of future frames. ______________________________________________________________________________ Q: What RTRT demos can I download for my PC? A: Look at http://www.acm.org/tog/resources/RTNews/demos/overview.html Some other demos might be available on the files web section for the mailinglist, but on a less permanent basis: http://www.egroups.com/groups/realtime_raytracing ______________________________________________________________________________ ______________________________________________________________________________ CODING QUESTIONS ______________________________________________________________________________ Q: Where can I find source code for realtime raytracing? A: A team for an open source realtime raytracer is forming currently. Released source code include: - the Taint intro by Marco "Pan" Foco (pan@spinningkids.org). - the Doublert 4k presented at Asm2k ______________________________________________________________________________ Q: What is first hit optimization? A: First hit optimizations concern the rays originating from the eye/camera: In this case some precalculations/simplifications for the intersection test can be done, exploiting various properties of the rays: - view frustrum culling can be used. - all rays originate from a single fixed point (i.e. quantities like the vector "sphere centre - ray origin" in an intersection test remain constant for all primary rays). - with a standard camera rays intersect a virtual screen plane in a regular pattern (a grid) which happens to be linear: to intersect rational implicit surfaces on subsequent points finite differences (for example) can be used see i.e: "The mathematics of quadric surface rendering and SOID," by P. Heckbert, 1984. http://www.cs.cmu.edu/~ph/ - rays corresponding to a scanline lie on a plane, see i.e.: "Faster ray tracing using scanline rejection", by Tomas Moeller in Graphics Gems V, Alan W. Paeth editor, (c)1995 Academic Press - actual intersection tests can be totally avoided by reversing the process: see hybrid raytracing Other related papers are: "Immediate-mode ray-casting" by John Alex and Seth Teller, 1999 Technical report MIT LCS TR-768. http://www.graphics.lcs.mit.edu/~seth/pubs/pubs.html ______________________________________________________________________________ Q: What is hybrid raytracing? A: Hybrid raytracing usually consists in using painter and scan-line (or Z-buffer) algorithms to determine visibility, followed by standard rays traced from each hit point, thereby skipping primary rays and related calculations. It's sometines named first hit optimizing, being very similar to this. Commercial products using hybrid raytracing include Maxis' Cinema 4D and discreet's 3DS MAX. ______________________________________________________________________________ Q: What is subsampling? A: In RTRT circles, subsampling (also referred to as undersampling, and incorrectly as supersampling) exploits spatial coherence in screen areas where all rays are likely to hit the same object. A single sample usually is taken every 4*4 pixels square, and then a refinement occurs only if all 4 rays at the square's corners didn't hit the same object. So calculations are performed where it's most likely they are needed: on object boundaries. This approach has some drawbacks: narrow features and objects thinner than 4 pixels might fall within the unsampled spaces, and therefore get lost. One realtime ray tracer using this type of technique is Paul Kahler's: http://www.oakland.edu/~phkahler/rtrt/, see especially his page: http://www.oakland.edu/~phkahler/rtrt/dre.html Also see: - Akimoto, Mase, Hashimoto & Suenaga - "Pixel selected ray tracing" in Eurographics 1989 - "Fast ray tracing of sequences by ray history evaluation" by Arno Formella, Christian Gill, Volker Hofmeyer. http://www-wjp.cs.uni-sb.de/~vhof/nv_widon.html ______________________________________________________________________________ Q: What's the best spatial partitioning scheme to use? A: There is no definitive answer to this question. Among bounding volume hierarchy, BSP trees, octrees, uniform grids, and nested grids, the latter seem to offer the best results when the closest intersection is desired (i.e. eye/reflect/refract rays), though bounding volume hierarchies can be comparable in speed for shadow testing. Also k-d trees seem to be quite widespread. Extensive discussions were reported in the Ray Tracing News, see i.e. v.12 n.1 & n.2, http://www.raytracingnews.org/ _____________________________________________________________________________ Q: What's 3DDDA? A: Start with a uniform grid around some scene, with objects in the scene stored in the grid cells that they overlap. 3DDDA is the process of shooting a ray through this grid, looking for an intersection. It is something like a 3D Bresenham line drawing algorithm, except that there is no "major stepping axis", i.e. all cells that the ray hits must be examined. As soon as an intersection is found in a grid cell, the traversal process can be stopped. This method is extremely fast when the grid cell bounding box closely fits the objects; large empty spaces in the uniform grid slow it down, so sparsely populated scenes might perform better with nested grids, octrees, bounding volume hierarchies, or other methods. Simple voxel traversal code by D. Cohen is included in Graphics Gems IV (p.366). Also useful can be "A faster voxel traversal algorithm for ray tracing", John Amanatides and Andrew Woo, Eurographics '87, 1987, p. 3-10. _____________________________________________________________________________ Q: How can temporal coherence be exploited? A: Just consider your animation as a scene in 4D space instead of 3D space, by adding time (with objects swept along their path, they become 4D hypervolumes), and then adapt typical 3D coherence methods to this new space. see also: - "Object space temporal coherence for raytracing," by David Jevans, in Proceedings of Graphics Interface '92 Canadian Information processing Society - Toronto, Ontario May 1992, p. 176-183 - "Spacetime Ray Tracing for Animation," Andrew S. Glassner, IEEE Computer Graphics and Applications, vol.8, no.2, March 1988, p. 60-70 Reusing the 3D grid from previous frames for objects moving in a scene: - "Dynamic acceleration structures for interactive raytracing," Reinhard, Smits, Hansen. http://www.cs.utah.edu/vissim/projects/raytracing/ Other approaches work in image space trying to reuse data obtained from the previous frames, see i.e.: - "Interactive rendering using the render cache" by Bruce Walter, George Drettakis, Steven Parker, EG Workshop on Rendering 99, 1999. http://www-imagis.imag.fr/~George.Drettakis/ ______________________________________________________________________________ Q: What are shadow buffers? A: Shadow buffers (or shadow maps) contain Z-buffered data for the scene as seen by the light, especially useful in RTRT with static scenes flythroughs. Implementation details and techniques are found in: - "The shadow depth map revisited" by Andrew Woo, in Graphics Gems III (though beware, this method has flaws - see the next reference) - Real-Time Rendering by E.Haines & T.Moeller http://www.realtimerendering.com - NVIDIA Developer's web site: "Shadow Mapping in OpenGL", http://www.nvidia.com/marketing/developer/devrel.nsf/TechnicalDemosFrame ______________________________________________________________________________ Q: What are algorithms for volumetric light scattering in a realtime setting? A: General integration for volumetric data such as light scattering is considered too slow for realtime. Special cases can instead be solved analytically, like with pointlights, uniform cones, and Warn lights. Still the Rubicon II intro presents interesting fog... ______________________________________________________________________________ ACKNOWLEDGMENTS: Many thanks to Eric Haines for proofreading and correcting this FAQ, and to all the mailing list subscribers for making it necessary :) ______________________________________________________________________________