Construction Of Polyhedral Surfaces From Serial Sections: Exact And Heuristic Solutions

The problem of reconstructing a polyhedral surface from cross-sectional data admits of an exact and automatic solution when the surface is densely sampled as a voxel surface. We regard such a surface as a discrete sampling of a smooth manifold in general position. Using the full adjacency graph of the surface provided by a voxel model, we are able to classify the small set of possible topological changes in the sections of the surface; we then deal with these cases exhaustively, and thereby guide the triangulation process. In this way we are able to carry out triangulation without human interaction. When the sections are sparsely sampled, heuristic methods must suffice for triangulation. These methods work well on segments of "generalized cylinder," i.e., runs of sections containing single loops, but they often fail when attempting to process highly convoluted surfaces. This is because the topology of the sections changes when a critical point of the surface is encountered. We outline a heuristic algorithm based upon the same theoretical considerations as the full (dense-sampling) algorithm. This second algorithm follows a parsing step similar to that of the full algorithm, but locates critical nodes which are saddle points by a least-squares procedure, and uses this fit to supply the information required to complete the triangulation. This method provides a solution which is comparable in quality to the correct solution derived from the first algorithm.