StanHull convex hull generation
Posted: Mon Mar 06, 2006 5:23 pm
from gdalgorithms:
About a year and half ago I posted a thread here (gdalgorithms list) about my difficulties getting a reliable convex hull generator. I ended up posting an outrageous hack that involved putting a wrapper around the huge pile of mess that is called ?Qhull?. The reason I am posting a message today is because I keep getting requests for that old build, called ?QhullLib?, from people searching the archives. The thing is that implementation was really stupid and I have been using something much better for some time.
Stan Melax, who is a bit of a genius at computational geometry, developed a dramatically improved convex hull generation algorithm. It is extremely fast (real-time fast), stable, and targeted specifically at the needs of game developers. I have chosen to name his hull generation code ?StanHull?.
You might wonder why I am posting some of Stan?s code. Well, the explanation for that is a bit complicated but I will try to give the very quick version. Again, about a year a half ago, I was working on a project I called the ?Open Dynamics Framework?, which was supposed to be an API and data model for rigid body physics that would work with any piece of physics middleware. I even made a presentation at the GameTech conference and was working with a consortium to standardize the data model. I started up a website and made a couple of releases, both 100% open source.
Then life happened. I was told to work on other stuff and that project just died. Since I work for a hardware company I was able to convince my employer that everything I do for them should be open-source. I am quite proud of this fact and I hope to make more code available in this way. My friend and colleague Stan Melax improved our hull generation code but we never released to the public.
I will have to let Stan talk for himself about the algorithm he used in his implementation. My primary contribution was packaging of the source code and doing some pre and post-processing cleanup.
First, packaging. The hull generation code is provided as one CPP and one H. Stan?s code was dependent on a vector library and a couple of template classes. These are embedded in the CPP so they are hidden from the user of the library. You can also put the whole thing in a namespace if that helps.
Here are the key features of Stan?s hull generation code:
? 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.
Here are the features of my wrapper around Stan?s hull code:
? Pre-processes the input point cloud by converting it to a unit-normal cube. Duplicate vertices are removed based on a normalized tolerance level (i.e. 0.1 means collapse vertices within 1/10th the width/breadth/depth of any side. This is extremely useful in eliminating slivers. When cleaning up ?duplicates and/or nearby neighbors? it also keeps the one which is ?furthest away? from the centroid of the volume.
? Outputs the convex hull as triangles or faces depending on a user setting.
? Outputs the faces in either winding order based on a user setting.
? Cleans up dead vertices generated. If you pass say 1,000 vertices into a hull generator, you might only get say 100 out. The hull generated will provide indices to the original 1,000 vertices however. The routine ?BringOutYourDead? will re-index the hull so that it only contains the 100 vertices which are actually used.
This new version of the library is completely open source. It comes with a small console application that loads a Wavefront .OBJ file, generates a hull, and then writes out the generated hull as another Wavefront OBJ. The console application accepts a few command line switches to control various parameters.
The single .CPP is about 3,000 lines of code; mostly because of the embedded template classes. The header file and implementation example are both very small.
My original ?Open Dynamics Framework? project is pretty much dead. The project continues on under a different name, and is still open source (so long as I can keep it that way). However, it got subsumed into my company and is being developed by other programmers than myself.
I hope you will indulge this post. I am only doing so because the original library was posted here and I continue to get so many requests for it.
Since I have gathered a large collection of open-source material in the past couple of years, I plan to start posting it in bite-sized pieces on a website I just set up today. My first post today contains ?StanHull?. If you have any questions about the code, in terms of how to use it, build it, or about the pre-processing phase, then contact me. If you have specific questions about the hull generation code and algorithm you will need to contact Stan Melax (melax@ageia.com).
You can find the StanHull.zip file at my new code website: http://www.codesuppository.blogspot.com/
Thanks,
John
About a year and half ago I posted a thread here (gdalgorithms list) about my difficulties getting a reliable convex hull generator. I ended up posting an outrageous hack that involved putting a wrapper around the huge pile of mess that is called ?Qhull?. The reason I am posting a message today is because I keep getting requests for that old build, called ?QhullLib?, from people searching the archives. The thing is that implementation was really stupid and I have been using something much better for some time.
Stan Melax, who is a bit of a genius at computational geometry, developed a dramatically improved convex hull generation algorithm. It is extremely fast (real-time fast), stable, and targeted specifically at the needs of game developers. I have chosen to name his hull generation code ?StanHull?.
You might wonder why I am posting some of Stan?s code. Well, the explanation for that is a bit complicated but I will try to give the very quick version. Again, about a year a half ago, I was working on a project I called the ?Open Dynamics Framework?, which was supposed to be an API and data model for rigid body physics that would work with any piece of physics middleware. I even made a presentation at the GameTech conference and was working with a consortium to standardize the data model. I started up a website and made a couple of releases, both 100% open source.
Then life happened. I was told to work on other stuff and that project just died. Since I work for a hardware company I was able to convince my employer that everything I do for them should be open-source. I am quite proud of this fact and I hope to make more code available in this way. My friend and colleague Stan Melax improved our hull generation code but we never released to the public.
I will have to let Stan talk for himself about the algorithm he used in his implementation. My primary contribution was packaging of the source code and doing some pre and post-processing cleanup.
First, packaging. The hull generation code is provided as one CPP and one H. Stan?s code was dependent on a vector library and a couple of template classes. These are embedded in the CPP so they are hidden from the user of the library. You can also put the whole thing in a namespace if that helps.
Here are the key features of Stan?s hull generation code:
? 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.
Here are the features of my wrapper around Stan?s hull code:
? Pre-processes the input point cloud by converting it to a unit-normal cube. Duplicate vertices are removed based on a normalized tolerance level (i.e. 0.1 means collapse vertices within 1/10th the width/breadth/depth of any side. This is extremely useful in eliminating slivers. When cleaning up ?duplicates and/or nearby neighbors? it also keeps the one which is ?furthest away? from the centroid of the volume.
? Outputs the convex hull as triangles or faces depending on a user setting.
? Outputs the faces in either winding order based on a user setting.
? Cleans up dead vertices generated. If you pass say 1,000 vertices into a hull generator, you might only get say 100 out. The hull generated will provide indices to the original 1,000 vertices however. The routine ?BringOutYourDead? will re-index the hull so that it only contains the 100 vertices which are actually used.
This new version of the library is completely open source. It comes with a small console application that loads a Wavefront .OBJ file, generates a hull, and then writes out the generated hull as another Wavefront OBJ. The console application accepts a few command line switches to control various parameters.
The single .CPP is about 3,000 lines of code; mostly because of the embedded template classes. The header file and implementation example are both very small.
My original ?Open Dynamics Framework? project is pretty much dead. The project continues on under a different name, and is still open source (so long as I can keep it that way). However, it got subsumed into my company and is being developed by other programmers than myself.
I hope you will indulge this post. I am only doing so because the original library was posted here and I continue to get so many requests for it.
Since I have gathered a large collection of open-source material in the past couple of years, I plan to start posting it in bite-sized pieces on a website I just set up today. My first post today contains ?StanHull?. If you have any questions about the code, in terms of how to use it, build it, or about the pre-processing phase, then contact me. If you have specific questions about the hull generation code and algorithm you will need to contact Stan Melax (melax@ageia.com).
You can find the StanHull.zip file at my new code website: http://www.codesuppository.blogspot.com/
Thanks,
John