{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T06:07:30Z","timestamp":1784268450622,"version":"3.55.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,7,29]],"date-time":"2007-07-29T00:00:00Z","timestamp":1185667200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2007,7,29]]},"abstract":"<jats:p>Rendering complex scenes with indirect illumination, high dynamic range environment lighting, and many direct light sources remains a challenging problem. Prior work has shown that all these effects can be approximated by many point lights. This paper presents a scalable solution to the many-light problem suitable for a GPU implementation. We view the problem as a large matrix of sample-light interactions; the ideal final image is the sum of the matrix columns. We propose an algorithm for approximating this sum by sampling entire rows and columns of the matrix on the GPU using shadow mapping. The key observation is that the inherent structure of the transfer matrix can be revealed by sampling just a small number of rows and columns. Our prototype implementation can compute the light transfer within a few seconds for scenes with indirect and environment illumination, area lights, complex geometry and arbitrary shaders. We believe this approach can be very useful for rapid previewing in applications like cinematic and architectural lighting design.<\/jats:p>","DOI":"10.1145\/1276377.1276410","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":88,"title":["Matrix row-column sampling for the many-light problem"],"prefix":"10.1145","volume":"26","author":[{"given":"Milo\u0161","family":"Ha\u0161an","sequence":"first","affiliation":[{"name":"Cornell University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabio","family":"Pellacini","sequence":"additional","affiliation":[{"name":"Dartmouth College"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kavita","family":"Bala","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,7,29]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882314"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882318"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141979"},{"key":"e_1_2_2_4_1","first-page":"51","article-title":"Gpu algorithms for radiosity and subsurface scattering","volume":"2003","author":"Carr N. A.","year":"2003","unstructured":"Carr , N. A. , Hall , J. D. , and Hart , J. C. 2003 . Gpu algorithms for radiosity and subsurface scattering . In Graphics Hardware 2003 , 51 -- 59 . Carr, N. A., Hall, J. D., and Hart, J. C. 2003. Gpu algorithms for radiosity and subsurface scattering. In Graphics Hardware 2003, 51--59.","journal-title":"Graphics Hardware"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/237748.237749"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1053427.1053460"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111411.1111428"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_29"},{"key":"e_1_2_2_9_1","unstructured":"Fernandez S. Bala K. and Greenberg D. P. 2002. Local illumination environments for direct lighting acceleration. In Rendering Techniques 2002: 13th Eurographics Workshop on Rendering 7--14.   Fernandez S. Bala K. and Greenberg D. P. 2002. Local illumination environments for direct lighting acceleration. In Rendering Techniques 2002: 13th Eurographics Workshop on Rendering 7--14."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.2312\/EGWR\/EGSR05\/055-064"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179849.1180063"},{"key":"e_1_2_2_12_1","doi-asserted-by":"crossref","unstructured":"Goreinov S. A. Tyrtyshnikov E. E. and Zamarashkin N. 1997. A theory of pseudoskeleton approximations. Linear Algebra and its Applications 261.  Goreinov S. A. Tyrtyshnikov E. E. and Zamarashkin N. 1997. A theory of pseudoskeleton approximations. Linear Algebra and its Applications 261 .","DOI":"10.1016\/S0024-3795(96)00301-1"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/122718.122740"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141998"},{"key":"e_1_2_2_15_1","volume-title":"Realistic image synthesis using photon mapping","author":"Jensen H. W.","unstructured":"Jensen , H. W. 2001. Realistic image synthesis using photon mapping . A. K. Peters, Ltd. , Natick, MA, USA. Jensen, H. W. 2001. Realistic image synthesis using photon mapping. A. K. Peters, Ltd., Natick, MA, USA."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258769"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.2312\/EGWR\/EGSR06\/127-138"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015749"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015750"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00254"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Purcell T. J. Donner C. Cammarano M. Jensen H. W. and Hanrahan P. 2003. Photon mapping on programmable graphics hardware. In Sypmosium on Graphics Hardware 2003.   Purcell T. J. Donner C. Cammarano M. Jensen H. W. and Hanrahan P. 2003. Photon mapping on programmable graphics hardware. In Sypmosium on Graphics Hardware 2003 .","DOI":"10.1145\/566570.566640"},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the 12th Eurographics Workshop on Rendering.","author":"Scheel A.","unstructured":"Scheel , A. , Stamminger , M. , and Seidel , H . -P. 2001. Thrifty final gather radiosity . Proceedings of the 12th Eurographics Workshop on Rendering. Scheel, A., Stamminger, M., and Seidel, H.-P. 2001. Thrifty final gather radiosity. Proceedings of the 12th Eurographics Workshop on Rendering."},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Scheel A. Stamminger M. and Seidel H. 2002. Grid based final gather for radiosity on complex clustered scenes. Computer Graphics Forum 21(3).  Scheel A. Stamminger M. and Seidel H. 2002. Grid based final gather for radiosity on complex clustered scenes. Computer Graphics Forum 21(3) .","DOI":"10.1111\/1467-8659.00705"},{"key":"e_1_2_2_24_1","first-page":"035","article-title":"Clustering for edge-cost minimization","volume":"6","author":"Schulman L. J.","year":"1999","unstructured":"Schulman , L. J. 1999 . Clustering for edge-cost minimization . Electronic Colloquium on Computational Complexity (ECCC) 6 , 035 . Schulman, L. J. 1999. Clustering for edge-cost minimization. Electronic Colloquium on Computational Complexity (ECCC) 6, 035.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/226150.226151"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566612"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/133994.134080"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566613"},{"key":"e_1_2_2_29_1","doi-asserted-by":"crossref","unstructured":"Vempala S. 2004. The Random Projection Method. DIMACS Series in Discrete Mathematics and Theoretical Computer Science.  Vempala S. 2004. The Random Projection Method . DIMACS Series in Discrete Mathematics and Theoretical Computer Science.","DOI":"10.1090\/dimacs\/065"},{"key":"e_1_2_2_30_1","volume-title":"14th Eurographics Workshop on Rendering, 74--81","author":"Wald I.","unstructured":"Wald , I. , Benthin , C. , and Slusallek , P . 2003. Interactive global illumination in complex and highly occluded environments . In 14th Eurographics Workshop on Rendering, 74--81 . Wald, I., Benthin, C., and Slusallek, P. 2003. Interactive global illumination in complex and highly occluded environments. In 14th Eurographics Workshop on Rendering, 74--81."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.2312\/EGWR\/EGWR99\/019-030"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073318"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141997"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/337680.337722"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/54852.378490"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-57963-9_2"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1276377.1276410","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1276377.1276410","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:17Z","timestamp":1750258337000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1276377.1276410"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,29]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,7,29]]}},"alternative-id":["10.1145\/1276377.1276410"],"URL":"https:\/\/doi.org\/10.1145\/1276377.1276410","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7,29]]},"assertion":[{"value":"2007-07-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}