欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

计算机图形学学习(一) 直线Bresenham算法讲解及matlab实现

程序员文章站 2022-07-14 10:00:52
...

Bresenham算法介绍

Bresenham是计算机图形学领域使用最广泛的直线扫描转换算法,其核心思想是由误差项符号决定下一个像素点取右边的一个点还是右上的一个点

Bresenham算法实现

  • 这里只讲最简单的一种情况:直线位于第一象限

  • 设直线起点终点分别为(x0,y0)、(x1,y1),直线方程为y=kx+b,k=(y1-y0)/(x1-x0)

  • 设当前像素点为(xi,yi),当x每次增加一个像素点时下一个像素点坐标为(xi+1,yi)或(xi+1,yi+1)

  • 下一个点坐标由直线在xi+1处与yi、yi+1的距离d1、d2决定,d1=y-yi=kx+b-kxi=k(xi+1)+b-yi
    d2=(yi+1)-y=yi+1-[(k(xi+1)+b)]
    计算机图形学学习(一) 直线Bresenham算法讲解及matlab实现
    如果d1-d2>0,则下一个像素点坐标为(xi+1,yi+1),否则为(xi+1,yi)

  • 令Pi=(d1-d2)Δx,将k=Δy/Δx带入Pi
    Pi=2xiΔy-2yiΔx+2Δy+(2b-1)Δx
    d1-d2是用于判断符号的误差项,因为在第一象限,所以Δx恒大于0,Pi仍可用于判断符号的误差,且计算仅包含整数运算,更利于计算机运算

  • ∵Pi=2xiΔy-2yiΔx+2Δy+(2b-1)Δx
    且Pi+1=2(xi+1)Δy-2(yi+1)Δx+2Δy+(2b-1)Δx
    ∴ Pi+1=Pi+2Δy-2(yi+1-yi)Δx
    若取右上方像素点,则yi+1-yi=1,则Pi+1=Pi+2Δy-2Δx
    若取右边像素点,则yi+1-yi=0,则Pi+1=Pi+2Δy

  • 求误差的初值P0: ∵y=kx+b,∴b=yi-kxi,将b,k=Δy/Δx,i=0代入Pi=2xiΔy-2yiΔx+2Δy+(2b-1)Δx
    解出结果为P0=2Δy-Δx

matlab代码实现

function Bresenham(x1,y1,x2,y2,color)

deltax=abs(x2-x1);
deltay=abs(y2-y1);

if(x2-x1>=0)
    s1=1;
else
    s1=-1;
end

if(y2-y1>=0)
    s2=1;
else
    s2=-1;
end

if(deltay>deltax)
    change=deltax;
    deltax=deltay;
    deltay=change;
    t=1;
else
    t=0;
end
f=2*deltay-deltax;
x=x1;
y=y1;
hold on
grid minor
scatter(x,y,'.',color)
for i=1:deltax
    if(f>=0)
        if(t==1)
            x=x+s1;
        else
            y=y+s2;
        end
        scatter(x,y,'.',color)
        f=f-2*deltax;
    else
         if(t==1)
            y=y+s2;
        else
            x=x+s1;
         end
         f=f+2*deltay;
    end
end
hold off

成果演示

计算机图形学学习(一) 直线Bresenham算法讲解及matlab实现

放大后观察为一个一个的点

计算机图形学学习(一) 直线Bresenham算法讲解及matlab实现

相关标签: 计算机图形学