Polyhedrization of an arbitrary 3D point set

Given a 3D point set, the problem of defining the volume associated, dividing it into a set of regions (elements) and defining a boundary surface is tackled. Several physical problems need to define volume domains, boundary surfaces and approximating functions from a given point distribution. This is for instance the case of particle methods, in which all the information is the particle positions and there are not boundary surfaces definition. Until recently, all the FEM mesh generators were limited to the generation of simple elements as tetrahedral or hexahedral elements (or triangular and quadrangular in 2D problems). The reason of this limitation was the lack of any acceptable shape function to be used in other kind of geometrical elements. Nowadays, there are several acceptable shape functions for a very large class of polyhedra. These new shape functions, together with a generalization of the Delaunay tessellation presented in this paper, gives an optimal marriage and a powerful tool to solve a large variety of physical problems by numerical methods. The domain partition into polyhedra presented here is not a standard mesh generation. The problem here is: for a given node distribution to find a suitable boundary surface and a suitable mesh to be used in the solution of a physical problem by a numerical method. To include new nodes or change their positions is not allowed. (C) 2003 Elsevier Science B.V. All rights reserved.