uniharmony's blog

Bresenham算法的思想：
　　按照一种递推的模式，根据当前点的坐标计算出下一个点的坐标。仅仅需要进行整数加减乘运算。

具体的说：
　　f(x)为要表现的函数，y(x)为像素化的数值。x和y(x)均是整数，f(x)是实数。
　　斜率大于0小于1的情况下，x每变化1，y的变化为：
　　　　0, 当 f(x) - y(x-1) < 1/2 时
　　　　1, 当 f(x) - y(x-1) >= 1/2 时
　　如果令 q(x) = f(x) - y(x-1) - 1/2，那么只需要考察 q(x) > 0 就可以决定y的增量为0还是为1。为了不做除法，可以在两端同时乘一个引子k，记 k * q(x) = p(x)，则只需考察 p(x) > 0。并且p(x)也无需每一步重新计算，只需要加上每一步的递推差值 p(x+1) - p(x)。
　　当斜率值在其他范围的时候，上述思想照样可以使用，只是将对应的值做一个关于坐标轴或者直线 y = x 的轴对称变化即可。以下对于直线讨论斜率大于0小于1的情况，对于圆和椭圆讨论斜率小于-1的情况。
　　对于过(x0,f(x0))和(x1,f(x1))的直线（x0<x1，且x0和x1均为整数），
　　则p( x0 + 1 ) = - ( x1 - x0 )
　　　　若y不变，则 p(x+1) = p(x) + 2*( f(x1) - f(x0) )
　　　　若y改变，则 p(x+1) = p(x) + 2*( f(x1) - f(x0) ) - 2*( x1 - x0 )
　　对于以r为半径的圆而言，取 x0 = r，则 p( x0 + 1 ) = 5 - 4*r
　　　　若y不变，则 p(x+1) = p(x) + 4*( 2*y(x) + 1 )
　　　　若y该表，则 p(x+1) = p(x) + 4*( 2*y(x) + 1 - 2*( x + 1 ) )
　　对于以a,b为长短轴的椭圆而言，取 x0 = a，则 p( x0 + 1 ) = 4*a*a - 4*a*b*b + b*b
　　　　若y不变，则 p(x+1) = p(x) + 4*a*a*( 2*y(x) + 1 )
　　　　若y该表，则 p(x+1) = p(x) + 4*a*a*( 2*y(x) + 1 ) - 4*b*b*( x + 1 )

画圆的伪代码描述：
{
　　先画上对应于( r, 0 )的点，因为对于 x0 = r 而言，f(x0)和y(x0)相等。
　　p = 5 - 4*r;　　//计算p的初始值;
　　x = r;
　　for( y = 1; x >= y; y++ )
　　{
　　　　if( p < 0 )
　　　　{
　　　　　　画点(x,y);
　　　　　　p += 4*( 2*y + 1 );　　//做x不变时p的计算
　　　　}
　　　　else
　　　　{
　　　　　　x--;
　　　　　　画点(x,y);
　　　　　　p += 4*( 2*y + 1 - 2*x );　　//做x改变时p的计算
　　　　}
　　}
}