C++ implementation of "Point Cloud Skeletons via Laplacian-Based Contraction"

What is in this repository?

This repository contains the C++ implementation of the point cloud skeletonization based on the Laplacian-based contraction [1]. In short, a point cloud is used as an input, a Laplacian operator is then built based on the concept of a one-ring neighbourhood. This operator is then used for contracting the point cloud. A skeleton is then built using farthest distance sampling with either a k-NN or a radius search.

Additionally, mesh skeletonization using the same method with the Laplacian defined on the mesh is also provided.

Dependencies

Standard dev tools

On Ubuntu, you need to install the following packages:

sudo apt-get update
sudo apt-get install git build-essential cmake libx11-dev mesa-common-dev libgl1-mesa-dev libglu1-mesa-dev libxrandr-dev libxi-dev libxmu-dev libblas-dev libxinerama-dev libxcursor-dev libeigen3-dev libyaml-cpp-dev python-matplotlib python-numpy python2.7-dev

Specific dependencies

The dependencies are specified for information only, however they should all be installed automatically.

1. Eigen (downloaded through sudo apt-get install)
2. yaml-cpp (downloaded through sudo apt-get install)
3. libGraphCpp (automatically download from the cmake file)
4. polyscope (downloaded as part of libGraphCpp)

Optional dependencies:

5. matplotlib-cpp

Installation instruction

To build, type into the console:

git clone https://github.com/rFalque/pointCloudSkeletonization.git
cd pointCloudSkeletonization
mkdir build
cd build
cmake ..
make -j3

Run the code

ℹ️ Info: The input files and the skeleton trimming method can be changed through the config.yaml file.

To run the sample, then just type:

./pointcloud_skeleton_extraction

todo

• add parallelization
• stop the contraction once the shrinking reach a certain stage, otherwise the skeleton diverges at some point

Differences with the original paper [1]

• Different implementation of the laplacian
• The nodes are generated using the farthest sampling algorithm (using either a sphere or k-NN to find neighbours). The k-NN sampling allows to have nodes generated with respect to the points density
• Several skeleton trimming is available depending of the required skeleton type

Link to the original papers

1. Point Cloud Skeletons via Laplacian-Based Contraction
2. Skeleton Extraction by Mesh Contraction

Other implementations

• Matlab implementation: https://github.com/ataiya/cloudcontr
• C++ implementation for triangular meshes: CGAL

Used in paper

@ARTICLE{8968326,
  author={Wu, Lan and Falque, Raphael and Perez-Puchalt, Victor and Liu, Liyang and Pietroni, Nico and Vidal-Calleja, Teresa},
  journal={IEEE Robotics and Automation Letters}, 
  title={Skeleton-Based Conditionally Independent Gaussian Process Implicit Surfaces for Fusion in Sparse to Dense 3D Reconstruction}, 
  year={2020},
  volume={5},
  number={2},
  pages={1532-1539},
  doi={10.1109/LRA.2020.2969175}}