“An adaptive subdivision algorithm and parallel architecture for realistic image synthesis” by Dippe and Swensen

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.

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.