More Web Proxy on the site http://driver.im/

Article

Free access

The geometry of beam tracing

Authors:

David G. Kirkpatrick,

John P. WalshAuthors Info & Claims

SCG '85: Proceedings of the first annual symposium on Computational geometry

Pages 55 - 61

https://doi.org/10.1145/323233.323241

Published: 01 June 1985 Publication History

Abstract

A solution to the hidden surface elimination problem called Beam Tracing is described. Beam tracing is related to ray tracing but uses spatial coherence within the scene, and area coherence within the image to batch computations. Beam tracing is an object space solution to the hidden surface problem.

Beam tracing is formulated in terms of its principal subprocesses: intersection, sorting, and clipping. A Hierarchical Scene Representation is proposed. This incorporates the space decomposition idea of the BSP tree [Fuchs, Kedem and Naylor, 80] along with the convex polytope intersection detection technique of [Dobkin and Kirkpatrick, 83] to interleave and efficiently solve the intersection and sorting subproblems of beam tracing.

References

[1]

[Amanatides, 84] Amanatides, J. "Ray Tracing With Cones", Computer Graphics, Vol. 18, No. 3, (Proceedings SIGGRAPH) July, 1984, pp. 129-135.

Digital Library

[2]

[Chazelle and Dobkin, 80] Chazelle, B. and Dobkin, D. "Detection is Easier Than Computation", ACM Symposium on Theory of Computing, Los Angeles, May, 1980, pp. 146-153.

Digital Library

[3]

[Clark, 76] Clark, J. H. "Hierarchical Geometric Models for Visible Surface Algorithms", CACM Vol. 19, No. 10, October, 1976, pp. 547-554.

Digital Library

[4]

[Dadoun, 82] Dadoun, N. "Hierarchical Approaches to The Hidden Surface Problem", M.Sc. Thesis, University of British Columbia, Vancouver, Canada, December, 1982.

[5]

[Dadoun, Kirkpatrick and Walsh, 82] Dadoun, N., Kirkpatrick, D. G., and Walsh, J. P. "Hierarchical Approaches to Hidden Surface Intersection Testing", Proceedings Graphics Interface 82, NCGA, Toronto, May, 1982.

[6]

[Dadoun, Kirkpatrick and Walsh, 85] Dadoun, N., Kirkpatrick, D. G., and Walsh, J.P. "Hierarchical Methods for Beam Tracing", In Preparation, 1985.

[7]

[Dobkin and Kirkpatrick, 83] Dobkin, D. P. and Kirkpatrick, D. G. "Fast Detection of Polyhedral Intersections", Theoretical Computer Science, 17, 1983, pp. 241-253.

[8]

[Fuchs, Kedem and Naylor, 80] Fuchs, H., Kedem, Z. M., and Naylor, B. F. "On Visible Surface Generation by A Priori Tree Structures", Computer Graphics, Vol. 14, No. 3, (Proceedings SIGGRAPH) July, 1980, pp. 124-133.

Digital Library

[9]

[Fuchs, Abrams and Grant, 83] Fuchs, H., Abrams, G. D., and Grant, E. D. "Near Real-Time Shaded Display of Rigid Objects", Computer Graphics, Vol. 17, No. 3, (Proceedings SIGGRAPH) July, 1983, pp. 65-72.

Digital Library

[10]

[Glassner, 84] Glassner, Andrew S. "Space Subdivision for Fast Ray Tracing", CG&A, Vol. 4, No. 10, October, 1984, pp. 15-22.

[11]

[Heckbert and Hanrahan, 84] Heckbert, Paul, S., and Pat Hanrahan, "Beam Tracing Polygonal Objects", Computer Graphics, Vol. 18, No. 3, (Proceedings SIGGRAPH) July, 1984, pp. 119-127.

Digital Library

[12]

[Kirkpatrick, 83] Kirkpatrick, D. G. "Optimal Search in Planar Subdivisions", SIAM Journal on Computing, 12(1), 1983, pp. 28-35.

[13]

[Preparata and Hong, 77] Preparata, F. P., and Hong, S. J. "Convex Hulls of Finite Sets of Points in Two and Three Dimensions", CACM, Vol. 20, No. 2, Feb. 1977, pp. 87-93.

Digital Library

[14]

[Roth, 82] Roth, S. D. "Ray Casting for Modelling Solids", CGIP, Vol. 18, February, 1982, pp. 109-144.

[15]

[Rubin and Whitted, 80] Rubin, S. M., and Whitted, T. "A 3-Dimensional Representation for Fast Rendering of Complex Scenes" SIGGRAPH 80 Proceedings, Computer Graphics Vol. 14, No. 3, July 1980, pp. 110-116.

Digital Library

[16]

[Sutherland and Hodgman, 74] Sutherland, I. E., and Hodgman, G. W. "Reentrant Polygon Clipping", CACM Vol. 17, No. 1, Jan. 1974, pp. 32-42.

Digital Library

[17]

[Sutherland, Sproull and Schumacker, 74] Sutherland, I. E., Sproull, R. F, and Schumacker, R. A. "A Characterisation of Ten Hidden-Surface Algorithms", Computing Surveys Vol. 6, No. 1, March 1974, pp. 1-55.

Digital Library

[18]

[Walsh, 79] Walsh, J. "The Simulation of Directional Sound Sources in Rooms by Means of a Digital Computer" M. Mus. Thesis, University of Western Ontario, London, Canada, Fall, 1979.

[19]

[Walsh and Dadoun, 81] Walsh, J. and Dadoun, N. "The Design and Development of Godot: A System for Room Acoustics Modelling", presented at 101st meeting of the Acoustical Society of America, Ottawa, May, 1981.

[20]

[Walsh and Dadoun, 82] Walsh, J. and Dadoun, N. "What Are We Waiting for? Development of Godot II", presented at 103rd meeting of the Acoustical Society of America, Chicago, April, 1982.

[21]

[Weiler, 80] Weiler, K. "Polygon Comparison using a Graph Representation", Computer Graphics, Vol. 14, No. 3, (Proceedings SIGGRAPH) July, 1980, pp. 10-18.

Digital Library

[22]

[Weiler and Atherton, 77] Weiler, K., and Atherton, P. "Hidden Surface Removal Using Polygon Area Sorting", Computer Graphics, Vol. 11, No. 2, (Proceeding SIGGRAPH) Summer 1977, pp. 214-222.

Digital Library

[23]

[Whitted, 80] Whitted, Turner. "An Improved Illumination Model for Shaded Display", CACM, Vol. 23, No. 6, June 1980, pp. 343-349.

Digital Library

Cited By

Liu SManocha D(2022)Sound Synthesis, Propagation, and RenderingSynthesis Lectures on Visual Computing10.2200/S01162ED1V01Y202201VCP03311:2(1-110)Online publication date: 24-Mar-2022
https://doi.org/10.2200/S01162ED1V01Y202201VCP033
Ghandeharizadeh S(2021)Holodeck: Immersive 3D Displays Using Swarms of Flying Light Specks [Extended Abstract]Proceedings of the 3rd ACM International Conference on Multimedia in Asia10.1145/3469877.3493698(1-7)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1145/3469877.3493698
Bian HFattah RZhong SZhang X(2020)An efficient rectilinear Gaussian beam tracing method for sound propagation modelling in a non-turbulent mediumThe Journal of the Acoustical Society of America10.1121/10.0002966148:6(4037-4048)Online publication date: Dec-2020
https://doi.org/10.1121/10.0002966
Show More Cited By

Index Terms

The geometry of beam tracing
1. Computing methodologies
  1. Computer graphics
    1. Image manipulation
    2. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Beam tracing polygonal objects
SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques

Ray tracing has produced some of the most realistic computer generated pictures to date. They contain surface texturing, local shading, shadows, reflections and refractions. The major disadvantage of ray tracing results from its point-sampling approach. ...
Beam tracing polygonal objects

Ray tracing has produced some of the most realistic computer generated pictures to date. They contain surface texturing, local shading, shadows, reflections and refractions. The major disadvantage of ray tracing results from its point-sampling approach. ...
Real-time volume caustics with adaptive beam tracing
I3D '11: Symposium on Interactive 3D Graphics and Games

Caustics are detailed patterns of light reflected or refracted on specular surfaces into participating media or onto surfaces. In this paper we present a novel adaptive and scalable algorithm for rendering surface and volume caustics in single-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '85: Proceedings of the first annual symposium on Computational geometry

June 1985

322 pages

ISBN:0897911636

DOI:10.1145/323233

Chairman:
Joseph O'Rourke
Johns Hopkins Univ., Baltimore, MD

Copyright © 1985 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1985

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCG85

Sponsor:

SCG85: The 1st Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry 1985

June 5 - 7, 1985

Maryland, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
685
Total Downloads

Downloads (Last 12 months)75
Downloads (Last 6 weeks)10

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu SManocha D(2022)Sound Synthesis, Propagation, and RenderingSynthesis Lectures on Visual Computing10.2200/S01162ED1V01Y202201VCP03311:2(1-110)Online publication date: 24-Mar-2022
https://doi.org/10.2200/S01162ED1V01Y202201VCP033
Ghandeharizadeh S(2021)Holodeck: Immersive 3D Displays Using Swarms of Flying Light Specks [Extended Abstract]Proceedings of the 3rd ACM International Conference on Multimedia in Asia10.1145/3469877.3493698(1-7)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1145/3469877.3493698
Bian HFattah RZhong SZhang X(2020)An efficient rectilinear Gaussian beam tracing method for sound propagation modelling in a non-turbulent mediumThe Journal of the Acoustical Society of America10.1121/10.0002966148:6(4037-4048)Online publication date: Dec-2020
https://doi.org/10.1121/10.0002966
V. Sander PKeyser J(2016)Guest Editor's Introduction to the Special Section on the ACM Symposium on Interactive 3D Graphics and Games (I3D)IEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2016.259685822:10(2214-2214)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1109/TVCG.2016.2596858
Marković DAntonacci FSarti ATubaro S(2016)3D Beam Tracing Based on Visibility Lookup for Interactive Acoustic ModelingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2016.251561222:10(2262-2274)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1109/TVCG.2016.2515612
Savioja LSvensson U(2015)Overview of geometrical room acoustic modeling techniquesThe Journal of the Acoustical Society of America10.1121/1.4926438138:2(708-730)Online publication date: 10-Aug-2015
https://doi.org/10.1121/1.4926438
Antonacci FSarti ATubaro S(2010)Two-dimensional beam tracing from visibility diagrams for real-time acoustic renderingEURASIP Journal on Advances in Signal Processing10.1155/2010/6423162010(1-18)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1155/2010/642316
Laine SSiltanen SLokki TSavioja L(2009)Accelerated beam tracing algorithmApplied Acoustics10.1016/j.apacoust.2007.11.01170:1(172-181)Online publication date: Jan-2009
https://doi.org/10.1016/j.apacoust.2007.11.011
Antonacci FFoco MSarti ATubaro S(2008)Fast Tracing of Acoustic Beams and Paths Through Visibility LookupIEEE Transactions on Audio, Speech, and Language Processing10.1109/TASL.2008.92006416:4(812-824)Online publication date: 1-May-2008
https://dl.acm.org/doi/10.1109/TASL.2008.920064
Foale CVamplew PHjorth LMilne E(2007)Portal-based sound propagation for first-person computer gamesProceedings of the 4th Australasian conference on Interactive entertainment10.5555/1367956.1367965(1-8)Online publication date: 3-Dec-2007
https://dl.acm.org/doi/10.5555/1367956.1367965
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents