第5章习题

计算机图形学基础华东理工大学计算机系·谢晓玲习题5.2/P1495.2用DDA算法、中点Bresenham算法和改进Bresenham算法扫描转换直线段P1P2，其中P1为(0,0)、P2为(8,6)。①DDA算法：已知P1(0,0)、P2(8,6)，则：dx=8,dy=6∵dxdy并且k1∴取Δx=1,Δy=k=6/8=0.75∴xi+1=xi+1,yi+1=yi+0.75ixiyi(xi,yi)00,0(0,0)11,0.75(1,1)22,1.5(2,2)33,2.25(3,2)44,3.0(4,3)55,3.75(5,4)66,4.5(6,5)77,5.25(7,5)88,6.0(8,6)i(xiyi)di(xi+1,yi+1)di+2(dx-dy)di-2dy0(0,0)-4(1,1)-4+4=01(1,1)0(2,1)0-12=-122(2,1)-12(3,2)-12+4=-83(3,2)-8(4,3)-8+4=-44(4,3)-4(5,4)-4+4=05(5,4)0(6,4)0-12=-126(6,4)-12(7,5)-12+4=-87(7,5)-8(8,6)习题5.2/P149②中点Bresenham算法：dx=8,dy=6,2(dx-dy)=4,-2dy=-12,d0=dx-2dy=-4习题5.2/P149③改进Bresenham算法：dx=8,dy=6,2dx=16,2dy=12,e0=-dx=-8i(xiyi)eiei+2dy(xi+1,yi+1)ei-2dx0(0,0)-8-8+12=4(1,1)4-16=-121(1,1)-12-12+12=0(2,1)2(2,1)00+12=12(3,2)12-16=-43(3,2)-4-4+12=8(4,3)8-16=-84(4,3)-8-8+12=4(5,4)4-16=-125(5,4)-12-12+12=0(6,4)6(6,4)00+12=12(7,5)12-16=-47(7,5)-4-4+12=8(8,6)5.3试用中点Bresenham算法画直线段的原理，推导斜率在[-1,0]之间的直线段绘制过程。∵k[-1,0]，即|k|1∴取|dx|=1①取dx=1,dy=-k设di=F(xi+1,yi-0.5)=yi-0.5-k(xi+1)-b当di0,下一点(xi+1,yi)di+1=F(xi+2,yi-0.5)=di-k当di0,下一点(xi+1,yi-1)di+1=F(xi+2,yi-1.5)=di-1-kd0=F(x0+1,y0-0.5)=-(k+0.5)令Di=2dxdi,得D0=-(dx+2dy),D与d同号当Di0,下一点(xi,yi-1),Di+1=Di-2dy当Di0,下一点(xi+1,yi-1),Di+1=Di-2(dx+dy)习题5.3/P149yi-1yixi+1xi第四象限yi-2xi+2②取dx=-1,dy=k设di=F(xi-1,yi+0.5)=yi+0.5-k(xi-1)-b当di0,下一点(xi-1,yi)di+1=F(xi-2,yi+0.5)=di+k当di0,下一点(xi-1,yi+1)di+1=F(xi-2,yi+1.5)=di+1+kd0=F(x0-1,y0+0.5)=0.5+k令Di=2dxdi,得D0=dx+2dy,D与d异号当Di0,下一点(xi-1,yi),Di+1=Di+2dy当Di0,下一点(xi-1,yi+1),Di+1=Di+2(dx+dy)习题5.3/P149yi+1yixi-1xi第二象限yi+2xi-2|k|≤1习题5.4/P1495.4将中点Bresenham算法画直线段，推广到任意斜率的直线段。13421(0≤k≤1)D0=dx-2dydx=1,dy0Di0,Di+1=Di+2(dx-dy)(xi+1,yi+1)Di0,Di+1=Di-2dy(xi+1,yi)2(0≤k≤1)D0=-dx+2dydx=-1,dy0Di0,Di+1=Di+2(dy-dx)(xi-1,yi-1)Di0,Di+1=Di+2dy(xi-1,yi)3(-1≤k≤0)D0=-dx-2dydx=1,dy0Di0,Di+1=Di-2dy(xi+1,yi)Di0,Di+1=Di-2(dx+dy)(xi+1,yi-1)4(-1≤k≤0)D0=dx+2dydx=-1,dy0Di0,Di+1=Di+2dy(xi-1,yi)Di0,Di+1=Di+2(dx+dy)(xi-1,yi+1)习题5.4/P14958765(k≥1)D0=2dx-dydx0,dy=1Di0,Di+1=Di+2(dx-dy)(xi+1,yi+1)Di0,Di+1=Di+2dx(xi,yi+1)6(k≥1)D0=-2dx+2dydx0,dy=-1Di0,Di+1=Di-2dx(xi,yi-1)Di0,Di+1=Di+2(dy-dx)(xi-1,yi-1)7(k≤-1)D0=2dx+dydx0,dy=1Di0,Di+1=Di+2(dx+dy)(xi-1,yi+1)Di0,Di+1=Di+2dx(xi,yi+1)8(k≤-1)D0=-2dx-dydx0,dy=-1Di0,Di+1=Di-2(dx+dy)(xi,yi-1)Di0,Di+1=Di-2dx(xi+1,yi-1)|k|≥1习题5.4/P149推而广之：如果k1，则将x,y位置对调；如果x0，则dx取负数如果y0，则dy取负数已知1(0≤k≤1)时的中点Bresenham算法函数：voidMidBresenhamLine(intx0,inty0,intx1,inty1,intcolor);1(0≤k≤1)(x0,y0),(x1,y1)MidBresenhamLine(x0,y0,x1,y1,15)2(0≤k≤1)(x0,y0),(x1,y1)MidBresenhamLine(-x0,-y0,-x1,-y1,15)3(-1≤k≤0)(x0,y0),(x1,y1)MidBresenhamLine(x0,-y0,x1,-y1,15)4(-1≤k≤0)(x0,y0),(x1,y1)MidBresenhamLine(-x0,y0,-x1,y1,15)5(k≥1)(x0,y0),(x1,y1)MidBresenhamLine(y0,x0,y1,x1,15)6(k≥1)(x0,y0),(x1,y1)MidBresenhamLine(-y0,-x0,-y1,-x1,15)7(k≤-1)(x0,y0),(x1,y1)MidBresenhamLine(y0,-x0,y1,-x1,15)8(k≤-1)(x0,y0),(x1,y1)MidBresenhamLine(-y0,x0,-y1,x1,15)习题5.6/P1495.6试用中点Bresenham算法扫描转换圆心在原点、半径为8的园。已知d0=1-R=-7i(xiyi)di2x+32(x-y)+50(0,8)-731(1,8)-452(2,8)1-73(3,7)-694(4,7)3-15(5,6)236(6,5)57习题5.11/P1495.11采用扫描转换算法对图所示多边形进行填充，试写出ET表和当扫描线y=4时的有效边表AET表。设节点的数据结构：多边形ET表6543211,3,1/26,6,-11,1,∞7,5,03,3,-13,6,1/46,5,1xminymax1/knextAET表∴按p119的规则1，得交点：(1,1)(7,1)、(2,2)(3,2)、(3,2)(7,2)、(4,3)(7,3)、(4,4)(6,4)、(6,4)(7,4)、(4,5)(5,5)6543211,3,1/26,6,-11,1,∞7,5,03,3,-13,6,1/46,5,16543211,3,1/23.75,6,1/47,5,01.5,3,1/23,3,-16,6,-13,6,1/47,5,03.25,6,1/47,5,06,5,17,5,03.5,6,1/45,6,-1补充题，扫描线种子填充算法栈：s2，3，14，3，15，3，16，3，18，9，7，3，110，9，7，3，19，7，3，112，11，7，3，111，7，3，17，3，113，3，13，11S32145689710111213