差分坐標(Differential Coordinates)以其相關之拉普拉斯運算子在三維數位幾何模型上已有許多的研究及應用，頂點的差分坐標計算是由頂點與拓撲上之相鄰點的相對位置關係所求得，因此頂點之差分坐標代表了區域曲面起伏變化情況，差分坐標其方向會近似於區域法線方向而其長度會近似予區域平均曲率，此兩項資訊為點雲資料重要幾何資訊。
對一個沒有任何連接資訊之點雲資料，如何於拓撲結構上求得適當的鄰近點資訊以正確計算出頂點之差分坐標，至今仍是一個問題。本論文對此問題提出一個鄰近點搜尋演算法，使用智慧型基因演算法(Intelligent Evolutionary Algorithm, IEA)，經由目標函式評估鄰近點組合，將問題編碼後經選擇、交配、突變、取代等演化程序，獲得一組最佳的鄰近點組合。
透過本研究方法可同時獲得點雲三大重要資訊：鄰近點、表面法線向量及表面曲率，透過這三項資訊可以運用於多項點雲資料的相關應用上，例如：點雲資料平滑處理、點雲資料攤平、點雲資料建模與點雲資料特徵擷取。由本實驗結果得知，透過本研究所提出的方法所計算出差分坐標的結果較其他方法正確，因此也比其他方法更能成功地應用在這些相關領域上。

Many digital geometric processinges (DGP) that process polygon models benefit greatly from the differential coordinates and its associated Laplacian operator. The differential coordinate is an intrinsic surface representation, which encodes each vertex as a local coordinate relative to its topological neighbors. In the area of differential geometry, it is well-known that the direction of differential coordinate approximates the direction of surface normal and the magnitude proportionally approximates the mean curvature. The normal and curvature are significant geometry information for 3D point clouds.
Given a point cloud data sampled from an unknown surface, the problem is how to determine proper topological neighbors of a vertex for accurately calculating the differential coordinate. In this thesis, we introduce a novel approach to select proper neighbor vertices by optimizing an objective function defined according to the properties of differential coordinate. The neighbor selection is regarded as an optimization problem and solved by a genetic algorithm. Our approach can obtain three most important geometry information for point clouds: surface normal, curvature and connectivity (point neighbors). The experimental results show that the generated differential coordinates can faithfully represent the geometry of 3D point models, and thus are very helpful for the related applications such as meshless smoothing, meshless parameterization, and feature detection and modeling.

