近年來由於三維掃描技術的快速發展，對於大規模點雲資料處理技術的需求日益增大，越來越多的應用是以點雲資料來儲存與表達三維模型，例如：三維地形圖、電腦輔助設計(CAD)、醫學影像、虛擬實境以及數位典藏資料庫等等方面之應用。本論文提出一個新的沒有組織與法向量資訊之點雲表面重建方法，使用者可選擇依自己喜好來決定參數或是選擇不輸入參數（由程式自動取得），本方法只需要點雲的資料即可，不需要其他額外的資訊就可進行表面重建。點雲表面重建程序可分為三個主要步驟：1)利用中值平移分類法將點雲資料分成多個獨立之近似平坦區域，其目的在避免產生特徵區域重建錯誤以及解決以往在特徵區域出現過度平滑化(over-smoothing)的問題，為了得到更好的分類結果，我們先取得點雲拉普拉斯座標，然後以次座標進行區域分類程序。2)利用區域性參數化技術 (local parameterization)將三維近似平坦區域攤平(mapping)到一個盤子狀(disk-like)的二維區塊。3)然後利用二維的狄龍尼三角化演算法(Delaunay triangulation)來進行區域的表面重建，最後將每個區塊整合起來就完成了表面重建。因此，我們將表面重建問題轉換成簡單的二維區域三角化問題，並且解決了特徵區域過度平滑的問題。

The recent advances in 3D scanning technologies have led to an increasing need for techniques capable of processing massive point cloud data and point cloud are receiving a growing amount of attention as a representation in many relative applications such as topography, computer-aided design (CAD), medical visualization, virtual reality and digital archive. This thesis introduces a novel unorganized point cloud reconstruction scheme based on the mean-shift clustering approach. This scheme does not request the users to input or tune any parameters (they are determined automatically). This scheme only takes the point cloud data as inputs. There are three main steps in the reconstruction process. First, the point cloud is decomposed into several near-flat and disk-like patches by utilizing the mean-shift clustering approach in order to avoid repairing the shape edges. To obtain better clustering results, the clustering is applied on the Laplacian coordinates of sampled points. Second, each separated patches are parameterized on 2D disk using local parameterization approach. Third, adopt Delaunay triangulation to construct the connectivity of surface patch. Eventually, the triangle mesh of point cloud is obtained by merging all separated patches. The proposed approach transforms the 3D surface reconstruction problem into a simple 2D local patch triangulation problem and can avoid over-smoothing on shape edges.

Amenta, N, Bern, M, and Kamvysselis, M.: A new Voronoi-based surface reconstruction algorithm. SIGGRAPH ’98, pp. 415-421, 1998.
Amenta, N. and Bern M.: Surface reconstruction by Voronoi filtering, Discrete and Computational Geometry. Vol. 22, pp. 481-504, 1999.
Amenta, N. and Kolluri, R.: The medial axis of a union of balls, Computational Geometry: Theory and Applications. Vol. 20, No. 1-2, pp. 25-37, 2001.
Arya S., Mount D. M., Netanyahu N. S., Silverman R., and Wu. A. Y.: An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM, 45(6):891–923, 1998.
Bajaj, C., Bernardini, F., and Xu, G.: Automatic reconstruction of surfaces and scalar fields from 3d scans. In Proceedings of ACM SIGGRAPH, pp. 109–118, 1995.
Bernardini, F., Mittleman, J., Rushmeier, H., Silva, C., and Taubin, G.: The ball-pivoting algorithm for surface reconstruction. IEEE Transactions on Visualization and Computer Graphics, Vol. 5, No. 4, pp. 349-359, 1999.
Carr, J.C., Beatson, R.K., Cherrie, J.B., Mitchell, T.J., Fright, W.R., McCallum, B.C. and Evans, T.R.: Reconstruction and representation of 3D objects with radial basis functions. SIGGRAPH’01, pp. 67-76, 2001.
Carr, J.C., Beatson, R.K., McCallum, B.C., Fright, W.R., McLennan, T.J. and Mitchell, T.J.: Smooth surface reconstruction from noisy range data. ACM GRAPHITE 2003, pp. 119-126, Melbourne, Australia, 2003.
Curless, B. and Levoy, M.: A volumetric method for building complex models from range images. SIGGRAPH ’96, pp. 303-312, 1996.
Comaniciu, D. and Meer, P.: Mean Shift Analysis and Applications. Proc. Seventh Int'l Conf. Computer Vision, pp. 1197-1203, 1999.
Comaniciu, D. and Meer, P.: Mean shift: A robust approach toward feature space analysis. IEEE Trans. Pattern Anal. Machine Intell., Vol. 24, pp. 603–619, 2002.
Floater, M. S. and Reimers, M.: Meshless parameterization and surface reconstruction. Computer Aided Geometric Design, Vol. 18, pp. 77–92, 2001.
Georgescu, B., Shimshoni, I. and Meer, P.: Mean shift based clustering in high dimensions: a texture classification example. Proc. of International Conference on Computer Vision, pp. 456–463, 2003.
Hoppe, H., DeRose, T., Duchamp, T., McDonald, J. and Stuetzle, W.: Surface reconstruction from unorganized points. ACM SIGGRAPH’92, pp. 71-78, 1992.
Hormann, K. and Reimers, M.: Triangulating point clouds with spherical topology. In Proceedings of Curve and Surface Design, pp. 215–224, 2002.
Kuo, C.C. and Yau, H.T.: A Delaunay-based region-growing approach to surface reconstruction from unorganized points. Computer-Aided Design, vol. 37, pp. 825-835, 2005.
Kuo, C.C. and Yau, H.T.: A New Combinatorial Approach to Surface Reconstruction with Sharp Features. IEEE Trans. Vis. Comput. Graph., pp. 73-82. 2006.
Sorkine O. and Cohen-Or D.: Least-squares meshes. In Proceedings of Shape Modeling International, pp. 191–199, 2004.
Sorkine O.: Laplacian mesh processing. In STAR Proceedings of Eurographics’05, pp. 53–70, Sept. 2005.
Zwicker, M. and Gotsman, C.: Meshing Point Clouds Using Spherical Parameterization. Proceedings of the Eurographics Symposium on Point-Based Graphics, Zurich, June 2004.