EntBlog
Code, 3D, Games, Linux and much more...

StanHull

John Ratcliff have published a library to build convex hulls (the core implementation have been coded by Stan Melax). It is much better than QHull and really well packaged (1 cpp, 1 h) to be included in your toolbox of things-to-be-needed in the future.

Description from John, in the GDAlgorithms-List:

• Designed to be fast and robust. Rarely if ever fails.
• Allows a user to specify a maximum number of vertices to consider. Eliminates slivers and other problem area.
• Designed to produce hulls optimal for collision detection purposes, not necessarily for general computational geometry solutions.
• Supports ‘skin width’. This is a powerful feature that allows the hull to be extruded so that it has a user specified ‘thickness’ around the hull. This helps with physics engines which use penalty methods for penetration. It can be done on a per-shape basis, avoiding global settings for error tolerances.

The license of this code is free. Thanks to John and Stam.

If you don’t know, convex hulls are used in one of the most optimal algorithms for real time collision detection: GJK and derivates.