计算机图形学-基本图形生成算法-图形的扫描转换

第三章基本图形生成算法

图形地扫描转换基本图形生成算法图元扫描转换直线段扫描转换圆弧扫描转换实区域填充光栅图形点地表示…(x,y)坐标地址线表一D表示显示屏幕二D表示像素由其左下角坐标表示光栅图形点地表示地址=(xmax-xmin)*(y-ymin)+(x-xmin)+基地址xyxmaxxminymaxymin每行像素点数行数行位置(x,y)光栅图形点地表示Address(x,y)=(xmax-xmin)*(y-ymin)+(x-xmin)+基地址=k一+k二y+xAddress(x±一,y)=k一+k二y+(x±一)=Address(x,y)±一Address(x,y±一)=k一+k二(y±一)+x=Address(x,y)±k二Address(x±一,y±一)=k一+k二(y±一)+(x±一)=Address(x,y)±k二±一对像素连续寻址时,如何减少计算量？增量法地优点？直线段扫描转换假设像素间均匀网格,整数型坐标系,直线段斜率零<m<一X方向每次迭代都增一,y方向不一定对m＞一,x,y互换直线段地扫描转换算法直线地扫描转换确定最佳逼近于该直线地一组象素按扫描线顺序,对这些象素行写操作三个常用算法:一数值微分法（DDA）二点画线法三Bresenham算法。数值微分(DDA)法(一/五)已知线段端点:P零(x零,y零),P一(x一,y一)直线方程y=kx+b{(xi,yi)},i=零,….n.浮点数取整:yi=round(yi)=(int)(yi+零.五)用到浮点数地乘法,加法与取整运算数值微分(DDA)法(二/五)增量算法yi+一=kxi+一+b=k(xi+一)+b=yi+k(xi,yi)→(xi+一,yi+k)缺点:有浮点数取整运算不利于硬件实现效率低仅适用于k≤一地情形:x每增加一,y最多增加一。当k一时,需要把x,y互换。数值微分(DDA)法(三/五)digitaldifferentialanalyzer基本思想用数值方法解微分方程dx/dt=xdy/dt=yxn+一=xn+єxyn+一=yn+єy如何选取є？选取є地原则:使零.五≤|єx|,|єy|≤一数值微分(DDA)法(四/五)对称地DDA取є=二-n使二n-一≤max(|x|,|y|)≤二n简单地DDA取є=一/max(|x|,|y|)使є|x|,є|y|必有一个是单位步长x为最大时,єx=一,єx=ky为最大时,єy=一,єy=一/k数值微分(DDA)法(五/五)缺点:浮点数运算不易硬件实现点画线法（一/四）问题:判断距离理想直线最近地下一个象素点已知:线段两端点(x零,y零),(x一,y一)直线方程:F(x,y)=ax+by+c=零a=y零-y一b=x一-x零c=x零y一-x一y零M如何判断M点在Q点上方还是在Q点下方？MP一P二P直线上方点:F(x,y)＞零直线下方点:F(x,y)＜零构造判别式:d=F(M)=F(Xp+一,Yp+零.五)由d＞零,d＜零可判定下一个象素(Xp+一,Yp+零.五)点画线法（二/四）分两种情形考虑再一下个象素地判定:若d≥零,点M在直线上方,取正右方象素P一(Xp+一,Yp)再下一个象素地判别式为:d一=F((Xp+一)+一,Yp+零.五)=a(Xp+二)+b(Yp+零.五)+c=d+ad地增量为a若d＜零,点M在直线下方,取右上方象素P二(Xp+一,Yp+一)再下一个象素地判别式为:d二=F((Xp+一)+一,(Yp+一)+零.五)=a(Xp+二)+b(Yp+一.五)+c=d+a+bd地增量为a+bMP一P二MP一P二d地初始值d零=F(X零+一,Y零+零.五)=F(X零,Y零)+a+零.五b=a+零.五b用二d代替d后,d零=二a+bd地增量都是整数优点:只有整数运算,不含乘除法可用硬件实现因(X零,Y零)在直线上,所以F(X零,Y零)=零点画线法（四/四）Bresenham画线算法（一/一一）使用最广泛与点画线法地思想类似由误差项符号决定下一个象素取正右方像素还是右上方像素Bresenham画线算法（二/一一）基本思想比较从理想直线到位于直线上方地像素地距离d一与相邻地位于直线下方地像素地距离d二根据距离误差项地符号确定与理想直线最近地象素Bresenham画线算法（三/一一）最大位移方向每次走一步k<一时,x为最大位移方向y方向走步与否取决于误差e值地大小误差计算初值:e零=y/x当e≥零.五时,最接近P二(xi+一,yi+一)y方向走一步当e<零.五时,最接近P一(xi+一,yi)y方向不走步eP一P二Pe’eP一P二Pe’Bresenham画线算法（四/一一）为方便与零比较,设e=e-零.五e零=y/x-零.五当e≥零时,最接近P二(xi+一,yi+一)y方向走一步当e<零时,最接近P一(xi+一,yi)y方向不走步有除法,不宜硬件实现eP一P二Pe’eP一P二Pe’Bresenham画线算法（五/一一）设e=e×二x,不影响判断地准确e零=二y-x当e≥零时,最接近P二(xi+一,yi+一)y方向走一步当e<零时,最接近P一(xi+一,yi)y方向不走步eP一P二Pe’eP一P二Pe’Bresenham画线算法（六/一一）下一步误差地计算当e≥零时,y方向走一步e’=二y/x-一=e+y/x-一e’=e+二y-二x当e<零时,y方向不走步e’=二y/x=e+y/xe’=e+二yeP一P二Pe’eP一P二Pe’Bresenham画线算法（七/一一）先确定最大位移方向确定误差e地计算方法,并根据e确定在非最大位移方向上如何走步Bresenham画线算法（八/一一）先确定最大位移方向|k|<一时,x为最大位移方向|k|>一时,y为最大位移方向增一还是减一,取决于直线所在象限x≥零时,s一=一,否则s一=-一y≥零时,s二=一,否则s二=-一yxx++y++x增一x增一ox++y++x++y--x--y++x--y--y增一x减一y增一y减一x减一y减一(x零,y零)Bresenham画线算法（九/一一）确定误差e地计算方法,并根据e确定在非最大位移方向上如何走步误差初值地计算|k|<一时,e=二|y|-|x||k|>一时,e=二|x|-|y|Bresenham画线算法（一零/一一）确定误差e地计算方法,并根据e确定在非最大位移方向上如何走步e<零,不走步|k|<一时,x=x+s一,e=e+二|y||k|>一时,y=y+s二,e=e+二|x|e≥零,走步|k|<一时,x=x+s一,y=y+s二,e=e+二|y|-二|x||k|>一时,y=y+s二,x=x+s一,e=e+二|x|-二|y|Bresenham画线算法（一一/一一）优点整数运算,速度快精度高乘二运算可用移位实现,适于硬件实现圆弧地扫描转换圆地八对称只考虑第二个八分圆假设圆心在原点x二+y二=R二yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oR圆弧地扫描转换两种直接离散生成方法离散点开方运算离散角度三角函数运算缺点:计算量大所画像素位置间地间距不一致点画圆法（一/二）F(X,Y)=X二+Y二-R二=零点M=(Xp+一,Yp-零.五)当F(M)＜零时,M在圆内,P一距离圆弧近,取P一当F(M)＞零时,M在圆外,P二距离圆弧近,取P二点画圆法（二/二）若d<零,取P一为下一象素,再下一象素地判别式为

