research-article

Discrete Ray Tracing

Authors:

Arie KaufmanAuthors Info & Claims

IEEE Computer Graphics and Applications, Volume 12, Issue 5

Pages 19 - 28

https://doi.org/10.1109/38.156009

Published: 01 September 1992 Publication History

Abstract

Discrete ray tracing, or 3-D raster ray tracing (RRT), which, unlike existing ray tracing methods that use geometric representation for the 3-D scene employs a 3-D discrete raster of voxels for representing the 3-D scene in the same way a 2-D raster of pixels represents a 2-D image, is discussed. Each voxel is a small quantum unit of volume that has numeric values associated with it representing some measurable properties or attributes of the real object or phenomenon at that voxel. It is shown that RRT operates in two phases: preprocessing voxel and discrete ray tracing. In the voxel phase, the geometric model is digitized using 3-D scan-conversion algorithms that convert the continuous representation of the model into a discrete representation within the 3-D raster. In the second phase, RRT employs a discrete variation of the conventional recursive ray tracer in which 3-D discrete rays are traversed through the 3-D raster to find the first surface voxel. Encountering a nontransparent voxel indicates a ray-surface hit. Results obtained by running the RRT software one one 20-MIPS (25-GHz) processor of a Silicon Graphics 4D/240GTX are presented in terms of CPU time.

References

[1]

1. A. Fujimoto, T. Tanata, and K. Iwata, "ARTS: Accelerated Ray-Tracing System," IEEE Computer Graphics and Applications, Vol. 6, No. 4, April 1986, pp. 16-26.]]

Digital Library

[2]

2. J. Amanatides and A. Woo, "A Fast Voxel Traversal Algorithm for Ray Tracing," Proc. Eurographics 87, North Holland, Amsterdam, Aug. 1987, pp. 3-9.]]

[3]

3. J.G. Cleary and G. Wyvill, "Analysis of an Algorithm for Fast Ray Tracing using Uniform Space Subdivision," Visual Computer, Vol. 4, 1988, pp. 65-83.]]

[4]

4. M. Levoy, "Display of Surfaces from Volume Data," IEEE Computer Graphics and Applications, Vol. 8, No. 5, May 1988, pp. 29-37.]]

Digital Library

[5]

5. J.F. Blinn, "Light Reflection Functions for Simulation for Clouds and Dusty Surfaces," Computer Graphics (Proc. Siggraph), Vol. 16, No. 3, July 1982, pp. 21-29.]]

Digital Library

[6]

6. J.T. Kajiya and B.P. Von Herzen, "Ray Tracing Volume Densities," Computer Graphics (Proc. Siggraph), Vol. 18, No. 3, July 1984, pp. 165-174.]]

Digital Library

[7]

7. A. Kaufman, R. Yagel, and D. Cohen, "Intermixing Surface and Volume Rendering," in 3D Imaging in Medicine: Algorithms, Systems, Applications, K.H. Höhne, H. Fuchs, and S.M. Pizer, eds., Springer-Verlag, Berlin, 1990, pp. 217-227.]]

[8]

8. R. Yagel, A. Kaufman, and O. Zhang, "Realistic Volume Imaging," Proc. Visualization 91, IEEE Computer Society Press, Los Alamitos, Calif., Oct. 1991, pp. 226-231.]]

Digital Library

[9]

9. A. Woo and J. Amanatides, "Voxel Occlusion Testing: A Shadow Determination Accelerator for Ray Tracing," Proc. Graphics Interface 90, Canadian Information Processing Society, Toronto, 1990, pp. 223- 230.]]

Digital Library

[10]

10. W. Mokrzycki, "Algorithms of Discretization of Algebraic Spatial Curves on Homogeneous Cubical Grids," Computers and Graphics, Vol. 12, No. 3/4, 1988, pp. 477-487.]]

[11]

11. A. Kaufman and E. Shimony, "3D Scan-Conversion Algorithms for Voxel-Based Graphics," Proc. 1986 Workshop on Interactive 3D Graphics, University of North Carolina, Chapel Hill, Oct. 1986, pp. 45-75.]]

Digital Library

[12]

12. A. Kaufman, "An Algorithm for 3D Scan-Conversion of Polygons," Proc. Eurographics 87, North Holland, Amsterdam, Aug. 1987, pp. 197-208.]]

[13]

13. A. Kaufman, "Efficient Algorithms for 3D Scan-Conversion of Parametric Curves, Surfaces, and Volumes," Computer Graphics (Proc. Siggraph), Vol. 21, No. 4, July 1987, pp. 171-179.]]

Digital Library

[14]

14. D. Cohen and A. Kaufman, "Scan-Conversion Algorithms for Linear and Quadratic Objects," in Volume Visualization, A. Kaufman, ed., IEEE Computer Society Press, Los Alamitos, Calif., 1990, pp. 280- 301.]]

[15]

15. A. Kaufman, "The Voxblt Engine: A Voxel Frame Buffer Processor," in Advances in Graphics Hardware III, A.A.M. Kuijk and W. Strasser, eds., Springer-Verlag, Berlin, 1992.]]

