計(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ì)-曲線長(zhǎng)度、曲率、撓率11長(zhǎng)度曲率撓率1.2數(shù)學(xué)基礎(chǔ)1.2.2常見幾何性質(zhì)-曲線長(zhǎng)度、曲率、撓率12P是平面曲線當(dāng)且僅當(dāng)P是直線當(dāng)且僅當(dāng)1.2數(shù)學(xué)基礎(chǔ)1.2.2常見幾何性質(zhì)-曲面法向、法曲率、主曲率、高斯曲率13法向主曲率法曲率1.3建模類型建模對(duì)象自然物體建模人造物體建模建模方式插值（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年，由法國(guó)工程師皮埃爾·貝塞爾（PierreBézier）在汽車外形設(shè)計(jì)時(shí)所采用最早由PauldeCasteljau（保羅·德·卡斯特里奧）于1959年運(yùn)用deCasteljau算法開發(fā)22PierreBézier(1910~1999),雷諾公司，法國(guó)工程師。PauldeCasteljau

(1930~),雪鐵龍公司，法國(guó)工程師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ì)長(zhǎng)條。用壓鐵使樣條通過指定的型值點(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:對(duì)圓錐曲線曲面等的精確表示工業(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ī)則（幾何）對(duì)于每個(gè)表面有k個(gè)頂點(diǎn)V1,V2,…,VK，形成新的對(duì)應(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ù)?對(duì)于每個(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ù)?對(duì)于每個(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)式方法基于視頻的基于激光測(cè)距的主動(dòng)式方法基于Kinect的4.1概念4.1.1被動(dòng)式不需要與重建對(duì)象接觸通過成像測(cè)量物體表面推測(cè)三維結(jié)構(gòu)輸入的是視頻、圖像等信息（ShapefromX）684.1概念4.1.1被動(dòng)式優(yōu)點(diǎn)破壞性小安全成本較低缺點(diǎn)對(duì)透明度敏感不能處理鏡面反射和內(nèi)部折射694.1概念4.1.2主動(dòng)式通過機(jī)械接觸或主動(dòng)觀測(cè)進(jìn)行三維掃描例：傳感器標(biāo)記、結(jié)構(gòu)光、激光、超聲波等704.1概念4.1.2主動(dòng)式三維掃描分類（按照測(cè)量手段）接觸式3D掃描儀，比如坐標(biāo)測(cè)量機(jī)71精確度高(μm)價(jià)格昂貴需要專業(yè)的操作者4.1概念4.1.2主動(dòng)式三維掃描分類（按照測(cè)量方法）“飛時(shí)測(cè)距”（time-of-flight）：發(fā)出一個(gè)光脈沖，通常是激光，計(jì)算這束光返回所需要的時(shí)間，距離為光路長(zhǎng)的一半72優(yōu)點(diǎn):掃描速度快便攜，方便測(cè)量范圍大缺點(diǎn):精度有限(~5mm)4.1概念4.1.2主動(dòng)式三維掃描分類（按照測(cè)量方法）三角測(cè)距激光掃描：發(fā)射一道激光到待測(cè)物上，并利用攝影機(jī)查找待測(cè)物上的激光光點(diǎn)；激光光點(diǎn)、攝影機(jī)，與激光發(fā)射源本身構(gòu)成一個(gè)三角形。73優(yōu)點(diǎn):精度較高適合測(cè)量大尺寸物體缺點(diǎn):掃描速度慢，需要花費(fèi)較長(zhǎng)時(shí)間4.1概念4.1.2主動(dòng)式三維掃描分類（按照測(cè)量方法）結(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)重建精度高對(duì)物體材質(zhì)不敏感缺點(diǎn)存在一定破壞性成本較高754.2基于圖像的三維重建4.2.1概念I(lǐng)mage-basedreconstruction從攝影圖像對(duì)三維物體對(duì)象進(jìn)行自動(dòng)重建多視角重建、單幅圖像重建76輸入:圖像輸出:3D模型4.2基于圖像的三維重建4.2.2多視角重建方法流程77用戶輸入紋理圖像幾何反射特性光照特性圖像基于圖像的建?；趫D像的繪制逼真的三維場(chǎng)景模型!場(chǎng)景外觀場(chǎng)景幾何

光照模型反射特性4.2基于圖像的三維重建4.2.2多視角重建方法流程攝像機(jī)標(biāo)定三角測(cè)量從運(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)檢測(cè)投影計(jì)算參數(shù)計(jì)算參數(shù)優(yōu)化進(jìn)行邊緣檢測(cè)，將各個(gè)矩形框邊緣擬合成直線求直線交點(diǎn)得到角點(diǎn)，根據(jù)先驗(yàn)知識(shí)即可得到各角點(diǎn)的二維坐標(biāo)和對(duì)應(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)檢測(cè)投影計(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)檢測(cè)投影計(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)檢測(cè)投影計(jì)算參數(shù)計(jì)算參數(shù)優(yōu)化通過對(duì)P的非線性優(yōu)化對(duì)相機(jī)參數(shù)進(jìn)行優(yōu)化4.2基于圖像的三維重建4.2.2多視角重建三角測(cè)量給定一些點(diǎn)在兩幅或更多的圖像間（從校準(zhǔn)相機(jī)）的對(duì)應(yīng)關(guān)系，計(jì)算這些點(diǎn)的三維位置85特征匹配基準(zhǔn)線相機(jī)1相機(jī)24.2基于圖像的三維重建4.2.2多視角重建三角測(cè)量給定一些點(diǎn)在兩幅或更多的圖像間（從校準(zhǔn)相機(jī)）的對(duì)應(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)在幾幅圖像間的對(duì)應(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)在幾幅圖像間的對(duì)應(yīng)關(guān)系，恢復(fù)得到它們的三維位置和相機(jī)參數(shù)88光束平差法如果點(diǎn)j在相機(jī)i中是可見的否則4.2基于圖像的三維重建4.2.2多視角重建立體匹配（stereomatch）對(duì)所有的像素點(diǎn)同時(shí)應(yīng)用特征匹配標(biāo)準(zhǔn)來獲取它們的三維深度值894.2基于圖像的三維重建4.2.2多視角重建立體匹配（stereomatch）對(duì)所有的像素點(diǎn)同時(shí)應(yīng)用特征匹配標(biāo)準(zhǔn)來獲取它們的三維深度值90極線約束法SSD:平方差和4.2基于圖像的三維重建4.2.2多視角重建重建結(jié)果（法國(guó)Acute3D）91

(Demo)4.2基于圖像的三維重建4.2.3單幅圖像重建從一幅圖像重建物體對(duì)象的三維模型高度病態(tài)問題92單幅圖像高度病態(tài)問題病態(tài)問題多幅圖像4.2基于圖像的三維重建4.2.3單幅圖像重建需要更多的先驗(yàn)知識(shí)作為問題求解的約束條件93輸入超像素填充區(qū)域標(biāo)識(shí)三維模型基于平面關(guān)系基于對(duì)稱性交互指定線結(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)：通過兩張圖像之間的對(duì)應(yīng)點(diǎn)，可以計(jì)算一個(gè)3x3的基礎(chǔ)矩陣F，也可以計(jì)算一個(gè)3x3的單應(yīng)變換H，比較用哪個(gè)變換誤差小，也就是分?jǐn)?shù)低。如果用單應(yīng)變換分?jǐn)?shù)小，則相對(duì)于第一張圖像來說，第二張圖像不能作為參考幀。964.3基于視頻的三維重建4.3.2-1基于關(guān)鍵幀的三維重建方法流程974.3基于視頻的三維重建4.3.2-2基于深度圖恢復(fù)的三維重建基本思想：恢復(fù)視頻中每一幀的像素點(diǎn)的深度信息重要問題：對(duì)視頻每一幀的深度圖恢復(fù)獨(dú)立進(jìn)行，因此恢復(fù)的深度圖存在時(shí)間上的不一致性98…………4.3基于視頻的三維重建4.3.2-2基于深度圖恢復(fù)的三維重建方法流程99SfM視差初始化束優(yōu)化獲取相機(jī)的內(nèi)外參數(shù)獲取幀間連續(xù)深度的初始估計(jì)利用極線約束對(duì)初始深度進(jìn)行迭代優(yōu)化4.3基于視頻的三維重建4.3.2-2基于深度圖恢復(fù)的三維重建重建結(jié)果1004.4基于激光測(cè)距的三維重建4.4.1概念利用激光測(cè)距的原理，通過記錄被測(cè)物體表面大量的密集的點(diǎn)的三維坐標(biāo)、反射率和紋理等信息，可快速?gòu)?fù)建出被測(cè)目標(biāo)的三維模型。1014.4基于激光測(cè)距的三維重建4.4.2方法流程1023D掃描視點(diǎn)規(guī)劃配準(zhǔn)合并網(wǎng)格點(diǎn)云多邊形重建4.4基于激光測(cè)距的三維重建4.4.2重建方法核心問題：從點(diǎn)云得到多邊形多面體近似物體表面103數(shù)學(xué)角度:數(shù)據(jù)擬合或者插值過程

MarchingcubeDelaunay三角化移動(dòng)最小二乘方法（MLS）泊松方法……4.4基于激光測(cè)距的三維重建4.4.2重建方法4.4.2-1Marchingcube給定采樣得到的一個(gè)體數(shù)據(jù)集，即三維物體的點(diǎn)云模型，將其分割為多個(gè)小立方體，相鄰的8個(gè)采樣點(diǎn)構(gòu)成一個(gè)立方體。按掃描線順序在每個(gè)立方體中構(gòu)建等值面作為對(duì)應(yīng)采樣點(diǎn)的重建表面，將所有等值面相連得到完整的重建表面。1044.4基于激光測(cè)距的三維重建4.4.2重建方法4.4.2-2Delaunay三角化給定一個(gè)采樣得到的三維體數(shù)據(jù)，即點(diǎn)云模型，應(yīng)用Voronoi圖對(duì)散亂點(diǎn)云進(jìn)行Delaunay三角化得到，選擇Delaunay三角化得到的某個(gè)子集作為重構(gòu)出來的以三角面片表示的曲面。1054.4基于激光測(cè)距的三維重建4.4.2重建方法4.4.2-3移動(dòng)最小二乘曲面擬合給定表面的一些點(diǎn)，尋找一個(gè)無網(wǎng)格的方法來定義一個(gè)擬合表面滿足：平滑逼近局部依賴性1064.4基于激光測(cè)距的三維重建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)云向量場(chǎng)解泊松方程求指示函數(shù)提取等值面1074.5基于Kinect的三維重建4.5.1概念利用Kinect提供的實(shí)時(shí)深度圖恢復(fù)物體對(duì)象三維模型1084.5基于Kinect的三維重建4.5.2方法4.5.2-1RGB-Dmapping基本思想：綜合圖像視覺特征和深度信息進(jìn)行幀間配準(zhǔn)，實(shí)時(shí)的融合深度圖，重建室內(nèi)場(chǎng)景三維模型。特點(diǎn)：從連續(xù)掃描的深度圖恢復(fù)三維場(chǎng)景，同時(shí)避免誤差累積及結(jié)構(gòu)歧義性等1094.5基于Kinect的三維重建4.5.2方法4.5.2-1RGB-Dmapping算法流程110視覺特征+深度信息三維模型深度配準(zhǔn)RGBD-ICP閉環(huán)檢測(cè)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)檢測(cè)判斷是否回到之前的位置：利用圖結(jié)構(gòu)記錄幀間配準(zhǔn)時(shí)誤差，沒有閉環(huán)的重建對(duì)應(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)：對(duì)物體從不同視角持續(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ù)深度圖中像素對(duì)應(yīng)的深度值，構(gòu)造體積分模型，即像素平面作為定義域，深度值作為函數(shù)值。通過積分運(yùn)算，生成封閉的體模型。1174.5基于Kinect的三維重建4.5.2方法4.5.2-2KinectFusion模型渲染通過投射光線與體模型的相交運(yùn)算，得到模型表面對(duì)應(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)檢測(cè)、后端優(yōu)化和建圖四個(gè)關(guān)鍵部分121視頻圖像vSLAM三維點(diǎn)云視頻幀序列視覺里程計(jì)建圖優(yōu)化回環(huán)檢測(cè)4.6視覺同時(shí)定位與地圖構(gòu)建4.6.2視覺同時(shí)定位與建圖視覺里程計(jì)提取和匹配圖像之間的特征點(diǎn)，以此估計(jì)兩幀的相機(jī)運(yùn)動(dòng)采用對(duì)極幾何、PnP和迭代最近鄰（ICP）三種方式計(jì)算幀間相機(jī)運(yùn)動(dòng)122基于ORB特征的圖像匹配對(duì)極幾何迭代最近鄰PnP4.6視覺同時(shí)定位與地圖構(gòu)建4.6.2視覺同時(shí)定位與建圖回環(huán)檢測(cè)接收視頻幀圖像序列，檢測(cè)相機(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)檢測(cè)的信息，進(jìn)一步對(duì)相機(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ù)要求的三維場(chǎng)景結(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簡(jiǎn)單邊界模型表示一個(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簡(jiǎn)單邊界模型優(yōu)點(diǎn)簡(jiǎ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)是一條邊的一半有向表示，而一對(duì)中的兩個(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-progress