2025/7/181計算機圖形學(xué)2025/7/182第二章圖形基元的顯示

掃描轉(zhuǎn)換將圖形描述轉(zhuǎn)換成用象素矩陣表示的過程圖形基元（輸出圖形元素）圖形系統(tǒng)能產(chǎn)生的最基本圖形線段、圓、橢圓、多邊形

2025/7/183第一節(jié)直線掃描轉(zhuǎn)換算法第二節(jié)圓的掃描轉(zhuǎn)換算法第三節(jié)橢圓掃描轉(zhuǎn)換算法第四節(jié)區(qū)域填充2025/7/184第一節(jié)直線掃描轉(zhuǎn)換算法DDA直線掃描轉(zhuǎn)換算法

中點畫線法

Bresenham畫線算法

2025/7/1851.DDA線段掃描轉(zhuǎn)換算法設(shè)待畫線段兩端點的坐標(biāo)值(x1,y1)和(x2,y2)，假定x1<x2 y=mx+b m=(y2-y1)/(x2-x1) b=(x2y1-x1y2)/(x2-x1)

|m|≤1,對x每增1取允許的各整數(shù)值:2025/7/186(0,0)(0,0)(0,2)(2,0)(5,7)(7,5)2025/7/187voidDDALine(intx1,inty1,intx2,inty2){ doubledx,dy,e,x,y; dx=x2-x1; dy=y2-y1; e=(fabs(dx)>fabs(dy))?fabs(dx):fabs(dy); dx/=e; dy/=e;

x=x1; y=y1; for(inti=0;i<=e;i++) { SetPixel((int)(x+0.5),(int)(y+0.5)); x+=dx; y+=dy; }}2025/7/1882.中點畫線法假定直線斜率在0、1之間，x=xi時已選(xi,yi)像素，

確定x=xi+1與直線最近的像素P1(xi+1,yi)、P2(xi+1,yi+1)

M表示P1與P2的中點，M=(xi+1,yi+0.5)。Q是直線與垂直線x=xi+1的交點若M在Q的下方，則P2離直線近，應(yīng)取為下一個像素；否則應(yīng)取P12025/7/189起點和終點分別為(x0,y0)和(x1,y1)。其所在直線F(x,y)=ax+by+c其中，a=y0-y1，b=x1-x0，c=x0y1-x1y0

。直線上的點，F(xiàn)(x,y)=0；直線上方的點，F(xiàn)(x,y)>0；直線下方的點，F(xiàn)(x,y)<0。2025/7/1810Q在M的上方還是下方，只要把M代入F(x，y)，并判斷它的符號。

d=F(M)=F(xi+1，yi+0.5)=a(xi+1)+b(yi+0.5)+c當(dāng)d<0

時，M在直線下方(即在Q的下方)，應(yīng)取右上方的P2

。當(dāng)d>0時，則取正右方的P1。當(dāng)d=0時，二者一樣合適，取P1。d是xi,yi的線性函數(shù)，因此可采用增量計算，提高運算效率。2025/7/1811對每一個像素計算判別式d，根據(jù)它的符號確定下一像素。若d≥0

時，取正右方像素P1，判斷再下一個像素應(yīng)取哪個，應(yīng)計算d1=F(xi+2，yi+0.5)=a(xi+2)+b(yi+0.5)+c=d+a故d的增量為a。2025/7/1812若d<0

時，則取右上方像素P2。要判斷再下一個像素，則要計算d2=F(xi+2，yi+1.5)=a(xi+2)+b(yi+1.5)+c=d+a+b故在第二種情況，d的增量為a+b2025/7/1813再看d的初始值。顯然，第一個像素應(yīng)取左端點(x0，y0)，相應(yīng)的判別式值為d0=F(x0+1，y0+0.5)=a(x0+1)+b(y0+0.5)+c=ax0+by0+c+a+0.5b=F(x0，y0)+a+0.5b但由于(x0，y0)在直線上，故F(x0，y0)=0。因此，d的初始值為d0=a+0.5b

為避免小數(shù)運算，考慮用2d來代替d的計算

2025/7/1814voidMidpointLine(intx0,inty0,intx1,inty1){ inta,b,delta1,delta2,d,x,y; a=y0-y1; b=x1-x0; d=2*a+b; delta1=2*a; delta2=2*(a+b);

x=x0; y=y0; SetPixel(x,y); while(x<x1) { if(d<0){ x++; y++;

d+=delta2; } else{ x++; d+=delta1; } SetPixel(x,y); }/*while*/}/*MidpointLine*/2025/7/1815

