由亂點資料建立三角網格模型之研究

On the Development of an Efficient Triangulation Algorithm for 3D Cloud Points

許凱韋(Kai-Wei Hsu)

指導教授 ： 賴景義

國立中央大學/工學院/機械工程學系/碩士(2008年)

摘要

三角網格有格式簡單、易於處理的特性，且利用三角網格可以構成任何形狀的物體，使得三角網格模型在許多領域，包括CAD/CAM、電腦繪圖、虛擬實境、電腦視覺化、醫學影像工程、快速原型製作、逆向工程…等，然而針對不同的需求，網格模型的品質都有一定程度的要求，以利於一些後續的處理，如網格切層、網格建構、面與特徵邊界擷取與網格模型偵錯。電腦輔助設計(CAD)與電腦輔助製造(CAM)目前在工業界已廣泛被使用，在逆向工程方面，首先要將物體模型利用三次元掃描設備將其點座標資料掃描進電腦並建成網格模型，在從網格模型建成曲面模型中其主要的困難點在於如何建構一個具有正確幾何與拓樸資料且與原來物體形狀相同的電腦模型。本研究使用本實驗室現有的逆向工程軟體RevCAD，主要探討、測試及修改其中亂點資料三角網格化功能，而本論文中假設所處裡的數位掃描所得到的亂點資料除了具有三維的點座標以外，將不具有任何其他可利用的幾何資訊，在這樣的前提下，目標發展研究一套完整的三角網格化演算法，並且合乎程式的演算效率與三角網格的品質，因此將可以解決所有廣泛的網格模型重建問題，可加速網格模型重建，以提高逆向工程的效率。

關鍵字

拓樸資料 ； 三角網格化 ； 網格重建 ； 逆向工程 ； CAD / CAM

並列摘要

The triangular model has the property of simple structure, easy treatment, and forming the any object, which makes it a popular model in different fields, including computer-aided design(CAD), computer aided manufacturing CAM, computer drawing, fictitious real border, visualization, medical image processing, rapid prototyping and reverse engineering. In reverse engineering, the triangulation of irregular cloud points is one of the important issues which should be dealt with. The main issue of triangulation is how to generate a geometrical model with a correct topology and geometry that is faithful to describe the original object which is complex in shape.
The purpose of this study is to test, analyse and revise a triangulation algorithm existing in RecCAD, a reverse engineering software developed in house. The input of this algorithm is a set of cloud point, without any geometric or relationship among the points. The output of this algorithm is a set of triangular meshes. The problem on the original algorithm is divided into three groups. Each of the problems in the three groups are carefully analysed and tested. Appropriate strategy for each of the problem is proposed and verified. Up to 50 set of cloud points, ranging from 1,800 to 500,000 points, have been tested, and the results have demonstrated the improvement of the proposed triangulation algorithm.

並列關鍵字

Reverse Engineering ； CAD / CAM ； Triangulation ； Surface Reconstruction ； STL data

參考文獻

[4] U. Adamy, J. Giesen and M. John, “New Techniques for Topologically Correct Surface Reconstruction”, Proceedings of the IEEE Visualization Conference, pp. 373-380, 2000.

[5] T. P. Fang and L. A. Piegl, “Delaunay Triangulation Using a Uniform Grid”, IEEE Computer Graphics and Applications, Vol. 13, No. 3, pp. 36-47, 1993.

[6] T. P. Fang and L. A. Piegl, “Delaunay Triangulation in Three Dimensions”, IEEE Computer Graphics and Applications, Vol. 13, No. 11, No.5, pp. 62-69, 1995.

[7] J. Huang and C. H. Menq, “Combinational Manifold Mesh Reconstruction and Optimization from Unorganized Points with Arbitrary Topology”, Computer-Aided Design, Vol. 34, pp. 149-165, 2002.

[8] B.Guo, J. Menon and B. Willette, “Surface Reconstruction Using Alpha Shapes”, Computer Graphics Forum, Vol. 16, No. 4, pp. 177-190, 1997.