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

Jan Kucwaj

doi:10.7494/csci.2014.15.3.329

Authors

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

DOI:

https://doi.org/10.7494/csci.2014.15.3.329

Keywords:

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

Abstract

The purpose of the paper is to generalize the Delaunay triangulation onto surfaces. A formal definition and appropriate algorithm are presented. Starting from plane domain Delaunay triangulation definition a theoretical approach is evolved which is a background for further considerations. It is proved that in case of plane surface the introduced Delaunay triangulation of surfaces is identical with classical Delaunay triangulation of plane domain. The proposed algorithm is implemented and numerical results are shown.

Downloads

Download data is not yet available.

References

Delaunay P. B.: Sur la Sph`ere Vide, Bulletin de l’Académie des Sciences de l’URSS, Classe de Sciences Mathématiques et Naturelles, pp. 793–800, 1934.

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.

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.

Jin H., Wiberg N. E.: Two-dimensional mesh generation, adaptive remeshing and refinement. Int. J. Num. Meth. Engng, 29, pp. 1501–1526, 1990.

Kucwaj J.: Delaunay Triangulation of Surfaces. ZAMM, 76, p. 3, 249, 250, 1996.

Kucwaj J.: Generation of Hybrid Grids over Plane Domains. Computer Assisted Mechanics and Engineering Sciences, 7, pp. 607–614, 2000.

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.

Lo S. H.: Delaunay triangulation of non-convex planar domains. Int. J. Num. Meth. Engng, 28, pp. 2695–2707, 1989.

Lo S. H. : Finite element mesh generation and adaptive meshing. Progress in Structural Engineering and Materials, 4, pp. 381–399, 2002.

Lo S. H.: A new mesh generation scheme for arbitrary planar domains. Int. J. Num. Meth. Engng, 21, pp. 1403–1426, 1985.

Loehner R., Morgan K.: An unstructured multigrid method for elliptic problems. Int. J. Num. Meth. Engng, 24, pp. 101–115, 1987.

Ohrhallinger S., Mudur S.P.: Interpolating an unorganized 2D point cloud with a single closed shape. Computer-Aided Design, 43, pp. 1629–1638, 2011.

Rajan V.T.: Optimality of the Delaunay triangulation in Rd. Discrete Comput. Geom., 12, pp. 189–202, 1994.

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.

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.

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.