图形学参考答案

5.3试用中点Bresenham算法画直线段的原理推导斜率在[-1,0]之间的直线段绘制过程（要求写清原理、误差函数、递推公式及最终画图过程）。解法一：构造直线方程F(x,y)=y-kx-b=0由于01k，即1xy，此时x为最大位移方向，算法每次在x方向上加1，y方向上减1或减0。即对于当前选定的点Pi（xi，yi），下一个点应该为1,1iidyxP或iiuyxP,1，选取哪一个点依赖于判别式。即有1111iiiiiyyyxx取Pu和Pd的中点M（xi+1，yi-0.5），将M的坐标代入直线方程构造判别式：bxkyyxfyxfdiiiiMM)1(5.0)5.0,1(,当（注意这里的判断方法）d0时，M点在Q点上方，取1,1iidyxPd0时，M点在Q点下方，取iiuyxP,1d=0时，M点与Q点重合，约定取iiuyxP,1即有)0(1)0(111dydyyxxiiiii递推公式的推导：当d0时,kdbxkyyxfdiiii1)2(5.15.1,212增量为-1-k当0d时,kdbxkyyxfdiiii12)2(5.05.0,2增量为-kkkbkxybxkyyxfd5.05.0)1(5.05.0,10000000由于x方向递增，0x，故此在等式两边同乘以x2，则有：当d0时,yxDDkdd22112增量为yx22当0d时,yDDkdd212增量为y2yxDkd25.000注意：此时优化要注意此时x0，优化时判别式要改变方向。解法二：构造直线方程F(x,y)=y-kx-b=0由于01k，即1xy，此时x为最大位移方向，算法每次在x方向上减1，y方向上加1或加0。即对于当前选定的点Pi（xi，yi），下一个点应该为1,1iiuyxP或iidyxP,1，选取哪一个点依赖于判别式。即有iiiiiyyyxx1111取Pu和Pd的中点M（xi-1，yi+0.5），将M的坐标代入直线方程构造判别式：bxkyyxfyxfdiiiiMM)1(5.0)5.0,1(,当d0时，M点在Q点上方，取iidyxP,1当d0时，M点在Q点下方，取1,1iiuyxP当d=0时，M点与Q点重合，约定取1,1iiuyxP即有)0()0(1111dydyyxxiiiii递推公式的推导：当d0时,kdbxkyyxfdiiii12)2(5.05.0,2增量为k当0d时,kdbxkyyxfdiiii1)2(5.15.1,212增量为1+kkkbkxybxkyyxfd5.05.0)1(5.05.0,10000000由于x方向递减，0x，故此在等式两边同乘以-x2，则有：当d0时,yDDkdd212增量为y2当0d时,yxDDkdd22112增量为yx22yxDkd25.0005.7利用中点Bresenham画圆算法的原理推导第一象限x＝y到y＝0圆弧段的扫描转换算法（要求写清原理、误差函数、递推公式及最终画图过程）。yPPlPrM解：在x=y到y=0的圆弧中，（R,0）点比在圆弧上，算法从该点开始。最大位移方向为y，由（R,0）点开始，y渐增，x渐减，每次y方向加1，x方向减1或减0。（注意算法的起始点）设P点坐标（xi,yi）,下一个候选点为Pr（xi,yi+1）和Pl（xi-1,yi+1），取Pl和Pr的中点M（xi-0.5,yi+1），设理想圆与y=yi+1的交点Q，构造判别式：222)1()5.0(),(RyxyxFdiMM当d0时，M在Q点左方，取Pr（xi,yi+1）d0时，M在Q点右方，取Pl（xi-1,yi+1）d＝0时，M与Q点重合，约定取Pl（xi-1,yi+1）所以有：)0()0(1111dxdxxyyiiiii推导判别式：0d时，取Pl（xi-1,yi+1），下一点为（xi-1,yi+2）和（xi-2,yi+2）5221)1(2)1(1)5.0(2)5.0()2()5.1()2,5.1(1222222iiiiiiiiiiyxdyyxxRyxyxFd0d时，取Pr（xi,yi+1），下一点为（xi,yi+2）和（xi-1,yi+2）321)1(2)1()5.0()2()5.0()2,5.0(1222222iiiiiiiiydyyxRyxyxFdRRRRRFd25.1125.0)1,5.0(220优化：令D=d-0.25则上述公式只有初值发生变化，即D=1-R，其余用D替换d即可。5.11如图5－59所示多边形，若采用扫描转换算法（ET边表算法）进行填充，试写出该多边形的ET表和当扫描线Y＝4时的有效边表（AET表，活性边表）。xy21345678123456解：ET表123456131/275033-166-1361/4651123456131/275033-166-1361/4651y＝4时的AET表3.561/4Y=466-1651750注意：（1）构造边表时，水平边不需要构造；（2）边表中纵向链表的长度等于多边形覆盖的扫描线数；（3）边表与有效边表中每个结点的第三项为1/k；（4）构造有效边表时，每个结点的第一项，即当前扫描线与多边形边交点处的x坐标不需要四舍五入，否则在计算下一条扫描线时可能会造成误差。5.22构造两个例子，一个是4－连通图，其边界是8－连通的，另一个是8－连通图，其边界是4－连通的。解：注意：由于八邻接点中包含四邻接点，所以四连通区域也可以看作八连通区域，但是四连通区域与八连通区域的边界条件是不同的，通常在边界表示的区域中，四连通区域边界（内环和外环边界）的连通性是八连通，而八连通区域边界（内环和外环边界）的连通性是四连通。在一些特殊的情况下一个区域的连通性可能既是四连通也是八连通，例如内点表示的四连通区域（内点表示没有显示的边界），或者将边界表示的四连通区域的所有边界（内环和外环边界）都改为四连通性质。6.4已知点P（xp，yp）及直线L的方程Ax+By+C=0，试推导一个相对L作对称变换的变换矩阵T，使点P的对称点为TPP'。解法一：（1）当B=0时，直线方程变为Ax+C=0，即x=-C/A，该直线与y轴平行。变换可以先将直线平移，使之与y轴重合，此时的对称变换是相对于y轴的对称变换，最后在反平移，使直线回到原来的位置。1020100011001000110001000110010001ACACACT（2）当0B时，直线方程变为BCxBAy，直线与y轴有一个交点（0，-C/B），直线的斜率k=-A/B。此时先将直线平移，使点（0，-C/B）与原点重合，在顺时针旋转θ角（tgθ=-A/B）使直线与x轴重合，此时的对称变换是相对于x轴的对称变换，最后反变换，使直线回到原来的位置。1)2cos1(2sin02cos2sin02sin2cos100100011000cossin0sincos1000100011000cossin0sincos10010001BCBCBCBCT2222222cos22sinABABBAAB12202022222222222222222ABBCABACABBAABABABABABABT解法二：当0B时，直线方程变为BCxBAy，直线与y轴有一个交点（0，-C/B），直线的斜率k=-A/B。令P（xp，yp）点关于直线的对称点为),('''ppyxP，则有1022''''BAxxyyCyyBxxApppppppp解得：22222222'22222222'2222BABCyBABAxBAAByABACyABABxABABxpppppp12202022222222222222222ABBCABACABBAABABABABABABT6.7题略（逆时针旋转45度）解：变换的过程包括：（1）平移：将P点平移至原点，变换矩阵为：145010001tT（2）旋转：图形绕原点（P点）旋转45度，变换矩阵为：100045cos45sin045sin45cos0RT（3）反平移：将P点移回原处，变换矩阵为：1450100011tT变换矩阵为122942250222202222145010001100045cos45sin045sin45cos14501000101tRtTTTT变换过程：12242251225422512242235122425122942250222202222141177137114'TPP注意写出变换矩阵以及变换过程。6.7题略（顺时针旋转45度）解：变换的过程包括：（1）平移：将P点平移至原点，变换矩阵为：145010001tT（2）旋转：图形绕原点（P点）旋转45度，变换矩阵为：100045cos45sin045sin45cos0RT（3）反平移：将P点移回原处，变换矩阵为：1450100011tT变换矩阵为122422950222202222145010001100045cos45sin045sin45cos14501000101tRtTTTT变换过程：12242251224225512234225124225122422950222202222141177137114'TPP6.13试用编码裁减算法裁剪如图所示的线段。y22A(3,3)B(-1,-2)xoCDE解：（1）首先对AB进行编码，A的编码code1为1010，B的编码code2为0101；由于code1|code2≠0，且code1&code2=0，因此对直线段AB既不能简取也不能简弃。（2）求交处理。A的编码为1010，右起第二位编码不为0，故求出直线段AB与窗口右边界的交点C(2,7/4)；此时AC必在窗口外，可简弃。C的编码为0000，用C点坐标代替A点坐标，code1=0000；由于code1|code2≠0，且code1&code2=0，直线段A（C）B仍然不能简取也不能简弃。（3）求交处理。A（C点）的编码为0000，交换code1与code2的值以及AB点的坐标值，此时code1=0101，code2=