Uso da Heterogeneidade para aceleração de Ray Tracing
Resumo
O objetivo deste trabalho é analisar os ganhos que podem ser obtidos adaptando-se um algoritmo computacionalmente caro a uma nova arquitetura de computadores. No presente caso, o algoritmo objeto da análise é a técnica de síntese de imagens denominada ray tracing, conhecida por produzir imagens com alto grau de realismo, mas a um elevado custo computacional. A estratégia utilizada para se acelerar tal técnica foi explorar o paralelismo inerente a ela num ambiente heterogêneo constituído por máquinas SIMD e MIMD. As implementações mostraram resultados bastante satisfatórios.
Referências
J. Arvo and D. Kirk. Fast ray tracing by ray classification. Comput. Graph., 21(4):55-64, July 1987.
J. Amanatides, Ray tracing with cones. Comput. Graph., 18(3):129-135, July 1984.
R. L. Cook. Stochastic sampling in computer graphics. ACM Trans. Graph., 5(1), January 1986.
R. L. Cook, T. Porter, and L. Carpenter. Distibuted ray tracing. Comput. Graph., 18(3):137-145, July 1984.
J. G. Clearly, B. M. Wyvill, G.M. Birtwistle, and R. Vatti. Multiprocessor ray tracing. Comput. Graph. For., 5:3-12, 1985.
M. Dippe and E. H. Wold. Antialiasing through stochastic sampling. Comput. Graph., 19(3):68-78, July 1985.
A. Fujimoto, T. Tanaka, and K. Iwata. Arts: Accelerated ray-tracing system. IEEE Comput. Graph. Appl., 6(4):16-26, April 1986.
James D. Foley, Andries van Dam, Steven K. Feiner, and John F. Hughes. Computer Graphics: Principles and Practice. Addison-Wesley Publishing Company, 2nd edition, 1990.
Al Geist, Adam Benguelim, Jack Dongarra, Weicheng Jiang, Robert Manchek, and Vandy Sunderam. PVM 3.0 User's Guide and Reference Manual. Oak Ridge National Laboratory, Feb 1993.
M. Gervautz. Three improvements of the ray tracing algorithm for csg trees. Comput. Graph., 10(4):333-339, 1986.
A.S. Glassner. Space subdivision for fast ray tracing. IEEE Comput. Graph. Appl., 4(10):15-22, October 1984.
Andrew S. Glassner, editor. An Introduction to Ray Tracing. Academic Press Inc., 1989.
J. Goldsmith and J. Salmon. A ray tracing system for the hypercube, 1985. Caltech Concurrent Computing Project Memorandum HM154, California Institute of Technology.
J. Goldsmith and J. Salmon, Automatic creation of object hierarchies for ray tracing. IEEE Comput. Graph. Appl., 7(5):14-20, May 1987.
P. Hanrahan. Ray tracing algebraic surfaces. Comput. Graph., 17(3):83-89, July 1983.
R. A. Hall and D. P. Greenberg. A testbed for realistic image synthesis. IEEE Comput. Graph. Appl., 3(10):10-20, November 1983.
E. A. Haines and D. P. Greenberg. The light buffer: a shadow testing accelerator. IEEE Comput. Graph. Appl., 6(9):6-16, September 1986.
P. S, Heckbert and P. Hanrahan. Beam tracing polygonal objects. Comput. Graph., 18(3):119-127, July 1984.
Francis S. Hill. Computer Graphics. Macmillan Publishing Company, Department of Electrical and Computer Engineering - University of Massachusetts, 1990.
F. W. Jansen. Data structures for ray tracing. In L.R.A. Kessener, F.J. Peters, and M.L.P. Lierop, editors, Data Structures for Raster Graphics, Proceedings Workshop, pages 57-73. Springer Verlag, 1986. Eurographics Seminars.
J. T. Kajiya. New techniques for ray tracing procedurally defined objects. Comput. Graph., 17(3):91-102, July 1983.
M. R. Kaplan. Space tracing a constant time ray tracer. state of the art in image synthesis. 11, July 1985. Siggraph '85 Course Notes.
T. L. Kay and J. Kajiya. Ray tracing complex scenes. Comput. Graph., 20(4):269-278, August 1986.
H. Kobayashi, T. Nakamura, and Y. Shigei. Parallel processing of an object space for image synthesis using ray tracing. The Visual Computer, 3(1):13-22, 1987.
M. Lee, A. R. Redner, and S. P. Uselton. Statistically optimized sampling for distributed ray tracing. Comput. Graph., 19(3):61-67, July 1985.
N. L. Max. Vectorized procedural models for natural terrain: waves and islands in the sunset. Comput. Graph., 15(3):317-324, August 1981.
K. Nemoto and T. Omachi. An adaptative subdivision by sliding boundary surfaces. In Proc. of Graphics Interface '86, pages 43-48, Vancouver, B. C., May 1986.
H. Nishimura, H. Ohno, H. Kawata, T. Shirakawa, and K. Omura, Links-I: a parallel pipelined multimicrocomputer system for imagem creation. In Proc. of the 10th Symposium on Computer Architecture, pages 387-394, 1983.
M. Ohta and M. Mackawa. Ray coherence theorem and constant time ray tracing algorithm. In T. L. Kunni, editor, Computer Graphics 1987, pages 303-314. Proc. of CG International '87.
JD. J. Plunkett and M. J. Bailey. The vectorization of a ray-tracing algorithm for improved execution sppeed. JEEE Comput. Graph. Appl., 5(8):52-60, August 1985.
W. Purgathofer. A statistical method for adaptative stochastic sampling. In A. A. G. Requicha, editor, Proc. Eurographics '86, pages 145-152, Elsevier(North-Holland), 1986.
S. D. Roth. Ray casting for modeling solids. Comput. Graph. Image Process., 18:109-144, 1982.
S. Rubbin and T. Whitted. A three-dimensional representation for fast rendering of complex scenes. Comput. Graph., 14(3):110-116, July 1980.
T.W. Sederberg and D.C. Anderson. Ray tracing of steiner patches. Comput. Graph., 18(3):159-164, July 1984.
M. Shinya, T. Takahashi, and S. Naito. Principles and applications of pencil tracing. Comput. Graph., 21(4):45-54, July 1987.
M. K. Ullner. Parallel machines for computer graphics. PhD thesis, California Institute of Technology, Pasadena, California, 1983.
T. Whitted. An improved illumination model for shaded display. Communi. of ACM, 23(6):343-349, June 1980.
J. Amanatides, Ray tracing with cones. Comput. Graph., 18(3):129-135, July 1984.
R. L. Cook. Stochastic sampling in computer graphics. ACM Trans. Graph., 5(1), January 1986.
R. L. Cook, T. Porter, and L. Carpenter. Distibuted ray tracing. Comput. Graph., 18(3):137-145, July 1984.
J. G. Clearly, B. M. Wyvill, G.M. Birtwistle, and R. Vatti. Multiprocessor ray tracing. Comput. Graph. For., 5:3-12, 1985.
M. Dippe and E. H. Wold. Antialiasing through stochastic sampling. Comput. Graph., 19(3):68-78, July 1985.
A. Fujimoto, T. Tanaka, and K. Iwata. Arts: Accelerated ray-tracing system. IEEE Comput. Graph. Appl., 6(4):16-26, April 1986.
James D. Foley, Andries van Dam, Steven K. Feiner, and John F. Hughes. Computer Graphics: Principles and Practice. Addison-Wesley Publishing Company, 2nd edition, 1990.
Al Geist, Adam Benguelim, Jack Dongarra, Weicheng Jiang, Robert Manchek, and Vandy Sunderam. PVM 3.0 User's Guide and Reference Manual. Oak Ridge National Laboratory, Feb 1993.
M. Gervautz. Three improvements of the ray tracing algorithm for csg trees. Comput. Graph., 10(4):333-339, 1986.
A.S. Glassner. Space subdivision for fast ray tracing. IEEE Comput. Graph. Appl., 4(10):15-22, October 1984.
Andrew S. Glassner, editor. An Introduction to Ray Tracing. Academic Press Inc., 1989.
J. Goldsmith and J. Salmon. A ray tracing system for the hypercube, 1985. Caltech Concurrent Computing Project Memorandum HM154, California Institute of Technology.
J. Goldsmith and J. Salmon, Automatic creation of object hierarchies for ray tracing. IEEE Comput. Graph. Appl., 7(5):14-20, May 1987.
P. Hanrahan. Ray tracing algebraic surfaces. Comput. Graph., 17(3):83-89, July 1983.
R. A. Hall and D. P. Greenberg. A testbed for realistic image synthesis. IEEE Comput. Graph. Appl., 3(10):10-20, November 1983.
E. A. Haines and D. P. Greenberg. The light buffer: a shadow testing accelerator. IEEE Comput. Graph. Appl., 6(9):6-16, September 1986.
P. S, Heckbert and P. Hanrahan. Beam tracing polygonal objects. Comput. Graph., 18(3):119-127, July 1984.
Francis S. Hill. Computer Graphics. Macmillan Publishing Company, Department of Electrical and Computer Engineering - University of Massachusetts, 1990.
F. W. Jansen. Data structures for ray tracing. In L.R.A. Kessener, F.J. Peters, and M.L.P. Lierop, editors, Data Structures for Raster Graphics, Proceedings Workshop, pages 57-73. Springer Verlag, 1986. Eurographics Seminars.
J. T. Kajiya. New techniques for ray tracing procedurally defined objects. Comput. Graph., 17(3):91-102, July 1983.
M. R. Kaplan. Space tracing a constant time ray tracer. state of the art in image synthesis. 11, July 1985. Siggraph '85 Course Notes.
T. L. Kay and J. Kajiya. Ray tracing complex scenes. Comput. Graph., 20(4):269-278, August 1986.
H. Kobayashi, T. Nakamura, and Y. Shigei. Parallel processing of an object space for image synthesis using ray tracing. The Visual Computer, 3(1):13-22, 1987.
M. Lee, A. R. Redner, and S. P. Uselton. Statistically optimized sampling for distributed ray tracing. Comput. Graph., 19(3):61-67, July 1985.
N. L. Max. Vectorized procedural models for natural terrain: waves and islands in the sunset. Comput. Graph., 15(3):317-324, August 1981.
K. Nemoto and T. Omachi. An adaptative subdivision by sliding boundary surfaces. In Proc. of Graphics Interface '86, pages 43-48, Vancouver, B. C., May 1986.
H. Nishimura, H. Ohno, H. Kawata, T. Shirakawa, and K. Omura, Links-I: a parallel pipelined multimicrocomputer system for imagem creation. In Proc. of the 10th Symposium on Computer Architecture, pages 387-394, 1983.
M. Ohta and M. Mackawa. Ray coherence theorem and constant time ray tracing algorithm. In T. L. Kunni, editor, Computer Graphics 1987, pages 303-314. Proc. of CG International '87.
JD. J. Plunkett and M. J. Bailey. The vectorization of a ray-tracing algorithm for improved execution sppeed. JEEE Comput. Graph. Appl., 5(8):52-60, August 1985.
W. Purgathofer. A statistical method for adaptative stochastic sampling. In A. A. G. Requicha, editor, Proc. Eurographics '86, pages 145-152, Elsevier(North-Holland), 1986.
S. D. Roth. Ray casting for modeling solids. Comput. Graph. Image Process., 18:109-144, 1982.
S. Rubbin and T. Whitted. A three-dimensional representation for fast rendering of complex scenes. Comput. Graph., 14(3):110-116, July 1980.
T.W. Sederberg and D.C. Anderson. Ray tracing of steiner patches. Comput. Graph., 18(3):159-164, July 1984.
M. Shinya, T. Takahashi, and S. Naito. Principles and applications of pencil tracing. Comput. Graph., 21(4):45-54, July 1987.
M. K. Ullner. Parallel machines for computer graphics. PhD thesis, California Institute of Technology, Pasadena, California, 1983.
T. Whitted. An improved illumination model for shaded display. Communi. of ACM, 23(6):343-349, June 1980.
Publicado
07/09/1993
Como Citar
LIMA, Mauricio Antônio de Castro; CORRÊA, Wagner Toledo; MEIRA JÚNIOR, Wagner; CARVALHO, Márcio Bunte de.
Uso da Heterogeneidade para aceleração de Ray Tracing. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 5. , 1993, Florianópolis/SC.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1993
.
p. 174-188.
DOI: https://doi.org/10.5753/sbac-pad.1993.23031.
