計(jì)算機(jī)圖形學(xué)第三章幾何建模供《現(xiàn)代計(jì)算機(jī)圖形學(xué)基礎(chǔ)》配套使用1提綱基本概念自由曲線曲面建模細(xì)分曲面建模三維重建數(shù)據(jù)結(jié)構(gòu)21.1幾何建模計(jì)算機(jī)圖形學(xué)中，幾何建模主要是指建立二維/三維幾何形狀的數(shù)學(xué)形式及數(shù)據(jù)結(jié)構(gòu)表示。3Beziercurve掃描數(shù)據(jù)NURBS網(wǎng)格點(diǎn)云1.1幾何建模幾何建模是CAD/CAM等的核心，通常也是圖形處理（繪制、交互等）的首要步驟。4CAD/CAM模型繪制模型交互1.2數(shù)學(xué)基礎(chǔ)1.2.1幾何形狀數(shù)學(xué)形式顯式表達(dá)隱式表達(dá)參數(shù)表達(dá)5

?隱式表達(dá)顯式表達(dá)參數(shù)表達(dá)代數(shù)形式（非參數(shù)形式）1.2數(shù)學(xué)基礎(chǔ)1.2.1幾何形狀數(shù)學(xué)形式顯式表達(dá)因變量隨自變量而變化的函數(shù)形式6平面直線

表達(dá)形式二維曲線三維曲面

1.2數(shù)學(xué)基礎(chǔ)1.2.1幾何形狀數(shù)學(xué)形式隱式表達(dá)多個(gè)變量共同定義的函數(shù)形式7表達(dá)形式二維曲線三維曲面

圓

環(huán)面1.2數(shù)學(xué)基礎(chǔ)1.2.1幾何形狀數(shù)學(xué)形式參數(shù)表達(dá)采用若干獨(dú)立變量的顯示表達(dá)式組成的集合8表達(dá)形式二維曲線三維曲面圓環(huán)面

1.2數(shù)學(xué)基礎(chǔ)1.2.1幾何形狀數(shù)學(xué)形式參數(shù)表達(dá)優(yōu)點(diǎn)具有直觀的解釋曲線：點(diǎn)p(u)形成的軌跡曲面：點(diǎn)p(u,v)充滿的集合91.2數(shù)學(xué)基礎(chǔ)1.2.1幾何形狀數(shù)學(xué)形式參數(shù)表達(dá)優(yōu)點(diǎn)具有直觀的解釋:點(diǎn)p(u)或者p(u,v)的軌跡可以寫成u或者(u,v)的形式。方便微積分等運(yùn)算10p

1.2數(shù)學(xué)基礎(chǔ)1.2.2常見幾何性質(zhì)-曲線長度、曲率、撓率11長度曲率撓率1.2數(shù)學(xué)基礎(chǔ)1.2.2常見幾何性質(zhì)-曲線長度、曲率、撓率12P是平面曲線當(dāng)且僅當(dāng)P是直線當(dāng)且僅當(dāng)1.2數(shù)學(xué)基礎(chǔ)1.2.2常見幾何性質(zhì)-曲面法向、法曲率、主曲率、高斯曲率13法向主曲率法曲率1.3建模類型建模對象自然物體建模人造物體建模建模方式插值（interpolation）擬合（fitting）14型值點(diǎn)插值擬合提綱基本概念自由曲線/曲面建模細(xì)分曲面建模三維重建數(shù)據(jù)結(jié)構(gòu)152.1多項(xiàng)式曲線2.1.1平面三次多項(xiàng)式曲線通過三次多項(xiàng)式插值或擬合給定的型值點(diǎn)集合曲線的參數(shù)表達(dá)16控制頂點(diǎn)2.1多項(xiàng)式曲線2.1.1平面三次多項(xiàng)式曲線給定4個(gè)型值點(diǎn)計(jì)算插值曲線17Givenfourdatapoints2.1多項(xiàng)式曲線2.1.1平面三次多項(xiàng)式曲線給定多于4個(gè)型值點(diǎn)計(jì)算擬合曲線18Givenmorethanfourdatapoints2.1多項(xiàng)式曲線2.1.2平面三次Hermite曲線給定兩個(gè)型值點(diǎn)及其一階導(dǎo)數(shù)計(jì)算插值曲線曲線的參數(shù)表達(dá)19GivenvaluesandderivativesoftwodatapointsHermite基函數(shù)2.1多項(xiàng)式曲線2.1.2平面三次Hermite曲線給定兩個(gè)型值點(diǎn)及其一階導(dǎo)數(shù)計(jì)算插值曲線曲線的參數(shù)表達(dá)20Givenvaluesandderivativesoftwodatapoints2.2Bezier曲線/曲面2.2.1Bezier曲線多項(xiàng)式曲線，但具有更直觀的幾何表達(dá)式方便外形設(shè)計(jì)21What’stheshape?Bernstein基函數(shù)控制多邊形2.2Bezier曲線/曲面2.2.1Bezier曲線歷史Bezier曲線于1960年，由法國工程師皮埃爾·貝塞爾（PierreBézier）在汽車外形設(shè)計(jì)時(shí)所采用最早由PauldeCasteljau（保羅·德·卡斯特里奧）于1959年運(yùn)用deCasteljau算法開發(fā)22PierreBézier(1910~1999),雷諾公司，法國工程師。PauldeCasteljau

(1930~),雪鐵龍公司，法國工程師2.2Bezier曲線/曲面2.2.1Bezier曲線定義n次Bernstein多項(xiàng)式(n+1)個(gè)控制頂點(diǎn)定義n次Bezier曲線23QuadraticCubicQuartic2.2Bezier曲線/曲面2.2.1Bezier曲線性質(zhì)插值端點(diǎn)曲線的起始點(diǎn)和終點(diǎn)和控制多邊形的起始和結(jié)束位置是相切的保凸性，即位于控制點(diǎn)的凸包（凸多邊形邊界）內(nèi)缺乏局部可控性242.2Bezier曲線/曲面2.2.1Bezier曲線deCasteljau遞歸算法（作圖定理）25…………2.2Bezier曲線/曲面2.2.2Bezier曲面多項(xiàng)式曲面參數(shù)表達(dá)由兩個(gè)變量的Bernstein混合函數(shù)表示m×n次Bezier曲面需要(m+1)×(n+1)個(gè)控制頂點(diǎn)26邊界性角點(diǎn)插值性凸包性角點(diǎn)切平面2.2Bezier曲線/曲面2.2.3幾何建模特點(diǎn)優(yōu)點(diǎn)容易編程（deCasteljau遞歸）端點(diǎn)和切向插值特性參數(shù)表達(dá)缺點(diǎn)缺乏局部可控性改變其中一個(gè)控制頂點(diǎn)的位置，就會(huì)改變整個(gè)曲線\曲面的形狀272.3B樣條曲線/曲面2.3.1B樣條曲線分段多項(xiàng)式曲線參數(shù)表達(dá)通過控制點(diǎn)生成28控制頂點(diǎn)節(jié)點(diǎn)樣條（spline）源于生產(chǎn)實(shí)踐，是富有彈性的細(xì)長條。用壓鐵使樣條通過指定的型值點(diǎn)，并調(diào)整樣條使它具有滿意的形狀，然后沿樣條畫出曲線。2.3B樣條曲線/曲面2.3.1B樣條曲線歷史Schoenberg:樣條曲線(1946)deBoor:B樣條曲線的遞歸算法(1966)Riesenfeld:B樣條曲線用作幾何設(shè)計(jì)(1970s)Versprille:第一次討論有理B樣條曲線(1975)NUBRS:成為工業(yè)標(biāo)準(zhǔn)(1990s)292.3B樣條曲線/曲面2.3.1B樣條曲線300123452.3B樣條曲線/曲面2.3.1B樣條曲線定義31控制點(diǎn)

ci(i=0,…,n)稱為deBoor點(diǎn)k階B樣條基函數(shù)（次數(shù)k-1）節(jié)點(diǎn)向量T={t0,…,tn+k+1}k階(k-1次)B樣條基函數(shù)deBoor-Cox遞推定義2.3B樣條曲線/曲面2.3.1B樣條曲線B樣條基函數(shù)取代Bernstein基函數(shù)1階（0次）基函數(shù)2階（1次）基函數(shù)322.3B樣條曲線/曲面2.3.1B樣條曲線B樣條基函數(shù)取代Bernstein基函數(shù)3階（2次）基函數(shù)332.3B樣條曲線/曲面2.3.1B樣條曲線三次B樣條曲線342.3B樣條曲線/曲面2.3.1B樣條曲線性質(zhì)保留Bezier曲線的優(yōu)點(diǎn)局部可控性：修改一個(gè)控制頂點(diǎn)最多會(huì)影響k+1條曲線靈活拼接352.3B樣條曲線/曲面2.3.1B樣條曲線deBoor遞歸算法36……………2.3B樣條曲線/曲面2.3.2B樣條曲面雙三次混合多項(xiàng)式曲面參數(shù)表達(dá)37局部性凸包性磨光性Bezier曲面包含性2.3B樣條曲線/曲面2.3.3非均勻有理B樣條曲面（NURBS）Non-uniform:節(jié)點(diǎn)向量Rational:對圓錐曲線曲面等的精確表示工業(yè)標(biāo)準(zhǔn)38權(quán)重2.3B樣條曲線/曲面2.3.3非均勻有理B樣條曲面（NURBS）NURBS曲線權(quán)重幾何意義如果固定曲線參數(shù)u，而使權(quán)重變化，則NURBS曲線變成以為參數(shù)的直線，即NURBS曲線上相同的點(diǎn)位于同一直線上。

