PATCH PEELING FROM 3D CONVEX HULL

10th International Multidisciplinary Scientific GeoConference - SGEM2010, www.sgem.org, SGEM2010 Conference Proceedings/ ISBN 10: 954-91818-1-2, June 20-26, 2010, Vol. 1, 1085-1092 pp

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.

Keywords: patch, peeling, 3D convex hull, 2D convex hull, triangulation