计算机图形学-中点画线算法
在编写的FDGK/GUI决定采用中点画线算法绘制直线。故先研究了一下算法。
中点画线算法的原则是：如下图所示，但斜率K<1时，选定一个点之后，再计算中点M。如果M>0,这线更靠近E点，下一点选择为E点。反之选择NE点。
首先：f(x,y) = ax+by+c=0,
且 y = dy/dx *x + B,
so : f(x,y) = dy*x-dx*y+Bdx =0
so: a = dy, b = -dx, c = Bdx.
假设，已经选定P点，应用中点法则选择下一点是，我们只要计算f(x+1,y+1/2),并考察是正数还是负数。
我们定义d=f(x+1,y+1/2)=a(x+1)+b(y+1/2)+c.这样，对于d>0,d<0，我们只要选择NE点和E点就可以了。
这边假设选定为E点，那么中点M的位置怎么变化和d的值如何变化呢？显然M就沿着x轴递增一步。
此时：d1 = f(x+2,y+1/2)
从d1中减去d，可以得到一个增量差。d1= a = dy。
同理：如果选定下一点为NE点，d2 = a+b = dy-dx。
基于上面的讨论，增量的中点技术可以概括为：在每一步，我们根据上一步所得到的增量的符号去选择下一个像素点。然后根据说选择的像素，判定变量增加相应的增量差d1或d2。
对于初始值，我们选择第一个端点为(x0,y0)。则M为(x0+1,y+1/2).
f(x0+1,y0+1/2) = f(x0,y0)+a+b/2.
故： d0 = a+b/2 = dy - dx/2
为去掉d0中的小数，我们对d0进行放大。（在方程两边同乘于2）
d0 = 2*dy - dx
d1 = 2*dy
d2 = 2*(dy-dx)
所以，在斜率小于1的情况下，中点画线的算法实现如下：
void GUI_DrawLine(uint16 x0,uint16 y0,uint16 x1,uint16 y1,uint16 color)
{
uint16 dx,dy,incrE,incrNE,x,y,d;
dx = x1 - x0;
dy = y1 - y0;
d = (dy<<1) - dx;
incrE = dy<<1;
incrNE = (dy - dx)<<1;
x = x0;
y = y0;
GUI_DrawPoint(x,y,color);
while(x
{
if(d > 0)
{
d += incrNE;
x++;
y++;
}
else
{
d += incrE;
x++;
}
GUI_DrawPoint(x,y,color);
}
}
以上只是在K<1的情况下即在（1）中成立。那其他情况怎么办呢？
我的处理方法是这样的：
1、把3，4，5，6情况下的两个端点调换，把它变换成1，2，7，8的情况，这样我们要考虑的情况就少一半。
2、1和8，2和7关于x轴对称。1和2关于y=x对称。这样，我们就可以把1情况下的算法，移植到其他情况下。
改进后的算法如下：
void swap(uint16 *x0,uint16 *y0,uint16 *x1,uint16 *y1)
{
uint16 x,y;
x = *x1;
*x1 = *x0;
*x0 = x;
y = *y1;
*y1 = *y0;
*y0 = y;
}
void GUI_DrawLine(uint16 x0,uint16 y0,uint16 x1,uint16 y1,uint16 color)
{
int16 dx,dy,d;
uint16 x,y;
if( x0 > x1) /* 保证x0
{
swap(&x0,&y0,&x1,&y1);
}
dx = x1 - x0;
dy = y1 - y0;
if( dx == 0) /* 斜率为无穷大，画直竖线 */
{
LCD_DrawVLine(x0,y0,y1,color);
return;
}
if( dy == 0) /*斜率为零，画水平线 */
{
LCD_DrawHLine(x0,y0,x1,color);
return;
}
x = x0;
y = y0;
GUI_DrawPoint(x,y,color);
if((dx>=dy)&&(dy>0)) /* when 0
{
d = (dy*2) - dx;
while(x
{
if(d > 0)
{
d += (dy - dx)*2; /* 选择NE点 */
x++;
y++;
}
else
{
d += dy*2; /* 选择N点 */
x++;
}
GUI_DrawPoint(x,y,color);
}
return;
}
if( (dy>dx)&&(dy>0)) /* when k>1 */
{
d = dy - (dx*2);
while(y
{
if(d < 0)
{
d += (dy - dx)*2; /* 选择 NE 点 */
x++;
y++;
}
else
{
d += (-dx)*2; /* 选择N点 */
y++;
}
GUI_DrawPoint(x,y,color);
}
return;
}
if((dx>=ABS(dy))&&(dy<0)) /* when -1=
{
d = (dy*2) + dx; /* d = 2a-b */
while(x
{
if(d < 0)
{
d += (dy+dx) * 2; /* 选择SE点 */
x++;
y--;
}
else
{
d += dy*2; /* 选择S点 */
x++;
}
GUI_DrawPoint(x,y,color);
}
return;
}
if( (ABS(dy)>dx)&&(dy<0)) /* when k<-1 */
{
d = dy + (dx*2); /* d = a - 2b */
while(y>y1)
{
if(d > 0)
{
d += (dy + dx)*2; /* 选择 SE 点 */
x++;
y--;
}
else
{
d += (dx)*2; /* 选择S点 */
y--;
}
GUI_DrawPoint(x,y,color);
}
return;
}
}
阅读(2772) | 评论(0) | 转发(0) |
