图形学参考答案.doc

5.3 试用中点Bresenham算法画直线段的原理推导斜率在[-1,0]之间的直线段绘制过程（要求写清原理、误差函数、递推公式及最终画图过程）。
解法一：构造直线方程F(x,y)=y-kx-b=0
由于，即，此时x为最大位移方向，算法每次在x方向上加1，y方向上减1或减0。即对于当前选定的点Pi（xi，yi），下一个点应该为或，选取哪一个点依赖于判别式。
即有
取Pu和Pd的中点M（xi+1，yi-0.5），将M的坐标代入直线方程构造判别式：

当（注意这里的判断方法）
d>0时， M点在Q点上方，取
d<0时， M点在Q点下方，取
d=0时，M点与Q点重合，约定取
即有

递推公式的推导：
当d>0时, 增量为-1-k
当时, 增量为-k

由于x方向递增，，故此在等式两边同乘以，则有：
当d>0时, 增量为
当时, 增量为

注意：此时优化要注意此时<0，优化时判别式要改变方向。

解法二：构造直线方程F(x,y)=y-kx-b=0
由于，即，此时x为最大位移方向，算法每次在x方向上减1，y方向上加1或加0。即对于当前选定的点Pi（xi，yi），下一个点应该为或，选取哪一个点依赖于判别式。
即有
取Pu和Pd的中点M（xi-1，yi+0.5），将M的坐标代入直线方程构造判别式：

当d>0时，M点在Q点上方，取
当d<0时，M点在Q点下方，取
当d=0时，M点与Q点重合，约定取
即有
递推公式的推导：
当d>0时, 增量为k
当时, 增量为1+k

由于x方向递减，，故此在等式两边同乘以-，则有：
当d>0时, 增量为
当时, 增量为

5.7 利用中点Bresenham画圆算法的原理推导第一象限x＝y到y＝0圆弧段的扫描转换算法（要求写清原理、误差函数、递推公式及最终画图过程）。

解：在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，
构造判别式：

当d<0时，M在Q点左方，取Pr（xi,yi+1）
d>0时，M在Q点右方，取Pl（xi-1,yi+1）
d＝0时，M与Q点重合，约定取Pl（xi-1,yi+1）
所以有：
推导判别式：
时，取Pl（xi-1,yi+1），下一点为（xi-1,yi+2）和（xi-2,yi+2）

时，取Pr（xi,yi+1），下一点为（xi,yi+2）和（xi-1,yi+2）

优化：令D=d-0.25
则上述公式只有初值发生变化，即D=1-R，其余用D替换d即可。

5.11 如图5－59所示多边形，若采用扫描转换算法（ET边表算法）进行填充，试写出该多边形的ET表和当扫描线Y＝4时的有效边表（AET表，活性边表）。

解： ET表

y＝4时的AET表

注意：
（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的对称点为。
解法一：（1）当B=0时，直线方程变为Ax+C=0，即x=-C/A，该直线与y轴平行。变换可以先将直线平移，使之与y轴重合，此时的对称变换是相对于y轴的对称变换，最后在反平移，使直线回到原来的位置。

（2）当时，直线方程变为，直线与y轴有一个交点（0，-C/B），直线的斜率k=-A/B。此时先将直线平移，使点（0，-C/B）与原点重合，在顺时针旋转θ角（tgθ=-A/B）使直线与x轴重合，此时的对称变换是相对于x轴的对称变换，最后反变换，使直线回到原来的位置。

解法二：当时，直线方程变为，直线与y轴有一个交点（0，-C/B），直线的斜率k=-A/B。
令P（xp，yp）点关于直线的对称点为，则有

解得：

6.7 题略（逆时针旋转45度）
解：变换的过程包括：
（1） 平移：将P点平移至原点，变换矩阵为：

（2） 旋转：图形绕原点（P点）旋转45度，变换矩阵为：

（3） 反平移：将P点移回原处，变换矩阵为：

变换矩阵为

变换过程：

注意写出变换矩阵以及变换过程。

6.7 题略（顺时针旋转45度）
解：变换的过程包括：
（1） 平移：将P点平移至原点，变换矩阵为：

（2） 旋转：图形绕原点（P点）旋转45度，变换矩阵为：

（3） 反平移：将P点移回原处，变换矩阵为：

变换矩阵为

变换过程：

6.13 试用编码裁减算法裁剪如图所示的线段。

解：（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=0000；
由于code1=0101，右起第一位编码不为0，故求出直线段A（B）B（C）与窗口左边界的交点D(0,-3/4)；
此时A（B）D必在窗口外，可简弃。D的编码为0100，用D点坐标代替A点坐标，code1=0100；
由于code1 | code2 ≠0，且code1 & code2 =0，直线段A（D）B（C）仍然不能简取也不能简弃。
（4）继续求交。Code1=0100，右起第三位编码不为0，故求出直线段A（D）B（C）与窗口下边界的交点E(3/5，0)；
此时EA（D）必在窗口外，可简弃。E的编码为0000，用E点坐标代替A点坐标，code1=0000；
由于code1 | code2 =0，直线段A（E）B（C）简取。

