Our implementation of the power crust algorithm for surface reconstruction and medial axis transform approximation is available as source code under the GNU public license. The source code is in C and C++, we have compiled it on SGIs and Linux machines. There is a Windows port, due to Patrick Min at Princeton, and a VTK port, due to Tim Hutton at University College, London. (THANKS!)The power crust algorithm works well (in fact, it's proved correct) on a dense point sample from the surface of a smooth object without boundary. Your input might not be sufficiently dense, it might have noise in it, it might be from a surface with boundary, it might fail to cover the whole surface, or it might be from a surface with sharp corners. We find that we can often get a good output in these situations as well, and the software includes some command-line parameters which you can twiddle to try and improve the quality of your output. No twiddling is necessary on good inputs. Here is the README file explaining the options. You should read some of our papers if you really want to understand what the program is doing. We do not plan to support this software and it comes with no warranty.
Our program incorperates two other important pieces of free computational geometry software. First, we construct both the Voronoi diagram and the power diagram using Ken Clarkson's program hull. This program robustly computes Voronoi diagrams, Delaunay triagulations and convex hulls in arbitrary dimension, which, believe us, is not easy. Since it outputs a combinatorial, but not a geometric, representation of the Voronoi diagram and power diagram, we use Jonathan Shewchuk's robust determininats to find the positions of Voronoi and power diagram vertices. This project would not have been possible without the excellent work of Dr. Clarkson and Prof. Shewchuk and their willingness to share their code.
Some of our output files are in the Geomview OFF format, which can be viewed with the free geometry visualization program Geomview, which was developed at The Geometry Center; the lead programmers were Stuart Levy, Tamara Munzner and Mark Phillips.
We would like to keep track of how many users we have and who they are.
Please fill out the three fields below and press the submit button.
You will then be allowed to download the software.