{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:04:48Z","timestamp":1740107088160,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T00:00:00Z","timestamp":1690156800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T00:00:00Z","timestamp":1690156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Athens University of Economics & Business"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Vis Comput"],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Spatial data structures, such as <jats:italic>k<\/jats:italic>-d trees and bounding volume hierarchies, are extensively used in computer graphics for the acceleration of spatial queries in ray tracing, nearest neighbour searches and other tasks. Typically, the splitting strategy employed during the construction of such structures is based on the greedy evaluation of a predefined objective function, resulting in a less than optimal subdivision scheme. In this work, for the first time, we propose the use of unsupervised deep learning to infer the structure of a fixed-depth <jats:italic>k<\/jats:italic>-d tree from a constant, subsampled set of the input primitives, based on the recursive evaluation of the cost function at hand. This results in high-quality upper spatial hierarchy, inferred in constant time and without paying the intractable price of a fully recursive tree optimisation. The resulting fixed-depth tree can then be further expanded, in parallel, into either a full <jats:italic>k<\/jats:italic>-d tree or transformed into a bounding volume hierarchy, with any known conventional tree builder. The approach is generic enough to accommodate different cost functions, such as the popular surface area and volume heuristics. We experimentally validate that the resulting hierarchies have competitive traversal performance with respect to established tree builders, while maintaining minimal overhead in construction times.\n<\/jats:p>","DOI":"10.1007\/s00371-023-02975-y","type":"journal-article","created":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T22:02:49Z","timestamp":1690236169000},"page":"3797-3809","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A neural builder for spatial subdivision hierarchies"],"prefix":"10.1007","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4556-390X","authenticated-orcid":false,"given":"Iordanis","family":"Evangelou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4774-0746","authenticated-orcid":false,"given":"Georgios","family":"Papaioannou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2282-4644","authenticated-orcid":false,"given":"Konstantinos","family":"Vardis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9673-2462","authenticated-orcid":false,"given":"Anastasios","family":"Gkaravelis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,24]]},"reference":[{"issue":"9","key":"2975_CR1","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509\u2013517 (1975)","journal-title":"Commun. ACM"},{"issue":"2","key":"2975_CR2","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1109\/34.121791","volume":"14","author":"PJ Besl","year":"1992","unstructured":"Besl, P.J., McKay, N.D.: A method for registration of 3-D shapes. IEEE Trans. Pattern Anal. Mach. Intell. 14(2), 239\u2013256 (1992)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"2975_CR3","unstructured":"Bitterli, B.: Rendering resources (2016)"},{"key":"2975_CR4","doi-asserted-by":"crossref","unstructured":"Charles, R.Q., Su, H., Kaichun, M., Guibas, L.J.: Pointnet: Deep learning on point sets for 3d classification and segmentation. In: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 77\u201385 (2017)","DOI":"10.1109\/CVPR.2017.16"},{"key":"2975_CR5","unstructured":"Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks on graphs with fast localized spectral filtering. In: NIPS\u201916, pp. 3844\u20133852. Curran Associates Inc., Red Hook, NY, USA (2016)"},{"key":"2975_CR6","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, HPG \u201915, pp. 13\u201320. Association for Computing Machinery, New York, NY, USA (2015)","DOI":"10.1145\/2790060.2790065"},{"issue":"3","key":"2975_CR7","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)"},{"issue":"5","key":"2975_CR8","doi-asserted-by":"publisher","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":"2975_CR9","doi-asserted-by":"crossref","unstructured":"Hanocka, R., Metzer, G., Giryes, R., Cohen-Or, D.: Point2mesh: a self-prior for deformable meshes. ACM Trans. Graph. 39(4), 126:1\u2013126:12 (2020)","DOI":"10.1145\/3386569.3392415"},{"issue":"2","key":"2975_CR10","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1111\/cgf.13143","volume":"36","author":"J Hendrich","year":"2017","unstructured":"Hendrich, J., Meister, D., Bittner, J.: Parallel BVH construction using progressive hierarchical refinement. Comput. Graph. Forum 36(2), 487\u2013494 (2017)","journal-title":"Comput. Graph. Forum"},{"issue":"1","key":"2975_CR11","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1214\/aoms\/1177703732","volume":"35","author":"PJ Huber","year":"1964","unstructured":"Huber, P.J.: Robust estimation of a location parameter. Ann. Math. Stat. 35(1), 73\u2013101 (1964)","journal-title":"Ann. Math. Stat."},{"key":"2975_CR12","doi-asserted-by":"crossref","unstructured":"Hunt, W., Mark, W.R., Fussell, D.: Fast and lazy build of acceleration structures from scene hierarchies. In: 2007 IEEE Symposium on Interactive Ray Tracing, pp. 47\u201354 (2007)","DOI":"10.1109\/RT.2007.4342590"},{"key":"2975_CR13","doi-asserted-by":"crossref","unstructured":"Jensen, H.W.: Global illumination using photon maps. In: Proceedings of the Eurographics Workshop on Rendering Techniques \u201996, pp. 21\u201330. Springer, Berlin (1996)","DOI":"10.1007\/978-3-7091-7484-5_3"},{"key":"2975_CR14","doi-asserted-by":"crossref","unstructured":"Kalojanov, J., Billeter, M., Slusallek, P.: Two-level grids for ray tracing on GPUs. Comput. Graph. Forum 30(2), 307\u2013314 (2011)","DOI":"10.1111\/j.1467-8659.2011.01862.x"},{"key":"2975_CR15","doi-asserted-by":"crossref","unstructured":"Karras, T., Aila, T.: Fast parallel construction of high-quality bounding volume hierarchies. In: Proceedings of the 5th High-Performance Graphics Conference, HPG \u201913, pp. 89\u201399. Association for Computing Machinery, New York, NY, USA (2013)","DOI":"10.1145\/2492045.2492055"},{"key":"2975_CR16","unstructured":"Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24\u201326, 2017, Conference Track Proceedings. OpenReview.net (2017)"},{"key":"2975_CR17","doi-asserted-by":"crossref","unstructured":"Klokov, R., Lempitsky, V.S.: Escape from cells: deep kd-networks for the recognition of 3d point cloud models. In: 2017 IEEE International Conference on Computer Vision (ICCV), pp. 863\u2013872 (2017)","DOI":"10.1109\/ICCV.2017.99"},{"key":"2975_CR18","doi-asserted-by":"crossref","unstructured":"Li, R., Li, X., Hui, K.H., Fu, C.W.: SP-GAN: sphere-guided 3d shape generation and manipulation. ACM Trans. Graph. 40(4), 1\u201312 (2021)","DOI":"10.1145\/3476576.3476732"},{"key":"2975_CR19","unstructured":"Lumberyard, A.: Amazon lumberyard bistro, open research content archive (ORCA) (2017)"},{"issue":"3","key":"2975_CR20","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01911006","volume":"6","author":"DJ MacDonald","year":"1990","unstructured":"MacDonald, D.J., Booth, K.S.: Heuristics for ray tracing using space subdivision. Vis. Comput. 6(3), 153\u2013166 (1990)","journal-title":"Vis. Comput."},{"key":"2975_CR21","doi-asserted-by":"crossref","unstructured":"Maturana, D., Scherer, S.: Voxnet: a 3d convolutional neural network for real-time object recognition. In: 2015 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 922\u2013928 (2015)","DOI":"10.1109\/IROS.2015.7353481"},{"key":"2975_CR22","unstructured":"McGuire, M.: Computer graphics archive (2017)"},{"key":"2975_CR23","doi-asserted-by":"crossref","unstructured":"Meister, D., Bittner, J.: Parallel reinsertion for bounding volume hierarchy optimization. Comput. Graph. Forum 37(2), 463\u2013473 (2018)","DOI":"10.1111\/cgf.13376"},{"issue":"2","key":"2975_CR24","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1111\/cgf.142662","volume":"40","author":"D Meister","year":"2021","unstructured":"Meister, D., Ogaki, S., Benthin, C., Doyle, M.J., Guthe, M., Bittner, J.: A survey on bounding volume hierarchies for ray tracing. Comput. Graph. Forum 40(2), 683\u2013712 (2021)","journal-title":"Comput. Graph. Forum"},{"key":"2975_CR25","unstructured":"Muja, M., Lowe, D.G.: Fast approximate nearest neighbors with automatic algorithm configuration. In: VISAPP International Conference on Computer Vision Theory and Applications, pp. 331\u2013340. INSTICC Press (2009)"},{"key":"2975_CR26","unstructured":"Pharr, M., Wenzel, J., Humphreys, G.: Scenes for pbrt-v3 (2016)"},{"issue":"2","key":"2975_CR27","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1111\/cgf.13142","volume":"36","author":"A P\u00e9rard-Gayot","year":"2017","unstructured":"P\u00e9rard-Gayot, A., Kalojanov, J., Slusallek, P.: GPU ray tracing using irregular grids. Comput. Graph. Forum 36(2), 477\u2013486 (2017)","journal-title":"Comput. Graph. Forum"},{"key":"2975_CR28","doi-asserted-by":"crossref","unstructured":"Riegler, G., Ulusoy, A.O., Geiger, A.: Octnet: learning deep 3d representations at high resolutions. In: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 6620\u20136629 (2017)","DOI":"10.1109\/CVPR.2017.701"},{"key":"2975_CR29","doi-asserted-by":"crossref","unstructured":"Stich, M., Friedrich, H., Dietrich, A.: Spatial splits in bounding volume hierarchies. In: Proceedings of the Conference on High Performance Graphics 2009, HPG \u201909, pp. 7\u201313. ACM, New York, NY, USA (2009)","DOI":"10.1145\/1572769.1572771"},{"key":"2975_CR30","doi-asserted-by":"crossref","unstructured":"Wald, I.: On fast construction of sah-based bounding volume hierarchies. In: Proceedings of the 2007 IEEE Symposium on Interactive Ray Tracing, RT \u201907, pp. 33\u201340. IEEE Computer Society, USA (2007)","DOI":"10.1109\/RT.2007.4342588"},{"issue":"3","key":"2975_CR31","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1111\/j.1467-8659.2004.00791.x","volume":"23","author":"I Wald","year":"2004","unstructured":"Wald, I., G\u00fcnther, J., Slusallek, P.: Balancing considered harmful\u2014faster photon mapping using the voxel volume heuristic\u2014. Comput. Graph. Forum 23(3), 595\u2013603 (2004)","journal-title":"Comput. Graph. Forum"},{"key":"2975_CR32","doi-asserted-by":"crossref","unstructured":"Wald, I., Havran, V.: On building fast kd-trees for ray tracing, and on doi2ng that in o(n log n). In: 2006 IEEE Symposium on Interactive Ray Tracing, pp. 61\u201369 (2006)","DOI":"10.1109\/RT.2006.280216"},{"key":"2975_CR33","doi-asserted-by":"crossref","unstructured":"Wald, I., Woop, S., Benthin, C., Johnson, G.S., Ernst, M.: Embree: a kernel framework for efficient CPU ray tracing. ACM Trans. Graph. 33(4), 1\u20138 (2014)","DOI":"10.1145\/2601097.2601199"},{"key":"2975_CR34","doi-asserted-by":"crossref","unstructured":"Wang, P.S., Sun, C.Y., Liu, Y., Tong, X.: Adaptive O-CNN: a patch-based deep representation of 3d shapes. ACM Trans. Graph. 37(6), 1\u201311 (2018)","DOI":"10.1145\/3272127.3275050"},{"key":"2975_CR35","unstructured":"Zaheer, M., Kottur, S., Ravanbhakhsh, S., P\u00f3czos, B., Salakhutdinov, R., Smola, A.J.: Deep sets. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS\u201917, pp. 3394\u20133404. Curran Associates Inc., Red Hook, NY, USA (2017)"},{"key":"2975_CR36","doi-asserted-by":"crossref","unstructured":"Zhou, K., Hou, Q., Wang, R., Guo, B.: Real-time KD-tree construction on graphics hardware. ACM Trans. Graph. 27(5), 1\u201311 (2008)","DOI":"10.1145\/1409060.1409079"}],"container-title":["The Visual Computer"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-023-02975-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00371-023-02975-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-023-02975-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T10:04:17Z","timestamp":1695722657000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00371-023-02975-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,24]]},"references-count":36,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["2975"],"URL":"https:\/\/doi.org\/10.1007\/s00371-023-02975-y","relation":{},"ISSN":["0178-2789","1432-2315"],"issn-type":[{"type":"print","value":"0178-2789"},{"type":"electronic","value":"1432-2315"}],"subject":[],"published":{"date-parts":[[2023,7,24]]},"assertion":[{"value":"14 June 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors declare that they have no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}