CGTools

 
Hardware
Mouses
Glasses
Data gloves
Head mounted displays
Acquisition
Printing

Data
Formats
  - 3D
  - Image
  - Vector
Meshes
Generation
  - Points
  - Edges
  - Meshes
Viewers
Modelisation
Reconstruction

Treatments
Denoising
Holes filling
Simplification
Subdivision
Compression
Convex hull
Clipper
Geometric texturing

Analysis
Differential Geometry
Geodesics
Segmentation
Normalization
Shape descriptors
Vectorization
Visibility
NPR
  - Stylised Lighting
  - Silhouettes and edges
  - Pen & ink, hatching,...
  - Volume illustration
Cutaways
Matching
Symmetry

Convex hull


Description

The 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

Programming
3D mesh libraries
Graphics libraries
Data structures
Partitioning
Quaternion
Pluecker
Triangulation

References
Library
Publications
Bookmark

News
OpenGL
Devmaster
Geeks3D
Web3d
oZone[3D].Net
3dvf

Mondes persistants
gamekult
jeuxvideo.fr
NoFrag
TDT 3D


Copyright CGTools 2008