Straight-skeleton based contour interpolation

ABSTRACT

In this paper we present an efficient method for interpolating a piecewise-linear surface between two parallel slices, each consisting of an arbitrary number of (possibly nested) polygons that define 'material' and 'nonmaterial' regions. This problem has applications to medical imaging, geographic information systems, etc. Our method is fully automatic and is guaranteed to produce non-self-intersecting surfaces in all cases regardless of the number of contours in each slice, their complexity and geometry, and the depth of their hierarchy of nesting. The method is based on computing cells in the overlay of the slices, that form the symmetric difference between them. Then, the straight skeletons of the selected cells guide the triangulation of these cells. Finally, the resulting triangles are lifted up in space to form an interpolating surface. We provide some experimental results on various complex examples to show the good and robust performance of our algorithm.

REFERENCES

• 1: {AAAG95} O. Aichholzer, D. A<u>lberts</u>, F. Aurenhammer, and B. Gärtner, A novel type of skeleton for polygons, J. of Universal Computer Science, 1 (1995), 752--761.
• 2: Chandrajit L. Bajaj , Edward J. Coyle , Kwun-Nan Lin, Arbitrary topology shape reconstruction from planar cross sections, Graphical Models and Image Processing, v.58 n.6, p.524-543, Nov. 1996 [doi>10.1006/gmip.1996.0044]
• 3: {BDG97} G. Barequet, M.T. Dickerson, and M.T. Goodrich, Voronoi diagrams for polygon-offset distance functions, Discrete & Computational Geometry, 25 (2001), 271--291.
• 4: {BST00} G. Barequet, D. Shapiro, and A. Tal, Multilevel sensitive reconstruction of polyhedral surfaces from parallel slices, The Visual Computer, 16 (2000), 116--133.
• 5: Gill Barequet , Micha Sharir, Piecewise-linear interpolation between polygonal slices, Computer Vision and Image Understanding, v.63 n.2, p.251-272, March 1996 [doi>10.1006/cviu.1996.0018]
• 6: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 7: 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]
• 8: {BG92} J.D. Boissonnatand B. Geiger, Three dimensional reconstruction of complex shapes based on the Delaunay triangulation, Technical Report 1697, Inria-Sophia Antipolis, 1992.
• 9: Siu-Wing Cheng , Tamal K. Dey, Improved constructions of Delaunay based contour surfaces, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.322-323, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304061]
• 10: Siu-Wing Cheng , Antoine Vigneron, Motorcycle graphs and straight skeletons, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.156-165, January 06-08, 2002, San Francisco, California
• 11: {CP94} Y.K. Choiand K.H. Park, A heuristic triangulation algorithm for multiple planar contours using an extended double branching procedure, The Visual Computer, 10 (1994), 372--387.
• 12: 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
• 13: {FO98} P. Felkeland S. Obdrzalek, Straight skeleton computation, Spring Conf. on Computer Graphics, Budmerice, Slovakia, 210--218, 1998.
• 14: {FO99} P. Felkeland S. Obdrzalek, Improvement of Oliva's algorithm for surface reconstruction from contours, Spring Conf. on Computer Graphics, Budmerice, Slovakia, 254--263, 1999.
• 15: {EE99} D. Eppsteinand J. Erickson, Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions, Disc. & Comp. Geometry, 22 (1999), 569--592.
• 16: 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]
• 17: {GD82} S. Ganapathyand T.G. Dennehy, A new general triangulation method for planar contours, ACM Trans. on Computer Graphics, 16 (1982), 69--75.
• 18: N. Kehtarnavaz , R. J. P. de Figueiredo, A framework for surface reconstruction from 3D contours, Computer Vision, Graphics, and Image Processing, v.42 n.1, p.32-47, April, 1988 [doi>10.1016/0734-189X(88)90141-7]
• 19: N. Ketarnavaz , L. R. Simar , R. J.P. Figueiredo, A syntactic/semantic technique for surface reconstruction from cross-sectional contours, Computer Vision, Graphics, and Image Processing, v.42 n.3, p.399-409, June, 1988 [doi>10.1016/S0734-189X(88)80048-3]
• 20: {Ke75} E. Keppel, Approximating complex surfaces by triangulation of contour lines, IBM Journal of Research and Development, 19 (1975), 2--11.
• 21: {MSS91} D. Meyers, S. Skinner, and K. Sloan, Surfaces from contours: The correspondence and branching problems, Proc. Graphics Interface, 246--254, 1991.
• 22: {OPC96} J.-M. Oliva, M. Perrin, and S. Coquillart, 3D reconstruction of complex polyhedral shapes from contours using a simplified generalized Voronoi diagram, Computer Graphics Forum, 15 (1996), C397--408.
• 23: Michael Shantz, Surface definition for branching, contour-defined objects, ACM SIGGRAPH Computer Graphics, v.15 n.2, July 1981 [doi>10.1145/988420.988426]
• 24: 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]
• 25: Y F Wang , J K Aggarwal, Surface reconstruction and representation of 3-D scenes, Pattern Recognition, v.19 n.3, p.197-207, 1986 [doi>10.1016/0031-3203(86)90010-5]
• 26: Emo Welzl , Barbara Wolfers, Surface reconstruction between simple polygons via angle criteria, Journal of Symbolic Computation, v.17 n.4, p.351-369, April 1994 [doi>10.1006/jsco.1994.1024]
• 27: {ZJH87} M.J. Zyda, A.R. Jones, and P.G. Hogan, Surface construction from planar contours, Computers and Graphics, 11 (1987), 393--408.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

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

General Terms:
Algorithms, Theory

Keywords:
Piecewise-linear interpolation, surface reconstruction