例:(0，0)、(5，2)a=y0-y1=-2，

b=x1-x0=5,d0=2*

a+b=1,delta1=2a=-4,delta2=2(a+b)=

6if(d<0){ x++; y++;

d+=delta2;}else{ x++; d+=delta1;}xydΔd001-410-36213-431-16425-45212025/7/1816斜率m在0到1之間，并且設(shè)在第i步已經(jīng)確定第i個像素點是，現(xiàn)在看第i+1步如何確定第i+1個像素點的位置。3.Bresenham畫線算法2025/7/1817下一個像素點取

下一個像素點取取兩像素點中的任意一個2025/7/18182025/7/18192025/7/1820確定P1,令i=1，可計算求出：

2025/7/1821voidBresenhamLine(intx1,inty1,intx2,inty2){ intx,y,dx,dy,p; x=x1; y=y1; dx=x2-x1; dy=y2-y1; p=2*dy-dx; for(;x<=x2;x++){ SetPixel(x,y); if(p>=0){

y++;

p+=2*(dy-dx); } else{

p+=2*dy; } }}第二節(jié)圓的掃描轉(zhuǎn)換算法x2+y2=R2

x=Rcos(θ)y=Rsin(θ)(a)(b)1012￡￡=xxy2/0sincospqqq￡￡==yx(a)(b)1012￡￡-=xxy2/0sincospqqq￡￡==yx2025/7/18232025/7/1824

討論如何從點(0，R)至(，)的1／8圓周 若x坐標(biāo)為(xi,yi)，下一個像素只能是(xi+1,yi)的P1點或(xi+1,yi-1)的P2點中點畫圓法2025/7/1825構(gòu)造函數(shù)：F(x,y)=x2+y2-R2圓上的點，F(xiàn)(x,y)=0圓外的點，F(xiàn)(x,y)>0圓內(nèi)的點，F(xiàn)(x,y)<0P1和P2的中點為M=(xi+1,yi-0.5)F(M)<0時，M在圓內(nèi)，取P1F(M)>0時，M在圓外，取P2F(M)=0時，P1或P2隨取一個即可，取P2

2025/7/1826構(gòu)造判別式若d<0，取P1作為下一個像素，而且再下一個像素的判別式為2025/7/1827若d≥0，應(yīng)取P2作為下一個像素，而且再下一個像素的判別式第一個像素是(0,R)，判別式d的初始值為 d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R。2025/7/1828voidMidpointCircle(intR){ intx,y; doubled; x=0;y=R;d=1.25-R; SetPixel(x,y); while(x<y){ if(d<0){ d+=2*x+3; x++;

} else{ d+=2*(x-y)+5; x++; y--; } SetPixel(x,y); }}2025/7/1829算法三：中點畫圓法改進一在上述算法中，使用了浮點數(shù)來表示判別式d。簡化算法，在算法中全部使用整數(shù)，使用e=d-0.25代替d。初始化運算d=1.25-R對應(yīng)于e=1-R。由于e的初值為整數(shù)，且在運算過程中的增量也是整數(shù)，故e始終是整數(shù)，所以判別式d<0對應(yīng)于e<-0.25，等價于e<0。判別式d≥0對應(yīng)于e≥-0.25，等價于e≥0。2025/7/1830voidMidpointCircle1(intR){ intx,y,d; x=0;y=R;d=1-R; SetPixel(x,y); while(x<y) { if(d<0) {d+=2*x+3;x++;} else {d+=2*(x-y)+5;x++;y--;} SetPixel(x,y); }}2025/7/1831算法三：中點畫圓法改進二設(shè)Δx=2*x+3，Δy=-2*y+2，則if(d<0){d+=Δx;Δx+=2;x++;}else{d+=(Δx+Δy);Δx+=2;Δy+=2;x++;y--;}每當(dāng)x遞增1，Δx遞增2。每當(dāng)y遞減1，Δy遞增2。由于初始像素為(0,R)，所以Δx的初值為3，Δy的初值為-2R+2。

