最新計算機圖形學第二章a課件

上海師范大學計算機圖形學第二章a上海師范大學計算機圖形學第二章a1intgetx(void);intgety(void);2.直線voidline(intx0,inty0,intx1,inty1);當前坐標（x,y）voidlineto(intx,inty);voidlinerel(intdeltax,intdeltay);當前坐標(x+deltax,y+deltay）例題：arc(40,40,0,120,30);intgetx(void);2最新計算機圖形學第二章a課件3最新計算機圖形學第二章a課件4最新計算機圖形學第二章a課件5最新計算機圖形學第二章a課件6最新計算機圖形學第二章a課件7最新計算機圖形學第二章a課件88DRAKGRAY9LIGHTBLUE10LIGHTGREEN11LIGHTCYAN12LIGHTRED13LIGHTMAGENTA14YELLOW15WHITE

8DRAKGRAY96.voidsetlinestyle(intlinestyle,unsignedupattern,intthickness);6.voidsetlinestyle(intline10Linestyle取值：

SOLID-LINE0實線DOTTED-LINE1點線CENTER-LINE2中心線DASHED-LINE3虛線USERBIT-LINE4用戶定義的線

upattern僅在userbit-line時起作用Linestyle取值：11thickness線寬

NORM-WIDTH1一個象素寬THICK-WIDTH3三個象素寬thickness線寬12例題：

setlinestyle(DASHED-LINE,0,THICK-WIDTH);或setlinestyle(3,0,3);line(300,50,300,200);例題：13上機作業(yè)2:畫出如下圖形上機作業(yè)2:畫出如下圖形14第二章基本圖形的生成和計算 如何在指定的輸出設備上描述構造基本二維幾何圖形（點、直線、圓、橢圓、多邊形、字符串及其相關屬性等）第二章基本圖形的生成和計算 如何在指定的輸出設152.1直線的生成算法圖形的掃描轉換：在光柵顯示器等數字設備上確定一個最佳逼近于圖形的象素集的過程。用一系列的象素點來逼近直線2.1直線的生成算法圖形的掃描轉換：在光柵162.1直線的生成算法2.1.1直線DDA算法(DigitalDifferentialAnalyser)設直線起點(x1,y1)，終點(x2,y2)xy(x1,y1)(x2,y2)2.1直線的生成算法2.1.1直線DDA算17則斜率mm=(y2-y1)/(x2-x1)=dy/dxxy(x1,y1)(x2,y2)dydx則斜率mxy(x1,y1)(x2,y2)dydx18xy(x1,y1)(x2,y2)dydxdy/dx=Dy/Dxxi+1=xi+Dxyi+1=yi+DyDy=m*Dx(xi,yi)(xi+1,yi+1)DxDyxy(x1,y1)(x2,y2)dydxdy/dx=Dy/D19xy1b1a4a4b3b3a2a2bxi+1=xi+1yi+1=yi+mxi+1=xi-1yi+1=yi-m(x1,y1)(x2,y2)Oxi+1=xi+1/myi+1=yi+1xy1b1a4a4b3b3a2a2bxi+1=xi+1xi20象限DxDy象限DxDy1a1m4a1-m1b1/m14b1/m-12a-1m2b-1/m13a-1-m3b-1/m-1結論：1.當|m|<1時，|Dx|=1,|Dy|=m否則|Dx|=1/m,|Dy|=1象限DxDy21結論：2.Dx,Dy的符號與dx,dy的符號相同。結論：22缺點：1.浮點增量的連續(xù)迭加，誤差積累使長線段計算的象素位置偏離實際線段2.浮點運算十分耗時缺點：231965年由Bresenham提出設直線起點(x1,y1)，終點(x2,y2)y=mx+bb=y1-m*x1m=(y2-y1)/(x2-x1)=dy/dx2.1.2直線Bresenham算法1965年由Bresenham提出2.1.2直線Bres241312111010111213（11，11）（12，11）或（12，12）當直線方向限于1a象限(x1,y1)(x2,y2)1312111010111213（11，11）（12，11）25當直線方向限于1a象限，則xi+1=xi+1yi+1<yi+1<yi當直線方向限于1a象限，則261312111010111213（xi，yi）(x1,y1)(x2,y2)(xi+1，yi)(xi+1,yi+1)d1=y-yid2=yi+1-y1312111010111213（xi，yi）(x1,y1)27Bresenham算法采取對整型參量的符號進行檢測，整型參量的值正比于兩象素與實際線段之間的偏移yi+1的選擇由d1，d2的大小決定

Bresenham算法采取對整型參量的符號進行檢測，整型參量28（xi，yi）(xi+1，yi)(xi+1,yi+1)d1=y-yid2=yi+1-y如d1>d2,則yi+1=yi+1,否則yi+1=yid1=y-yi

d2=yi+1-y（xi，yi）(xi+1，yi)(xi+1,yi+1)d1=29d1-d2=2y-2yi-1y=m(xi+1)+bm=dy/dxd1=y-yi

d2=yi+1-y∴d1-d2=2dy/dx(xi+1)+2b-2yi-1兩邊*dx,令Pi=(d1-d2)dx則Pi=2dy(xi+1)+2b*dx-2yi*dx-dx=2xidy-2yidx+2dy+(2b-1)dxd1-d2=2y-2yi-1d1=y-yi30由于dx>0，則Pi可用來判斷符號Pi+1=2xi+1dy-2yi+1dx+2dy+(2b-1)dx=2(xi+1)dy-2yi+1dx+2dy+(2b-1)dx=Pi+2dy-2yi+1dx+2yidx=Pi+2dy-2(yi+1-yi)dxPi=2xidy-2yidx+2dy+(2b-1)dx由于dx>0，則Pi可用來判斷符號Pi=2xidy-231P1=2x1dy-2y1dx+2dy+(2b-1)dx=2x1dy-2y1dx+2dy+[2(y1-(dy/dx)x1)-1]dx=2x1dy-2y1dx+2dy+2y1dx-2x1dy-dx=2dy-dxPi=2xidy-2yidx+2dy+(2b-1)dxb=y1-m*x1P1=2x1dy-2y1dx+2dy+(2b-1)dxPi=321.畫點(x1,y1)dx=x2-x1dy=y2-y1P1=2dy-dxi=12.xi+1=xi+1當Pi>0,則yi+1=yi+1,否則yi+1=yi3.畫點(xi+1,yi+1)

畫線步驟：P1=2dy-dx1.畫點(x1,y1)畫線步驟：P1=2dy-dx334.求Pi+1,當Pi>0則Pi+1=Pi+2dy-2dx否則Pi+1=Pi+2dy5.i=i+1如i<dx+1則轉2否則結束4.求Pi+1,當Pi>0則34

優(yōu)點1.不做除法2.只用整數3.只有整數加減和乘2運算優(yōu)點35例：起點(20,10)終點(30,18)斜率0.8dx=10,dy=8P1=2dy-dx=2*8-10=6iPi(xi+1,yi+1)123例：起點(20,10)終點(30,18)斜36iPi(xi+1,yi+1)45678910

iPi37例：起點(20,10)終點(30,18)斜率0.8dx=10,dy=8P1=2dy-dx=2*8-10=6iPi(xi+1,yi+1)16(21,11)22(22,12)3-2(23,12)例：起點(20,10)終點(30,18)斜38iPi(xi+1,yi+1)414(24,13)510(25,14)66(26,15)72(27,16)8-2(28,16)914(29,17)1010(30,18)

iPi39Bresenham畫法對任意斜率的線段具有通用性。當m>0,且m>1，則交換x，y之間規(guī)則Bresenham畫法對任意斜率的線段具有通用性。402.2圓的生成算法2.2.1基礎知識設圓心坐標(xc,yc),半徑r1.直角坐標法(x-xc)2+(y-yc)2=r2

∴y=yc±(r2-(x-xc)2)1/2

x-xc從-r~r作加1遞增，可求出y坐標但圓周上的點不均勻即象素位置間的間距不一致。2.2圓的生成算法2.2.1基礎知識411212422.2圓的生成算法2.極坐標法x=xc+rcosθy=yc+rsinθrθθ∈[0,∏/4],利用對稱法則2.2圓的生成算法2.極坐標法rθθ∈[43(x,y)yy=-xy=x(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)(x,y)yy=-xy=x(y,x)(-y,x)(-x,y)442.2圓的生成算法2.2.2圓的Bresenham算法Bresenham圓算法通過比較象素與圓的距離的平方而避免了平方根運算。設圓心坐標(0,0)半徑為r起點(0,r)順時針方向1/8圓周xi+1=xi+1yi+1=yi或yi+1=yi-12.2圓的生成算法2.2.2圓的Bre45xyxixi+1yiyyi-1d21/2d11/2xyxixi+1yiyyi-1d21/2d11/2462.2圓的生成算法y2=r2-(xi+1)2d1=yi2-y2=yi2-r2+(xi+1)2d2=y2-(yi-1)2=r2-(xi+1)2-(yi-1)2令Pi=d1-d2=2(xi+1)2+yi2+(yi-1)2-2r2Pi+1=Pi+4xi+6+2(yi+12+1-yi2)-2(yi+12+1-yi2)當P<0，則yi+1=yi,否則yi+1=yi-12.2圓的生成算法y2=r2-(xi+1472.2圓的生成算法Pi+1=2(xi+2)2+yi+12+(yi+1-1)2-2r2=2(xi+1)2+4xi+6+yi+12+(yi+1-1)2-2r2

=Pi+4xi+6-yi2-(yi-1)2+yi+12+(yi+1-1)2

=Pi+4xi+6+2(yi+12-yi2)-2(yi+1-yi)當P1(x1=0,y1=r)P1=2+r2+(r-1)2-2r2

=3-2r2.2圓的生成算法Pi+1=2(xi+2482.3區(qū)域填充算法2.3.1基本知識1.區(qū)域填充定義：給出一個區(qū)域的邊界，要求對邊界范圍內的所有象素單元賦予指定的顏色代碼。最常用的是多邊形填色。2.3區(qū)域填充算法2.3.1基本知識49

2.3區(qū)域填充算法2.數學方法：掃描交點的奇偶數判斷法1)將多邊形畫在平面上2)用一根水平掃描線從左到右通過多邊形,從而與多邊形的邊界相交，掃描線與邊界相交奇數次后進入多邊形，偶次數后走出多邊形。2.3區(qū)域填充算法2.數學方法：掃描50最新計算機圖形學第二章a課件51ABC錯判錯判錯判ABC錯判錯判錯判521.掃描線填色算法：按掃描線順序計算掃描線與多邊形的相交區(qū)間，再用要求的顏色或圖案顯示這些區(qū)間的象素，需提供多邊形各頂點的坐標填色算法2.種子填色算法：要求給出邊界顏色特征區(qū)域內的一個點的坐標。1.掃描線填色算法：按掃描線順序計算掃描線與多邊形的相交區(qū)間532.3.2掃描線填色算法1.用水平掃描線由上往下掃描多邊形2.每根掃描線與多邊形各邊產生一系列交點，采用遞歸算法3.將交點按x坐標進入分類，將分類后的交點成對取出，作為兩個端點，以所需要填的色彩畫水平直線。2.3.2掃描線填色算法1.用水平掃描線由上往下掃54掃描線與邊的求交點方法采用遞歸算法：以(x1,y1),(x2,y2)為端點的邊與第i+1條掃描線的交點:yi+1=yi-1，xi+1=xi-(x2-x1)/(y2-y1)即xi+1=xi-1/m，yi(x2,y2)Pi(xi,yi)(x1,y1)Pi+1(xi+1,yi+1)yi+1掃描線與邊的求交點方法采用遞歸算法：以(x1,y1),(x255左右頂點處理：（以1、2、3次序畫多邊形外框）左頂點2：y1<y2<y3123123右頂點2：y1>y2>y3左右頂點處理：123123右頂點2：y1>y2>y356一個頂點同屬于多邊形兩條邊的端點，如果所交的頂點是左頂點或右頂點，填色因掃描交點的奇偶計數出錯而出現(xiàn)錯誤。解決方法:刪去左右頂點的入邊的終點，(即1-2邊)123123一個頂點同屬于多邊形兩條邊的端點，如果所交的頂點是左頂點或右57對于左頂點，(x1,y1),(x2,y2)改為(x1,y1),(x2-1/m,y2-1)對于右頂點，(x1,y1),(x2,y2)改為(x1,y1),(x2+1/m,y2+1)刪去水平邊123123對于左頂點，(x1,y1),(x2,y2)改為12312358水平邊處理刪去水平邊水平邊處理刪去水平邊592.3.3種子填色算法已知多邊形邊界位置及顏色以及多邊形內的一點(x,y)位置。

(x,y)2.3.3種子填色算法已知多邊形邊界位置及顏色以及多60方法：1.從(x,y)開始檢測相鄰位置以確定它們是否是邊界顏色，若不是，則用填充顏色涂色，并檢測其相鄰位置。2.直至檢測完所有象素。

方法：61常用的：四鄰法和八鄰法常用的：四鄰法和八鄰法62四鄰法不能通過狹窄區(qū)域四鄰法不能通過狹窄區(qū)域63種子填色算法voidseed_filling(x,y,fill_color,boundary_color)intx,y,fill_color,boundary_color;{intc;c=inquire_color(x,y);if((c<>boundary_color)&&(c<>fill_color)){setpixel(x,y,fill_color);seed_filling(x,y+1,fill_color,boundary_color);seed_filling(x,y-1,fill_color,boundary_color);seed_filling(x-1,y,fill_color,boundary_color);seed_filling(x+1,y,fill_color,boundary_color);}}種子填色算法voidseed_filling(x,y,fi64種子填色算法種子填色算法65種子填色算法（上，下，左，右）種子填色算法（上，下，左，右）66最新計算機圖形學第二章a課件67上海師范大學計算機圖形學第二章a上海師范大學計算機圖形學第二章a68intgetx(void);intgety(void);2.直線voidline(intx0,inty0,intx1,inty1);當前坐標（x,y）voidlineto(intx,inty);voidlinerel(intdeltax,intdeltay);當前坐標(x+deltax,y+deltay）例題：arc(40,40,0,120,30);intgetx(void);69最新計算機圖形學第二章a課件70最新計算機圖形學第二章a課件71最新計算機圖形學第二章a課件72最新計算機圖形學第二章a課件73最新計算機圖形學第二章a課件74最新計算機圖形學第二章a課件758DRAKGRAY9LIGHTBLUE10LIGHTGREEN11LIGHTCYAN12LIGHTRED13LIGHTMAGENTA14YELLOW15WHITE

8DRAKGRAY766.voidsetlinestyle(intlinestyle,unsignedupattern,intthickness);6.voidsetlinestyle(intline77Linestyle取值：

SOLID-LINE0實線DOTTED-LINE1點線CENTER-LINE2中心線DASHED-LINE3虛線USERBIT-LINE4用戶定義的線

upattern僅在userbit-line時起作用Linestyle取值：78thickness線寬

NORM-WIDTH1一個象素寬THICK-WIDTH3三個象素寬thickness線寬79例題：

setlinestyle(DASHED-LINE,0,THICK-WIDTH);或setlinestyle(3,0,3);line(300,50,300,200);例題：80上機作業(yè)2:畫出如下圖形上機作業(yè)2:畫出如下圖形81第二章基本圖形的生成和計算 如何在指定的輸出設備上描述構造基本二維幾何圖形（點、直線、圓、橢圓、多邊形、字符串及其相關屬性等）第二章基本圖形的生成和計算 如何在指定的輸出設822.1直線的生成算法圖形的掃描轉換：在光柵顯示器等數字設備上確定一個最佳逼近于圖形的象素集的過程。用一系列的象素點來逼近直線2.1直線的生成算法圖形的掃描轉換：在光柵832.1直線的生成算法2.1.1直線DDA算法(DigitalDifferentialAnalyser)設直線起點(x1,y1)，終點(x2,y2)xy(x1,y1)(x2,y2)2.1直線的生成算法2.1.1直線DDA算84則斜率mm=(y2-y1)/(x2-x1)=dy/dxxy(x1,y1)(x2,y2)dydx則斜率mxy(x1,y1)(x2,y2)dydx85xy(x1,y1)(x2,y2)dydxdy/dx=Dy/Dxxi+1=xi+Dxyi+1=yi+DyDy=m*Dx(xi,yi)(xi+1,yi+1)DxDyxy(x1,y1)(x2,y2)dydxdy/dx=Dy/D86xy1b1a4a4b3b3a2a2bxi+1=xi+1yi+1=yi+mxi+1=xi-1yi+1=yi-m(x1,y1)(x2,y2)Oxi+1=xi+1/myi+1=yi+1xy1b1a4a4b3b3a2a2bxi+1=xi+1xi87象限DxDy象限DxDy1a1m4a1-m1b1/m14b1/m-12a-1m2b-1/m13a-1-m3b-1/m-1結論：1.當|m|<1時，|Dx|=1,|Dy|=m否則|Dx|=1/m,|Dy|=1象限DxDy88結論：2.Dx,Dy的符號與dx,dy的符號相同。結論：89缺點：1.浮點增量的連續(xù)迭加，誤差積累使長線段計算的象素位置偏離實際線段2.浮點運算十分耗時缺點：901965年由Bresenham提出設直線起點(x1,y1)，終點(x2,y2)y=mx+bb=y1-m*x1m=(y2-y1)/(x2-x1)=dy/dx2.1.2直線Bresenham算法1965年由Bresenham提出2.1.2直線Bres911312111010111213（11，11）（12，11）或（12，12）當直線方向限于1a象限(x1,y1)(x2,y2)1312111010111213（11，11）（12，11）92當直線方向限于1a象限，則xi+1=xi+1yi+1<yi+1<yi當直線方向限于1a象限，則931312111010111213（xi，yi）(x1,y1)(x2,y2)(xi+1，yi)(xi+1,yi+1)d1=y-yid2=yi+1-y1312111010111213（xi，yi）(x1,y1)94Bresenham算法采取對整型參量的符號進行檢測，整型參量的值正比于兩象素與實際線段之間的偏移yi+1的選擇由d1，d2的大小決定

Bresenham算法采取對整型參量的符號進行檢測，整型參量95（xi，yi）(xi+1，yi)(xi+1,yi+1)d1=y-yid2=yi+1-y如d1>d2,則yi+1=yi+1,否則yi+1=yid1=y-yi

d2=yi+1-y（xi，yi）(xi+1，yi)(xi+1,yi+1)d1=96d1-d2=2y-2yi-1y=m(xi+1)+bm=dy/dxd1=y-yi

d2=yi+1-y∴d1-d2=2dy/dx(xi+1)+2b-2yi-1兩邊*dx,令Pi=(d1-d2)dx則Pi=2dy(xi+1)+2b*dx-2yi*dx-dx=2xidy-2yidx+2dy+(2b-1)dxd1-d2=2y-2yi-1d1=y-yi97由于dx>0，則Pi可用來判斷符號Pi+1=2xi+1dy-2yi+1dx+2dy+(2b-1)dx=2(xi+1)dy-2yi+1dx+2dy+(2b-1)dx=Pi+2dy-2yi+1dx+2yidx=Pi+2dy-2(yi+1-yi)dxPi=2xidy-2yidx+2dy+(2b-1)dx由于dx>0，則Pi可用來判斷符號Pi=2xidy-298P1=2x1dy-2y1dx+2dy+(2b-1)dx=2x1dy-2y1dx+2dy+[2(y1-(dy/dx)x1)-1]dx=2x1dy-2y1dx+2dy+2y1dx-2x1dy-dx=2dy-dxPi=2xidy-2yidx+2dy+(2b-1)dxb=y1-m*x1P1=2x1dy-2y1dx+2dy+(2b-1)dxPi=991.畫點(x1,y1)dx=x2-x1dy=y2-y1P1=2dy-dxi=12.xi+1=xi+1當Pi>0,則yi+1=yi+1,否則yi+1=yi3.畫點(xi+1,yi+1)

畫線步驟：P1=2dy-dx1.畫點(x1,y1)畫線步驟：P1=2dy-dx1004.求Pi+1,當Pi>0則Pi+1=Pi+2dy-2dx否則Pi+1=Pi+2dy5.i=i+1如i<dx+1則轉2否則結束4.求Pi+1,當Pi>0則101

優(yōu)點1.不做除法2.只用整數3.只有整數加減和乘2運算優(yōu)點102例：起點(20,10)終點(30,18)斜率0.8dx=10,dy=8P1=2dy-dx=2*8-10=6iPi(xi+1,yi+1)123例：起點(20,10)終點(30,18)斜103iPi(xi+1,yi+1)45678910

iPi104例：起點(20,10)終點(30,18)斜率0.8dx=10,dy=8P1=2dy-dx=2*8-10=6iPi(xi+1,yi+1)16(21,11)22(22,12)3-2(23,12)例：起點(20,10)終點(30,18)斜105iPi(xi+1,yi+1)414(24,13)510(25,14)66(26,15)72(27,16)8-2(28,16)914(29,17)1010(30,18)

iPi106Bresenham畫法對任意斜率的線段具有通用性。當m>0,且m>1，則交換x，y之間規(guī)則Bresenham畫法對任意斜率的線段具有通用性。1072.2圓的生成算法2.2.1基礎知識設圓心坐標(xc,yc),半徑r1.直角坐標法(x-xc)2+(y-yc)2=r2

∴y=yc±(r2-(x-xc)2)1/2

x-xc從-r~r作加1遞增，可求出y坐標但圓周上的點不均勻即象素位置間的間距不一致。2.2圓的生成算法2.2.1基礎知識10812121092.2圓的生成算法2.極坐標法x=xc+rcosθy=yc+rsinθrθθ∈[0,∏/4],利用對稱法則2.2圓的生成算法2.極坐標法rθθ∈[110(x,y)yy=-xy=x(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)(x,y)yy=-xy=x(y,x)(-y,x)(-x,y)1112.2圓的生成算法2.2.2圓的Bresenham算法Bresenham圓算法通過比較象素與圓的距離的平方而避免了平方根運算。設圓心坐標(0,0)半徑為r起點(0,r)順時針方向1/8圓周xi+1=xi+1yi+1=yi或yi+1=yi-12.2圓的生成算法2.2.2圓的Bre112xyxixi+1yiyyi-1d21/2d11/2xyxixi+1yiyyi-1d21/2d11/21132.2圓的生成算法y2=r2-(xi+1)2d1=yi2-y2=yi2-r2+(xi+1)2d2=y2-(yi-1)2=r2-(xi+1)2-(yi-1)2令Pi=d1-d2=2(xi+1)2+yi2+(yi-1)2-2r2Pi+1=Pi+4xi+6+2(yi+12+1-yi2)-2(yi+12+1-yi2)當P<0，則yi+1=yi,否則yi+1=yi-12.2圓的生成算法y2=r2-(xi+11142.2圓的生成算法Pi+1=2(xi+2)2+yi+12+(yi+1-1)2-2r2=2(xi+1)2+4xi+6+yi+12+(yi+1-1)2-2r2

=Pi+4xi+6-yi2-(yi-1)2+yi+12+(yi+1-1)2

=Pi+4xi+6+2(yi+12-yi2)-2(yi+1-yi)當P1(x1=0,y1=r)P1=2+r2+(r-1)2-2r2

=3-2r2.2圓的生成算法Pi+1=2(xi+21152.3區(qū)域填充算法2.3.1基本知識1.區(qū)域填充定義：給出一個區(qū)域的邊界，要求對邊界范圍內的所有象素單元賦予指定的顏色代碼。最常用的是多邊形填色。2.3區(qū)域填充算法2.3.1基本知識116

2.3區(qū)域填充算法2.數學方法：掃描交點的奇偶數判斷法1)將多邊形畫在平面上2)用一根水平掃描線從左到右通過多邊形,從而與多邊形的邊界相交，掃描線與邊界相交奇數次后進入多邊形，偶