增大或減小，曲線被拉向或推離ci點(diǎn)39ci建模實(shí)例2.3B樣條曲線/曲面40B-splinecontrolpointsB-splinecurveNURBSsurfaceDemo提綱基本概念自由曲線/曲面建模細(xì)分曲面建模三維重建數(shù)據(jù)結(jié)構(gòu)413.1概念細(xì)分曲面：給定多面體，按照指定的細(xì)分規(guī)則進(jìn)行無窮細(xì)化的極限極限曲面遞歸生成重新添加邊、頂點(diǎn)、面來重新定義網(wǎng)格（拓?fù)洌┮苿?dòng)頂點(diǎn)的空間位置來平滑網(wǎng)格（幾何）423.1概念細(xì)分曲面的特點(diǎn)曲面更靈活也更光滑在計(jì)算機(jī)動(dòng)畫中有廣泛的應(yīng)用43Catmull-Clark細(xì)分（DeRose，Pixar）AcademyAwardforBestAnimatedShortFilm,19983.1細(xì)分曲面細(xì)分曲面的核心：細(xì)分規(guī)則Catmull-ClarkDoo-SabinLoopButterfly443.2類型3.2.1Catmull-Clark細(xì)分E.Catmull和J.Clark在1978年發(fā)現(xiàn)雙三次B樣條的推廣應(yīng)用到多邊形網(wǎng)格中幾乎為C^2的連續(xù)性（除一些特殊點(diǎn)）453.2類型3.2.1Catmull-Clark細(xì)分雙三次B樣條曲面的切割磨光生成46面點(diǎn)邊點(diǎn)新頂點(diǎn)3.2類型3.2.1Catmull-Clark細(xì)分任意多邊形細(xì)分規(guī)則（幾何）加一個(gè)新頂點(diǎn)（表面點(diǎn)）到每個(gè)表面的中心給每個(gè)邊加一個(gè)新頂點(diǎn)（邊點(diǎn)），這個(gè)頂點(diǎn)是兩個(gè)端點(diǎn)和表面點(diǎn)的平均值用新的頂點(diǎn)替代舊的頂點(diǎn)47FacepointEdgepointVertexpoint3.2類型3.2.1Catmull-Clark細(xì)分任意多邊形細(xì)分規(guī)則(拓?fù)?連接每個(gè)表面點(diǎn)到鄰接的新邊點(diǎn)上連接每個(gè)頂點(diǎn)到鄰接的新邊點(diǎn)上48細(xì)化的網(wǎng)格3.2類型3.2.1Catmull-Clark細(xì)分連續(xù)性作用細(xì)分規(guī)則一次以后，所有的面均變?yōu)樗倪呅?，而且從此以后度?shù)不為4的頂點(diǎn)（稱為奇異點(diǎn)）的個(gè)數(shù)保持不變。除了奇異點(diǎn)以外，Catmull-Clark曲面由一系列雙三次B樣條曲面覆蓋而成，從而處處達(dá)到曲率連續(xù)。在奇異點(diǎn)處，僅切平面保持連續(xù)。49度為n的網(wǎng)格頂點(diǎn)3.2類型3.2.1Catmull-Clark細(xì)分結(jié)果示例50

(Demo)3.2類型3.2.2Doo-Sabin細(xì)分D.Doo和M.Sabin在1978年發(fā)現(xiàn)雙二次B樣條的推廣應(yīng)用到多邊形網(wǎng)格C^1的連續(xù)性513.2類型3.2.2Doo-Sabin細(xì)分雙二次B樣條的切割磨光生成52每個(gè)面的每個(gè)頂點(diǎn)產(chǎn)生一個(gè)新頂點(diǎn)3.2類型3.2.2Doo-Sabin細(xì)分任意多邊形細(xì)分規(guī)則（幾何）對于每個(gè)表面有k個(gè)頂點(diǎn)V1,V2,…,VK，形成新的對應(yīng)的頂點(diǎn)V1’,V2’,….,VK’53

3.2類型3.2.2Doo-Sabin細(xì)分任意多邊形細(xì)分規(guī)則（拓?fù)洌┻B接新的頂點(diǎn)去形成一個(gè)新的F類型表面連接圍繞一個(gè)邊周圍的4個(gè)頂點(diǎn)去形成新的表面E連接圍繞一個(gè)舊邊周圍的4個(gè)新的頂點(diǎn)，形成V54FEV3.2類型3.2.2Doo-Sabin細(xì)分連續(xù)性分析經(jīng)過一次Doo-Sabin細(xì)分后，每個(gè)頂點(diǎn)的度數(shù)均為4；再經(jīng)過一次細(xì)分后，度數(shù)不為4的面的個(gè)數(shù)保持不變。除了有限個(gè)奇異點(diǎn)外，由一系列雙二次B樣條曲面覆蓋而成。在奇異點(diǎn)處，Doo-Sabin曲面也是一階光滑連續(xù)。55新頂點(diǎn)3.2類型3.2.2Doo-Sabin細(xì)分結(jié)果示例56

(Demo)3.2類型3.2.3Loop細(xì)分C.Loop在1987年發(fā)現(xiàn)

箱樣條的推廣應(yīng)用到三角形網(wǎng)格中幾乎為C^2的連續(xù)性（除一些特殊點(diǎn)）573.2類型3.2.3Loop細(xì)分規(guī)則(幾何/拓?fù)?對于每個(gè)邊，計(jì)算一個(gè)新的點(diǎn)更新頂點(diǎn)位置連接新點(diǎn)形成一個(gè)新的網(wǎng)格583.2類型3.2.3Loop細(xì)分結(jié)果示例59

(Demo)3.2類型3.2.4Butterfly細(xì)分N.Dynetal.在1990年發(fā)現(xiàn)應(yīng)用到三角形網(wǎng)格里幾乎為C^1的連續(xù)性（除一些特殊點(diǎn)）603.2類型3.2.4Butterfly細(xì)分規(guī)則(幾何/拓?fù)?對于每個(gè)邊，使用規(guī)定的模式創(chuàng)造一個(gè)新的點(diǎn)保留舊的頂點(diǎn)，使用舊的邊點(diǎn)和定點(diǎn)把一個(gè)舊表面轉(zhuǎn)化成四個(gè)新表面613.2類型3.2.4Butterfly細(xì)分結(jié)果示例62

(Demo)3.2類型建模例子633.2類型建模例子64Demo提綱基本概念自由曲線/曲面建模細(xì)分曲面建模三維重建數(shù)據(jù)結(jié)構(gòu)654.1概念在計(jì)算機(jī)圖形學(xué)中，三維重建是指獲取真實(shí)世界中物體形狀和表觀的過程66斯坦福大學(xué)“數(shù)字米開朗基羅”項(xiàng)目4.1概念分為被動(dòng)式和主動(dòng)式兩種方式67基于圖像的被動(dòng)式方法基于視頻的基于激光測距的主動(dòng)式方法基于Kinect的4.1概念4.1.1被動(dòng)式不需要與重建對象接觸通過成像測量物體表面推測三維結(jié)構(gòu)輸入的是視頻、圖像等信息（ShapefromX）684.1概念4.1.1被動(dòng)式優(yōu)點(diǎn)破壞性小安全成本較低缺點(diǎn)對透明度敏感不能處理鏡面反射和內(nèi)部折射694.1概念4.1.2主動(dòng)式通過機(jī)械接觸或主動(dòng)觀測進(jìn)行三維掃描例：傳感器標(biāo)記、結(jié)構(gòu)光、激光、超聲波等704.1概念4.1.2主動(dòng)式三維掃描分類（按照測量手段）接觸式3D掃描儀，比如坐標(biāo)測量機(jī)71精確度高(μm)價(jià)格昂貴需要專業(yè)的操作者4.1概念4.1.2主動(dòng)式三維掃描分類（按照測量方法）“飛時(shí)測距”（time-of-flight）：發(fā)出一個(gè)光脈沖，通常是激光，計(jì)算這束光返回所需要的時(shí)間，距離為光路長的一半72優(yōu)點(diǎn):掃描速度快便攜，方便測量范圍大缺點(diǎn):精度有限(~5mm)4.1概念4.1.2主動(dòng)式三維掃描分類（按照測量方法）三角測距激光掃描：發(fā)射一道激光到待測物上，并利用攝影機(jī)查找待測物上的激光光點(diǎn)；激光光點(diǎn)、攝影機(jī)，與激光發(fā)射源本身構(gòu)成一個(gè)三角形。73優(yōu)點(diǎn):精度較高適合測量大尺寸物體缺點(diǎn):掃描速度慢，需要花費(fèi)較長時(shí)間4.1概念4.1.2主動(dòng)式三維掃描分類（按照測量方法）結(jié)構(gòu)光掃描：例如Kinect，使用紅外線發(fā)射器和紅外線傳感器，發(fā)射紅外線并接收反射回來的紅外線來獲取深度圖像。74優(yōu)點(diǎn):價(jià)格便宜、易于安裝缺點(diǎn):有限的深度（40cm~3.5m）4.1概念4.1.2主動(dòng)式優(yōu)點(diǎn)重建精度高對物體材質(zhì)不敏感缺點(diǎn)存在一定破壞性成本較高754.2基于圖像的三維重建4.2.1概念I(lǐng)mage-basedreconstruction從攝影圖像對三維物體對象進(jìn)行自動(dòng)重建多視角重建、單幅圖像重建76輸入:圖像輸出:3D模型4.2基于圖像的三維重建4.2.2多視角重建方法流程77用戶輸入紋理圖像幾何反射特性光照特性圖像基于圖像的建?；趫D像的繪制逼真的三維場景模型!場景外觀場景幾何