解：（1）首先对AB进行编码，A的编码code1为1010，B的编码code2为0101；
由于code1 | code2 ≠0，且code1 & code2 =0，因此对直线段AB既不能简取也不能简弃。
（2）求交处理。A的编码为1010，右起第二位编码不为0，故求出直线段AB与窗口右边界的交点C(2,11/4)；
此时AC必在窗口外，可简弃。C的编码为1000，用C点坐标代替A点坐标，code1=1000；
由于code1 | code2 ≠0，且code1 & code2 =0，直线段A（C）B仍然不能简取也不能简弃。
（3）求交处理。A的编码为1000，右起第四位编码不为0，故求出直线段A（C）B与窗口上边界的交点D(7/4,2)；
此时A(C)D必在窗口外，可简弃。D的编码为0000，用D点坐标代替A(C)点坐标，code1=0000；
由于code1 | code2 ≠0，且code1 & code2 =0，直线段A（D）B仍然不能简取也不能简弃。
（4）求交处理。A（D点）的编码为0000，交换code1与code2的值以及AB点的坐标值，此时code1=0101，code2=0000；
由于code1=0101，右起第一位编码不为0，故求出直线段A（B）B（D）与窗口左边界的交点E(0,3/5)；
此时A（B）E必在窗口外，可简弃。E的编码为0000，用D点坐标代替A点坐标，code1=0000；
由于code1 | code2 =0，直线段A（E）B（D）简取。

6.15 用梁友栋算法裁减线段AB （B点的坐标改为（－2，－1））
解：以A（3，3）为起点，B(-2，-1)为终点（这里起点和终点可以互换，但这样直线的参数方程将会改变）。
所以有x1=3，y1=3，x2=-2，y2=-1，wxl=0，wxr=2，wyb=0，wyt=2
构造直线参数方程：

即
计算各个p和q值有：

根据，有

由于，故此直线AB有一部分在裁减窗口内，将代入直线参数方程，得到直线在窗口内部分的端点C（7／4，2）和D(0，3／5)。

解：以A（3，3）为起点，B(-1，-2)为终点（这里起点和终点可以互换，但这样直线的参数方程将会改变）。
所以有x1=3，y1=3，x2=-1，y2=-2，wxl=0，wxr=2，wyb=0，wyt=2
构造直线参数方程：

即
计算各个p和q值有：

根据，有

由于，故此直线AB有一部分在裁减窗口内，将代入直线参数方程，得到直线在窗口内部分的端点C（2，7/4）和D(3/5，0)。

6.16 题略

（1）用左边界裁剪 （2）用下边界裁剪
输入：ABCDE 输入：BCD12A
输出：BCD12A 输出：56D1234B

（3）用右边界裁剪 （4）用下边界裁剪
输入：56D1234B 输入：D1234B7
输出：D1234B7 输出：91234B78

6.17 试用Weiler-Atherton算法对下图所示的多边形进行裁剪，要求画出每次裁剪对应的图形，并标明输入和输出的顶点。

解：输入：ABCDE。逆时针处理多边形，此时沿窗口边界处理的顺序也是逆时针。
（1）输入AB，由不可见侧进入可见侧，输出直线段IB；
（2）输入BC，由可见侧进入不可见侧，输出直线段BJ，并从J点沿窗口逆时针找到距离最近的交点L，输出直线段JK和KL；
（3）输出CD，由不可见侧进入不可见侧，不输出；
（4）输出DE，由不可见侧进入可见侧再进入不可见侧，输出直线段LF，并从F点沿窗口逆时针找到距离最近的交点G，输出直线段FG；
（5）输出EA，由不可见侧进入可见侧再进入不可见侧，输出直线段GH，并从H点沿窗口逆时针找到距离最近的交点I，输出直线段HI；

7.5题略
解：关于P点整体放大两倍，可以先将P点平移至原点，再进行比例变换，最后反平移。
变换矩阵为：

变换过程为

所以变换后各点的规范化齐次坐标（注意要转换成规范化齐次坐标）分别为：
（2，2，-2，1），（2，6，－2，1），（－2，6，－2，1），（2，6，2，1）

注意：本题中的比例变换矩阵也可写为
则

变换过程为

所以变换后各点的规范化齐次坐标分别为：
（2，2，-2，1），（2，6，－2，1），（－2，6，－2，1），（2，6，2，1）

7.6 假定一空间直线AB的两端点坐标为A(0,0,0)和B(2,2,2),试写出绕AB旋转30º的三维复合变换矩阵。

解：变换步骤如下
(1) 将ABB'绕x轴逆时针旋转α角，则AB旋转到xoz平面上。

(2) 将OB绕y轴顺时针旋转β角，则OB旋转到z轴上。

(3) 此时AB轴与z轴重合，绕AB轴的旋转转换为绕z轴的旋转。

(4) 最后，求TRx，TRy的逆变换，回到AB原来的位置。

最后的变换矩阵是这5个矩阵相乘的形式：

7.7 题略（平移矢量均为1）
解：（1）主视图（主视图不需要平移）

（2）俯视图

注意：这里可以直接写出变换矩阵，如果你记下来的话。

（3）侧视图

注意：这里可以直接写出变换矩阵，如果你记下来的话。

注意：三个图要画在一个坐标系中，注意点与点的连接关系以及直线的可见性问题。