S. Ganapathy
ABSTRACT
The problem of approximating the surface spanning a given set of 3D points as a polyhedron of triangular faces (“triangulation”) is a significant one, and has many applications in the fields of computer graphics and computer vision. In this paper, several solutions to this problem are reviewed. These solutions can be grouped into two classes, and particular emphasis is given to the class of surfaces spanned by parallel planar contours. For a contour pair P0,P1,...Pm−1 and Q0,Q1,...Qn−1, a graph theoretic approach can be used to arrive at a class of solutions, each requiring exactly m+n steps to triangulate the pair. Existing methods (both rigorous and heuristic) for extracting a particular solution from this group are reviewed, and a new heuristic based on inter-contour coherence is proposed. This heuristic is being used in the field of Ultrasonic Non-destructive Evaluation to produce images of flaws in pressure vessels, and its performance is shown to compare favorably with methods of greater computational complexity. It is believed that this heuristic can also be used with success in industrial vision systems where similar contours are obtained using a laser range finder.
- 1.Boissonnat, J.D. and Faugeras, O.D., "Triangulation of 3D Objects," PROCEEDINGS OF THE 1981 INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 658-660.Google Scholar
- 2.O'Roarke, Joseph, "Triangulation of Minimal Area as 3D Object Models," PROCEEDINGS OF THE 1981 INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 664-666.Google Scholar
- 3.Fuchs, H., etal., "Optimal Surface Reconstruction from Planar Contours," COMMUNICATIONS OF THE ACM, XX-10 (October 1977), 693-702. Google ScholarDigital Library
- 4.Keppel, E., "Approximating Complex Surfaces by Triangulation of Contour Lines," IBM JOURNAL OF RESEARCH AND DEVELOPMENT, XIX (January 1975), 2-11.Google ScholarDigital Library
- 5.Christianson, H. and Sederberg, T.W., "Conversion of Complex Contour Line Definitions into Polygonal Element Mosaics," COMPUTER GRAPHICS, XIII,2 (August, 1978), 187-192. Google ScholarDigital Library
- 6.Ganapathy, S., etal., "Ultrasonic Imaging Techniques for Real-time In-service Inspection of Nuclear Power Reactors", Nuclear Regulatory Commission Report NUREG/CR-2154, September, 1981.Google Scholar
- 7.Nilsson, Nils, PRINCIPLES OF ARTIFICIAL INTELLIGENCE, (Palo Alto: Tioga Publishing Co.) 1980. Google ScholarDigital Library
- 8.Horn, Berthold K. P., "Hill Shading and the Reflectance Map," PROCEEDINGS OF THE IEEE, LXIX, 1 (January, 1981) 14-47.Google ScholarCross Ref
Index Terms
- A new general triangulation method for planar contours
Recommendations
A new general triangulation method for planar contours
The problem of approximating the surface spanning a given set of 3D points as a polyhedron of triangular faces (“triangulation”) is a significant one, and has many applications in the fields of computer graphics and computer vision. In this paper, ...
Approximated algorithms for the minimum dilation triangulation problem
The complexity status of the minimum dilation triangulation (MDT) problem for a general point set is unknown. Therefore, we focus on the development of approximated algorithms to find high quality triangulations of minimum dilation. For an initial ...
Well-Centered Triangulation
Meshes composed of well-centered simplices have nice orthogonal dual meshes (the dual Voronoi diagram). This is useful for certain numerical algorithms that prefer such primal-dual mesh pairs. We prove that well-centered meshes also have optimality ...
Comments