Optimal surface reconstruction from planar contours

H. Fuchs, Z. M. Kedem, S. P. Uselton

Research output: Contribution to journalArticle

Abstract

In many scientific and technical endeavors, a three-dimensional solid must be reconstructed from serial sections, either to aid in the comprehension of the object's structure or to facilitate its automatic manipulation and analysis. This paper presents a general solution to the problem of constructing a surface over a set of cross-sectional contours. This surface, to be composed of triangular tiles, is constructed by separately determining an optimal surface between each pair of consecutive contours. Determining such a surface is reduced to the problem of finding certain minimum cost cycles in a directed toroidal graph. A new fast algorithm for finding such cycles is utilized. Also developed is a closed-form expression, in terms of the number of contour points, for an upper bound on the number of operations required to execute the algorithm. An illustrated example which involves the construction of a minimum area surface describing a human head is included.

Original languageEnglish (US)
Pages (from-to)693-702
Number of pages10
JournalCommunications of the ACM
Volume20
Issue number10
DOIs
StatePublished - Oct 1 1977

Keywords

  • continuous tone displays
  • contour data
  • minimum cost paths
  • serial sections
  • surface reconstruction
  • three-dimensional computer graphics

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal surface reconstruction from planar contours'. Together they form a unique fingerprint.

  • Cite this