《图形显示软件》PPT课件

《《图形显示软件》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机图形显示技术2第十一讲图形软件Bresenham画线算法圆的生成算法Bresenham画圆法中点画圆法区域填充算法扫描线填充算法边界填充算法3图形软件——Bresenham画线算法AboutBresenhamE.JackBresenham——ProfessorofComputerSciencePh.D.,StanfordUniversity,1964MSIE,StanfordUniversity,1960BSEE,UniversityofNewMexico,1959Retiredfrom27yearsse

2、rviceatIBMasaSeniorTechnicalStaffMemberin1987.Havetaught10yearsatWinthrop.Holderoffivepatents.4图形软件——Bresenham画线算法Bresenham算法该算法由Bresenham在1965年提出，是目前使用较为广泛的一种扫描转换算法，可用于直线、圆弧等图元的扫描转换。5图形软件——Bresenham画线算法Bresenham画线算法基本思想过各行各列像素中心构造一组假想的栅格按直线从起点到终点的顺序计算直线与各垂直

3、网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素6图形软件——Bresenham画线算法Bresenham画线算法设直线从起点（x1,y1）到终点（x2,y2）设直线方程为：y=kx+b其中b=y1-k*x17图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）根据即DDA算法的讨论有：xi+1=xi+1(1)yi+1=yi+k(2)在1a象限里，当直线光栅化时，x每次都增加1个单元：xi+1=xi+18图形软件——Bresen

4、ham画线算法Bresenham画线算法由于k不一定是整数，因此由(2)式求出的y也不一定是整数。所以要用最靠近y的整数yi来代替y假设直线上第i个像素坐标为(xi,yi)，那么，它的下一个点的像素点的可能位置为(xi+1,yi)或(xi+1,yi+1)。如图：9图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）如上图在x=xi+1处，直线上y的值y=k(xi+1)+b该点距离点(xi+1,yi)和点(xi+1,yi+1)的距离分别为d1和d2

5、：d1=y-yi=k(xi+1)+b-yid2=yi+1-y=yi+1-k(xi+1)-b因此，这两个距离的差为：d1-d2=2k(xi+1)-2yi+2b-1(1)10图形软件——Bresenham画线算法Bresenham画线算法根据（1）式，作如下讨论分析：当d1-d2>0时，说明直线上的理论点距离(xi+1,yi+1)较近，因此下一个直线像素点应取(xi+1,yi+1)。当d1-d2<0时，说明直线上的理论点距离(xi+1,yi)较近，因此下一个直线像素点应取(xi+1,yi)。当d1-d2=0时，说明

6、直线上的理论点距离上、下两个像素点的距离相等，因此规定取(xi+1,yi+1)作为下一个直线像素点11图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）因此，利用（d1-d2）的符号就可以决定下一个像素点的选择然而含有变量xi、yi，不利于计算。为此，我们构造一个新的判别式：pi=x*(d1-d2)=2xiy-2yix+c（2）其中：x=(x2-x1)>0，因此pi与(d1-d2)符号相同；y=y2-y1；c=2y+x(2b-1)

7、12图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）①以i+1代入式(2)中的i，得：pi+1=x*(d1-d2)=2xi+1y-2yi+1x+c（3）②将式(3)减去式(2)，并由xi+1=xi+1可得：pi+1=pi+2y-2x(yi+1-yi)（4）③假设直线上的初始端点恰好是其像素点的坐标，则将x1,y1和b代入式（2）中的xi,yi可到pi的初始值p1=2x1y-2y1x+2y+x[2(y1-kx1)-1]=2y

8、-x（5）13图形软件——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）利用上面构造的误差判别变量，可得第1a象限内的直线Bresenham算法：p1=2y-xxi+1=xi+1yi+1=yi+1,pi+1=pi+2(y-x)当pi≥0时yi+1=yi,pi+1=pi+2y当pi<0时14图形软件——Bresenh