计算机图形学习题课

1、Computer GraphicsComputer Graphics3. Liang-Barsky3. Liang-Barsky算法算法分析：P1(x1,y1)和P2(x2,y2)将线段看成由方向性：外到内 内到外p1p2p1p1左右下上Liang-BarskyLiang-Barsky算法算法x=x1+u(x2-x1)y=y1+u(y2-y1)0 u 10 u 1任意直线段I（X1,Y1）J(X2,Y2)的参数方程：xyowytwybwxlwxr窗口给定裁剪窗口：Liang-BarskyLiang-Barsky算法算法wxl x1+u(x2-x1) wxrwyby1+u(y2-y1) wytu

2、(x1-x2) x1 wxl 左边界u(x2-x1) wxr x1 右边界u(y1-y2) y1 wyb 下边界u(y2-y1) wyt y1 上边界p1 = x1-x2p2 = x2-x1p3 = y1-y2p4 = y2-y1令：q1 = x1 wxlq2 = wxr x1q3 = y1 wybq4 = wyt y1upkqk k=1,2,3,4如果任一点（）在窗口内则：v 取“=”时求得的u对应的是直线与窗口边界的交点v 1、2、3、4分别对应左、右、下、上边界v U=0和1时分别对应直线的起点和中点xyowytwybwxlwxr窗口裁剪后的两端点是哪些点？ 分析：裁剪的本质 Uone=

3、max(0,uk|pk0,uk|pk0,uk|pk0)I1J1对于I1J1P1、P4小于0 U在0、U1、U4取大者P2、P3大于0 U在1、U2、U3取小者如果Uone Utwo取可求得两端点左p1 = x1-x2 右p2 = x2-x1下p3 = y1-y2上p4 = y2-y1q1 = x1 wxlq2 = wxr x1q3 = y1 wybq4 = wyt y1假定PK不为0左p1 = x1-x2 右p2 = x2-x1下p3 = y1-y2上p4 = y2-y1q1 = x1 wxlq2 = wxr x1q3 = y1 wybq4 = wyt y1如果Uone Utwo表明什么？P1

4、、P3小于0 U在0、U1、U3取大者P2、P4大于0 U在1、U2、U4取小者Uone=max(0,uk|pk0,uk|pk0,uk|pk0)I1J1特殊处理：(a)直线段与窗口边界wxl和wxr平行的情况(b)直线段与窗口边界wyb和wyt平行的情况wytwybwxlwxrwxrwxlwybwytA AB BC CD DE EF FG GH HI IJ JK KL LPK为0p1=p2=0p3=p4=0Uone=max(0,uk|pk0)左p1 = x1-x2 右p2 = x2-x1下p3 = y1-y2上p4 = y2-y1q1 = x1 wxlq2 = wxr x1q3 = y1 wy

5、bq4 = wyt y1窗口B(-2,-1)A(3,3)xyx=3+u(-2-3)y=3+u(-1-3)0 u 10 u 1即：即：x=3-5uy=3-4u这里：这里：wxl=0,wxr=2wyb=0,wyt=2（0 u 10 u 1）解：直线段AB的参数方程为：p1 = x1-x2=50p2 = x2-x1 =-50p4 = y2-y1 =-40 可见P均不为0因此：q1 = x1 wxl=3q2 = wxr x1=-1q3 = y1 wyb=3q4 = wyt y1=-11、试用liang-barsky算法裁剪图中的线段AB。由于有： p1 、p3大于0， p2、 p4小于0Uone=ma

6、x(0,uk|pk0,uk|pk0,uk|pk0)因此：Uone=max(0,u2,u4)=max(0,0.2,0.25)=0.25Utwo=min(1, u1,u3)=min(1,0.6,0.75)=0.6可见Uone0p2 = x2-x1 =-50p4 = y2-y1 =-40q1 = x1 wxl=3q2 = wxr x1=-1q3 = y1 wyb=3q4 = wyt y1=-1I（1.75,2）J(0,0.6)2、试用中点Bresenham算法扫描转换一条连接两点（0，0）和（8，5）的直线段。oxy如果两点变为（0，0）和（5，8）的直线段，可以怎样做？ox解：x=x2-x1=8-

7、0=8 y=y2-y1=5-0=5直线斜率k=y/yx=5/8，满足0k1,k1,所以每次x增加1，求y的值。d的初始值为x-2y=8-2*5=-2往右上方的增量为2x-2y=6往正右方的增量为-2y=-10初始点为（0，0）由于d0.5xi d0.5证明：k1，x 0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x,y+1)。5.当直线没有画完时，重复步骤3和4。否则结束。影响此算法效率的主要原因是存在浮点数及浮点数与0.5的大小比较，为消除这些不利因素的影响，可进行如下优化：优化优化1 1：令：令e = d - 0.5e = d - 0.5yi+1

8、 = yi + 1xi+1 =xi + 1 e0 xi e0e初=-0.5，每走一步有e=e+m。if (e0) then e=e-1改进改进2 2：用：用2e2ey y来替换来替换e ene初=-y，n每走一步有e=e+2x。nif (e0) then e=e-2y最终得到了一个整数的算法。最终得到了一个整数的算法。影响此算法效率的主要原因是存在浮点数及浮点数与0.5的大小比较，为消除这些不利因素的影响，可进行如下优化：优化后的算法步骤：优化后的算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-y、x=x0、y=y0。3.绘制点(x,y)。4.

