• 光栅画线算法关闭
  • 雪峰 发表于 2016-09-24

    • 今天了弄了一整天，终于把3种画直线的光栅算法的demo给弄好了，主要是想实现把一个小方块作为一个像素块显示直线算法的锯齿形状，以及改编适应各种斜率及方向。顺便把demo展示页给改了一下，把文字介绍默认隐藏了，便于全屏展示。

    下面是测试的效果图：

    baidu-ime_2016-9-23_23-0-59

    3种光栅画线算法分别是DDA算法，中点画线算法以及bresenham算法。从原理上来说DDA算法最简单，也适用于各种斜率。但是算法效率低，也只是适用于y = kx + b这一类型。中点画线可以把效率提高到整数加法级别，但是只适用于Ax + By + C = 0这一类型。而bresenham通过设定决策参数进行判断下一个像素的位置，而不依赖任何特定函数，所以适用于直线和曲线，且效率也可以提高至整数加法级别。

     

    1.DDA算法

    DDA算法即数字微分分析法，从名字即可知道采用微分增量进行位置设置。只不过像素的最小单位为1，可以看做是离散化的微分，即以x或y为方向进行增量为1的计算。增量运算的方向可以通过k值进行判断，应尽可能在变化量多的方向进行增量计算，以保证图像的正确性。

    |k|>1：即dy > dx ，以y为方向进行1个单位的递增或递减运算，然后得出dx = 1/k，跟前项x值相加，然后四舍五入得到下个像素点的x值。

    |k|< 1：即dy < dx，方法同上，dx = ±1，dy =± k。

    在下面的代码中，通过|dx|与|dy|的大小，以其中大的一个为step即递增或递减次数，然而直接计算每一步的dx和dy，这样就无需进行判断k的大小了，也就是任意k都可以实行，算是比较简便实用的算法了。算法来自《计算机图形学（第四版）》的中文版P103。

    
/*
DDA画线算法的区块化应用
*/

function DDA_Block(x1 , y1 , x2 , y2 , color){
var dx = x2 - x1;
var dy = y2 - y1;
var x = x1, y = y1;
var step;
if(Math.abs(dx) > Math.abs(dy)){
step = Math.abs(dx);
}else{
step = Math.abs(dy);
}
var xD = dx / step;
var yD = dy / step;
putBlock(x , y , colorS);
for(var i= 0 ; i < step; i++){
x += xD;
y += yD;
if(i == step - 1){
putBlock(Math.round(x) , Math.round(y) , colorE);
}else{
putBlock(Math.round(x) , Math.round(y) , color);
}
}
DrawTipLine(x1 , y1 , x2 , y2);
}

     

    2.中点画线算法

    该算法需要先确定k的大小，然后根据Ax + By + C = 0这个方程算出下个像素点的的两个可能值之间的中点与实际函数值之间的差值d，然后根据d的正负性判断像素点的位置，不断的算出新的d值即可。如当0 < k < 1时，以x方向为递增方向，dx = 1，假设当前像素点位置为（x，y），那么下一像素点的位置只能是（x + 1 ，y）或（x + 1 ， y + 1），它们的中点即为（x + 1 ， y + 0.5），所以可以通过直线方程Ax + By + C = 0算出 x + 1时的y值与中点的距离d，若d <0则说明直线在中点下方，所以离下面的像素点（x + 1 ， y）更近，反之则离上面的像素点（x + 1 ， y  + 1）更近，然后算出相应d的增量得到新的d值，如此持续下去即可。

    这个算法比较麻烦的是需要根据k的方向算出不同情况的d值，及增量的方向，可以分为 0 < k < 1 , k > 1 , – 1 < k < 0 ,  k < -1这几种。目前还在思考如何进行优化比较好。

     

    3.Bresenham画线算法

    利用Bresenham算法进行画线大致的思路是这样的：根据k值大小判断下一像素点的两个可能取值，然后分别算出两个点离理论像素点的距离，将这两个距离相减得到一个值p可作为判定依据。实际就是判断哪个点离理论值更近，跟中点画线算法类似，只需求出初始的p值即可，此后只需不断更新p值即可不断地判断。

    该算法也需对k的大小进行分类处理，不过只有两类，|k|<1 , |k| > 1。

    
/*
Bresenham画线算法
*/

function Bresenham_Block(x1 , y1 , x2 , y2 , color){
var dx = Math.abs(x2 - x1);
var dy = Math.abs(y2 - y1);
var p ;
var twoDMain;
var twoM;
var max;

var x = x1 , y = y1;
var direction = (x2 - x1) * (y2 - y1);

/*
根据dx与dy的相互大小，即|K|是否小于1，小于1则以x为增量，反之以y为增量
*/

if(dx > dy){
p = 2 * dy - dx
twoDMain = 2 * dy;
twoM = 2 * (dy - dx);
if( x1 > x2){
x = x2 ;
y = y2;
max = x1 ;
}else{
max = x2;
}
putBlock(x , y , colorS);
Bresenham_d("x");
}else{
p = 2 * dx - dy
twoDMain = 2 * dx;
twoM = 2 * (dx - dy);
if( y1 > y2){
x = x2 ;
y = y2;
max = y1 ;
}else{
max = y2;
}
putBlock(x , y , colorS);
Bresenham_d("y");
}

function Bresenham_d(main){
var another;
var type = main;
if(main == "x"){
main = x;
another = y;
console.log("dx > dy");
}else{
main = y;
another = x;
console.log("dy > dx");
}
while (main < max){
main++;
if(p < 0){
p += twoDMain;
}else{
if(direction > 0){
another++;
}else{
another--;
}
p += twoM;
}
if(type == "x"){
if(main == max){
putBlock(main , another , colorE);
}else{
putBlock(main , another , color);
}
}else{
if(main == max){
putBlock(another , main , colorE);
}else{
putBlock(another , main , color);
}
}

}

}

function great(a , b){
return (a>b) ? a : b;
}

DrawTipLine(x1 , y1 , x2 , y2);
}

    查看介绍

    光栅画线算法