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

Article

Free access

On the partitionability of hierarchical radiosity

Author:

Robert GarmannAuthors Info & Claims

PVGS '99: Proceedings of the 1999 IEEE symposium on Parallel visualization and graphics

Pages 69 - 78

https://doi.org/10.1145/328712.319339

Published: 25 October 1999 Publication History

Abstract

The Hierarchical Radiosity Algorithm (HRA) is one of the most efficient sequential algorithms for physically based rendering. Unfortunately, it is hard to implement in parallel. There exist fairly efficient shared-memory implementations but things get worst in a distributed memory (DM) environment. In this paper we examine the structure of the IIRA in a graph partitioning setting. Various measurements performed on the task access graph of the HRA indicate the existance of several bottlenecks in a potential DM implementation. We compare “optimal” partitioning results obtained by the partitioning software Metis with a trivial and a spatial partitioning algorithm, and show that the spatial partitioning copes with most of the bottlenecks well.

References

[1]

C.-A. Bohn and R. Garmann. A Parallel Approach To Hierarchical Radiosity. In V. Skala, editor, Proc. Winter School of Computer Graphics '95, pages 26-35, Plzen, Czech Republic, February 1995. University of West Bohemia.

[2]

M.B. Carter. ParallelHierarchicalRadiosity Rendering. PhD thesis, Iowa State University, Department of Electrical Engineering and Computer Engineering, Ames, Iowa, November 1993.

Digital Library

[3]

E. Caspary and I. D. Scherson. A Self-Balanced Parallel Ray- Tracing Algorithm. In Dew, Earnshaw, Heywood, eds.,Parallel processing for computer vision and display, Addison Wesley, 1989.

[4]

M.F. Cohen and J. R. Wallace. Radiosity And Realistic Image Aynthesis. Academic Press Professional, Cambridge, 1993.

Digital Library

[5]

D. Culler, R. Karp, D. Patterson, A. Sahay, K. Schauser, E. Santos, and T. van Eicken. LogP: Towards A Realistic Model Of Parallel Computation. In Proc. of the ACM SIG- PLAN Symposium on Principles and Practice of Parallel Programming, pages 1-12, 1993.

Digital Library

[6]

I. S. Duff, R. G. Grimes, and J. G. Lewis. User's Guide For The Harwell-Boeing Sparse Matrix Collection (Release I). Technical report, CERFACS, Toulouse Cedex, France, October 1992.

[7]

D. Fellner, S. Sch~ifer, and M. Zens. Photorealistic Rendering In Heterogeneous Networks. In Proc. ParCo97, Advances in Parallel Computing, North-Holland, Amsterdam, 1997.

[8]

T. A. Funkhouser. Coarse-Grained Parallelism For Hierarchical Radiosity Using Group Iterative Methods. In SIGGRAPH '96, New Orleans, LA, August 1996.

Digital Library

[9]

M. R. Garey and D. S. Johnson. Computers And Intractability: A Guide To The Theo17 Of NP-Completeness. Freeman, San Francisco CA, 1979.

Digital Library

[10]

R. Garmann. Maintaining Dynamic Geometric Objects On Parallel Processors. In Symposium on Parallel Rendering, Phoenix, AZ, October 1997.

Digital Library

[11]

R. Garmann. Locality Preserving Load Balancing With Provably Small Overhead. In A. Ferreira et al., editors, IRREG- ULAR'98, Berkeley, California, August 9-11, LNCS 1457. Springer, 1998.

Digital Library

[12]

R. Garmann. On The Partitionability Of Hierarchical Radiosity. Technical report 702, FB Informatik, Universit~it Dortmund, January 1999.

[13]

S. W. Hammond. Mapping Unstructured Grid Computations To Massively Parallel Computers. Technical Report 92.14, RIACS, NASA Ames, 1992.

[14]

E Hanrahan, D. Salzman, and L. Aupperle. A Rapid Hierarchical Radiosity Algorithm. Computer Graphics, 25(4):197- 206, July 1991.

Digital Library

[15]

B. Hendrickson and R. Leland. Chaco. http://www.cs.sandia. gov/CRF/chac.html.

[16]

G. Karypis and V. Kumar. Metis. http://www.cs.umn.edu/ karypis/metis.

[17]

F. T. Leighton. Innvduction To Parallel Algorithms And Architectures: Arrays, Trees, Hypercobes. Morgan Kaufman Publishers, 1992.

Digital Library

[18]

D. Paddon and A. Chalmers. Parallel Processing Of The Radiosity Method. Computer-Aided Design, 26(12):917-927, December 1994.

[19]