9、e更新为e+2x，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2y；否则(x,y)更新为(x,y+1)。5.当直线没有画完时，重复步骤3和4。否则结束。4、求将图中的空间四面体进行如下变换的变换矩阵，写出复合变换后图形各顶点的规范化齐次坐标，并画出符合变换后的图形。（1）关于点P整体放大2倍；（2）关于y轴进行对称变换。C(0,2,0)A(2,0,0)B(2,2,0)D(2,2,2)y yx xz zP(2,-2,2)解：（1）分为3次基本变换：平移、整体放大、反向平移平移：Tx=-2,Ty=2,Tz=-2 T1=整体放大：S=1/2 反向平移：Tx=2,Ty

10、=-2,Tz=2 T2= T3=100001000010-22-21C(0,2,0)A(2,0,0)B(2,2,0)D(2,2,2)y yx xz zP(2,-2,2)1000010000100000.51000010000102-221T= T1 T2 T3= =100001000010-22-211000010000100000.51000010000102-221100001000010-11-10.5C(0,2,0)A(2,0,0)B(2,2,0)D(2,2,2)y yx xz zP(2,-2,2)四面体ABCD的齐次坐标表示矩阵为：2001A2201B0201C2221DP=2001

11、220102012221P=PT=100001000010-11-10.511-10.5A13-10.5B-13-10.5C1310.5D四面体ABCD各顶点变换后的齐次坐标为：A(1,1,-1,0.5),B(1,3,-1,0.5),C(-1,3,-1,0.5),D(1,3,1,0.5)规范化的齐次坐标为：A(2,2,-2,1),B(2,6,-2,1),C(-2,6,-2,1),D(2,6,2,1)变换后各点的坐标为：A(2,2,-2),B(2,6,-2),C(-2,6,-2),D(2,6,2)C(0,2,0)A(2,0,0)B(2,2,0)D(2,2,2)y yx xz zP(2,-2,2)

12、C(-2,6,-2)A(2,2,-2)B(2,6,-2)D(2,6,2)y yx xz z变换后各点的坐标为：A(2,2,-2),B(2,6,-2),C(-2,6,-2),D(2,6,2)图形如下（b）所示：P(2,-2,2)（b）（a）5、试证明一个均匀比例（Sx=Sy）和一个旋转变换是一个可交换对。证明：即需要证明这两个变换的变换矩阵的乘积满足交换率。均匀比例变换的变换矩阵为：Ts=旋转变换的变换矩阵为：Tr=S000S0001cossin0-sincos0001T2=TrTs=S000S0001cossin0-sincos0001scosssin0-ssinscos0001T1=TsTr

13、=S000S0001cossin0-sincos0001scosssin0-ssinscos0001如果先作比例变换再作旋转变换，复合变换的变换矩阵为T1：如果先作旋转变换再作比例变换，复合变换的变换矩阵为T2：T1=T2，因此可证明一个均匀比例（Sx=Sy）和一个旋转变换是一个可交换对。6、如下图所示多边形，若采用扫描转换算法（ET边表算法）进行填充，试写出该多边形的ET表和当扫描线Y=2时的有效边表AET表（活性边表），并说明在该处的填充区间。xy213 4 5 6 7 8 9111234567891011121012p1p3p4p5(a) 多边形P0P1P2P3P4P5P6P0p2p0p

14、61234567891011123-1/3353/485-1/2891/21122/5712-1795桶p3p2p3p4p5p4p5p6p2p1p0p1p0p6x|yminymax1/knext(c) 边表6解：边表的纵向链表长度为多边形所占有的最大扫描线数12；共有7条边，每条边的数据形成一个结点，链入与该边最小y坐标相对应的桶处。 由此，可写出该多边形的ET表，如下图所示：xy213 4 5 6 7 8 9111234567891011121012p1p3p4p5(a) 多边形P0P1P2P3P4P5P6P0p2p0p6当扫描线Y=1时的有效边表AET表（活性边表）如下：可见，这4个节点在

15、扫描线Y=2时仍为有效边，且在扫描线Y=2处没有新边出现，因此，扫描线Y=2时的有效边表AET表（活性边表）如下：xy213 4 5 6 7 8 9111234567891011121012p1p3p4p5(a) 多边形P0P1P2P3P4P5P6P0p2p0p6在扫描线Y=2的交点按序为: （8/3，2）（3.75,2）（7.5,2）（8.5,2）真正的交点序列为： （3，2）（4,2）（8,2）（9,2）填色区间为： （3，2）和（4,2）之间，（8,2）和（9,2）之间。 补充说明：（1）水平线的处理： 进行说明，表明不用考虑且不会影响结果（2）垂直线的处理： 与一般直线段统一处理，只是 m=1/k=01234567654321xy07、名词解释：字符精度文字剪裁字符精度字符剪裁是一种舍弃不完全落在窗口内的字符的一种文字裁剪方法，如图所示：Computer graph mputegraph（a）裁剪前（b）裁剪后2w级DAC帧缓冲存储器C