masbcpp

masbcpp is a C++ implementation of the shrinking ball algorithm to approximate the Medial Axis Transform (MAT) of an oriented point cloud. It is being developed in support of the 3DSM project that aims to explore possible applications of the MAT for GIS point clouds (e.g. from airborne LiDAR). To deal with noisy input data a novel noise-handling mechanism is built-in.

See this video for a demonstration of the MAT of some LiDAR point clouds. And this video demonstrates how the shrinking ball algorithm works.

Installation

For Linux/OS X:

$ git clone https://github.com/tudelft3d/masbcpp.git
$ cd masbcpp
$ cmake .
$ make

For Windows:

1. Download and install PCL-1.8.1-AllInOne-msvc2015-win64.exe binary install package @ https://github.com/PointCloudLibrary/pcl/releases
2. Add C:\Program Files\PCL 1.8.1\bin in your Path of Environment variables
3. Open masbcpp\vs_build\masbcpp.sln using Visual Studio 2015
4. Build compute_ma, compute_normals, compute_simplify based on your needs

External dependencies

PCL is currently the only dependency that is not included in this distribution (but PCL has many dependencies of its own).

###Build with OpenMP support (multithreading) The build system should autodetect whether your compiler supports OpenMP and build masbpp with multithreading support accordingly. To enable multithreading on Mac OS X (tested with version 10.10), do

$ brew install clang-omp

prior to building masbcpp (assuming you have installed Homebrew).

Usage

See

$ ./compute_ma --help

and

$ ./compute_normals --help

and

$ ./simplify --help

Currently only NumPy binary files (.npy) are supported as input and output. Use pointio for reading and writing of .npy files and conversion from the ASPRS LAS format.

Limitations

The current implementation is not infinitely scalable, mainly in terms of memory usage. Processing very large datasets (hundreds of millions of points or more) is therefore not really supported.

Acknowledgements

The shinking ball algorithm was originally introduced by

@article{ma12,
  title={3D medial axis point approximation using nearest neighbors and the normal field},
  author={Ma, Jaehwan and Bae, Sang Won and Choi, Sunghee},
  journal={The Visual Computer},
  volume={28},
  number={1},
  pages={7--19},
  year={2012},
  publisher={Springer}
}

Details on how I adapted the shrinking ball algorithm to handle noisy inputs can be found in

@article{Peters16,
	author = {Peters, Ravi and Ledoux, Hugo},
	title = {Robust approximation of the {Medial Axis Transform} of {LiDAR} point clouds as a tool for visualisation},
	journal = {Computers \& Geosciences},
	year = {2016},
	volume = {90},
	number = {A},
	pages = {123--133},
	month = {mar}
}

I would like to thank the authors of the following libraries for releasing their code to the general public under permissive licenses, masbcpp ships with (parts of) these libraries: