Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Accelerating ARTS

  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

A major fraction of ray-tracing computation time is spent on ray-object intersection calculation. To reduce this calculation cost, one method, ARTS, subdivides the 3-D object space into voxels and uses a 3-D line-drawing routine to simulate ray propagation in the subdivided space to select objects for intersection testing. Finer space subdivision gives better object selection resolution and fewer ray-object tests. However, as the subdivision increases, the improvement is offset by a linear degradation of the line-drawing-routine efficiency and a cubic growth of the memory requirement. We solve these time and memory scalability problems in ARTS using an adaptive 3-D line-drawing algorithm, which traverses space with multiple stepsizes, and a hybrid database that employs both the octree and the 3-D array data structures. The space traversal cost in our solution grows logarithmically with the subdivision increase, and the memory requirement grows only linearly.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Arvo J, Kirk D (1987) Fast ray tracing by ray classification. Comput Graph (SIGGRAPH), pp 55–64

  2. Arvo J, Kirk D (1988) A survey of ray tracing acceleration techniques. ACM SIGGRAPH'88 Course Notes

  3. Bresenham JE (1982) Incremental line compaction. Comput J 25(1):116–120

    Google Scholar 

  4. Cook RL, Porter T, Carpenter L (1984) Distributed ray tracing. Comput Graph 1803:137–145

    Google Scholar 

  5. Cook R, Torrance K (1982) A reflectance model for computer graphics. ACM Trans Graph 1 (1):7–24

    Google Scholar 

  6. Cleary J, Wyvill G (1988) Analysis of an algorithm for fast ray tracing using uniform space subdivision. The Visual Computer 4:65–83

    Google Scholar 

  7. Cleary J, Wyvill B, Birtwistle G, Vatti R (1983) Multiprocessor ray tracing. Technical report, University of Calgary

  8. Dippe M, Swensen J (1984) An adaptive subdivision algorithm and parallel architecture for realistic image synthesis. Comput Graph (SIGGRAPH), pp 149–158

  9. Elfes A (1989) A tesselated probabilistic representation for spatial robot perception and navigation. In NASA Conference on Space Telerobotics. JPL/NASA

  10. Fujimoto A, Iwata K (1985) Accelerated ray-tracing. Comput Graph, pp 41–65

  11. Fujimoto A, Perrott CG, Iwata K (1986a) Environment for fast elaboration of contructive solid geometry. Advanced Comput Graph: Proc of Computer Graphics Tokyo '86, pp 20–33

  12. Fujimoto A, Tanaka T, Iwata K (1986b) ARTS: accelerated ray-tracing system. IEEE Comput Graph Appl, pp 16–26

  13. Glassner AS (1984) Space subdivision for fast ray tracing. IEEE Comput Graph Appl, pp 15–22

  14. Goldstein R, Nagel R (1971) 3-D visual simulation. Simulation, p 25

  15. Haines E (1987) A proposal for standard graphics environments. IEEE Comput Graph Appl, p 3–5

  16. Kaplan MR (1985) Space-tracing: a constant time raytracer. ACM SIGGR APH '85 Course Notes.

  17. Kaufman A (1988) Efficient algorithms for scan-converting 3d polygons. Comput Graph 12 (2):213–219

    Google Scholar 

  18. Meagher DJ (1980) Octree encoding: a new technique for the representation, the manipulation, and display of arbitrary 3-D objects by computer. Technical report, Image Processing Laboratories, Rensselaer Polytechnic Institute

  19. Phong B (1975) Illumination for computer generated pictures. CACM 18 (6):311

    Google Scholar 

  20. Snyder JM, Barr AH (1987) Ray tracing complex models containing surface tessellations. Comput Graph, p 119–128

  21. Samet H, Webber RE (1988) Hierarchical data structures and algorithms for computer graphics. IEEE Comput Graph Appl, p 48–68

  22. Thibadeau R (1988) CMU raytracer. Technical report, The Robotics Institute, Carnegie-Mellon University

  23. Whitted T (1980) An improved illumination model for shaded display. CACM, p 343–349

  24. Wyvill G, Kunii T, Shirai Y (1986) Space division for ray tracing in CSG. IEEE Comput Graph Appl, p 28

Download references

Author information

Authors and Affiliations

  1. The Robotics Institute, School of Computer Science, Carnegie Mellon University, 15212, Pittsburgh, PA, USA

    Ping-Kang Hsiung & Robert Thibadeau

Authors
  1. Ping-Kang Hsiung
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Robert Thibadeau
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hsiung, PK., Thibadeau, R. Accelerating ARTS. The Visual Computer 8, 181–190 (1992). https://doi.org/10.1007/BF01902138

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01902138

Key words

Search

Navigation