若d>=零,取P二为下一象素,再下一象素地判别式为初始象素是（零,R）,判别式d地初值为P一(Xp+一,Yp)P二(Xp+一,Yp-一)使用e=d-零.二五代替de零=一-RDDA画圆法（一/三）圆地方程:f(x,y)=x二+y二-R二=零全微分:df(x,y)=二xdx+二ydy=零微分方程:dy/dx=-x/y递推方程:(yn+一-yn)/(xn+一-xn)=-єxn/єynxn+一-xn=єynyn+一-yn=-єxn实际画出地曲线不是圆,而是螺旋线,为什么？DDA画圆法（二/三）将递推公式写成矢量形式:构造一个行列式值为一地矩阵对应地圆方程递推关系为xn+一=xn+єynyn+一=-єxn+(一-є二)yn=yn-єxn+一DDA画圆法（三/三）针对不同象限及顺逆时针画圆,赋给є适当地符号є不同,圆形状不同,є大近似椭圆Bresenham画圆算法（一/七）顺时针画第一四分圆,下一步选择哪个点？基本思想:通过比较像素与圆地距离方来避免开方运算下一像素有三种可能地选择mH=|(xi+一)二+yi二-R二|mD=|(xi+一)二+(yi-一)二-R二|mV=|xi二+(yi-一)二-R二|选择像素地原则使其与实际圆弧地距离方达到最小(xi,yi)HPi①VD(xi+一,yi)(xi,yi-一)(xi+一,yi-一)②③④⑤Bresenham画圆算法（二/七）圆弧与点(xi,yi)附近光栅网格地相关系有五种右下角像素D(xi,yi)与实际圆弧地近似程度i=(xi+一)二+(yi-一)二-R二当i<零时,D在圆内,①②当i>零时,D在圆外,③④当i=零时,D在圆上,⑤(xi,yi)HPi①VD(xi+一,yi)(xi,yi-一)(xi+一,yi-一)②③④⑤Bresenham画圆算法（三/七）当i<零时,D在圆内,①②情形①,选mH,mD最小者d=mH-mD=|(xi+一)二+yi二-R二|-|(xi+一)二+(yi-一)二-R二|=(xi+一)二+yi二-R二+(xi+一)二+(yi-一)二-R二=二(i+yi)-一若d<零,则选H若d>零,则选D若d=零,则选H情形②也适用(xi,yi)HPi①VD(xi+一,yi)(xi,yi-一)(xi+一,yi-一)②Bresenham画圆算法（四/七）当i>零时,D在圆外,③④情形③,选mv,mD最小者d’=mD-mV=|(xi+一)二+(yi-一)二-R二|-|xi二+(yi-一)二-R二|=(xi+一)二+(yi-一)二-R二+xi二+(yi-一)二-R二=二(i-xi)-一若d’<零,则选D若d’>零,则选V若d’=零,则选D情形④也适用(xi,yi)HPiVD(xi+一,yi)(xi,yi-一)(xi+一,yi-一)③④Bresenham画圆算法（五/七）当i=零时,D在圆上,⑤按d判别,有d>零,应选D按d’判别,有d’<零,应选D(xi,yi)HPiVD(xi+一,yi)(xi,yi-一)(xi+一,yi-一)⑤Bresenham画圆算法（六/七）当i<零时,若d≤零,选H若d>零,选D当i>零时,若d’≤零,选D若d’>零,选V当i=零时,选D(xi,yi)HPiVD(xi+一,yi)(xi,yi-一)(xi+一,yi-一)Bresenham画圆算法（七/七）判别式地递推关系当取H(xi+一,yi)时i+一=(xi+一+一)二+(yi-一)二-R二=i+二(xi+一)+一当取V(xi,yi-一)时i+一=(xi+一)二+(yi-一-一)二-R二=i-二(yi-一)+一当取D(xi+