Concomitant Hierarchy Construction and Rendering of Large Point Clouds
Resumo
Rendering large point clouds ordinarily requires building a hierarchical data structure for accessing the points that best represent the object for a given viewing frustum and level-of-detail. The building of such data structures frequently represents a large portion of the cost of the rendering pipeline both in terms of time and space complexity, especially when rendering is done for inspection purposes only. In this work we present OMiCroN -- Oblique Multipass Hierarchy Creation while Navigating -- which is the first algorithm capable of immediately displaying partial renders of the geometry, provided the cloud is made available sorted in Morton order. In fact, a pipeline coupling OMiCroN with an incremental sorting algorithm running in parallel can start rendering as soon as the first sorted prefix is produced, making this setup very convenient for streamed viewing.
Referências
S. Rusinkiewicz and M. Levoy, “Qsplat: A multiresolution point rendering system for large meshes,” in Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, ser. SIGGRAPH ’00. New York, NY, USA: ACM Press/Addison-Wesley Publishing Co., 2000, pp. 343–352. [Online]. Available: http://dx.doi.org/10.1145/344779.344940
M. Wimmer and C. Scheiblauer, “Instant points: Fast rendering of unprocessed point clouds,” in Proceedings of the 3rd Eurographics / IEEE VGTC Conference on Point-Based Graphics, ser. SPBG’06. Aire-la-Ville, Switzerland, Switzerland: Eurographics Association, 2006, pp. 129–137. [Online]. Available: http://dx.doi.org/10.2312/SPBG/SPBG06/129-136
J. Klein and G. Zachmann, “Point cloud collision detection,” in Com-puter Graphics Forum, vol. 23, no. 3. Wiley Online Library, 2004, pp. 567–576.
Morton, “A computer oriented geodetic data base and a new technique in file sequencing,” IBM Ltd., Tech. Rep. Ottawa, Ontario, Canada, 1966.
J. T. Klosowski, M. Held, J. S. B. Mitchell, H. Sowizral, and K. Zikan, “Efficient collision detection using bounding volume hierarchies of k-dops,” IEEE Transactions on Visualization and Computer Graphics, vol. 4, no. 1, pp. 21–36, Jan. 1998. [Online]. Available: http://dx.doi.org/10.1109/2945.675649
S. A. Ehmann and M. C. Lin, “Accurate and fast proximity queries between polyhedra using convex surface decomposition,” Computer Graphics Forum, vol. 20, no. 3, pp. 500–511, 2001. https://doi.org/10.1111/1467-8659.00543
C. Lauterbach, Q. Mo, and D. Manocha, “gproximity: Hierarchical gpu-based operations for collision and distance queries.” Comput. Graph. Forum, vol. 29, no. 2, pp. 419–428, 2010. https://doi.org/10.1111/j.1467-8659.2009.01611.x
O. Argudo, I. Besora, P. Brunet, C. Creus, P. Hermosilla, I. Navazo, and À. Vinacua, “Interactive inspection of complex multi-object industrial assemblies,” Computer-Aided Design, vol. 79, pp. 48 – 59, 2016. https://doi.org/10.1016/j.cad.2016.06.005
M. Levoy and T. Whitted, The use of points as a display primitive. Chapel Hill, NC, USA: University of North Carolina, Department of Computer Science, 1985.
J. P. Grossman and W. J. Dally, “Point sample rendering,” in Rendering Techniques ’98, G. Drettakis and N. Max, Eds. Vienna: Springer Vienna, 1998, pp. 181–192. https://doi.org/10.1007/978-3-7091-6453-2_17
M. Sainz and R. Pajarola, “Point-based rendering techniques,” Computers & Graphics, vol. 28, no. 6, pp. 869–879, 2004. https://doi.org/10.1016/j.cag.2004.08.014
L. Kobbelt and M. Botsch, “A survey of point-based techniques in computer graphics,” Computers & Graphics, vol. 28, no. 6, pp. 801– 814, 2004. https://doi.org/10.1016/j.cag.2004.08.009
M. Alexa, M. Gross, M. Pauly, H. Pfister, M. Stamminger, and M. Zwicker, “Point-based computer graphics,” in ACM SIGGRAPH 2004 Course Notes. ACM, 2004, p. 7. https://doi.org/10.1145/1103900.1103907
M. Gross, “Getting to the point...?” IEEE computer graphics and applications, vol. 26, no. 5, pp. 96–99, 2006. https://doi.org/10.1109/MCG.2006.106
M. Gross and H. Pfister, Point-Based Graphics. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2011. https://doi.org/10.1016/B978-0-12-370604-1.X5000-7
F. Ramos, J. Huerta, and F. Benitez, “Characterization of multiresolution models for real-time rendering in gpu-limited environments,” in International Conference on Articulated Motion and Deformable Objects. Springer, 2016, pp. 157–167. https://doi.org/10.1007/978-3-319-41778-3_16
C. Dachsbacher, C. Vogelgsang, and M. Stamminger, “Sequential point trees,” in ACM Transactions on Graphics (TOG), vol. 22, no. 3. ACM,2003, pp. 657–662. https://doi.org/10.1145/1201775.882321
R. Pajarola, M. Sainz, and R. Lario, “Xsplat: External memory mul-tiresolution point visualization,” in Proceedings IASTED Invernational Conference on Visualization, Imaging and Image Processing, 2005, pp. 628–633. https://doi.org/10.5167/uzh-47730
E. Gobbetti and F. Marton, “Layered point clouds: A simple and efficient multiresolution structure for distributing and rendering gigantic point-sampled models,” Comput. Graph., vol. 28, no. 6, pp. 815–826, Dec. 2004. [Online]. Available: http://dx.doi.org/10.1016/j.cag.2004.08.010
M. Wand, A. Berner, M. Bokeloh, A. Fleck, M. Hoffmann, P. Jenke, B. Maier, D. Staneker, and A. Schilling, “Interactive editing of large point clouds.” in SPBG, 2007, pp. 37–45. http://dx.doi.org/10.2312/SPBG/SPBG07/037-045
F. Bettio, E. Gobbetti, F. Marton, A. Tinti, E. Merella, and R. Combet, “A point-based system for local and remote exploration of dense 3d scanned models.” in VAST, 2009, pp. 25–32. http://dx.doi.org/10.2312/VAST/VAST09/025-032
E. Hubo and P. Bekaert, “A data distribution strategy for parallel point-based rendering,” 2005.
W. T. Corrêa, S. Fleishman, and C. T. Silva, “Towards point-based acquisition and rendering of large real-world environments,” in Computer Graphics and Image Processing, 2002. Proceedings. XV Brazilian Symposium on. IEEE, 2002, pp. 59–66. https://doi.org/10.1109/SIBGRA.2002.1167124
W. T. Corrêa, J. T. Klosowski, and C. T. Silva, “Out-of-core sort-first parallel rendering for cluster-based tiled displays,” Parallel Computing, vol. 29, no. 3, pp. 325–338, 2003. https://doi.org/10.1016/S0167-8191(02)00249-1
P. Goswami, M. Makhinya, J. Bösch, and R. Pajarola, “Scalable parallel out-of-core terrain rendering.” in EGPGV, 2010, pp. 63–71. https://doi.org/10.2312/egpgv/egpgv10/063-071
P. Goswami, F. Erol, R. Mukhi, R. Pajarola, and E. Gobbetti, “An efficient multi-resolution framework for high quality interactive rendering of massive point clouds using multi-way kd-trees,” The Visual Computer, vol. 29, no. 1, pp. 69–83, 2013. [Online]. Available: http://dx.doi.org/10.1007/s00371-012-0675-2
N. Lukac et al., “Hybrid visualization of sparse point-based data using gpgpu,” in Computing and Networking (CANDAR), 2014 Second International Symposium on. IEEE, 2014, pp. 178–184. https://doi.org/10.1109/CANDAR.2014.76
Z. Gao, L. Nocera, M. Wang, and U. Neumann, “Visualizing aerial lidar cities with hierarchical hybrid point-polygon structures,” in Proceedings of Graphics Interface 2014, ser. GI ’14. Toronto, Ont., Canada, Canada: Canadian Information Processing Society, 2014, pp. 137–144.
R. Richter, S. Discher, and J. Döllner, “Out-of-core visualization of classified 3d point clouds,” in 3D Geoinformation Science. Springer, 2015, pp. 227–242. https://doi.org/10.1007/978-3-319-12181-9_14
A. Febretti, K. Richmond, P. Doran, and A. Johnson, “Parallel processing and immersive visualization of sonar point clouds,” in Large Data Analysis and Visualization (LDAV), 2014 IEEE 4th Symposium on. IEEE, 2014, pp. 111–112. https://doi.org/10.1109/LDAV.2014.7013214
M. Potenziani, M. Callieri, M. Dellepiane, M. Corsini, F. Ponchio, and R. Scopigno, “3dhop: 3d heritage online presenter,” Computers & Graphics, vol. 52, pp. 129–141, 2015. https://doi.org/10.1016/j.cag.2015.07.001
R. Tredinnick, M. Broecker, and K. Ponto, “Experiencing interior environments: New approaches for the immersive display of large-scale point cloud data,” in Virtual Reality (VR), 2015 IEEE. IEEE, 2015, pp. 297–298. https://doi.org/10.1109/VR.2015.7223413
H. Okamoto and H. Masuda, “A point-based virtual reality system for supporting product development,” in ASME 2016 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2016, pp. V01BT02A052–V01BT02A052. https://doi.org/10.1115/DETC2016-59756
K. Ponto, R. Tredinnick, and G. Casper, “Simulating the experience of home environments,” in Virtual Rehabilitation (ICVR), 2017 International Conference on. IEEE, 2017, pp. 1–9. https://doi.org/10.1109/ICVR.2017.8007521
M. Schütz, “Potree: Rendering large point clouds in web browsers,” Technische Universität Wien, Wiedeń, 2016.
M. Wimmer and C. Scheiblauer, “Instant points: Fast rendering of unprocessed point clouds,” in Proceedings of the 3rd Eurographics / IEEE VGTC Conference on Point-Based Graphics, ser. SPBG’06. Aire-la-Ville, Switzerland, Switzerland: Eurographics Association, 2006, pp. 129–137. [Online]. Available: http://dx.doi.org/10.2312/SPBG/SPBG06/129-136
J. Klein and G. Zachmann, “Point cloud collision detection,” in Com-puter Graphics Forum, vol. 23, no. 3. Wiley Online Library, 2004, pp. 567–576.
Morton, “A computer oriented geodetic data base and a new technique in file sequencing,” IBM Ltd., Tech. Rep. Ottawa, Ontario, Canada, 1966.
J. T. Klosowski, M. Held, J. S. B. Mitchell, H. Sowizral, and K. Zikan, “Efficient collision detection using bounding volume hierarchies of k-dops,” IEEE Transactions on Visualization and Computer Graphics, vol. 4, no. 1, pp. 21–36, Jan. 1998. [Online]. Available: http://dx.doi.org/10.1109/2945.675649
S. A. Ehmann and M. C. Lin, “Accurate and fast proximity queries between polyhedra using convex surface decomposition,” Computer Graphics Forum, vol. 20, no. 3, pp. 500–511, 2001. https://doi.org/10.1111/1467-8659.00543
C. Lauterbach, Q. Mo, and D. Manocha, “gproximity: Hierarchical gpu-based operations for collision and distance queries.” Comput. Graph. Forum, vol. 29, no. 2, pp. 419–428, 2010. https://doi.org/10.1111/j.1467-8659.2009.01611.x
O. Argudo, I. Besora, P. Brunet, C. Creus, P. Hermosilla, I. Navazo, and À. Vinacua, “Interactive inspection of complex multi-object industrial assemblies,” Computer-Aided Design, vol. 79, pp. 48 – 59, 2016. https://doi.org/10.1016/j.cad.2016.06.005
M. Levoy and T. Whitted, The use of points as a display primitive. Chapel Hill, NC, USA: University of North Carolina, Department of Computer Science, 1985.
J. P. Grossman and W. J. Dally, “Point sample rendering,” in Rendering Techniques ’98, G. Drettakis and N. Max, Eds. Vienna: Springer Vienna, 1998, pp. 181–192. https://doi.org/10.1007/978-3-7091-6453-2_17
M. Sainz and R. Pajarola, “Point-based rendering techniques,” Computers & Graphics, vol. 28, no. 6, pp. 869–879, 2004. https://doi.org/10.1016/j.cag.2004.08.014
L. Kobbelt and M. Botsch, “A survey of point-based techniques in computer graphics,” Computers & Graphics, vol. 28, no. 6, pp. 801– 814, 2004. https://doi.org/10.1016/j.cag.2004.08.009
M. Alexa, M. Gross, M. Pauly, H. Pfister, M. Stamminger, and M. Zwicker, “Point-based computer graphics,” in ACM SIGGRAPH 2004 Course Notes. ACM, 2004, p. 7. https://doi.org/10.1145/1103900.1103907
M. Gross, “Getting to the point...?” IEEE computer graphics and applications, vol. 26, no. 5, pp. 96–99, 2006. https://doi.org/10.1109/MCG.2006.106
M. Gross and H. Pfister, Point-Based Graphics. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2011. https://doi.org/10.1016/B978-0-12-370604-1.X5000-7
F. Ramos, J. Huerta, and F. Benitez, “Characterization of multiresolution models for real-time rendering in gpu-limited environments,” in International Conference on Articulated Motion and Deformable Objects. Springer, 2016, pp. 157–167. https://doi.org/10.1007/978-3-319-41778-3_16
C. Dachsbacher, C. Vogelgsang, and M. Stamminger, “Sequential point trees,” in ACM Transactions on Graphics (TOG), vol. 22, no. 3. ACM,2003, pp. 657–662. https://doi.org/10.1145/1201775.882321
R. Pajarola, M. Sainz, and R. Lario, “Xsplat: External memory mul-tiresolution point visualization,” in Proceedings IASTED Invernational Conference on Visualization, Imaging and Image Processing, 2005, pp. 628–633. https://doi.org/10.5167/uzh-47730
E. Gobbetti and F. Marton, “Layered point clouds: A simple and efficient multiresolution structure for distributing and rendering gigantic point-sampled models,” Comput. Graph., vol. 28, no. 6, pp. 815–826, Dec. 2004. [Online]. Available: http://dx.doi.org/10.1016/j.cag.2004.08.010
M. Wand, A. Berner, M. Bokeloh, A. Fleck, M. Hoffmann, P. Jenke, B. Maier, D. Staneker, and A. Schilling, “Interactive editing of large point clouds.” in SPBG, 2007, pp. 37–45. http://dx.doi.org/10.2312/SPBG/SPBG07/037-045
F. Bettio, E. Gobbetti, F. Marton, A. Tinti, E. Merella, and R. Combet, “A point-based system for local and remote exploration of dense 3d scanned models.” in VAST, 2009, pp. 25–32. http://dx.doi.org/10.2312/VAST/VAST09/025-032
E. Hubo and P. Bekaert, “A data distribution strategy for parallel point-based rendering,” 2005.
W. T. Corrêa, S. Fleishman, and C. T. Silva, “Towards point-based acquisition and rendering of large real-world environments,” in Computer Graphics and Image Processing, 2002. Proceedings. XV Brazilian Symposium on. IEEE, 2002, pp. 59–66. https://doi.org/10.1109/SIBGRA.2002.1167124
W. T. Corrêa, J. T. Klosowski, and C. T. Silva, “Out-of-core sort-first parallel rendering for cluster-based tiled displays,” Parallel Computing, vol. 29, no. 3, pp. 325–338, 2003. https://doi.org/10.1016/S0167-8191(02)00249-1
P. Goswami, M. Makhinya, J. Bösch, and R. Pajarola, “Scalable parallel out-of-core terrain rendering.” in EGPGV, 2010, pp. 63–71. https://doi.org/10.2312/egpgv/egpgv10/063-071
P. Goswami, F. Erol, R. Mukhi, R. Pajarola, and E. Gobbetti, “An efficient multi-resolution framework for high quality interactive rendering of massive point clouds using multi-way kd-trees,” The Visual Computer, vol. 29, no. 1, pp. 69–83, 2013. [Online]. Available: http://dx.doi.org/10.1007/s00371-012-0675-2
N. Lukac et al., “Hybrid visualization of sparse point-based data using gpgpu,” in Computing and Networking (CANDAR), 2014 Second International Symposium on. IEEE, 2014, pp. 178–184. https://doi.org/10.1109/CANDAR.2014.76
Z. Gao, L. Nocera, M. Wang, and U. Neumann, “Visualizing aerial lidar cities with hierarchical hybrid point-polygon structures,” in Proceedings of Graphics Interface 2014, ser. GI ’14. Toronto, Ont., Canada, Canada: Canadian Information Processing Society, 2014, pp. 137–144.
R. Richter, S. Discher, and J. Döllner, “Out-of-core visualization of classified 3d point clouds,” in 3D Geoinformation Science. Springer, 2015, pp. 227–242. https://doi.org/10.1007/978-3-319-12181-9_14
A. Febretti, K. Richmond, P. Doran, and A. Johnson, “Parallel processing and immersive visualization of sonar point clouds,” in Large Data Analysis and Visualization (LDAV), 2014 IEEE 4th Symposium on. IEEE, 2014, pp. 111–112. https://doi.org/10.1109/LDAV.2014.7013214
M. Potenziani, M. Callieri, M. Dellepiane, M. Corsini, F. Ponchio, and R. Scopigno, “3dhop: 3d heritage online presenter,” Computers & Graphics, vol. 52, pp. 129–141, 2015. https://doi.org/10.1016/j.cag.2015.07.001
R. Tredinnick, M. Broecker, and K. Ponto, “Experiencing interior environments: New approaches for the immersive display of large-scale point cloud data,” in Virtual Reality (VR), 2015 IEEE. IEEE, 2015, pp. 297–298. https://doi.org/10.1109/VR.2015.7223413
H. Okamoto and H. Masuda, “A point-based virtual reality system for supporting product development,” in ASME 2016 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2016, pp. V01BT02A052–V01BT02A052. https://doi.org/10.1115/DETC2016-59756
K. Ponto, R. Tredinnick, and G. Casper, “Simulating the experience of home environments,” in Virtual Rehabilitation (ICVR), 2017 International Conference on. IEEE, 2017, pp. 1–9. https://doi.org/10.1109/ICVR.2017.8007521
M. Schütz, “Potree: Rendering large point clouds in web browsers,” Technische Universität Wien, Wiedeń, 2016.
Publicado
28/10/2019
Como Citar
SILVA, Vinícius; MARROQUIM, Ricardo Guerra; ESPERANÇA, Claudio.
Concomitant Hierarchy Construction and Rendering of Large Point Clouds. In: WORKSHOP DE TESES E DISSERTAÇÕES - CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 32. , 2019, Rio de Janeiro.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 70-76.
DOI: https://doi.org/10.5753/sibgrapi.est.2019.8304.