Digital Library

[16]

16. U. Tiede et al., "Investigation of Medical 3D-Rendering Algorithms," IEEE Computer Graphics and Applications, Vol. 10, No. 3, March 1990, pp. 41-53.]]

Digital Library

Cited By

Čomić L(2022)On the Number of 0-Tandems in Simple nD Digital 0-Connected CurvesCombinatorial Image Analysis10.1007/978-3-031-23612-9_3(46-55)Online publication date: 13-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-23612-9_3
Čomić LMagillo P(2019)Repairing 3D Binary Images Using the FCC GridJournal of Mathematical Imaging and Vision10.1007/s10851-019-00904-061:9(1301-1321)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.1007/s10851-019-00904-0
Porter-Sobieraj JŠwiechowski M(2010)Fast and accurate machined surface rendering using an octree modelProceedings of the 2010 international conference on Computer vision and graphics: Part II10.5555/1894615.1894650(276-283)Online publication date: 20-Sep-2010
https://dl.acm.org/doi/10.5555/1894615.1894650
Show More Cited By

Discrete Ray Tracing
1. Computing methodologies
  1. Artificial intelligence
  2. Computer graphics
    1. Rendering

Recommendations

Distributed ray tracing

Ray tracing is one of the most elegant techniques in computer graphics. Many phenomena that are difficult or impossible with other techniques are simple with ray tracing, including shadows, reflections, and refracted light. Ray directions, however, ...
Ray tracing-based interactive diffuse indirect illumination

Despite great efforts in recent years to accelerate global illumination computation, the real-time ray tracing of fully dynamic scenes to support photorealistic indirect illumination effects has yet to be achieved in computer graphics. In this paper, we ...
Adaptive radiosity textures for bidirectional ray tracing

We present a rendering method designed to provide accurate, general simulation of global illumination for realistic image synthesis. Separating surface interaction into diffuse plus specular, we compute the specular component on the fly, as in ray ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Computer Graphics and Applications

IEEE Computer Graphics and Applications Volume 12, Issue 5

September 1992

110 pages

ISSN:0272-1716

Issue’s Table of Contents

Copyright © Copyright © 1992 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 September 1992

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Čomić L(2022)On the Number of 0-Tandems in Simple nD Digital 0-Connected CurvesCombinatorial Image Analysis10.1007/978-3-031-23612-9_3(46-55)Online publication date: 13-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-23612-9_3
Čomić LMagillo P(2019)Repairing 3D Binary Images Using the FCC GridJournal of Mathematical Imaging and Vision10.1007/s10851-019-00904-061:9(1301-1321)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.1007/s10851-019-00904-0
Porter-Sobieraj JŠwiechowski M(2010)Fast and accurate machined surface rendering using an octree modelProceedings of the 2010 international conference on Computer vision and graphics: Part II10.5555/1894615.1894650(276-283)Online publication date: 20-Sep-2010
https://dl.acm.org/doi/10.5555/1894615.1894650
Shen RBoulanger P(2007)Hardware-accelerated volume rendering for real-time medical data visualizationProceedings of the 3rd international conference on Advances in visual computing - Volume Part II10.5555/1779090.1779176(801-810)Online publication date: 26-Nov-2007
https://dl.acm.org/doi/10.5555/1779090.1779176
Lim SShin B(2007)A Half-Skewed Octree for Volume Ray CastingIEICE - Transactions on Information and Systems10.1093/ietisy/e90-d.7.1085E90-D:7(1085-1091)Online publication date: 1-Jul-2007
https://dl.acm.org/doi/10.1093/ietisy/e90-d.7.1085
Shen RBoulanger P(2007)Hardware-Accelerated Volume Rendering for Real-Time Medical Data VisualizationAdvances in Visual Computing10.1007/978-3-540-76856-2_79(801-810)Online publication date: 26-Nov-2007
https://dl.acm.org/doi/10.1007/978-3-540-76856-2_79
Chatelier PMalgouyres R(2006)A low-complexity discrete radiosity methodComputers and Graphics10.1016/j.cag.2005.10.00830:1(37-45)Online publication date: 1-Feb-2006
https://dl.acm.org/doi/10.1016/j.cag.2005.10.008
Lim SShin B(2006)Bidirectional distancemap for efficient volume ray castingProceedings of the 21st international conference on Computer and Information Sciences10.1007/11902140_37(334-342)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1007/11902140_37
Lim SShin B(2006)Hierarchical σ-octree for visualization of ultrasound datasetsProceedings of the Third international conference on Fuzzy Systems and Knowledge Discovery10.1007/11881599_129(1044-1053)Online publication date: 24-Sep-2006
https://dl.acm.org/doi/10.1007/11881599_129
Zhao HXiao P(2006)An accurate vertex normal computation schemeProceedings of the 24th international conference on Advances in Computer Graphics10.1007/11784203_38(442-451)Online publication date: 26-Jun-2006
https://dl.acm.org/doi/10.1007/11784203_38
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents