第十三章

三維場景表示為了理解場景并與場景中的物體交互作用，必須將場景的三維數(shù)據(jù)進(jìn)行有效的表示．

三維場景表示包含有兩個(gè)基本問題：場景重建和場景分割

場景重建(reconstruction)是指使用插值或擬合方法從采樣點(diǎn)(稠密深度測量值或稀疏深度測量值)計(jì)算曲面的連續(xù)函數(shù)，實(shí)際中通常使用許多三角片或小平面片構(gòu)成的網(wǎng)面來近似表示場景深度測量值；場景分割是將表示場景的網(wǎng)面分割成若干部分，每一部分表示一個(gè)物體或一個(gè)特定的區(qū)域，這樣有利于物體識別、曲面精確估計(jì)等后處理算法的實(shí)現(xiàn)．13.1三維空間曲線

曲線表示有三種形式：隱式、顯式和參數(shù)式。在機(jī)器視覺領(lǐng)域中，曲線的參數(shù)表示比隱式和顯式表示更為常用。北京理工大學(xué)計(jì)算機(jī)系三維曲線的參數(shù)形式為：P=(x,y,z)=(x(t),y(t),z(t))t0

tt1上式說明曲線上的一點(diǎn)可由參數(shù)t表示的三個(gè)函數(shù)來定義，曲線的起點(diǎn)為(x(t0),y(t0),z(t0))，終點(diǎn)為(x(t1),y(t1),z(t1))。比如，從p1=(x1,y1,z1)到p2=(x2,y2,z2)的直線段的參數(shù)方程為：13.1.1三次樣條曲線北京理工大學(xué)計(jì)算機(jī)系三維曲線都可以用樣條函數(shù)來表示，這和前面討論的平面曲線表示類似．三次樣條函數(shù)是一系列首尾相連的三次多項(xiàng)式曲線，每一段三次樣條函數(shù)的參數(shù)表示形式為：

x(t)=axt3+bxt2+cxt+dxy(t)=ayt3+byt2+cyt+dyz(t)=azt3+bzt2+czt+dz其中0t1更復(fù)雜的曲線可以表示為一系列首尾相連的三次多項(xiàng)式：

p1(t)=a1t3+b1t2+c1t+d1p2(t)=a2t3+b2t2+c2t+d2

Pn(t)=ant3+bnt2+cnt+dn其中0t1．如果定義第i個(gè)三次多項(xiàng)式段在單位區(qū)間i-1ti上，那么整個(gè)序列就定義在區(qū)間為0tn上.這個(gè)三次多項(xiàng)式序列叫做一個(gè)三次樣條函數(shù)北京理工大學(xué)計(jì)算機(jī)系···13.2三維空間曲面的表示

平面多邊形，也叫平面片(planarpatch)，可以組成復(fù)雜的網(wǎng)面（polygonmesh），以表示各種物體的形狀．下圖是三角形網(wǎng)面和四邊形網(wǎng)面示意圖。北京理工大學(xué)計(jì)算機(jī)系平面多邊形網(wǎng)面表示：(1)一系列平面多邊形的頂點(diǎn)坐標(biāo)表．表示直觀；問題：一個(gè)頂點(diǎn)在表中重復(fù)出現(xiàn)多次．(2)頂點(diǎn)從1到n進(jìn)行編號表示，頂點(diǎn)在表中僅出現(xiàn)一次，問題：這種頂點(diǎn)表不能明顯地表示相鄰表面的邊界，對于一給定頂點(diǎn)，也不能有效地發(fā)現(xiàn)所有包含此頂點(diǎn)的表面．北京理工大學(xué)計(jì)算機(jī)系翼邊緣數(shù)據(jù)結(jié)構(gòu)(WingedEdgeDataStructure)．

一種網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)，它具有三種類型數(shù)據(jù)記錄：頂點(diǎn)、邊和面．沿著數(shù)據(jù)結(jié)構(gòu)包含的數(shù)據(jù)指針可以找到所有元素的鄰接關(guān)系，而無須搜索整個(gè)網(wǎng)面，也無須將每一元素的所有鄰接元素都存儲起來．在多邊形網(wǎng)面中，每一個(gè)頂點(diǎn)對應(yīng)數(shù)據(jù)結(jié)構(gòu)中的一個(gè)頂點(diǎn)記錄，每一個(gè)面對應(yīng)一個(gè)面記錄、每一條邊對應(yīng)一個(gè)邊記錄。這樣，可以直接查詢一條邊對應(yīng)的兩個(gè)頂點(diǎn)和兩個(gè)多邊形面，也可以直接查詢一個(gè)頂點(diǎn)對應(yīng)的所有多邊形面（或邊），查詢時(shí)間正比于該頂點(diǎn)對應(yīng)的多邊形面（或邊）的數(shù)北京理工大學(xué)計(jì)算機(jī)系多邊形面（或邊）的位置可以由頂點(diǎn)的坐標(biāo)計(jì)算出來．每一個(gè)面記錄指向該面的某一個(gè)邊記錄，每一個(gè)頂點(diǎn)記錄指向該頂點(diǎn)對應(yīng)的邊記錄。邊記錄包含將多邊形面及其頂點(diǎn)連結(jié)成多邊形網(wǎng)面的指針，并且允許對多邊形網(wǎng)面頂點(diǎn)進(jìn)行快速的掃描．具體地說，每一個(gè)邊記錄包含有兩個(gè)端點(diǎn)指針，其兩側(cè)的兩個(gè)多邊形面指針和4個(gè)鄰接翼指針