第五章

圖形變換與裁剪計(jì)算機(jī)學(xué)院蘇小紅二維圖形的顯示流程計(jì)算機(jī)學(xué)院蘇小紅5.1窗口視圖變換

1.窗口和視圖區(qū)用戶坐標(biāo)系（worldcoordinatesystem，簡稱WC）設(shè)備坐標(biāo)系（devicecoordinatesystem，簡稱DC）窗口區(qū)（window）視圖區(qū)（viewport）計(jì)算機(jī)學(xué)院蘇小紅2.窗口到視圖區(qū)的變換窗口區(qū)與視圖區(qū)間的映射關(guān)系：窗口區(qū)中的任一點(diǎn)(xw,yw)

與視圖區(qū)中的任一點(diǎn)(xv,yv)存在如下對(duì)應(yīng)關(guān)系：（5-1）（5-2）XwOwWxlWxrYwWybWyt窗口(xw,yw)YuXuOuVxlVxrVybVyt視圖區(qū)(xv,yv)窗口與視圖區(qū)的對(duì)應(yīng)關(guān)系計(jì)算機(jī)學(xué)院蘇小紅

（5-3）（5-4）由式（5-1）和式（5-2）可分別解得：令有（5-5）

（5-6）

計(jì)算機(jī)學(xué)院蘇小紅5.2二維圖形幾何變換5.2.1二維圖形幾何變換的原理二維圖形由點(diǎn)或直線段組成直線段可由其端點(diǎn)坐標(biāo)定義二維圖形的幾何變換：對(duì)點(diǎn)或?qū)χ本€段端點(diǎn)的變換計(jì)算機(jī)學(xué)院蘇小紅1.平移變換（translation）平行于x軸的方向上的移動(dòng)量平行于y軸的方向上的移動(dòng)量

5.2.2幾種典型的二維圖形幾何變換xy平移變換（5-7）（5-8）計(jì)算機(jī)學(xué)院蘇小紅平行于x軸的方向上的縮放量平行于y軸的方向上的縮放量2.比例變換（scale）指相對(duì)于原點(diǎn)的比例變換

yx相對(duì)于原點(diǎn)的比例變換相對(duì)于重心的比例變換yx重心（5-10）（5-9）計(jì)算機(jī)學(xué)院蘇小紅比例變換的性質(zhì)當(dāng)時(shí)，變換前的圖形與變換后的圖形相似當(dāng)時(shí)，圖形將放大，并遠(yuǎn)離坐標(biāo)原點(diǎn)當(dāng)時(shí)，圖形將縮小，并靠近坐標(biāo)原點(diǎn)當(dāng)時(shí)，圖形將發(fā)生畸變計(jì)算機(jī)學(xué)院蘇小紅3.旋轉(zhuǎn)變換（rotation）

點(diǎn)P繞原點(diǎn)逆時(shí)針轉(zhuǎn)θ度角（設(shè)逆時(shí)針旋轉(zhuǎn)方向?yàn)檎较颍?-11）（5-12）將式（5-11）代入式（5-12）得：（5-13）（5-14）yx旋轉(zhuǎn)變換計(jì)算機(jī)學(xué)院蘇小紅5.2.3齊次坐標(biāo)（homogeneouscoordinates）技術(shù)

1.齊次坐標(biāo)技術(shù)的引入平移、比例和旋轉(zhuǎn)等變換的組合變換處理形式不統(tǒng)一，將很難把它們級(jí)聯(lián)在一起。

2.變換具有統(tǒng)一表示形式的優(yōu)點(diǎn)便于變換合成便于硬件實(shí)現(xiàn)3.齊次坐標(biāo)技術(shù)的基本思想

把一個(gè)n維空間中的幾何問題轉(zhuǎn)換到n+1維空間中解決。計(jì)算機(jī)學(xué)院蘇小紅4.齊次坐標(biāo)表示齊次坐標(biāo)表示不是唯一的

有n個(gè)分量的向量有n+1個(gè)分量的向量啞元或標(biāo)量因子規(guī)格化的齊次坐標(biāo)計(jì)算機(jī)學(xué)院蘇小紅5.基本幾何變換的齊次坐標(biāo)表示

平移變換

比例變換旋轉(zhuǎn)變換：6.無窮遠(yuǎn)點(diǎn)或無窮遠(yuǎn)區(qū)域的齊次坐標(biāo)表示

時(shí)，齊次坐標(biāo)表示一個(gè)n維的無窮遠(yuǎn)點(diǎn)逆時(shí)針為正

計(jì)算機(jī)學(xué)院蘇小紅5.2.3常用的二維幾何變換

1.對(duì)稱變換（symmetry）（反射變換或鏡像變換）（1）相對(duì)于y軸對(duì)稱（2）相對(duì)于x軸對(duì)稱oyx對(duì)稱變換（1）yxo對(duì)稱變換（2）計(jì)算機(jī)學(xué)院蘇小紅（3）相對(duì)于原點(diǎn)對(duì)稱（即中心對(duì)稱）（4）相對(duì)于直線y=x對(duì)稱oxy對(duì)稱變換（3）xyoy=x對(duì)稱變換（4）計(jì)算機(jī)學(xué)院蘇小紅（5）相對(duì)于直線y=-x對(duì)稱xyoy=-x對(duì)稱變換（5）計(jì)算機(jī)學(xué)院蘇小紅2.錯(cuò)切變換（shear）（1）沿x軸方向關(guān)于y軸錯(cuò)切將圖形上關(guān)于y軸的平行線沿x方向推成θ角的傾斜線，而保持y坐標(biāo)不變?！鱴

錯(cuò)切變換（1）yx計(jì)算機(jī)學(xué)院蘇小紅（2）沿y軸方向關(guān)于x軸錯(cuò)切將圖形上關(guān)于x軸的平行線沿y方向推成Ψ角的傾斜線，而保持x坐標(biāo)不變。

