\(r\)-regular shape reconstruction from unorganized points. (English) Zbl 0904.68172

Summary: The problem of reconstructing a surface, given a set of scattered data points is addressed. First, a precise formulation of the reconstruction problem is proposed. The solution is mathematically defined as a particular mesh of the surface called the normalized mesh. This solution has the property to be included inside the Delaunay graph. A criterion to detect faces of the normalized mesh inside the Delaunay graph is proposed. This criterion is proved to provide the exact solution in 2D for points sampling a \(r\)-regular shapes with a sampling path \(\varepsilon <\sin (\pi/8)r\). In 3D, this result cannot be extended and the criterion cannot retrieve every face. A heuristic is proposed in order to complete the surface.


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI


[1] Attali, D.; Montanvert, A., Modeling noise for a better simplification of skeletons, (Proceedings of the International Conference on Image Processing, Vol. III (1996)), 13-16
[2] Bajaj, C.; Bernardini, F.; Xu, G., Automatic reconstruction of surfaces and scalar fields from 3d scans, (Computer Graphics Proceedings, SIGGRAPH ’95 (1995)), 109-118
[3] Barequet, G.; Dickerson, M.; Eppstein, D., On triangulation 3-dimensional polygons, (Proc. of the 12th ACM Symp. on Computational Geometry (1996)), 38-47
[4] Boissonnat, J. D., Geometric structures for three-dimensional shape representation, ACM Trans. Graphics, 3, 4, 266-286 (1984)
[5] Brandt, J. W., Convergence and continuity criteria for discrete approximations of the continuous planar skeletons, CVGIP: Image Understanding, 59, 1, 116-124 (1994)
[6] Colchester, A. C.F.; Robinson, G. P.; Griffin, L. D., A unified approach to the segmentation of grey-level and dot-pattern, (Proc. of the 11th International Conference on Pattern Recognition. Proc. of the 11th International Conference on Pattern Recognition, The Netherlands (1992)), 319-322
[7] Edelsbrunner, H.; Kirkpatrick, D. G.; Seigel, R., On the shape of a set of points in the plane, IEEE Trans. Inform. Theory, 29, 4, 551-559 (1983) · Zbl 0512.52001
[8] Edelsbrunner, H.; Mucke, E. P., Three-dimensional alpha shapes, ACM Trans. Graphics, 13, 1, 43-72 (1994) · Zbl 0806.68107
[9] Fairfield, J., Segmenting dot patterns by Voronoi diagram concavity, IEEE Trans. PAMI, 5, 1, 104-110 (1983)
[10] Hoppe, H.; DeRose, T.; Duchamp, T.; McDonnald, J.; Stuetzle, W., Surface reconstruction from unorganized points, Computer Graphics, 26, 2, 71-77 (1992)
[11] Lorensen, W. E.; Cline, H. E., Marching cubes: A high resolution 3d surface construction algorithm, Computer Graphics, 21, 163-169 (1987)
[12] O’Rourke, J., Polyhedra of minimal area as 3d objects models, (Proc. of the International Joint Conference on Artificial Intelligence (1981)), 664-666
[13] O’Rourke, J.; Booth, H.; Washington, R., Connect-the-dots: A new heuristic, Computer Vision, Graphics and Image Processing, 39, 258-266 (1987) · Zbl 0657.68118
[14] Rippa, S., Minimal roughness property of the Delaunay triangulation, Comput. Aided Geom. Design, 7, 489-497 (1990) · Zbl 0714.65009
[15] Serra, J., Image Analysis and Mathematical Morphology (1982), Academic Press: Academic Press London · Zbl 0565.92001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.