Marching Cubes
It started in July 1984 with a seminar by Carl Crawford.
In 1984 Carl was working in GE's Medical Systems Business Groupi in Milwaukee. Carl worked in the Applied Sciences Lab (ASL) and was a recognized expert in Computed Tomography (CT) reconstruction. Carl was also part of a company task force that was looking for applications for an exciting new GE product, the Graphicon. The GE Graphicon was a high performance rendering engine. Each GE division was asked to look for applications of this technology. Carl's seminar was held in Building 37, at the downtown Schenectady GE manufacturing facility. The main research campus where I worked was about 4 miles away. Several of the research labs that did advanced engineering work were in Building 37.
Carl described the capabilities of the (not yet built) Graphicon. He described his vision for using this polygon engine for 3D medical surface display. The current GE 3D product was based on cuberilles and was optimized for implementation in the limited memory Data General computersii. This technology was licensed from the University of Pennsylvania. Carl challenged the seminar attendees to think how they might replace the cuberille technology with polygon-based technology.
Harvey Cline and I attended the seminar. Harvey was in the Electronic Materials Lab and I was in Computer Systems and Services, part of the central computer group at CRD. Harv and I had been doing some work on reconstructing 3D surfaces from interferograms. The application was reconstruction of microscopic surfaces of electronic materials. The final step of our reconstruction algorithm used Movie.BYU's Mosaic program to generate triangles bewteen adjacent contours. We had been looking for medical applications and saw Carl's challenge as a way to get our foot into GE Medical Systems. Carl's talk was in the morningiii and Harv and I returned to my office to brainstorm about the problem. Rubick's Cube was the rage at the time and Harv was analyzing the Cube problem using the symmetry of cubical lattices. The accepted way of generating surfaces from volume data was to generate 2D contours on each slice and then try to connect the contours with triangles. This is exactly what Mosaic did. Whenever Harv and I got together it was an explosion of ideasiv. It's difficult to say who originated or how we came up with the idea. But, somehow we determined that solving the problem one cube at a time would remove a lot of the complexity. The inside/outside notion labeling of vertices may have come from the Movie.BYU Mosaic program. We quickly moved to the notion of solving the volume to surface problem one cube at a timev. Harv and I started to solve the problem for each of the 256 cases. After just a few, we realized the effort was fruitless. But, using cube symmetry operations we reduced the number of unique cases to 14. Harv and I worked out the triangulations for the basic cases. I started to write code to permute the base cases into the 256 cases.
Then I began coding the algorithm. The algorithm was really easy to implement. I had something running the next day. The first implementation read volumes in as ascii files. Harv put together a simple volume of a few slices so I had some data to test the code. I used the Movie.BYU display program to produce hidden line and shaded surface models. Movie.BYU could only render up to 8192 polygons. The original Marching Cubes implementation created polygons, although later I switched to generating only triangles. Once the code was debugged, we tried the code on some medical data. We obtained a small CT dataset that include a spine. We extracted a small region of interest that isolated the spine. Since we were restricted to rendering 8192 triangles, the data had to be fairly small. We were excited with the results to say the least.
