An algorithm of semi-Delaunay triangulation of points cloud scattered on a surface

• Autorzy: Kucwaj J.

Identyfikatory

DOI

10.7494/csci.2014.15.3.329

• Języki publikacji: EN

Abstrakty

EN

The purpose of this paper is to generalize the Delaunay[13] triangulation onto surfaces. A formal definition and an appropriate algorithm are presented. Starting from a plane domain Delaunay triangulation definition, a theoretical approach is evolved (which is a background for further considerations). It has been proven that, in the case of a plane surface, the introduced Delaunay triangulation of surfaces is identical to classical Delaunay triangulation of the plane domain. The proposed algorithm is implemented and numerical results are shown.

Słowa kluczowe

EN

Delaunay triangulation; surface reconstruction; advancing front technique; surface meshing

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2014
• Tom: Vol. 15 (3)
• Strony: 329--348
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Kucwaj J.

• Institute for Computer Science, Department of Physics, Mathematics and Computer Science, Cracow University of Technology, ul. Warszawska 24, 31-155 Kraków

Bibliografia

• [1] Delaunay P. B.: Sur la Sph`ere Vide, Bulletin de l’Acad ́emie des Sciences de l’URSS, Classe de Sciences Math ́ematiques et Naturelles, pp. 793–800, 1934.
• [2] Ebeida M. S., Mitchell S. A., Davidson A. A., Patney A., Knupp P. M., Owens J. D.: Efficient and good Delaunay meshes from random points. Computer-Aided Design, 43, 6, 1506–1515, 2011.
• [3] Guan Z., Shan J., Zheng Y., Gu Y.: An extended advancing front technique for closed surfaces mesh generation. Int. J. Num. Meth. Engng, 74, pp. 642–667, 2008.
• [4] Jin H., Wiberg N. E.: Two-dimensional mesh generation, adaptive remeshing and refinement. Int. J. Num. Meth. Engng, 29, pp. 1501–1526, 1990.
• [5] Kucwaj J.: Delaunay Triangulation of Surfaces. ZAMM, 76, p. 3, 249, 250, 1996.
• [6] Kucwaj J.: Generation of Hybrid Grids over Plane Domains. Computer Assisted Mechanics and Engineering Sciences, 7, pp. 607–614, 2000.
• [7] Kucwaj J.: Glossary of grid generation, in Handbook of grid generation. Edited by J. F. Thompson, B. K. Soni, N. P. Weatherwill, Boca Raton London New York Washington, D. C., Appendix A-17 & Appendix B-29. Computer Assisted Mechanics and Engineering Sciences,7 , pp. 607–614, 2000.
• [8] Lo S. H.: Delaunay triangulation of non-convex planar domains. Int. J. Num. Meth. Engng, 28, pp. 2695–2707, 1989.
• [9] Lo S. H.: Finite element mesh generation and adaptive meshing. Progress in Structural Engineering and Materials, 4, pp. 381–399, 2002.
• [10] Lo S. H.: A new mesh generation scheme for arbitrary planar domains. Int. J. Num. Meth. Engng, 21
• [11] Loehner R., Morgan K.: An unstructured multigrid method for elliptic problems. Int. J. Num. Meth. Engng, 24, pp. 101–115, 1987.
• [12] Ohrhallinger S., Mudur S. P.: Interpolating an unorganized 2D point cloud with a single closed shape. Computer-Aided Design, 43, pp. 1629–1638, 2011.
• [13] Rajan V.T.: Optimality of the Delaunay triangulation in Rd. Discrete Comput. Geom., 12, pp. 189–202, 1994.
• [14] Schroeder W. J., Shepard M. S., Geometry-based fully automatic mesh generation and the Delaunay triangulation. Int. J. Num. Meth. Engng, 26, pp. 2503–2515, 1988.
• [15] Wang Y., Feng H. Y., Delorme F. E., Engin S.: An adaptive normal estimation method scanned point cloud with small features. Computer Aided Design, 45, pp. 1333–1348, 2013.
• [16] Hsi-Yung Feng, Endrias D. H., Taher M. A.: Hao Song, An accurate and efficient algorithm for determining minimum circumscribed circles and spheres from discrete data points. Computer Aided Design, 45, pp. 105–112, 2013.