錯(cuò)切變換（2）yx△y計(jì)算機(jī)學(xué)院蘇小紅問題：如何實(shí)現(xiàn)復(fù)雜變換？變換分解變換合成5.3.3二維組合變換計(jì)算機(jī)學(xué)院蘇小紅1.相對(duì)于任意點(diǎn)（x0,y0）的比例變換對(duì)任意點(diǎn)比例變換的步驟：（1）平移變換（2）相對(duì)于原點(diǎn)的比例變換（3）平移變換

當(dāng)（x0,y0）為圖形重心的坐標(biāo)時(shí)，這種變換實(shí)現(xiàn)的是相對(duì)于重心的比例變換。計(jì)算機(jī)學(xué)院蘇小紅令任意點(diǎn)比例變換示意圖平移平移比例則有計(jì)算機(jī)學(xué)院蘇小紅2.繞任意點(diǎn)（x0,y0）的旋轉(zhuǎn)變換繞任意點(diǎn)旋轉(zhuǎn)變換的步驟：（1）平移變換（2）對(duì)圖形繞原點(diǎn)進(jìn)行旋轉(zhuǎn)變換（3）平移變換

θ(x2,y2)(x3,y3)(x0,y0)θOxy(x1,y1)(x4,y4)相對(duì)于任意點(diǎn)(x0,y0)的旋轉(zhuǎn)變換計(jì)算機(jī)學(xué)院蘇小紅任意點(diǎn)旋轉(zhuǎn)變換示意圖平移平移旋轉(zhuǎn)令則有計(jì)算機(jī)學(xué)院蘇小紅變換的結(jié)果與變換的順序有關(guān)（矩陣乘法不可交換）變換的固定坐標(biāo)系模式相對(duì)于同一個(gè)固定坐標(biāo)系先調(diào)用的變換先執(zhí)行，后調(diào)用的變換后執(zhí)行計(jì)算機(jī)學(xué)院蘇小紅三維幾何變換（1/7）三維齊次坐標(biāo)(x,y,z)點(diǎn)對(duì)應(yīng)的齊次坐標(biāo)為標(biāo)準(zhǔn)齊次坐標(biāo)(x,y,z,1)右手坐標(biāo)系

xyz計(jì)算機(jī)學(xué)院蘇小紅三維幾何變換（2/7）平移變換

放縮變換計(jì)算機(jī)學(xué)院蘇小紅三維幾何變換（3/7）旋轉(zhuǎn)變換:右手螺旋方向?yàn)檎@x軸yxyzz’y’zoox軸指向紙外繞軸旋轉(zhuǎn)角計(jì)算機(jī)學(xué)院蘇小紅三維幾何變換（4/7）繞z軸繞y軸計(jì)算機(jī)學(xué)院蘇小紅三維幾何變換（5/7）對(duì)稱變換關(guān)于坐標(biāo)平面xy的對(duì)稱變換計(jì)算機(jī)學(xué)院蘇小紅三維幾何變換錯(cuò)切變換zyxzyxzyxzyxzyxzyx三維錯(cuò)切變換沿z含x錯(cuò)切沿z含y錯(cuò)切沿y含x錯(cuò)切沿y含z錯(cuò)切沿x含y錯(cuò)切

沿x含z錯(cuò)切計(jì)算機(jī)學(xué)院蘇小紅三維幾何變換（7/7）三維變換的一般形式哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅32第五章

圖形變換與裁剪

投影變換計(jì)算機(jī)學(xué)院蘇小紅33基本內(nèi)容1三維圖形的基本問題平面幾何投影平行投影透視投影34三維圖形的基本問題（1/5）顯示器屏幕、繪圖紙等是二維的顯示對(duì)象是三維的解決方法----投影三維顯示設(shè)備正在研制中1.在二維屏幕上如何顯示三維物體？35三維圖形的基本問題（2/5）2.如何表示三維物體？二維形體的表示----直線段,折線,曲線段,多邊形區(qū)域二維形體的輸入----簡單（圖形顯示設(shè)備與形體的維數(shù)一致）三維形體的表示----空間直線段、折線、曲線段、多邊形、曲面片三維形體的輸入、運(yùn)算、有效性保證----困難解決方法----各種用于形體表示的理論、模型、方法36三維圖形的基本問題（3/5）3.如何反映遮擋關(guān)系？物體之間或物體的不同部分之間存在相互遮擋關(guān)系遮擋關(guān)系是空間位置關(guān)系的重要組成部分解決方法----消除隱藏面與隱藏線37三維圖形的基本問題（4/5）何謂真實(shí)感圖形？逼真的示意的人們觀察現(xiàn)實(shí)世界產(chǎn)生的真實(shí)感來源于空間位置關(guān)系----近大遠(yuǎn)小的透視關(guān)系和遮擋關(guān)系光線傳播引起的物體表面顏色的自然分布解決方法建立光照明模型開發(fā)真實(shí)感圖形繪制方法4.如何產(chǎn)生真實(shí)感圖形38三維圖形的基本問題（5/5）三維圖形的基本研究內(nèi)容投影三維形體的表示消除隱藏面與隱藏線建立光照明模型、研究真實(shí)感圖形繪制方法39照像機(jī)模型與投影

如何投影?生活中的類比--如何拍攝景物？拍攝過程選景取景--裁剪對(duì)焦—參考點(diǎn)按快門--成像移動(dòng)方式移動(dòng)景物移動(dòng)照相機(jī)兩個(gè)坐標(biāo)系平面幾何投影（1/17）40投影—照相機(jī)模型選定投影類型

設(shè)置投影參數(shù)–拍攝方向、距離等三維裁剪

–取景投影和顯示

–成像簡單的三維圖形顯示流程圖二平面幾何投影（2/17）41平面幾何投影及其分類

投影將n維的點(diǎn)變換成小于n維的點(diǎn)

