A reconstruction of an unknown 3-D surface from a collection of its cross sections; an implementation

Abstract

In biological research, medical diagnosis and therapy, as well as in architecture, automobile, and ship design a three dimensional solid must be reconstructed from a set of sections, either to aid in the comprehension of the object's structure or to facilitate its automatic manipulation and analysis.

This paper presents a mathematical solution to that problem which is due to Fuchs, Kedem and Uselton [3] and an algorithm that implements that solution; the solution of the problem requires the approximation of each lateral surface band delimited by two neighbouring contour lines by tiles. To determine the set of tiles needed to approximate each lateral band, one has to find a certain minimum cost cycle in a directed toroidal graph. It is shown that the search for this cycle could be restricted to a planar graph. An algorithm for finding that cycle is given and its implementation is presented.

Keywords:

• Algorithms
• graph
• image generation
• object modeling
• contour
• object reconstruction
• graphics pipeline
• data structures
• sampling

C.R. Categories:

• D.1.0 Programming Techniques
• E.1 Data Structures
• F.2.0 Analysis of Algorithms
• G.2.2 Graph Theory
• I.3.4 Graphics Utilities I.3.5 Object Modeling
• I.4.0 Image Processing
• J.3 Medical Sciences