簡介這份資源面向計算機圖形學(xué)、GIS與測繪方向的開發(fā)者及學(xué)生提供一套基于VC 6.0實現(xiàn)的快速TIN三角網(wǎng)生成算法工程可用于地形建模、點云三角剖分與Delaunay構(gòu)網(wǎng)等場景的學(xué)習(xí)與二次開發(fā)。壓縮包共88個文件、約769KB包含13個cpp與13個h源碼文件覆蓋頂點、邊、三角形、三角網(wǎng)及節(jié)點樹等核心類另有obj、sbr、pdb等編譯中間文件與兩個可執(zhí)行程序以及rc、res、ico等界面資源工程結(jié)構(gòu)完整可直接用VC 6.0打開編譯運行。目前已有1320人學(xué)習(xí)下載。讀者可從中獲得Delaunay三角剖分的完整實現(xiàn)思路包括三角形與邊結(jié)構(gòu)設(shè)計、點插入與構(gòu)網(wǎng)流程、三角網(wǎng)組織方式以及對話框輸入與視圖繪制等交互模塊便于對照源碼理解算法細節(jié)并移植到自己的項目中。1. 三角網(wǎng)生成為什么“最快”往往不是你以為的那個快提到 TIN 三角網(wǎng)生成多數(shù)人第一反應(yīng)是 Delaunay 三角剖分接著想到逐點插入、翻邊、空圓檢測這一整套流程。但真正在工程里跑過大規(guī)模點云的人會發(fā)現(xiàn)一個反直覺的事實決定整體速度的往往不是剖分算法本身而是點定位和數(shù)據(jù)結(jié)構(gòu)。同樣一套 Delaunay 邏輯換個定位策略耗時能差出一個數(shù)量級。這也是“最快的 TIN 三角網(wǎng)生成算法”這類資源值得深挖的原因——它比拼的不是某個玄學(xué)常數(shù)而是把點定位、邊翻轉(zhuǎn)、內(nèi)存布局這幾件事壓到極限。搞懂它你才知道自己項目里那幾秒卡在哪而不是對著 profiler 里的黑匣子干瞪眼。2. 點定位增量插入為什么總在“找三角形”上翻車增量式 Delaunay 的核心循環(huán)只有三步取一個未插入點、在現(xiàn)有三角網(wǎng)里找到包含它的三角形、插入后修復(fù)局部 Delaunay 性質(zhì)。三步里第三步的翻邊是局部的、代價可控第二步的點定位卻是全局的——每插一個點都要重新找一次。點數(shù)到十萬級定位次數(shù)就是十萬次單次定位哪怕只慢幾微秒累計起來就是肉眼可見的卡頓。所以“最快”的第一個戰(zhàn)場一定在點定位。2.1 從線性掃描到行走定位最樸素的定位是遍歷所有三角形做點在三角形內(nèi)測試復(fù)雜度 O(n)n 是當(dāng)前三角形數(shù)。點數(shù)一多直接崩。常見的改進是“行走”walk從上次插入的三角形出發(fā)沿著重心方向一步步走到目標(biāo)三角形。行走的平均步數(shù)和點的空間分布強相關(guān)均勻分布下接近常數(shù)但遇到長條形三角形或點云局部密集時會退化。// 行走定位的骨架從 start 三角形出發(fā)朝目標(biāo)點 p 逼近 Triangle* locate(Triangle* start, const Point p) { Triangle* t start; while (true) { // 依次檢查三條有向邊p 落在某條邊的外側(cè)就跨過去 for (int i 0; i 3; i) { if (orient(t-v[i], t-v[(i1)%3], p) 0) { t t-neighbor[i]; // 跨到相鄰三角形 goto next_triangle; // 換一個三角形繼續(xù) } } return t; // 三條邊都在內(nèi)側(cè)命中 next_triangle:; } }這段代碼的關(guān)鍵在orient它用有向面積判斷點在有向邊的哪一側(cè)返回負值說明點在外側(cè)需要跨過這條邊。neighbor[i]是與第 i 條邊相鄰的三角形這個鄰接關(guān)系必須在插入和翻邊時同步維護否則行走會走進死胡同。行走的代價取決于起點離目標(biāo)多近所以“記住上次插入的三角形”這個看似不起眼的優(yōu)化實際收益很大——點云若有一定空間局部性起點往往就在目標(biāo)附近。2.2 為什么還要一張輔助網(wǎng)格行走在均勻點云上表現(xiàn)不錯但真實數(shù)據(jù)經(jīng)常是局部密、局部疏。密集區(qū)三角形小、行走步數(shù)多稀疏區(qū)三角形大、一步跨很遠。為了把最壞情況壓住常見的實現(xiàn)思路是在三角網(wǎng)之上再疊一層均勻網(wǎng)格bucket grid每個格子記錄落在其中的三角形或點定位時先用 O(1) 的除法算出目標(biāo)點所在格子再從格子里的候選三角形開始行走。這樣行走的起點被約束在目標(biāo)附近步數(shù)基本與點云密度無關(guān)。網(wǎng)格的粒度是個取舍格子太粗候選三角形多退化成小范圍掃描格子太細內(nèi)存開銷和跨格維護成本上升。我一般會按“平均每個格子落 1 到 2 個點”來定格子尺寸這個經(jīng)驗值在多數(shù)點云上能把定位壓到接近常數(shù)時間。資源里若強調(diào)“最快”大概率就是在這層網(wǎng)格的尺寸和維護策略上做了針對性處理而不是單純換了個剖分公式。2.3 定位失敗時看什么定位環(huán)節(jié)出問題現(xiàn)象通常是死循環(huán)或越界。死循環(huán)多半是鄰接關(guān)系不一致——某次翻邊后neighbor指針沒更新行走在幾個三角形之間來回跳。越界則常發(fā)生在網(wǎng)格邊界目標(biāo)點落在網(wǎng)格外時除法算出負索引。排查時先驗證三角網(wǎng)的拓撲一致性每條內(nèi)部邊被兩個三角形共享且雙方的neighbor互指。這個檢查寫起來不復(fù)雜但能一次性揪出大部分定位 bug。3. 翻邊與棧局部修復(fù)為什么能保證全局正確插入一個點后只有與它相連的三角形可能違反空圓性質(zhì)所以修復(fù)是局部的。這是 Delaunay 增量算法能 work 的根本原因全局性質(zhì)由局部操作逐步累積保證不需要每次重算整張網(wǎng)。理解這一點才能理解為什么翻邊棧的管理方式會直接影響性能。3.1 空圓檢測與翻邊的判定對每條新產(chǎn)生的邊檢查其對頂點是否落在當(dāng)前三角形的外接圓內(nèi)。若在圓內(nèi)說明這條邊不滿足 Delaunay 條件需要翻轉(zhuǎn)成另一條對角線。翻轉(zhuǎn)后新的邊又可能違反條件于是把相關(guān)邊壓棧繼續(xù)處理。// 翻邊判定點 d 是否在三角形 abc 的外接圓內(nèi) bool inCircle(const Point a, const Point b, const Point c, const Point d) { // 用行列式判斷符號取決于三點的朝向 double det orient(a, b, c); double adx a.x - d.x, ady a.y - d.y; double bdx b.x - d.x, bdy b.y - d.y; double cdx c.x - d.x, cdy c.y - d.y; double abdet adx * bdy - bdx * ady; double bcdet bdx * cdy - cdx * bdy; double cadet cdx * ady - adx * cdy; double alift adx*adx ady*ady; double blift bdx*bdx bdy*bdy; double clift cdx*cdx cdy*cdy; double inc alift*bcdet blift*cadet clift*abdet; return (det 0) ? (inc 0) : (inc 0); // 朝向決定符號 }orient給出三點朝向inc是四點共圓行列式的值。注意符號處理如果三角形是順時針判定條件要反過來否則會把該翻的邊漏掉最終生成的網(wǎng)不是 Delaunay 的。這類符號錯誤在浮點坐標(biāo)下尤其隱蔽因為大部分邊判定正確只有少數(shù)邊翻錯肉眼很難發(fā)現(xiàn)但后續(xù)定位會因此變慢。3.2 棧的順序為什么影響速度翻邊用棧來管理待處理邊棧的壓入順序決定了處理順序。常見的實現(xiàn)思路是后進先出因為新翻出來的邊往往和剛處理的邊空間相鄰連續(xù)處理能提高緩存命中。如果改成隊列處理順序在空間上跳躍緩存不友好速度會掉。這個差異在小數(shù)據(jù)上看不出來百萬級點云上能差出百分之十幾。另一個細節(jié)是去重同一條邊可能被多次壓棧重復(fù)處理純屬浪費?？梢栽趬簵Ｇ坝靡粋€標(biāo)記位記錄該邊是否已在棧中出棧時清標(biāo)記。這個優(yōu)化不改變正確性但能砍掉可觀的冗余翻邊。3.3 退化情形共圓與共線四個點嚴格共圓時翻不翻邊都滿足 Delaunay 條件算法可能陷入來回翻轉(zhuǎn)。標(biāo)準做法是加一個確定性規(guī)則比如只在嚴格大于時翻轉(zhuǎn)等于時保持原狀。共線三點則根本無法構(gòu)成三角形插入前要過濾掉否則外接圓半徑無窮大判定失效。真實點云里這類退化不算罕見尤其是規(guī)則采樣或 CAD 導(dǎo)出的數(shù)據(jù)資源若聲稱“最快”通常也會在這些邊界條件上做防御避免為了正確性反復(fù)回退。4. 內(nèi)存布局為什么指針滿天飛會拖垮“最快”算法邏輯再漂亮數(shù)據(jù)在內(nèi)存里散著放緩存未命中一樣能把速度吃掉。三角網(wǎng)天然是圖結(jié)構(gòu)三角形之間互相引用最直觀的寫法是每個三角形存三個指針指向鄰居。這種寫法在教科書里沒問題在追求“最快”的實現(xiàn)里往往是瓶頸。4.1 從指針到索引把指針換成數(shù)組索引好處是三角形可以連續(xù)存放在一塊內(nèi)存里遍歷時順序訪問緩存友好。鄰接關(guān)系存成int索引體積也比指針小。插入新三角形時往數(shù)組尾部追加刪除時用交換到尾部再彈出避免中間空洞。struct Triangle { int v[3]; // 三個頂點索引 int nb[3]; // 三條邊的鄰接三角形索引-1 表示邊界 bool alive; // 刪除標(biāo)記配合交換刪除 }; std::vectorTriangle tris; // 連續(xù)存儲遍歷友好頂點坐標(biāo)單獨放一個std::vectorPoint三角形只存索引。這樣翻邊和定位時訪問頂點是另一塊連續(xù)內(nèi)存雖然多一次間接尋址但兩塊內(nèi)存各自連續(xù)整體局部性仍然好于指針亂飛。alive標(biāo)記配合交換刪除能讓tris始終保持緊湊遍歷時不用跳過大量空洞。4.2 頂點重排與緩存行如果點云插入順序是隨機的頂點數(shù)組的訪問模式也會隨機。一個進階做法是插入完成后按空間位置對頂點重排比如按網(wǎng)格的 Morton 序讓空間相鄰的點在內(nèi)存里也相鄰。這對后續(xù)的遍歷、導(dǎo)出、渲染都有好處。代價是重排后所有索引要跟著改實現(xiàn)上多一層映射。緩存行通常是 64 字節(jié)一個Triangle若控制在 24 到 32 字節(jié)一個緩存行能裝兩個左右遍歷時命中率明顯提升。這也是為什么很多高性能實現(xiàn)刻意把結(jié)構(gòu)體壓小寧可多一次計算也不多存冗余字段。4.3 邊界處理與哨兵三角網(wǎng)的凸包邊界沒有鄰居nb里填 -1每次訪問都要判空。另一種思路是引入一個虛擬的“外部三角形”作為所有邊界邊的鄰居這樣鄰接關(guān)系永遠有效行走和翻邊不用到處判 -1。代價是外部三角形的頂點是無窮遠點涉及它的幾何計算要特殊處理。兩種做法各有取舍資源里若追求極致速度大概率選了后者來消除分支預(yù)測失敗——分支在熱循環(huán)里也是成本。5. 避坑TIN 實現(xiàn)里那些讓人后悔藥的細節(jié)5.1 現(xiàn)象小數(shù)據(jù)正常大數(shù)據(jù)生成結(jié)果有洞原因浮點精度導(dǎo)致orient在近共線時符號抖動翻邊判定錯亂局部三角形被誤刪或漏建。解決對orient加一個與坐標(biāo)量級相關(guān)的容差近零時按共線處理或者用自適應(yīng)精度謂詞只在接近零時提高計算精度。不要全局放大容差那會引入新的錯誤。5.2 現(xiàn)象定位偶爾死循環(huán)CPU 跑滿原因翻邊后鄰接指針沒同步更新行走在幾個三角形間循環(huán)。解決每次翻邊后立即更新受影響的nb并在調(diào)試版里加一個行走步數(shù)上限超限就 dump 當(dāng)前三角形和鄰接關(guān)系通常一眼能看出哪條邊指錯了。5.3 現(xiàn)象插入順序一變速度差好幾倍原因行走定位的起點依賴上次插入位置隨機順序下起點離目標(biāo)遠步數(shù)多。解決插入前按空間順序如網(wǎng)格序或 Hilbert 序?qū)c排序讓相鄰插入的點在空間上也相鄰行走步數(shù)大幅下降。這個改動往往比換算法更立竿見影。5.4 現(xiàn)象內(nèi)存占用隨點數(shù)暴漲原因刪除的三角形只標(biāo)記不回收tris數(shù)組只增不減。解決用交換刪除保持數(shù)組緊湊或定期做一次壓縮。注意壓縮后所有索引要重映射別在壓縮過程中還持有舊索引。5.5 現(xiàn)象邊界附近的點定位越界原因輔助網(wǎng)格的索引計算沒處理負坐標(biāo)或超出范圍的點。解決網(wǎng)格索引做 clamp或者在外圍加一圈哨兵格子把越界點歸到邊界格子里避免負索引訪問。6. 設(shè)計取舍快是壓出來的不是算出來的回頭看“最快的 TIN 三角網(wǎng)生成算法”這個說法本身就有誤導(dǎo)性。Delaunay 的數(shù)學(xué)定義是固定的能變的只有實現(xiàn)路徑點定位用行走還是網(wǎng)格加速、鄰接用指針還是索引、翻邊棧怎么排、退化情形怎么兜底。每一處都是取舍沒有免費的午餐。網(wǎng)格加速換來定位的常數(shù)時間代價是額外內(nèi)存和維護成本索引化換來緩存友好代價是多一層間接尋址和重排邏輯哨兵邊界消除分支代價是幾何計算要處理無窮遠點。我一般會這么判斷先看數(shù)據(jù)規(guī)模和分布均勻小數(shù)據(jù)用樸素行走就夠別過度設(shè)計十萬級以上或分布不均再上網(wǎng)格和空間排序。驗證方法也很直接——構(gòu)造幾組不同分布的點云均勻、聚集、規(guī)則網(wǎng)格、近共線分別測定位步數(shù)、翻邊次數(shù)和總耗時看哪一項隨規(guī)模增長得最快瓶頸就在那。別只看總時間總時間會把真正的熱點藏起來。血淚經(jīng)驗是正確性永遠排在速度前面。一個翻錯邊的網(wǎng)可能跑得飛快但后續(xù)所有基于它的查詢都會悄悄出錯等到發(fā)現(xiàn)時已經(jīng)很難回溯是哪一步翻錯了。從那以后我每次改完定位或翻邊邏輯都強制先跑一遍拓撲一致性檢查和空圓抽查再談優(yōu)化。希望幫到你。本文還有配套的精品資源點擊獲取