將3維的點(diǎn)變換成小于3維的點(diǎn)投影中心(COP:CenterofProjection)視覺系統(tǒng)—觀察點(diǎn)、視點(diǎn)電影放映機(jī)—光源投影面不經(jīng)過投影中心平面--照相機(jī)底片曲面—球幕電影,視網(wǎng)膜平面幾何投影（3/17）42平面幾何投影（4/17）投影線從投影中心向物體上各點(diǎn)發(fā)出的射線

直線—光線曲線—噴繪平面幾何投影

投影面是平面投影線為直線投影變換投影過程投影的數(shù)學(xué)表示43平面幾何投影（5/17）投影分類投影中心與投影平面之間的距離為無限

投影中心與投影平面之間的距離為有限

44平面幾何投影（6/17）透視投影平行投影45平面幾何投影（7/17）平行投影

投影中心與投影平面之間的距離為無限是透視投影的極限狀態(tài)投影方向投影平面46平面幾何投影（8/17）正投影與斜投影正平行投影斜平行投影47平面幾何投影（9/17）三視圖：正視圖、側(cè)視圖和俯視圖

yzx主視圖俯視圖側(cè)視圖圖3一個(gè)直角棱臺(tái)的三視圖48解決：投影平面不垂直于任何一個(gè)坐標(biāo)軸——正軸測投影

yxz圖5正軸測投影平面的定義投影方程：平面幾何投影（10/17）49120°120°120°(a)正等軸測yzx投影平面三個(gè)單位向量將投影成三個(gè)長度相等的平面向量，即三根坐標(biāo)軸有相同的變形系數(shù)正方體的正等軸測投影

平面幾何投影（11/17）50正方體的正軸測投影(c)正三軸測yzx投影平面(b)正二軸測投影平面yzx平面幾何投影（12/17）51透視投影投影中心與投影平面之間的距離為有限參數(shù)：投影方向，距離例子：室內(nèi)白熾燈的投影，視覺系統(tǒng)特點(diǎn)：產(chǎn)生近大遠(yuǎn)小的視覺效果，由它產(chǎn)生的圖形深度感強(qiáng)，看起來更加真實(shí)。平面幾何投影（13/17）52

透視投影投影方程yxz投影中心dx’y’P’Pyxz投影平面一點(diǎn)透視平面幾何投影（14/17）53滅點(diǎn)的個(gè)數(shù)?滅點(diǎn)：不平行于投影平面的平行線，經(jīng)過透視投影之后相交于一點(diǎn)，稱為滅點(diǎn).yxzz軸滅點(diǎn)圖7正方體的一點(diǎn)透視及其滅點(diǎn)空間平行線可認(rèn)為是相交于無窮遠(yuǎn)點(diǎn)，滅點(diǎn)可以看成是無窮遠(yuǎn)點(diǎn)經(jīng)透視投影后得到的點(diǎn)滅點(diǎn)的位置?無窮遠(yuǎn)點(diǎn)滅點(diǎn)平面幾何投影（15/17）54一點(diǎn)透視兩點(diǎn)透視三點(diǎn)透視主滅點(diǎn):平行于坐標(biāo)軸的平行線產(chǎn)生的滅點(diǎn)。一點(diǎn)透視兩點(diǎn)透視三點(diǎn)透視主滅點(diǎn)的個(gè)數(shù)由什么決定?平面幾何投影（16/17）55平面幾何投影（17/17）56第五章圖形變換與裁剪（三）

5.5二維線段裁剪蘇小紅計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)575.5二維線段裁剪1直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)分割裁剪算法梁友棟-Barsky算法2多邊形裁剪

Sutherland_Hodgman算法

Weiler-Atherton算法

581.直線段裁剪(1/18)裁剪（clipping）的目的判斷圖形元素是否在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分裁剪處理的基礎(chǔ)圖元關(guān)于窗口內(nèi)外關(guān)系的判別圖元與窗口的求交裁剪與覆蓋的區(qū)別591.直線段裁剪(2/18)裁剪窗口矩形、圓形、一般多邊形被裁剪對(duì)象線段、多邊形、曲線、字符設(shè)計(jì)裁剪算法的核心問題效率高，速度快601.直線段裁剪(3/18)把直線當(dāng)作點(diǎn)的集合，逐點(diǎn)裁剪點(diǎn)(x,y)在窗口內(nèi)的充分必要條件是：

問題：極其費(fèi)時(shí)，精度不高。611.直線段裁剪(4/18)把直線當(dāng)作一個(gè)整體來裁剪矩形裁剪窗口：

[xmin，xmax]

[ymin，ymax]待裁剪線段：前提：任何平面線段在凸多邊形窗口進(jìn)行裁剪后，落在窗口內(nèi)的線段不會(huì)多于1條。621.直線段裁剪(5/18)待裁剪線段和窗口的關(guān)系完全落在窗口內(nèi),完全落在窗口外,部分在內(nèi)，部分在外.635.5二維線段裁剪1直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)分割裁剪算法梁友棟-Barsky算法64直接求交算法直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。1.直線段裁剪(6/18)655.5二維線段裁剪1直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)分割裁剪算法梁友棟-Barsky算法66Cohen-Sutherland算法1.直線段裁剪(7/18)為提高效率，該算法強(qiáng)調(diào)：快速判斷情形(1)(2)；減少情形(3)的求交次數(shù)和求交所需的計(jì)算量。待裁剪線段和窗口的關(guān)系完全落在窗口內(nèi),完全落在窗口外,部分在內(nèi)，部分在外.67Cohen-Sutherland算法算法步驟：判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，則線段完全可見，轉(zhuǎn)至第4步；判別線段是否為顯然不可見，如果是，則裁剪結(jié)束，轉(zhuǎn)至第4步；求線段與窗口邊延長線的交點(diǎn)，這個(gè)交點(diǎn)將線段分為兩段，其中一段顯然不可見，丟棄。對(duì)余下的另一段重新進(jìn)行第1步處理，結(jié)束裁剪過程是遞歸的。1.直線段裁剪(8/18)68關(guān)鍵問題：如何快速判別完全可見和完全不可見線段？解決方法——編碼：由窗口四條邊所在直線把二維平面分成9個(gè)區(qū)域，每個(gè)區(qū)域賦予一個(gè)四位編碼，CtCbCrCl，上下右左；Cohen-Sutherland

算法1.直線段裁剪(9/18)11100000011100000011100000011100000069端點(diǎn)編碼：定義為它所在區(qū)域的編碼快速判斷“完全不可見”

線段兩端點(diǎn)編碼的邏輯“與”運(yùn)算結(jié)果非零

，則完全不可見。Cohen-Sutherland算法1.直線段裁剪(10/18)所以也稱為編碼裁剪算法70逐個(gè)端點(diǎn)判斷其編碼ClCtCrCb中各位是否為“1”，若是，則需求交。最壞情形：線段求交四次。對(duì)于那些部分可見又部分不可見的線段，需要求交，求交前先測試與窗口哪條邊所在直線有交？Cohen-Sutherland算法1.直線段裁剪(11/18)71

1）特點(diǎn)：用編碼方法可快速判斷線段-——

完全可見或完全不可見。

2）特別適用兩種場合：大窗口場合；窗口特別小的場合（如：光標(biāo)拾取圖形時(shí)，光標(biāo)看作小的裁剪窗口）1.直線段裁剪(12/18)Cohen-Sutherland算法725.5二維線段裁剪1直線段裁剪

直接求交算法

Cohen-Sutherland算法

中點(diǎn)分割裁剪算法梁友棟-Barsky算法73中點(diǎn)分割法基本思想：利用對(duì)分搜索思想搜索交點(diǎn)從P1點(diǎn)出發(fā)找出距P1最近的可見點(diǎn)從P2點(diǎn)出發(fā)找出距P2最近的可見點(diǎn)不斷地在中點(diǎn)處將線段一分為二，對(duì)每段線段重復(fù)Cohen-Sutherland裁剪算法的線段可見性測試方法，直至找到每段線段與窗口邊界線的交點(diǎn)或分割子段的長度充分小可視為一點(diǎn)為止取中點(diǎn)Pm=(P1+P2)/2。P2P1從P1點(diǎn)出發(fā)找距P1最近的可見點(diǎn)PmP1用P1Pm代替P1P2P2P2用PmP2代替P1P2PmP11.直線段裁剪(13/18)741.直線段裁剪(13/18)優(yōu)點(diǎn)：算法原理和編碼裁剪是一致的，不同之處在于用移位運(yùn)算代替求交計(jì)算適合硬件實(shí)現(xiàn)中點(diǎn)分割法755.5二維線段裁剪1直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)分割裁剪算法

梁友棟-Barsky算法76Liang-Barsky裁剪算法

P4P1P3P2ymaxyminxminxmaxRTSULABAS是一維窗口TS中的可見部分1.直線段裁剪(14/18)基本思想：把二維裁剪化為一維裁剪問題，并向x（或y）方向投影以決定可見線段77Liang-Barsky裁剪算法

直線L與區(qū)域的交：1.直線段裁剪(15/18)P4P1P3P2ymaxyminxminxmaxRTSULABP4P1P3P2ymaxyminxminxmaxRTSULAB當(dāng)Q為空集時(shí)，線段AB不可能在窗口中有可見線段。當(dāng)Q不為空集時(shí)，Q可看成是一個(gè)一維窗口

78存在可見線段的充要條件即不為空集。1.直線段裁剪(16/18)P4P1P3P2ymaxyminxminxmaxRTSULABP4P1P3P2ymaxyminxminxmaxRTSULAB當(dāng)Q為空集時(shí)，線段AB不可能在窗口中有可見線段。當(dāng)Q不為空集時(shí)，Q可看成是一個(gè)一維窗口。

79Liang-Barsky裁剪算法

1.直線段裁剪(17/18)向x軸投影，得到可見線段端點(diǎn)的x坐標(biāo)變化范圍

左端點(diǎn)x坐標(biāo)右端點(diǎn)x坐標(biāo)RS,AB,TU三條線段的交集的端點(diǎn)坐標(biāo)等價(jià)于求三條線段的左端點(diǎn)的最大值，右端點(diǎn)的最小值

y坐標(biāo)可由將x坐標(biāo)代入直線方程計(jì)算得到P4P1P3P2ymaxyminxminxmaxRTSULABAS是一維窗口TS中的可見部分URTS80Liang-Barsky裁剪算法AB有可見部分的充要條件也可表示為1.直線段裁剪(18/18)P4P1P3P2ymaxyminxminxmaxRTSULABAS是一維窗口TS中的可見部分URTS815.5二維線段裁剪1直線段裁剪

直接求交算法

Cohen-Sutherland算法中點(diǎn)分割裁剪算法梁友棟-Barsky算法2多邊形裁剪

Sutherland_Hodgman算法

Weiler-Atherton算法

822.多邊形裁剪（Ploygonclipping）-1/3錯(cuò)覺：多邊形裁剪是直線段裁剪的組合？新的問題：圖1因丟失頂點(diǎn)信息而去法確定裁剪區(qū)域ABAB圖2原來封閉的多邊形變成了孤立的線段邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它8312123(a)(b)(c)AB裁剪后的多邊形頂點(diǎn)形成的幾種情況分裂為幾個(gè)多邊形2.多邊形裁剪-2/384關(guān)鍵：不僅在于求出新的頂點(diǎn)，刪去界外頂點(diǎn)還在于形成正確的頂點(diǎn)序列常用算法

Sutherland_Hodgman算法

Weiler-Atherton算法

2.多邊形裁剪-3/385Sutherland-Hodgman算法-1/4分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。流水線過程(左上右下)：左邊的結(jié)果是右邊的開始。亦稱逐邊裁剪算法86Sutherland-Hodgman算法-2/4內(nèi)側(cè)空間與外側(cè)空間多邊形的邊與半空間的關(guān)系

線段與當(dāng)前裁剪邊的位置關(guān)系可見一側(cè)窗口(a)輸出Pi+1當(dāng)前裁剪邊Pi+1Pi可見一側(cè)窗口(a)無輸出當(dāng)前裁剪邊Pi+1Pi可見一側(cè)窗口(a)輸出I當(dāng)前裁剪邊Pi+1Pi可見一側(cè)窗口(a)輸出I和Pi+1當(dāng)前裁剪邊Pi+1PiII87Sutherland-Hodgman算法-3/4裁剪結(jié)果的頂點(diǎn)構(gòu)成：裁剪邊內(nèi)側(cè)的原頂點(diǎn)；多邊形的邊與裁剪邊的交點(diǎn)。順序連接。幾點(diǎn)說明：裁剪算法采用流水線方式，適合硬件實(shí)現(xiàn)?？赏茝V到任意凸多邊形裁剪窗口88Sutherland-Hodgman算法-4/4

存在的問題逐邊裁剪要求裁剪窗口為凸多邊形，那么凹多邊形窗口怎么辦？

逐邊裁剪法對(duì)凹多邊形裁剪時(shí)，裁剪后分裂為幾個(gè)多邊形，這幾個(gè)多邊形沿邊框產(chǎn)生多余的線段？圖6逐邊裁剪法對(duì)凹多邊形裁剪時(shí)可能出現(xiàn)的問題321876954103217654108932174108956原圖對(duì)左邊裁對(duì)頂邊裁32174108956對(duì)右邊裁對(duì)底邊裁Demo89Weiler-Atherton算法-1/7裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為SP裁剪多邊形：裁剪窗口，記為CP90約定：SP與CP均用它們頂點(diǎn)的環(huán)形鏈表定義外邊界取順時(shí)針方向內(nèi)邊界取逆時(shí)針方向使得沿多邊形的邊走動(dòng)，其右邊為多邊形的內(nèi)部。Weiler-Atherton算法-2/7C2C1C3C4C8C7C5C6I1I8I2I3I4I5I6I791SP和CP把二維平面分成兩部分。內(nèi)裁剪：SP∩CP外裁剪：SP-CPWeiler-Atherton算法-3/7裁剪結(jié)果區(qū)域的邊界由兩部分構(gòu)成：SP的部分邊界CP的部分邊界且在交點(diǎn)處，邊界發(fā)生交替即由SP邊界轉(zhuǎn)至CP邊界或由CP邊界轉(zhuǎn)至SP邊界

92Weiler-Atherton算法-4/7如果SP與CP有交點(diǎn)，則交點(diǎn)成對(duì)出現(xiàn)，它們被分為如下兩類：進(jìn)點(diǎn)：SP邊界由此進(jìn)入CP

如，I1,I3,I5,I7,I9,I11出點(diǎn)：SP邊界由此離開CP

如，I0,I2,I4,I6,I8,I10

93Weiler-Atherton算法-5/7由任一個(gè)進(jìn)點(diǎn)出發(fā)，沿SP的邊，跟蹤檢測其與CP的交點(diǎn)（前交點(diǎn)），并判斷該交點(diǎn)是進(jìn)點(diǎn)還是出點(diǎn)。若是進(jìn)點(diǎn)：則沿SP邊所示方向收集頂點(diǎn)序列。若是出點(diǎn)：則從此點(diǎn)開始，檢測CP的邊所示方向收集頂點(diǎn)序列。如此交替沿兩個(gè)多邊形的邊行進(jìn)。直至回到跟蹤的起始點(diǎn)為止。94Weiler-Atherton算法-6/7C2C1C3C4S1S2S3S4S5S6I1I2I3I4I5I6I7I8裁剪多邊形CP主多邊形SP算法裁剪后所生成的多邊形為I1I2I3S3I4I5I6I7S6I8I1主多邊形表裁剪多邊形表S1S2I1S3S4S5S6I2I3I4I5I6I7I8C1C2I3I4C4I8I1I2I5C3I5I6S1I7C1開始結(jié)束95Weiler-Atherton算法-7/7C2C1C3C4C8C7C5C6S2S1S3S4S8S7S5S6I1I8I2I3I4I5I6I7主多邊形表裁剪多邊形表S1S2I1I4S4S6I5I2I3S3S1S5S7I6S8I7I8S5C1C2C3C4I4I5I1I8C1C5C5C6I2I3I6C7C8I7算法裁剪后所生成的多邊形為I1I2I7I8I1和I3I4I5I6I3

裁剪多邊形CP主多邊形SP開始開始結(jié)束結(jié)束蘇小紅哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第6章實(shí)體幾何造型基礎(chǔ)實(shí)體造型（SolidModeling）幾何造型技術(shù)第一代：手工繪制工程圖第二代：二維計(jì)算機(jī)繪圖第三代：三維線架系統(tǒng)第四代：曲面造型第五代：實(shí)體造型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅97三維實(shí)體的表示（1/7）模型分類哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅98完全以數(shù)據(jù)描述規(guī)則形體的建模方法邊界表示分解表示構(gòu)造表示以過程和控制參數(shù)描述不規(guī)則形體的建模方法隨機(jī)插值模型迭代函數(shù)系統(tǒng)L系統(tǒng)粒子系統(tǒng)動(dòng)力系統(tǒng)三維實(shí)體的表示（2/7）過程模型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅99包括----隨機(jī)插值模型、迭代函數(shù)系統(tǒng)、L系統(tǒng)、粒子系統(tǒng)、復(fù)變函數(shù)迭代等以一個(gè)過程和相應(yīng)的控制參數(shù)描述例如用一些控制參數(shù)和一個(gè)生成規(guī)則描述的植物以一個(gè)數(shù)據(jù)文件和一段代碼的形式存在三維實(shí)體的表示（3/7）數(shù)據(jù)模型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅100完全以數(shù)據(jù)描述例如用以8個(gè)頂點(diǎn)表示的立方體以中心點(diǎn)和半徑表示的球以數(shù)據(jù)文件的形式存在包括----邊界表示、分解表示、構(gòu)造表示等三維實(shí)體的表示（6/7）線框模型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅101相鄰頂點(diǎn)連接構(gòu)成棱邊表示幾何形狀特征形體表示成一組輪廓線的集合，只需建立三維線段表數(shù)據(jù)結(jié)構(gòu)簡單、處理速度快所構(gòu)成的圖形含義不確切，與形體之間不存在一一對(duì)應(yīng)關(guān)系，有二義性不能計(jì)算面積、體積等物理量，不便進(jìn)行光照或消隱處理，不適合真實(shí)感顯示和數(shù)控加工----物體的骨架圖6-8用線框模型表示的有二義性的物體可以有三種不同的理解，從三個(gè)方向中的一個(gè)方向打一個(gè)方孔

