Crust is an algorithm for reconstructing surfaces of any topology. In other words, it is a computational method for digitally rendering any 2-D shape, using data in three-dimensional space as input.
Strange topology at MIT
Such methods garner a lot of attention these days. Here are a few reasons why: Graphical simulation models are increasingly needed for visualization and testing purposes in the field of particle physics. World of Warcraft and Second Life rely heavily on computationally intensive computer graphics, and scalable distributed systems. The U.S. economy is a highly complex system, partly guided by the results of mathematical models.
Crust was developed as a collaborative effort between two staff scientists at Xerox PARC and a researcher at MIT.
None of this happened recently. In fact, Crust hasn’t been semantically linked with the word “new” since its debut at the 1998 ACM SIGGRAPH Conference.
What is so special about Crust?
The Crust algorithm is special because it has certain features uncommon in most quantitative models, yet highly sought after.
First, Crust offers results with “provable” guarantees. Given a good sample from a smooth surface, Crust’s results are guaranteed. That is, Crust guarantees that its output is topologically correct, converging to the original surface with increasing faithfulness depending on the input data density.
Graphical computation with Crust: Voronoi Piggy
The third member of the Crust project team was Manolis Kamvysellis, a Ph.D. student at MIT. Manolis did much of the implementation and testing work—he wrote a short-form version, A New Voronoi Based Reconstruction Algorithm [PDF], of the original ACM journal publication. Happily, he had the good sense to demonstrate Crust with this fine pink pig! Let’s do the same.
Highly efficient porcine reconstruction in three dimensions
Recall that Crust’s criteria for acceptable sample size is determined dynamically . A single topological surface, such as Piggy, may have very detailed surfaces, with high data density. Observe this near Piggy’s ears and snout. Other areas like the hindquarters are quite featureless.
Crust dynamically adjusts its smallest acceptable sample size accordingly. Even minimally detailed surfaces such as Piggy’s lower hind quarters above the hooves can be reconstructed accurately.
To be continued…
Ellie Asks Why 