{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T15:12:44Z","timestamp":1773414764205,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"6-8","license":[{"start":{"date-parts":[[2016,5,7]],"date-time":"2016-05-07T00:00:00Z","timestamp":1462579200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Grantov\u00a0a Agentura Cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["P202\/12\/2413"],"award-info":[{"award-number":["P202\/12\/2413"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Cesk\u00e9 Vysok\u00e9 Ucen\u00ed Technick\u00e9 v Praze (CZ)","award":["SGS16\/237\/OHK3\/3T\/13"],"award-info":[{"award-number":["SGS16\/237\/OHK3\/3T\/13"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Vis Comput"],"published-print":{"date-parts":[[2016,6]]},"DOI":"10.1007\/s00371-016-1241-0","type":"journal-article","created":{"date-parts":[[2016,5,7]],"date-time":"2016-05-07T11:12:15Z","timestamp":1462619535000},"page":"977-987","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Parallel BVH construction using k-means clustering"],"prefix":"10.1007","volume":"32","author":[{"given":"Daniel","family":"Meister","sequence":"first","affiliation":[]},{"given":"Ji\u0159\u00ed","family":"Bittner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,7]]},"reference":[{"key":"1241_CR1","doi-asserted-by":"crossref","unstructured":"Aila, T., Karras, T., Laine, S.: On quality metrics of bounding volume hierarchies. In: Proceedings of High Performance Graphics, pp. 101\u2013108. ACM, New York (2013)","DOI":"10.1145\/2492045.2492056"},{"key":"1241_CR2","doi-asserted-by":"crossref","unstructured":"Aila, T., Laine, S.: Understanding the efficiency of ray traversal on GPUs. In: Proceedings of HPG, pp. 145\u2013149 (2009)","DOI":"10.1145\/1572769.1572792"},{"key":"1241_CR3","doi-asserted-by":"publisher","unstructured":"Apetrei, C.: Fast and simple agglomerative LBVH construction. In: Borgo, R., Tang, W. (eds.) Computer Graphics and Visual Computing (CGVC). The Eurographics Association (2014). doi: 10.2312\/cgvc.20141206","DOI":"10.2312\/cgvc.20141206"},{"key":"1241_CR4","unstructured":"Arthur, D., Vassilvitskii, S.: $$K$$ K -means++: the advantages of careful seeding. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907), pp. 1027\u20131035. Society for Industrial and Applied Mathematics, Philadelphia (2007)"},{"issue":"1","key":"1241_CR5","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1111\/cgf.12000","volume":"32","author":"J Bittner","year":"2013","unstructured":"Bittner, J., Hapala, M., Havran, V.: Fast insertion-based optimization of bounding volume hierarchies. Comput. Graph. Forum 32(1), 85\u2013100 (2013)","journal-title":"Comput. Graph. Forum"},{"key":"1241_CR6","doi-asserted-by":"crossref","unstructured":"Bittner, J., Havran, V.: RDH: ray distribution heuristics for construction of spatial data structures. In: Proceedings of SCCG, pp. 61\u201367. ACM, New York (2009)","DOI":"10.1145\/1980462.1980475"},{"key":"1241_CR7","doi-asserted-by":"crossref","first-page":"1225","DOI":"10.1111\/j.1467-8659.2008.01261.x","volume":"27","author":"H Dammertz","year":"2008","unstructured":"Dammertz, H., Hanika, J., Keller, A.: Shallow bounding volume hierarchies for fast SIMD ray tracing of incoherent rays. Comput. Graph. Forum 27, 1225\u20131233(9) (2008)","journal-title":"Comput. Graph. Forum"},{"key":"1241_CR8","unstructured":"Dasgupta, S.: The hardness of $$k$$ k -means clustering. Department of Computer Science and Engineering, University of California, San Diego (2008)"},{"key":"1241_CR9","doi-asserted-by":"crossref","unstructured":"Domingues, L.R., Pedrini, H.: Bounding volume hierarchy optimization through agglomerative treelet restructuring. In: Proceedings of the 7th Conference on High-Performance Graphics, pp. 13\u201320 (2015)","DOI":"10.1145\/2790060.2790065"},{"key":"1241_CR10","unstructured":"Fabianowski, B., Fowler, C., Dingliana, J.: A cost metric for scene-interior ray origins. In: Eurographics, Short Papers, pp. 49\u201352 (2009)"},{"key":"1241_CR11","unstructured":"Feltman, N., Lee, M., Fatahalian, K.: SRDH: specializing BVH construction and traversal order using representative shadow ray sets. In: Proceedings of HPG, pp. 49\u201355 (2012)"},{"issue":"3","key":"1241_CR12","first-page":"23","volume":"4","author":"P Ganestam","year":"2015","unstructured":"Ganestam, P., Barringer, R., Doggett, M., Akenine-M\u00f6ller, T.: Bonsai: rapid bounding volume hierarchy generation using mini trees. J. Comput. Graph. Tech. (JCGT) 4(3), 23\u201342 (2015)","journal-title":"J. Comput. Graph. Tech. (JCGT)"},{"key":"1241_CR13","doi-asserted-by":"crossref","unstructured":"Garanzha, K., Pantaleoni, J., McAllister, D.: Simpler and faster HLBVH with work queues. In: Proceedings of HPG\u201911, pp. 59\u201364. ACM SIGGRAPH\/Eurographics, Vancouver (2011)","DOI":"10.1145\/2018323.2018333"},{"issue":"5","key":"1241_CR14","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1109\/MCG.1987.276983","volume":"7","author":"J Goldsmith","year":"1987","unstructured":"Goldsmith, J., Salmon, J.: Automatic creation of object hierarchies for ray tracing. IEEE Comput. Graph. Appl. 7(5), 14\u201320 (1987)","journal-title":"IEEE Comput. Graph. Appl."},{"key":"1241_CR15","doi-asserted-by":"crossref","unstructured":"Gu, Y., He, Y., Fatahalian, K., Blelloch, G.E.: Efficient BVH construction via approximate agglomerative clustering. In: Proceedings of high performance graphics, pp. 81\u201388. ACM, New York (2013)","DOI":"10.1145\/2492045.2492054"},{"key":"1241_CR16","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1109\/RT.2006.280217","volume":"2006","author":"V Havran","year":"2006","unstructured":"Havran, V., Herzog, R., Seidel, H.P.: On the fast construction of spatial data structures for ray tracing. Proc. IEEE Symp. Interact. Ray Tracing 2006, 71\u201380 (2006)","journal-title":"Proc. IEEE Symp. Interact. Ray Tracing"},{"key":"1241_CR17","doi-asserted-by":"crossref","unstructured":"Hunt, W.: Corrections to the surface area metric with respect to mail-boxing. In: IEEE Symposium on Interactive Ray Tracing (RT\u201908), pp. 77\u201380 (2008)","DOI":"10.1109\/RT.2008.4634625"},{"key":"1241_CR18","doi-asserted-by":"crossref","unstructured":"Hunt, W., Mark, W.R., Fussell, D.: Fast and lazy build of acceleration structures from scene hierarchies. In: Proceedings of Symposium on Interactive Ray Tracing, pp. 47\u201354 (2007)","DOI":"10.1109\/RT.2007.4342590"},{"key":"1241_CR19","unstructured":"Ize, T., Wald, I., Parker, S.G.: Asynchronous BVH construction for ray tracing dynamic scenes on parallel multi-core architectures. In: Proceedings of Symposium on Parallel Graphics and Visualization\u201907, pp. 101\u2013108 (2007)"},{"key":"1241_CR20","volume-title":"Algorithms for Clustering Data","author":"AK Jain","year":"1988","unstructured":"Jain, A.K., Dubes, R.C.: Algorithms for Clustering Data. Prentice-Hall Inc, Upper Saddle River (1988)"},{"key":"1241_CR21","unstructured":"Karras, T.: Maximizing parallelism in the construction of BVHs, octrees, and k-d trees. In: Proceedings of High Performance Graphics, pp. 33\u201337 (2012)"},{"key":"1241_CR22","doi-asserted-by":"crossref","unstructured":"Karras, T., Aila, T.: Fast Parallel construction of high-quality bounding volume hierarchies. In: Proceedings of High Performance Graphics, pp. 89\u2013100. ACM, New York (2013)","DOI":"10.1145\/2492045.2492055"},{"key":"1241_CR23","doi-asserted-by":"crossref","unstructured":"Kay, T.L., Kajiya, J.T.: Ray tracing complex scenes. In: Evans, D.C., Athay, R.J. (eds.) SIGGRAPH \u201986 Proceedings, vol.\u00a020, pp. 269\u2013278 (1986)","DOI":"10.1145\/15922.15916"},{"key":"1241_CR24","doi-asserted-by":"crossref","unstructured":"Kensler, A.: Tree rotations for improving bounding volume hierarchies. In: Proceedings of the 2008 IEEE Symposium on Interactive Ray Tracing, pp. 73\u201376 (2008)","DOI":"10.1109\/RT.2008.4634624"},{"issue":"3","key":"1241_CR25","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/BF00289116","volume":"23","author":"M Kriv\u00e1nek","year":"1986","unstructured":"Kriv\u00e1nek, M., Mor\u00e1vek, J.: NP-hard problems in hierarchical-tree clustering. Acta Inf. 23(3), 311\u2013323 (1986)","journal-title":"Acta Inf."},{"issue":"2","key":"1241_CR26","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.: Fast BVH construction on GPUs. Comput. Graph. Forum 28(2), 375\u2013384 (2009)","journal-title":"Comput. Graph. Forum"},{"issue":"2","key":"1241_CR27","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"Lloyd, S.: Least squares quantization in PCM. IEEE Trans. Inf. Theor. 28(2), 129\u2013137 (1982)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"1241_CR28","unstructured":"MacQueen, J.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. Volume 1: Statistics, pp. 281\u2013297. University of California Press, Berkeley (1967)"},{"issue":"2","key":"1241_CR29","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1145\/1365490.1365500","volume":"6","author":"J Nickolls","year":"2008","unstructured":"Nickolls, J., Buck, I., Garland, M., Skadron, K.: Scalable parallel programming with CUDA. Queue 6(2), 40\u201353 (2008)","journal-title":"Queue"},{"key":"1241_CR30","unstructured":"Pantaleoni, J., Luebke, D.: HLBVH: hierarchical LBVH construction for real-time ray tracing of dynamic geometry. In: Proceedings of High Performance Graphics\u201910, pp. 87\u201395 (2010)"},{"key":"1241_CR31","doi-asserted-by":"crossref","unstructured":"Rubin, S.M., Whitted, T.: A 3-dimensional representation for fast rendering of complex scenes. In: SIGGRAPH\u201980 Proceedings, vol.\u00a014, pp. 110\u2013116 (1980)","DOI":"10.1145\/965105.807479"},{"issue":"8","key":"1241_CR32","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1111\/cgf.12140","volume":"32","author":"M Vinkler","year":"2013","unstructured":"Vinkler, M., Bittner, J., Havran, V., Hapala, M.: Massively parallel hierarchical scene processing with applications in rendering. Comput. Graph. Forum 32(8), 13\u201325 (2013)","journal-title":"Comput. Graph. Forum"},{"key":"1241_CR33","doi-asserted-by":"crossref","unstructured":"Wald, I.: On fast construction of SAH based bounding volume hierarchies. In: Proceedings of the Symposium on Interactive Ray Tracing, pp. 33\u201340 (2007)","DOI":"10.1109\/RT.2007.4342588"},{"issue":"1","key":"1241_CR34","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1109\/TVCG.2010.251","volume":"18","author":"I Wald","year":"2012","unstructured":"Wald, I.: Fast construction of SAH BVHs on the Intel many integrated core (MIC) architecture. IEEE Trans. Vis. Comput. Graph. 18(1), 47\u201357 (2012)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"1241_CR35","doi-asserted-by":"crossref","unstructured":"Walter, B., Bala, K., Kulkarni, M., Pingali, K.: Fast agglomerative clustering for rendering. In: IEEE Symposium on Interactive Ray Tracing, pp. 81\u201386 (2008)","DOI":"10.1109\/RT.2008.4634626"},{"issue":"1","key":"1241_CR36","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1145\/357332.357335","volume":"3","author":"H Weghorst","year":"1984","unstructured":"Weghorst, H., Hooper, G., Greenberg, D.P.: Improved computational methods for ray tracing. ACM Trans. Graph. 3(1), 52\u201369 (1984)","journal-title":"ACM Trans. Graph."}],"container-title":["The Visual Computer"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-016-1241-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00371-016-1241-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-016-1241-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T07:48:16Z","timestamp":1567842496000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00371-016-1241-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,7]]},"references-count":36,"journal-issue":{"issue":"6-8","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["1241"],"URL":"https:\/\/doi.org\/10.1007\/s00371-016-1241-0","relation":{},"ISSN":["0178-2789","1432-2315"],"issn-type":[{"value":"0178-2789","type":"print"},{"value":"1432-2315","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,7]]}}}