Computer Graphics

浏览量:5,350

布雷森汉姆直线算法

本篇文章,主要介绍布雷森汉姆直线算法,包括一个用glut实现的demo。代码的下载地址为:https://github.com/twinklingstar20/twinklingstar_cn_demo_bresenham-line-algorithm 一.             布雷森汉姆(Bresenham)算法说明 图1. 在显示器上绘制直线 如图1所示,在显示器上绘制一条直线,直线上一些像素会被启动,由此形成一条直线效果。直线绘制算法是图形学中的一个基本的算法,绘制直线时需要考虑哪些像素需要被启动,这里介绍布雷森汉姆直线绘制算法。它是一种基本的递增算法,基于前一个像素信息就可以计算出下一个像素值,能确定一条直线上哪些像素要启动,而且它的计算只采用整数值,避免了浮点运算运算。 布雷森汉姆算法有几种变种,这里考虑其中的一个中点算法。假设现在要绘制两个端点是(ax,ay)和(bx,by)之间的线段,需要确定介于它们之间的像素序列。为了简化讨论,这里考虑一种特殊的情况,即ax<bx,直线斜率0<k<1的情况。线段的宽是W=bx-ax,高是H=by-ay,则有W>H,所有穿过两个端点的直线都满足下面的一个等式: -W(y-ay)+H(x-ax)=0 定义一个函数如下所示: F(x,y) = -2W(y-ay)+2H(x-ax) 如果F(x,y)>0,则说明(x,y)位于直线下;如果F(x,y)<0,则说明(x,y)位于直线上。 图2. 中点算法的一个参数 图中所示,假设从黑色点(Px,Py)处开始考虑算法,现在考虑在Px+1的位置上,Y方向上最合适的值是Py +1还是Py,即U(Px+1, Py+1)还是L(Px +1,Py)。接着是要判断Q点更靠近U还是L,可以通过计算中间值M(Px+1,Py+1/2),可以使用上面所说的等式,如果F(Mx,My)<0,则点M在直线上,选择L点;如果F(Mx,My)>0,则点M在直线下,选择U点,Y方向上加1。 F(Mx,My)=-2W(Py+1/2-ay) + 2H(Px+1-ax) 接下来,当X方向上的值是Px+2时,判断现在的M取值是M’还是M’’。如果前面一步选择的是L点,则取M’(Px+2,Py+1/2);相反,如果前一步选择的是U点,则取M’’ (Px+2,Py+3/2)。    所以分下面两种情况讨论: 1)  如果前一步F的值是负的,则有Fnext=F(Px+2,Py+1/2)=-2W(Py+1/2-ay) + 2H(Px+2-ax) = F(Mx,My)+2H 2)  如果前一步F的值是正的,则有 Fnext=F(Px+2,Py+3/2)=-2W(Py+3/2-ay) + 2H(Px+2-ax) = F(Mx,My)+2(H-W) 初始情况下M=(ax+1,ay+1/2),则有F(x,y)=-2W(ay+1/2-ay)+2H(ax+1-ax)=2H-W,如果这里没有乘以2的话,就会有浮点数存在了。总结下算法流程就是: 1)  初始化F=2H-W,x=ax,y=ay

spacer