if(d<0){d+=2*x+3;x++;}else{d+=2*(x-y)+5;x++;y--;}2025/7/1832voidMidpointCircle2(intR){ intx,y,deltax,deltay,d; x=0;y=R;d=1-R;

deltax=3;deltay=2-R-R; SetPixel(x,y); while(x<y){ if(d<0){

d+=deltax;deltax+=2; x++;

} else{

d+=(deltax+deltay);

deltax+=2;deltay+=2; x++;y--; } SetPixel(x,y); }}2025/7/1833在0≤x≤y的1/8圓周上，像素坐標(biāo)x值單調(diào)增加，y值單調(diào)減少。

設(shè)第i步已確定（xi,yi）是要畫圓上的像素點，看第i+1步像素點（xi+1,yi+1）應(yīng)如何確定。下一個像素點只能是（xi+1,yi）或者（xi+1,yi-1）中的一個算法四：Bresenham畫圓算法2025/7/1834構(gòu)造判別式：2025/7/1835構(gòu)造判別式：1.精確圓弧是③，則dH>0和dD>0． 若pi<0，即dH<dD應(yīng)選H點。 若pi≥0，即dH≥dD應(yīng)選D點。2.若精確圓弧是①或②，顯然H是應(yīng)選擇點，而此時dH≤0，dD>0，必有pi<0。3.若精確圓弧是④或⑤，顯然D是應(yīng)選擇點，而此時dH>0，dD≤0，必有pi>0。得出結(jié)論：pi做判別量，pi<0時，選H點為下一個像素點，pi≥0時，選D點為下一個像素點。⑤④③②①HD(xi,yi)2025/7/1836從pi計算pi+1

2025/7/1837從pi計算pi+1

當(dāng)pi≥0時，應(yīng)選D點，即選當(dāng)pi<0時，應(yīng)選H點，即選2025/7/1838畫圓的起始點是(0，R)，即x1=0，y1=R，代入前式，令i=1，就得到： 2025/7/1839voidBresenhamCircle(intR){

intx,y,p; x=0;

y=R; p=3-2*R; for(;x<=y;x++){

SetPixel(x,y); if(p>=0){

p+=4*(x-y)+10; y--; } else{ p+=4*x+6; } }}2025/7/1840只需修改語句SetPixel(x,y)，畫八個對稱的點，就可以畫出全部圓周。若加一個平移，就可以畫出圓心在任意位置的圓周。voidBresenhamCircle(intR){

intx,y,p; x=0;

y=R; p=3-2*R; for(;x<=y;x++){

SetPixel(x,y); if(p>=0){

p+=4*(x-y)+10; y--; } else{ p+=4*x+6; } }}2025/7/1841第三節(jié)橢圓掃描轉(zhuǎn)換算法中點畫圓法推廣到一般的二次曲線橢圓上一點(x,y)處的法向量為上半部分：下半部分：2025/7/1842橢圓的掃描轉(zhuǎn)換算法:2025/7/18432025/7/18442025/7/18452025/7/18462025/7/1847voidMidpointEllipse(inta,intb){ intx,y; doubled1,d2; x=0;y=b; d1=b*b+a*a*(-b+0.25); SetPixel(x,y); while(b*b*(x+1)<a*a*(y-0.5)){ if(d1<0){ d1+=b*b*(2*x+3);x++; }else{ d1+=(b*b*(2*x+3)+a*a*(-2*y+2));x++;y--; } SetPixel(x,y); } d2=b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b; while(y>0){ if(d2<0){ d2+=b*b*(2*x+2)+a*a*(-2*y+3);x++;y--; }else{ d2+=a*a*(-2*y+3);y--; } SetPixel(x,y); }}2025/7/1848第四節(jié)區(qū)域填充種子填充算法掃描線填充算法多邊形掃描轉(zhuǎn)換算法邊填充算法圖案填充2025/7/18491.概念區(qū)域：指光柵網(wǎng)格上的一組像素。區(qū)域填充：把某確定的像素值送入到區(qū)域內(nèi)部的所有像素中。一、種子填充算法2025/7/18502.區(qū)域填充方法分為兩大類。

⑴區(qū)域由多邊形圍成，區(qū)域由多邊形的頂點序列來定義;

優(yōu)點：占用內(nèi)存少，缺點：需要區(qū)分內(nèi)外側(cè)

