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