Scholarly record
PATCH PEELING FROM 3D CONVEX HULL
Abstract
This paper presents an algorithm for construction of a patch from a set of points in 3D space. Usualy, such set of points is a subset of surface points obtained from, for example, a 3D model or a terrain. To construct the patch, the points should be connected into a triangular mesh. Because the patch can have various characteristics the connection of input points in the resulting triangular mesh is rather difficult. The algorithm starts with construction of a 3D convex hull from given set of points. The 3D convex hull is used because it is a good approximation of the final patch, its construction is fast, simple and computationally stable and most important, it already contains basic characteristics of the patch. These characteristics are used to peel the patch from the convex hull. The patch peeling procedure is divided into two main steps. In the first step, boundary points of the patch are identified. To identify boundary points in a 3D convex hull the average plane is estimated and a 2D convex hull is constructed. During the second step several heuristics tests are performed to form the triangles of the final patch. All the tests are performed on triangles of a 3D convex hull. When the tests are finished, the patch is peeled from the 3D convex hull. The results show that the method succesfully solves various realistic scenarios.
Publication details
References12
Fang T.P. & Piegl L. Delaunay Triangulation Using a Uniform Grid, IEEE Computer & Graphics Applications, vol. 13, pp 36-47, 1993.
Gubais L., Knuth D. & Sharir M. Randomized incremental construction of Delaunay and Voronoi diagrams, Algorithmica, vol. 7, pp 381-413, 1992.
Cignoni P., Montani C. & Scopigno R. DeWall: A fast divide and conquer Delaunay triangulation algorithm, Computer-Aided Design, vol. 30, pp 333-341, 1998.
Zalik B. An efficient sweep-line Delaunay triangulation algorithm, Computer-Aided Design, Country, vol.37, pp 1027-1038, 2005.
Choi B.K., Shin H.Y., Yoon Y.I. & Lee J.W. Triangulation of scattered date in 3D space, Computer-Aided Design, vol. 20/issue 5, pp 239-248, 1988
Lo S.H. Volume discretization into tetrahedral-3D triangulation by advancing front approach, Computers & Structures, vol. 39/issue 5, pp 501-511, 1991.
Golias N.A. & Dutton R.W. Delaunay triangulation and 3D adaptive mesh generation, Finite Elements in Analysis and Design, vol. 25/issue 3-4, pp 331-341, 1997.
Preparata F.P. & Shamos M.I. Computational Geometry, Springer- Verlag, 1985.
Barber C.B., Dobkin D.P. & Huhdanpaa H. The quickhull algorithm for convex hulls, ACM Trans. Math. Softw., vol. 22/issue 4, pp 469-483, 1996.
Hoppe H., DeRose T., Duchamp T. McDonald J. & Stuetzle W. Surface reconstruction from unorganized points, Proceedings of the 1 9 Annual Conference on Computer Graphics and interactive Techniques, J. J. Thomas, Ed. SIGGRAPH '92. ACM, 1992.
Algori M.E. & Schmitt F. Surface reconstruction from unstructured 3D data, Computer Graphics Forum, vol. 15/issue 1, pp 47-60, 1996.
Pivec B. & Domiter V. A general algorithm for triangular meshes simplification, Computer science and technology, (Electrical and engineering series), WSEAS, pp 611-615, 2007.
View or Download full articleAccess options
SWS access login
Login as SWS Scientific CommitteeLogin as SWS Scientific PartnerLogin as SWS AuthorAuthors and approved SWS contributors will read and export their own linked papers after identity matching by SWS profile, email and SGEM GlobalID.
For librarian assistance: [email protected]
Purchase Instant Access
- Article can be downloaded after successful payment.
- Article may be used according to SWS library access terms.
- Article cannot be redistributed.