Fast algorithms to compute an approximation of the minimal volume oriented bounding box of a point cloud in 3D.
Status
| Build | UnitTests | | ------------------------------------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------------------------------------- | | | |
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 :
To build the library, the tests and the example you need the build tool cmake. This library has these light-weight required dependencies:
brew install eigen3
and theses optional dependecies:
brew install pugixml
#define PUGIXML_HAS_LONG_LONGenabled in
pugiconfig.hpp.
ApproxMVBB_XML_SUPPORT=ON(default=
OFF).
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.txtfile (or over the console by
-D=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
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
-jNflag in the
makecommand, 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.cmakeand
approxmvbb-config-version.cmakeinto the
lib/cmakefolder. 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_KDTREEadditionally loads the dependency meta for the
KdTree.hppheader and
SUPPORT_XMLloads pugixml for the
KdTreeXml.hppheader.
If you installed the library into non-system generic location you can set the cmake variable
$ApproxMVBB_DIRbefore invoking the
find_librarycommand:
set(ApproxMVBB_DIR "path/to/installation/lib/cmake") find_package(ApproxMVBB [version] [Required] )
See the example
example/libraryUsagewhich should be configured as a separate build, and the example
example/kdTreeFilteringfor more information on how to set up the dependencies!
The code has been tested on Linux and OS X with compilers
clangand
gcc. It should work for Windows as well, but has not been tested properly. Under Visual Studio 15 it seems to build.
Please see the
example/approxMVBB/main.cppin the source directory. Given a point cloud with
n=10000points sampled in the unit cube in 3D we compute an approximation of the minimum volume bounding volume by the following calls:
#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; }
The returned object oriented bounding box
oobbcontains the lower
oobb.m_minPointand upper point
oobb.m_maxPointexpressed in the coordinate frame K of the bounding box. The bounding box also stores the rotation matrix from the world frame to the object frame K as a quaternion
oobb.m_q_KI. The rotation matrix
R_KIfrom frame I to frame K can be obtained by
oobb.m_q_KI.matrix()(see
Eigen::Quaternion). This rotation matrix
R_KIcorresponds to a coordinate transformation A_IK which transforms coordinates from frame K to coordinates in frame I. Thereforce, to get the lower point expressed in the coordinate frame I this yields:
ApproxMVBB::Vector3 p = oobb.m_q_KI * oobb.m_minPoint // A_IK * oobb.m_minPoint
Degenerate OOBB: The returned bounding box might have a degenerated extent in some axis directions depending on the input points (e.g. 3 points defines a plane which is the minimal oriented bounding box with zero volume). The function
oobb.expandToMinExtentRelative(0.1);is a post processing function to enlarge the bounding box by a certain percentage of the largest extent (if existing, otherwise a default value is used).
Points Outside of the final OOBB: Because the algorithm works internally with a sample of the point cloud, the resulting OOBB might not contain all points of the original point cloud! To compensate for this an additional loop is required:
ApproxMVBB::Matrix33 A_KI = oobb.m_q_KI.matrix().transpose(); auto size = points.cols(); for( unsigned int i=0; iFunction Parameters & How It Works: The most important function:
ApproxMVBB::approximateMVBB(pts, epsilon, pointSamples, gridSize, mvbbDiamOptLoops, mvbbGridSearchOptLoops)computes an approximation of the minimal volume bounding box in the following steps:
- An approximation of the diameter (direction which realizes the diameter:
z) of the pointsptsis computed. The valueepsilonis the absolute tolerance for the approximation of the diameter and has the same units as the pointspts(in the example 0.001 meter)- The points are projected into the plane perpendicular to the direction
z- An approximation of the diameter of the projected points in 2D is computed (direction
x)- The initial approximate bounding box
Ais computed in the orthogonal frame[x,y,z]- A first optional optimization loop is performed (parameter
mvbbDiamOptLoopsspecifies how many loops) by computing the minimal volume bounding box over a directiontwhere the directiontis choosen sequentially from the current optimal bounding box solution. The algorithm starts with the directions of the boxA. This optimization works with all points inptsand might use a lot of time- The initial bounding box
Ais used as a tight fit around the pointsptsto compute a representative sampleRSof the point cloud. The valuepointSamplesdefines how many points are used for the exhaustive grid search procedure in the next step- An exhaustive grid search (value
gridSizespecifies the x,y,z dimension of the grid defined by the bounding boxA) is performed. This search is a simple loop over all grid directions (see Gill Barequet, and Sariel Har-Peled [1]) to find a even smaller bounding box. For each grid directiongthe minimal bounding box of the projected points in directiongis computed. This consists of finding the minimal rectangle (axisuandvin world frame) of the projected point cloud in the plane perpendicular to directiong. The minimal bounding boxGin directiongcan be computed from the basis(u,v,g)and is a candidate for the overall minimization problem. Each found bounding box candidateGand its directions(u,v,g)can be used as a starting point for a second optional optimization loop (parametermvbbGridSearchOptLoops, same algorithm as in step 5 but with less points, namelyRS).- The final approximation for the minimal volume bounding box (minimal volume over all computed candidates) is returned. :poop:
Example Usage: Generating a KdTree and Outlier Filtering
The library includes a fast KdTree implementation (which is not claimed to be ultimativly fast and absolutely memory efficient, but was written to fulfill this aspects to a certain level, real benchmarks still need to be done, the implementation can really well compete with famous implementations such as PCL(FLANN),ANN, and CGAL ) The KdTree splitting heuristic implements an extendable sophisticated splitting optimization which in the most elaborate, performance worst case consists of searching for the best split between the splitting heuristics
MIDPOINT,MEDIANandGEOMETRIC_MEANby evaluating a user-provided quality evaluator. The simple standard quality evaluator is theLinearQualityEvaluatorwhich computes the split quality by a weighted linear combination of the quantitiessplitRatio,pointRatio,minMaxExtentRatio.Outlier filtering is done with the k-nearest neighbor search algorithm (similar to the PCL library but faster, and with user defined precision) and works roughly as the following: The algorithm finds for each point
pin the point cloudknearest neighbors and averages their distance (distance functor) to the pointpto obtain a mean distancedistancefor this particular point. All nearest mean distances for all points give a histogram with a sample meanmeanand sample standard deviationstdDev. All points which have a mean nearest neighbor distance greater or equal tomean + stdDevMult * stdDevare classified as outlier points.Look at the examples in
examples/kdTreeFilteringwhich produced the following pictures with the provided visualization notebookexamples/kdTreeFiltering/python/VisualizeKdTree.ipynb.Function Parameters & How It Works To come
Building and Visualizing the Tests
Building and installing the basic tests is done by:
cd ApproxMVBB git submodule init git submodule update cd ../Build make build_and_test*Note that if the tests fail, submit a new issue and report which test failed. The results can still be visualized and should be correct. *
Note: To run the test in high-performance mode (needs lots of ram), which tests also points clouds of 140 million points and some polygonal statue
lucy.txtsuccessfully you need to set the cmake variableApproxMVBB_TESTS_HIGH_PERFORMANCEtoONand additionally initialize the submoduleadditionaland unzip the files:cd ApproxMVBB git submodule init git submodule update cd additional/tests/files; cat Lucy* | tar xzand rebuild the tests. (this will copy the additional files next to the executable)
Executing the test application
cd tests; ./ApproxMVBBTestswill then run the following tests:
- Testing the ConvexHull2D for several point clouds in 2D
- Minimal area rectangle tests for several point clouds in 2D
- Testing the diameter computation and calculation of the initial bounding box
A(see section) for point clouds in 3D- Testing the full optimization pipeline to generate an approximation of the minimal volume bounding box
The output can be visualized with the
ipython notebook/tests/python/PlotTestResults.ipynb:cd Build/tests ipython noteboook
Benchmark
Here are some short benchmarks (single core) from the tests folder:
| Point Cloud | # Points | ~ CPU Time
approximateMVBB| | --------------- | ----------: | ---------------------------: | | Standford Bunny | 35'945 | 0.91 s | | Standford Lucy | 14'027'872 | 1.19 s | | Unit Cube | 140'000'000 | 7.0 s |approximateMVBBrunsapproximateMVBBDiamand performs a grid search afterwards (here 5x5x5=25 directions with 5 optimization runs for each) It seems to take a long time for 140 million points. The most inefficient task is to get a good initial bounding box. This takes the most time as diameter computations are performed in 3d and then all points are projected in the found diameter direction in 3d and another diameter in the projected plane in 2d is computed. Afterwards the point cloud is sampled (not just random points, its done with a grid) and convex hull, minimal rectangle computations are performed over the grid directions. These algorithms could be made faster by exploiting the following things:
You can build the library with OpenMP (by default enabled) You can set the cmake cache variables
ApproxMVBB_OPENMP_USE_OPENMP=Onwhich will further enable
ApproxMVBB_OPENMP_USE_NTHREADS=On/Off. The variable
ApproxMVBB_OPENMP_USE_NTHREADStoogles the number of threads to use. If
Off, the number of threads is determined at runtime (default).
If you use clang, make sure you have the OpenMP enabled clang! GCC already supports OpenMP.
The main articles this code is based on:
@Article{malandain2002, Author = {Gr'egoire Malandain and Jean-Daniel Boissonnat}, Journal = {International Journal of Computational Geometry & Applications}, Month = {December}, Number = {6}, Pages = {489 - 510}, Timestamp = {2015.09.02}, Title = {Computing the Diameter of a Point Set}, Volume = {12}, Year = {2002}}
and
@inproceedings{barequet2001, Author = {Gill Barequet and Sariel Har-peled}, Booktitle = {In Proc. 10th ACM-SIAM Sympos. Discrete Algorithms}, Pages = {38--91}, Timestamp = {2015.09.02}, Title = {Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions}, Year = {2001}}
Optimizations for future work:
@Article{chang2011, Acmid = {2019641}, Address = {New York, NY, USA}, Articleno = {122}, Author = {Chang, Chia-Tche and Gorissen, Bastien and Melchior, Samuel}, Doi = {10.1145/2019627.2019641}, Issn = {0730-0301}, Issue_Date = {October 2011}, Journal = {ACM Trans. Graph.}, Keywords = {Computational geometry, bounding box, manifolds, optimization}, Month = oct, Number = {5}, Numpages = {16}, Pages = {122:1--122:16}, Publisher = {ACM}, Timestamp = {2015.09.03}, Title = {Fast Oriented Bounding Box Optimization on the Rotation Group {$SO(3,\mathbb{R})$}}, Url = {http://doi.acm.org/10.1145/2019627.2019641}, Volume = {30}, Year = {2011}, Bdsk-Url-1 = {http://doi.acm.org/10.1145/2019627.2019641}, Bdsk-Url-2 = {http://dx.doi.org/10.1145/2019627.2019641}}
This source code is released under MPL 2.0.
ApproxMVBB was written by Gabriel Nützi, with source code from Grégoire Malandain & Jean-Daniel Boissonnat for the approximation of the diameter of a point cloud. I was inspired by the work and algorithms of Gill Barequet & Sariel Har-Peled for computing a minimal volume bounding box. Additionally, the geometric predicates (orient2d) used in the convex hull algorithm (graham scan) have been taken from the fine work of Jonathan Richard Shewchuk. Special thanks go to my significant other which always had an ear during breakfast for this little project :kissing_heart: