计算机图形学第5章习题.ppt

计算机图形学基础12021/5/27习题习题5.2/P149o5.2 5.2 用用DDADDA算法、中点算法、中点BresenhamBresenham算法和改进算法和改进BresenhamBresenham算法扫描转换直线段算法扫描转换直线段P1P2P1P2，其中，其中P1P1为为(0,0)(0,0)、P2P2为为(8,6)(8,6)。DDADDA算法：算法：已知已知P1(0,0)P1(0,0)、P2(8,6)P2(8,6)，则：则：dx=8,dy=6dx=8,dy=6dxdydxdy并且并且k1k0 D Di i0,D0,Di+1i+1=D=Di i+2(dx-dy)(x+2(dx-dy)(xi i+1,y+1,yi i+1)+1)D Di i 0,D0,Di+1i+1=D=Di i-2dy (x-2dy (xi i+1,y+1,yi i)2(0k1)2(0k1)D D0 0=-dx+2dy=-dx+2dy dx=-1,dy0 D Di i0,D0,Di+1i+1=D=Di i+2(dy-dx)(x+2(dy-dx)(xi i-1,y-1,yi i-1)-1)D Di i 0,D0,Di+1i+1=D=Di i+2dy (x+2dy (xi i-1,y-1,yi i)3(-1k0)3(-1k0)D D0 0=-dx-2dy=-dx-2dy dx=1,dy0 D Di i0,D0 D Di i0,D0,dy=1 D Di i0,D0,Di+1i+1=D=Di i+2(dx-dy)(x+2(dx-dy)(xi i+1,y+1,yi i+1)+1)D Di i 0,D0,Di+1i+1=D=Di i+2dx (x+2dx (xi i,y,yi i+1)6(k6(k1)D D0 0=-2dx+2dy=-2dx+2dy dx0,dy=-1 D Di i0,D0,Di+1i+1=D=Di i-2dx (x-2dx (xi i,y,yi i-1)-1)D Di i 0,D0,Di+1i+1=D=Di i+2(dy-dx)(x+2(dy-dx)(xi i-1,y-1,yi i-1)7(k-1)7(k-1)D D0 0=2dx+dy=2dx+dy dx0,dy=1 D Di i0,D0,dy=-1 D Di i0,D1k1，则将，则将x,yx,y位置对调；位置对调；o如果如果 x0 x0，则，则dxdx取负数取负数o如果如果 y0y0，则，则dydy取负数取负数已知已知1(0k1)1(0k1)时的时的中点中点BresenhamBresenham算法函数：算法函数：void MidBresenhamLine(int x0,int y0,int x1,int y1,int color);void MidBresenhamLine(int x0,int y0,int x1,int y1,int color);1(0k1)1(0k1)(x0,y0),(x1,y1)MidBresenhamLine(x0,y0,x1,y1,15)MidBresenhamLine(x0,y0,x1,y1,15)2(0k1)2(0k1)(x0,y0),(x1,y1)MidBresenhamLine(-x0,-y0,-x1,-y1,15)MidBresenhamLine(-x0,-y0,-x1,-y1,15)3(-1k0)3(-1k0)(x0,y0),(x1,y1)MidBresenhamLine(x0,-y0,x1,-y1,15)MidBresenhamLine(x0,-y0,x1,-y1,15)4(-1k0)4(-1k0)(x0,y0),(x1,y1)MidBresenhamLine(-x0,y0,-x1,y1,15)MidBresenhamLine(-x0,y0,-x1,y1,15)5(k1)5(k1)(x0,y0),(x1,y1)MidBresenhamLine(y0,x0,y1,x1,15)MidBresenhamLine(y0,x0,y1,x1,15)6(k1)6(k1)(x0,y0),(x1,y1)MidBresenhamLine(-y0,-x0,-y1,-x1,15)MidBresenhamLine(-y0,-x0,-y1,-x1,15)7(k-1)7(k-1)(x0,y0),(x1,y1)MidBresenhamLine(y0,-x0,y1,-x1,15)MidBresenhamLine(y0,-x0,y1,-x1,15)8(k-1)8(k-1)(x0,y0),(x1,y1)MidBresenhamLine(-y0,x0,-y1,x1,15)MidBresenhamLine(-y0,x0,-y1,x1,15)习题习题5.6/P1495.6 5.6 试用中点试用中点BresenhamBresenham算法扫描转换圆心在原点、算法扫描转换圆心在原点、半径为半径为8 8的园。的园。已知已知d d0 0=1-R=-7=1-R=-7i (xi yi)di 2x+3 2(x-y)+50 (0,8)-7 31(1,8)-4 5 2(2,8)1 -73(3,7)-6 94(4,7)3-15(5,6)2 36(6,5)5 7习题习题5.11/P1495.11 5.11 采用扫描转换算法对图所示多边形进行填充，采用扫描转换算法对图所示多边形进行填充，试写出试写出ETET表和当扫描线表和当扫描线y=4y=4时的有效边表时的有效边表AETAET表。表。设节点的数据结构：设节点的数据结构：多边形多边形ETET表表6543211,3,1/26,6,-11,1,7,5,03,3,-13,6,1/46,5,1xmin ymax 1/k nextAETAET表表按按p119p119的的规则规则1 ，得交点：，得交点：(1,1)(7,1)(1,1)(7,1)、(2,2)(3,2)(2,2)(3,2)、(3,2)(7,2)(3,2)(7,2)、(4,3)(7,3)(4,3)(7,3)、(4,4)(6,4)(4,4)(6,4)、(6,4)(7,4)(6,4)(7,4)、(4,5)(5,5)(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