直线和直线图形2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,直线和直线图形2,第二章 直线,在光栅显示器的荧光屏上生成一个图形，实质上是往帧缓存存放器的相应单元中填入数据。,计算机生成图形时，需要绘制大量的直线，设计快速有效的直线绘制算法意义重大。,一般来讲，水平、垂直直线和对角线能准确地画出，但要准确绘制一条斜线并不容易。,在光栅显示器上画x1,y1到x2,y2的直线，实质上是确定最正确逼近直线的象素序列。,2,1生成的直线要直,选择最靠近直线的象素点来逼近直线。,理想绘制效果,1,、绘制直线的要求,实际绘制效果,3,2起点和终点要准确：,在绘制直线的过程中由于受精度的影响，直线的终点与原终点有一个累积误差，导致直线的终点不准。,4,3直线的粗细要均匀,由于选点不均匀，造成直线粗细不均匀，直观上反映出直线的亮度不均匀。,5,4直线宽度应该与线段的长度和斜率无关：要取得均匀的线段宽度，应该保持每单位长度的点数是常数。,5显示线段的速度应快：直线的绘制是生成计算机图形的根底，其绘制速度直接影响到计算机图形生成的效率，常采用硬件来实现。,6,2,、直线的方程,假设其始坐标和终点坐标分别为：,那么斜率为,截距为,(1),(2),(3),直线的绘制算法以直线方程1、2和3式为根底。,直线的点斜式方程为：,对任何沿直线给定的,x,的增量,x,，对应的,y,增量,y,：,ymx,同样，对应于,y,的增量,y,，,x,的增量,x,为：,x(1/m)y,7,3、逐点比较法,1算法的根本思想：,在绘制直线的过程中，每绘制一个点，就与原直线进展比较，根据比较的结果断定下一步的走向，这样一步一步逼近直线。保证要绘制的点尽可能的靠近直线而不发生远离直线的趋向。,8,2绘制思路,由当前点到下一个点的走法是只在X方向或Y 方向走一步。,计算当前点偏差：,=,tg,-tg,K1,K2,1),=0,，点在直线上；,2),0,，点在直线上方，下一步走,X,方向；,3),0,，点在直线下方，下一步走,Y,方向。,9,可以简化为,根据 计算出偏差，然后确定下一步的走向。,初始：,那么 =0；,第一步：,第二步：,假定起点为坐标原点偏差计算公式为：,(7,5),A,(0,0),10,偏差递推公式,1 时，走X方向一步，即,2 时，走Y方向一步，即,偏差计算公式为：,11,以上讨论的是起点为原点，X为最大步长方向的情况，对于起点是任意点，最大步长方向为其他情况下的绘制直线的偏差计算和偏差判别，可类似推导。,判别终点的方法：设立计数器，计数取X或Y方向的最大增量值计长方向，在计长方向每走一步，计数器减1，只到计数器值为零为止。,12,2、,DDA,算法,(Digital Differential Analyzer),DDA算法是建立在微分方程的根底上。,由 到 的直线段满足的微分方程为：,13,因此有,那么有,令,有,14,DDA,绘制的直线,1/15,；,15,DDA,绘制直线的算法,if|x,b,-x,a,|y,b,-y,a,|then,计算直线在,y,方向上的增量：,length=|y,b,-y,a,|,else,计算直线在,x,方向上的增量：,length=|x,b,-x,a,|,计算,x,方向的单位增量：,dx=(x,b,-x,a,)/length,计算,y,方向的单位增量：,dy=(y,b,-y,a,)/length,置初值：,x=x,a,，,y=y,a,for i=1 to length do begin,输出点,(trunc(x),trunc(y),计算下一个点坐标,x=x+dx,，,y=y+dy end,end of algorithm,16,3,、,Bresenham,算法,算法的根本思想：每次迭代在增量最大方向上走一步，,另一方向上是否也走，取决于计算出来的点与直线上的点,的误差，根据误差决定是否走一步。即x方向的步长总是1(斜率小于1的情况)，y方向是否有变化，取决于直线的理论值与假设点之间的误差值大小。例如取X方向为最大增量方向，那么有：,其中,1,；,17,绘制的直线时点的选取,y,i,y,i+1,18,偏差计算,设偏差为,当 时，计算的点实际直线上的点在,中点的上方，取,当 0 时，计算的点实际直线上的点在,中点的下方，取,整理后，有,y,i,y,i+1,19,偏差的递推关系,误差,因为,有,偏差初值,0,=,m,20,将乘以2x记为2x，那么同有一样的符号，根据的符号确定象素点的过程仍然正确。此时偏差的表示式做如下变动：,初始误差项：02x 0,2y-x；,积累误差 k+1 km修改为：,k+12x k+1,2x(ky/x,2x k2y,k2y；,如果选取上面的象素点，积累误差还要减去1，修改为：k+12x k+11,k 2y 2x,21,Bresenham,直线生成算法描述,计算,x,和,y,方向的增量：,dx=|x,b,-x,a,|,，,dy=|y,b,-y,a,|,计算递推公式的初值,d,1,:d=2dy-dx,计算两个单位增量：,incr1=2dy,incr2=2(dy-dx),if(x,a,x,b,)then,置起点为,x=x,b,，,y=y,b,，置终点为,x,e,=x,a,y,e,=y,a,else,置起点为,x=x,a,，,y=y,a,，置终点为,x,e,=x,b,，,y,e,=y,b,输出起点,(x,y),while(x,x,e,)do,begin,x=x+1,if(d,0)then d=d+incr1,else y=y+1,，,d=d+incr2,输出点,(x,y),end,end of algorithm,22,总结,前面所介绍的逐点比较法、数值微分法以与,Bresenham算法，它们各有优缺点。因此在使用,不同的图形输出设备时要选用最适合于该设备,的方法，如在绘图仪中多采用逐点比较法，在点,迹技术的显示设备中多用DDA法和Bresenham算法。,23,4,、直线的属性,任何影响图元显示方法的参数称为属性参数。,线段的根本属性有线型、宽度和颜色。,线型：实线、虚线、点线等。,通过设置沿直线路径显示的实线线段的长度和间,距来修改画线算法，产生各种类型的直线。,24,线宽：,线刷子：沿着生成直线时获得的象素点，移动一把具有一定宽度的“刷子来实现。斜率k=1，刷子设置为垂直方向，否那么设置为水平方向,25,线的连接：,一定宽度的折线段时，线段的接头处会出现缺口，典型的处理方式有：尖头，圆头和方头三种,线头：,绘制具有宽度的线段，需要对线头进展处理，典型的线头有下述三种,26,27,第三章 二次曲线,圆也是图形系统中常用的元素。圆可以定义为,所有以距离中心位置 为给定值,r,的点集。,圆的方程为：,利用这个方程，我们可以沿,x,轴，从,到 以单位步长计算对应的,y,值，从而得到圆周上每点的位置。,可以利用圆的对称性：可以先绘制八分之一圆弧，再利用对称性绘制整个圆,28,1,、中点画圆算法,考虑圆心在原点的圆。设函数：,故有 x,y)位于圆边界内,x,y)位于圆边界上,x,y)位于圆边界外,对上述函数在每个取点步骤上，对接近圆周的两个象素,点的中点进展测试来决定取点。,29,考虑一个四分之一圆弧,从x=0到x=y的情况第一象限的上八分之一圆弧，圆的曲率从0变化到-1，在该段弧上的正x方向取单位步长，并确定每一步更接近圆弧的y的位置。,设已经取的点为 ，决策参数为：,以此来判断下一步 的点如何取。,是 还是 。,30,故有,中点位于圆边界内,中点位于圆边界上,中点位于圆边界外,31,递推决策函数,其中 的取值，决定于 的符号。,32,中点画圆,33,圆弧上点的对称关系,只画1/8圆，其余点通过对称关系求得,。,34,象限判别,在进展绘制圆弧曲线时，需要考虑轨迹点所在象限的情况，,因此需要进展象限的判别。对于在坐标轴上的点，需要根,据绘制圆的方向来决定。,A,B,C,D,35,2,、,Bresenham,算法,仍然考虑圆心在原点的一个第一象限的圆弧 。,对于圆弧上的点,p(x,y),，其下一个可选择的点如图。,36,圆弧上点与该二点之间的关系,H、D,全在圆外；,H,在圆外，,D,在圆内；,H,在圆外，,D,在圆上；,H,、,D,全在圆内；,可以计算出这三点到圆心的距离与半径的差：,37,分析：,1当 时，圆弧在D的上方，可以取的点是H或D，,只要看H和D两个点，哪个与圆弧的距离近。,设：,时，,H,点距离圆弧近，,H,为可取的下一个点。,表示了,H,和,D,点到圆弧的距离之差。,时，,H,和,D,点均为可取的下一个点。,时，,D,点距离圆弧近，,D,为可取的下一个点。,当,38,2当 时，圆弧在D的下方，可以取的点是D或V，只要看D和V两个点，哪个与圆弧的距离近。设：,时，,V,点距离圆弧近，,V,为可取的下一个点。,时，,V,和,D,点均为可取的下一个点。,时，,D,点距离圆弧近，,D,为可取的下一个点。,当,3),当 时，,D,点在圆上，取,D,点。,39,3,、多边形逼近法,考虑绘制圆心在(xc,yc)，半径为r的圆，一个第一象限的圆弧。对于内接正多边形顶点Pi(xi,yi)，其幅角为i，那么：,下一个顶点,P,i,+1,坐标为：,只需要计算一次,sin(,),，,cos(,),，就可以递推计算其他顶点，计算一个顶点只需四次乘法。,40,3,、二次曲线参数拟合法,研究二次曲线的参数方程以与通过的型值点构造,二次曲线的参数拟合方法。,二次曲线的参数方程为：,其中 是常数向量，是常数，那么r(t),表示了二次曲线的轨迹。,41,构造二次曲线,二次曲线上的三个型值点 ，当t=0时，过,点，且与 相切，当t=1时，过 点，且与,相切。根据条件，可以建立方程：,42,建立方程组,43,分类,1抛物线,2双曲线,3椭圆弧,44,绘制曲线,(,步长为,0.4),45,绘制曲线,(,步长为,0.2),46,绘制曲线,(,步长为,0.1),47,谢谢欣赏,48,Thank You!,不尽之处，恳请指正！,