KD-tree acceleration structures for a GPU raytracer

ABSTRACT

Modern graphics hardware architectures excel at compute-intensive tasks such as ray-triangle intersection, making them attractive target platforms for raytracing. To date, most GPU-based raytracers have relied upon uniform grid acceleration structures. In contrast, the kd-tree has gained widespread use in CPU-based raytracers and is regarded as the best general-purpose acceleration structure. We demonstrate two kd-tree traversal algorithms suitable for GPU implementation and integrate them into a streaming raytracer. We show that for scenes with many objects at different scales, our kd-tree algorithms are up to 8 times faster than a uniform grid. In addition, we identify load balancing and input data recirculation as two fundamental sources of inefficiency when raytracing on current graphics hardware.

REFERENCES

• 1: {ATI04} ATI: Radeon X800 product site, 2004. http://www.ati.com/products/radeonx800.
• 2: {BFH*04} Buck I., Foley T., Horn D., Sugerman J., Fatahalian K., Houston M., Hanrahan P.: Brook for GPUs: Stream computing on graphics hardware. In Proceedings of ACM SIGGRAPH 2004 (2004).
• 3: Ian Buck , Pat Hanrahan, Stream computing on graphics hardware, Stanford University, Stanford, CA, 2005
• 4: {BWS03} Benthin C., Wald I., Slusallek P.: A scalable approach to interactive global illumination. In Proceedings of Eurographics (2003), vol. 22, pp. 621--630.
• 5: {CHH02} Carr N. A., Hall J. D., Hart J. C.: The Ray Engine. Tech. Rep. UIUCDCS-R-2002-2269, Department of Computer Science, University of Illinois, 2002.
• 6: {Chr05} Christen M.: Ray Tracing on GPU. Diploma thesis, University of Applied Sciences Basel, Switzerland, 2005.
• 7: H. C. Delany, Ray tracing on a connection machine, Proceedings of the 2nd international conference on Supercomputing, p.659-667, June 1988, St. Malo, France [doi>10.1145/55364.55429]
• 8: {EVG04} Ernst M., Vogelgsang C., Greiner G.: Stack implementation on programmable graphics hardware. In Vision Modeling and Visualization 2004 (2004), pp. 255--262.
• 9: K. Fatahalian , J. Sugerman , P. Hanrahan, Understanding the efficiency of GPU algorithms for matrix-matrix multiplication, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France [doi>10.1145/1058129.1058148]
• 10: {Hal01} Hall D.: The AR350: Today's ray trace rendering processor. 2001 SIGGRAPH / Eurographics Workshop On Graphics Hardware - Hot 3D Session 1, 2001. http://graphicshardware.org/previous/www_2001/presentations/Hot3D_Daniel_Hall.pdf.
• 11: {Hav00} Havran V.: Heuristic Ray Shooting Algorithms. Ph.D. thesis, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague, November 2000.
• 12: {HB02} Havran V., Bittner J.: On improving kd-trees for ray shooting. In Proceedings of WSCG'2002 conference (2002), pp. 209--217.
• 13: {KL04} Karlsson F., Ljungstedt C. J.: Ray Tracing Fully Implemented on Programmable Graphics Hardware. M.S. thesis, Chalmers University of Technology Göteborg, Sweden, 2004.
• 14: {LAM00} Lext J., Assarsson U., Moeller T.: BART: A Benchmark for Animated Ray Tracing. Tech. rep., Chalmers University of Technology, Goeteborg, Sweden, May 2000. http://www.ce.chalmers.se/BART/.
• 15: David J. MacDonald , Kellogg S. Booth, Heuristics for ray tracing using space subdivision, The Visual Computer: International Journal of Computer Graphics, v.6 n.3, p.153-166, 1990 [doi>10.1007/BF01911006]
• 16: {MFM04} Moreno-Fortuny G., McCool M.: Unified stream processing raytracer. Poster at GP^2: The ACM Workshop on General Purpose Computing on Graphics Processors, and SIGGRAPH 2004 poster, 2004. http://www.cgl.uwaterloo.ca/ gmoreno/streamray.html.
• 17: {NVI04} NVIDIA: Geforce 6 series technical specifications, 2004. http://www.nvidia.com/object/geforce6_techspecs.html.
• 18: Timothy J. Purcell , Ian Buck , William R. Mark , Pat Hanrahan, Ray tracing on programmable graphics hardware, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 19: Matt Pharr , Greg Humphreys, Physically Based Rendering: From Theory to Implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 20: Steven Parker , William Martin , Peter-Pike J. Sloan , Peter Shirley , Brian Smits , Charles Hansen, Interactive ray tracing, Proceedings of the 1999 symposium on Interactive 3D graphics, p.119-126, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300537]
• 21: Jörg Schmittler , Ingo Wald , Philipp Slusallek, SaarCOR: a hardware architecture for ray tracing, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 22: Jörg Schmittler , Sven Woop , Daniel Wagner , Wolfgang J. Paul , Philipp Slusallek, Realtime ray tracing of dynamic scenes on an FPGA chip, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France [doi>10.1145/1058129.1058143]
• 23: Ingo Wald , Carsten Benthin , Philipp Slusallek, Distributed Interactive Ray Tracing of Dynamic Scenes, Proceedings of the 2003 IEEE Symposium on Parallel and Large-Data Visualization and Graphics, p.11, October 20-21, 2003 [doi>10.1109/PVGS.2003.1249045]
• 24: {Wen05} Wenzel C.: Far Cry and DirectX. Game Developers Conference, 2005. http://download.nvidia.com/developer/presentations/2005/GDC/Direct3D_Day/D3DTutoria108_FarCryAndDX9.pdf.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture