[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article
Free access

An adaptive subdivision algorithm and parallel architecture for realistic image synthesis

Published: 01 January 1984 Publication History

Abstract

An algorithm for computing ray traced pictures is presented, which adaptively subdivides scenes into S subregions, each with roughly uniform load. It can yield speedups of O(S2/3) over the standard algorithm.
This algorithm can be mapped onto a parallel architecture consisting of a three dimensional array of computers which operate autonomously. The algorithm and architecture are well matched, so that communication overhead is small with respect to the computation, for sufficiently complex scenes. This allows close to linear improvements in performance, even with thousands of computers, in addition to the improvement due to subdivision.
The algorithm and architecture provide mechanisms to gracefully degrade in response to excessive load. The architecture also tolerates failures of computers without errors in the computation.

References

[1]
Peter R. Atherton, Kevin J. Weiler, and Donald P. Greenberg, "Polygon Shadow Generation," pp. 275-281 in SIGGRAPH '78 Conference Proceedings, ACM,(August, 1978)
[2]
Richard H. Bartels, John C. Beatty, and Brian A. Barsky, An Introduction to the Use of Splines in Computer Graphics, Technical Report No. UCB/CSD 83/136, Computer Science Division, Electrical Engineering and Computer Sciences Department, University of California, Berkeley, California, USA. (August, 1983). Also Tech. Report No. CS-83-9, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada.
[3]
James F. Blinn, "A Generalization of Algebraic Surface Drawing," ACM Transactions on Graphics, Vol. 1, No. 3, July, 1982, pp. 235-256. Also published in SIGGRAPH '82 Conference Proceedings (Vol. 16, No. 3)
[4]
John G. Cleary, Brian Wyvill, Graham M. Birtwistle, and Reddy Vatti, Multiprocessor Ray Tracing, Technical Report No. 83/128/17, Department of Computer Science, The University of Calgary (October, 1983).
[5]
Franklin C. Crow, "Shadow Algorithms for Computer Graphics," pp. 242-248 in SIGGRAPH '77 Conference Proceedings, ACM,(July, 1977).
[6]
Mark E. Dippé, Spatiotemporal Functional Prefiltering, Ph.D. Thesis, University of California, Berkeley, California (1984).
[7]
Eugene Fiume, Alain Fournier, and Larry Rudolph, "A Parallel Scan Conversion Algorithm with Anti-Aliasing for a General-Purpose Ultracomputer: Preliminary Report," pp. 11-21 in Proceedings Graphics Interface '83, (May, 1983)
[8]
W. Randolph Franklin, "A Linear Time Exact Hidden Surface Algorithm," pp. 117-123 in SIGGRAPH '80 Conference Proceedings, ACM, (July, 1980).
[9]
Fuchs, H. and Poulton, J., "Pixel-Planes: A VLSI-Oriented Design for a Raster Graphics Engine," VLSI Design. No. 3, 1981, pp. 20-28.
[10]
Fussell, D. and Rathi, B., "A VLSI-Oriented Architecture for Real-Time Display of Shaded Polygons," pp. 373-380 in Graphics Interface '82, (1982).
[11]
Clark, James H., "The Geometry Engine: A VLSI System for Graphics," pp. 127-133 in SIGGRAPH '82 Conference Proceedings, (July, 1982)
[12]
Roy A. Hall and Donald P. Greenberg, "A Testbed for Realistic Image Synthesis," IEEE Computer Graphics and Applications, Vol. 3, No. 8, November, 1983, pp. 10-19.
[13]
James T. Kajiya, "New Techniques for Raytracing Procedurally Defined Objects," ACM Transactions on Graphics, Vol. 2, No. 3, July, 1983, pp. 161-181.
[14]
Hans P. Moravec, "3D Graphics and the Wave Theory," pp. 289-296 in SIGGRAPH '81 Conference Proceedings, (August, 1981).
[15]
H. Nishimura, H. Ohno, T. Kawata, I. Shirakawa, and K. Omura, "LINKS-1: A Parallel Pipelined Multimicrocomputer System for Image Creation," pp. 387-394 in Proceedings of the 10th Symposium on Computer Architecture, SIGARCH,(1983).
[16]
George Pólya and Gabor Szegö, Problems and Theorems in Analysis I, Springer-Verlag, New York (1972).
[17]
Steven M. Rubin and J. Turner Whitted, "A 3-Dimensional Representation for Fast Rendering of Complex Scenes," pp. 110-116 in SIGGRAPH '80 Conference Proceedings, ACM,(July, 1980).
[18]
Ivan E. Sutherland, Robert F. Sproull, and Robert A. Schumacker, "A Characterization of Ten Hidden Surface Algorithms," ACM Computing Surveys, Vol. 6, No. 1, March, 1974, pp. 1-55.
[19]
J. E. Thornton, Design of a Computer: The Control Data 6600, Scott, Foresman and Company, Glenview, Illinois (1970).
[20]
Michael Ullner, Parallel Machines for Computer Graphics, Ph.D. Thesis, California Institute of Technology, Pasadena, California (1983).
[21]
Weinberg, Richard, "Parallel Processing Image Synthesis and Anti-Aliasing," pp. 55-62 in SIGGRAPH '81 Conference Proceedings, (August, 1981).
[22]
J. Turner Whitted, "An Improved Illumination Model for Shaded Display," Communications of the ACM, Vol. 23, No. 6, June, 1980, pp. 343-349.

Cited By

View all
  • (2022)R2E2ACM Transactions on Graphics10.1145/3528223.353017141:4(1-12)Online publication date: 22-Jul-2022
  • (2014)Parallel methodologies for a micropolygon rendererProceedings of the 14th Eurographics Symposium on Parallel Graphics and Visualization10.5555/2855568.2855573(17-24)Online publication date: 9-Jun-2014
  • (2014)Exploring the Spectrum of Dynamic Scheduling Algorithms for Scalable Distributed-MemoryRay TracingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2013.26120:6(893-906)Online publication date: 1-Jun-2014
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGGRAPH Computer Graphics
ACM SIGGRAPH Computer Graphics  Volume 18, Issue 3
July 1984
264 pages
ISSN:0097-8930
DOI:10.1145/964965
Issue’s Table of Contents
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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1984
Published in SIGGRAPH Volume 18, Issue 3

Check for updates

Author Tags

  1. Adaptive
  2. Parallel
  3. Ray tracing
  4. Subdivision

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)195
  • Downloads (Last 6 weeks)21