⑵是通過像素的值來定義區(qū)域的內(nèi)部優(yōu)點：形狀可任意復(fù)雜，可直接著色缺點：幾何意義不直觀2025/7/18513.用像素值定義區(qū)域（1）內(nèi)定義區(qū)域(oldvalue)指出區(qū)域內(nèi)部所具有的像素值,（內(nèi)點表示）（2）邊界定義區(qū)域(boundaryvalue)，指出區(qū)域邊界所具有的像素值。此時區(qū)域邊界上所有像素具有某個邊界boundaryvalue。區(qū)域的邊界應(yīng)該是封閉的，指明區(qū)域的內(nèi)部和外部。以像素為基礎(chǔ)的區(qū)域填充主要是依據(jù)區(qū)域的連通性進行。2025/7/18524.區(qū)域的連通性（1）四連通:從區(qū)域中的一個像素出發(fā)，經(jīng)連續(xù)地向上下左右四個相鄰像素的移動，就可以到達區(qū)域內(nèi)的任意另一個像素。（2）八連通:如果除了要經(jīng)上下左右的移動，還要經(jīng)左上、右上、左下和右下的移動，才能由一個像素走到區(qū)域中另外任意一個像素.四連通區(qū)域必定是八連通區(qū)域，反之不一定。四連通區(qū)域八連通區(qū)域2025/7/18534.區(qū)域的連通性（1）四連通（2）八連通2025/7/18545.種子填充算法

利用區(qū)域的連通性進行區(qū)域填充的要素：明確定義區(qū)域，事先給定一個區(qū)域內(nèi)部像素，稱為種子。做區(qū)域填充時，要對光柵網(wǎng)格進行遍歷，找出由種子出發(fā)能達到而又不穿過邊界的所有像素。這種利用連通性的填充，優(yōu)點：不受區(qū)域不規(guī)則性的影響，缺點：需要事先知道一個內(nèi)部像素。