三維實(shí)體的表示（7/7）表面模型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅102----物體的皮膚用有向棱邊圍成的部分來定義形體表面，由面的集合來定義形體形體與其表面一一對(duì)應(yīng)，避免了二義性能夠滿足真實(shí)感顯示和數(shù)控加工等需求能夠計(jì)算面積，表達(dá)物體的表面形狀，只有面的信息，形體信息不完整進(jìn)行剖切操作時(shí)，內(nèi)部為空洞，無法計(jì)算和分析物體的整體性質(zhì)（如體積、重心等），限制了在工程分析方面的應(yīng)用在面模型上打孔，內(nèi)部為“空洞”三維實(shí)體的表示（7/7）實(shí)體模型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅103----”有血有肉”的物體模型主要是明確定義了表面的哪一側(cè)存在實(shí)體，在表面模型的基礎(chǔ)上，使用表面的外法線矢量方向來指明實(shí)體存在的一側(cè)，例如規(guī)定正向指向體外。通常用有向棱邊隱含地表示表面的外法線矢量方向在定義表面時(shí)，有向棱邊按右手法則取向，沿著閉合的棱邊所得的方向與表面外法線矢量方向一致。用此方法還可檢查形體的拓?fù)湟恢滦?，拓樸合法的形體在相鄰兩個(gè)面的公共邊界上，棱邊的方向正好相反。包含描述實(shí)體所需的較多信息，如幾何信息、拓?fù)湫畔?，表示完整而無歧義。實(shí)現(xiàn)所有的CAD/CAM任務(wù)，保證CAD/CAM的自動(dòng)化三種表示模型的功能比較哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅104多面體模型（1/10）每個(gè)多邊形的數(shù)據(jù)被存儲(chǔ)在多邊形數(shù)據(jù)表中多邊形數(shù)據(jù)表可分兩組：幾何表包括物體的幾何數(shù)據(jù)（如頂點(diǎn)坐標(biāo)等）和用來標(biāo)識(shí)多邊形表面空間取向的參數(shù)（如表面外法線方向）屬性表包括物體透明度、表面反射系數(shù)以及紋理特征參數(shù) 哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅105多面體模型（2/10）通常以層次結(jié)構(gòu)存儲(chǔ)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅106圖6-1繪制多面體所需的層次數(shù)據(jù)結(jié)構(gòu)信息表面表0表面表1…多邊形表0多邊形表1…V0,Nv0V1,Nv1V2,Nv2V3,Nv3…Np0Np1…表面表數(shù)組多邊形表面數(shù)組頂點(diǎn)數(shù)組多邊形法向量數(shù)組Nv3Nv0Nv1Nv2V3V0V1V2Np0(b)多邊形信息(a)層次數(shù)據(jù)結(jié)構(gòu)信息在Phong明暗處理算法中用到在背面剔除中用到多面體模型（3/10）缺點(diǎn)：相鄰多邊形的共享邊在上述數(shù)據(jù)結(jié)構(gòu)中沒有得到顯式表達(dá)，這使得同一條邊在繪制過程中可能被處理兩次。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅107多面體模型（4/10）基于邊的表示邊數(shù)組的每個(gè)元素包含4個(gè)指針，分別指向?qū)?yīng)邊的兩個(gè)頂點(diǎn)和它鄰接的兩個(gè)多邊形法向量哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅108圖6-2基于邊的繪制方法所需的數(shù)據(jù)結(jié)構(gòu)信息(a)多邊形信息邊數(shù)組頂點(diǎn)數(shù)組法向量數(shù)組V0,Nv0V1,Nv1V2,Nv2V3,Nv3…1,2,2,00,1,1,03,0,1,02,3,2,03,1,2,1…NULLNp1Np2…V0Nv3Nv0Nv1Nv2V3V1V2Np1Np2E1E0E2E3E4(b)基于邊的數(shù)據(jù)結(jié)構(gòu)信息多面體模型（8/10）多面體模型的優(yōu)點(diǎn)數(shù)據(jù)結(jié)構(gòu)相對(duì)簡單集合運(yùn)算、明暗圖的生成和顯示速度快缺點(diǎn)：雖然多面體可以任意精度逼近任意復(fù)雜的曲面物體，但它畢竟是曲面物體的一種近似逼近表示，存在誤差

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅109圖6-5曲面物體的多面體近似逼近表示過程曲面物體曲面逼近多邊形多邊形頂點(diǎn)曲面模型（1/10）曲面造型研究在計(jì)算機(jī)內(nèi)如何描述一張曲面，如何對(duì)曲面的形狀進(jìn)行控制與顯示可以由數(shù)學(xué)函數(shù)來定義包括二次曲面、超二次曲面、隱函數(shù)曲面等也可以由用戶輸入一系列離散的數(shù)據(jù)點(diǎn)來確定的參數(shù)曲面（第4章）如Coons曲面、B樣條曲面、NURBS曲面等哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅110哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅111四面體網(wǎng)格模型表示方法將包含實(shí)體的空間分割成四面體單元的集合特點(diǎn)可以以邊界面片為四面體的一個(gè)面，模型精度高能夠構(gòu)建復(fù)雜形體的網(wǎng)格模型在復(fù)雜對(duì)象的科學(xué)計(jì)算和工程分析中具有重要的應(yīng)用四面體網(wǎng)格模型數(shù)據(jù)結(jié)構(gòu)復(fù)雜，實(shí)現(xiàn)復(fù)雜空間域邊界一致的四面體剖分是近年來的研究熱點(diǎn)。

