Hybrid sort-first and sort-last parallel rendering with a cluster of PCs

ABSTRACT

We investigate a new hybrid of sort-first and sort-last approach for parallel polygon rendering, using as a target platform a cluster of PCs. Unlike previous methods that statically partition the 3D model and/or the 2D image, our approach performs dynamic, view-dependent and coordinated partitioning of both the 3D model and the 2D image. Using a specific algorithm that follows this approach, we show that it performs better than previous approaches and scales better with both processor count and screen resolution. Overall, our algorithm is able to achieve interactive frame rates with efficiencies of 55.0% to 70.5% during simulations of a system with 64 PCs. While it does have potential disadvantages in client-side processing and in dynamic data management—which also stem from its dynamic, view-dependent nature—these problems are likely to diminish with technology trends in the future.

REFERENCES

• 1: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015]
• 2: Yuqun Chen , Angelos Bilas , Stefanos N. Damianakis , Cezary Dubnicki , Kai Li, UTLB: a mechanism for address translation on network interfaces, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.193-204, October 02-07, 1998, San Jose, California, United States
• 3: J. Clark. A VLSI geometry processor for graphics. Computer (IEEE), 13:59-62, 64, 66-68, July 1980.
• 4: James H. Clark, The Geometry Engine: A VLSI Geometry System for Graphics, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.127-133, July 1982
• 5: Michael Brian Cox, Algorithms for parallel rendering, Princeton University, Princeton, NJ, 1995
• 6: Thomas W. Crockett, PARALLEL RENDERING, Institute for Computer Applications in Science and Engineering (ICASE), 1995
• 7: Thomas W. Crockett, An introduction to parallel rendering, Parallel Computing, v.23 n.7, p.819-843, July 1997 [doi>10.1016/S0167-8191(97)00028-8]
• 8: David A. Ellsworth, A New Algorithm for Interactive Graphics on Multicomputers, IEEE Computer Graphics and Applications, v.14 n.4, p.33-40, July 1994 [doi>10.1109/38.291529]
• 9: Henry Fuchs , Brian W. Johnson, An expandable multiprocessor architecture for video graphics (Preliminary Report), Proceedings of the 6th annual symposium on Computer architecture, p.58-67, April 23-25, 1979 [doi>10.1145/800090.802893]
• 10: Henry Fuchs, Distributing a visible surface algorithm over multiple processors, Proceedings of the 1977 annual conference, p.449-451, January 1977 [doi>10.1145/800179.810237]
• 11: Thomas A. Funkhouser, Coarse-grained parallelism for hierarchical radiosity using group iterative methods, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.343-352, August 1996 [doi>10.1145/237170.237273]
• 12: Christopher Giersten , Johnny Petersen, Parallel Volume Rendering on a Network of Workstations, IEEE Computer Graphics and Applications, v.13 n.6, p.16-23, November 1993 [doi>10.1109/38.252548]
• 13: Jeremy Hubbell. Network rendering. In Autodesk University Sourcebook, volume 2, pages 443-453. Miller Freeman, 1996.
• 14: Homan Igehy , Gordon Stoll , Pat Hanrahan, The design of a parallel graphics interface, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.141-150, July 1998 [doi>10.1145/280814.280837]
• 15: Kwan-Liu Ma , James S. Painter , Charles D. Hansen , Michael F. Krogh, Parallel Volume Rendering Using Binary-Swap Compositing, IEEE Computer Graphics and Applications, v.14 n.4, p.59-68, July 1994 [doi>10.1109/38.291532]
• 16: Steven Edward Molnar, Image-composition architectures for real-time image generation, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1992
• 17: Steven Molnar , Michael Cox , David Ellsworth , Henry Fuchs, A Sorting Classification of Parallel Rendering, IEEE Computer Graphics and Applications, v.14 n.4, p.23-32, July 1994 [doi>10.1109/38.291528]
• 18: John S. Montrym , Daniel R. Baum , David L. Dignam , Christopher J. Migdal, InfiniteReality: a real-time graphics system, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.293-302, August 1997 [doi>10.1145/258734.258871]
• 19: Carl Mueller, The sort-first rendering architecture for high-performance graphics, Proceedings of the 1995 symposium on Interactive 3D graphics, p.75-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199417]
• 20: Carl Mueller, Hierarchical graphics databases in sort-first, Proceedings of the IEEE symposium on Parallel rendering, p.49-ff., October 20-21, 1997, Phoenix, Arizona, United States [doi>10.1145/266638.266652]
• 21: Ulrich Neumann, Parallel volume-rendering algorithm performance on mesh-connected multicomputers, Proceedings of the 1993 symposium on Parallel rendering, p.97-104, October 25-26, 1993, San Jose, California, United States [doi>10.1145/166181.166196]
• 22: Ulrich Neumann, Communication Costs for Parallel Volume-Rendering Algorithms, IEEE Computer Graphics and Applications, v.14 n.4, p.49-58, July 1994 [doi>10.1109/38.291531]
• 23: F. A. Ortega , C. D. Hansen , J. P. Ahrens, Fast data parallel polygon rendering, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.709-718, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169820]
• 24: Frederic I. Parke, Simulation and expected performance analysis of multiple processor Z-buffer systems, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.48-56, July 14-18, 1980, Seattle, Washington, United States
• 25: Pixar. PhotoRealistic RenderMan Toolkit. 1998.
• 26: Rodney J. Recker , David W. George , Donald P. Greenberg, Acceleration techniques for progressive refinement radiosity, Proceedings of the 1990 symposium on Interactive 3D graphics, p.59-66, February 1990, Snowbird, Utah, United States
• 27: Rudrajit Samanta , Thomas Funkhouser , Kai Li , Jaswinder Pal Singh, Hybrid sort-first and sort-last parallel rendering with a cluster of PCs, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.97-108, August 21-22, 2000, Interlaken, Switzerland [doi>10.1145/346876.348237]
• 28: Rudrajit Samanta , Jiannan Zheng , Thomas Funkhouser , Kai Li , Jaswinder Pal Singh, Load balancing for multi-projector rendering systems, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.107-116, August 08-09, 1999, Los Angeles, California, United States [doi>10.1145/311534.311584]
• 29: Bengt-Olaf Schneider. Parallel rendering on pc workstations. In International Conference on Parallel and Distributed Processing Techniques and Applications (PDTA98), Las Vegas, NV, 1998.
• 30: Jaswinder Pal Singh , Anoop Gupta , Marc Levoy, Parallel Visualization Algorithms: Performance and Architectural Implications, Computer, v.27 n.7, p.45-55, July 1994 [doi>10.1109/2.299410]
• 31: Daniel S. Whelan, Animac: a multiprocessor architecture for real-time computer animation (graphics, shadows, vlsi), 1985
• 32: Scott Whitman, Multiprocessor methods for computer graphics rendering, A. K. Peters, Ltd., Natick, MA, 1992
• 33: Scott Whitman, Dynamic Load Balancing for Parallel Polygon Rendering, IEEE Computer Graphics and Applications, v.14 n.4, p.41-48, July 1994 [doi>10.1109/38.291530]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Parallel processing

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Graphics processors
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
cluster computing, parallel rendering