Reflects downloads up to 03 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2022)R2E2ACM Transactions on Graphics10.1145/3528223.353017141:4(1-12)Online publication date: 22-Jul-2022
  • (2014)Parallel methodologies for a micropolygon rendererProceedings of the 14th Eurographics Symposium on Parallel Graphics and Visualization10.5555/2855568.2855573(17-24)Online publication date: 9-Jun-2014
  • (2014)Exploring the Spectrum of Dynamic Scheduling Algorithms for Scalable Distributed-MemoryRay TracingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2013.26120:6(893-906)Online publication date: 1-Jun-2014
  • (2007)Generating High Quality Pictures by Ray‐TracingComputer Graphics Forum10.1111/j.1467-8659.1985.tb00198.x4:2(87-99)Online publication date: 9-Oct-2007
  • (2007)Evaluation of parallel ray tracing algorithm using screen space subdivision for image generation system MAGGSystems and Computers in Japan10.1002/scj.469025110825:11(78-87)Online publication date: 21-Mar-2007
  • (2005)Message handling in parallel radianceRecent Advances in Parallel Virtual Machine and Message Passing Interface10.1007/3-540-63697-8_121(486-493)Online publication date: 29-Jul-2005
  • (2004)Tuning of algorithms for independent task placement in the context of demand-driven parallel ray tracingProceedings of the 5th Eurographics conference on Parallel Graphics and Visualization10.5555/2386103.2386120(101-109)Online publication date: 10-Jun-2004
  • (2004)Computer graphics for water modeling and rendering: a surveyFuture Generation Computer Systems10.1016/j.future.2004.05.02620:8(1355-1374)Online publication date: Nov-2004
  • (2002)A PVM-Based Parallel Implementation of the REYES Image Rendering ArchitectureProceedings of the 9th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface10.5555/648139.749474(165-173)Online publication date: 29-Sep-2002
  • (2002)Computer Graphics Techniques for Realistic Modeling, Rendering, and Animation of Water. Part IProceedings of the International Conference on Computational Science-Part II10.5555/645458.655472(181-190)Online publication date: 21-Apr-2002
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media