《计算机图形学直线生成课件.ppt》由会员分享，可在线阅读，更多相关《计算机图形学直线生成课件.ppt（28页珍藏版）》请在三一办公上搜索。
1、第,2,章,基本光栅图形生成技术,显示器是由离散像素组成的矩阵，在绘制具有连续性质的,直线、曲线或区域等基本图形时，需要确定最佳逼近它们的像,素，这个过程称为,光栅化,。,虽然几乎所有的程序设计语言都提供了线、圆弧、填充等,的绘制函数，但只有学习了基本图形的生成原理和算法，才能,超越具体程序设计语言的限制，满足用户的特殊绘图要求。,假定,，编程语言提供了一个显示像素函数：,SetPixel(x,y,color);,其中，,x,和,y,为像素的位置坐标，,color,为像素的颜色。,1,2.1,光栅图形中点的表示,(,x,y,),坐标,地址线性表,显示屏幕,1D,表示,2D,表示,像素由其左下角
2、坐标表示,2,2.2,直线的扫描转换,一、数学直线,二、光栅平面显示的直线,三、直线的扫描转换,在数学上，理想的,在光栅显示平面上，,直线的扫描转换，,直线是一条没有宽度的,只能用二维光栅格网上尽,就是要找出显示平面上,、由无数个无限小的连,可能靠近这条直线的象素,最佳逼近理想直线的那,续的点构成的集合。,点的集合来表示它。每个,些象素的坐标值，并将,象素的坐标,x,和,y,只能是整,这些象素置成所要求的,颜色。,数，也就是说相邻象素的,坐标值是阶跃的而不是连,续的。,直线的扫描转换,数学直线,光栅直线,3,2.3,线的生成算法,由于一幅图中可能包含成千上万条直线，所以要求绘,制算法应该：,1
3、,、最接近数学上的直线；,2,、画线速度尽可能的快；,3,、沿着线段分布的象素应均匀。,不均匀的例子,如右图，对同样长,的线段进行图中的,扫描转换，会因为,斜率不同，产生的,象素个数不相等，,这样将导致象素亮,度分布不均匀。,4,?,直线的生成算法,斜率截距直线方程：,y,?,kx,?,b,k,表示斜率，,b,是,y,轴截距。,给定两个端点,P,0,(x,0,y,0,),和,P,1,(x,1,y,1,),，,线段的斜率,k,和截距,b,为：,k,?,?,y,/,?,x,?,(,y,1,?,y,0,),/(,x,1,?,x,0,),b,?,y,0,?,k,?,x,0,从起点到终点，,x,每次增加
4、,(,或减少,)1,，用直线方程计算对应的,y,值，再用,SetPixel(x, int(y),color),输出该像素。,?,复杂度：,乘法,+,加法,+,取整,缺点,：每步都需要一个浮点乘法运算和一个取整运算，所以效率太低。,5,?,数值微分,(DDA),法,数值微分法即,DDA,法,(Digital Differential Analyzer),，是一种,基于直线的微分方程来生成直线的方法。,6,一、直线,DDA,算法描述：,设,(x,1,，,y,1,),和,(x,2,，,y,2,),分别为所求直线的起点和终点坐标，由,直线的微分方程得直线的斜率,k,：,= k =,直线的斜率,(2,1
5、),1.,可通过计算由,x,方向的增量,x,引起,y,的改变来生成直线：,x,i+1,=x,i,+,x,y,i+1,=y,i,+,y=y,i,+,x,k,(2,2),(2,3),2.,也可通过计算由,y,方向的增量,y,引起,x,的改变来生成直线：,y,i+1,=y,i,+,y,(2,4),x,i+1,=x,i,+,x=x,i,+,y/k,(2,5),7,式,(2,2),至,(2,5),是递推的。,二、直线,DDA,算法思想：,选定,|x,2,x,1,|,和,|y,2,y,1,|,中较大者作为步进方向,(,假设,|x,2,x,1,|,较大,),，取该方向上的增量为一个象素单位,(,x=1),，
6、然后利用,式,(2,1),计算另一个方向的增量,y=,x,k=k),。通过递推公式,究竟用方法,1,还是方法,(,2,来生成直线？,(2,2),至,(2,5),，把每次计算出的,(x,i+1,，,y,i+1,),经,取整,后送到显示,为什么？,器输出，则得到扫描转换后的直线。,算法实现中还应注意直线的生成方向，以决定,x,及,y,是,取正值还是负值。,8,二、直线,DDA,算法思想（续）,之所以取,x,2,x,1,和,y,2,y,1,中较大者作为步进方向，是考虑,沿着线段分布的象素应均匀，这在下图中可看出。,9,举例,:,线段,P,0,(0,0),和,P,1,(5,2),的,DDA,方法扫描转
7、换。,x int(y+0.4) y+0.4,0 0 0+0.4,1 0 0.4+0.4,2 1 0.8+0.4,3 1 1.2+0.4,0 1 2 3 4 5,Line: P,0,(0, 0)- P,1,(5, 2),3,2,1,4 2 1.6+0.4,5 2 2.0+0.4,10,三、,直线,DDA,算法的思考,？复杂度：,加,法,+,取整,给定两个端点,P,0,(x,0,y,0,),和,P,1,(x,1,y,1,),，线段的斜率,k,和截距,b,为：,k,?,(,y,1,?,y,0,),/(,x,1,?,x,0,),b,?,y,0,?,k,?,x,0,画线过程从,x,的左端点,x,0,开始
8、，向,x,右端点步进，步长,=1(,像素,),，计算相应的,y,坐标：,y=kx+b,，取像素点,(x, int(y),作为当前点的坐标。,计算,y,i+1,= kx,i+1,+b=k(x,i,+,?,x)+b= kx,i,+b+k,?,x,= y,i,+k,?,x,当,?,x =1,时,y,i+1,= y,i,+k,（,i+1,int(,i+1,+0.5,),x,y,即：当,x,每递增,1,，,y,递增,k(,即直线斜率,),。,（,i,i),x,y,（,i+1,i+1),x,y,（,i,int(,i,+0.5,),x,y,11,四、,直线,DDA,算法的实现,1,、已知直线的两端点坐标：,
9、(x1,，,y1),，,(x2,，,y2),2,、已知画线的颜色：,color,3,、计算两个方向的变化量：,x =x2,x1,y =y2,y1,4,、求出两个方向最大变化量的绝对值：,steps=max(|,x |,，,|,y |),5,、计算两个方向的增量,(,考虑了生成方向,),：,dx =,x / steps,dy =,y / steps,6,、设置初始象素坐标：,x=x1,y=y1,7,、用循环实现直线的绘制：,for(i=1,；,i=steps,；,i+),SetPixel(x,，,int( y+,y ),color),；,x=x+ dx,；,y=y+ dy,；,12,五、,DDA
10、,算法生成直线的部分,JA,V,A,语言程序,float dx, dy;,int,length;,if (Math.abs(x1-x0)=Math.abs(y1-y0),length=Math.abs(x1-x0);,else,length=Math.abs(y1-y0);,dx = (float)Math.abs(x,1,-x,0,)/length;,dy = (float) Math.abs(y,1,-y,0,)/length;,float,x= x,0,;,float,y= y,0,;,int i=1;,while(i=length),SetPixel (x, y, color);,x=
11、x+dx;,y=int (y+dy );,i+;,?,13,六、直线,DDA,算法特点：,DDA,算法简单，实现容易；,DDA,算法与基本算法相比，减少了浮点乘法，提高了效率。,但是由于在循环中涉及实型数的运算（,x,与,dx,、,y,与,dy,用浮点,数表示），每一步要进行取整，因此生成直线的速度较慢，,不利于硬件实现，因而效率仍有待提高。,14,实验报告二,算法,?,算法描述,?,算法的复杂度描述,?,算法实例,1,：,（,100,，,200,）和（,500,，,400,）,的源代码,?,算法实例,2,：,（,100,，,400,）和（,500,，,200,）,的源代码,15,?,Bres
12、enham,算法,Bresenham,算法,1965,年提出，在生成直线的算法中，,Bresenham,算法是最有效的算法。,Bresenham,算法是一种,基于误差判别式来生成直线的方法。,16,?,一、基本思想,比较从理想直线到位于直线上方的像素的距离,d1,和相邻的位于直线下方的像素的距离,d2,，根据距离误,差项的符号确定与理想直线最近的象素。,y,y,k,+,1,y,y,k,0,P,2,P,P,1,x,k,x,k,+,1,d,2,d,1,x,17,一、基本思想（续）,如图,3-3,所示，对于直线斜率,k,在,01,之间的情况，从给定线段,的左端点,P,0,(x,0, y,0,),开始
13、，逐步处理每个后续列,(,x,位置,),，并在扫,描线,y,值最接近线段的像素上绘出一点。,y,i,+1,y,y,i,假设当前直线上的像素坐标为,(x,i, y,i,),，那么下一步需要在列,x,i,+1,上确定扫描线,y,的值。,P2,d,2,P,d,1,y,值要么不变，要么递增,1,，可通过比较,d1,和,d2,来,决定。,x,i,X,i,+1,P1,图,3-3,根据误差量来确定理想的像素点,18,二、直线,Bresenham,算法描述：,Bresenham,算法也是采用递推步进的办法，令每次最大变,化方向的坐标步进一个象素，同时另一个方向的坐标依据误差,判别式的符号来决定是否也要步进一个
14、象素。,我们首先讨论,k=,y/,x,，当,0k1,且,x1x2,且,y1y2,时的,Bresenham,算法。从,DDA,直线算法可知这些条件成立时，,公式,(2-2),、,(2-3),可写成：,x,i+1,=x,i,+,x,(2,2),x,i+1,=x,i,+1,y,i+1,=y,i,+,k,(2,6),(2,7),y,i+1,=y,i,+,y=y,i,+,x,k,(2,3),19,根据误差项,d,决定,y,是否增,1,y,i,+1,y,P2,d,2,d,1,?,y,?,y,i,?,(,k,（,x,i,?,1,),?,b,),?,y,i,d,1,?,d,2,?,2,k,(,x,i,?,1,
15、）,?,2,y,i,?,2,b,?,1,d,2,?,(,y,i,?,1,),?,y,?,y,i,?,1,?,(,k,（,x,i,?,1,),?,b,),y,i,x,i,P,d,1,X,i,+1,P1,设,y=y,1,y,0,x=x,1,x,0,，,则,k=,y/,x,，代入上式，得；,?,x,(,d,1,?,d,2,),?,2,?,?,y,?,x,i,?,2,?,?,x,?,y,i,?,2,?,?,y,?,?,x,(,2,b,?,1,),c,?,2,?,y,?,?,x,(,2,b,?,1,),令,d,i,?,?,x,(,d,1,?,d,2,),则,d,i,的计算仅包括整数运算，其符号与,(d,
16、1,-d,2,),的符号相同。,?,当,d,i,0,时，像素,(x,i,1,，,y,i,),与直线上理想位置更接近，应取右方像素；,?,当,d,i,0,时，像素,(x,i,1,，,y,i,1,),与直线上理想位置更接近；,?,当,d,i,=0,时，两个像素与直线上理想位置一样接近，可约定取,(x,i,1,，,y,i,1,),。,20,是常量，与像素位置无关,思考问题,?,决策变量,d,i,与,0,之间的大小关系,?,如何确定下一个像素点的决策变量,d,i+1,?,是否可以找出,d,i,与,d,i+1,的关系式,?,如何确定第一个决策变量,d,i,21,d,i,?,?,x,(,d,1,?,d,2
17、,),?,2,?,?,y,?,x,i,?,2,?,?,x,?,y,i,?,c,对于,i+1,步，误差参数为：,d,i,?,1,?,2,?,?,y,?,x,i,?,1,?,2,?,?,x,?,y,i,?,1,?,c,d,i,?,1,?,d,i,?,2,?,?,y,?,(,x,i,?,1,?,x,i,),?,2,?,?,x,?,(,y,i,?,1,?,y,i,),此时参数,C,已经消去，且,x,i+1,=x,i,+1,得：,d,i,?,1,?,d,i,?,2,?,?,y,?,2,?,?,x,?,(,y,i,?,1,?,y,i,),如果选择右上方像素，即：,y,，则：,i,?,1,?,y,i,?,1
18、,如果选择右方像素，即：,y,i,?,1,?,y,i,，则：,d,i,?,1,?,d,i,?,2,?,y,?,2,?,x,d,i,?,1,?,d,i,?,2,?,y,对于每个整数,x,，从线段的坐标端点开始，循环的进行误差量的计,算。假设直线的初始端点恰好是其象素点的坐标，即满足：,y,0,=k,x,0,+b,在起始像素,(x,0,，,y,0,),的第一个参数,d,0,为,：,d,0,?,2,?,y,?,?,x,22,决策变量,d,i,的作用,?,决定当前像素点的纵坐标（横坐,标）是加,1,还是不变,?,决定下一个像素点的决策变量,d,i+1,的表达式,d,i,?,1,?,d,i,?,2,?,
19、y,?,2,?,x,OR,d,i,?,1,?,d,i,?,2,?,y,23,举例,:,线段,P,0,(0,0),和,P,1,(5,2),的,Bresenham,方法扫描转换。,x d,0,1 2,y,-,x,1,2 d+2,y,3,3,d+2,(y,-,x),3,4 d+2,y,1,5,d+2,(y,-,x),5,y,0,0,0,1,1,Line: P,(0, 0)- P,1,(5, 2),3,2,1,0 1 2 3 4 5,2,2,24,三、,Bresenham,画线算法的实现,条件：,0k1,且,x,1,x,2,1,、输入线段的两个端点坐标和画线颜色：,x,1,，,y,1,，,x,2,，,
20、y,2,，,color,；,2,、设置象素坐标初值：,x=x,1,，,y=y,1,；,3,、设置初始误差判别值：,d=2y,-,x,；,4,、分别计算：,x=x,2,-x,1,、,y=y,2,-y,1,；,5,、循环实现直线的生成：,for(x=x,1,；,x=x,2,；,x+), setPixel(x,y,color),；,if(d=0),y=y+1,；,d=d+2(y,-,x),；,else,d=d+2y,；,25,四、直线,Bresenham,算法特点：,由于程序中不含实型数运算，因此速度快、效率高，是一种,有效的画线算法。,？复杂度：,乘,法,+,加法,26,实验报告三,Bresenh
21、am,算法,?,Bresenham,算法描述,?,Bresenham,算法的复杂度描述,?,Bresenham,算法实例,1,：,（,0,，,0,）和（,400,，,50,）的源代码,?,Bresenham,算法实例,2,：,（,0,，,200,）和（,500,，,0,）的源代码,27,实验报告四（选做）,?,在生成直线的算法中，我们先后学习了普,通直线生成算法、数值微分法（,DDA,）算,法和,Bresenham,算法。写写学习心得和学,习所得。,?,注：如果你在课堂或课后学习了以上提到,的三种算法（尤其是后两种算法），无论,学习效果如何或是自己对三种算法理解程,度是深是浅，希望选做实验报告四，为本,门课程做一个相对圆满的总结。,28,