R. Preis and R. Diekmann. Party Partitioning Library. http://www.uni-paderbom.de/cs/robsy/party.html.

[20]

E Schr6der. Wavelet Algorithms For Illumination Computations. PhD thesis, Princeton University, November 1994.

[21]

F.X. Sillion and C. Puech. Radiosity & Global Illumination. Morgan Kaufman, San Francisco, 1994.

Digital Library

[22]

J. E Singh. Parallel HierarchicalN-Body Methods And Their Implications For Multiprocessors. PhD thesis, Stanford University, February 1993.

Digital Library

[23]

J.P. Singh, A. Gupta, and M. Levoy. Parallel Visualization Algorithms: Performance And Architectural Implications. IEEE Computer Graphics & Applications, pages 45-55, July 1994.

Digital Library

[24]

M. Stamminger, H. Schirmacher, and Ph. Slusallek. Getting Rid Of Links In Hierarchical Radiosity. In Computer Graphics Forum (Proceedings EUROGRAPHICS '98), 1998.

[25]

C. Walshaw. Jostle-Mesh Partitioning Software. http://www. gre.ac.uk/jostle.

[26]

D. M. Zareski. Parallel Decomposition Of View-Independent Global Illumination Algorithms. Master's thesis, Comell University, January 1996.

Cited By

Sinop AAbaci TAkkuş ÜGürsoy AGüdükbay U(2018)PHRThe Journal of Supercomputing10.1007/s11227-005-0107-431:3(249-263)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s11227-005-0107-4
(2011)BibliographyPractical Parallel Rendering10.1201/b10622-13(337-362)Online publication date: 19-Apr-2011
https://doi.org/10.1201/b10622-13
Garmann R(2001)Spatial Partitioning for Parallel Hierarchical Radiosity on Distributed Memory ArchitecturesHigh Performance Computing in Science and Engineering 200010.1007/978-3-642-56548-9_39(478-493)Online publication date: 2001
https://doi.org/10.1007/978-3-642-56548-9_39

Index Terms

On the partitionability of hierarchical radiosity
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision representations
        Hierarchical representations
  2. Computer graphics
    1. Rendering
      1. Ray tracing
    2. Shape modeling
2. Software and its engineering
  1. Software notations and tools
    1. Development frameworks and environments
      1. Object oriented frameworks

Recommendations

GI-cube: an architecture for volumetric global illumination and rendering
HWWS '00: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware

The power and utility of volume rendering is increased by global illumination. We present a hardware architecture, GI-Cube, designed to accelerate volume rendering, empower volumetric global illumination, and enable a host of ray-based volumetric ...
Interactive volume segmentation with the PAVLOV architecture
PVGS '99: Proceedings of the 1999 IEEE symposium on Parallel visualization and graphics

We propose a new paradigm for interactive volume visualization which allows enhanced exploration of datasets through the use of real-time volume processing (e.g., segmentation) tightly coupled with rendering. We show examples of how this paradigm ...
Hierarchical image-space radiosity for interactive global illumination
EGSR'09: Proceedings of the Twentieth Eurographics conference on Rendering

We introduce image-space radiosity and a hierarchical variant as a method for interactively approximating diffuse indirect illumination in fully dynamic scenes. As oft observed, diffuse indirect illumination contains mainly low-frequency details that do ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PVGS '99: Proceedings of the 1999 IEEE symposium on Parallel visualization and graphics

October 1999

122 pages

ISBN:1581132379

Sponsors

IEEE-CS\TCCG: TC on Computer Graphics
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

IEEE Computer Society

United States

Publication History

Published: 25 October 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PVG99

Sponsor:

IEEE-CS\TCCG
SIGGRAPH

PVG99: IEEE Symposium on Parallel Visualization and Graphics

October 25 - 26, 1999

California, San Francisco, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
245
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)13

Reflects downloads up to 24 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sinop AAbaci TAkkuş ÜGürsoy AGüdükbay U(2018)PHRThe Journal of Supercomputing10.1007/s11227-005-0107-431:3(249-263)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s11227-005-0107-4
(2011)BibliographyPractical Parallel Rendering10.1201/b10622-13(337-362)Online publication date: 19-Apr-2011
https://doi.org/10.1201/b10622-13
Garmann R(2001)Spatial Partitioning for Parallel Hierarchical Radiosity on Distributed Memory ArchitecturesHigh Performance Computing in Science and Engineering 200010.1007/978-3-642-56548-9_39(478-493)Online publication date: 2001
https://doi.org/10.1007/978-3-642-56548-9_39

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

Figures

Tables

Media

View Table of Conten