Keywords: MOAA approach, triangular mesh, subdivision.

This paper is concerned with the construction of triangular surface mesh from a set of unorganised data points. The proposed method, the Maximum Opposite Angulation Approach - MOAA has some features about controllability and mesh quality. This research is able to solve many common problems in CAD, CAE, animation, virtual reality, reverse engineering and medical science.

The MOAA method is capable of producing triangular meshes both in 2-D and 3-D space by presetting uniformity to the unorganized point data set. This pre-set uniformity is achieved by the algorithm, i.e. by forming point pairs yielding possible shortest line segments. Then those line segments are connected with proper data points which will provide the vertices of the triangular meshes in such a way that each candidate vertex point provides the maximum opposite angle for the line segment of interest. These two criterions are satisfied by the MOAA by presetting the uniformity to the point data set. Thus, the constructed meshes through the MOAA provide good quality mesh architecture with well-balanced interior angles and good aspect ratios.

The MOAA is the same as Delaunay approach in 2-D with good efficiency, but much more efficient in forming triangular meshes in 3-D surface reconstruction when it is compared with many other algorithms with respect to preservation capability of the original surface topology.

Besides, the topology optimization and thus topology judgment are included in the MOAA to prevent distortion which is related with data points in the neighbourhood of the corners and boundaries and edges, to provide high precision on the reconstructed surface. The algorithm developed for this purpose is also presented in this study.

The development of MOAA is based on the following ideas: Firstly, surface feature or mesh structure cannot be decided by the simple stodgy method, especially at the corner and on the edge. But, in the surface region similar to a plane, the best structure has some verdicts. Therefore the mesh corresponding to such region can be finished earlier than that in the region without such property. Also these structures will provide the reference to mesh generation of other region. Secondly, the mesh generation approaches need the ability of controllability of the feature and allowance of the error. Thirdly, in the process of mesh generation, characteristics of the approaches may also be reflected to mesh structures, for example twice continuous differentiability, topology of surfaces and loss of the geometric feature. Such distortions are hoped to be reduced to the limit. Fourthly, the best way to obtain the good mesh structure is to choose the mesh after comprehensive examinations. So the demands stated above are necessary to be made in generation algorithms.

In the present study, weaknesses of the methods in the past are pointed out in section 2. And in the following sections, characteristics of the proposed method, such as generation of high quality mesh structure, avoidance of the loss of information of a point and the surface structure, and retention of characteristics at the corner or on the edge is stated. In the last part of this paper, some complex models are used to show the value of the MOAA.

1

B. Fausto, M. Joshua, R. Holly, S. Claudio and T. Gabriel, The ball-pivoting algorithm for surface reconstruction. IEEE Transactions on Visualization and Computer Graphics, 5, No.4 (1999), 349-359. doi:10.1109/2945.817351

2

H. Hoppe, Surface reconstruction from unorganized points. Doctoral Thesis, University of Washington, 1994.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)