描述實(shí)體的信息GeometryTopology哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅112描述形體的幾何元素（頂點(diǎn)、邊、面）之間的連接關(guān)系，形成物體邊界表示的“骨架”描述形體的幾何元素性質(zhì)和度量關(guān)系，如位置、大小、方向、尺寸、形狀等信息猶如附著在“骨架”上的肌肉按照：體－面－環(huán)－邊－點(diǎn)的層次記錄信息

實(shí)體的定義（1/14）表示形體的基本幾何元素：頂點(diǎn)（Vertex）邊（Edge）面（Face）環(huán)（Loop）體（Body）哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅113零維幾何元素。在齊次坐標(biāo)系下，n維空間中的點(diǎn)用n+1維向量來表示。

一維幾何元素。對(duì)正則形體，邊是兩鄰面的交集，對(duì)非正則形體，邊有可能是多個(gè)鄰面的交集。邊的形狀可以是直線，也可以是曲線。二維幾何元素。可以無內(nèi)環(huán)，但必須有一個(gè)且只有一個(gè)外環(huán)。面有方向性，一般用其外法線方向作為該面的正向。面的形狀可以是平面，也可以是曲面

二維幾何元素。有序、有向邊（直線段或曲線段）組成的面的封閉邊界。外環(huán)邊通常按逆時(shí)針方向排序，內(nèi)環(huán)邊通常按順時(shí)針方向排序。三維幾何元素。由封閉表面圍成的空間，其邊界是有限面的并集。實(shí)體的定義（2/14）幾何造型就是通過對(duì)點(diǎn)、線、面、體等幾何元素經(jīng)平移、放縮、旋轉(zhuǎn)等幾何變換和并、交、差等集合運(yùn)算產(chǎn)生實(shí)際的或想象的物體模型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅114實(shí)體幾何造型（SolidModeling）研究三維幾何實(shí)體在計(jì)算機(jī)中的完整信息表示的模型和方法的技術(shù)實(shí)體的定義（3/14）如何保證實(shí)體的有效性呢？一個(gè)無效的實(shí)體當(dāng)然也不具備可加工性要保證實(shí)體的有效性和可加工性，形體必須是正則的那么什么是正則形體呢？哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅115實(shí)體的定義（3/14）二維流形（2-manifold）美國H.B.Voelcker和A.A.G.Requicha等為描述正則形體引入的概念指這樣一些面，其上任意一點(diǎn)都存在一個(gè)充分小的鄰域，該鄰域與平面上的封閉圓盤是同構(gòu)的，即在該鄰域與圓盤之間存在連續(xù)的一一映射正則形體？對(duì)于任一形體，它是三維歐氏空間R3中非空、有界的封閉子集，且其邊界是二維流形（即該形體是連通的）否則稱為非正則形體哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅116實(shí)體的定義（3/14）如何得到一個(gè)正則形體？將三維形體點(diǎn)集分成內(nèi)部點(diǎn)集和邊界點(diǎn)集兩部分先找出形體的內(nèi)部點(diǎn)集然后形成形體內(nèi)部點(diǎn)集的閉包哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅117圖6-9正則形體的形成過程示意圖(a)形體的開集(b)圖(a)開集的閉包(c)圖(a)形體的內(nèi)部點(diǎn)集(d)圖(c)內(nèi)部點(diǎn)集的閉包實(shí)體的定義（3/14）正則形體的性質(zhì)？（1）剛性不變形的實(shí)體，不能隨實(shí)體的位置和方向而發(fā)生形狀變化（2）維數(shù)的一致性三維空間中的實(shí)體的各部分均應(yīng)是三維的哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅118實(shí)體的定義（8/14）

幾何元素

正則形體

非正則形體

面

是形體表面的一部分不允許存在懸面

可以是形體表面的一部分，也可以是形體內(nèi)的一部分，也可以與形體相分離。

邊

只有兩個(gè)鄰面不允許存在懸邊

可以有多個(gè)鄰面、一個(gè)鄰面或沒有鄰面。

點(diǎn)

至少和三個(gè)面（或三條邊）鄰接不允許存在孤立點(diǎn)