2025/7/1855（1）四連通內(nèi)定義區(qū)域填充算法：voidFloodfill(intx,inty,COLORREFoldvalue,COLORREFnewvalue){/*(x,y)為種子

oldvalue是原值

newvalue是新值，應(yīng)不等于原值。*/{

//是否在區(qū)域內(nèi)并且尚未被訪問過

if(GetPixel(x,y)==oldvalue){{

SetPixel(x,y,newvalue);//賦值為新值 Floodfill(x,y-1,oldvalue,newvalue);//向上擴散

Floodfill(x,y+1,oldvalue,newvalue);//向下擴散

Floodfill(x-1,y,oldvalue,newvalue);//向左擴散

Floodfill(x+1,y,oldvalue,newvalue);//向右擴散

}}

優(yōu)點：算法簡單缺點：重復(fù)多2025/7/1856（2）四連通邊界定義區(qū)域填充算法：voidBoundaryfill(intx,inty,COLORREFboundaryvalue,COLORREFnewvalue)/*(x,y)為種子位置boundaryvalue是邊界像素值newvalue是區(qū)域內(nèi)像素新值，未填充前區(qū)域內(nèi)不應(yīng)有值為newvalue的像素。*/{ if(GetPixel(x,y)!=boundaryvalue &&GetPixel(x,y)!=newvalue)//未達邊界且未訪問過 { SetPixel(x,y,newvalue);//賦以新值

//向四個方向擴散。

Boundaryfill(x,y-1,boundaryvalue,newvalue); Boundaryfill(x,y+1,boundaryvalue,newvalue); Boundaryfill(x-1,y,boundaryvalue,newvalue); Boundaryfill(x+1,y,boundaryvalue,newvalue); }}//算法簡單，多層遞歸，存儲空間有限－>堆棧溢出2025/7/1857掃描線種子填充算法(適用于邊界定義的四連通區(qū)域）像素段：將區(qū)域內(nèi)由邊界點限定的同一行內(nèi)相連接的不具有新值newvalue的一組像素稱為一個像素段，像素段用它最右邊的像素來標(biāo)識。

6123475二、掃描線填充算法2025/7/1858算法的步驟如下：1.[初始化]將堆棧置為空，將給定的種子點(x,y)壓入堆棧2.[出棧]如果堆棧為空，算法結(jié)束，否則取棧頂元素(x,y)作為種子點3.[區(qū)段填充]從種子點(x,y)開始沿當(dāng)前掃描線向左右兩個方向逐個像素進行填充，直到遇到邊界點為止4.[定范圍]用xl和xr分別表示在步驟3中填充的區(qū)段的左右兩個端點的橫坐標(biāo)5.[進棧]對當(dāng)前掃描線上下相鄰的兩條掃描線從右向左的確定位于[xl,xr]區(qū)域內(nèi)的像素段。

如果區(qū)域內(nèi)的像素未填充且不是邊界，則取像素段的右端點作為種子點，壓入堆棧，再轉(zhuǎn)到步驟2， 否則轉(zhuǎn)到步驟2。2025/7/1859下面我們用偽C語言寫出掃描線填充算法。

voidScanlineSeedfill(intx,inty,COLORREFboundaryvalue,COLORREFnewvalue){ intx0,xl,xr,y0,xid; intflag; Stacks；

Pointp;

s.push(Point(x,y));//種子像素入棧

while(!s.isempty())

{

p=s.pop();//棧頂像素出棧

x=p.x;y=p.y;

SetPixel(x,y,newvalue);

2025/7/1860 x0=x+1;while(GetPixel(x0,y)!=boundaryvalue&&

GetPixel(x0,y)!=newvalue)//填充右方像素{ SetPixel(x0,y,newvalue); x0++;}xr=x0-1;//最右邊像素x0=x-1; while(GetPixel(x0,y)!=boundaryvalue&&

GetPixel(x0,y)!=newvalue)//填充左方像素{ SetPixel(x0,y,newvalue); x0--;}xl=x0+1;//最左邊像素2025/7/1861//檢查上一條掃描線和下一條掃描線，//若存在非邊界且未填充的像素，//則選取代表各連續(xù)區(qū)間的種子像素入棧。y0=y;for(inti=1;i>=-1;i-=2)//從最右像素開始尋找上下兩行的像素段{ x0=xr；

y=y0+i; while(x0>=xl) { flag=0;//是否找到像素段的標(biāo)識，是為1，否為0 while((GetPixel(x0,y)!=boundaryvalue)&& (GetPixel(x0,y)!=newvalue)

&&(x0>=xl)) { if(flag==0)

{ flag=1;//標(biāo)志找到新的像素段

xid=x0; } x0--; }12025/7/1862//將最右側(cè)可填充像素壓入棧中

if(flag==1) {

s.push(Point(xid,y)); flag=0; }//檢查當(dāng)前填充行是否被中斷，若被中斷，尋找左方第一個可填充像素//判斷當(dāng)前點是否為邊界點//判斷當(dāng)前點是否為已填充點

while((GetPixel(x0,y)==boundaryvalue ||(GetPixel(x0,y)==newvalue)) &&(x0>=xl))

x0--;

}//while(x0>=xl)

}//for(inti=1;i>=-1;i-=2) }//while(!s.isempty())}1122025/7/18632025/7/18642025/7/1865三、多邊形的掃描轉(zhuǎn)換算法“奇偶”性質(zhì)：即一條直線與任意封閉的曲線相交時，總是從第一個交點進入內(nèi)部，再從第二個交點退出，以下交替的進入退出，即奇數(shù)次進入，偶數(shù)次退出。當(dāng)然可能有一些“相切”的點應(yīng)特殊處理。2025/7/1866奇偶規(guī)則

凹多邊形自相交多邊形帶有空洞的多邊形2025/7/1867e1e6e2e5e3e4三、多邊形的掃描轉(zhuǎn)換算法掃描轉(zhuǎn)換算法步驟：對于每一條掃描線step1．找出掃描線與多邊形邊界線的所有交點；step2．按x坐標(biāo)增加順序?qū)稽c排序；step3．在交點對之間進行填充。（偶數(shù)）2025/7/1868e1e6e2e5e3e4三、多邊形的掃描轉(zhuǎn)換算法局部極大：如果一個頂點的前面和后面各有一些相鄰頂點的y坐標(biāo)，都小于該頂點的y坐標(biāo)，則這個頂點是局部極大。局部極?。喝绻粋€頂點的前面和后面各有一些相鄰頂點的y坐標(biāo)，都大于該頂點的y坐標(biāo)，則這個頂點是局部極小。2025/7/1869三、多邊形的掃描轉(zhuǎn)換算法問題一：交點個數(shù)是奇數(shù)奇數(shù)個交點的特殊處理：發(fā)生奇數(shù)個交點的情況出現(xiàn)在掃描線穿過非局部極值點，該非局部極值點看做是一個頂點，將其上面的邊縮短一個單位。

