{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:03Z","timestamp":1740107103087,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"9-11","license":[{"start":{"date-parts":[[2021,7,28]],"date-time":"2021-07-28T00:00:00Z","timestamp":1627430400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,28]],"date-time":"2021-07-28T00:00:00Z","timestamp":1627430400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Vis Comput"],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Large-scale unstructured point cloud scenes can be quickly visualized without prior reconstruction by utilizing levels-of-detail structures to load an appropriate subset from out-of-core storage for rendering the current view. However, as soon as we need structures within the point cloud, e.g., for interactions between objects, the construction of state-of-the-art data structures requires <jats:italic>O<\/jats:italic>(<jats:italic>NlogN<\/jats:italic>) time for <jats:italic>N<\/jats:italic> points, which is not feasible in real time for millions of points that are possibly updated in each frame. Therefore, we propose to use a surface representation structure which trades off the (here negligible) disadvantage of single-frame use for <jats:italic>both output-dominated and near-linear construction time in practice<\/jats:italic>, exploiting the inherent 2D property of sampled surfaces in 3D. This structure tightly encompasses the assumed surface of unstructured points in a set of bounding depth intervals for each cell of a discrete 2D grid. The sorted depth samples in the structure permit fast surface queries, and on top of that an occlusion graph for the scene comes almost for free. This graph enables novel real-time user operations such as revealing partially occluded objects, or scrolling through layers of occluding objects, e.g., walls in a building. As an example application we showcase a 3D scene exploration framework that enables fast, more sophisticated interactions with point clouds rendered in real time.<\/jats:p>","DOI":"10.1007\/s00371-021-02243-x","type":"journal-article","created":{"date-parts":[[2021,7,28]],"date-time":"2021-07-28T11:02:44Z","timestamp":1627470164000},"page":"2769-2781","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast occlusion-based point cloud exploration"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5938-557X","authenticated-orcid":false,"given":"Mohamed","family":"Radwan","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Ohrhallinger","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Wimmer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,28]]},"reference":[{"issue":"5","key":"2243_CR1","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1111\/cgf.12169","volume":"32","author":"S Asafi","year":"2013","unstructured":"Asafi, S., Goren, A., Cohen-Or, D.: Weak convex decomposition by lines-of-sight. Comput. Graphics Forum 32(5), 23\u201331 (2013)","journal-title":"Comput. Graphics Forum"},{"key":"2243_CR2","doi-asserted-by":"crossref","unstructured":"Benger, W., Hildenbrand, D., Dobler, W.: Optimizing refined geometric primitive\u2019s leaflet visibility for interactive 3d visualization via geometric algebra. In: Proceedings of CGI 2018, p. 267\u2013272. ACM, NY (2018)","DOI":"10.1145\/3208159.3208194"},{"issue":"5","key":"2243_CR3","first-page":"1077","volume":"12","author":"S Bruckner","year":"2006","unstructured":"Bruckner, S., Groeller, M.E.: Exploded views for volume data. IEEE TVCG 12(5), 1077\u20131084 (2006)","journal-title":"IEEE TVCG"},{"issue":"4","key":"2243_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3072959.3073714","volume":"36","author":"S Calderon","year":"2017","unstructured":"Calderon, S., Boubekeur, T.: Bounding proxies for shape approximation. ACM Trans. Graphics 36(4), 1\u201313 (2017)","journal-title":"ACM Trans. Graphics"},{"issue":"5","key":"2243_CR5","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1109\/TVCG.2012.159","volume":"19","author":"R Carnecky","year":"2013","unstructured":"Carnecky, R., Fuchs, R., Mehl, S., Jang, Y., Peikert, R.: Smart transparency for illustrative visualization of complex flow surfaces. IEEE Trans. Vis. Comput. Graphics 19(5), 838\u2013851 (2013)","journal-title":"IEEE Trans. Vis. Comput. Graphics"},{"issue":"4","key":"2243_CR6","first-page":"634","volume":"18","author":"J Cashion","year":"2012","unstructured":"Cashion, J., Wingrave, C., LaViola Jr., J.J.: Dense and dynamic 3d selection for game-based virtual environments. IEEE TVCG 18(4), 634\u2013642 (2012)","journal-title":"IEEE TVCG"},{"issue":"06","key":"2243_CR7","first-page":"1320","volume":"13","author":"M Chen","year":"2007","unstructured":"Chen, M., Correa, C., Silver, D.: Illustrative deformation for data exploration. TVCG 13(06), 1320\u20131327 (2007)","journal-title":"TVCG"},{"key":"2243_CR8","unstructured":"Xian, C., Lin, H., Gao, S.: Automatic generation of coarse bounding cages from dense meshes. In: 2009 IEEE ICSMA, pp. 21\u201327 (2009)"},{"issue":"3","key":"2243_CR9","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1145\/882262.882321","volume":"22","author":"C Dachsbacher","year":"2003","unstructured":"Dachsbacher, C., Vogelgsang, C., Stamminger, M.: Sequential point trees. ACM ToG 22(3), 657\u2013662 (2003)","journal-title":"ACM ToG"},{"key":"2243_CR10","first-page":"538","volume":"26","author":"Z Deng","year":"2011","unstructured":"Deng, Z., Luo, X., Miao, X.P.: Automatic cage building with quadric error metrics. JCST 26, 538\u2013547 (2011)","journal-title":"JCST"},{"key":"2243_CR11","doi-asserted-by":"crossref","unstructured":"Diepstraten, J., Weiskopf, D., Ertl, T.: Transparency in Interactive Technical Illustrations. CGF (2002)","DOI":"10.1111\/1467-8659.00591"},{"key":"2243_CR12","doi-asserted-by":"crossref","unstructured":"Eisemann, E., Paris, S., Durand, F.: A visibility algorithm for converting 3d meshes into editable 2d vector graphics. ACM Trans. Graph. 28(3), 83:1\u201383:8 (2009)","DOI":"10.1145\/1531326.1531389"},{"key":"2243_CR13","doi-asserted-by":"crossref","unstructured":"Elmqvist, N., Tsigas, P.: A taxonomy of 3d occlusion management techniques. In: 2007 IEEE Virtual Reality Conference, pp. 51\u201358 (2007)","DOI":"10.1109\/VR.2007.352463"},{"key":"2243_CR14","doi-asserted-by":"crossref","unstructured":"Elvins, T.T., Nadeau, D.R., Kirsh, D.: Worldlets\u20133d thumbnails for wayfinding in virtual environments. In: Proc. UIST \u201997, pp. 21\u201330. ACM, NY, USA (1997)","DOI":"10.1145\/263407.263504"},{"key":"2243_CR15","unstructured":"Everitt, C.: Interactive order-independent transparency. Tech. rep., NVIDIA corporation (2001)"},{"key":"2243_CR16","unstructured":"Faure, F., Barbier, S., Allard, J., Falipou, F.: Image-based collision detection and response between arbitrary volume objects. EG Ass. (2008)"},{"issue":"6","key":"2243_CR17","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.cag.2004.08.010","volume":"28","author":"E Gobbetti","year":"2004","unstructured":"Gobbetti, E., Marton, F.: Layered point clouds: A simple and efficient multiresolution structure for distributing and rendering gigantic point-sampled models. Comput. Graphics 28(6), 815\u2013826 (2004)","journal-title":"Comput. Graphics"},{"key":"2243_CR18","unstructured":"Heidelberger, B., Teschner, M., Gross, M.: Real-time volumetric intersections of deforming objects. In: VMV\u201903, vol. 2003, pp. 461\u2013468 (2003)"},{"key":"2243_CR19","unstructured":"Heidelberger, B., Teschner, M., Gross, M.: Detection of collisions and self-collisions using image-space techniques. J. WSCG 12, 145\u2013152 (2004)"},{"key":"2243_CR20","unstructured":"Hoberock, J., Bell, N.: Thrust: A parallel template library (2010). http:\/\/thrust.github.io\/. Version 1.7.0"},{"key":"2243_CR21","doi-asserted-by":"crossref","unstructured":"Hofmann, N., Bogend\u00f6rfer, P., Stamminger, M., Selgrad, K.: Hierarchical multi-layer screen-space ray tracing. In: Proc. of HPG \u201917. ACM, NY, USA (2017)","DOI":"10.1145\/3105762.3105781"},{"key":"2243_CR22","doi-asserted-by":"crossref","unstructured":"Hu, Q., Yang, B., Xie, L., Rosa, S., Guo, Y., Wang, Z., Trigoni, N., Markham, A.: Randla-net: Efficient semantic segmentation of large-scale point clouds. In: Proceedings of the IEEE Conference on CVPR (2020)","DOI":"10.1109\/CVPR42600.2020.01112"},{"issue":"6","key":"2243_CR23","first-page":"801","volume":"28","author":"L Kobbelt","year":"2004","unstructured":"Kobbelt, L., Botsch, M.: A survey of point-based techniques in computer graphics. C&G 28(6), 801\u2013814 (2004)","journal-title":"C&G"},{"key":"2243_CR24","doi-asserted-by":"crossref","unstructured":"Kopper, R., Bacim, F., Bowman, D.A.: Rapid and accurate 3d selection by progressive refinement. In: 2011 IEEE Symp. on 3D User Int. (3DUI), pp. 67\u201374 (2011)","DOI":"10.1109\/3DUI.2011.5759219"},{"key":"2243_CR25","doi-asserted-by":"crossref","unstructured":"Mossel, A., Koessler, C.: Large scale cut plane: An occlusion management technique for immersive dense 3d reconstructions. In: Proc. 22nd ACM Conference on VRST, pp. 201\u2013210. ACM, NY, USA (2016)","DOI":"10.1145\/2993369.2993384"},{"key":"2243_CR26","doi-asserted-by":"crossref","unstructured":"Ponto, K., Tredinnick, R., Casper, G.: Simulating the experience of home environments. In: 2017 International Conference on Virtual Rehabilitation (ICVR), pp. 1\u20139 (2017)","DOI":"10.1109\/ICVR.2017.8007521"},{"key":"2243_CR27","unstructured":"Qi, C.R., Su, H., Mo, K., Guibas, L.J.: Pointnet: Deep learning on point sets for 3d classification and segmentation. arXiv:1612.00593 (2016)"},{"key":"2243_CR28","unstructured":"Qi, C.R., Yi, L., Su, H., Guibas, L.J.: Pointnet++: Deep hierarchical feature learning on point sets in a metric space (2017)"},{"key":"2243_CR29","doi-asserted-by":"crossref","unstructured":"Radwan, M., Ohrhallinger, S., Wimmer, M.: Efficient collision detection while rendering dynamic points. In: Proceedings of the 2014 Graphics Interface Conference, pp. 25\u201333 (2014)","DOI":"10.1201\/9781003059325-4"},{"key":"2243_CR30","doi-asserted-by":"crossref","unstructured":"R\u00f6hlig, M., Schumann, H.: Visibility widgets: Managing occlusion of quantitative data in 3d terrain visualization. In: Proc. 9th Intl Symp. VICI, VINCI \u201916, pp. 51\u201358. ACM, New York, NY, USA (2016)","DOI":"10.1145\/2968220.2968230"},{"key":"2243_CR31","doi-asserted-by":"crossref","unstructured":"Rusinkiewicz, S., Levoy, M.: Qsplat: A multiresolution point rendering system for large meshes. In: Proc. 27th Ann. Conf. CGIT, pp. 343\u2013352. ACM, USA (2000)","DOI":"10.1145\/344779.344940"},{"key":"2243_CR32","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/2816795.2818093","volume":"34","author":"L Sacht","year":"2015","unstructured":"Sacht, L., Vouga, E., Jacobson, A.: Nested cages. ACM Trans. Graphics 34, 6 (2015)","journal-title":"ACM Trans. Graphics"},{"key":"2243_CR33","doi-asserted-by":"crossref","unstructured":"Sander, P.V., Gu, X., Gortler, S.J., Hoppe, H., Snyder, J.: Silhouette clipping. SIGGRAPH \u201900, pp. 327\u2013334. ACM Press\/Addison-Wesley Publishing Co., USA (2000)","DOI":"10.1145\/344779.344935"},{"key":"2243_CR34","unstructured":"Schuetz, M.: Potree: Rendering large point clouds in web browsers. Master\u2019s thesis, ICGA, TU Wien (2016)"},{"key":"2243_CR35","doi-asserted-by":"crossref","unstructured":"Shade, J., Gortler, S., He, L.W., Szeliski, R.: Layered depth images. In: Proc. 25th Ann. Conf. CGIT, SIGGRAPH \u201998, pp. 231\u2013242. ACM, NY, USA (1998)","DOI":"10.1145\/280814.280882"},{"key":"2243_CR36","doi-asserted-by":"crossref","unstructured":"Stoakley, R., Conway, M.J., Pausch, R.: Virtual reality on a wim: Interactive worlds in miniature. In: Proc. of SIGCHI, CHI \u201995, pp. 265\u2013272. ACM, USA (1995)","DOI":"10.1145\/223904.223938"},{"key":"2243_CR37","doi-asserted-by":"crossref","unstructured":"Tredinnick, R., Broecker, M., Ponto, K.: Progressive feedback point cloud rendering for virtual reality display. In: 2016 IEEE Virtual Reality (VR), pp. 301\u2013302 (2016)","DOI":"10.1109\/VR.2016.7504773"},{"key":"2243_CR38","doi-asserted-by":"crossref","unstructured":"Vanacken, L., Grossman, T., Coninx, K.: Exploring the effects of environment density and target visibility on object selection in 3d virtual environments. In: 2007 IEEE Symposium on 3D User Interfaces (2007)","DOI":"10.1109\/3DUI.2007.340783"},{"key":"2243_CR39","unstructured":"Wimmer, M., Scheiblauer, C.: Instant points: Fast rendering of unprocessed point clouds. In: Proc. Symp. on PBG 2006, pp. 129\u2013136. Eurographics, EG Ass. (2006)"},{"issue":"5","key":"2243_CR40","doi-asserted-by":"publisher","first-page":"1555","DOI":"10.1109\/TVCG.2015.2443804","volume":"22","author":"M Wu","year":"2016","unstructured":"Wu, M., Popescu, V.: Multiperspective focus+context visualization. IEEE Trans. Vis. Comput. Graphics 22(5), 1555\u20131567 (2016)","journal-title":"IEEE Trans. Vis. Comput. Graphics"},{"issue":"1","key":"2243_CR41","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00371-011-0595-6","volume":"28","author":"C Xian","year":"2012","unstructured":"Xian, C., Lin, H., Gao, S.: Automatic cage generation by improved obbs for mesh deformation. Vis. Comput. 28(1), 21\u201333 (2012)","journal-title":"Vis. Comput."}],"container-title":["The Visual Computer"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-021-02243-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00371-021-02243-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-021-02243-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T14:24:59Z","timestamp":1630419899000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00371-021-02243-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,28]]},"references-count":41,"journal-issue":{"issue":"9-11","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["2243"],"URL":"https:\/\/doi.org\/10.1007\/s00371-021-02243-x","relation":{},"ISSN":["0178-2789","1432-2315"],"issn-type":[{"type":"print","value":"0178-2789"},{"type":"electronic","value":"1432-2315"}],"subject":[],"published":{"date-parts":[[2021,7,28]]},"assertion":[{"value":"4 July 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The Authors declare that there is no conflict of interest","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}}]}}