The maximum opposite angulation for mesh construction

Cheng W., Sorguc A., Shinoda J., Hagiwara I.

JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS, vol.22, no.1, pp.21-44, 2005 (SCI-Expanded) identifier identifier


In this paper, a new approach, "the Maximum Opposite Angulation (MOA for short)" algorithm, for the construction of a triangular mesh from a set of unorganized data points is proposed. A topological judgment algorithm is coupled to the MOA algorithm to avoid holes and/or intersections that can be encountered on the reconstructed surface. The MOA algorithm is based on the idea of "the list," which presets a uniformity to the initial data set to fulfill the task of forming "the good mesh architecture" which is defined as the meshes having well balanced interior angles and good aspect ratios. The list, consists of line segments formed by point pairs sorted from the shortest to the longest. The idea of MOA is then to use the shortest line segment as the initial data to start with for reconstruction of a triangular mesh. The vertex point of the triangular geometry is then searched with respect to this line segment to give the good mesh. It is also shown that, the MOA in 3-D which includes the topological judgment in smoothing out the surface of the reconstructed solid model, is superior both in speed and quality, to the existing algorithms.