用有限像素点表示无限点的直线。
用离散像素点去逼近直线,需要知道像素点的坐标。
求过P0(x0,y0),P1(x1,y1)的直线段方程
y = kx +b;
k = (y1-y0)/(x1-x0) ; (x1 != x0)
假设x已知,从x的起点x0开始,沿x方向前进一个像素(步长为1),即可求出相应的y值。 因为像素的坐标是整数,所以y值要做取整处理。
如(1.7 , 0.8) ---取整---> (1 , 0)
(1.7 , 0.8) --- +0.5 --->(2.2 , 1.3) ---取整 --->(2 , 1);
直线在计算机中是最基础的图形,一个动画或者真实感图形往往需要调用大量的画直线程序,因此直线算法的好坏与效率将直接影响图形的显示速度与质量。
回顾算法 : y = kx + b ,需要做一次乘法,一次加法和一次取整处理。在计算机中,最快的是加法运算,为了提高效率,减少计算量,关键就是如何把乘法取消。
三个著名的 直线绘制的常用算法:1,数值微分法(DDA) 2.中点画线法 3.Bresenham算法
数值微分法(Digital Differential Analyzer):
引进了图形学一个很重要的思想——增量思想
假设(xi , yi) (x i+1 ,y i+1) 都在直线上, 因为x是递增的,每次递增的量为1,所以
所以 y i+1 = yi + k
这个式子含义就是,当前步的y值等于前一步的y值加上斜率k 。
这样就把原来的一个乘法和一个加法 变成了 一个加法 。
DDA示例
改进效率 y i+1 = yi + k ,每步只做一个加法,如何改进?
1.一般情况下y,k都是浮点数,每一步运算都需要对y进行四舍五入再取整,改进途径:把浮点运算变成整数加法。
2.现在是用斜截式表示直线,用其他的式子来表示直线方程?