Convex hull
DescriptionThe 3D convex hull of a set of points is the smallest subset
of the space where, for any two points u and v, the segment
joining these two points is in the subset. Several kind of algorithms computes
this subset (Incremental, QuickHull, Divide and Conquer,...)
The algorithm used there is based on the version proposed by O'Rourke in "Computational Geometry
in C" (Second Edition). The original source code can be found there. Nevertheless, this
version implements the incremental algorithm which is not the faster algorithm.
Moreover, the original version works with integers. Despite of its relative
efficiency, you'll find here a C++ version of this code for points with floating
coordinates.
For better results and more general implementation, you can use the CGAL (Computational Geometry Algorithms
Library). Details about the implemented algorithms can be found there.
Download
Results
Benchmark
3d model 
original model 
time 
convex hull 

# vertices 
# faces 

# vertices 
# faces 
Rabbit 
453 
902 
20ms 
90 
176 
Beethoven 
2521 
5030 
624ms 
164 
324 
Stanford's bunny 
35948 
69451 
286.493s 
1387 
2770 
Horse 
48485 
96966 
531.607s 
1885 
3764 
