計(jì)算機(jī)圖形學(xué)第3章-基本圖形生成算法

第3章基本圖形生成算法直線的生成1圓的生成2輸出圖元的屬性3自由曲線的生成4字符的生成5本章知識(shí)結(jié)構(gòu)圖重點(diǎn)掌握重點(diǎn)掌握重點(diǎn)掌握貝奇爾、B樣條曲線重點(diǎn)掌握?qǐng)D形生成：從圖形定義的物空間到進(jìn)行顯示處理的圖像空間的轉(zhuǎn)換。圖形顯示方式：單位為像素掌握：原理、算法、程序、特點(diǎn)3.1直線的生成直接生成法數(shù)值微分法Bresenham畫線算法中點(diǎn)畫線法雙步畫線算法直接由直線方程計(jì)算出(x，y)值，并生成直線。直線的方程可表示為

3.1.1

直接生成法

直接生成算法的缺點(diǎn)：涉及浮點(diǎn)數(shù)的乘除、加減、取整，效率低。一個(gè)方向的坐標(biāo)取單位步長的變化，然后計(jì)算另一方向坐標(biāo)相應(yīng)的變化值。已知直線的兩個(gè)端點(diǎn)(x0，y0)、(x1，y1)：①

當(dāng)|dx|＞|dy|(即|m|<1)若x0＜x1(即直線從左到右)：若x0＞x1(即直線從右到左)：②當(dāng)|dx|≤|dy|(即|m|≥1)若x0＜x1(即直線從左到右)：若x0＞x1(即直線從右到左)：3.1.2

數(shù)值微分法（DDA）原理3.1.3

中點(diǎn)畫線法PBPTQ2m1PQ1m2例題：利用中點(diǎn)畫線算法生成P（2，1）到Q（10，5）的直線所經(jīng)過的像素點(diǎn)。要求寫出每一步遞推過程的X,Y坐標(biāo)和判別式d的值，然后圖示直線結(jié)果。（2，1）3.1.4

Bresenham畫線法原理：當(dāng)進(jìn)行第i步，選定象素Pi-1，使它距離實(shí)際要畫的直線最近。在第i步要決定選擇Ti還是Si。如果s<t，則Si比較接近，應(yīng)選Si；否則選Ti。SiTitsPi-1具體步驟：判別式：di+1=di+2dy-2dx(yi-yi-1)如果di≥0，選Ti，yi=yi-1+1

則di+1=di+2（dy-dx）如果di<0，選Si，yi=yi-1

則di+1=di+2dy

其中d1=2dy-dx(加法、減法和移位（乘2））例題：利用Bresenham算法生成P（0，0）到Q（6，5）的直線所經(jīng)過的像素點(diǎn)。要求先列出計(jì)算式算出各點(diǎn)的坐標(biāo)值，然后在方格中標(biāo)出各點(diǎn)。（1，1）原理3.1.5

雙步畫線法模式1：當(dāng)右像素位于右下角時(shí)，中間像素位于底線模式4：當(dāng)右邊像素位右上角時(shí)，中間像素位于中線模式2和模式3：當(dāng)右像素位于中線時(shí)，中間像素可能位于底線上，也可能位于中線上，分別對(duì)應(yīng)于模式2和模式3，需進(jìn)一步判斷。當(dāng)0≤k≤1/2時(shí)，模式4不可能出現(xiàn)，當(dāng)1/2≤k≤1時(shí)，模式1不可能出現(xiàn)。中點(diǎn)畫圓算法3.2圓的生成圓心位于坐標(biāo)原點(diǎn)的圓弧算法，對(duì)于圓心為任意點(diǎn)的圓弧，可以先將其平移到原點(diǎn)，然后進(jìn)行掃描轉(zhuǎn)換，再平移到原來的位置。圓的八點(diǎn)對(duì)稱算法正負(fù)畫圓算法圓的畫法Bresenham畫圓算法3.2.1

圓的八點(diǎn)對(duì)稱

注意：當(dāng)x=y時(shí)，調(diào)用對(duì)稱函數(shù)會(huì)使對(duì)稱軸上四個(gè)點(diǎn)繪制兩次，該處應(yīng)單獨(dú)處理。

該算法是最有效的算法之一。不失一般性，假設(shè)圓心(xc，yc)

,圓上的點(diǎn)(x′，y′)，則：圓心為原點(diǎn)，半徑為R的位于第一象限1/8圓弧的畫法，即(0,R)～()。思想:每一步都選擇一個(gè)距離理想圓周最近的點(diǎn)P(，

)，使其誤差項(xiàng)最小。

3.2.2

Bresenham畫圓法PP1P2例題：繪制半徑為17的圓的第一個(gè)8分圓，并用對(duì)稱性生成第二個(gè)8分圓。要求先列出計(jì)算式算出各點(diǎn)的坐標(biāo)值，然后在方格中標(biāo)出各點(diǎn)。（0，0）3.2.3

中點(diǎn)畫圓法例題：繪制半徑為17的圓的第一個(gè)8分圓，并用對(duì)稱性生成第二個(gè)8分圓。要求先列出計(jì)算式算出各點(diǎn)的坐標(biāo)值，然后在方格中標(biāo)出各點(diǎn)。（0，0）

正負(fù)法是畫圓的一種有效方法。圓心為(xc，yc)，半徑為R的圓在第一象限內(nèi)的1/8圓弧，圓弧上點(diǎn)Pi(xi，yi)思想：圓弧關(guān)于x單調(diào)下降，通過找到圓弧附近的點(diǎn)來顯示圓弧。令函數(shù)

則圓的方程為F(x,y)=0當(dāng)點(diǎn)(x,y)在圓內(nèi)時(shí)，有F(x,y)<0當(dāng)點(diǎn)(x,y)在圓外時(shí)，有F(x,y)>03.2.4

正負(fù)法畫圓根據(jù)F(xi,yi)的函數(shù)值來確定下一點(diǎn)Pi+1(xi+1,yi+1)的走向。①如果F(xi,yi)≤0，下一位置xi+1=xi+1,yi+1=yi。

②如果F(xi,yi)>0，下一位置xi+1=xi,yi+1=yi―1：

正負(fù)法不僅可以用于畫圓，而且可以方便地用于畫其他曲線。3.3自由曲線的生成正弦函數(shù)曲線多項(xiàng)式函數(shù)曲線自由曲線指數(shù)函數(shù)曲線概率分布曲線及樣條函數(shù)曲線基本概念規(guī)則曲線：可用數(shù)學(xué)方程式表示出來的，如拋物線等。自由曲線：很難用一個(gè)數(shù)學(xué)方程式描述的，如高速公路等。可通過曲線擬合(插值、逼近)的方法來實(shí)現(xiàn)。

2.1.43.3.1

曲線的基本理論

控制點(diǎn)：用于控制曲線和曲面的位置和形狀的點(diǎn)，但相應(yīng)的曲線和曲面一般不經(jīng)過這些控制點(diǎn)。型值點(diǎn)：用于控制曲線和曲面的位置和形狀的點(diǎn)，而相應(yīng)的曲線和曲面要經(jīng)過這些型值點(diǎn)。插值點(diǎn)：在型值點(diǎn)間插入的點(diǎn)，以提高曲線和曲面的輸出精度?？刂泣c(diǎn)型值點(diǎn)曲線和曲面的表示顯式：y=f(x)z=f(x,y)隱式:f(x,y)=0f(x,y,z)=0xyF(X,Y,Z)=0G(X,Y,Z)=0Z=F(X,Y)Z=G(X,Y)參數(shù)：x=X(μ),y=Y(μ),z=Z(μ)μ∈[a,b]該點(diǎn)坐標(biāo)的矢量:P(μ)＝[X(μ)Y(μ)Z(μ)]三維空間曲面：Q(u，v)＝[X(u，v)Y(u，v)Z(u，v)]參數(shù)化表示的優(yōu)點(diǎn)：方便表示斜率為無窮大情況；封閉曲線的始點(diǎn)和終點(diǎn)；避免出現(xiàn)多值性；構(gòu)成幾何無關(guān)性函數(shù)。曲線的連續(xù)性多條曲線段光滑連接而成的曲線。零階連續(xù)一階連續(xù)二階連續(xù)Bézier曲線：通過一組多邊折線（控制多邊形）的各頂點(diǎn)唯一地定義的曲線。在多邊形的各頂點(diǎn)中，只有第一點(diǎn)和最后一點(diǎn)在曲線上，其余頂點(diǎn)用于控制曲線的形狀。第一條和最后一條折線表示曲線在起點(diǎn)和終點(diǎn)處的切線方向。曲線的形狀盡量接近控制多邊形的形狀。3.3.2

Bézier曲線Bézier例子一次Bézier曲線(n=1)Q(t)=[t1]()()0≤t≤1二次Bézier曲線(n=2)Q(t)=[t2t1]0≤t≤1-1110P0P11-21-220100P0P1P2三次Bézier曲線(n=3)Q(t)=[t3t2t1]0≤t≤1P0P1P2P3-13-313-630-33001000例題：已知Bézier曲線上4個(gè)點(diǎn)Q0(150,0),Q1(45,0),Q2(0,45),Q3(0,150)對(duì)應(yīng)的參數(shù)分別為0，1/3，2/3，1。反求Bézier曲線的控制多邊形頂點(diǎn)C1，C2C3C4。Bézier曲線的基本性質(zhì)：曲線經(jīng)過控制折線的起點(diǎn)和終點(diǎn)。起點(diǎn)和終點(diǎn)的切線方向與經(jīng)過起點(diǎn)和終點(diǎn)的折線方向一致。利用這兩個(gè)性質(zhì)，可以用分段曲線模擬復(fù)雜曲線，只要保證曲線的連接處相鄰兩個(gè)點(diǎn)在一條直線上即可獲得C1連續(xù)。（折線共線）

凸包性

Bézier曲線均落在由它的控制點(diǎn)形成的凸殼內(nèi)。 這個(gè)性質(zhì)的優(yōu)點(diǎn)是判斷是否與曲線有交點(diǎn)首先判斷是否在凸包內(nèi)。由此減少了大量的曲線求交運(yùn)算。幾何無關(guān)性: Bézier曲線的形狀僅與特征多邊形各控制點(diǎn)有關(guān)，而不依賴與坐標(biāo)系的選擇。變差縮減性

指平面內(nèi)任意直線與曲線的交點(diǎn)個(gè)數(shù)不多于該直線和其特征多邊形的交點(diǎn)個(gè)數(shù)。Bézier曲線沒有局部控制的能力 即當(dāng)修改某個(gè)控制點(diǎn)的位置后，曲線的形狀會(huì)產(chǎn)生較大的變化。Bézier曲線的階次隨控制點(diǎn)的增加而增加 由此導(dǎo)致計(jì)算量增加。3.3.3B樣條曲線

B樣條曲線的定義

其中Pi，i=0，1，…，n+m為控制頂點(diǎn)。

Fk,n(t)稱為B樣條分段混合基函數(shù)；n為曲線次數(shù)，段數(shù)=m+1,每段曲線與n+1個(gè)頂點(diǎn)有關(guān)。Qj,n(t)=

Pj+k

Fk,n(t)nk=0

二次B樣條曲線

P(t)=1/2[t2t1]0≤t≤11-21-220110Q0Q1Q2B樣條的性質(zhì)包含Bézier曲線的所有優(yōu)點(diǎn)，如幾何不變性，凸包性等；B樣條有局部修改的能力?；瘮?shù)（基本樣條）在局部參數(shù)區(qū)域分布（支撐區(qū)間），因此影響范圍有限。