光照模型反射特性4.2基于圖像的三維重建4.2.2多視角重建方法流程攝像機(jī)標(biāo)定三角測量從運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)（稀疏形狀估計(jì)）立體匹配（稠密形狀估計(jì)）7812344.2基于圖像的三維重建4.2.2多視角重建攝像機(jī)標(biāo)定從一些已知坐標(biāo)的三維/二維點(diǎn)計(jì)算相機(jī)的內(nèi)參（如焦距、畸變）和外參（相機(jī)的姿態(tài)）79小孔相機(jī)4.2基于圖像的三維重建4.2.2多視角重建攝像機(jī)標(biāo)定從一些已知坐標(biāo)的三維/二維點(diǎn)計(jì)算相機(jī)的內(nèi)參（如焦距、畸變）和外參（相機(jī)的姿態(tài)）80焦距畸變系數(shù)4.2基于圖像的三維重建4.2.2多視角重建攝像機(jī)標(biāo)定從一些已知坐標(biāo)的三維/二維點(diǎn)計(jì)算相機(jī)的內(nèi)參（如焦距）和外參（相機(jī)的姿態(tài)）81角點(diǎn)檢測投影計(jì)算參數(shù)計(jì)算參數(shù)優(yōu)化進(jìn)行邊緣檢測，將各個(gè)矩形框邊緣擬合成直線求直線交點(diǎn)得到角點(diǎn)，根據(jù)先驗(yàn)知識(shí)即可得到各角點(diǎn)的二維坐標(biāo)和對應(yīng)的空間點(diǎn)的三維坐標(biāo)4.2基于圖像的三維重建4.2.2多視角重建攝像機(jī)標(biāo)定從一些已知坐標(biāo)的三維/二維點(diǎn)計(jì)算相機(jī)的內(nèi)參（如焦距、畸變）和外參（相機(jī)的姿態(tài)）82角點(diǎn)檢測投影計(jì)算參數(shù)計(jì)算參數(shù)優(yōu)化直接線性變換（DLT）4.2基于圖像的三維重建4.2.2多視角重建攝像機(jī)標(biāo)定從一些已知坐標(biāo)的三維/二維點(diǎn)計(jì)算相機(jī)的內(nèi)參（如焦距）和外參（相機(jī)的姿態(tài)）83角點(diǎn)檢測投影計(jì)算參數(shù)計(jì)算參數(shù)優(yōu)化從P計(jì)算內(nèi)參矩陣和外參矩陣4.2基于圖像的三維重建4.2.2多視角重建攝像機(jī)標(biāo)定從一些已知坐標(biāo)的三維/二維點(diǎn)計(jì)算相機(jī)的內(nèi)參（如焦距）和外參（相機(jī)的姿態(tài)）84角點(diǎn)檢測投影計(jì)算參數(shù)計(jì)算參數(shù)優(yōu)化通過對P的非線性優(yōu)化對相機(jī)參數(shù)進(jìn)行優(yōu)化4.2基于圖像的三維重建4.2.2多視角重建三角測量給定一些點(diǎn)在兩幅或更多的圖像間（從校準(zhǔn)相機(jī)）的對應(yīng)關(guān)系，計(jì)算這些點(diǎn)的三維位置85特征匹配基準(zhǔn)線相機(jī)1相機(jī)24.2基于圖像的三維重建4.2.2多視角重建三角測量給定一些點(diǎn)在兩幅或更多的圖像間（從校準(zhǔn)相機(jī)）的對應(yīng)關(guān)系，計(jì)算這些點(diǎn)的三維位置86三維視射線相交4.2基于圖像的三維重建4.2.2多視角重建從運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)（structure-from-motion）通過分析物體的運(yùn)動(dòng)得到三維結(jié)構(gòu)信息的過程，即給定多個(gè)點(diǎn)在幾幅圖像間的對應(yīng)關(guān)系，恢復(fù)得到它們的三維位置和相機(jī)參數(shù)874.2基于圖像的三維重建4.2.2多視角重建從運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)（structure-from-motion）通過分析物體的運(yùn)動(dòng)得到三維結(jié)構(gòu)信息的過程，即給定多個(gè)點(diǎn)在幾幅圖像間的對應(yīng)關(guān)系，恢復(fù)得到它們的三維位置和相機(jī)參數(shù)88光束平差法如果點(diǎn)j在相機(jī)i中是可見的否則4.2基于圖像的三維重建4.2.2多視角重建立體匹配（stereomatch）對所有的像素點(diǎn)同時(shí)應(yīng)用特征匹配標(biāo)準(zhǔn)來獲取它們的三維深度值894.2基于圖像的三維重建4.2.2多視角重建立體匹配（stereomatch）對所有的像素點(diǎn)同時(shí)應(yīng)用特征匹配標(biāo)準(zhǔn)來獲取它們的三維深度值90極線約束法SSD:平方差和4.2基于圖像的三維重建4.2.2多視角重建重建結(jié)果（法國Acute3D）91

(Demo)4.2基于圖像的三維重建4.2.3單幅圖像重建從一幅圖像重建物體對象的三維模型高度病態(tài)問題92單幅圖像高度病態(tài)問題病態(tài)問題多幅圖像4.2基于圖像的三維重建4.2.3單幅圖像重建需要更多的先驗(yàn)知識(shí)作為問題求解的約束條件93輸入超像素填充區(qū)域標(biāo)識(shí)三維模型基于平面關(guān)系基于對稱性交互指定線結(jié)構(gòu)線/平面三維模型整體三維模型

(Demo)4.3基于視頻的三維重建4.3.1概念將視頻幀序列作為輸入，進(jìn)行物體的重建優(yōu)點(diǎn)容易拍攝可以提供更加完整的數(shù)據(jù)靈活性缺點(diǎn)冗余數(shù)據(jù)結(jié)構(gòu)混淆94Demo4.3基于視頻的三維重建4.3.2類型根據(jù)數(shù)據(jù)利用方式的不同基于關(guān)鍵幀的視頻重建基于深度圖恢復(fù)的重建954.3基于視頻的三維重建4.3.2-1基于關(guān)鍵幀的三維重建重要問題：關(guān)鍵幀的選擇幾何魯棒性標(biāo)準(zhǔn)(GRIC)：通過兩張圖像之間的對應(yīng)點(diǎn)，可以計(jì)算一個(gè)3x3的基礎(chǔ)矩陣F，也可以計(jì)算一個(gè)3x3的單應(yīng)變換H，比較用哪個(gè)變換誤差小，也就是分?jǐn)?shù)低。如果用單應(yīng)變換分?jǐn)?shù)小，則相對于第一張圖像來說，第二張圖像不能作為參考幀。964.3基于視頻的三維重建4.3.2-1基于關(guān)鍵幀的三維重建方法流程974.3基于視頻的三維重建4.3.2-2基于深度圖恢復(fù)的三維重建基本思想：恢復(fù)視頻中每一幀的像素點(diǎn)的深度信息重要問題：對視頻每一幀的深度圖恢復(fù)獨(dú)立進(jìn)行，因此恢復(fù)的深度圖存在時(shí)間上的不一致性98…………4.3基于視頻的三維重建4.3.2-2基于深度圖恢復(fù)的三維重建方法流程99SfM視差初始化束優(yōu)化獲取相機(jī)的內(nèi)外參數(shù)獲取幀間連續(xù)深度的初始估計(jì)利用極線約束對初始深度進(jìn)行迭代優(yōu)化4.3基于視頻的三維重建4.3.2-2基于深度圖恢復(fù)的三維重建重建結(jié)果1004.4基于激光測距的三維重建4.4.1概念利用激光測距的原理，通過記錄被測物體表面大量的密集的點(diǎn)的三維坐標(biāo)、反射率和紋理等信息，可快速復(fù)建出被測目標(biāo)的三維模型。1014.4基于激光測距的三維重建4.4.2方法流程1023D掃描視點(diǎn)規(guī)劃配準(zhǔn)合并網(wǎng)格點(diǎn)云多邊形重建4.4基于激光測距的三維重建4.4.2重建方法核心問題：從點(diǎn)云得到多邊形多面體近似物體表面103數(shù)學(xué)角度:數(shù)據(jù)擬合或者插值過程

