NVidia has this great article on marching cubes to generate complex procedural terrain.
It really drives the point home on how simple (which doesn’t mean easy!) it can be, and was a a-ha moment for me about GPU streaming design, the power of shaders for procedural generation, and the connection with signal processing.
AKA my first experience with patent law. Marching cubes is an incredibly obvious algorithm, and the owners of the patent for it sued people gleefully in my experience. I talked to numerous game and simulation developers at the time and the story was the same: a need to convert volumetric data into a 3D surface, coming up with the obvious approach, get a nasty letter that it was patented.
Very happy when the patent expired.
Condolences to his family, though. He sounds like he was actually a good guy.
There's also Marching Tetrahedra which wasn't covered by the marching cubes patent and was kindly allowed to be used freely (and had some small improvements). [1]
GE controlled the patent, not Bill. He was also very happy when the patent expired.
I would also argue whether it was obvious or not. At the time it was developed, not that many people were doing surface reconstruction of volumetric data. Bill and Harvey came up with Marching and Dividing Cubes to support GE Medical.
"Marching Cubes remains the most widely cited visualization algorithm ever".
It's an awesome algorithm that takes an isosurface (imagine a 3D map of weights) and generates a polygonal mesh. This algo was heavily used in the demoscene and often referred to as 'meta balls'.
> This algo was heavily used in the demoscene and often referred to as 'meta balls'.
No. It is used to implement 'meta balls' effect sometimes. But the two terms are not synonymous. From my experience it's more common to see meta balls implemented with raytracing or some screen-space techniques.
“Gears are often referred to as ‘pocket watches’” is not a correct statement, even though gears are sometimes used in the implementation of pocket watches.
I'll give a shot at explaining isosurfaces in a little more detail.
The prefix iso- means "the same." An isosurface is a surface for which some value is the same at every point. Marching Cubes is used for creating a polygon mesh of a 3D isosurface, but it's easier to understand by first imagining the 2D case.
In two dimensions, you don't really have isosurfaces. As you lack the third dimension, you have isolines. You're probably familiar with those already when viewing terrain maps. The contour lines on terrain maps are isolines. They are drawn for some chosen height value(s) and as you trace along a line, every point on that line has the same height value. You can generate those lines using "marching squares", a 2D version of marching cubes.
I'm not terribly familiar with the details of the marching cubes algorithm, because I took one look at the tables I'd need to transcribe and decided not to implement it myself, but basically you split the world into a big grid. You query the values at the grid cell corners, and based on which corners are above or below the isovalue, you know what edges the isosurface passes through.
There's a table of shapes to that correspond to a given combination of corners in or out. For edges that have an intersection point with the isosurface, you then estimate its position on the edge by interpolating the two corners and finding the where it equals the isovalue.
The results of most VFX fluid simulations today are particles, and the distance to the nearest particle creates a distance field defined through all space. If you pick some distance value, you can then polygonize the isosurface with marching cubes. You'll probably also need a bit of smoothing, since otherwise the isosurface will be bumpy.
I'm not sure if films like Moana [1] actually polygonized their fluid isosurface before rendering it or if they directly solved the equation for the implicit surface during ray tracing, but the fact that I can't tell should give you some indication of the potential quality of the result.
IIRC, marching cubes also has a patent on it so many applications generating meshes from isosurfaces use slight derivations of marching cubes that generally speaking, accomplish the same goal. I don't know if this is still true (patented part).
Edit: the patent has expired and is in the public domain. Alternatives were used for many years though.
The Marching Cubes triangle lookup table is a 3D Wang-tileset for corner connections, reduced for symmetries. Here is a 2D example of a Wang tileset [0].
Edit: the defining quality of a Wang tileset is that it can tesselate a grid of N different colors with square tiles. Usually there are only two colors (with Marching Cubes inside and outside) because the number of tiles needed grows fast with N.
My dad spent his entire career at GE research. One day he arranged for Bill Lorensen to give me a tour of their computer graphics lab. Great guy! Sad to hear that he has passed.
It really drives the point home on how simple (which doesn’t mean easy!) it can be, and was a a-ha moment for me about GPU streaming design, the power of shaders for procedural generation, and the connection with signal processing.
https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch01....