[1] Allgower, E. L., and P. H. Schmidt. 1985. An algorithm for piecewise linear approximation of an implicitly defined manifold. SIAM Journal of Numerical Analysis 22 (2):322-335.
[2] Bajaj, C. L., F. Bernardini, and G. Xu. 1995. Automatic reconstruction of surfaces and scalar fields from 3D scans. Proceedings of the 22nd annual conference on Computer graphics and interactive techniques:109-118.
[3] Chen, C. Y., and K. Y. Cheng. 2005. A sharpness dependent filter for mesh smoothing. Computer Aided Geometric Design 22 (5):376-391.
[4] Desbrun, M., M. Meyer, P. Schroder, and A. H. Barr. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. Proceedings of the 26th annual conference on Computer graphics and interactive techniques:317-324.
[5] Dey, T. K., G. Li, and J. Sun. 2005. Normal estimation for point clouds: a comparison study for a voronoi based method. Eurographics Symposium on Point-Based Graphics:39-46.
[6] Floater, M. S. 1997. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design 14 (3):231-250.
[7] Michael S. Floater. 2003. Mean value coordinates. Computer Aided Geometric Design 20 (1):19-27.
[8] Floater, M. S., and K. Hormann. 2005. Surface parameterization: a tutorial and survey. Advances in Multiresolution for Geometric Modelling:157-186.
[9] Floater, M. S., and M. Reimers. 2001. Meshless parameterization and surface reconstruction. Computer Aided Geometric Design 18 (2):77-92.
[10] Guo, X., X. Li, Y. Bao, X. Gu, and H. Qin. 2006. Meshless Thin-Shell Simulation Based on Global Conformal Parameterization. IEEE Transactions on Visualization and Computer Graphics:375-385.
[11] Halir, R., and J. Flusser. 1998. Numerically stable direct least squares fitting of ellipses. Proc. Int. Conf. in Central Europe on Computer Graphics, Visualization and Interactive Digital Media (WSCG98):125–132.
[12] Hildebrandt, K., and K. Polthier. 2004. Anisotropic Filtering of Non-Linear Surface Features. Computer Graphics Forum 23 (3):391-400.
[13] Ho, S. Y., L. S. Shu, and J. H. Chen. 2004. Intelligent evolutionary algorithms for large parameter optimization problems. Evolutionary Computation, IEEE Transactions on 8 (6):522-541.
[14] Holland, J. H. 1975. Adaptation in Natural and Artificial Systems. Ann Arbor MI: University of Michigan Press.
[15] Hoppe, H., T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. 1992. Surface reconstruction from unorganized points. Proceedings of the 19th annual conference on Computer graphics and interactive techniques:71-78.
[16] Hormann, K., and M. Reimers. 2002. Triangulating Point Clouds with Spherical Topology. Proceedings of curve and surface design, Saint Malo. pp.?
[17] Lipman, Y., D. Cohen-Or, and D. Levin. 2006. Error bounds and optimal neighborhoods for MLS approximation. Proceedings of the fourth Eurographics symposium on Geometry processing:71-80.
[18] Lipman, Y., O. Sorkine, D. Cohen-Or, D. Levin, C. Rossi, and H. P. Seidel. 2004. Differential coordinates for interactive mesh editing. Shape Modeling Applications, 2004. Proceedings:181-190.
[19] Mitra, N. J., and A. Nguyen. 2003. Estimating surface normals in noisy point cloud data. Proceedings of the nineteenth annual symposium on Computational geometry:322-328.
[20] Myers, M., M. Desbrun, P. Schroder, and A. Barr. 2002. Discrete differentialgeometry operators for triangulated 2-manifolds. Visualization and mathematics 3:34–57.
[21] Ohbuchi, R., A. Mukaiyama, and S. Takahashi. 2002. A Frequency-Domain Approach to Watermarking 3D Shapes. Computer Graphics Forum 21 (3):373-382.
[22] Ohtake, Y., A. Belyaev, M. Alexa, G. Turk, and H. P. Seidel. 2003. Multi-level partition of unity implicits. International Conference on Computer Graphics and Interactive Techniques:463-470.
[23] Pauly, M., M. Gross, L. P. Kobbelt, E. T. Hochschule, and S. Zurich. 2002. Efficient simplification of point-sampled surfaces. IEEE Visualization (VIS):163-170.
[24] Praun, E., H. Hoppe, and A. Finkelstein. 1999. Robust mesh watermarking. Proceedings of the 26th annual conference on Computer graphics and interactive techniques:49-56.
[25] Rao, C. R. 1947. Factorial experiments derivable from combinatorial arrangements of arrays. Supplement to the Journal of the Royal Statistical Society 9:128-139.
[26] Schneider, R., and L. Kobbelt. 2001. Geometric fairing of irregular meshes for free-form surface design. Computer Aided Geometric Design 18 (4):359-379.
[27] Sorkine, O. 2005. Laplacian mesh processing. Eurographics State-of-the-Art Report:53-70.
[28] Sorkine, O., D. Cohen-Or, Y. Lipman, M. Alexa, C. Rossl, and H. P. Seidel. 2004. Laplacian surface editing. Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing:175-184.
[29] Sorkine, O., D. Cohen-Or, and S. Toledo. 2003. High-pass quantization for mesh encoding. Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing:42-51.
[30] Taguchi, G., and S. Konishi. 1987. Orthogonal arrays and linear graphs: American Supplier Institute Dearborn, Mich.
[31] Taubin, G. 1995. A signal processing approach to fair surface design. Proceedings of the 22nd annual conference on Computer graphics and interactive techniques:351-358.
[32] Zwicker, M., and C. Gotsman. 2004. Meshing Point Clouds Using Spherical Parameterization. Proc. Eurographics Symp. Point-Based Graphics:173-180.