Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换方法。bresenham算法是计算机图形学中为了“显示器(屏幕或打印机)系由像素构成”的这个特性而设计出来的算法,使得在求直线各点的过程中全部以整数来运算,因而大幅度提升计算速度。
原理
过各行、各列像素中心构造一组虚拟网格线,按直线从起点到终点的顺序计算直线各垂直网格线的交点,然后确定该列像素中与此交点最近的像素。
优点
该算法的优点在于可以采用增量计算,使得对于每一列,只要检查一个误差项的符号,就可以确定该列所求的像素。
公式
voidIntegerBresenhamlin(intx0,inty0,intx1,inty1,intcolor)
{
intx,y,dx,dy,unitx,unity,fabsdx,fabsdy,e;
dxx1x0;
dyy1y0;
fabsdx(int)fabs(dx);
fabsdy(int)fabs(dy);
xx0;
yy0;
if(fabsdxfabsdy)
{
for(i0;i0)
{
ee2
}
}forend
}
else
{
efabsdy
for(i0;i0)
{
ee2
}
}forend
}ifend
}:
改进算法
原理:
上述bresenham算法在计算直线斜率与误差项时用到了小数与除法,可以改用整数以避免除法。由于算法中用到误差项的符号,因此可以做如下替换:e2edx。
以下是C语言方式描述的,在MFC下的核心绘图代码(画圆的算法)
{
CDCpDCGetDC();
intp,r,x,y,c,i;
r...
(全文)