e1e6e2e5e3e4

對非極值點的簡便處理2025/7/18702025/7/1871e1e6e2e5e3e4三、多邊形的掃描轉(zhuǎn)換算法問題二：“相切”是否滿足奇偶規(guī)則?“相切”點的特殊處理：不做處理與平行的掃描線“相切”的切點一定是局部極大或局部極小。邊的“切點”一定是偶數(shù)個，滿足奇偶規(guī)則，不做處理。2025/7/1872頂點處理當(dāng)頂點表現(xiàn)為是局部極大或局部極小時，就看做是二個，否則看做一個。局部極大或局部極小點，交點看做是二個非局部極值點，交點看做一個2025/7/1873step1．如何計算掃描線與多邊形邊界線的所有交點？若掃描線yi與多邊形邊界線交點x的坐標(biāo)是xi，則對下一條掃描線yi+l，它與那條邊界線的交點的x坐標(biāo)xi+1，可如下求出：2025/7/1874邊表ET：記錄多邊形的所有邊，按邊的下端點y坐標(biāo)遞增排序

“吊桶”:記錄一條邊的信息ymaxxmin

1/mnextymax:邊的上端點(具有較大y坐標(biāo)的端點)的y坐標(biāo)xmin:邊的下端點(具有較小的y坐標(biāo)的端點)的x坐標(biāo)1/m:斜率的倒數(shù)next:指向下一條邊的指針2025/7/1875活躍邊：與當(dāng)前掃描線相交的邊活躍邊表AET：存貯當(dāng)前掃描線相交的各邊的表。

ymaxx1/mnextymax:當(dāng)前邊的上端點的y坐標(biāo)x:當(dāng)前邊與掃描線交點的x坐標(biāo)1/m:當(dāng)前邊的斜率的倒數(shù)next:指向下一條邊的指針每次離開一條掃描線進入下一條之前，將表中有但與下一條掃描線不相交的邊清除出表，將與下一條掃描線相交而表中沒有的邊加入表中。2025/7/18761.邊的上端點y坐標(biāo)ymax。2.邊的下端點的x坐標(biāo)xmin。3.斜率的倒數(shù)，即1/m。2025/7/1877Polygonfill(EdgeTableET,COLORREFcolor){1.y=置y為邊表ET中各登記項對應(yīng)的y坐標(biāo)中最小的值;2.活躍邊表AET初始化為空表;3.若AET非空或ET非空，則做下列步驟，否則算法結(jié)束{3.1.將ET中登記項y對應(yīng)的各“吊桶”合并到表AET中,將AET中各吊桶按x坐標(biāo)遞增排序；3.2.在掃描線y上，按照AET表提供的x坐標(biāo)對,用color實施填充；3.3.將AET表中有y=ymax的各項清除出表；3.4.對AET中留下的各項，分別將x換為x+1/m，求出AET中各邊與下一條掃描線交點的x坐標(biāo)；3.5.y=y＋1，返回步驟3處理下一條掃描線。}}2025/7/1878基本思想：對于每一條掃描線和每條多邊形邊的交點，都將該掃描線上交點右方的所有像素取補，并對多邊形的每條邊按一定順序(逆時針、順時針均可)做此處理四、邊填充算法(正負(fù)相消法)2025/7/1879待填充區(qū)域D對區(qū)域的每一條邊與掃描線的每一個交點當(dāng)做

沿D的邊界經(jīng)歷一周后，只要則否則D2025/7/1880voidEdgeFill(PointArray&ptArray,COLORREFcolor){ for(y=y1;y<=y2;y++) for(x=x1;x<=x2;x++) MASK[y][x]=false; for(區(qū)域D內(nèi)的每一條邊PiPi+1){ xs=x[i];dxs=(x[i+1]-x[i])/(y[i+1]-y[i]); dys=abs(y[i+1]-y[i])/(y[i+1]-y[i]); for(ys=y[i];ys!=y[i+1];ys+=dys){ Ixs=int(xs+0.5); for(x=Ixs;x<=x2;x++) MASK[ys][x]=!MASK[ys][x]; xs=xs+dys*dxs