例題：有點(diǎn)P0（4，3）；P1（6，5）；P2（10，6）；P3（12，4），用以上4點(diǎn)構(gòu)造2次B樣條曲線。2.1.7非均勻有理B樣條非均勻有理B樣條NURBS（NonUniformRationalB-Spline）；可用統(tǒng)一的參數(shù)形式表示自由曲線曲面和二次曲線曲面，便于工程數(shù)據(jù)庫的存取和應(yīng)用；通過控制點(diǎn)和權(quán)因子靈活改變形狀；比一般的曲線曲面定義方法更費(fèi)存儲(chǔ)空間和處理時(shí)間。NURBS數(shù)學(xué)模型特征多邊形頂點(diǎn)位置矢量：Pi在三維空間的曲線：

r(

)=

式中的hi可以看作是對(duì)第i項(xiàng)的權(quán)重，對(duì)曲線有幾何推拉作用。

hiPi

Ni,k(

)ni=0

hi

Ni,k(

)ni=0h=6h=1NURBS數(shù)學(xué)模型例子---權(quán)重h的推拉作用3.5輸出圖元的屬性線寬控制復(fù)制像素法移動(dòng)畫筆法區(qū)域填充法線型控制★

復(fù)制像素法

思想：線寬為n，在生成直線時(shí)選擇的像素點(diǎn)的水平或垂直方向顯示n個(gè)像素。

