A triangulation algorithm from arbitrary shaped multiple planar contours

ABSTRACT

Conventional triangulation algorithms from planar contours suffer from some limitations. For instance, incorrect results can be obtained when the contours are not convex, or when the contours in two successive slices are very different. In the same way, the presence of multiple contours in a slice leads to ambiguities in defining the appropriate links. The purpose of this paper is to define a general triangulation procedure that provides a solution to these problems. We first describe a simple heuristic triangulation algorithm which is extended to nonconvex contours. It uses an original decomposition of an arbitrary contour into elementary convex subcontours. Then the problem of linking one contour in a slice to several contours in an adjacent slice is examined. To this end, a new and unique interpolated contour is generated between the two slices, and the link is created using the previously defined procedure. Next, a solution to the general case of linking multiple contours in each slice is proposed. Finally, the algorithm is applied to the reconstitution of the external surface of a complex shaped object: a human vertebra.

REFERENCES

• 1: HERMELINE, F. Triangulation automatique d'un polyhbdre en dimension N. RAIRO, Analyse numdrique, 16, 3, 211-242.
• 2: BOtSSONAT, J. D. Representing 2D and 3D shapes with the Delaunay triangulation. Proceedings of IEEE ICASSP (1984), pp.745-748.
• 3: O'RouaKE, J. Triangulation of minimal area of 3D object model. In Proceedings of 1981 International Joint Conference on Artificial Intelligence (1981), pp.664-666.
• 4: KEt'PEL, E. Approximating complex surfaces by triangulation of contour lines, IBM. J. Res. Dev. 19 (1975), 2-11.
• 5: 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]
• 6: 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
• 7: COOK, P. N., ANt) BATNITSKY, S. Three-dimensional reconstruction from serial-sections for medical applications. In Proceedings of the 14th Hawaii International Conference on System Sciences, 2 (1981), pp.358-389.
• 8: CooK, P.W, Three-dimensional reconstruction from surface contour for head C.T. examinations. J. Comput. Assist. Tomography 5, I (1981).
• 9: 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
• 10: BOISSON^T, J. D. Surface reconstruction from planar cross-sections. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (June 1985), pp. 393-397.
• 11: Michael Shantz, Surface definition for branching, contour-defined objects, ACM SIGGRAPH Computer Graphics, v.15 n.2, July 1981 [doi>10.1145/988420.988426]
• 12: ZVDA, M. J. M., AND ALLAN, R. J. Surface construction from planar contours. Comput. Graph. 11, 4 (1987), 393-408.
• 13: EKOULE, A., PEVRIN, F., ann ODET, C. A triangulation algorithm for surface display in biomedical engineering. In Proceeding of EUSIPCO (1982), pp. 801-804.
• 14: SKL^NSKY, J. Measuring concavity on a rectangular mosaic. IEEE Trans. Comput. C-21, 12 (1972), 1355-1354.
• 15: GRAHAM, . An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett., (1972), 132-133

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

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

General Terms:
Algorithms

Keywords:
slice interpolation, triangulation