{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T11:48:15Z","timestamp":1763466495623,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,6,1]],"date-time":"2010-06-01T00:00:00Z","timestamp":1275350400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003626","name":"Defense Acquisition Program Administration","doi-asserted-by":"publisher","award":["UD080042AD"],"award-info":[{"award-number":["UD080042AD"]}],"id":[{"id":"10.13039\/501100003626","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005073","name":"Agency for Defense Development","doi-asserted-by":"publisher","award":["UD080042AD"],"award-info":[{"award-number":["UD080042AD"]}],"id":[{"id":"10.13039\/501100005073","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002994","name":"Ministry of Knowledge Economy","doi-asserted-by":"publisher","award":["KRF-2008-313-D00922MKE\/MCST\/IITA[2008-F-033-02]"],"award-info":[{"award-number":["KRF-2008-313-D00922MKE\/MCST\/IITA[2008-F-033-02]"]}],"id":[{"id":"10.13039\/501100002994","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003561","name":"Ministry of Culture, Sports and Tourism","doi-asserted-by":"publisher","award":["KRF-2008-313-D00922MKE\/MCST\/IITA[2008-F-033-02]"],"award-info":[{"award-number":["KRF-2008-313-D00922MKE\/MCST\/IITA[2008-F-033-02]"]}],"id":[{"id":"10.13039\/501100003561","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2010,6]]},"abstract":"<jats:p>We present a cache-oblivious ray reordering method for ray tracing. Many global illumination methods such as path tracing and photon mapping use ray tracing and generate lots of rays to simulate various realistic visual effects. However, these rays tend to be very incoherent and show lower cache utilizations during ray tracing of models. In order to address this problem and improve the ray coherence, we propose a novel<jats:italic>Hit Point Heuristic<\/jats:italic>(HPH) to compute a coherent ordering of rays. The HPH uses the hit points between rays and the scene as a ray reordering measure. We reorder rays by using a space-filling curve based on their hit points. Since a hit point of a ray is available only after performing the ray intersection test with the scene, we compute an approximate hit point for the ray by performing an intersection test between the ray and simplified representations of the original models. Our method is a highly modular approach, since our reordering method is decoupled from other components of common ray tracing systems. We apply our method to photon mapping and path tracing and achieve more than an order of magnitude performance improvement for massive models that cannot fit into main memory, compared to rendering without reordering rays. Also, our method shows a performance improvement even for ray tracing small models that can fit into main memory. This performance improvement for small and massive models is caused by reducing cache misses occurring between different memory levels including the L1\/L2 caches, main memory, and disk. This result demonstrates the cache-oblivious nature of our method, which works for various kinds of cache parameters. Because of the cache-obliviousness and the high modularity, our method can be widely applied to many existing ray tracing systems and show performance improvements with various models and machines that have different cache parameters.<\/jats:p>","DOI":"10.1145\/1805964.1805972","type":"journal-article","created":{"date-parts":[[2010,6,30]],"date-time":"2010-06-30T20:27:11Z","timestamp":1277929631000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["Cache-oblivious ray reordering"],"prefix":"10.1145","volume":"29","author":[{"given":"Bochang","family":"Moon","sequence":"first","affiliation":[{"name":"KAIST, Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongyoung","family":"Byun","sequence":"additional","affiliation":[{"name":"KAIST, Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tae-Joon","family":"Kim","sequence":"additional","affiliation":[{"name":"KAIST, Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pio","family":"Claudio","sequence":"additional","affiliation":[{"name":"KAIST, Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hye-Sun","family":"Kim","sequence":"additional","affiliation":[{"name":"Electronics and Telecommunications Research Institute (ETRI), Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yun-Ji","family":"Ban","sequence":"additional","affiliation":[{"name":"Electronics and Telecommunications Research Institute (ETRI), Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seung Woo","family":"Nam","sequence":"additional","affiliation":[{"name":"Electronics and Telecommunications Research Institute (ETRI), Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sung-Eui","family":"Yoon","sequence":"additional","affiliation":[{"name":"KAIST, Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,7,2]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Arge L. Brodal G. S. and Fagerberg R. 2005. Cache-Oblivious Data Structures in Handbook of Data Structures. CRC Press. Arge L. Brodal G. S. and Fagerberg R. 2005. Cache-Oblivious Data Structures in Handbook of Data Structures. CRC Press.","DOI":"10.1201\/9781420035179.ch34"},{"volume-title":"Proceedings of the IEEE Symposium on Interactive Ray Tracing. 131--138","author":"Boulos S.","key":"e_1_2_2_2_1","unstructured":"Boulos , S. , Wald , I. , and Benthin , C . 2008. Adaptive ray packet reordering . In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 131--138 . Boulos, S., Wald, I., and Benthin, C. 2008. Adaptive ray packet reordering. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 131--138."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01378.x"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.t01-1-00702"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/2151237X.2006.10129226"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276476"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2386103.2386119"},{"volume-title":"Proceedings of the Computer Graphics International Conference. 115--121","author":"Diaz-Gutierrez P.","key":"e_1_2_2_8_1","unstructured":"Diaz-Gutierrez , P. , Bhushan , A. , Gopi , M. , and Pajarola , R . 2005. Constrained strip generation and management for efficient interactive 3D rendering . In Proceedings of the Computer Graphics International Conference. 115--121 . Diaz-Gutierrez, P., Bhushan, A., Gopi, M., and Pajarola, R. 2005. Constrained strip generation and management for efficient interactive 3D rendering. In Proceedings of the Computer Graphics International Conference. 115--121."},{"key":"e_1_2_2_9_1","volume-title":"Razor: An architecture for dynamic multiresolution ray tracing. Tech. rep. TR-07-52","author":"Djeu P.","year":"2007","unstructured":"Djeu , P. , Hunt , W. , Wang , R. , Elhassan , I. , Stoll , G. , and Mark , W. R . 2007 . Razor: An architecture for dynamic multiresolution ray tracing. Tech. rep. TR-07-52 , The University of Texas at Austin, Department of Computer Sciences . January 24. Djeu, P., Hunt, W., Wang, R., Elhassan, I., Stoll, G., and Mark, W. R. 2007. Razor: An architecture for dynamic multiresolution ray tracing. Tech. rep. TR-07-52, The University of Texas at Austin, Department of Computer Sciences. January 24."},{"volume-title":"Proceedings of the IEEE Symposium on Interactive Ray Tracing. 35--40","author":"Ernst M.","key":"e_1_2_2_10_1","unstructured":"Ernst , M. and Greiner , G . 2008. Multi bounding volume hierarchies . In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 35--40 . Ernst, M. and Greiner, G. 2008. Multi bounding volume hierarchies. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 35--40."},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Frigo M. Leiserson C. Prokop H. and Ramachandran S. 1999. Cache-Oblivious algorithms. In Foundations of Computer Science. 285--297. Frigo M. Leiserson C. Prokop H. and Ramachandran S. 1999. Cache-Oblivious algorithms. In Foundations of Computer Science. 285--297.","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258849"},{"volume-title":"Proceedings of the IEEE Symposium on Interactive Ray Tracing. 59--66","author":"Gribble C. P.","key":"e_1_2_2_13_1","unstructured":"Gribble , C. P. and Ramani , K . 2008. Coherent ray tracing via stream filtering . In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 59--66 . Gribble, C. P. and Ramani, K. 2008. Coherent ray tracing via stream filtering. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 59--66."},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of Compugraphics Conference.","author":"Havran V.","year":"1997","unstructured":"Havran , V. 1997 . Cache sensitive representation for the bsp tree . In Proceedings of Compugraphics Conference. Havran, V. 1997. Cache sensitive representation for the bsp tree. In Proceedings of Compugraphics Conference."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800031.808588"},{"key":"e_1_2_2_16_1","unstructured":"Hennessy J. L. Patterson D. A. and Goldberg D. 2007. Computer Architecture A Quantitative Approach. Morgan Kaufmann. Hennessy J. L. Patterson D. A. and Goldberg D. 2007. Computer Architecture A Quantitative Approach. Morgan Kaufmann."},{"key":"e_1_2_2_17_1","unstructured":"Jensen H. W. 2005. Realistic Image Synthesis Using Photon Mapping. AK Peters. Jensen H. W. 2005. Realistic Image Synthesis Using Photon Mapping. AK Peters."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01599.x"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2009.71"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01377.x"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2008.01270.x"},{"volume-title":"Proceedings of the IEEE Symposium on Interactive Ray Tracing. 39--46","author":"Lauterbach C.","key":"e_1_2_2_22_1","unstructured":"Lauterbach , C. , Yoon , S.-E. , Tuft , D. , and Manocha , D . 2006. RT-DEFORM: Interactive ray tracing of dynamic scenes using bvhs . In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 39--46 . Lauterbach, C., Yoon, S.-E., Tuft, D., and Manocha, D. 2006. RT-DEFORM: Interactive ray tracing of dynamic scenes using bvhs. In Proceedings of the IEEE Symposium on Interactive Ray Tracing. 39--46."},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Luebke D. Reddy M. Cohen J. Varshney A. Watson B. and Huebner R. 2002. Level of Detail for 3D Graphics. Morgan-Kaufmann. Luebke D. Reddy M. Cohen J. Varshney A. Watson B. and Huebner R. 2002. Level of Detail for 3D Graphics. Morgan-Kaufmann.","DOI":"10.1016\/B978-155860838-2\/50003-0"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/RT.2007.4342594"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/RT.2007.4342596"},{"key":"e_1_2_2_26_1","unstructured":"Pharr M. and Humphreys G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann Publishers San Francisco CA. Pharr M. and Humphreys G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann Publishers San Francisco CA."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258791"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/RT.2007.4342597"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073329"},{"key":"e_1_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Sagan H. 1994. Space-Filling Curves. Springer-Verlag. Sagan H. 1994. Space-Filling Curves. Springer-Verlag.","DOI":"10.1007\/978-1-4612-0871-6"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Shirley P. and Morley R. K. 2003. Realistic Ray Tracing 2nd Ed. AK Peters. Shirley P. and Morley R. K. 2003. Realistic Ray Tracing 2nd Ed. AK Peters.","DOI":"10.1201\/9781439864449"},{"key":"e_1_2_2_32_1","unstructured":"Silva C. Chiang Y.-J. Correa W. El-Sana J. and Lindstrom P. 2002. Out-of-Core algorithms for scientific visualization and computer graphics. In IEEE Visualization Course Notes. Silva C. Chiang Y.-J. Correa W. El-Sana J. and Lindstrom P. 2002. Out-of-Core algorithms for scientific visualization and computer graphics. In IEEE Visualization Course Notes."},{"volume-title":"Proceedings of the Graphics Interface Conference. 97--104","author":"Steinhurst J.","key":"e_1_2_2_33_1","unstructured":"Steinhurst , J. , Coombe , G. , and Lastra , A . 2005. Reordering for cache conscious photon mapping . In Proceedings of the Graphics Interface Conference. 97--104 . Steinhurst, J., Coombe, G., and Lastra, A. 2005. Reordering for cache conscious photon mapping. In Proceedings of the Graphics Interface Conference. 97--104."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2386124.2386128"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015748"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189762.1206075"},{"volume-title":"Proceedings of the EG Symposium on Rendering. 82--91","author":"Wald I.","key":"e_1_2_2_39_1","unstructured":"Wald , I. , Dietrich , A. , and Slusallek , P . 2004. An interactive out-of-core rendering framework for visualizing massively complex models . In Proceedings of the EG Symposium on Rendering. 82--91 . Wald, I., Dietrich, A., and Slusallek, P. 2004. An interactive out-of-core rendering framework for visualizing massively complex models. In Proceedings of the EG Symposium on Rendering. 82--91."},{"key":"e_1_2_2_40_1","unstructured":"Wald I. Mark W. R. G\u00fcnther J. Boulos S. Ize T. Hunt W. Parker S. G. and Shirley P. 2007b. State of the art in ray tracing animated scenes. In Eurographics State of the Art Reports. Wald I. Mark W. R. G\u00fcnther J. Boulos S. Ize T. Hunt W. Parker S. G. and Shirley P. 2007b. State of the art in ray tracing animated scenes. In Eurographics State of the Art Reports."},{"volume-title":"Proceedings of the EG Workshop on Rendering. 277--288","author":"Wald I.","key":"e_1_2_2_41_1","unstructured":"Wald , I. , Slusallek , P. , and Benthin , C . 2001. Interactive distributed ray tracing of highly complex models . In Proceedings of the EG Workshop on Rendering. 277--288 . Wald, I., Slusallek, P., and Benthin, C. 2001. Interactive distributed ray tracing of highly complex models. In Proceedings of the EG Workshop on Rendering. 277--288."},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Yoon S.-E. Gobbetti E. Kasik D. and Manocha D. 2008. Real-Time Massive Model Rendering. Morgan &amp; Claypool. Yoon S.-E. Gobbetti E. Kasik D. and Manocha D. 2008. Real-Time Massive Model Rendering. Morgan &amp; Claypool.","DOI":"10.1007\/978-3-031-79531-2"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.162"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073278"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2006.00970.x"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1805964.1805972","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1805964.1805972","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:42Z","timestamp":1750245762000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1805964.1805972"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1145\/1805964.1805972"],"URL":"https:\/\/doi.org\/10.1145\/1805964.1805972","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2010,6]]},"assertion":[{"value":"2010-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}