{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T12:38:29Z","timestamp":1775738309757,"version":"3.50.1"},"reference-count":39,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,2,4]],"date-time":"2021-02-04T00:00:00Z","timestamp":1612396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100014813","name":"Centre for Digital Entertainment","doi-asserted-by":"publisher","award":["EP\/L016540\/1"],"award-info":[{"award-number":["EP\/L016540\/1"]}],"id":[{"id":"10.13039\/501100014813","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Plymouth Marine Laboratory","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}]},{"name":"UKRI Block Grant fund","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Remote Sensing"],"abstract":"<jats:p>In this paper, we investigate the performance of six data structures for managing voxelised full-waveform airborne LiDAR data during 3D polygonal model creation. While full-waveform LiDAR data has been available for over a decade, extraction of peak points is the most widely used approach of interpreting them. The increased information stored within the waveform data makes interpretation and handling difficult. It is, therefore, important to research which data structures are more appropriate for storing and interpreting the data. In this paper, we investigate the performance of six data structures while voxelising and interpreting full-waveform LiDAR data for 3D polygonal model creation. The data structures are tested in terms of time efficiency and memory consumption during run-time and are the following: (1) 1D-Array that guarantees coherent memory allocation, (2) Voxel Hashing, which uses a hash table for storing the intensity values (3) Octree (4) Integral Volumes that allows finding the sum of any cuboid area in constant time, (5) Octree Max\/Min, which is an upgraded octree and (6) Integral Octree, which is proposed here and it is an attempt to combine the benefits of octrees and Integral Volumes. In this paper, it is shown that Integral Volumes is the more time efficient data structure but it requires the most memory allocation. Furthermore, 1D-Array and Integral Volumes require the allocation of coherent space in memory including the empty voxels, while Voxel Hashing and the octree related data structures do not require to allocate memory for empty voxels. These data structures, therefore, and as shown in the test conducted, allocate less memory. To sum up, there is a need to investigate how the LiDAR data are stored in memory. Each tested data structure has different benefits and downsides; therefore, each application should be examined individually.<\/jats:p>","DOI":"10.3390\/rs13040559","type":"journal-article","created":{"date-parts":[[2021,2,4]],"date-time":"2021-02-04T21:29:27Z","timestamp":1612474167000},"page":"559","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Comparative Study about Data Structures Used for Efficient Management of Voxelised Full-Waveform Airborne LiDAR Data during 3D Polygonal Model Creation"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4715-5048","authenticated-orcid":false,"given":"Milto","family":"Miltiadou","sequence":"first","affiliation":[{"name":"Centre for Digital Entertainment, Department of Computer Science, University of Bath, Bath BA2 7AY, UK"},{"name":"Remote Sensing Group, Plymouth Marine Laboratory, Plymouth PL1 3DH, UK"},{"name":"ERATOSTHENES Centre of Excellence, Department of Civil Engineering and Geomatics, Cyprus University of Technology, Lemesos 3036, Cyprus"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neill D. F.","family":"Campbell","sequence":"additional","affiliation":[{"name":"Centre for Digital Entertainment, Department of Computer Science, University of Bath, Bath BA2 7AY, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Darren","family":"Cosker","sequence":"additional","affiliation":[{"name":"Centre for Digital Entertainment, Department of Computer Science, University of Bath, Bath BA2 7AY, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael G.","family":"Grant","sequence":"additional","affiliation":[{"name":"Remote Sensing Group, Plymouth Marine Laboratory, Plymouth PL1 3DH, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,4]]},"reference":[{"key":"ref_1","first-page":"100","article-title":"From single-pulse to full-waveform airborne laser scanners","volume":"60","author":"Wanger","year":"2004","journal-title":"ISPRS J. Photogramm. Remote. Sens."},{"key":"ref_2","unstructured":"LAS Specification (2010). VERSION 1.3\u2014R11, The American Society for Photogrammetry and Remote Sensing."},{"key":"ref_3","unstructured":"Riegl (2012). Long-Range Airborne Laser Scanner for Full Waveform Analysis (LMS-Q680i), RIEGL Laser Measurement Systems GmbH."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Miltiadou, M., Agapiou, A., Gonzalez Aracil, S., and Hadjimitsis, D.G. (2020). Detecting Dead Standing Eucalypt Trees from Voxelised Full-Waveform Lidar Using Multi-Scale 3D-Windows for Tackling Height and Size Variations. Forests, 11.","DOI":"10.3390\/f11020161"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Zhou, T., Popescu, S., Malambo, L., Zhao, K., and Krause, K. (2018). From LiDAR waveforms to Hyper Point Clouds: A novel data product to characterize vegetation structure. Remote Sens., 10.","DOI":"10.20944\/preprints201811.0222.v1"},{"key":"ref_6","first-page":"135","article-title":"Detection of dead standing Eucalyptus camaldulensis without tree delineation for managing biodiversity in native Australian forest","volume":"67","author":"Miltiadou","year":"2018","journal-title":"Int. J. Appl. Earth Obs. Geoinf."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.isprsjprs.2005.12.001","article-title":"Gaussian decompositions and calibration of a novel small-footprint full-waveform digitising airborne laser scanner","volume":"60","author":"Wanger","year":"2006","journal-title":"ISPRS J. Photogramm. Remote. Sens."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.cageo.2013.01.010","article-title":"Sorted pulse data (SPD) library\u2014Part II: A processing framework for LiDAR data from pulsed laser systems in terrestrial environments","volume":"56","author":"Bunting","year":"2013","journal-title":"Comput. Geosci."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Chauve, A., Bretar, F., Durrieu, S., Pierrot-Deseilligny, M., and Puech, W. (2009, January 12\u201317). FullAnalyze: A research tool for handling, processing and analysing full-waveform LiDAR data. Proceedings of the IEEE International Geoscience and Remote Sensing Symposium, Cape Town, South Africa.","DOI":"10.1109\/IGARSS.2009.5417508"},{"key":"ref_10","unstructured":"Isenburg, M. (2012). PulseWaves: An Open, Vendor-Neutral, Stand-Alone, LAS-Compatible Full Waveform LiDAR Standard, rapidlasso GmbH."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Miltiadou, M., Michael, G., Campbell, N.D., Warren, M., Clewley, D., and Hadjimitsis, D.G. (2019, January 18\u201321). Open source software DASOS: Efficient accumulation, analysis, and visualisation of full-waveform lidar. Proceedings of the Seventh International Conference on Remote Sensing and Geoinformation of the Environment (RSCy2019), Paphos, Cyprus.","DOI":"10.1117\/12.2537915"},{"key":"ref_12","first-page":"103","article-title":"Visualisation and Analysis of full-waveform airborne laser scanner data","volume":"36","author":"Persson","year":"2005","journal-title":"Int. Arch. Photogramm. Remote. Sens. Spat. Inf. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1257","DOI":"10.5194\/isprsarchives-XL-7-W3-1257-2015","article-title":"Alignment of hyperspectral imagery and full-waveform LiDAR data for visualisation and classification purposes","volume":"40","author":"Miltiadou","year":"2015","journal-title":"Int. Arch. Photogramm. Remote. Sens. Spat. Inf. Sci. ISPRS Arch."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Hanrahan, P. (1983). Ray tracing algebraic surfaces. ACM SIGGRAPH Comput. Graph., 17.","DOI":"10.1145\/964967.801136"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1145\/37402.37422","article-title":"Marching cubes: A high resolution 3D surface construction algorithm","volume":"21","author":"Lorensen","year":"1987","journal-title":"ACM Siggraph Comput. Graph."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/38.511","article-title":"Display of surfaces from volume data","volume":"8","author":"Levoy","year":"1988","journal-title":"IEEE Comput. Graph. Appl."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Hadwiger, M., Beyer, J., Jeong, W.K., and Pfister, H. (2012). Interactive Volume Exploration of Patascale Microscopy Data Streams Using Visualizatin-Driven Virtual Memory Approach. IEEE Trans. Vis. Comput. Graph.","DOI":"10.1109\/TVCG.2012.240"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Crassin, C., Neyret, F., Lefebvre, S., and Eisemann, E. (March, January 27). GigaVoxels: Ray-Guided Streaming for Efficient and Detailed Voxel Rendering. Proceedings of the 2009 Symosium on Interactive 3D Graphics and Games, Boston, MA, USA.","DOI":"10.1145\/1507149.1507152"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1048","DOI":"10.1109\/TVCG.2010.240","article-title":"Efficient Sparse Voxel Octrees","volume":"17","author":"Laine","year":"2011","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"686","DOI":"10.1016\/j.cag.2005.08.027","article-title":"Adaptive polygonization of implicit surfaces","volume":"29","year":"2005","journal-title":"Sci. Direct Comput. Graph."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s003710050126","article-title":"A marching method for the triangulation of surfaces","volume":"14","author":"Hartmann","year":"1998","journal-title":"Vis. Comput."},{"key":"ref_22","unstructured":"Hansen, C.D., and Hinker, P. (1992, January 19\u201323). Massively Parallel Isosurface Extraction. Proceedings of the 3rd Conference on Visualization \u201992, Boston, MA, USA."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Galbraith, C., MacMurchy, P., and Wyvill, B. (2004). BlobTree Trees. IEEE Comput. Graph. Int., 78\u201385.","DOI":"10.1109\/CGI.2004.1309195"},{"key":"ref_24","unstructured":"Sutter, H., and Alexandrescu, A. (2004). C++ Coding Standards: 101 Rules, Guidlines, and Best Practices, Addison-Wesley."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"e0176871","DOI":"10.1371\/journal.pone.0176871","article-title":"3D Forest: An application for descriptions of three-dimensional forest structures using terrestrial LiDAR","volume":"12","author":"Trochta","year":"2017","journal-title":"PLoS ONE"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1007\/s00138-017-0845-3","article-title":"Urban 3D segmentation and modelling from street view images and LiDAR point clouds","volume":"28","author":"Babahajiani","year":"2017","journal-title":"Mach. Vis. Appl."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1109\/JSTARS.2017.2781132","article-title":"LiDAR point clouds to 3-D Urban Models: A review","volume":"11","author":"Wang","year":"2018","journal-title":"IEEE J. Sel. Top. Appl. Earth Obs. Remote. Sens."},{"key":"ref_28","unstructured":"Isenburg, M. (2012, October 09). LAStools\u2014Efficient Tools for LiDAR Processing. Available online: http:http:\/\/www.cs.unc.edu\/~{}isenburg\/lastools\/."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/j.rse.2015.07.027","article-title":"Comparison of small-footprint discrete return and full waveform airborne lidar data for estimating multiple forest variables","volume":"173","author":"Sumnall","year":"2016","journal-title":"Remote Sens. Environ."},{"key":"ref_30","unstructured":"Newton, A., Cantarello, E., Myers, G., Douglas, S.J., and Tejedor, N. (2010). The Condition and Dynamics of New Forest Woodlands, Pisces Publications."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Abd Latif, Z., and Blackburn, G.A. (2010, January 21\u201323). Extraction of gap and canopy properties using LiDAR and multispectral data for forest microclimate modelling. Proceedings of the IEEE 2010 6th International Colloquium on Signal Processing & Its Applications, Mallaca City, Malaysia.","DOI":"10.1109\/CSPA.2010.5545315"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1145\/357306.357310","article-title":"A Generalization of Algebraic Surface Drawing","volume":"1","author":"Blinn","year":"1982","journal-title":"ACM Trans. Graph. TOG"},{"key":"ref_33","first-page":"169","article-title":"Real-time 3d reconstruction at scale using voxel hashing","volume":"32","author":"Izadi","year":"2013","journal-title":"ACM Trans. Graph. TOG"},{"key":"ref_34","first-page":"5","article-title":"Lidar data segmentation and classification based on octree structure","volume":"1","author":"Wang","year":"2004","journal-title":"Parameters"},{"key":"ref_35","unstructured":"Miltiadou, M., Campbell, N.D., Brown, M., Cosker, D., and Grant, M.G. (2016). Improving and optimising visualisations of full-waveform LiDAR data. ACM Digit. Libr., 45\u201347."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1145\/964965.808600","article-title":"Summed-Area Tables for Texture Mapping","volume":"18","author":"Crow","year":"1984","journal-title":"ACM Comput. Graph."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1145\/99308.99321","article-title":"Octrees for faster isosurface generation","volume":"24","author":"Wilhelms","year":"1990","journal-title":"ACM SIGGRAPH Comput. Graph."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/S0895-6111(00)00084-7","article-title":"Growing-cube isosurface extraction algorithm for medical volume data","volume":"25","author":"Lee","year":"2001","journal-title":"Comput. Med Imaging Graph."},{"key":"ref_39","unstructured":"Zhao, Y., Wei, X., Fan, Z., Kaufman, A., and Qin, H. (2003, January 19\u201324). Voxels on fire [computer animation]. Proceedings of the IEEE Visualization, Seattle, WA, USA."}],"container-title":["Remote Sensing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2072-4292\/13\/4\/559\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:20:23Z","timestamp":1760160023000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2072-4292\/13\/4\/559"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,4]]},"references-count":39,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["rs13040559"],"URL":"https:\/\/doi.org\/10.3390\/rs13040559","relation":{},"ISSN":["2072-4292"],"issn-type":[{"value":"2072-4292","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,4]]}}}