MarchingcubeDelaunay三角化移動(dòng)最小二乘方法（MLS）泊松方法……4.4基于激光測距的三維重建4.4.2重建方法4.4.2-1Marchingcube給定采樣得到的一個(gè)體數(shù)據(jù)集，即三維物體的點(diǎn)云模型，將其分割為多個(gè)小立方體，相鄰的8個(gè)采樣點(diǎn)構(gòu)成一個(gè)立方體。按掃描線順序在每個(gè)立方體中構(gòu)建等值面作為對應(yīng)采樣點(diǎn)的重建表面，將所有等值面相連得到完整的重建表面。1044.4基于激光測距的三維重建4.4.2重建方法4.4.2-2Delaunay三角化給定一個(gè)采樣得到的三維體數(shù)據(jù)，即點(diǎn)云模型，應(yīng)用Voronoi圖對散亂點(diǎn)云進(jìn)行Delaunay三角化得到，選擇Delaunay三角化得到的某個(gè)子集作為重構(gòu)出來的以三角面片表示的曲面。1054.4基于激光測距的三維重建4.4.2重建方法4.4.2-3移動(dòng)最小二乘曲面擬合給定表面的一些點(diǎn)，尋找一個(gè)無網(wǎng)格的方法來定義一個(gè)擬合表面滿足：平滑逼近局部依賴性1064.4基于激光測距的三維重建4.4.2重建方法4.4.2-4泊松方法給定一個(gè)有向點(diǎn)集，使用一個(gè)隱函數(shù)框架來計(jì)算一個(gè)三維指示函數(shù)（在模型內(nèi)部的點(diǎn)定義為1，外部的點(diǎn)定義為0），并且通過提取等值面來獲取重建的表面。建立八叉樹空間計(jì)算有向點(diǎn)云向量場解泊松方程求指示函數(shù)提取等值面1074.5基于Kinect的三維重建4.5.1概念利用Kinect提供的實(shí)時(shí)深度圖恢復(fù)物體對象三維模型1084.5基于Kinect的三維重建4.5.2方法4.5.2-1RGB-Dmapping基本思想：綜合圖像視覺特征和深度信息進(jìn)行幀間配準(zhǔn)，實(shí)時(shí)的融合深度圖，重建室內(nèi)場景三維模型。特點(diǎn)：從連續(xù)掃描的深度圖恢復(fù)三維場景，同時(shí)避免誤差累積及結(jié)構(gòu)歧義性等1094.5基于Kinect的三維重建4.5.2方法4.5.2-1RGB-Dmapping算法流程110視覺特征+深度信息三維模型深度配準(zhǔn)RGBD-ICP閉環(huán)檢測4.5基于Kinect的三維重建4.5.2方法4.5.2-1RGB-DmappingRGBD-ICP（IterativeClosestPoint：迭代最鄰近點(diǎn)）利用SIFT+深度作為特征，進(jìn)行深度圖的幀間配準(zhǔn)1114.5基于Kinect的三維重建4.5.2方法4.5.2-1RGB-Dmapping閉環(huán)檢測判斷是否回到之前的位置：利用圖結(jié)構(gòu)記錄幀間配準(zhǔn)時(shí)誤差，沒有閉環(huán)的重建對應(yīng)線性鏈（linearchain）重建的重復(fù)物體進(jìn)行正確歸并112surfel點(diǎn)云4.5基于Kinect的三維重建4.5.2方法4.5.2-2KinectFusion基本思想：追蹤相機(jī)姿態(tài)，并將當(dāng)前的深度數(shù)據(jù)從相機(jī)實(shí)時(shí)地融合到一個(gè)全局的3D模型中。特點(diǎn)：對物體從不同視角持續(xù)掃描，三維重建精度可以由粗到細(xì)地逐漸提高。1134.5基于Kinect的三維重建4.5.2方法4.5.2-2KinectFusion算法流程114深度圖轉(zhuǎn)換姿態(tài)配準(zhǔn)三維融合模型渲染4.5基于Kinect的三維重建4.5.2方法4.5.2-2KinectFusion深度圖轉(zhuǎn)換轉(zhuǎn)換深度值到相機(jī)坐標(biāo)系中計(jì)算頂點(diǎn)法向量115像素的深度值Kinect攝像頭的內(nèi)參矩陣深度值在相機(jī)坐標(biāo)系中的3D表示4.5基于Kinect的三維重建4.5.2方法4.5.2-2KinectFusion姿態(tài)配準(zhǔn)ICP（IterativeClosestPoint：迭代最鄰近點(diǎn)）1164.5基于Kinect的三維重建4.5.2方法4.5.2-2KinectFusion立體空間融合根據(jù)深度圖中像素對應(yīng)的深度值，構(gòu)造體積分模型，即像素平面作為定義域，深度值作為函數(shù)值。通過積分運(yùn)算，生成封閉的體模型。1174.5基于Kinect的三維重建4.5.2方法4.5.2-2KinectFusion模型渲染通過投射光線與體模型的相交運(yùn)算，得到模型表面對應(yīng)的交點(diǎn)位置、法向等繪制參數(shù)。利用光線跟蹤方法進(jìn)行模型繪制和顯示。118光線投射4.5基于Kinect的三維重建4.5.2方法4.5.2-2KinectFusion結(jié)果1194.6視覺同時(shí)定位與地圖構(gòu)建4.6.1概念利用激光雷達(dá)、攝像機(jī)等傳感器數(shù)據(jù)構(gòu)建未知環(huán)境下的空間位置、運(yùn)動(dòng)狀態(tài)、環(huán)境三維模型120同時(shí)定位與建圖傳感器傳感器采集數(shù)據(jù)傳感器空間位置、運(yùn)動(dòng)狀態(tài)環(huán)境三維模型4.6視覺同時(shí)定位與地圖構(gòu)建4.6.2視覺同時(shí)定位與建圖傳感器主要使用攝像機(jī)，采集數(shù)據(jù)主要是視頻圖像的一類同時(shí)定位與建圖技術(shù)（vSLAM）主要包括前端時(shí)間里程計(jì)、回環(huán)檢測、后端優(yōu)化和建圖四個(gè)關(guān)鍵部分121視頻圖像vSLAM三維點(diǎn)云視頻幀序列視覺里程計(jì)建圖優(yōu)化回環(huán)檢測4.6視覺同時(shí)定位與地圖構(gòu)建4.6.2視覺同時(shí)定位與建圖視覺里程計(jì)提取和匹配圖像之間的特征點(diǎn)，以此估計(jì)兩幀的相機(jī)運(yùn)動(dòng)采用對極幾何、PnP和迭代最近鄰（ICP）三種方式計(jì)算幀間相機(jī)運(yùn)動(dòng)122基于ORB特征的圖像匹配對極幾何迭代最近鄰PnP4.6視覺同時(shí)定位與地圖構(gòu)建4.6.2視覺同時(shí)定位與建圖回環(huán)檢測接收視頻幀圖像序列，檢測相機(jī)是否經(jīng)過之前的位置而形成的環(huán)路主要用于解決視覺里程計(jì)過程中產(chǎn)生的累積漂移1234.6視覺同時(shí)定位與地圖構(gòu)建4.6.2視覺同時(shí)定位與建圖后端優(yōu)化接收視覺里程計(jì)估計(jì)的不同時(shí)刻的相機(jī)位姿，以及回環(huán)檢測的信息，進(jìn)一步對相機(jī)位姿進(jìn)行優(yōu)化，得到全局一致的軌跡和地圖124基于卡爾曼濾波優(yōu)化基于BA的后端優(yōu)化4.6視覺同時(shí)定位與地圖構(gòu)建4.6.2視覺同時(shí)定位與建圖建圖構(gòu)建地圖的過程，在接收優(yōu)化后的相機(jī)位姿后，根據(jù)估計(jì)的軌跡構(gòu)建符合任務(wù)要求的三維場景結(jié)構(gòu)度量地圖和拓?fù)涞貓D125度量地圖拓?fù)涞貓D提綱基本概念自由曲線/曲面建模細(xì)分曲面建模三維重建數(shù)據(jù)結(jié)構(gòu)1265.1概念在計(jì)算機(jī)內(nèi)部表示、存儲(chǔ)幾何模型的數(shù)據(jù)組織形式層次模型構(gòu)造實(shí)體幾何模型（CSG）八叉樹模型邊界模型體素模型127實(shí)體建模計(jì)算機(jī)5.2常用數(shù)據(jù)結(jié)構(gòu)5.2.1構(gòu)造實(shí)體幾何模型Constructivesolidgeometry（CSG）元幾何元素通過布爾操作的模型描述元幾何：球體，圓柱體，立方體,…布爾操作：或，交集，差,…1285.2常用數(shù)據(jù)結(jié)構(gòu)5.2.1構(gòu)造實(shí)體幾何模型布爾操作或，交集，差129

