Surfaces from contours

ABSTRACT

This paper is concerned with the problem of reconstructing the surfaces of three-dimensional objects, given a collection of planar contours representing cross-sections through the objects. This problem has important aplications in biomedical research and instruction, solid modeling, and industrial inspection. The method we describe produces a triangulated mesh from the data points of the contours which is then used in conjunction with a piecewise parametric surface-fitting algorithm to produce a reconstructed surface. The problem can be broken into four subproblems: the correspondence problem (which contours should be connected by the surface?), the tiling problem (how should the contours be connected?), the branching problem (what do we do when there are branches in the surface?), and the surface-fitting problem (what is the precise geometry of the reconstructed surface?) We describe our system for surface reconstruction from sets of contours with respect to each of these subproblems. Special attention is given to the correspondence and branching problems. We present a method that can handle sets of contours in which adjacent contours share a very contorted boundary, and we describe a new approach to solving the correspondence problem using a Minimum Spanning Tree generated from the contours.

REFERENCES

• 1: Jean-Daniel Boissonnat, Shape reconstruction from planar cross sections, Computer Vision, Graphics, and Image Processing, v.44 n.1, p.1-29, Oct. 1988 [doi>10.1016/S0734-189X(88)80028-8]
• 2: Y. Bresler , J. A. Fessler , A. Macovski, A Bayesian Approach to Reconstruction from Incomplete Projections of a Multiple Object 3D Domain, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.8, p.840-858, August 1989 [doi>10.1109/34.31446]
• 3: B. Chazelle , J. Incerpi, Triangulation and shape-complexity, ACM Transactions on Graphics (TOG), v.3 n.2, p.135-152, April 1984 [doi>10.1145/357337.357340]
• 4: CHEW, L.P. Constrained Delaunay triangulations. Algorithmico 4 (1989), 97 108.
• 5: 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
• 6: CooK, L. T., COOK, P. N., LEE, K. R., BATN1TZKY, S., WON(;, B. Y. S., FRITZ, S. L., OPHIR, J., I)WV~:R, S. J., II1, BlilON(IIARI, L. R., AND TEMPI,ETON, A. W. An algorithm for volume estimation based on polyhedral approximation. 1EEE Trans. Biomed. Eng. BME-27, 9 (Sept. 1980), 493 500.
• 7: Din)^, R. O., ^Nl~ HART, P.E. Pattern Classification and Scene Analysis. Wiley, New York, 1973.
• 8: 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 [doi>10.1145/108360.108363]
• 9: G. Farin, Curves and surfaces for computer aided geometric design, Academic Press Professional, Inc., San Diego, CA, 1990
• 10: A. Fournier , D. Y. Montuno, Triangulating Simple Polygons and Equivalent Problems, ACM Transactions on Graphics (TOG), v.3 n.2, p.153-174, April 1984 [doi>10.1145/357337.357341]
• 11: H. Fuchs , Z. M. Kedem , S. P. Uselton, Optimal surface reconstruction from planar contours, Communications of the ACM, v.20 n.10, p.693-702, Oct. 1977 [doi>10.1145/359842.359846]
• 12: 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
• 13: GAREY, M. R., JOttNSON, D. S., PREPARATA, F. P., AND TAIrlAN, R.E. Triangulating a simple polygon. Inf. Proc. Lett. 7, 4 (June 1978), 175-179.
• 14: KEPPEL, E. Approximating complex surfaces by triangulation of contour lines. IBM J. Res. Dev. 19 (Jan. 1975), 2-11.
• 15: 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
• 16: LOUNSBER~, M., LOOP, C., MANN, S., MEYERS, D., PAINTER, J., DERosE, T., AND SLOAN, K. A testbed for the comparison of parametric surface methods. In SPIE/SPSE Symposium on Electronic Imaging Science and Technology (Santa Clara, Calif., Feb.). 1990.
• 17: MANN, S., LOOP, C., LOUNSBERY, M., MEYERS, D., PAINTER, J., DEROSE, T., AND SLOAN, g. A comparison of methods for parametric surface interpolation. In SIAM Conference on Geometric Design (Tempe, Ariz., Nov.). 1989.
• 18: MANN, S., LOOP, C., LOUNSBERY, M., MEYERS, D., PAINTER, J., DEROSE, T., AND SLOAN, K. A survey of parametric scattered data fitting using triangular interpolants. In Curve and Surface Modeling, Hans Hagen, Ed. SIAM Philadelphia, P. To be published.
• 19: 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
• 20: NIELSON, G. M. A transfinite, visually continuous, triangular interpolant. In Geometric Modelling: Algorithms and New Trends, G. Farin, Ed., SIAM, Philadelphia, Pa., 1987, 235-246.
• 21: O'RoURKE, J., AND SUBRAMANIAN, V. On reconstructing polyhedra from parallel slices. Tech. Rep. TR 008, Dept. of Computer Science, Smith College, Northampton, Mass., 1991.
• 22: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 23: SLOAN, K. R., JR. Analysis of"dot product space" shape descriptions. Tech. Rep. 74, Dept. of Computer Science, Univ. of Rochester, 1980.
• 24: SLOAN, K. R., JR., AND HRECHANYK, L.M. Surface reconstruction from sparse data. In IEEE Conference on Pattern Recognition and Image Processing (Aug). 1981, IEEE, New York, pp. 45 -48.
• 25: Kenneth R. Sloan, Jr. , James Painter, From contours to surfaces: testbed and initial results, Proceedings of the SIGCHI/GI conference on Human factors in computing systems and graphics interface, p.115-120, April 05-09, 1987, Toronto, Ontario, Canada
• 26: 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 [doi>10.1109/34.9117]
• 27: SOROKA, B. I. Generalized cones from serial sections. Comput. Graph. Image Proc. 15 (1981), 154-166.
• 28: WANG, Y. F., AND AGGARWAL, J.K. Construction of surface representation from 3-D volumetric scene description. In Processing of Computer Vision and Pattern Recognition (San Francisco, Calif., June). 1985.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Boundary representations; Geometric algorithms, languages, and systems
      I.3.8 Applications

General Terms:
Algorithms

Keywords:
branching problem, branching surfaces, correspondence problem, meshes, minimum spanning tree, surface fitting, surface reconstruction, tiling