OMiCroN - Oblique Multipass Hierarchy Creation while Navigating
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. This problem has been addressed in the past by incremental construction approaches, but these either result in low quality hierarchies or in longer construction times. 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. OMiCroN is fast, being capable of building the entire data structure in memory spending an amount of time that is comparable to that of just reading the cloud from disk. Thus, there is no need for storing an expensive hierarchy, nor for delaying the rendering until the whole hierarchy is read from disk. 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.
Palavras-chave:
Graphics data structures, Object hierarchies, Viewing algorithms, Computational Geometry, Computer Graphics
Referências
S. Rusinkiewicz, M. Levoy Qsplat: a multiresolution point rendering system for large meshes. Proceedings of the 27th annual conference on computer graphics and interactive techniques, SIGGRAPH’00, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA (2000), pp. 343-352, 10.1145/344779.344940. https://doi.org/10.1145/344779.344940. ISBN 1-58113-208-5.
M. Wimmer, C. Scheiblauer. Instant points: fast rendering of unprocessed point clouds. Proceedings of the 3rd Eurographics / IEEE VGTC conference on point-based graphics, SPBG’06, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland (2006), pp. 129-137, 10.2312/SPBG/SPBG06/129-136. https://doi.org/10.2312/SPBG/SPBG06/129-136. ISBN 3-905673-32-0.
J. Klein, G. Zachmann. Point cloud collision detection. Comput Graph Forum Wiley Online Library, 23 (2004), pp. 567-576.
C. Ericson. Real-time collision detection, CRC Press, Inc., Boca Raton, FL, USA (2004). ISBN 1558607323, 9781558607323.
J. Bittner, M. Hapala, V. Havran. Incremental BVH construction for ray tracing. Comput Graph, 47 (2015), pp. 135-144
Morton. A computer oriented geodetic data base and a new technique in file sequencing. Tech. Rep., IBM Ltd., Ottawa, Ontario, Canada (1966)
J.T. Klosowski, M. Held, J.S.B. Mitchell, H. Sowizral, K. Zikan. Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Trans Vis Comput Graph, 4 (1) (1998), pp. 21-36, 10.1109/2945.675649
S.A. Ehmann, M.C. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Comput Graph Forum, 20 (3) (2001), pp. 500-511
C. Lauterbach, Q. Mo, D. Manocha. gproximity: hierarchical GPU-based operations for collision and distance queries. Comput Graph Forum, 29 (2) (2010), pp. 419-428
O. Argudo, I. Besora, P. Brunet, C. Creus, P. Hermosilla, I. Navazo, A. Vinacua. Interactive inspection of complex multi-object industrial assemblies. Comput Aided Des, 79 (2016), pp. 48-59, 10.1016/j.cad.2016.06.005
M. Levoy, T. Whitted. The use of points as a display primitive, University of North Carolina, Department of Computer Science, Chapel Hill, NC, USA (1985)
J.P. Grossman, W.J. Dally. Point sample rendering. Drettakis G., Max N. (Eds.), Rendering techniques ’98, Springer, Vienna (1998), pp. 181-192. ISBN 978-3-7091-6453-2.
M. Sainz, R. Pajarola. Point-based rendering techniques. Comput Graph, 28 (6) (2004), pp. 869-879
L. Kobbelt, M. Botsch. A survey of point-based techniques in computer graphics. Comput Graph, 28 (6) (2004), pp. 801-814
M. Alexa, M. Gross, M. Pauly, H. Pfister, M. Stamminger, M. Zwicker. Point-based computer graphics. Proceedings of the ACM SIGGRAPH. Course Notes, ACM (2004), p. 7
M. Gross. Getting to the point...? IEEE Comput Graph Appls, 26 (5) (2006), pp. 96-99
M. Gross, H. Pfister. Point-based graphics, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2011)
ISBN 0123706041, 9780080548821.
F. Ramos, J. Huerta, F. Benitez. Characterization of multiresolution models for real-time rendering in GPU-limited environments. Proceedings of the international conference on articulated motion and deformable objects, Springer (2016), pp. 157-167
C. Dachsbacher, C. Vogelgsang, M. Stamminger. Sequential point trees. ACM Trans Graph (TOG), 22 (2003), pp. 657-662
R. Pajarola, M. Sainz, R. Lario. Xsplat: external memory multiresolution point visualization. Proceedings of the IASTED international conference on visualization, imaging and image processing (2005), pp. 628-633
E. Gobbetti, F. Marton. Layered point clouds: a simple and efficient multiresolution structure for distributing and rendering gigantic point-sampled models. Comput Graph, 28 (6) (2004), pp. 815-826, 10.1016/j.cag.2004.08.010
M. Wand, A. Berner, M. Bokeloh, A. Fleck, M. Hoffmann, P. Jenke, B. Maier, D. Staneker, A. Schilling. Interactive editing of large point clouds. Proceedings of the SPBG (2007), pp. 37-45
F. Bettio, E. Gobbetti, F. Marton, A. Tinti, E. Merella, R. Combet. A point-based system for local and remote exploration of dense 3d scanned models. Proceedings of the VAST (2009), pp. 25-32
Hubo E., Bekaert P.. A data distribution strategy for parallel point-based rendering. 2005,.
W.T. Corrêa, S. Fleishman, C.T. Silva. Towards point-based acquisition and rendering of large real-world environments. Proceedings of the XV Brazilian symposium on computer graphics and image processing, IEEE (2002), pp. 59-66
W.T. Corrêa, J.T. Klosowski, C.T. Silva. Out-of-core sort-first parallel rendering for cluster-based tiled displays
Parallel Comput, 29 (3) (2003), pp. 325-338
P. Goswami, M. Makhinya, J. Bösch, R. Pajarola. Scalable parallel out-of-core terrain rendering. Proceedings of the EGPGV (2010), pp. 63-71
P. Goswami, F. Erol, R. Mukhi, R. Pajarola, E. Gobbetti. An efficient multi-resolution framework for high quality interactive rendering of massive point clouds using multi-way kd-trees. Vis Comput, 29 (1) (2013), pp. 69-83, 10.1007/s00371-012-0675-2
N. Lukac, et al. Hybrid visualization of sparse point-based data using GPGPU. Proceedings of the second international symposium on computing and networking (CANDAR), IEEE (2014), pp. 178-184
Z. Gao, L. Nocera, M. Wang, U. Neumann. Visualizing aerial liDAR cities with hierarchical hybrid point-polygon structures. Proceedings of the graphics interface, GI ’14, Canadian Information Processing Society. ISBN 978-1-4822-6003-8, Toronto, Ont., Canada (2014), pp. 137-144. http://dl-acm-org.ez29.capes.proxy.ufrj.br/citation.cfm?id=2619648.2619672.
R. Richter, S. Discher, J. Döllner. Out-of-core visualization of classified 3d point clouds. 3D geoinformation science, Springer (2015), pp. 227-242
A. Febretti, K. Richmond, P. Doran, A. Johnson. Parallel processing and immersive visualization of sonar point clouds. Proceedings of the 4th IEEE symposium on large data analysis and visualization (LDAV), IEEE (2014), pp. 111-112
M. Potenziani, M. Callieri, M. Dellepiane, M. Corsini, F. Ponchio, R. Scopigno. 3DHOP: 3D heritage online presenter
Comput Graph, 52 (2015), pp. 129-141
R. Tredinnick, M. Broecker, K. Ponto. Experiencing interior environments: New approaches for the immersive display of large-scale point cloud data. Proceedings of the IEEE virtual reality (VR), IEEE (2015), pp. 297-298
H. Okamoto, H. Masuda. A point-based virtual reality system for supporting product development. Proceedings of the ASME international design engineering technical conferences and computers and information in engineering conference, American Society of Mechanical Engineers (2016)
K. Ponto, R. Tredinnick, G. Casper. Simulating the experience of home environments. Proceedings of the international conference on virtual rehabilitation (ICVR), IEEE (2017), pp. 1-9
T. Karras. Maximizing parallelism in the construction of BVHs, octrees, and k-d trees. Proceedings of the fourth ACM SIGGRAPH/Eurographics conference on high-performance graphics, Eurographics Association (2012), pp. 33-37
M. Zwicker, H. Pfister, J. van Baar, M. Gross. Surface splatting. Proceedings of the 28th annual conference on computer graphics and interactive techniques, SIGGRAPH ’01, ACM, New York, NY, USA (2001), pp. 371-378, 10.1145/383259.383300. http://doi.acm.org/10.1145/383259.383300. ISBN 1-58113-374-X.
M. Zwicker, J. Räsänen, M. Botsch, C. Dachsbacher, M. Pauly. Perspective accurate splatting. Proceedings of graphics interface, GI ’04, School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada (2004), pp. 247-254. http://dl.acm.org/citation.cfm?id=1006058.1006088. Canadian Human-Computer Communications Society. ISBN 1-56881-227-2
M. Botsch, M. Spernat, L. Kobbelt. Phong splatting. Proceedings of the first Eurographics conference on point-based graphics, SPBG’04, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland (2004), pp. 25-32, 10.2312/SPBG/SPBG04/025-032. https://doi.org/10.2312/SPBG/SPBG04/025-032. ISBN 3-905673-09-6.
T. Weyrich, S. Heinzle, T. Aila, D.B. Fasnacht, S. Oetiker, M. Botsch, C. Flaig, S. Mall, K. Rohrer, N. Felber, H. Kaeslin, M. Gross. A hardware architecture for surface splatting. Proceedings of the ACM SIGGRAPH Papers, SIGGRAPH ’07, ACM, New York, NY, USA (2007), 10.1145/1275808.1276490. http://doi.acm.org/10.1145/1275808.1276490.
M. Schütz. Potree: rendering large point clouds in web browsers, Technische Universität Wien, Wiedeń (2016)
J. Baert, A. Lagae, P. Dutré. Out-of-core construction of sparse voxel octrees. Comput Graph Forum, 33 (6) (2014), pp. 220-227, 10.1111/cgf.12345
J. Wu, Z. Zhang, L. Kobbelt. Progressive splatting. Proceedings of the Eurographics/IEEE VGTC symposium point-based graphics (2005), pp. 25-142, 10.1109/PBG.2005.194060
M. Wimmer, C. Scheiblauer. Instant points: fast rendering of unprocessed point clouds. Proceedings of the 3rd Eurographics / IEEE VGTC conference on point-based graphics, SPBG’06, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland (2006), pp. 129-137, 10.2312/SPBG/SPBG06/129-136. https://doi.org/10.2312/SPBG/SPBG06/129-136. ISBN 3-905673-32-0.
J. Klein, G. Zachmann. Point cloud collision detection. Comput Graph Forum Wiley Online Library, 23 (2004), pp. 567-576.
C. Ericson. Real-time collision detection, CRC Press, Inc., Boca Raton, FL, USA (2004). ISBN 1558607323, 9781558607323.
J. Bittner, M. Hapala, V. Havran. Incremental BVH construction for ray tracing. Comput Graph, 47 (2015), pp. 135-144
Morton. A computer oriented geodetic data base and a new technique in file sequencing. Tech. Rep., IBM Ltd., Ottawa, Ontario, Canada (1966)
J.T. Klosowski, M. Held, J.S.B. Mitchell, H. Sowizral, K. Zikan. Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Trans Vis Comput Graph, 4 (1) (1998), pp. 21-36, 10.1109/2945.675649
S.A. Ehmann, M.C. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Comput Graph Forum, 20 (3) (2001), pp. 500-511
C. Lauterbach, Q. Mo, D. Manocha. gproximity: hierarchical GPU-based operations for collision and distance queries. Comput Graph Forum, 29 (2) (2010), pp. 419-428
O. Argudo, I. Besora, P. Brunet, C. Creus, P. Hermosilla, I. Navazo, A. Vinacua. Interactive inspection of complex multi-object industrial assemblies. Comput Aided Des, 79 (2016), pp. 48-59, 10.1016/j.cad.2016.06.005
M. Levoy, T. Whitted. The use of points as a display primitive, University of North Carolina, Department of Computer Science, Chapel Hill, NC, USA (1985)
J.P. Grossman, W.J. Dally. Point sample rendering. Drettakis G., Max N. (Eds.), Rendering techniques ’98, Springer, Vienna (1998), pp. 181-192. ISBN 978-3-7091-6453-2.
M. Sainz, R. Pajarola. Point-based rendering techniques. Comput Graph, 28 (6) (2004), pp. 869-879
L. Kobbelt, M. Botsch. A survey of point-based techniques in computer graphics. Comput Graph, 28 (6) (2004), pp. 801-814
M. Alexa, M. Gross, M. Pauly, H. Pfister, M. Stamminger, M. Zwicker. Point-based computer graphics. Proceedings of the ACM SIGGRAPH. Course Notes, ACM (2004), p. 7
M. Gross. Getting to the point...? IEEE Comput Graph Appls, 26 (5) (2006), pp. 96-99
M. Gross, H. Pfister. Point-based graphics, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2011)
ISBN 0123706041, 9780080548821.
F. Ramos, J. Huerta, F. Benitez. Characterization of multiresolution models for real-time rendering in GPU-limited environments. Proceedings of the international conference on articulated motion and deformable objects, Springer (2016), pp. 157-167
C. Dachsbacher, C. Vogelgsang, M. Stamminger. Sequential point trees. ACM Trans Graph (TOG), 22 (2003), pp. 657-662
R. Pajarola, M. Sainz, R. Lario. Xsplat: external memory multiresolution point visualization. Proceedings of the IASTED international conference on visualization, imaging and image processing (2005), pp. 628-633
E. Gobbetti, F. Marton. Layered point clouds: a simple and efficient multiresolution structure for distributing and rendering gigantic point-sampled models. Comput Graph, 28 (6) (2004), pp. 815-826, 10.1016/j.cag.2004.08.010
M. Wand, A. Berner, M. Bokeloh, A. Fleck, M. Hoffmann, P. Jenke, B. Maier, D. Staneker, A. Schilling. Interactive editing of large point clouds. Proceedings of the SPBG (2007), pp. 37-45
F. Bettio, E. Gobbetti, F. Marton, A. Tinti, E. Merella, R. Combet. A point-based system for local and remote exploration of dense 3d scanned models. Proceedings of the VAST (2009), pp. 25-32
Hubo E., Bekaert P.. A data distribution strategy for parallel point-based rendering. 2005,.
W.T. Corrêa, S. Fleishman, C.T. Silva. Towards point-based acquisition and rendering of large real-world environments. Proceedings of the XV Brazilian symposium on computer graphics and image processing, IEEE (2002), pp. 59-66
W.T. Corrêa, J.T. Klosowski, C.T. Silva. Out-of-core sort-first parallel rendering for cluster-based tiled displays
Parallel Comput, 29 (3) (2003), pp. 325-338
P. Goswami, M. Makhinya, J. Bösch, R. Pajarola. Scalable parallel out-of-core terrain rendering. Proceedings of the EGPGV (2010), pp. 63-71
P. Goswami, F. Erol, R. Mukhi, R. Pajarola, E. Gobbetti. An efficient multi-resolution framework for high quality interactive rendering of massive point clouds using multi-way kd-trees. Vis Comput, 29 (1) (2013), pp. 69-83, 10.1007/s00371-012-0675-2
N. Lukac, et al. Hybrid visualization of sparse point-based data using GPGPU. Proceedings of the second international symposium on computing and networking (CANDAR), IEEE (2014), pp. 178-184
Z. Gao, L. Nocera, M. Wang, U. Neumann. Visualizing aerial liDAR cities with hierarchical hybrid point-polygon structures. Proceedings of the graphics interface, GI ’14, Canadian Information Processing Society. ISBN 978-1-4822-6003-8, Toronto, Ont., Canada (2014), pp. 137-144. http://dl-acm-org.ez29.capes.proxy.ufrj.br/citation.cfm?id=2619648.2619672.
R. Richter, S. Discher, J. Döllner. Out-of-core visualization of classified 3d point clouds. 3D geoinformation science, Springer (2015), pp. 227-242
A. Febretti, K. Richmond, P. Doran, A. Johnson. Parallel processing and immersive visualization of sonar point clouds. Proceedings of the 4th IEEE symposium on large data analysis and visualization (LDAV), IEEE (2014), pp. 111-112
M. Potenziani, M. Callieri, M. Dellepiane, M. Corsini, F. Ponchio, R. Scopigno. 3DHOP: 3D heritage online presenter
Comput Graph, 52 (2015), pp. 129-141
R. Tredinnick, M. Broecker, K. Ponto. Experiencing interior environments: New approaches for the immersive display of large-scale point cloud data. Proceedings of the IEEE virtual reality (VR), IEEE (2015), pp. 297-298
H. Okamoto, H. Masuda. A point-based virtual reality system for supporting product development. Proceedings of the ASME international design engineering technical conferences and computers and information in engineering conference, American Society of Mechanical Engineers (2016)
K. Ponto, R. Tredinnick, G. Casper. Simulating the experience of home environments. Proceedings of the international conference on virtual rehabilitation (ICVR), IEEE (2017), pp. 1-9
T. Karras. Maximizing parallelism in the construction of BVHs, octrees, and k-d trees. Proceedings of the fourth ACM SIGGRAPH/Eurographics conference on high-performance graphics, Eurographics Association (2012), pp. 33-37
M. Zwicker, H. Pfister, J. van Baar, M. Gross. Surface splatting. Proceedings of the 28th annual conference on computer graphics and interactive techniques, SIGGRAPH ’01, ACM, New York, NY, USA (2001), pp. 371-378, 10.1145/383259.383300. http://doi.acm.org/10.1145/383259.383300. ISBN 1-58113-374-X.
M. Zwicker, J. Räsänen, M. Botsch, C. Dachsbacher, M. Pauly. Perspective accurate splatting. Proceedings of graphics interface, GI ’04, School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada (2004), pp. 247-254. http://dl.acm.org/citation.cfm?id=1006058.1006088. Canadian Human-Computer Communications Society. ISBN 1-56881-227-2
M. Botsch, M. Spernat, L. Kobbelt. Phong splatting. Proceedings of the first Eurographics conference on point-based graphics, SPBG’04, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland (2004), pp. 25-32, 10.2312/SPBG/SPBG04/025-032. https://doi.org/10.2312/SPBG/SPBG04/025-032. ISBN 3-905673-09-6.
T. Weyrich, S. Heinzle, T. Aila, D.B. Fasnacht, S. Oetiker, M. Botsch, C. Flaig, S. Mall, K. Rohrer, N. Felber, H. Kaeslin, M. Gross. A hardware architecture for surface splatting. Proceedings of the ACM SIGGRAPH Papers, SIGGRAPH ’07, ACM, New York, NY, USA (2007), 10.1145/1275808.1276490. http://doi.acm.org/10.1145/1275808.1276490.
M. Schütz. Potree: rendering large point clouds in web browsers, Technische Universität Wien, Wiedeń (2016)
J. Baert, A. Lagae, P. Dutré. Out-of-core construction of sparse voxel octrees. Comput Graph Forum, 33 (6) (2014), pp. 220-227, 10.1111/cgf.12345
J. Wu, Z. Zhang, L. Kobbelt. Progressive splatting. Proceedings of the Eurographics/IEEE VGTC symposium point-based graphics (2005), pp. 25-142, 10.1109/PBG.2005.194060
Publicado
28/10/2019
Como Citar
DA SILVA, Vinícius; MARROQUIM, Ricardo; ESPERANÇA, Claudio.
OMiCroN - Oblique Multipass Hierarchy Creation while Navigating. In: CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 32. , 2019, Rio de Janeiro.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
DOI: https://doi.org/10.5753/sibgrapi.2019.9810.