UnionIntersection

Difference

5.2常用數(shù)據(jù)結(jié)構(gòu)5.2.1構(gòu)造實(shí)體幾何模型布爾操作或，交集，差1305.2常用數(shù)據(jù)結(jié)構(gòu)5.2.1構(gòu)造實(shí)體幾何模型優(yōu)點(diǎn)數(shù)學(xué)精確，比如在CAD/CAM固體或者不透水物體模型，比如制造業(yè)缺點(diǎn)形式復(fù)雜1315.2常用數(shù)據(jù)結(jié)構(gòu)5.2.2邊界模型由頂點(diǎn)和面列表的多邊形網(wǎng)格的描述邊界表示法（B-rep）：顯式模型的頂點(diǎn)，邊，和額外的鄰接信息存儲(chǔ)在網(wǎng)格面1325.2常用數(shù)據(jù)結(jié)構(gòu)5.2.2邊界模型5.2.2-1簡單邊界模型表示一個(gè)多邊形網(wǎng)格的一種常見的方法是一個(gè)共享的頂點(diǎn)列表和一個(gè)存儲(chǔ)指向它的頂點(diǎn)的指針列表。這種表示是方便和高效的許多目的，但是在某些領(lǐng)域，它證明是無效的。1335.2常用數(shù)據(jù)結(jié)構(gòu)5.2.2邊界模型5.2.2-1簡單邊界模型優(yōu)點(diǎn)簡單，方便構(gòu)造缺點(diǎn)復(fù)雜數(shù)據(jù)操作困難134不容易獲得實(shí)體之間的相鄰關(guān)系，并執(zhí)行插入/刪除操作！5.2常用數(shù)據(jù)結(jié)構(gòu)5.2.2邊界模型5.2.2-2半邊表示半邊數(shù)據(jù)結(jié)構(gòu)是一條邊的一半有向表示，而一對中的兩個(gè)邊有相反的方向135v1v2v3v4v5f1f2f3e1,1e2,1e3,1e3,2e4,1e5,1e4,2e6,1e7,1Twohalf-edgesmakeupanedge.5.2常用數(shù)據(jù)結(jié)構(gòu)5.2.2邊界模型5.2.2-2半邊表示一條邊的一半136SolidFaceLoopHalfEdgeVertexnextsnextfnextlnxtnextvprevsprevfprevlprvprevvsfacesvtxfloopsledgfsolidlfacefsolid5.2常用數(shù)據(jù)結(jié)構(gòu)5.2.2邊界模型5.2.2-2半邊表示頂點(diǎn)為主137v1v2v3v4v5f1f2f3e1,1e2,1e3,1e3,2e4,1e5,1e4,2e6,1e7,1頂點(diǎn)坐標(biāo)開始點(diǎn)的半邊v1(x1,y1,z1)e2,1v2(x2,y2,z2)e1,1v3(x3,y3,z3)e4,1v4(x4,y4,z4)e7,1v5(x5,y5,z5)e5,1頂點(diǎn)存儲(chǔ)5.2常用數(shù)據(jù)結(jié)構(gòu)5.2.2邊界模型5.2.2-2半邊表示半邊為主138v1v2v3v4v5f1f2f3e1,1e2,1e3,1e3,2e4,1e5,1e4,2e6,1e7,1半邊開始點(diǎn)相反半邊表面下一個(gè)半邊前一個(gè)半邊e3,1v3e3,2f1e1,1e2,1e3,2v2e3,1f2e4,1e5,1邊存儲(chǔ)5.2常用數(shù)據(jù)結(jié)構(gòu)5.2.2邊界模型5.2.2-2半邊表示優(yōu)點(diǎn)直接表示頂點(diǎn)，表面，邊,…允許在常量時(shí)間內(nèi)執(zhí)行所有的鄰接查詢,e.g,vertex2edge,vertex2face,edge2face,…缺點(diǎn)形式復(fù)雜1395.2常用數(shù)據(jù)結(jié)構(gòu)5.2.3體素模型用符號(hào)距離函數(shù)（SDF）、示性函數(shù)等隱式形式記錄三維幾何形狀。三維空間離散化為稠密的體素塊，存儲(chǔ)每個(gè)體素塊索引以及該體素中心位置的隱式函數(shù)值。140

5.2常用數(shù)據(jù)結(jié)構(gòu)5.2.3體素模型體素塊集合：隱式函數(shù)值：141ReferencesTheNURBSbook.LesA.Piegl,WayneTiller.Springer,2013.Pointcloudsurfacerepresentation.MarkPauly.Eurographicscourse,2003.Asurveyofpoint-basedtechniquesincomputergraphics.LeifKobbelt,MarioBotsch.ComputerandGraphics,2004.Polygonmeshprocessing.Botsch,Kobbelt,Pauly,Alliez,Levy.CRCpress,2010.Multipleviewgeometryincomputervision.R.Hartley,A.Zisserman.2000.142ReferencesFittingB-splinecurvestopointcloudsbycurvature-basedsquareddistanceminimization.W.Wang,etal.,TOG2006.Surfacereconstructionfromunorganizedpoints.Hoppe,DeRose,Duchamp,McDonald,Stuetzle.Siggraph92.Statisticalpointgeometry.Kalaiah,Varshney.SymposiumonGeometryProcessing,2003.Reconstructionandrepresentationof3Dobjectswithradialbasisfunctions.Carr,Beatson,Cherrie,Mitchell,Fright,McCallum,Evans.Siggraph,2001.Spectralsurfacequadrangulation.S.Dong,P.Bremer,M.Garland,V.Pascucci,J.Hart.Siggraph,2007.Variationaltetrahedralmeshing.P.Alliez,D.Cohen-Steiner,M.Yvinec,M.Desbrun.Siggraph2005.All-hexmeshgenerationviavolumetricpolycubedeformation.J.Gregson,A.Sheffer,E.Zhang.ComputerGraphicsForum,2011.Harmonicvolumetricmappingforsolidmodelingapplications.X.Li,X.Guo,H.Wang,Y.He,X.Gu,H.Qin.SPM,2007.143ReferencesAhierarchicalboundarymodelforsolidobjectrepresentation.L.Floriani,B.Falcidieno.TOG1988.Surfacereconstructionfromconstructivesolidgeometryforinteractivevisualization.AdvancesinVisualComputing,2007.OctreerepresentationanditsapplicaionsinCAD.Z.-S.Tang.JCST,1992.Directededges–ascalablerepresentationfortrianglemeshes.S.Campagna,L.Kobbelt,H.Seidel.ACMJournalofGraphicsTools,1998.Passivereconstructionofhighqualitytextured3Dmodelsofworksofart.N.Brusco,L.Ballan,G.Cortelazzo.VAST,2005.Thebundleadjustment-progressandprospects.D.C.Brown.InternationalArchivesofPhotogrammetry,21(3),1976.Bundleadjustment–amodernsynthesis.W.Triggs,etal.Springer,2000R.SzeliskiandS.B.Kang.Recovering3Dshapeandmotionfromimagestreamsusingnonlinearleastsquares.J.VisualCommun.ImageRepresent,1994.144ReferencesSeeingdoublewithoutconfusion:structure-from-motioninhighlyambiguousscenes.N.Jiang,etal.CVPR,2012.Multiple-viewstructureandmotionfromlinecorrespondences.A.Bartoli,P.Sturm.ICCV,2003.Robustplane-basedstructurefrommotion.Z.Zhou,H.Jin,Y.Ma.CVPR,2012.Semanticstructurefrommotionwithpoints,regions,andobjects.S.Bao,M.Bagra,Y.Chao,S.Savarese.CVPR,2012.Marchingcubes:ahighresolution3Dsurfaceconstructionalgorithm.W.LorensenandH.Cline.Siggraph,1987.AnewVoronoi-basedsurfacereconstructionalgorithm.N.Amenta,etal.Siggraph,1998.Robustmovingleast-squaresfittingwithsharpfeature.S.Fleishman,etal.Siggraph,2005.Poissonsurfacereconstruction.M.Kazhdan,etal.SGP,2006.145ReferencesRGB-Dmapping:usingkinect-styledepthcamerasfordense3Dmodelingofindoorenvironments.P.Henry,etal.IJRR,2012.Integratingdepthandcolorcuesfordensemulti-resolutionscenemappingusingRGB-Dcameras.J.StucklerandS.Behnke.MFI,2012.KinectFusion:real-time3Dreconstructionandinteractionusingamovingdepthcamera.S.Izadi.UIST,2012.Modelingbyexample.T.Funkhouser,M.Kazhdan,P.Shilane,P.Min,W.Kiefer,A.Tal.Siggraph,2004.AProbabilisticModelforComponent-BasedShapeSynthesis.EKalogerakis,etal.,Siggraph2012.Plants,FractalsandFormalLanguage.A.R.Smith.ComputerGraphics,1984.146計(jì)算機(jī)圖形學(xué)第四章數(shù)字幾何處理供《現(xiàn)代計(jì)算機(jī)圖形學(xué)基礎(chǔ)》配套使用147提綱1.基礎(chǔ)2.網(wǎng)格去噪3.網(wǎng)格簡化

