|
|
以前看到Bresenham畫(huà)線算法，直接拿來(lái)用，沒(méi)有去推導(dǎo)它,近日,參考一些資料,特整理其算法推導(dǎo)過(guò)程如下。各位大蝦如果知道其細(xì)節(jié)，趕緊閃過(guò)，不用浪費(fèi)時(shí)間了。
基本上Bresenham畫(huà)線算法的思路如下:
// 假設(shè)該線段位于第一象限內(nèi)且斜率大于0小于1,設(shè)起點(diǎn)為(x1,y1),終點(diǎn)為(x2,y2).
// 根據(jù)對(duì)稱性,可推導(dǎo)至全象限內(nèi)的線段.
1.畫(huà)起點(diǎn)(x1,y1).
2.準(zhǔn)備畫(huà)下個(gè)點(diǎn)。x坐標(biāo)增1，判斷如果達(dá)到終點(diǎn)，則完成。否則，由圖中可知,下個(gè)要畫(huà)的點(diǎn)要么為當(dāng)前點(diǎn)的右鄰接點(diǎn),要么是當(dāng)前點(diǎn)的右上鄰接點(diǎn).
2.1.如果線段ax+by+c=0與x=x1+1的交點(diǎn)的y坐標(biāo)大于M點(diǎn)的y坐標(biāo)的話,下個(gè)點(diǎn)為U(x1+1,y1+1)
2.2.否則,下個(gè)點(diǎn)為B(x1+1,y1)
3.畫(huà)點(diǎn)(U或者B).
4.跳回第2步.
5.結(jié)束.
這里需要細(xì)化的是怎么判斷下個(gè)要畫(huà)的點(diǎn)為當(dāng)前點(diǎn)的右鄰接點(diǎn)還是當(dāng)前點(diǎn)的右上鄰接點(diǎn).
設(shè)線段方程：ax+by+c=0(x1<x<x2,y1<y<y2)
令dx=x2-x1,dy=y2-y1
則：斜率-a/b = dy/dx.
從第一個(gè)點(diǎn)開(kāi)始，我們有F(x,1,y1) = a*x1+b*y1+c=0
下面求線段ax+by+c=0與x=x1+1的交點(diǎn):
由a*(x1+1)+b*y+c = 0, 求出交點(diǎn)坐標(biāo)y=(-c-a(x1+1))/b
所以交點(diǎn)與M的y坐標(biāo)差值Sub1 = (-c-a(x1+1))/b - (y1+0.5) =-a/b-0.5，即Sub1的處始值為-a/b-0.5。
則可得條件當(dāng) Sub1 = -a/b-0.5>0時(shí)候,即下個(gè)點(diǎn)為U.
反之,下個(gè)點(diǎn)為B.
代入a/b,則Sub1 = dy/dx-0.5.
因?yàn)槭莻�(gè)循環(huán)中都要判斷Sub,所以得求出循環(huán)下的Sub表達(dá)式,我們可以求出Sub的差值的表達(dá)式.下面求x=x1+2時(shí)的Sub，即Sub2
1.如果下下個(gè)點(diǎn)是下個(gè)點(diǎn)的右上鄰接點(diǎn)，則
Sub2 = (-c-a(x1+2))/b - (y1+1.5) = -2a/b - 1.5
故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 1.5 - (-a/b-0.5) = -a/b -1.代入a/b得Dsub = dy/dx -1;
2.如果下下個(gè)點(diǎn)是下個(gè)點(diǎn)的右鄰接點(diǎn)，
Sub2 = (-c-a(x1+2))/b - (y1+0.5) = -2a/b - 0.5
故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 0.5 - (-a/b-0.5) = -a/b.代入a/b得Dsub = dy/dx;
于是，我們有了Sub的處始值Sub1 = -a/b-0.5 = dy/dx-0.5,又有了Sub的差值的表達(dá)式Dsub =dy/dx -1 （當(dāng)Sub1 > 0）或 dy/dx（當(dāng)Sub1 <0）.細(xì)化工作完成。
于是pcode可以細(xì)化如下：
// Pcode for Bresenham Line
// By SoRoMan
x=x1;
y=y1;
dx = x2-x1;
dy = y2-y1;
Sub = dy/dx-0.5; // 賦初值，下個(gè)要畫(huà)的點(diǎn)與中點(diǎn)的差值
DrawPixel(x, y); // 畫(huà)起點(diǎn)
while(x<x2)
{
x++;
if(Sub > 0) // 下個(gè)要畫(huà)的點(diǎn)為當(dāng)前點(diǎn)的右上鄰接點(diǎn)
{
Sub += dy/dx - 1; //下下個(gè)要畫(huà)的點(diǎn)與中點(diǎn)的差值
y++; // 右上鄰接點(diǎn)y需增1
}
else// 下個(gè)要畫(huà)的點(diǎn)為當(dāng)前點(diǎn)的右鄰接點(diǎn)
{
Sub += dy/dx;
}
// 畫(huà)下個(gè)點(diǎn)
DrawPixel(x,y);
}
PS:一般優(yōu)化：
為避免小數(shù)轉(zhuǎn)整數(shù)以及除法運(yùn)算，由于Sub只是用來(lái)進(jìn)行正負(fù)判斷，所以可以令Sub= 2*dx*Sub = 2dy-dx,則
相應(yīng)的DSub = 2dy - 2dx或2dy.
思考1:如果Sub = 0時(shí)，會(huì)產(chǎn)生取兩個(gè)點(diǎn)都可以的問(wèn)題。這個(gè)問(wèn)題還沒(méi)深入。
//========================================以上部分轉(zhuǎn)===========================================
優(yōu)化后的代碼：
void GUI_Line(u8 x1,u16 y1,u8 x2,u16 y2,u16 Color)
{
s16 dx,dy,d;
u16 y=y1;
u8 x;
dx=x2-x1;
dy=y2-y1;
d=2*dy-dx;
for(x=x1;x<x2+1;x++)
{
GUI_Pixel(x,y,Color);
if(d>0)
{
y++;
d+=2*(dy-dx);
}
else
{
d+=2*dy;
}
}
}
而適合任意斜率的代碼如下：
void GUI_Line(u8 x1,u16 y1,u8 x2,u16 y2,u16 Color)
{
s16 d,d1,d2;
s16 x=x1,y=y1,a=y1-y2,b=x2-x1;
s16 cx=(b>=0 ? 1 :(b=-b,-1));
s16 cy=(a<=0 ? 1 :(a=-a,-1));
if(-a<=b)//斜率絕對(duì)值 <=1
{
d=2*a+b;
d1=2*a;
d2=2*(a+b);
while(x!=x2+1)
{
GUI_Pixel(x,y,Color);
if (d< 0)
y+= cy, d += d2;
else
d+= d1;
x +=cx;
}
}
else//斜率絕對(duì)值 > 1
{
d = 2 * b + a;
d1 = 2 * b;
d2 = 2 * (a + b);
while(y != y2+1)
{
GUI_Pixel(x,y,Color);
if(d<0)
d+=d1;
else
x+=cx,d+=d2;
y+=cy;
}
}
}
|
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
