UCT CS Research Document Archive

Fast in-place binning of laser range-scanned point sets

Merry, Bruce, James Gain and Patrick Marais (2013) Fast in-place binning of laser range-scanned point sets. Journal on Computing and Cultural Heritage 6(3):14:1-14:19.

Full text available as:
PDF (Main document) - Requires Adobe Acrobat Reader or other PDF viewer.


Laser range scanning is commonly used in cultural heritage to create digital models of real-world artefacts. A large scanning campaign can produce billions of point samples — too many to be manipulated in memory on most computers. It is thus necessary to spatially partition the data so that it can be processed in bins or slices. We introduce a novel compression mechanism that exploits spatial coherence in the data to allow the bins to be computed with only 1.01 bytes of I/O traffic for each byte of input, compared to 2 or more for previous schemes. Additionally, the bins are loaded from the original files for processing rather than from a sorted copy, thus minimising disk space requirements. We demonstrate that our method yields performance improvements in a typical point-processing task, while also using little memory and guaranteeing an upper bound on the number of samples held in-core.

EPrint Type:Journal (Paginated)
Keywords:Binning, Point cloud, Octree, Out-of-core
Subjects:I Computing Methodologies: I.3 COMPUTER GRAPHICS
ID Code:852
Deposited By:Merry, Bruce
Deposited On:05 September 2013
Alternative Locations:http://doi.acm.org/10.1145/2499931.2499935