4.重新網(wǎng)格化5.網(wǎng)格編輯6.網(wǎng)格形變1481.1幾何數(shù)字化媒體數(shù)字化進(jìn)程聲音、圖像、視頻、幾何149媒體數(shù)字化聲音圖像視頻幾何1.1幾何數(shù)字化2000年左右1995年，“玩具總動(dòng)員”動(dòng)畫，數(shù)字化娛樂1997年，“數(shù)字米開朗基羅”計(jì)劃，數(shù)字化文物1998年，“數(shù)字地球”，數(shù)字化生活1501.2數(shù)字幾何1.2.1幾何表示離散元素表示幾何形狀點(diǎn)云多邊形網(wǎng)格1511.2數(shù)字幾何1.2.1幾何表示1.2.1-1點(diǎn)云采用三維坐標(biāo)點(diǎn)作為模型幾何表示的基本單元1522.5K6K17K1.2數(shù)字幾何1.2.1幾何表示1.2.1-1點(diǎn)云優(yōu)點(diǎn)簡單的數(shù)據(jù)結(jié)構(gòu)更精致缺點(diǎn)不連續(xù)的幾何基元大量的數(shù)據(jù)拓?fù)浣Y(jié)構(gòu)等性質(zhì)表示復(fù)雜153≈10億個(gè)點(diǎn)1.2數(shù)字幾何1.2.1幾何表示1.2.1-2多邊形網(wǎng)格由頂點(diǎn)、邊和多邊形面組成的集合，定義了三維形狀154三角形網(wǎng)格四邊形網(wǎng)格1.2數(shù)字幾何1.2.1幾何表示1.2.1-2多邊形網(wǎng)格由頂點(diǎn)、邊和多邊形面組成的集合，定義了三維形狀分段線性逼近函數(shù)1551.2數(shù)字幾何1.2.1幾何表示1.2.1-2多邊形網(wǎng)格156NURBS網(wǎng)格CncontinuityQuadtopologyC0continuityTopologyfree點(diǎn)云網(wǎng)格C-1continuityTopologyfreeNo-connectivityC0continuityTopologyfreeConnectivity1.2數(shù)字幾何1.2.2幾何性質(zhì)1.2.2-1基本概念頂點(diǎn)的度（degree）：相鄰邊的數(shù)量表面朝向（orientation）：順時(shí)針方向的頂點(diǎn)的順序或者逆時(shí)針方向1571.2數(shù)字幾何1.2.2幾何性質(zhì)1.2.2-1基本概念拓?fù)洌╰opology）：網(wǎng)格幾何元素的連接關(guān)系虧格（genus）：影響表面連續(xù)性的分割曲線條數(shù)1581.2數(shù)字幾何1.2.2幾何性質(zhì)1.2.2-2基本性質(zhì)流形網(wǎng)格：局部同胚與圓盤每個(gè)邊只連接一個(gè)或者兩個(gè)表面表面上相鄰頂點(diǎn)形成一個(gè)封閉或開放式扇形非流形網(wǎng)格：局部與圓盤不同胚1591.2數(shù)字幾何1.2.2幾何性質(zhì)1.2.2-2基本性質(zhì)開網(wǎng)格：具有一條或多條邊界邊界邊：只連接一個(gè)入射的表面，或者說頂點(diǎn)只連接一個(gè)開的扇形閉網(wǎng)格：不存在邊界1601.2數(shù)字幾何1.2.2幾何性質(zhì)1.2.2-2基本性質(zhì)歐拉-龐加萊特性給定一個(gè)無邊界的流形網(wǎng)格M，頂點(diǎn)、邊、面的個(gè)數(shù)滿足：161#V=766#F=1536#E=2304g=2#V=2999#F=5998#E=8997g=1#V=7929#F=15855#E=23782g=01.2數(shù)字幾何1.2.3三角網(wǎng)格上的微分算子三角面片的線性表示：重心坐標(biāo)1621.2數(shù)字幾何1.2.3三角網(wǎng)格上的微分算子三角面片的線性表示：重心坐標(biāo)一階導(dǎo)數(shù)1631.2數(shù)字幾何1.2.3三角網(wǎng)格上的微分算子三角面片的線性表示：重心坐標(biāo)一階導(dǎo)數(shù)1641.2數(shù)字幾何1.2.3三角網(wǎng)格上的微分算子三角面片的線性表示：重心坐標(biāo)一階導(dǎo)數(shù)二階導(dǎo)數(shù)1651.3幾何深度學(xué)習(xí)通過在三維幾何上定義深度神經(jīng)網(wǎng)絡(luò)并進(jìn)行計(jì)算，完成數(shù)字幾何處理的相關(guān)任務(wù)。166?1.3幾何深度學(xué)習(xí)1.3.1點(diǎn)云神經(jīng)網(wǎng)絡(luò)PointNet：面向三維點(diǎn)云數(shù)據(jù)的深度神經(jīng)網(wǎng)絡(luò)輸入：點(diǎn)云轉(zhuǎn)換成n×3的向量結(jié)構(gòu)：多層感知機(jī)、向量卷積輸出：特征向量1671.3幾何深度學(xué)習(xí)1.3.1點(diǎn)云神經(jīng)網(wǎng)絡(luò)PointNet：面向三維點(diǎn)云數(shù)據(jù)的深度神經(jīng)網(wǎng)絡(luò)168點(diǎn)云分割1.3幾何深度學(xué)習(xí)1.3.2網(wǎng)格神經(jīng)網(wǎng)絡(luò)MeshCNN：面向三角網(wǎng)格數(shù)據(jù)的深度神經(jīng)網(wǎng)絡(luò)輸入：三角網(wǎng)格面片結(jié)構(gòu)：以邊為基本單元的卷積算子輸出：特征向量169五維向量1.3幾何深度學(xué)習(xí)1.3.2網(wǎng)格神經(jīng)網(wǎng)絡(luò)MeshCNN：面向三角網(wǎng)格數(shù)據(jù)的深度神經(jīng)網(wǎng)絡(luò)170網(wǎng)格分割提綱1.基礎(chǔ)2.網(wǎng)格去噪3.網(wǎng)格簡化

4.網(wǎng)格參數(shù)化5.網(wǎng)格編輯6.網(wǎng)格形變1712.1概念現(xiàn)實(shí)世界中的物體通過數(shù)字化掃描獲取與重建后的網(wǎng)格往往是帶有噪聲的激光掃描的深度圖像

從圖像重建的三維模型1722.1概念網(wǎng)格去噪消除網(wǎng)格模型表面噪聲，獲得一個(gè)幾何光滑模型又稱為網(wǎng)格光順、網(wǎng)格濾波等173網(wǎng)格去噪2.1概念網(wǎng)格去噪的主要挑戰(zhàn)什么是網(wǎng)格表面的噪聲？表面的凹凸表面的高頻部分…沒有精確的數(shù)學(xué)公式檢測困難較彎曲的地方高頻部分…1742.2方法目標(biāo)

消除高頻噪聲：量化模型表面的高頻信息保留全局特征：全局特征的幾何表示175+=平滑噪聲特征2.2方法形狀演化策略移動(dòng)網(wǎng)格頂點(diǎn)保持拓?fù)洌翰桓淖冞B接關(guān)系保持形狀：減少曲率變化描述為形狀演化1762.2方法形狀演化策略直接方案直接拉普拉斯平滑加權(quán)拉普拉斯平滑間接方案全局拉普拉斯平滑1772.2方法2.2.1直接拉普拉斯平滑將頂點(diǎn)移動(dòng)到相鄰頂點(diǎn)的平均位置178平均位置移動(dòng)頂點(diǎn)2.2方法2.2.1直接拉普拉斯平滑示例1792.2方法2.2.1直接拉普拉斯平滑特點(diǎn)循環(huán)迭代執(zhí)行等價(jià)于某種能量函數(shù)最小化能量：網(wǎng)格中邊長平方之和參數(shù)：??>

