ApproxMVBB

C++ Deps System

Status

Build UnitTests
Build Status Build Status

Homepage


Fast algorithms to compute an approximation of the minimal volume oriented bounding box of a point cloud in 3D.

Computing the minimal volume oriented bounding box for a given point cloud in 3D is a hard problem in computer science. Exact algorithms are known and of cubic order in the number of points in 3D. A faster exact algorithm is currently not know. However, for lots of applications an approximation of the minimum volume oriented bounding box is acceptable and already accurate enough. This project was developed for research in Granular Rigidbody Dynamics. This small standard compliant C++11 library can either be built into a shared object library or directly be included in an existing C++ project.

I am not especially proud of the underlying code as it was written years ago, nevertheless consider PR for refactoring and clean ups are very welcome!

This library includes code for :

  • computing an approximation of an oriented minimal volume box (multithreading support: OpenMP),
  • computing the convex hull of a point cloud in 2d,
  • computing the minimal area rectangle of a 2d point cloud,
  • 2d projections of point clouds,
  • fast building a kD-Tree (n-dimensional, templated) with sophisticated splitting techniques which optimizes a quality criteria during the splitting process,
  • computing the k-nearest neighbors to a given point (kNN search) via kd-Tree.
  • fast statistical outlier filtering of point clouds via (nearest neighbor search, kD-Tree).


Installation & Dependencies

To build the library, the tests and the example you need the build tool cmake. This library has these light-weight required dependencies:

  • Eigen at least version 3.
    • With homebrew or linuxbrew: brew install eigen3
  • meta
    • Install optional: Gets downloaded and used during build.

and theses optional dependecies:

  • pugixml
    • With homebrew or linuxbrew: brew install pugixml
    • install with #define PUGIXML_HAS_LONG_LONG enabled in pugiconfig.hpp.
    • only needed if cmake variable ApproxMVBB_XML_SUPPORT=ON (default=OFF).
  • python3 only needed for visualization purposes.

Download these and install it on your system.

Download the latest ApproxMVBB code:

    git clone https://github.com/gabyx/ApproxMVBB.git ApproxMVBB

Make a build directory and navigate to it:

    mkdir Build
    cd Build

Invoke cmake in the Build directory:

    cmake ../ApproxMVBB

The cmake script tries to find Eigen,meta and pugixml If you installed these in a system wide folder (e.g /usr/local/) this should succeed without any problems. In the CMakeCache.txt file (or over the console by -D<variable>=ON) you can specify what you want to build, the following options are availabe:

  • ApproxMVBB_BUILD_LIBRARY,
  • ApproxMVBB_BUILD_TESTS
  • ApproxMVBB_BUILD_EXAMPLE
  • ApproxMVBB_BUILD_BENCHMARKS
  • etc. See the marked red options after configuring in cmake-gui.

To install the library and the header files at a specific location /usr/local/ run cmake with:

    cmake -DCMAKE_INSTALL_PREFIX="/usr/local/" ../ApproxMVBB

Finally, build and install the project:

    make all
    make install

By default the multithreading support is enabled if OpenMP is found! (see Multithreading Support) To build in parallel use the -jN flag in the make command, where Ndenotes the number of parallel threads to use, or use the Ninja Generator which already uses maximum threads your system offers.

CMake FindScripts The installation installs also scripts approxmvbb-config.cmake and approxmvbb-config-version.cmake into the lib/cmake folder. To include the library in another project the only thing you need to add in your cmake script is

    find_package(ApproxMVBB [version] [COMPONENTS [SUPPORT_KDTREE] [SUPPORT_XML] ] [Required] )

which defines the following targets if ApproxMVBB has been found successfully:

    ApproxMVBB::Core            # Main target to link with!
    ApproxMVBB::KdTreeSupport   # Optional target for KdTree support to link with (only available if installed with this supported!)
    ApproxMVBB::XMLSupport      # Optional target for XML support to link with (only available if installed with this supported!)

The components SUPPORT_KDTREE additionally loads the dependency meta for the KdTree.hpp header and SUPPORT_XML loads pugixml for the KdTreeXml.hpp header.

If you installed the library into non-system generic location you can set the cmake variable $ApproxMVBB_DIR before invoking the find_library command:

    set(ApproxMVBB_DIR "path/to/installation/lib/cmake")
    find_package(ApproxMVBB [version] [Required] )

See the example example/libraryUsage which should be configured as a separate build, and the example example/kdTreeFiltering for more information on how to set up the dependencies!


Supported Platforms

The code has been tested on Linux and OS X with compilers clang and gcc. It should work for Windows as well, but has not been tested properly. Under Visual Studio 15 it seems to build.


Example Usage: Approximation MVBB

Please see the example/approxMVBB/main.cpp in the source directory. Given a point cloud with n=10000 points sampled in the unit cube in 3D we compute an approximation of the minimum volume bounding volume by the following calls:

<div class="highlight highlight-source-c++ position-relative overflow-auto" data-snippet-clipboard-copy-content=" #include
#include "ApproxMVBB/ComputeApproxMVBB.hpp"

int main(int argc, char** argv)
{
ApproxMVBB::Matrix3Dyn points(3,10000);
points.setRandom();
ApproxMVBB::OOBB oobb = ApproxMVBB::approximateMVBB(points,0.001,500,5,0,5);
oobb.expandToMinExtentRelative(0.1);
return 0;
}
“>

    #include <iostream>
    #include "ApproxMVBB/ComputeApproxMVBB.hpp"

    int  main(int argc, char** argv)
    {
          ApproxMVBB::Matrix3Dyn points(3,10000);
          points.setRandom();
          ApproxMVBB::OOBB oobb = ApproxMVBB::approximateMVBB(points,0.001,500,5,0,5);
          oobb.expandToMinExtentRelative(0.1);
          return 0;
    }