StanHull convex hull generation

Physics APIs, Physics file formats, Maya, Max, XSI, Cinema 4D, Lightwave, Blender, thinkingParticles™ and other simulation tools, exporters and importers
Post Reply
ageia
Posts: 1
Joined: Mon Mar 06, 2006 5:21 pm

StanHull convex hull generation

Post by ageia »

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
melax
Posts: 42
Joined: Mon Apr 24, 2006 4:55 pm

Re: StanHull convex hull generation

Post by melax »

ageia wrote: 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.
I initially wrote the code to use in a 3ds max plugin where the artist could select the number of vertices he wanted in a convex hull. The artist would apply the "convex hull" modifier and select the number of verts interactivly using a spinner widget up and down (or just type in the number). Initially, I wasn’t anticipating offline usage. Some people, including John, were having some issues with another convex hull generator they were using and decided to try my code. It turned out to be helpful for them.

Some recent questions that I've had:
did you develop this code any further since John Ratcliff released it?
No, I haven’t done any updates to it. But, Yes, There are some improvements that I would like to make.
what algorithm is it using?
Its basically the same iterative technique that is used in quickhull, where you find a new vertex and add it to the existing hull. The difference is that quickhull tries to compute the hull in O(n lg(n)). I didn’t care about that. Instead, I wanted to find a hull up to a given number of vertices. So at each step, I find the best vertex for expansion. In other words, a greedy approach. After each expansion, you have to reevaluate the remaining vertices to pick the best candidate. So its O(n*n). Technically if you limit yourself to k vertices, then its O(n*k). The quickhull paper mentions that when expanding the current polyhedron to add a new vertex, you can get flipped faces. Like them, I detect this case and correct it. The qhull implementation lets you compute hulls for points in a space with an arbitrary number of dimensions. I only do 3D. In fact I don’t really do 2D. If the code doesn't find a starting tetrahedron, then it just returns nothing.
did you have any ideas about how I should extend it to merge coplanar faces?
The implementation is triangle centric. I figured it wouldn’t make a difference until the end anyways. i.e. if a new vertex is above a quad, then it would also be above 2 triangles that make up such a quad.

Merging coplanar faces will be a bit easier for a convex hull than for general polyhedrons. The reason is that every facet on a convex polyhedron will have to be a convex polygon.

is there anything I should look out for when using it?
Coplanar input might fail right away since the code wont find a starting tetrahedron/simplex. I’m not sure if there is a “fix” in the version John posted that will generate a small box at the “center” (avg of points) should this occur.

John Ratcliff added a wrapper that might be scaling the input to be in the 0 to 1 range. If I remember correctly, this scaling might be non uniform.

If you change this, then be warned about the hardcoded epsilon value found within the code. Yes, I do know that you cannot just assume epsilon is 0.00001. The code started out in an experimental 3dsmax plugin and got moved into a more serious production environment rather quick.



Another issue:
The algorithm uses a greedy iteration where it finds the vertex furthest out in a particular direction at each step. One issue with this approach is that its possible to pick a vertex that, while at the limit of the convex hull, can be interpolated using neighboring vertices. In other words, its lies along an edge (collinear), or within a face (coplanar) made up by other vertices. An example would be a tessellated box. You want to just pick the 8 corners and avoid picking any other the other vertices. To avoid this, after finding a candidate vertex, the code perturbs the support direction to see if it still selects the same vertex. If not, then it ignores this vertex. Its not a very elegant solution. I suspect this could cause the algorithm to be unable to find candidates on a highly tessellated sphere.

A cleaner and more robust approach would be to just allow such interpolating extreme vertices initially, and then after generating a hull, successively measure the contribution of each vertex to the hull and remove those that add no value. That would require more processing, but this is usually an offline process anyways. I haven’t had the opportunity to go back and implement this improvement.
melax
Posts: 42
Joined: Mon Apr 24, 2006 4:55 pm

Re: StanHull convex hull generation

Post by melax »

I recently had a bit of free time between employers to redo the hull implementation. updated code can be found at:
https://github.com/melax/sandbox
https://github.com/melax/sandbox/blob/m ... ude/hull.h

Algorithmic-wise its the same. The difference is that the code is tighter and style follows c++11 conventions. Code uses std::vector rather than yet another custom dynamic array<> template class. No longer does it call new/delete on every triangle. The frequent small memory allocation/deallocation was an issue for some developers (yeah - sorry bout that). Dependencies are minimal. The code does assume you have float3 and int3 structs (or classes) - too ugly to implement 3d math without these. All the hull code is in one file so its easy to search-replace with your own naming preferences. Like before, algorithm is only volume centric (doesn't consider surface area for example) so the results for a flat "pancake" point cloud might not be so good. Note, this minimal version doesn't transform to/from a normalized space nor wont be as battlefield tested as what John posted years ago.

Also rewrote a couple other things on there, such as bsp merging. Admittedly, my previous open source code for the geomod demo had too many integrated systems making it difficult if anybody actually wanted to look at or try to extract that part of the algorithm. This version comes instead with a very short sample program that just booleans a couple of shapes.

use, wrap, modify, learn-from, rewrite or ignore as you see fit. comments welcome.

cheers
RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: StanHull convex hull generation

Post by RBD »

Thank you for sharing Mr. Melax, appreciated.
ronanronan
Posts: 1
Joined: Sun Sep 06, 2015 7:39 am

Re: StanHull convex hull generation

Post by ronanronan »

well done and thanks for this great information..... you are amazing......
Post Reply