計(jì)算機(jī)圖形學(xué)-cg lesson polygonal object and data structure物體多邊形表示及數(shù)據(jù)結(jié)構(gòu)

浙江大學(xué)CAD&CG 空間任何一點(diǎn)可以用三個(gè)坐標(biāo)(xyz) y z

z 有不同的表示形式。 表示

球心在原(x-1)2+(y-1)2+(z-1)2- 球心在最終表達(dá)式：x2+y2+z2-2x-2y-表示1最為簡(jiǎn)單，表示2 z局部坐

世界坐 l在局部坐標(biāo)系中而不是在世界坐標(biāo)系中直ll在同一幾何場(chǎng)景中，同一個(gè)幾何物體可能會(huì)標(biāo)系到世界坐標(biāo)系變換所得到的： yYx 局部坐標(biāo)系中的變

X世界坐標(biāo)系中的變 l世界坐標(biāo)系和局部(景物)坐標(biāo)系之間的關(guān) 幾何物體的多邊 多邊形表示的來(lái) 多邊形表示與2－流 多邊形表示的半邊數(shù)據(jù) 多邊形表示的不 幾何物體的多邊 多邊形表示的來(lái) 多邊形表示與2－流 多邊形表示的半邊數(shù)據(jù) 多邊形表示的不 l物體的多邊形表用大量平面多邊形(三角形、四邊形或者n)來(lái)近幾何l物體的多邊形表示優(yōu)點(diǎn) 線框

原始法 (c)平均法 多邊形表示的野鴨模型：6656個(gè)面片，3474個(gè)頂 幾何物體的多邊 多邊形表示的來(lái) 多邊形表示與2－流 多邊形表示的半邊數(shù)據(jù) 多邊形表示的不 ll原始數(shù)據(jù)一般為三中l(wèi)采用適當(dāng)?shù)闹亟ㄋ惴ú拍艿胠該方法適用于數(shù)學(xué)公式難以 ll常用的幾何物體數(shù)學(xué)表示l滿足精度的曲面物體多邊形近

參數(shù)曲面的多邊形細(xì)分曲面的多邊形 隱式曲面的多邊形 幾何物體的多邊 多邊形表示的來(lái) 多邊形表示與2－流 多邊形表示的半邊數(shù)據(jù) 多邊形表示的不 非流 閉流 開流 l2－流形上的每一點(diǎn)都存在一個(gè)位于流形內(nèi)的任意小開 非流形頂點(diǎn)：兩個(gè)流形交于一 非流形邊：一條邊與三 自相交 幾何物體的多邊 多邊形表示的來(lái) 多邊形表示與2－流 多邊形表示的半邊數(shù)據(jù) 多邊形表示的不 由WavefrontTechnologies首先 沒(méi)有尺寸，可以在注釋 法向表(nx,ny,nz)：可以控制物體繪制時(shí)的光滑程度 (面片)法向：繪制出來(lái)的多邊形物體棱角分明，見(jiàn)圖 (頂點(diǎn))法向：則繪制出來(lái)的多邊形物體是光滑的，見(jiàn)圖 vi=(xiyizi)i=1,2,…,頂點(diǎn)數(shù)vna=(nxanyanza)a=1,2,…法向數(shù)fs=(…,vi/vtp/vna,vj/vtq/vnb,vk/vtr/vnc,…s=1,2,…,i,j,k,…面片 詳細(xì)信息見(jiàn)課件中“ObjectFiles 空間的考 拓?fù)渖? 算法上的考慮 半邊結(jié)構(gòu)(Half-EdgeStructure)：可定向 每條邊被記為兩條半邊，記錄每條半 鄰接面的指針(如果為邊界，指針為NULL 面：邊界上的一 頂

e3,2f2

面

e3,2f2e4,1

面 優(yōu) 操作時(shí)間(通常) CGAL(ComputationalGeometryAlgorithmsLibrary) 幾何物體的多邊 多邊形表示的來(lái) 多邊形表示與2－流 多邊形表示的半邊數(shù)據(jù) 多邊形表示的不 l在表示復(fù)雜拓?fù)浜途哂胸S富細(xì)節(jié)的物體時(shí)， 16.7×106個(gè)多邊 四叉樹與八叉樹(Quadtree& k-d-樹(k-d- 二叉空間剖分樹(BSPtreeBinarySpacePartitiontree) CAD&CG國(guó) 給定：平面點(diǎn)集PQ=[x1x2][y1 如果P中只有一個(gè)點(diǎn)，則四叉樹只有一個(gè)葉節(jié)點(diǎn) Q和 l四叉樹空間復(fù)雜度和構(gòu)造時(shí)間復(fù)雜度：一個(gè)深度為d、有n個(gè)點(diǎn)的四叉樹，其節(jié)點(diǎn)數(shù)目為 kd-樹(k-d-treekd- 空間剖分樹(binaryspacepartitioning 然后，對(duì)于兩個(gè)子集D<s和D>s，分別選擇剖分線Y=t1和 遞歸執(zhí)行上述步驟，直至每一個(gè)葉節(jié)點(diǎn)包含一 l每個(gè)中間節(jié)點(diǎn)對(duì)應(yīng)一個(gè)剖 計(jì)算kd-樹節(jié)點(diǎn)的矩形R(v，如果 n)，其中a為結(jié)果 二叉空間剖分樹BSPtreeBinarySpacePartitiontree kd-樹的 應(yīng)用于景物空間的物體排序與消 與上述層次數(shù)據(jù)結(jié)構(gòu)的

集合，關(guān)于O的層次包圍盒BVH(O為 關(guān)于BVH定義中的兩個(gè)參 l子節(jié)點(diǎn)數(shù)目n(v)：大部分情況是二叉樹，也 BVH設(shè)計(jì)原則 性 相關(guān)參 wavefrontO