計(jì)算機(jī)視覺(jué)三維測(cè)量與建模 課件 【ch08】三維表面建模與網(wǎng)格模型濾波

第八章計(jì)算機(jī)視覺(jué)三維測(cè)量與建模三維表面建模與網(wǎng)格模型濾波南京航空航天大學(xué)研究生教育教學(xué)改革專項(xiàng)（優(yōu)質(zhì)教學(xué)資源建設(shè)）項(xiàng)目資助01三維表面網(wǎng)格模型】9在計(jì)算機(jī)上存儲(chǔ)表面模型的網(wǎng)格（Mesh）的方法有很多種。不同的數(shù)據(jù)結(jié)構(gòu)在編碼、內(nèi)存和訪問(wèn)性能方面具有非常不同的復(fù)雜性。這些結(jié)構(gòu)的核心是存儲(chǔ)定義網(wǎng)格的兩類信息，即在創(chuàng)建的網(wǎng)格中會(huì)編碼兩種類型的信息：幾何信息（即頂點(diǎn)在空間中的位置和表面法向量）和拓?fù)湫畔ⅲ淳W(wǎng)格的連通性以及面之間的關(guān)系）。三維表面網(wǎng)格模型】9以三角形網(wǎng)格為例，網(wǎng)格中的每個(gè)三角形都和其他三角形共享邊。這樣的網(wǎng)格模型包含三類基本幾何信息：每個(gè)三角形都有三個(gè)頂點(diǎn)，各頂點(diǎn)都有可能和其他三角形共享；邊，一個(gè)三角形有三條邊，每條邊都連接了兩個(gè)頂點(diǎn)：面，每個(gè)三角形都對(duì)應(yīng)一個(gè)面，可以用頂點(diǎn)列表或邊列表來(lái)表示面。010203三維表面網(wǎng)格模型在實(shí)際的數(shù)據(jù)存儲(chǔ)中，一個(gè)網(wǎng)格模型通常會(huì)存儲(chǔ)頂點(diǎn)列表和三角形列表（圖8.2），存儲(chǔ)多邊形網(wǎng)格時(shí)，還需要定義一個(gè)多邊形類，用來(lái)表達(dá)有任意多頂點(diǎn)的面。頂點(diǎn)列表中的每個(gè)頂點(diǎn)包含的最基本數(shù)據(jù)是一個(gè)三維坐標(biāo)，也可能含有點(diǎn)的法向量和顏色亮度等附加數(shù)據(jù)。每個(gè)三角形由對(duì)應(yīng)于頂點(diǎn)列表的三個(gè)索引組成，其中頂點(diǎn)索引的順序是非常重要的，因?yàn)橐粋€(gè)三角形的三個(gè)頂點(diǎn)順序關(guān)系到該三角形面的“正面”和“反面”。一般會(huì)用逆時(shí)針?lè)较蛄谐鲰旤c(diǎn)指示的面為正面，這樣該面的法向量與三個(gè)點(diǎn)的列表順序滿足右手螺旋指向，另外預(yù)先計(jì)算的面的法向量和紋理坐標(biāo)等也可以存儲(chǔ)在面列表中。三維表面網(wǎng)格模型半邊數(shù)據(jù)結(jié)構(gòu)（FalfedgeDataStructure）是流形網(wǎng)格模型中的一種數(shù)據(jù)存儲(chǔ)表達(dá)方式，其最大特點(diǎn)是定義了半邊(Halfedge）的概念。如圖8.4所示，網(wǎng)格的每條邊都被分為兩個(gè)半邊，每條半邊都是一個(gè)有向邊，兩條半邊的方向相反。如果一條邊被兩個(gè)面元公用，則每個(gè)面元都能各自擁有一條半邊。構(gòu)造立體幾何（ConstructiveSolidGeometry,CsG）是一種基于簡(jiǎn)單初級(jí)實(shí)體基元組成的對(duì)象模型表示法。CSG的模型通過(guò)初級(jí)實(shí)體集合的布爾型運(yùn)算組合在一起。三維表面網(wǎng)格模型】9第一類算法是直接計(jì)算幾何建模算法，也稱為豆式建模算法，包括計(jì)算凸包（Convex

Fulls）、計(jì)算獄洛尼三角剖分（DelaunayTriangulation）和計(jì)算阿爾法形狀（cshape）等代表性算法。顯式建模算法主體上通過(guò)連接采樣點(diǎn)構(gòu)建三角形，是對(duì)采樣點(diǎn)的精確插值。第二類是隱式建模算法，這類算法假設(shè)采樣點(diǎn)云中隱含一種能夠近似表達(dá)幾何表面模型的隱函數(shù)。該類算法將空間區(qū)域假設(shè)為一個(gè)標(biāo)量場(chǎng)，即由采樣點(diǎn)云構(gòu)造一個(gè)函數(shù)值分布空間。三維表面網(wǎng)格模型】9第三類算法是利用先導(dǎo)模式化結(jié)構(gòu)對(duì)目標(biāo)進(jìn)行建模，是一種自上而下的建模算法。在第6章中介紹基于模型的場(chǎng)景結(jié)構(gòu)分割的理論時(shí)，對(duì)模式化的結(jié)構(gòu)有所定義，可以說(shuō)這里的模式化建模就是在點(diǎn)云模型化分割的基礎(chǔ)上形成網(wǎng)格的一種后處理?；谀０寤蛘呦闰?yàn)?zāi)Ｊ降闹亟ǚ椒梢约?xì)分出更多種類、更復(fù)雜的子類，隨應(yīng)用場(chǎng)景的不同而可以有多種多樣的設(shè)計(jì)形式。三維表面網(wǎng)格模型紋理模式紋理模式是用于三維模型的真實(shí)可視化的直觀表達(dá)方式，紋理是讓三維模型看起來(lái)接近現(xiàn)實(shí)物體的一個(gè)最基本的要素。最簡(jiǎn)單形式的紋理貼圖涉及將單個(gè)紋理（如照片或正射影像）映射到由一個(gè)或多個(gè)多邊形組成的表面多邊形上。當(dāng)將影像映射到對(duì)象上時(shí)，每個(gè)對(duì)象的多邊形顏色都將由從紋理派生的相應(yīng)顏色進(jìn)行修改。01三維表面網(wǎng)格模型陰影模式陰影模式（ShadingModel）是基于光學(xué)理論（蘭伯特余弦定理）設(shè)計(jì)的，該理論指出，基于完美散射起伏表面的任何小區(qū)域（多邊形）的亮度都會(huì)隨著入射平行光角度的余弦而增大。該算法中，最廣為人知的是平面陰影和平滑陰影。平面陰影和平滑陰影之間的主要區(qū)別在于使用法線的方式。02三維表面網(wǎng)格模型光照模式要為真實(shí)場(chǎng)景創(chuàng)建這樣一個(gè)完整的模型，需要使用大量的視圖。這些視圖可以視為具有相應(yīng)顏色值的光線集合，它們是一個(gè)完全連續(xù)函數(shù)的離散樣本。考慮到物理限制的附加信息，必須從記錄的光線中插入未表示的光線。03三維表面網(wǎng)格模型01壓縮數(shù)據(jù)的幾何形狀：這類算法試圖改善網(wǎng)格的數(shù)字信息（頂點(diǎn)的位置、法線、顏色等）的存儲(chǔ)，或者尋求對(duì)網(wǎng)格拓?fù)溥M(jìn)行有效編碼的方法。02控制細(xì)節(jié)層次(LOD)：出于可視化目的，軟件可以用LOD技術(shù)在整個(gè)場(chǎng)景中平滑變化，不同位置的渲染的細(xì)膩程度取決于觀察者所在的當(dāng)前位置。03網(wǎng)格濾波（Filtering）優(yōu)化和簡(jiǎn)化(Decimation）：這些算法簡(jiǎn)化了網(wǎng)格，去掉了冗余的頂點(diǎn)、邊和三角形基元，可以選代地移除不符合特定距離/角度標(biāo)準(zhǔn)的頂點(diǎn)，或?qū)⑦呎郫B成唯一的項(xiàng)點(diǎn)。04點(diǎn)渲染：特別適用于點(diǎn)云可視化，并且通過(guò)是示較少數(shù)量的圖元來(lái)工作。QSplat是一個(gè)基于點(diǎn)的渲染系統(tǒng)，能夠使用不同復(fù)雜形狀的濺斑（Splat）圖元和不同的透明度米渲染相同的對(duì)象，以避免鋸齒邊緣，在實(shí)時(shí)性和渲染方面是示出良好的效果。基于網(wǎng)格模型的幾何信息和拓?fù)浣Y(jié)構(gòu)這兩個(gè)信息，學(xué)者們針對(duì)三角形網(wǎng)格模型提出了許多壓縮算法。三維表面網(wǎng)格模型02顯式建模方法凸集有兩種定義方式。第一種：如果對(duì)任意兩點(diǎn)2.9ES，線段P9CS，則集合S是凸的。第二種：如果集合5是(可能無(wú)限多個(gè)）半空間的交集，則S是凸的。圖8.7給出了凸集和非凸集的二維示例。顯式建模方法顯式建模方法二維空間的Delaunay三角剖分Delaunay三角剖分是一種標(biāo)準(zhǔn)，己有許多計(jì)算Delaunay三角剖分的算法，它們主要依賴于檢測(cè)點(diǎn)是否在三角形的外接圓內(nèi)，需要設(shè)計(jì)快速存儲(chǔ)三角形的有效數(shù)據(jù)結(jié)構(gòu)。增量式的枸網(wǎng)算法是最直接有效地計(jì)算Delaunay三角剖分的算法。這類算法通過(guò)逐點(diǎn)添加的形式插入新頂點(diǎn)，確定圖形受影響的部分，僅對(duì)一部分區(qū)域進(jìn)行三角剖分約束判斷和優(yōu)化調(diào)整。顯式建模方法二維空間的Delaunay三角剖分01顯式建模方法三維點(diǎn)云數(shù)據(jù)的Delaunay三角剖分02把Delaunay三角剖分的屈性從二維擴(kuò)展到更高的三維，其背后的原理是一致的。三維點(diǎn)云的Delaunay三角剖分的約束是四個(gè)點(diǎn)組成的四面體（4個(gè)三角形）的外接球不包含其他的點(diǎn)，即要生成符合空外接球規(guī)則的四面體組成。顯式建模方法三維點(diǎn)云數(shù)據(jù)的Delaunay三角剖分對(duì)三維點(diǎn)云處理，依然適用增量式的Delaunay三角劑分算法。首先，初始化一個(gè)大的四面體，能夠?qū)?chǎng)景中的所有三維點(diǎn)都包含在內(nèi)，大四面體的頂點(diǎn)不一定是輸入數(shù)據(jù)的點(diǎn)。然后，依次逐點(diǎn)向其中插入新的頂點(diǎn)，進(jìn)行判斷和構(gòu)網(wǎng)。每次插入新頂點(diǎn)p時(shí)，需要判斷點(diǎn)p是落在哪一個(gè)四面體的內(nèi)部，這個(gè)四面體被視為一個(gè)父節(jié)點(diǎn)，新的頂點(diǎn)會(huì)將父節(jié)點(diǎn)四面體剖分重組，父節(jié)點(diǎn)四面體進(jìn)而被標(biāo)注為無(wú)效。新生成的四面體被視為子節(jié)點(diǎn)。尋找父節(jié)點(diǎn)的方法可以是遍歷己經(jīng)生成的列表中的所有四面體，也可以是通過(guò)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)加速檢索。顯式建模方法】9顯式建模方法03隱式建模方法】9隱式建模方法】9隱函數(shù)表達(dá)式：隱式建模方法徑向基函數(shù)（RadialBasisFunctions,RBF）是一種常用的對(duì)離散數(shù)據(jù)插值的函數(shù)方法。對(duì)于一組給定采樣數(shù)據(jù)，RBF方法使用一組徑向?qū)ΨQ的基函數(shù)的線性組合生成高度平滑的擬合結(jié)果。隱式建模方法隱式建模方法移動(dòng)最小二乘（MovingLeastSquares,MIS）算法將重建表面近似為一個(gè)空間變化的低階多項(xiàng)式。如8.3.1節(jié)所達(dá)，隱式表面建模對(duì)應(yīng)的是一個(gè)插值問(wèn)題，MLS算法用局部多項(xiàng)式f(x)逼近表面F。用移動(dòng)最小二乘算法將插值問(wèn)題變?yōu)橐粋€(gè)函數(shù)優(yōu)化問(wèn)題，f(x)被選為對(duì)數(shù)據(jù)點(diǎn)x的最佳名項(xiàng)式逼近。隱式建模方法隱式建模方法】9泊松表面重建方法（PoissonReconstruction）是KazhdanM等人在2006年提出的種隱函數(shù)建模方法143，并且提供了開源代碼，是目前廣為使用的一種表面建模方法。泊松表面重建方法利用Poisson兩數(shù)來(lái)解決有向點(diǎn)云的表面擬合問(wèn)題。它結(jié)合了全局?jǐn)M合和局部擬合兩類方法的特點(diǎn)，因此在速度和精度兩個(gè)方面有較好的效果。由于全局優(yōu)化的特性，在形成鄰近區(qū)域、選擇面片類型和調(diào)整權(quán)重時(shí)不涉及啟發(fā)式的決策。另外，基函數(shù)是和周圍空間相關(guān)的而不僅是和數(shù)據(jù)點(diǎn)相關(guān)的，有一個(gè)局部層次支持的結(jié)構(gòu)，從而產(chǎn)生稀疏的優(yōu)良表現(xiàn)。隱式建模方法】9隱式建模方法01下面介紹用MC算法構(gòu)建網(wǎng)格模型的步驟：將三維空間規(guī)則地進(jìn)行體素化，離散后的每個(gè)體素單元都包含8個(gè)頂點(diǎn){v1,…,v8}，每個(gè)頂點(diǎn)都能夠由隱函數(shù)計(jì)算出對(duì)應(yīng)的函數(shù)值，即計(jì)算出f(vi）。02對(duì)體素的頂點(diǎn)進(jìn)行標(biāo)記。如果f(vi)的值大于或等于零等值面的值，則認(rèn)為該頂點(diǎn)位于等值面之外，標(biāo)記為“0”03根據(jù)8個(gè)頂點(diǎn)的二進(jìn)制標(biāo)記值計(jì)算體素的素31號(hào)index。隱式建模方法04根據(jù)體素的索引號(hào)index，在預(yù)先構(gòu)建好的查找表中找到體素內(nèi)的網(wǎng)格的連接方式。05盡管知道了等值面會(huì)穿過(guò)哪條邊，如邊（VaVb），但具體在邊上會(huì)經(jīng)過(guò)的點(diǎn)位置還沒(méi)有確定。此時(shí)，需要通過(guò)插值計(jì)算找到，可以使用邊的兩個(gè)頂點(diǎn)位置由簡(jiǎn)單的線性插值計(jì)算。06消除歧義。在算法中設(shè)計(jì)了根據(jù)體素頂點(diǎn)的法向量消除這樣的不連貫歧義。在整體的體素劃分空間中，每個(gè)頂點(diǎn)有上、下、左、右、前、后6個(gè)相鄰的頂點(diǎn)，采用中心差分方法可以計(jì)算該頂點(diǎn)的梯度矢量隱式建模方法04模型網(wǎng)格濾波去噪雙邊濾波（BilateralFilter）算法最早由Tomasi和Manduchi于1998年在影像處理領(lǐng)域中提出。雙邊港波利用像素的至高差異和亮度差異兩類信息設(shè)計(jì)加權(quán)平均的平滑算子，在對(duì)亮度值降樂(lè)平滑的同時(shí)保持影像的梯度邊緣特征。具體公式為:模型網(wǎng)格濾波去噪法向量是一種能夠反映場(chǎng)景幾何表面形態(tài)的重要參數(shù)，平滑區(qū)域的三角形面元的法向量應(yīng)當(dāng)是接近平行的；而表面轉(zhuǎn)折明顯的邊緣區(qū)域的三角形面元的法向量表現(xiàn)出較大的夾角。法向量引導(dǎo)濾波（NormalGuidedFitter）1s91是指利用網(wǎng)格面元的法向量信息來(lái)引導(dǎo)面元的頂點(diǎn)更新的技術(shù)，它可以拆解為法向量更新和頂點(diǎn)更新兩個(gè)主要的步驟。首先，對(duì)網(wǎng)格的三角形面元的法向量進(jìn)行平滑濾波，得到調(diào)整后的法向量信息；然后，根據(jù)調(diào)整后的法向量更新面元的頂點(diǎn)坐標(biāo)，使之能夠與法向量的信息匹配一致。模型網(wǎng)格濾波去噪在SunX等人設(shè)計(jì)的法向量濾波中，濾波結(jié)果是鄰域法向量的加權(quán)平均。下面介紹幾種法向量濾波的改進(jìn)技術(shù)。模型網(wǎng)格濾波去噪05應(yīng)用舉例在法向量引導(dǎo)的頂點(diǎn)更新算法中，法向量的準(zhǔn)確性直接關(guān)系到頂點(diǎn)更新的準(zhǔn)確性。在計(jì)算機(jī)圖形學(xué)中使用的許多網(wǎng)格都是分段平滑的，即它們的表面包含由尖鎖的邊緣隔開的平滑區(qū)域。在對(duì)尖邊緣附近的表面三角形面元的法向量進(jìn)行濾波時(shí)，應(yīng)避免將其與跨邊緣的外部法向量相聯(lián)系。應(yīng)用舉例】9數(shù)字化的三維模型幾乎已經(jīng)應(yīng)用到了各行各業(yè)中，比如圖8.32列舉的例子。根據(jù)具體的應(yīng)用需求不同，建模所選擇的方法會(huì)有所區(qū)別，但整體而言，尋求精簡(jiǎn)、保真和表面流形的要求是大多數(shù)算法都需要滿足條件。應(yīng)用舉例圖8.34展示了一組利用各種網(wǎng)格去噪濾波算法對(duì)網(wǎng)格模型進(jìn)行處理的對(duì)比實(shí)驗(yàn)，放大視口展示了局部的三角網(wǎng)分布。從圖中可以看出模型經(jīng)過(guò)濾