资源描述
计算机图形学基础：,基本图形生成算法,直线及圆弧的扫描转换,广东工业大学机电学院图学与数字媒体工程系,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,计算机图形学基础,直线及圆弧的扫描转换,广东工业大学机电学院图学与数字媒体工程系,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,1/58,通常认为，基本二维图形包含点、直线、圆、椭圆、多边形域和字符串等。复杂曲线及各种复杂图形均可由直线段和圆弧来拟合，所以研究直线和圆弧生成算法是二维图形生成技术基础。,2/58,在光栅显示器生成一个对象，实质上是往帧缓冲区对应单元中写入数据；如画一条直线，实质上是发觉最正确迫近直线像素序列、并填入对应颜色过程，这个过程称为直线光栅化，或者称为直线扫描转换。,3/58,“,发觉最正确迫近直线像素序列”就是发觉直线生成算法。不一样算法有不一样效率，但各种算法,关键都是围绕着判别和生成,x,、,y,增量过程和方法（走笔规则）,展开研究。,4/58,通常从以下四方面评价直线扫描转换算法质量：,一、显示像素点应尽可能靠近理想直线，直线要直，走样小；,二、直线端点准确，且绘制无定向性，即以哪一个端点为绘制起点得到线段应重合；,三、直线亮度和色泽要均匀，防止造成视觉上一段亮一段暗感觉。这经过所绘制像素点密度保持均匀来实现；,四、画线速度尽可能快，即算法效率要高。,5/58,直线扫描转换,惯用直线生成算法有逐点比较法、正负法、数值微分法和,Bresenham,算法等。,介绍,逐点比较法,详细介绍,数值微分法,和,Bresenham,算法,。,6/58,算法判断规则,在绘图过程中，画笔每走一步，就要与理想图形进行比较，然后决定下一步走向，用步步迫近方法画出指定起止点间直线段。,直线扫描转换,逐点比较法,7/58,走笔约定,以第一象限为例。当画笔（光标当前位置）位于理想直线上方，则横向走笔，即画笔沿,x,方向移动一个单位；当画笔位于理想直线下方时，则纵向走笔，即画笔沿,y,方向移动一个单位。,直线扫描转换,逐点比较法,8/58,要确定画线时光标移动方向，必须要知道当前光标点与理想直线位置关系。位置关系经过坐标偏差来决定。,以第一象限为例分析逐点比较法偏差计算过程。,直线扫描转换,逐点比较法,9/58,设要绘制直线为,OA,（即理想直线），当前点为,M,，当前点与理想直线相对位置（即点,M,在,OA,上方或下方）用偏差值,正负来判断。,计算公式为：,直线扫描转换,逐点比较法,tan,函数在是单调递增函数，所以,正负表达,b,和,a,大小。,10/58,偏差与走笔关系分析：,当,0,时，角,b,a,，点,M,在理想直线下方，按约定，画笔应向上（,+,y,）走一步；,当,P,0,时，角,b,P,a,，点,M,在理想直线上方或在直线上，按约定，画笔应向右（,+,x,）走一步。,直线扫描转换,逐点比较法,11/58,从计算偏差值公式,可知，分子正负决定,正负，所以将公式简化以下：,直线扫描转换,逐点比较法,12/58,设当前位置为,M,i,（,x,i,，,y,i,），则计算偏差函数为,从偏差函数可知，光标每移动一个点，就要与理想直线终点坐标进行计算、比较，然后确定下一步走笔方向和步长增量，这么绘制直线效率必定会很低，所以要对偏差函数进行简化。,有效方法是利用前一个点偏差来推算下一个点偏差值，这种方法称为,递推法,。,直线扫描转换,逐点比较法,13/58,比如已知前一个点偏差值,F,i,P,0,，说明点在理想直线上方，画笔应该沿,+,x,方向移动一个步长；反之，则应该沿,+,y,向移动一个步长。,开始绘制直线时，光标位于理想直线起点，所以一直有,F,0,=,0,。,直线扫描转换,逐点比较法,14/58,若,F,i,P,0,，表示第,i,点在直线上方，,则有,x,i+,1,x,i,1,（其中,1,为步长）,y,i+,1,y,i,，,第,i,+1,点偏差判别式为：,将递推法用数学方法表示为：,设当前位置为,M,i,（,x,i,，,y,i,），,下一个点位置为,M,i+,1,（,x,i+,1,，,y,i+,1,）,直线扫描转换,逐点比较法,求偏差基本公式：,15/58,将递推法用数学方法表示为：,若,F,i,0,，,表示第,i,点在直线下方，,则有,x,i+,1,x,i,y,i+,1,y,i,1,（其中,1,为步长），,即第,i,+1,点偏差判别式为：,直线扫描转换,逐点比较法,求偏差基本公式：,16/58,直线段,位置,偏差值,F,k,P,0,偏差值,F,k,0,第一象限,走笔,+X,F,k+1,=F,k,-,|,y,A,|,走笔,+Y,F,k+1,=F,k,+,|,x,A,|,第三象限,走笔,-X,走笔,-Y,第二象限,走笔,+Y,F,k+1,=F,k,-,|,x,A,|,走笔,-X,F,k+1,=F,k,+,|,y,A,|,第四象限,走笔,-Y,走笔,+X,各象限判别式,直线扫描转换,逐点比较法,逐点比较法绘制直线,.doc,17/58,【,注,】,递推公式作用：,意义：,简化计算过程，提升效率。,标准：,尽可能以加减法代替乘除法。,方法：,用当前点偏差推算出走笔方向，并计算出下一步偏差；再以画笔当前位置重复上述过程，推算出画笔下一步动作。,18/58,数值微分法（,Digital Differential Analyzer,）,简称,DDA,法，利用直线微分方程生成直线方法。,设直线端点坐标为（,X,0,，,Y,0,）和（,X,1,，,Y,1,），直线参数方程为：,直线扫描转换,数值微分法,19/58,直线扫描转换,数值微分法,DDA,算法原理：因为直线一阶导数是连续，且,x,和,y,是成百分比，所以能够经过在当前位置,(,x,i,y,i,),分别加上两个小增量,H,x,和,H,y,（其中,为无穷小正数）来求出下一个点,(,x,i+1,y,i+1,),坐标。,式中，,i=0,1,2,n-1,，,20/58,直线扫描转换,数值微分法,当精度无限高情况下，绘制出直线无限靠近理想直线。这种理想情况不可能出现（因为设备精度有限）也没必要追求，所以通常增量系数,取值为：,21/58,绘制直线时，要确定一个方向增量为单位增量，即,确定画线基本步进方向,，另一个方向增量由直线斜率决定。,确定基本步进方向依据是理想直线斜率,k,。,通常设：,当直线斜率小于或等于,1,，,x,方向为基本步进方向，即,x=,1,，,y,值由直线斜率决定。,当直线斜率大于,1,，,y,为基本步进方向，即,y=,1,，,x,值由直线斜率决定。,直线扫描转换,数值微分法,22/58,DDA,算法坐标迭代公式：,情况一：当 ，即 时，有：,直线扫描转换,数值微分法,23/58,情况二：当 ，即 时，有：,直线扫描转换,数值微分法,24/58,直线扫描转换,数值微分法,需要注意是：因为在光栅化过程中，绘制点最小单位是,1,，所以对求出,x,i+,1,和,y,i+,1,值需要进行四舍五入。,DDA,算法是一个增量算法，优点是直观、易于实现；,缺点是要做浮点运算和舍入取整，不利于硬件实现。,25/58,直线扫描转换,数值微分法,斜率,1,时，以,y,为基本步进方向，,y,方向每次步进增量为,1,。,26/58,直线扫描转换,数值微分法,void dda_line(float x0,float y0,float x1,float y1),int i,epsl;,float xincre,yincre,x,y;,epsl=max(abs(x1-x0),abs(y1-y0);,xincre=(x1-x0)/epsl;,yincre=(y1-y0)/epsl;,x=x0;,y=y0;,for(i=1;i=epsl;i+),drawPoint(int(x+0.5),int(y+0.5);,/,四舍五入取整,x=x+xincre;,y=y+yincre;,27/58,直线扫描转换,Bresenham,算法,Bresenham,提出直线生成算法基本原理为：在某一计长方向上，每次改变一个单位步长或一个象素单位，另一个方向上是否走步取决于误差项。,计长方向由直线斜率,k,决定。当,0=k1,时，,y,为计长方向。,关键问题是怎样生成误差项判断条件。,28/58,直线扫描转换,中点,Bresenham,算法,中点,Bresenham,算法依据直线斜率截距方程。,设直线斜率为,k,，,截距为,b,；直线斜率、截距方程为：,F(x,y),=y-,kx,b=0,当直线经过端点,P,0,(,X,0,Y,0,),和,P,1,(X,1,Y,1,),时,29/58,直线扫描转换,中点,Bresenham,算法,符号说明：,P,当前点；,M,中点；,P,d,和,P,u,下一步可能位置；,Q,理想直线在,x=x,i,+1,位置上点；,30/58,直线扫描转换,中点,Bresenham,算法,算法说明：,设直线斜率在,01,之间，且位于第一象限。光标走步规则为：每次在,x,方向上加,1,，,y,方向依据误差项判断，或加,1,或加,0,。,31/58,直线扫描转换,中点,Bresenham,算法,误差项判别式结构：,当前点,P,，下一个点可能为,P,d,(,即,y,i+1,=y,i,点,),，可能为,P,u,(,即,y,i+1,=y,i,+1,点,),。,M,为,P,d,与,P,u,中点。,若,M,在,Q,点下方，说明,P,u,点离直线近，则有,y,i+1,=y,i,+1,;,若,M,在,Q,点上方，说明,P,d,点离直线近，则有,y,i+1,=y,i,;,32/58,直线扫描转换,中点,Bresenham,算法,直线方程为：,要判断点,M,与直线位置关系，只需要把,M,坐标代入直线方程，若：,F(x,M,y,M,)=,0,，即点,M,在直线上；,F(x,M,y,M,),0,，即点,M,在直线上方；,F(x,M,y,M,),0,，即点,M,在直线下方；,33/58,直线扫描转换,中点,Bresenham,算法,点,M,与点,Q,误差项,d,判别式推导：,当,d,i,=0,时，,M,在直线上方或在直线上，,P,d,(,即,y,i+1,=y,i,点,),为下一个点。,依据递推思想，推导出,d,i,与,d,i+1,关系。,34/58,直线扫描转换,中点,Bresenham,算法,当,d,i,=0,时，,x,i,+1,=,x,i,+1;,y,i,+1,=,y,i,;,则有,d,初值：绘制直线时，光点最初在直线起点,P,0,(,x,0,y,0,),处，可推导出：,d,0,=0.5-,k,36/58,直线扫描转换,中点,Bresenham,算法,直线斜率,k=dy/dx,，将斜率带入判别式：,当,d,i,=0,时，则有,d,初值：,d,i,正负决定下一个点位置，与,d,i,详细数值无关，所以，统一以,2,dx,H,d,i,替换,d,i,，以简化判别式。,37/58,直线扫描转换,中点,Bresenham,算法,当,d,i,=0,时，则有,d,初值：,所以在代码中最终用到判别式为：,38/58,直线扫描转换,中点,Bresenham,算法,绘制点,(,x,y,),yes,no,39/58,直线扫描转换,中点,Bresenham,算法,上述推导中点,Bresenham,算法绘制直线判别式适合用于直线斜率在,01,之间情况。,观察例,mid_bresenham.cpp,绘制斜率在,01,之间直线和斜率大于,1,直线。,当直线大于,1,时，可无须重新推导判别式，只需交换,x,和,y,规则。,bresenham.cpp,40/58,直线扫描转换,Bresenham,算法,中点,Bresenham,算法误差项判别式需要用到直线斜率，改进后,Bresenham,算法，思绪保持不变，对误差项判别式进行简化。,Bresenham,算法直接比较距离,t,和,s,大小，来确定下一个绘制像素。,41/58,推导、简化后得到误差项判别式为：,当,d,i,=0,时，,x,i,+1,=,x,i,+1;,y,i,+1,=,y,i,+1;,有,直线扫描转换,Bresenham,算法,当,d,i,1,时，该变量取值,1,；当斜率,=1,时，该变量取值,0,。,直线扫描转换,Bresenham,算法,44/58,圆扫描转换,给出圆心,(,x,c,y,c,),和半径,r,，逐点绘制圆方式有：,一、利用直角坐标方程,利用直角坐标方程绘制圆弧思绪清楚，但计算包括开方运算，计算量大。更大缺点是，因为,y,不是,x,线性函数，所以，当,x,取值从,0,到,r,均匀递增时，,y,值改变极不均匀，尤其当,x,靠近,r,时，绘制出来圆会出现较大间断。,45/58,圆扫描转换,二、利用圆参数方程,利用参数方程绘制圆弧能够克服直角坐标方程画圆弊端。参数为圆周角，当圆周角按固定增量改变时，能取得均匀分布在圆周上点。,46/58,圆扫描转换,不过，利用圆参数方程绘制圆弧有两个严重缺点：,一、每次求点坐标都需要计算三角函数，计算量大，效率低。,二、,t,增量大小与半径相关。如，若,t,取某一定值，当半径很小时，计算出来像素可能会重合（相邻像素,x,和,y,增量都不于,1,）；而当半径较大时，有可能会造成圆弧出现断开现象（相邻像素,x,和,y,增量过大）。,观察例程“参数方程画圆”,47/58,圆扫描转换,八分法画圆,圆心位于原点圆有四条对称轴线：,若已知圆周上任意一点，能够利用圆对称性得到另外七个点坐标，从而得到整个圆转换扫描像素集。,48/58,圆扫描转换,八分法画圆,drawPoint(xc+x,yc+y);,/,画点,A,drawPoint(xc-x,yc+y);,/,画点,A7,drawPoint(xc+x,yc-y);,/,画点,A3,drawPoint(xc-x,yc-y);,/,画点,A4,drawPoint(xc+y,yc+x);,/,画点,A1,drawPoint(xc-y,yc+x);,/,画点,A2,drawPoint(xc+y,yc-x);,/,画点,A6,drawPoint(xc-y,yc-x);,/,画点,A5,49/58,圆扫描转换,中点,Bresenham,算法,中点,Bresenham,法求圆弧上点思绪与直线绘制相同。,考虑圆心在原点，位于图示区域八分之一圆弧。,中点,Bresenham,画圆算法按照从点,(0,0),到点,顺时针确定最正确迫近理想圆弧像素序列。,50/58,圆扫描转换,中点,Bresenham,算法,算法基本原理：,x,为基本步进方向。每一次沿,x,方向走一步，,y,方向坐标或减,1,，或减,0,。,当前点为,P,，下一步中点为,M,。假如点,M,在圆内，则,Pu,为下一个点，即,y,方向坐标减,0,；假如点,M,在圆外，则,Pd,为下一个点，即,y,方向坐标减,1,。,51/58,圆扫描转换,中点,Bresenham,算法,设当前点为,P(,x,i,y,i,),，则有点,M(,x,i,+1,y,i,-0.5),。,结构误差项判别式：,若,d,i,0,，下一个点为,P,u,(,x,i,+1,y,i,),；,不然下一个点为,P,d,(,x,i,+1,y,i,-1),；,52/58,圆扫描转换,中点,Bresenham,算法,误差项判别式递推公式：,当,d,i,=0,时，此时有,x,i,+1,=,x,i,+1,，,y,i,+1,=,y,i,-1,53/58,圆扫描转换,中点,Bresenham,算法,误差项初值：,开始绘制圆弧第一个为理想圆弧上,P,0,(0,R,),点，所以有判别项初值为：,为防止做浮点运算，用,1,取代,1.25,。造成误差项初值有,0.25,误差。因为绘制圆弧以一个像素为基本单位，,0.25,舍去不会影响下一个点误差项计算，所以初值为：,54/58,圆扫描转换,中点,Bresenham,算法,void bresenham_circle(int xc,int yc,int r),int x=0,y=r,d;,d=1-r;,while(x=y),drawPoint(xc+x,yc+y);,if(d0),d+=2*x+3;,else,d+=2*(x-y)+5;y-;,x+;,55/58,圆扫描转换,中点,Bresenham,算法,在第一象限,y,=,x,到,y,=0,区域，以,y,为基本走步方向，即,y,i,+1,=,y,i,-1,，,x,坐标依据中点与理想圆弧位置关系，或加,1,或加,0,。,56/58,圆扫描转换,中点,Bresenham,算法,决定,x,坐标增量标准是：当下一步中点,M,(,xi,+0.5,yi,-1),在圆周上或在圆外，即误差项,则,x,坐标增量为,0,，下一个点坐标为,(,x,i,y,i,-1),；,不然,x,坐标增量为,1,，下一个点坐标为,(,x,i,+1,y,i,-1),。,57/58,圆扫描转换,中点,Bresenham,算法,绘制整圆方法通常可利用中点,Bresenham,画圆算法结合八分法实现。利用中点,Bresenham,画圆算法求出第一象限,x,=,y,到,x,=0,八分之一区域内点，利用八分法求出其余区域内点。,例：,brescircle.cpp,58/58,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