0控制收斂速度不反映網(wǎng)格形狀拉普拉斯坐標(biāo)對旋轉(zhuǎn)敏感局部幾何形狀會(huì)發(fā)生扭曲1802.2方法2.2.2加權(quán)拉普拉斯平滑傘型權(quán)重均值權(quán)重簡單的平均，獲得的精度較低余切權(quán)重可獲得較好的網(wǎng)格變形結(jié)果1812.2方法2.2.2加權(quán)拉普拉斯平滑結(jié)果182原始直接拉普拉斯加權(quán)拉普拉斯(余切)2.2方法2.2.3全局拉普拉斯平滑183網(wǎng)格的拉普拉斯算子其他

線性方程組2.2方法2.2.3全局拉普拉斯平滑求解拉普拉斯方程齊次方程k是網(wǎng)格中連通區(qū)域的數(shù)量需要加上某些限制184秩(L)=n-k；2.2方法185控制點(diǎn)控制點(diǎn)2.2.3全局拉普拉斯平滑求解拉普拉斯方程加上部分控制點(diǎn)進(jìn)行約束秩(L)=n3070個(gè)頂點(diǎn)，6144個(gè)三角形2.2方法2.2.3全局拉普拉斯平滑結(jié)果186Demo134359個(gè)頂點(diǎn)，268714個(gè)三角形提綱1.基礎(chǔ)2.網(wǎng)格去噪3.網(wǎng)格簡化

4.網(wǎng)格參數(shù)化5.網(wǎng)格編輯6.網(wǎng)格形變1873.1概念網(wǎng)格簡化（meshsimplification）通過刪除或者修改模型中對形狀影響不大的部分網(wǎng)格面片信息（包括頂點(diǎn)、邊和面片等）來減少多邊形面片數(shù)量。1883.1概念網(wǎng)格簡化（meshsimplification）問題起源：重建的網(wǎng)格模型通常規(guī)模較大，不利于存儲(chǔ)、傳輸和顯示，因此需要進(jìn)行滿足條件的網(wǎng)格數(shù)據(jù)簡化189≈20億個(gè)三角形移動(dòng)設(shè)備3.1概念遵循原則頂點(diǎn)最少原則：即在給定誤差上界的情況下,使得簡化模型的頂點(diǎn)數(shù)最少誤差最小原則：給定簡化模型的頂點(diǎn)個(gè)數(shù),使得簡化模型與原始模型之間的誤差最小1903.2簡化方法3.2.1頂點(diǎn)聚類思想：空間相鄰的近似頂點(diǎn)進(jìn)行合并方法：將原模型包圍盒劃分,使得小區(qū)域中包含了許多散落其中的頂點(diǎn)；再將此區(qū)域中的頂點(diǎn)合并,形成新的頂點(diǎn)；根據(jù)原始網(wǎng)格的拓?fù)潢P(guān)系,把這些頂點(diǎn)三角化后,從而得到簡化模型1913.2簡化方法3.2.1頂點(diǎn)聚類算法聚類生成通過空間劃分將原始模型的包圍盒劃分成若干區(qū)域1923.2簡化方法3.2.1頂點(diǎn)聚類算法合并新頂點(diǎn)頂點(diǎn)位置的平均值作為新頂點(diǎn)頂點(diǎn)位置的中值作為新頂點(diǎn)通過二次誤差測度求得新頂點(diǎn)1933.2簡化方法3.2.1頂點(diǎn)聚類算法合并新頂點(diǎn)頂點(diǎn)位置的平均值作為新頂點(diǎn)頂點(diǎn)位置的中值作為新頂點(diǎn)通過二次誤差測度求得新頂點(diǎn)194平均頂點(diǎn)位置中值頂點(diǎn)位置二次誤差測度3.2簡化方法3.2.1頂點(diǎn)聚類算法網(wǎng)格生成聚類p：{??_0,…??_??}q：{??_0,…??_??}如果(??_??,??_??)中間有邊那么就連接(p,q)195Demo3.2簡化方法3.2.2漸進(jìn)式網(wǎng)格（Progressivemesh,PM）思想：基于頂點(diǎn)和邊的基本操作進(jìn)行化簡方法：以邊合并和點(diǎn)移除為基本操作，記錄模型簡化過程中原頂點(diǎn)和新頂點(diǎn)位置以及頂點(diǎn)間的連接關(guān)系的變動(dòng)信息,從而生成由原始模型的最簡化模型和一系列簡化信息組成的漸進(jìn)表示1963.2簡化方法3.2.2漸進(jìn)式網(wǎng)格（Progressivemesh,PM）迭代算法選取網(wǎng)格區(qū)域應(yīng)用簡化算子(減少頂點(diǎn)與邊)直到?jīng)]有更多減少的可能1973.2簡化方法3.2.2漸進(jìn)式網(wǎng)格（Progressivemesh,PM）簡化算子：點(diǎn)移除198選擇一個(gè)即將移除的頂點(diǎn)選擇所有和頂點(diǎn)相連的三角形移除選擇的三角形添補(bǔ)缺失3.2簡化方法3.2.2漸進(jìn)式網(wǎng)格（Progressivemesh,PM）簡化算子：邊合并1993.2簡化方法3.2.2漸進(jìn)式網(wǎng)格（Progressivemesh,PM）結(jié)果200Demo3.2簡化方法方法對比頂點(diǎn)聚類計(jì)算快，但難以控制簡化網(wǎng)格網(wǎng)格拓?fù)浣Y(jié)構(gòu)被改變誤差在全局范圍內(nèi)，但沒有接近最優(yōu)漸進(jìn)式網(wǎng)格網(wǎng)格質(zhì)量與速度之間良好的平衡網(wǎng)格拓?fù)浣Y(jié)構(gòu)不改變可以限制偏差，提高網(wǎng)格質(zhì)量2013.3基于深度學(xué)習(xí)的網(wǎng)格簡化簡化算子：復(fù)雜網(wǎng)格到簡單網(wǎng)格的映射深度神經(jīng)網(wǎng)絡(luò)進(jìn)行簡化算子的函數(shù)擬合202頂點(diǎn)聚類f頂點(diǎn)移除點(diǎn)采樣器邊預(yù)測器面分類器3.3基于深度學(xué)習(xí)的網(wǎng)格簡化點(diǎn)采樣器：從原始網(wǎng)格的N個(gè)頂點(diǎn)中選取用于構(gòu)造簡化網(wǎng)格的M個(gè)頂點(diǎn)。頂點(diǎn)與1-鄰域內(nèi)頂點(diǎn)偏離程度為2033.3基于深度學(xué)習(xí)的網(wǎng)格簡化邊預(yù)測器：建立采樣頂點(diǎn)之間的邊連接關(guān)系。兩個(gè)頂點(diǎn)與

之間邊連接的概率為2043.3基于深度學(xué)習(xí)的網(wǎng)格簡化面分類器：根據(jù)邊預(yù)測器得到的三角面片作為初值，通過圖神經(jīng)網(wǎng)絡(luò)挑選能夠出現(xiàn)在簡化網(wǎng)格中的三角面片。兩個(gè)三角面片與

之間相對位置關(guān)系2053.3基于深度學(xué)習(xí)的網(wǎng)格簡化206通過面分類器獲得每個(gè)三角面片屬于簡化網(wǎng)格的概率，并通過和預(yù)設(shè)的閾值比較，得到保留下來的三角面片，組成簡化后的網(wǎng)格。提綱1.基礎(chǔ)2.網(wǎng)格去噪3.網(wǎng)格簡化

4.網(wǎng)格參數(shù)化5.網(wǎng)格編輯6.網(wǎng)格形變2074.1概念4.1.1定義網(wǎng)格表面和參數(shù)域之間的連續(xù)映射輸入：三維多邊形網(wǎng)格表面輸出：參數(shù)域同構(gòu)多邊形2084.1概念4.1.1定義問題起源：1974年，Catmull提出紋理映射技術(shù)，通過紋理空間(u,v)和三維曲面(s,t)之間的對應(yīng)關(guān)系，計(jì)算三維曲面上每一點(diǎn)顏色值209紋理映射4.1概念4.1.1定義問題起源世界地圖繪制球面坐標(biāo)系2104.1概念4.1.1定義問題起源世界地圖繪制211原圖球極平面投影墨卡托投影阿爾伯斯投影保角的等積的保角的4.1概念4.1.1定義問題起源世界地圖繪制212墨卡托投影4.1概念4.1.2類型理想的參數(shù)化：保形參數(shù)化保持所有的基本幾何量不變：長度、角度、面積僅適用于可展曲面對于一般曲面總會(huì)有扭曲！213可展曲面一般曲面4.1概念4.1.2類型按照幾何量扭曲分類保長度參數(shù)化（等距）保角度參數(shù)化（等角）保面積參數(shù)化（等積）214保長度參數(shù)化保角度參數(shù)化保面積參數(shù)化長度角度面積4.1概念4.1.2類型按照參數(shù)域分類平面參數(shù)化參數(shù)域是平面非平面參數(shù)化球面參數(shù)化基域參數(shù)化……215平面參數(shù)化球面參數(shù)化基域參數(shù)化4.2方法4.2.1數(shù)學(xué)模型參數(shù)域(u,v)參數(shù)化映射X(u,v)Jacobi矩陣反映

