quickhull

by akuukka

akuukka / quickhull

C++ implementation of the 3D QuickHull algorithm

135 Stars 27 Forks Last release: Not found 100 Commits 0 Releases

Available items

No Items, yet!

The developer of this repository has not created any items for sale yet. Need a bug fixed? Help with integration? A different license? Create a request here:

This implementation is 100% Public Domain.

Feel free to use.

C++11 is needed to compile it.

Basic usage:

#include "quickhull/quickhull.hpp"

using namespace quickhull; QuickHull qh; // Could be double as well std::vector> pointCloud; // Add points to point cloud ... auto hull = qh.getConvexHull(pointCloud, true, false); const auto& indexBuffer = hull.getIndexBuffer(); const auto& vertexBuffer = hull.getVertexBuffer(); // Do what you want with the convex triangle mesh

Vertex data can be passed as a pointer to float/double as long as the data is in X0,Y0,Z0,X1,Y1,Z1,...,XN,YNZN format:

auto hull = qh.getConvexHull(&pointCloud[0].x, pointCloud.size(), true, false);

The first boolean parameter of getConvexHull specifies whether the resulting mesh should have its triangles in CCW orientation.

The second boolean parameter specifies whether the mesh should use vertex indices of the original point cloud. If it is false, a new vertex buffer is generated which consists only of those vertices that are part of the convex hull. In this case, the new vertex buffer is owned by the returned ConvexHull object. Otherwise, the original point cloud is used as vertex buffer and since the vertices are not copied, make sure you don't call ConvexHull::getVertexBuffer after releasing the memory that contains the original point cloud data.

This implementation is fast, because the convex hull is internally built using a half edge mesh representation which provides quick access to adjacent faces. It is also possible to get the output convex hull as a half edge mesh:

auto mesh = qh.getConvexHullAsMesh(&pointCloud[0].x, pointCloud.size(), true);

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.