空間散亂點集Delaunay三角剖分的算法優(yōu)化及實現(xiàn).pdf

1、三角剖分在曲面重構(gòu)、三維有限元方法的預處理、醫(yī)學可視化及地理信息系統(tǒng)(GIS)等領域有廣泛的應用。Delaunay三角剖分是計算機輔助幾何設計、幾何造型及計算機圖形學中的重要研究內(nèi)容之一。對于設計一個三角剖分算法來說，最重要的就是其復雜度低和高質(zhì)量網(wǎng)格的形成。Delaunay三角剖分算法由于其良好的優(yōu)化特性受到青睞，本文對其算法進行研究及優(yōu)化改進有著重要的理論意義和重大的應用價值。 本文討論的空間三維散亂點Delaunay三角剖

2、分的方法，由散亂點的導入、三角剖分到最后的結(jié)果顯示輸出，涉及到了計算幾何、計算機圖形學及Direct3D編程等相關知識。平面的Delaunay三角剖分已經(jīng)較為成熟，而三維Delaunay三角剖分仍需進一步完善和改進，這正是本文對其進行研究的目的。 本文在詳細研究和分析了典型的Delaunay三角剖分算法的思想后，針對增量算法中的關鍵問題提出改進的方法，從降低算法的時間復雜度的角度出發(fā)，以點定位搜索這一關鍵問題為切入點，提出新的改

3、進搜索的方法，該算法利用四面體三角面的法矢與該面的點到插入點之間形成的向量的夾角來確定定位方向，不需額外的搜索數(shù)據(jù)結(jié)構(gòu)，且對于每個搜索四面體只需三個面的法矢和夾角的計算，減少了搜索過程中的計算量，且定位的路徑較優(yōu)，有效提高了算法的效率，使整個Delaunay三角剖分算法的時間復雜度約為O(NL12)，接近線性時間。 算法的實現(xiàn)和結(jié)果的輸出顯示是一個重要的環(huán)節(jié)，本文集成了Direct3D與MFC單文檔框架，并基于該框架建立三維散亂