Optimal surface reconstruction from planar contours

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal surface reconstruction from planar contours

Full text

Pdf (1.07 MB)

Source

Communications of the ACM archive
Volume 20 , Issue 10 (October 1977) table of contents

Pages: 693 - 702

Year of Publication: 1977

ISSN:0001-0782

Authors

H. Fuchs	Univ. of Texas, Richardson
Z. M. Kedem	Univ. of Texas, Richardson
S. P. Uselton	Univ. of Texas, Richardson

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 151, Citation Count: 95

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/359842.359846 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Brooks, R.A., and DiChiro, G. Theory of image reconstruction in computed tomography. Radiology 117 (Dec. 1975), 561-572.
	3	Nicos Christofides, Graph theory: An algorithmic approach (Computer science and applied mathematics), Academic Press, Inc., Orlando, FL, 1975
	4	Fuchs, H. The automatic sensing and analysis of threedimensional surface points from visual scenes. UTECH-CSC-76- 720, U. of Utah, Salt Lake City, Utah, Aug. 1975.
	5	Harary, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
	6	Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
	7	Kedem, Z.M., and Fuchs, H. A fast method for finding several shortest paths in certain graphs. Submitted for publication.
	8	Keppel, E. Approximating complex surfaces by triangulation o{ contour lines. IBM J. Res. Develop. 19 (Jan. 1975), 2-11.
	9	Levinthal, C., and Ware, R. Three-dimensional reconstruction from serial sections. Nature 236 (March 1972), 207-210.
	10	Shantz, M.J., and McGann, G. D. Computational morphology: three-dimensional computer graphics for electron microscopy. To appear in IEEE Transactions on Biomedical Engineering.
	11	Weinstein, M., and Castleman, K.R. Reconstructing 3-D specimens from 2-D section images. Proc. SPIE 26 (May 1971), 131-138.

CITED BY 95

	Jihad El-Sana , Amitabh Varshney, Controlled simplification of genus for polygonal models, Proceedings of the 8th conference on Visualization '97, p.403-ff., October 18-24, 1997, Phoenix, Arizona, United States
	E. Ruth Johnson , Charles E. Mosher, Jr., Integration of volume rendering and geometric graphics: work in progress, Proceedings of the 1989 Chapel Hill workshop on Volume visualization, p.1-7, May 1989, Chapel Hill, Noth Carolina, United States
	Kwan-Liu Ma , Z. C. Zheng, 3D visualization of unsteady 2D airplane wake vortices, Proceedings of the conference on Visualization '94, October 17-21, 1994, Washinton, D.C.
	Norman Badler , Ruzena Bajcsy, Three-dimensional representations for computer graphics and computer vision, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.153-160, August 1978
	William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
	W.-C. Lin , C.-C. Liang , C.-T. Chen, Dynamic elastic interpolation for 3-D object reconstruction from serial cross-sectional images, Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, p.620-627, December 1987, Dallas, Texas, United States
	Lee Westover, Interactive volume rendering, Proceedings of the 1989 Chapel Hill workshop on Volume visualization, p.9-16, May 1989, Chapel Hill, Noth Carolina, United States
	George Nagy , Sharad Wagle, Geographic Data Processing, ACM Computing Surveys (CSUR), v.11 n.2, p.139-181, June 1979
	J. N. England, A system for interactive modeling of physical curved surface objects, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.336-340, August 1978
	Georgios Sakas , Stefan Walter, Extracting surfaces from fuzzy 3D-ultrasound data, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.465-474, September 1995
	Jianyun Chai , Takaharu Miyoshi , Eihachiro Nakamae, Contour interpolation and surface reconstruction of smooth terrain models, Proceedings of the conference on Visualization '98, p.27-33, October 18-23, 1998, Research Triangle Park, North Carolina, United States
	Gill Barequet , Micha Sharir, Piecewise-linear interpolation between polygonal slices, Proceedings of the tenth annual symposium on Computational geometry, p.93-102, June 06-08, 1994, Stony Brook, New York, United States
	Chandrajit L. Bajaj , Daniel R. Schikore, Distributed design of hip prostheses with BHAUTIK, Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, p.36-39, February 14-16, 1993, Indianapolis, Indiana, United States
	Gill Barequet , Michael T. Goodrich , Aya Levi-Steiner , Dvir Steiner, Straight-skeleton based contour interpolation, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Aristides G. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys (CSUR), v.12 n.4, p.437-464, Dec. 1980
	Greg Turk , James F. O'Brien, Shape transformation using variational implicit functions, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.335-342, July 1999
	Allen van Gelder , Jane Wilhelms, Topological considerations in isosurface generation, ACM Transactions on Graphics (TOG), v.13 n.4, p.337-375, Oct. 1994
	James D. Fix , Richard E. Ladner, Multiresolution banded refinement to accelerate surface reconstruction from polygons, Proceedings of the fourteenth annual symposium on Computational geometry, p.240-248, June 07-10, 1998, Minneapolis, Minnesota, United States
	Daniel S. Schlusselberg , Wade K. Smith , Margaret H. Lewis , Bradley G. Culter , Donald J. Woodward, A general system for computer based acquisition, analysis and display of medical image data, Proceedings of the ACM '82 conference, p.18-25, January 1982
	Armin Bruderlin , Lance Williams, Motion signal processing, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.97-104, September 1995
	Alain Fournier , Don Fussell , Loren Carpenter, Computer rendering of stochastic models, Communications of the ACM, v.25 n.6, p.371-384, June 1982
	Gill Barequet , Daniel Shapiro , Ayellet Tal, History consideration in reconstructing polyhedral surfaces from parallel slices, Proceedings of the 7th conference on Visualization '96, p.149-ff., October 28-29, 1996, San Francisco, California, United States
	James V. Miller , David E. Breen , William E. Lorensen , Robert M. O'Bara , Michael J. Wozny, Geometrically deformed models: a method for extracting closed geometric models form volume data, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.217-226, July 1991
	Chandrajit L. Bajaj , Malcolm C. Fields, The VAIDAK medical image model reconstruction toolkit, Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, p.28-35, February 14-16, 1993, Indianapolis, Indiana, United States
	Robert A. Drebin , Loren Carpenter , Pat Hanrahan, Volume rendering, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.65-74, Aug. 1988
	Mìchael L. Rhodes, An algorithmic approach to controlling search in three-dimensional image data, ACM SIGGRAPH Computer Graphics, v.13 n.2, p.134-142, August 1979
	Thomas W. Sederberg , Eugene Greenwood, A physically based approach to 2–D shape blending, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.25-34, July 1992
	Chris Weigle , David C. Banks, Extracting iso-valued features in 4-dimensional scalar fields, Proceedings of the 1998 IEEE symposium on Volume visualization, p.103-110, October 19-20, 1998, Research Triangle Park, North Carolina, United States
	Bradley A. Payne , Arthur W. Toga, Surface Reconstruction by Multiaxial Triangulation, IEEE Computer Graphics and Applications, v.14 n.6, p.28-35, November 1994
	Marc Levoy, Efficient ray tracing of volume data, ACM Transactions on Graphics (TOG), v.9 n.3, p.245-261, July 1990
	M. R. Stytz , G. Frieder , O. Frieder, Three-dimensional medical imaging: algorithms and computer systems, ACM Computing Surveys (CSUR), v.23 n.4, p.421-499, Dec. 1991
	James L. Helman , Lambertus Hesselink, Visualizing Vector Field Topology in Fluid Flows, IEEE Computer Graphics and Applications, v.11 n.3, p.36-46, May 1991
	A. B. Ekoule , F. C. Peyrin , C. L. Odet, A triangulation algorithm from arbitrary shaped multiple planar contours, ACM Transactions on Graphics (TOG), v.10 n.2, p.182-199, April 1991
	Sargur N. Srihari, Representation of Three-Dimensional Digital Images, ACM Computing Surveys (CSUR), v.13 n.4, p.399-424, Dec. 1981
	R. Szeliski , D. Terzopoulos, From splines to fractals, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.51-60, July 1989
	Jean-Daniel Boissonnat, Geometric structures for three-dimensional shape representation, ACM Transactions on Graphics (TOG), v.3 n.4, p.266-286, Oct. 1984
	S. Ganapathy , T. G. Dennehy, A new general triangulation method for planar contours, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.69-75, July 1982
	Ehud Artzy , Gideon Frieder , Gabor T. Herman, The theory, design, implementation and evaluation of a three-dimensional surface detection algorithm, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.2-9, July 1980
	David Meyers , Shelley Skinner , Kenneth Sloan, Surfaces from contours, ACM Transactions on Graphics (TOG), v.11 n.3, p.228-258, July 1992
	Klaus D. Toennies , Jayaram K. Udupa , Gabor T. Herman , Isaac L. Wornom III , Steven R. Buchman, Medical Imaging: Registration of 3D Objects and Surfaces, IEEE Computer Graphics and Applications, v.10 n.3, p.52-62, May 1990
	Marc Levoy, Volume Rendering, IEEE Computer Graphics and Applications, v.10 n.2, p.33-40, March 1990
	Michael Shantz, Surface definition for branching, contour-defined objects, ACM SIGGRAPH Computer Graphics, v.15 n.2, July 1981
	Shenchang Eric Chen , Richard E. Parent, Shape Averaging and it's Applications to Industrial Design, IEEE Computer Graphics and Applications, v.9 n.1, p.47-54, January 1989
	P. V. Sander , Z. J. Wood , S. J. Gortler , J. Snyder , H. Hoppe, Multi-chart geometry images, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
	Yaser Yacoob, Displaying voxel-based objects according to their qualitative shape synthesis, Proceedings of the 1st conference on Visualization '90, October 23-26, 1990, San Francisco, California
	J. P. M. Hultquist, Constructing stream surfaces in steady 3D vector fields, Proceedings of the 3rd conference on Visualization '92, October 19-23, 1992, Boston, Massachusetts
	Eric L. Schwartz , Bjorn Merker , Estarose Wolfson , Alan Shaw, Applications of Computer Graphics and Image Processing to 2D and 3D Modeling of the Functional Architecture of Visual Cortex, IEEE Computer Graphics and Applications, v.8 n.4, p.13-23, July 1988
	Alyn Rockwood, Accurate display of tensor product isosurfaces, Proceedings of the 1st conference on Visualization '90, October 23-26, 1990, San Francisco, California
	J. L. Helman , Lambertus Hesselink, Surface representations of two- and three-dimensional fluid flow topology, Proceedings of the 1st conference on Visualization '90, October 23-26, 1990, San Francisco, California
	Yoshihisa Shinagawa , Tosiyasu L. Kunii, Constructing a Reeb graph automatically from cross sections, IEEE Computer Graphics and Applications, v.11 n.6, p.44-51, November 1991
	Kenneth R. Sloan, Jr. , James Painter, From contours to surfaces: testbed and initial results, ACM SIGCHI Bulletin, v.18 n.4, p.115-120, April 1987
	Craig Upson , Michael Keeler, V-buffer: visible volume rendering, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.59-64, Aug. 1988
	M. R. Stytz , G. Frieder , O. Frieder, Three-dimensional medical imaging: algorithms and computer systems, ACM Computing Surveys (CSUR), v.23 n.4, p.421-499, Dec. 1991
	H. N. Christiansen , T. W. Sederberg, Conversion of complex contour line definitions into polygonal element mosaics, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.187-192, August 1978
	Yoshihisa Shinagawa , Tosiyasu L. Kunii , Yannick L. Kergosien, Surface Coding Based on Morse Theory, IEEE Computer Graphics and Applications, v.11 n.5, p.66-78, September 1991
	C. H. Lee, Image Surface Approximation with Irregular Samples, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.2, p.206-212, February 1989
	Kenneth R. Sloan , James Painter, Pessimal Guesses may be Optimal: A Counterintuitive Search Result, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.6, p.949-955, November 1988
	J. W. Gorman , O. R. Mitchell , F. P. Kuhl, Partial Shape Recognition Using Dynamic Programming, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.2, p.257-266, March 1988
	Bradley A. Payne , Arthur W. Toga, Medical Imaging: Surface Mapping Brain Function on 3D Models, IEEE Computer Graphics and Applications, v.10 n.5, p.33-41, September 1990
	P. T. Sander , S. W. Zucker, Inferring Surface Trace and Differential Structure from 3-D Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.9, p.833-854, September 1990
	Ehud Artzy , Gabor T. Herman, Boundary detection in 3-dimensions with a medical application, ACM SIGGRAPH Computer Graphics, v.15 n.1, April 1981
	Ye Duan , Hong Qin, A subdivision-based deformable model for surface reconstruction of unknown topology, Graphical Models, v.66 n.4, p.181-202, July 2004
	A. Iglesias , G. Echevarría , A. Gálvez, Functional networks for B-spline surface reconstruction, Future Generation Computer Systems, v.20 n.8, p.1337-1353, November 2004
	Ake Wallin, Constructing Isosurfaces From CT Data, IEEE Computer Graphics and Applications, v.11 n.6, p.28-33, November 1991
	Jihad El-Sana , Amitabh Varshney, Topology Simplification for Polygonal Virtual Environments, IEEE Transactions on Visualization and Computer Graphics, v.4 n.2, p.133-144, April 1998
	Yuefeng Zhang, A Fuzzy Approach to Digital Image Warping, IEEE Computer Graphics and Applications, v.16 n.4, p.34-41, July 1996
	R. Szeliski, Fast Surface Interpolation Using Hierarchical Basis Functions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.6, p.513-528, June 1990
	Alain Fournier , Don Fussell, Stochastic modeling in computer graphics, ACM SIGGRAPH Computer Graphics, v.14 n.SI, p.1-8, July 1980
	Henry Fuchs , Marc Levoy , S. M. Pizer, Interactive Visualization of 3D Medical Data, Computer, v.22 n.8, p.46-51, August 1989
	Gill Barequet , Michael T. Goodrich , Aya Levi-Steiner , Dvir Steiner, Contour interpolation by straight skeletons, Graphical Models, v.66 n.4, p.245-260, July 2004
	Ross T. Sowell , Cindy M. Grimm, A tool for fitting surfaces to medical image data, ACM SIGGRAPH 2006 Research posters, July 30-August 03, 2006, Boston, Massachusetts
	N. C. Gabrielides , A. I. Ginnis , P. D. Kaklis, Constructing smooth branching surfaces from cross sections, Proceedings of the 2006 ACM symposium on Solid and physical modeling, June 06-08, 2006, Cardiff, Wales, United Kingdom
	Greg Turk , James F. O'Brien, Shape transformation using variational implicit functions, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	Yann Frauel , Octavio Quesada , Ernesto Bribiesca, Detection of a polymorphic Mesoamerican symbol using a rule-based approach, Pattern Recognition, v.39 n.7, p.1380-1390, July, 2006
	Sergey Bereg , Minghui Jiang , Binhai Zhu, Contour interpolation with bounded dihedral angles, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	Ya-Hui Shiao , Keh-Shih Chuang , Tzong-Jer Chen , Chun-Yuan Chen, Polygon interpolation for serial cross sections, Computers in Biology and Medicine, v.37 n.9, p.1241-1251, September, 2007
	Ilya Braude , Jeffrey Marker , Ken Museth , Jonathan Nissanov , David Breen, Communicated by Hans-Peter Seidel: Contour-based surface reconstruction using MPU implicit models, Graphical Models, v.69 n.2, p.139-157, March, 2007
	N. C. Gabrielides , A. I. Ginnis , P. D. Kaklis , M. I. Karavelas, G1-smooth branching surface construction from cross sections, Computer-Aided Design, v.39 n.8, p.639-651, August, 2007
	Hoi-Man Yip , Ishfaq Ahmad , Ting-Chuen Pong, An Efficient Parallel Algorithm for Computing the Gaussian Convolution of Multi-dimensional Image Data, The Journal of Supercomputing, v.14 n.3, p.233-255, Dec.1.1999
	J. D. Boissonnat, Reconstruction of solids, Proceedings of the first annual symposium on Computational geometry, p.46-54, June 05-07, 1985, Baltimore, Maryland, United States
	K. D. Toennies , U. Tronnier, 3D modeling using an extended cell enumeration representation, ACM SIGGRAPH Computer Graphics, v.24 n.5, p.13-20, Nov. 1990
	Zoë J. Wood , Peter Schröder , David Breen , Mathieu Desbrun, Semi-regular mesh extraction from volumes, Proceedings of the conference on Visualization '00, p.275-282, October 2000, Salt Lake City, Utah, United States
	David Weinstein, Scanline surfacing: building separating surfaces from planar contours, Proceedings of the conference on Visualization '00, p.283-289, October 2000, Salt Lake City, Utah, United States
	T. Todd Elvins, A survey of algorithms for volume visualization, ACM SIGGRAPH Computer Graphics, v.26 n.3, p.194-201, Aug. 1992
	John K. Johnstone , Kenneth R. Sloan, Tensor Product Surfaces Guided by Minimal Surface Area Triangulations, Proceedings of the 6th conference on Visualization '95, p.254, October 29-November 03, 1995
	Jane Wilhelms , Allen Van Gelder, Topological considerations in isosurface generation extended abstract, ACM SIGGRAPH Computer Graphics, v.24 n.5, p.79-86, Nov. 1990
	Tao Ju , Qian-Yi Zhou , Michiel van de Panne , Daniel Cohen-Or , Ulrich Neumann, Reusable skinning templates using cage-based deformations, ACM Transactions on Graphics (TOG), v.27 n.5, December 2008
	Scott Dillard , John Bingert , Dan Thoma , Bernd Hamann, Construction of Simplified Boundary Surfaces from Serial-sectioned Metal Micrographs, IEEE Transactions on Visualization and Computer Graphics, v.13 n.6, p.1528-1535, November 2007
	Fady Massarwi , Craig Gotsman , Gershon Elber, Paper-craft from 3D polygonal models using generalized cylinders, Computer Aided Geometric Design, v.25 n.8, p.576-591, November, 2008
	S. Biasotti , L. De Floriani , B. Falcidieno , P. Frosini , D. Giorgi , C. Landi , L. Papaleo , M. Spagnuolo, Describing shapes by geometrical-topological properties of real functions, ACM Computing Surveys (CSUR), v.40 n.4, p.1-87, October 2008
	Ross T. Sowell , Lu Liu , Tao Ju , Cindy M. Grimm, An interactive tool for fitting surfaces to volume data, ACM SIGGRAPH 2008 posters, August 11-15, 2008, Los Angeles, California
	Toshiro Kubota, A Shape Representation with Elastic Quadratic Polynomials--Preservation of High Curvature Points under Noisy Conditions, International Journal of Computer Vision, v.82 n.2, p.133-155, April 2009
	Young-Kyu Choi, Dividing Virtual Belt Algorithm for Reconstructing Surface from a Set of Wire-Frame Contours, IEICE - Transactions on Information and Systems, v.E91-D n.9, p.2365-2368, September 2008
	Joseph O'Rourke, Polyhedra of minimal area as 3D object models, Proceedings of the 7th international joint conference on Artificial intelligence, p.664-666, August 24-28, 1981, Vancouver, BC, Canada
	R. Sowell , L. Liu , T. Ju , C. Grimm , C. Abraham , G. Gokhroo , D. Low, Volume viewer: an interactive tool for fitting surfaces to volume data, Proceedings of the 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling, August 01-02, 2009, New Orleans, Louisiana

INDEX TERMS

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

Collaborative Colleagues:

H. Fuchs: colleagues

Z. M. Kedem: colleagues

S. P. Uselton: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player