浙江大學碩士學位論文辯論 辯論人：楊振羽 導師：彭群生教授 鄭文庭副研究員基于點表示幾何體的造型技術I緒論背景根本流程主要研究內容背景傳統圖形學需要解決的問題高效率繪制高度復雜的物體及場景減少冗余，節約存儲空間新的繪制體系結構的需求直接繪制由3D掃描設備生成的密集點云背景(二)基于點的表示與繪制的優點繪制體系簡單拓撲結構簡單適合于表示外表幾何及光照細節高度復雜的模型適合混合繪制很少冗余硬件支持根本流程獲取來源于3D掃描設備或現存的幾何模型處理前期處理：實體表示后期處理：實體造型繪制

獲取

處理

點云表示模型正向Warping過濾、光影計算可見性剔除圖象重構幀緩存混合表示網格表示隱函數表示造型處理：光順、除噪、變形、編輯等傳統技術處理…傳統技術處理配準映射到幾何錯誤校正簡化、去冗余紋理網格化原始點云三維掃描設備深度相機相機其它模型深度圖象光影照片三維點集直接點云表示流程圖論文工作范圍獲取處理繪制主要研究內容 基于點表示幾何體的外表表示以及在此根底上的造型技術。基于Surfels表示實體的的布爾運算點云表示幾何體的光順造型II基于點的表示與基于點的造型基于點的幾何表示參數化表示隱式表示Surfels表示〔顯式表示〕混合表示等基于點的造型光順、采樣、變形、編輯、布爾運算等基于點的幾何表示外表重構的目標[Hoppe] 用一個采樣集P以及采樣處理的一些信息(如誤差大小以及采樣密度)來確定一個近似表示未知外表M的外表M’參數化表示定義一個2維參數域到的映射優點快速高效地繪制細節豐富，能表示銳利的特征保存微分屬性支持LOD等缺點拓撲維護困難，不適合作過度的變形布爾操作困難隱式表示通過尋找一個光滑的標量函數使得在誤差允許范圍內以零集Z(g)來表示實體外表。優點全局連續、光滑容易作布爾運算缺點繪制效率不高難以表示銳利的特征Surfels表示(顯式表示)Surfel:一個帶形狀因子與光照屬性的0維n元組，用來局部近似物體外表[Pfister]。Surfels表示(二)優點容易獲取容易實現LOD容易實現混合繪制，提高繪制效率支持局部造型，快速簡便缺點不能得到處處連續的實體表示，不能應用于精密造型受允許誤差的影響較大III基于Surfels表示實體的布爾運算相關工作隱式方法徑向基函數[Carr]針對不同情況用不同的隱函數擬合外表[Ohtake]顯式方法顯式點云布爾運算，利用八叉樹加速內外測試[Adams]混合方法MLS+顯式點[Pauly]一般點模型的離散布爾操作重建幾何顯式表示，實體將空間劃分為內部/外部/邊界三局部內外判別內部/外部/相交求取交線重構外表A∪B={s|s∈A&&soutsideB}∪{s|s∈B&&soutsideA}A∩B={s|s∈A&&sinsideB}∪{s|s∈B&&sinsideA}A?B={s|s∈A&&soutsideB}∪{s|s∈B&&sinsideA}邊界處點元沿交線重采樣點模型離散布爾運算的難點內外判別困難缺少拓撲信息離散的外表表示精度問題難以精確地表示邊界Adams算法流程圖Adams算法的缺陷數據過于理想，算法應用局限性太大；對噪聲很敏感，容易出現歧義判別；內外測試精度不高；每個待測試surfel只能計算一條交線，在曲率較大或細節豐富的區域邊界表示不夠精確。一般點模型布爾運算流程圖重建幾何-自適應三色八叉樹

按坐標平面方向剖分的八叉樹。根據結點內所含surfel個數進行自適應剖分。保證內部結點與外部結點被邊界結點隔開。每個結點被歸類為內部結點、外部結點或邊界結點這三種結點之一。重建幾何-改進的結點判別方法記錄所有空結點與其相鄰邊界結點的判別值C；記錄同一連通區域內所有空結點的帶權值的判別值之和ΣλC；

根據ΣλC判別整個連通區域內所有空結點為同一類空結點。

重建幾何-邊界結點進一步剖分采用兩個平行判別平面將邊界結點剖分為邊界內側，邊界外側，邊界。內外測試包圍盒-包圍盒測試點-包圍盒測試點-邊界結點測試位于兩個平行判別平面之外，可快速判別位于兩個平行判別平面之內，需進一步判別點-點測試 查找另一實體中與待測試surfels可能相交的surfel集。如果此集合中有surfel與s相交，那么可判定s為相交；否那么查找另一實體中與s最近的surfelt，根據t的法向與s跟t連線的夾角判別。求取交線-主交線的選取取surfels的中心到各交線段的最短距離，計算與各交線段長度的比值，取比值最小的那條交線作為主交線。主交線邊界表示的誤差估算用δ表示，其取值為surfels所有交線段上的點到主交線的最大距離。

邊界surfel沿主交線剖分自適應細分加密采樣Adams剖分策略的缺陷：無法精確表示那些外表細節變化很大的相交邊界局部區域，僅對光滑的相交邊界局部區域有效不適用于不同分辨率點模型間的布爾運算本文策略：邊界surfel根據局部采樣特性作自適應細分加密后再沿主交線剖分。細分加密采樣細分加密采樣(實例)實現結果缺陷IV光順造型問題描述 給定一個由含有幾何噪聲的點云表示的模型外表，光順造型的目標是生成一個外表光滑、與原始模型外表盡可能接近的新點云相關工作點云模型的光順MLS[Alexa]，光順重采樣體積約束Laplace算子光順[Pauly]Laplace光順算子 擴散過程[Desbrun]優點:迭代的時間、空間復雜度為線性缺點:細節喪失、外表收縮和變形，特征喪失點模型光順無須考慮連接噪聲(connectivitynoise)與拓撲噪聲(topologynoise)，而只要考慮幾何噪聲(geometrynoise)即可。難點：無拓撲無鄰接關系—缺乏標架缺乏足夠的外表信息支持進一步分析鄰域結構局部解決標架問題理論上仍然是一個難點對于各向同性的Laplace算子可以作空間分解:對此鄰域的Laplace迭代可以分解為兩個相互獨立的子空間上的迭代光順除噪從統計的角度看，假設鄰域近似平面分布，而而噪聲呈分布，那么鄰域重心的噪聲分布為：鄰域規模越大，鄰域重心的噪聲就越小。如果約束鄰域重心，那么在光順的同時可以克服點云的過度漂移。鄰域重心約束的光順算法

采用劉新國的算法，局部求解單個鄰域的帶約束目標能量最小化問題。重心約束條件為：

其中續前鄰域控制:矩陣A奇異條件： A每一行為0，即此鄰域群是孤立的。解決方案：將此鄰域群內的點當成錯誤點全部剔除適當擴大鄰域規模局部光順:通過對初始點的約束來實現局部光順實現結果結果一

0.02-0.02結果二結果三結果四總結提出了一個新的適用于一般點云模型的交互式布爾運算算法。采用自適應八叉樹剖分實體來實現