{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T05:25:26Z","timestamp":1777958726745,"version":"3.51.4"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"23","license":[{"start":{"date-parts":[[2015,8,27]],"date-time":"2015-08-27T00:00:00Z","timestamp":1440633600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Multimed Tools Appl"],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1007\/s11042-015-2896-7","type":"journal-article","created":{"date-parts":[[2015,8,26]],"date-time":"2015-08-26T02:32:37Z","timestamp":1440556357000},"page":"15881-15899","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient kd-tree construction for ray tracing using ray distribution sampling"],"prefix":"10.1007","volume":"75","author":[{"given":"Xiao","family":"Liang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongyu","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanci","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Yin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yue","family":"Cao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,27]]},"reference":[{"issue":"9","key":"2896_CR1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"Bentley JL (1975) Multidimensional binary search trees used for associative searching. Commun ACM 18(9):509\u2013517","journal-title":"Commun ACM"},{"key":"2896_CR2","doi-asserted-by":"crossref","unstructured":"Bittner J, Havran V (2009) RDH: ray distribution heuristics for construction of spatial data structures, Proceedings of the 25th Spring Conference on Computer Graphics, pp 51\u201358","DOI":"10.1145\/1980462.1980475"},{"issue":"1","key":"2896_CR3","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.cag.2011.11.007","volume":"36","author":"B Choi","year":"2012","unstructured":"Choi B, Chang B, Ihm I (2012) Construction of efficient kd-trees for static scenes using voxel-visibility heuristic. Comput Graph 36(1):38\u201348","journal-title":"Comput Graph"},{"key":"2896_CR4","unstructured":"Choi B, Komuravelli R, Lu V, Sung H, Bocchino RL, Adve SV, Hart JC (2010) Parallel SAH k-D tree construction for fast dynamic scene ray tracing, high performance graphics, pp 77\u201386"},{"issue":"5","key":"2896_CR5","doi-asserted-by":"crossref","first-page":"115:1","DOI":"10.1145\/2019627.2019634","volume":"30","author":"P Djeu","year":"2011","unstructured":"Djeu P, Hunt W, Wang R, Elhassan I, Stoll G, Mark WR (2011) Razor: an architecture for dynamic multiresolution ray tracing. ACM Trans Graph 30(5):115:1\u2013115:26","journal-title":"ACM Trans Graph"},{"key":"2896_CR6","unstructured":"Fabianowski B, Fowler C, Dingliana J (2009) A cost metric for scene-interior ray origins, Eurographics Short Papers, pp 49\u201352"},{"key":"2896_CR7","unstructured":"Feltman N, Lee M, Fatahalian K (2012) SRDH: specializing BVH construction and traversal order using representative shadow ray sets, Eurographics Conference on High-Performance Graphics, pp 49\u201355"},{"issue":"4","key":"2896_CR8","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1109\/MCG.1986.276715","volume":"6","author":"A Fujimoto","year":"1986","unstructured":"Fujimoto A, Tanaka T, Iwata K (1986) Arts: accelerated ray-tracing system. IEEE Comput Graph Appl 6(4):16\u201326","journal-title":"IEEE Comput Graph Appl"},{"key":"2896_CR9","unstructured":"Havran V (2000) Heuristic ray shooting algorithms, Ph.D. Thesis"},{"key":"2896_CR10","doi-asserted-by":"crossref","unstructured":"Hunt W, Mark WR, Fussel D (2007) Fast and lazy build of acceleration structure from scene hierarchies, IEEE Symposium on Interactive Ray Tracing, pp 47\u201354","DOI":"10.1109\/RT.2007.4342590"},{"key":"2896_CR11","doi-asserted-by":"crossref","unstructured":"Hunt W, Mark WR, Stoll G (2006) Fast kd-tree construction with an adaptive error-bounded heuristic, symposium on interactive ray tracing, Los Alamitos, CA, USA, pp 81\u201388","DOI":"10.1109\/RT.2006.280218"},{"key":"2896_CR12","unstructured":"Hurley J, Kapustin E, Reshetov E, Soupikov A (2002) Fast ray tracing for modern general purpose CPU, In Proceedings of Graphicon, 7(5):2002"},{"key":"2896_CR13","unstructured":"Kang Y-S, Nah J-H, Park W-C, Yang S-B (2013) gkDtree: a group-based parallel update kd-tree for interactive ray tracing. J Sys Archit, pp 166\u2013175"},{"issue":"1","key":"2896_CR14","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1111\/j.1467-8659.2009.01377.x","volume":"28","author":"C Lauterbach","year":"2009","unstructured":"Lauterbach C, Garland M, Sengupta S, Luebke D, Manocha D (2009) Fast BVH construction on GPUs. Comput Graphics Forum 28(1):375\u2013384","journal-title":"Comput Graphics Forum"},{"issue":"3","key":"2896_CR15","first-page":"596","volume":"9","author":"X Liang","year":"2014","unstructured":"Liang X, Yang H, Qian Y, Zhang Y (2014) A fast Kd-tree construction for ray tracing based on efficient ray distribution. J Softw 9(3):596\u2013604","journal-title":"J Softw"},{"issue":"3","key":"2896_CR16","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01911006","volume":"6","author":"J MacDonald","year":"1990","unstructured":"MacDonald J, Booth K (1990) Heuristics for ray tracing using space subdivision. Vis Comput 6(3):153\u2013166","journal-title":"Vis Comput"},{"key":"2896_CR17","series-title":"From theory to implementation","volume-title":"Physically based rendering","author":"M Pharr","year":"2010","unstructured":"Pharr M, Humphreys G (2010) Physically based rendering, 2nd edn, From theory to implementation. Morgan Kaufmann Publishers Inc, San Francisco","edition":"2"},{"key":"2896_CR18","doi-asserted-by":"crossref","unstructured":"Popov S, G\u00fcnther J, Seidel H-P, Slusallek P (2006) Experiences with streaming construction of SAH KD-trees, Proceedin of the 17th Eurographics Ysmposium on Rendering, pp 139\u2013149","DOI":"10.1109\/RT.2006.280219"},{"issue":"3","key":"2896_CR19","doi-asserted-by":"crossref","first-page":"1176","DOI":"10.1145\/1073204.1073329","volume":"24","author":"A Reshetov","year":"2005","unstructured":"Reshetov A, Soupikov A, Hurley J (2005) Multi-level ray tracing algorithm. ACM Trans Graph 24(3):1176\u20131185","journal-title":"ACM Trans Graph"},{"key":"2896_CR20","doi-asserted-by":"crossref","unstructured":"Rubin S, Whitted T (1980) A 3-dimensional representation for fast rendering of complex scenes, In Proceedings of SIGGRAPH, pp 110\u2013116","DOI":"10.1145\/800250.807479"},{"issue":"3","key":"2896_CR21","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1111\/j.1467-8659.2007.01062.x","volume":"26","author":"M Shevtsov","year":"2007","unstructured":"Shevtsov M, Soupikov A, Kapustin A (2007) Highly parallel fast KD-tree construction for interactive ray tracing of dynamic scenes. Comput Graphics Forum 26(3):395\u2013404","journal-title":"Comput Graphics Forum"},{"key":"2896_CR22","doi-asserted-by":"crossref","unstructured":"Solomon H (1978) Geometric probability, J.W. Arrowsmith Ltd","DOI":"10.1137\/1.9781611970418"},{"issue":"4","key":"2896_CR23","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/j.cag.2012.02.013","volume":"36","author":"M Vinkler","year":"2012","unstructured":"Vinkler M, Havran V, Sochor J (2012) Visibility driven BVH build up algorithm for ray tracing. Comput Graph 36(4):283\u2013296","journal-title":"Comput Graph"},{"key":"2896_CR24","unstructured":"W\u00e4chter C, Keller A (2006) Instant ray tracing: the bounding interval hierarchy, Proceedings of the 17th Eurographics Symposium on Rendering, pp 139\u2013149"},{"issue":"3","key":"2896_CR25","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1145\/1141911.1141913","volume":"25","author":"I Wald","year":"2006","unstructured":"Wald I, Ize T, Kensler A, Knoll A, Parker SG (2006) Ray Tracing Animated Scenes using Coherent Grid Traversal. ACM Trans Graph (Proc ACM SIGGRAPH) 25(3):485\u2013493","journal-title":"ACM Trans Graph (Proc ACM SIGGRAPH)"},{"key":"2896_CR26","doi-asserted-by":"crossref","unstructured":"Wald I, Slusallek P, Benthin C, Wagner M (2006) On building fast kd-trees for ray tracing, and on doing that in O(N log(N), Proceedings of the 2006 I.E. Symposium on Interactive Ray Tracing, pp 61\u201369","DOI":"10.1109\/RT.2006.280216"},{"key":"2896_CR27","doi-asserted-by":"crossref","unstructured":"Wu Z, Zhao F, Liu X (2011) SAH KD-tree construction on GPU. high performance graphics, pp 71\u201378","DOI":"10.1145\/2018323.2018335"},{"key":"2896_CR28","doi-asserted-by":"crossref","unstructured":"Zhou K, Hou Q, Wang R, Guo B (2008) Real-time KD-tree construction on graphics hardware, ACM SIGGRAPH Asia, pp 126:1\u2013126:11","DOI":"10.1145\/1409060.1409079"}],"container-title":["Multimedia Tools and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11042-015-2896-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11042-015-2896-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11042-015-2896-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11042-015-2896-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,29]],"date-time":"2019-08-29T16:57:29Z","timestamp":1567097849000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11042-015-2896-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,27]]},"references-count":28,"journal-issue":{"issue":"23","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["2896"],"URL":"https:\/\/doi.org\/10.1007\/s11042-015-2896-7","relation":{},"ISSN":["1380-7501","1573-7721"],"issn-type":[{"value":"1380-7501","type":"print"},{"value":"1573-7721","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,27]]}}}