可以與多個(gè)面（或邊）鄰接，也可以是聚集體、聚集面、聚集邊或孤立點(diǎn)。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅119實(shí)體的定義（4/14）正則形體的性質(zhì)？（3）有限性一個(gè)實(shí)體必須占據(jù)有限的三維空間（4）邊界的確定性根據(jù)實(shí)體的邊界能區(qū)分出實(shí)體的內(nèi)部和外部（5）封閉性經(jīng)過一系列剛體運(yùn)動(dòng)和任意次序的集合運(yùn)算之后，實(shí)體仍保持其同等的有效性哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅120實(shí)體的定義（4/14）正則形體的表面的性質(zhì)（1）連通性位于實(shí)體表面上的任意兩個(gè)點(diǎn)都可用實(shí)體表面上的一條路經(jīng)連接起來（2）有界性實(shí)體在有限空間內(nèi)是可定義的，即實(shí)體表面可將空間分成互不連通的兩個(gè)區(qū)域，其中一個(gè)區(qū)域是有界的。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅121實(shí)體的定義（4/14）正則形體的表面的性質(zhì)（3）非自交性實(shí)體的表面不能自交克萊茵瓶（KleinBottle）就是一個(gè)自交且不可定向的封閉曲面（4）可定向性表面的兩側(cè)可明確地定義出屬于實(shí)體的內(nèi)側(cè)還是外側(cè)莫比烏斯帶（MobiusBand）則是一個(gè)單邊不可定向的例子哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅122實(shí)體的定義（4/14）確定多面體表面是否具有可定向性的方法Mobius提出將實(shí)體的每個(gè)表面的邊環(huán)定義一個(gè)一致的方向（例如逆時(shí)針方向），這樣，每條邊會(huì)得到兩個(gè)指示方向的箭頭，當(dāng)且僅當(dāng)每條邊在每個(gè)方向都具有一個(gè)箭頭時(shí)，該實(shí)體表面就是可定向的。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅123歐拉公式與歐拉運(yùn)算歐拉特征設(shè)表面s由一個(gè)平面模型給出，且v,e,f分別表示其頂點(diǎn)、邊和小面的個(gè)數(shù)，那么v-e+f是一個(gè)常數(shù)，它與s劃分形成平面模型的方式無關(guān)。該常數(shù)稱為Euler特征。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅124v=8,e=13,f=7v-e+f=2歐拉公式歐拉公式與歐拉運(yùn)算歐拉物體滿足歐拉公式的物體歐拉運(yùn)算增加或者刪除面、邊和頂點(diǎn)以生成新的歐拉物體的過程哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅125歐拉公式只是檢查實(shí)體有效性的一個(gè)必要條件，而不是充分條件實(shí)體的正則集合運(yùn)算為什么在正則實(shí)體造型中，不使用普通的并、交、差等集合運(yùn)算，而要使用正則集合運(yùn)算呢？普通的集合運(yùn)算會(huì)產(chǎn)生懸邊、懸面等低于三維的形體哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅126正則集合運(yùn)算保證集合運(yùn)算的結(jié)果仍是一個(gè)正則形體實(shí)體的正則集合運(yùn)算如何實(shí)現(xiàn)正則集合運(yùn)算？方法1：先按照普通集合運(yùn)算再刪去不符合正則形體定義的部分：懸邊、懸面等方法2：定義正則集合算子，直接計(jì)算得到哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅127正則集合運(yùn)算任何物體都可用三維歐氏空間中點(diǎn)的集合來表示，但三維歐氏空間中任意點(diǎn)的集合卻不一定對(duì)應(yīng)于一個(gè)有效的物體設(shè)有三維空間中的一個(gè)點(diǎn)集A，那么稱為A的正則點(diǎn)集。如果A滿足那么稱A為正則點(diǎn)集。其中，r表示正則化算子，b、i分別表示取閉包運(yùn)算和取內(nèi)點(diǎn)運(yùn)算。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅128正則集合運(yùn)算正則集合運(yùn)算定義如下：正則并正則交正則差哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅129正則集合運(yùn)算以正則交集合運(yùn)算為例符合正則形體定義的實(shí)體，是三維空間中的點(diǎn)的正則點(diǎn)集，可以用它的邊界點(diǎn)集和內(nèi)部點(diǎn)集來表示，即寫成A為符合正則形體定義的實(shí)體bA代表A的邊界點(diǎn)集iA代表A的內(nèi)部點(diǎn)集哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅130正則集合運(yùn)算普通集合交運(yùn)算確定兩個(gè)相交物體的重疊邊界中的有效部分確定圖中粗實(shí)線所示邊界中的有效部分哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅131圖6-17正則交運(yùn)算的候選部分(a)

(b)(d)ABABAB12AB(c)正則集合運(yùn)算確定兩個(gè)相交物體的重疊邊界中的有效部分確定圖中粗實(shí)線所示邊界中的有效部分如果對(duì)物體的邊界采用一致的方向約定，那么，在兩個(gè)相交物體的重疊邊界上，如果某點(diǎn)處的切矢同向，則重疊邊界線段就是的有效邊界，否則，就是無效的邊界哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅132圖6-17正則交運(yùn)算的候選部分(a)

(b)(d)ABABAB12AB(c)正則集合運(yùn)算哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅133數(shù)據(jù)模型——邊界表示BoundaryRepresentation，也稱BR表示或BRep表示最成熟、無二義性當(dāng)前CAD/CAM系統(tǒng)中的最主要的表示方法物體的邊界與物體一一對(duì)應(yīng)實(shí)體的邊界是表面的并集表面的邊界是邊的并集哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅134數(shù)據(jù)模型——邊界表示多面體表示的實(shí)體的表面、棱邊、頂點(diǎn)之間的連接關(guān)系有9種類型至少需要選擇其中的2種才能表示一個(gè)實(shí)體的完整的拓?fù)湫畔⒐枮I工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅135圖6-20表面、棱邊、頂點(diǎn)之間的拓?fù)潢P(guān)系ffffff→{f}feeeef→{e}fvvvvf→{v}effe→{f}eeeeee→{e}evve→{v}vfffv→{f}veeev→{e}vvvvv→{v}采用較少的關(guān)系類型進(jìn)行組合來表示一個(gè)實(shí)體，所需的存儲(chǔ)空間小，但對(duì)數(shù)據(jù)的查找時(shí)間長反之，所需的存儲(chǔ)空間大，但對(duì)數(shù)據(jù)的查找時(shí)間短數(shù)據(jù)模型——邊界表示比較著名的有半邊數(shù)據(jù)結(jié)構(gòu)、翼邊數(shù)據(jù)結(jié)構(gòu)、輻射邊數(shù)據(jù)結(jié)構(gòu)等翼邊數(shù)據(jù)結(jié)構(gòu)最早是由美國斯坦福大學(xué)B.G.Baumgart等人于1972年提出以邊為核心來組織數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)用指針記錄每一邊的兩個(gè)鄰面（即左外環(huán)和右外環(huán)）、兩個(gè)頂點(diǎn)、兩側(cè)各自相鄰的兩個(gè)鄰邊（即左上邊、左下邊、右上邊和右下邊）用這一數(shù)據(jù)結(jié)構(gòu)表示多面體模型是完備的，但它不能表示帶有精確曲面邊界的實(shí)體哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅136圖6-21翼邊數(shù)據(jù)結(jié)構(gòu)左上邊右上邊左下邊右下邊左外環(huán)右外環(huán)eP2P1數(shù)據(jù)模型——邊界