计算机图形学直线生成

1、12(x,y)坐标地址线性表地址线性表1D表示显示屏幕显示屏幕2D表示像素由其左下角坐标表示像素由其左下角坐标表示3一、数学直线在数学上，理想的直线是一条无限小的连续的点数学直线二、光栅平面显示的直线在光栅显示平面上，只能用二维光栅格网上尽可能靠近这条直线的象素点的集合来表示它。每个象素的坐标x和y只能是整数，也就是说相邻象素的坐标值是阶跃的而不是连续的。光栅直线三、直线的扫描转换直线的扫描转换，就是要找出显示平面上最佳逼近理想直线的那些象素的坐标值，并将这些象素置成所要求的颜色。直线的扫描转换4由于一幅图中可能包含成千上万条直线，所以要求绘制算法应该：1、最接近数学上的直线；2、画线速度尽可

2、能的快；3、沿着线段分布的象素应均匀。不均匀的例子如右图，对同样长的线段进行图中的扫描转换，会因为斜率不同，产生的象素个数不相等，这样将导致象素亮度分布不均匀。5缺点：每步都需要一个浮点乘法运算和一个取整运算，所以效率太低。bkxy斜率截距直线方程：k表示斜率，b是y轴截距。给定两个端点P0(x0,y0)和P1(x1,y1)，线段的斜率k和截距b为：)/()(/0101xxyyxyk00 xkyb从起点到终点，x每次增加(或减少)1，用直线方程计算对应的y值，再用SetPixel(x,int(y),color)输出该像素。6数值微分法即DDA法(DigitalDifferentialAnaly

3、zer)，是一种基于直线的微分方程来生成直线的方法。7一、直线DDA算法描述：设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得直线的斜率k：=k=直线的斜率(21)1.可通过计算由x方向的增量x引起y的改变来生成直线：xi+1=xi+x(22)yi+1=yi+y=yi+xk(23)2.也可通过计算由y方向的增量y引起x的改变来生成直线：yi+1=yi+y(24)xi+1=xi+x=xi+y/k(25)式(22)至(25)是递推的。8二、直线DDA算法思想：选定|x2x1|和|y2y1|中较大者作为步进方向(假设|x2x1|较大)，取该方向上的增量为一个象素单位

4、(x=1)，然后利用式(21)计算另一个方向的增量(y=xk=k)。通过递推公式(22)至(25)，把每次计算出的(xi+1，yi+1)经取整后送到显示器输出，则得到扫描转换后的直线。算法实现中还应注意直线的生成方向，以决定x及y是取正值还是负值。究竟用方法1,还是方法2来生成直线？9二、直线DDA算法思想（续）之所以取x2x1和y2y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。100 1 2 3 4 5321Line: P(0, 0)- P(5, 2)举例:线段P0(0,0)和P1(5,2)的DDA方法扫描转换。xint(y+0.4)y+0.4522.0+0.4

5、421.6+0.4311.2+0.4210.8+0.4100.4+0.4000+0.40111给定两个端点P0(x0,y0)和P1(x1,y1)，线段的斜率k和截距b为：)/()(0101xxyyk00 xkyb画线过程从x的左端点x0开始，向x右端点步进，步长=1(像素)，计算相应的y坐标：y=kx+b，取像素点(x,int(y)作为当前点的坐标。计算yi+1=kxi+1+b=k(xi+x)+b=kxi+b+kx=yi+kx当x=1时yi+1=yi+k即：当x每递增1，y递增k(即直线斜率)。（xi,int(yi+0.5)（xi,yi)（xi+1,yi+1)（xi+1,int(yi+1+0.

6、5)？复杂度：？复杂度：加法加法+取整取整121、已知直线的两端点坐标：(x1，y1)，(x2，y2)2、已知画线的颜色：color3、计算两个方向的变化量：x =x2x1y =y2y14、求出两个方向最大变化量的绝对值：steps=max(|x |，|y |)5、计算两个方向的增量(考虑了生成方向)：dx=x /stepsdy=y/steps6、设置初始象素坐标：x=x1,y=y17、用循环实现直线的绘制：for(i=1；i=Math.abs(y1-y0)length=Math.abs(x1-x0);elselength=Math.abs(y1-y0);dx=(float)Math.abs(

7、x1-x0)/length;dy=(float)Math.abs(y1-y0)/length;floatx=x0;floaty=y0;inti=1;while(i=length)SetPixel(x,y,color);x=x+dx;y=int(y+dy);i+;五、DDA算法生成直线的部分JAVA语言程序14DDA算法简单，实现容易；DDA算法与基本算法相比，减少了浮点乘法，提高了效率。但是由于在循环中涉及实型数的运算（x与dx、y与dy用浮点数表示），每一步要进行取整，因此生成直线的速度较慢，不利于硬件实现，因而效率仍有待提高。六、直线DDA算法特点：15算法描述算法的复杂度描述算法实例1：

8、（100，200）和（500，400）的源代码算法实例2：（100，400）和（500，200）的源代码16Bresenham算法1965年提出，在生成直线的算法中，Bresenham算法是最有效的算法。Bresenham算法是一种基于误差判别式来生成直线的方法。17l一、基本思想比较从理想直线到位于直线上方的像素的距离d1和相邻的位于直线下方的像素的距离d2，根据距离误差项的符号确定与理想直线最近的象素。yyk+1yykxkxk+1xP2P1d2d1018图3-3根据误差量来确定理想的像素点假设当前直线上的像素坐标为(xi, yi)，那么下一步需要在列xi+1上确定扫描线y的值。如图3-3所

9、示，对于直线斜率k在01之间的情况，从给定线段的左端点P0(x0, y0)开始，逐步处理每个后续列(x位置)，并在扫描线y值最接近线段的像素上绘出一点。y值要么不变，要么递增值要么不变，要么递增1，可通过比较，可通过比较d1和和d2来来决定。决定。一、基本思想（续）yi+1yyixiXi+1d2d119二、直线描述：Bresenham算法也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。xi+1=xi+1(26)yi+1=yi+k(27)xi+1=xi+x(22)yi+1=yi+y=yi+xk(23)我们首先讨论k

10、=y/x，当0k1且x1x2且y1y2时的Bresenham算法。从DDA直线算法可知这些条件成立时，公式(2-2)、(2-3)可写成：20根据误差项根据误差项d决定决定y是否增是否增1iiiybxkyyd) 1(1（) 1(1) 1(2bxkyyydiii（1221(221byxkddii）) 12(222)(21bxyyxxyddxii设y=y1y0,x=x1x0，则k=y/x，代入上式，得；) 12(2bxyc是常量，与像素位置无关)(21ddxdi令则di的计算仅包括整数运算，其符号与(d1-d2)的符号相同。当di0时，像素(xi1，yi1)与直线上理想位置更接近；当di=0时，两个

11、像素与直线上理想位置一样接近，可约定取(xi1，yi1)。yi+1yyixiXi+1d2d12122对于i+1步，误差参数为：cyxxydiii11122cyxxyddxdiii22)(21)(2)(2111iiiiiiyyxxxydd此时参数C已经消去，且xi+1=xi+1,得：)(2211iiiiyyxydd如果选择右上方像素，即：，则：11iiyyxyddii221iiyy1yddii21xyd 20如果选择右方像素，即：，则：23l决定当前像素点的纵坐标（横坐标）是加1还是不变l决定下一个像素点的决策变量xyddii221yddii21240 1 2 3 4 5321Line: P(0

12、, 0)- P(5, 2)举例:线段P0(0,0)和P1(5,2)的Bresenham方法扫描转换。5d+2(y-x)54d+2y13d+2(y-x)32d+2y312y-x101xdy221100025条件：0k1且x1x21、输入线段的两个端点坐标和画线颜色：x1，y1，x2，y2，color；2、设置象素坐标初值：x=x1，y=y1；3、设置初始误差判别值：d=2y-x；4、分别计算：x=x2-x1、y=y2-y1；5、循环实现直线的生成：for(x=x1；x=0)y=y+1；d=d+2(y-x)；elsed=d+2y；26由于程序中不含实型数运算，因此速度快、效率高，是一种有效的画线算法。四、直线Bresenham算法特点：？复杂度：？复杂度：乘法乘法+加法加法27Bresenham算法描述Bresenham算法的复杂度描述Bresenham算法实例1：（0，0）和（40