幾何扭曲2164.2方法4.2.1數(shù)學(xué)模型Jacobi矩陣奇異值分解217gG奇異值:γ,Γ保角度

γ=Γ保面積

γ

Γ

=1保長度

γ=Γ

=14.2方法4.2.1數(shù)學(xué)模型Jacobi矩陣奇異值分解2184.2方法4.2.1數(shù)學(xué)模型定理：每一個(gè)保長度的映射都是保角度的和保面積的，反之亦然。保長度參數(shù)化是理想的但是并不多見。在實(shí)際計(jì)算中，我們使用：保角度的保面積的兩者之間的平衡219保長度保角度保面積4.2方法4.2.2平面參數(shù)化尋找網(wǎng)格表面和平面之間的一一映射開網(wǎng)格（具有邊界的網(wǎng)格）固定邊界映射自由邊界映射閉網(wǎng)格設(shè)定邊界轉(zhuǎn)化為開網(wǎng)格2204.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化彈簧模型（Springsystem）221彈簧系數(shù)4.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化彈簧模型（Springsystem）222仿射組合系數(shù)4.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化彈簧模型（Springsystem）仿射組合系數(shù)凸組合（convexcombination）線性重構(gòu)（linearreproduction）223平均系數(shù)均值坐標(biāo)調(diào)和坐標(biāo)4.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化彈簧模型（Springsystem）仿射組合系數(shù)線性方程組求解224增加約束條件計(jì)算非平凡解！4.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化固定邊界映射（重心坐標(biāo)映射）225正方形已知未知4.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化固定邊界映射（重心坐標(biāo)映射）2264.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化固定邊界映射（重心坐標(biāo)映射）227平均系數(shù)均值坐標(biāo)調(diào)和坐標(biāo)4.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化自由邊界映射固定邊界（凸邊界）產(chǎn)生較大的幾何扭曲通過自由邊界減少參數(shù)化過程中幾何扭曲228固定邊界自由邊界關(guān)鍵問題：尋找合適的約束來計(jì)算有效參數(shù)化4.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化基于角度的網(wǎng)格展開（Angle-basedflattening,ABF）思想：通過構(gòu)建參數(shù)域三角形內(nèi)角分布，恢復(fù)頂點(diǎn)對應(yīng)的平面坐標(biāo)，從而達(dá)到保持角度的目的方法：在三角形的內(nèi)角形成的角度空間定義參數(shù)化映射，通過平面三角形的角度約束計(jì)算最優(yōu)參數(shù)化坐標(biāo)2294.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化基于角度的網(wǎng)格展開（Angle-basedflattening,ABF）230角度約束:所有內(nèi)角為正三角形內(nèi)角之和為π平面頂點(diǎn)周角為2π平面頂點(diǎn)一周封閉4.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化基于角度的網(wǎng)格展開（Angle-basedflattening,ABF）優(yōu)點(diǎn)不會(huì)發(fā)生邊“翻轉(zhuǎn)”優(yōu)化過程收斂缺點(diǎn)非線性優(yōu)化（牛頓迭代優(yōu)化）邊界可能發(fā)生交叉2314.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化最小二乘共形映射（Least-squareconformalmapping,LSCM）思想：保角度映射即共形映射，滿足柯西-黎曼方程方法：在三角面上離散柯西-黎曼方程2324.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化最小二乘共形映射（Least-squareconformalmapping,LSCM）233目標(biāo)函數(shù):4.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化最小二乘共形映射（Least-squareconformalmapping,LSCM）優(yōu)點(diǎn)保持角度線性優(yōu)化缺點(diǎn)無法保證參數(shù)化的有效性2344.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化直接幾何扭曲優(yōu)化思想：約束三角片參數(shù)化映射的幾何扭曲方法：直接優(yōu)化以奇異值為變量的函數(shù)235保角度

γ=Γ保面積

γ

Γ

=1保長度

γ=Γ

=1ASAPAAAPARAP4.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化直接幾何扭曲優(yōu)化2364.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化直接幾何扭曲優(yōu)化優(yōu)點(diǎn)保長度參數(shù)化迭代線性優(yōu)化缺點(diǎn)無法保證參數(shù)化結(jié)果的有效性2371st2nd3rd4.2方法4.2.2平面參數(shù)化4.2.2-1開網(wǎng)格的平面參數(shù)化238ABFLSCMARAP4.2方法4.2.2平面參數(shù)化4.2.2-2閉網(wǎng)格的平面參數(shù)化尋找最優(yōu)切割線將網(wǎng)格切開，變成開網(wǎng)格采用開網(wǎng)格平面參數(shù)化2394.2方法4.2.2平面參數(shù)化4.2.2-2閉網(wǎng)格的平面參數(shù)化切割線方法方法1：通過最小生成樹在網(wǎng)格表面尋找曲率高的網(wǎng)格頂點(diǎn)及邊，形成分割線方法2：結(jié)合網(wǎng)格頂點(diǎn)的可見性分布，尋找盡可能被隱藏的切割線240方法1方法24.2方法4.2.2平面參數(shù)化優(yōu)點(diǎn)計(jì)算復(fù)雜度較低顯式控制幾何扭曲缺點(diǎn)僅適用于與拓?fù)鋱A盤同構(gòu)的網(wǎng)格曲面對于虧格大于0的網(wǎng)格曲面，一般需要按照一定的規(guī)則將整個(gè)網(wǎng)格分片，會(huì)引起參數(shù)化結(jié)果不連續(xù)2414.2方法4.2.3球面參數(shù)化將虧格為零的三維網(wǎng)格參數(shù)化映射到球面等價(jià)于將頂點(diǎn)之間連接結(jié)構(gòu)嵌入到單位球242Steinitz‘stheorem：任何虧格為零且封閉的三角化可以映射成球面三角化。4.2方法4.2.3球面參數(shù)化球面重心坐標(biāo)映射243Laplacian矩陣i-throwofLaplacian4.2方法4.2.3球面參數(shù)化球面重心坐標(biāo)映射2444.2方法4.2.4基域參數(shù)化選取幾何簡單，同時(shí)拓?fù)浣Y(jié)構(gòu)（虧格）一致的基網(wǎng)格作為參數(shù)域。最常用的基網(wǎng)格參數(shù)域是單純復(fù)形（可以看作是傳統(tǒng)網(wǎng)格的一部分，只包含連接信息）。245genus=0genus=3提綱1.基礎(chǔ)2.網(wǎng)格去噪3.網(wǎng)格簡化

4.網(wǎng)格參數(shù)化5.網(wǎng)格編輯6.網(wǎng)格形變2465.1概念網(wǎng)格編輯（Meshediting/deformation）定義：操縱和修改網(wǎng)格表面的幾何形狀，同時(shí)能夠保留原始網(wǎng)格幾何細(xì)節(jié)的操作。2475.1概念網(wǎng)格編輯（Meshediting/deformation）問題起源：各種應(yīng)用中需要?jiǎng)討B(tài)形狀，例如，游戲、電影、計(jì)算機(jī)輔助設(shè)計(jì)等。但是，每種狀態(tài)下的形狀單獨(dú)建模比較費(fèi)時(shí)費(fèi)力。目標(biāo)通過內(nèi)部或者外部作用力改變形狀編輯應(yīng)該是快速的并且盡可能接近現(xiàn)實(shí)物體操作2485.2編輯方法5.2.1自由編輯（Free-formdeformation）思想：將網(wǎng)格嵌入到一個(gè)簡單的控制多面體中控制多面體比原始形狀簡單方法：對控制多面體進(jìn)行變形

根據(jù)變形后的控制多面體更新嵌入網(wǎng)格的形狀249控制網(wǎng)格和原始網(wǎng)格編輯后結(jié)果5.2編輯方法5.2.1自由編輯（Free-formdeformation）5.2.1-1基于樣條控制頂點(diǎn)的編輯采用三變量張量積樣條表示網(wǎng)格形狀改變樣條控制頂點(diǎn)編輯網(wǎng)格形狀2505.2編輯方法5.2.1自由編輯（Free-formdeformation）5.2.1-2基于重心坐標(biāo)的編輯三角形重心坐標(biāo)三角網(wǎng)格重心坐標(biāo)2515.2編輯方法5.2.1自由編輯（Free-formdeformation）5.2.1-2基于重心坐標(biāo)的編輯結(jié)果252Demo5.2編輯方法5.2.1自由編輯（Free-formdeformation）優(yōu)點(diǎn)任意形狀的平滑編輯對編輯的局