算法：將繪制單個(gè)像素的語句改寫成以該像素為中心繪制水平或垂直排列的多個(gè)像素。

線段：/K/<1時(shí)，垂直方向復(fù)制像素；/K/>1時(shí)，水平方向上復(fù)制像素。3.5.1線寬控制

曲線：當(dāng)前像素的斜率來決定水平或垂直繪制，寬度在法線方向上衡量。

特點(diǎn)：算法簡單，效率高，適合較小線寬；斜線與水平（垂直）線粗細(xì)不均勻；線段兩端真實(shí)感不夠好；繪制折線時(shí)，連接處產(chǎn)生缺口；寬度為偶數(shù)時(shí)，繪制的線條粗（細(xì)）一個(gè)像素、★

移動(dòng)畫筆法

思想：線寬為n，將寬度為n的畫筆的中心沿線段移動(dòng)，并將畫筆圖形內(nèi)的像素全部置成圖元顏色，畫筆的形狀有方形、圓形等不同形狀。

算法：將原來繪制單個(gè)像素的語句改寫成以該像素為中心繪制畫筆位圖的語句。

特點(diǎn)：簡單、易實(shí)現(xiàn)，但效率比較低；

用方形畫筆繪制的線段，兩個(gè)端點(diǎn)總是方的；寬度不均勻；存在重復(fù)寫像素的問題；

繪制圓弧時(shí)，與復(fù)制像素法正好相反，即當(dāng)斜率接近1時(shí)，寬度最大(等于k)?！飬^(qū)域填充法

根據(jù)線條的寬度，計(jì)算出線條的內(nèi)外輪廓，然后調(diào)用填充圖元的生成函數(shù)將其填充，產(chǎn)生具有一定線寬的線條。常用線型3.5.2線型控制算法：每一種線型可以用一個(gè)布爾值的數(shù)組來存放。例：18位的整數(shù)存放18個(gè)布爾值，用這樣的整數(shù)存放線型定義時(shí)，線型必須以18個(gè)像素為周期進(jìn)行重復(fù)。111100111100111100程序：將寫像素語句

drawpixel(x,y,color);改為

if（位串[i%18]）drawpixel(x,y,color);缺點(diǎn)：采用固定劃線長度的實(shí)現(xiàn)方法會(huì)在不同直線方向上產(chǎn)生不等長的劃線段。3.6

字符的生成字符指計(jì)算機(jī)在文本方式下能夠在屏幕上顯示的數(shù)字、字母、音標(biāo)、標(biāo)點(diǎn)、數(shù)學(xué)符號(hào)、漢字等。

常用字符：“美國信息交換用標(biāo)準(zhǔn)代碼集”簡稱ASCII碼；漢字字符；其它符號(hào)。

字庫：點(diǎn)陣字庫（位圖）和矢量字庫（輪廓線）點(diǎn)陣字庫：每個(gè)字符用二值點(diǎn)陣信息表示；矢量字庫：則用直線和曲線（如三次B樣條曲線/Bezier曲線）來描述字符的輪廓形狀。

3.6.1

字符形狀表示

★

位圖表示每個(gè)字符是一個(gè)位圖表，通過一個(gè)稱為字符掩膜的矩陣來表示，矩陣的每個(gè)元素都是一位二進(jìn)制數(shù)，如果該位為1表示字符的筆畫經(jīng)