應用具平行運算架構之區域成長演算法於亂點網格重建技術

A Region Growing Algorithm using Parallel Computation for Surface Reconstruction from Unorganized Points

簡宏哲(Hung-Je Jian)

指導教授 ： 姚宏宗

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

摘要

本論文提出一套基於平行運算架構的區域成長演算法應用於網格重建技術，本論文的平行運算架構分為CPU平行運算與GPU平行運算兩種。首先，針對多核心中央處理器開發Multi-core based平行化區域成長，利用Hilbert curve對點資料分區，每個核心負責重建一個區域的點資料，並且每個核心同步計算，最後再合併所有的網格區域。近年來由於電腦圖學技術的快速發展，繪圖處理器具備浮點運算能力與可程式化的突破，使得平行運算的能力明顯提升；因此本論文創新地改良區域成長演算法配合繪圖處理器的執行架構，開發GPU-based平行化區域成長法。在GPU-based的重建過程中，每個點資料皆同步進行區域成長，然後再移除重疊的網格，並進行孔洞修補，最後形成完整的網格模型。 論文中實際使用三維掃描機獲取物體的表面資訊，利用其掃描點進行測試，藉以說明本文演算法的品質與效率。同時與過去的亂點重建演算法比較及分析，說明本文演算法在效率上的優勢，並且驗證其實用性。 關鍵字：亂點重建、區域成長、平行運算

關鍵字

平行運算 ； 區域成長 ； 亂點重建

並列摘要

A region growing algorithm with parallel computing is proposed in this thesis for the surface reconstruction from unorganized point clouds. The parallel computing architecture of this thesis can be divided into two modes: multi-core parallel computing and GPU-based parallel computing. First, for the development of multi-core region growing algorithm, Hilbert curve was used to segment point clouds dependent on the number of CPU. Each CPU is responsible for the reconstruction of a given region. Finally, all patches can be merged into single mesh by stitching the boundaries. Moreover, with the significant improvement of the graphic processor about floating point calculation and parallel computing capability, this thesis proposes a novel parallel computing architecture for the region growing algorithm based on GPU calculation structure. During the process, each point will be expanded synchronously until all patches overlap with one another completely. Then the overlapped patches will be removed and holes will be filled during the GPU-based calculation. Finally, a complete surface model will be constructed.
In order to validate the parallel region growing algorithm proposed, unorganized point cloud was captured by a 3D scanner and reconstructed with the parallel region growing algorithm. According to the result, the algorithm proposed by this research has better performance compared to other previous researches.

Keywords: surface reconstruction, region growing algorithm, parallel computation.

並列關鍵字

parallel computation ； region growing algorithm ； surface reconstruction

參考文獻

[2] N. Amenta, S. Choi, and R. K. Kolluri, "The power crust, unions of balls, and the medial axis transform," Computational Geometry, vol. 19, pp. 127-153, 2001.

[3] M. Gopi, S. Krishnan, and C. T. Silva, "Surface Reconstruction based on Lower Dimensional Localized Delaunay Triangulation," presented at the EUROGRAPHICS 2000, 2000.

[4] C.-C. Kuo and H.-T. Yau, "Reconstruction of Virtual Parts from Unorganized Scanned Data for Automated Dimensional Inspection," Journal of Computing and Information Science in Engineering, vol. 3, pp. 76-86, 2003.

[5] C. Buchart, D. Borro, and A. Amundarain, "GPU Local Triangulation: an interpolating surface reconstruction algorithm," presented at the Computer Graphics Forum, 2008.

[7] L. Zhang, L. Liu, C. Gotsman, and H. Huang, "Mesh reconstruction by meshless denoising and parameterization," Computers & Graphics, vol. 34, pp. 198-208, 2010.