计算机图形学学习(一) 直线Bresenham算法讲解及matlab实现
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)]
如果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
成果演示
放大后观察为一个一个的点
上一篇: 字符驱动设备之poll机制