《计算机图形学》练习题（答案）(2)

P9

P9

P7

P7

P8 P1 P6 P8 P1 P6 P3 P5 P3 P5

P4

P4 P2 P2

图1(e) 图1(f)

7．简述多边形扫描填充算法基本原理和大致步骤，并以具体例子说明边分类表内容、扫描过程中活化边表的信息变化。 (1)原理：

在直角坐标系中，假设有一条从左至右的扫描线穿过多边形，从左至右开始计数，与多边形交点为奇数时，开始进入多边形，与多边形交点为偶数时，走出多边形。这样在这相邻配对的奇偶交点间的所有象素都在多边形内。如图，奇数交点a，c，都是入多边形，偶数交点b ，d都是走出多边形，相邻的奇偶交点配对，a，b之间，c，d之间的象素都多边形内，可见一条扫描线上，与多边形交点个数需要为偶数。依据这样的思路，扫描线从上到下从左到右依次扫过多边形即可求得多边形所占据的象素。（注意退化情况的处理，也就是扫描线刚 好经过顶点或者多边形的边本身就是水平的情况）

(2)步骤：

1)输入多边形的顶点的坐标 2)建立边表（ET） 3)初始化Y值

4)初始化活性边表（AEL），设置为空

5)每个扫描线从底部到顶部，做以下步骤直到ET和AEL是空的： ?建立AEL ?设置颜色 ?更新AEL：

6

当Y= YMAX时,删除边 x = x +?X Y = y + 1 ④返回AEL (3)例子：

7

0

8． 由坐标A(0,0,0)，B(1,0,0)，C(0,1,0)，D(0,01)确定的锥体绕直线L旋转45,其中L的方向为V=J+K，且通过点C(0,1,0)。写出锥体旋转后的坐标。

32

9.设3次参数多项式函数P(u)=au+bu+cu+d,求出满足下列边界条件的3次Hermite插值曲线(用矩阵表示):

P(0) = Pk P(1) = Pk+1 P’(0) = DPk P’(1) = DPk+1

10.Cohen-Sutherland直线段裁剪算法和Liang-Barsky直线段裁剪算法是直线段裁剪的两种基本算法，试述两种算法的基本原理，并分析它们的优点和不足。

（1）通过一个矩形的裁剪区域将整个屏幕分成9个部分，并为每一个部分赋予相应的区域码，然后根据端点的位置确定这个端点的区域码。先判断能否完全接受或者完全排除一条线段，若以上2个判断无法直接得出，则逐步裁剪，选取一个位于裁剪区外的端点，把端点的区域码和裁剪边界的区域码进行逻辑与运算，若结果为真，则端点在该裁剪边界外部，这时将端点移向线段和该边界的交点处，如此循环，直到裁剪结束。 （2）利用线段的参数表达形式直接判别落在窗口内的部分线段. 大体上有以下几步,有些步骤依据中间的判断结果可以省略或跳转. 第一步：计算出pk和qk(k=1,2,3,4) 第二步：看pki的符号进行判断

8

第三步：计算u1=max(0,qk/pk),u2=min(1,qk/pk) 如果,u2>u1,则线段是可见的 第四步：利用u1和u2计算端点坐标 （3）比较：

Cohen-Sutherland：直观方便，速度较快

多次重复计算线段与裁剪窗口边界的交点，计算量大 采用位逻辑乘，在有些高级语言中不便进行 全部舍弃的判断仅适用于那些仅在窗口的线段，不适合跨越三个区域的 线段，就不能一次做出判别 Liang-Barsky：所需计算量小，更有效 可以扩展成三维裁剪算法 只能应用于矩阵窗口的情形

10. 简述Bezier曲线与B-Spline曲线的异同点，指出他们的特点和不足。

11. DDA算法和Bresenham算法是两种直线生成的基本算法，试述两种算法的基本原理，并分析它们的优点和不足。 （1）DDA算法：

?选定x2－x1和y2－y1中较大者作为步进方向(假设x2－x1较大)，取该方向上的增量为一个象素单位(△x=1)，

?利用式(2－1)计算另一个方向的增量(△y=△x·m=m)。通过递推公式(2－2)至(2－5)，把每次计算出的(xi+1，yi+1)经取整后送到显示器输出，则得到扫描转换后的直线。

?之所以取x2－x1和y2－y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。

④另外，算法实现中还应注意直线的生成方向，以决定Δx及Δy是取正值还是负值。

（2）Bresenham算法：

假定直线斜率k在0~1之间。此时，只需考虑x方向每次递增1个单位，决定y方向每次递增0或1。

设：直线当前点为(xi,y)

直线当前光栅点为(xi,yi)

则：下一个直线的点应为(xi+1,y+k)

下一个直线的光栅点为右光栅点(xi+1,yi)（y方向递增量0）或为右上光栅点(xi+1,yi+1)（y方向递增量1）

（3）优缺点：

DDA算法：算法简单，实现容易

由于在循环中涉及实型数的运算，因此生成直线的速度较慢。 浮点数运算 不易硬件实现

Bresenham算法：不必计算直线之斜率,因此不做除法; 不用浮点数,只用整数;

只做整数加减法和乘2运算,而乘2运算可以用硬件移位实现. 算法速度很快,并适于用硬件实现.

12. 简述直线段裁剪与多边形裁剪的异同点。

9

多边形的剪裁比直线剪裁复杂。如果按照直线剪裁算法对多边形的边作剪裁，剪裁后的多边形的边就会成为一组彼此不连贯的折线，从而给填色带来困难。多边形剪裁算法的关键在于，通过剪裁，不仅要保持窗口内多边形的边界部分，而且要将窗框的有关部分按一定次序插入多边形的保留边界之间，从而使剪裁后的多边形的边仍然保持封闭状态，以便填色算法得以正确实现

13. 在计算机辅助设计与图形学中，样条曲线通常采用3次多项式参数表示，请说明理由。

14. 图形学中消隐算法有两大类，z缓冲器(z-buffer)算法属于哪一类？请阐述它的基本原理和特点。

(1)属于图像空间消隐 (2)基本原理：

Z缓冲器中每个单元的值是对应象素点所反映对象的z坐标值。Z缓冲器中每个单元的初值取成z的极小值，帧缓冲器每个单元的初值可放对应背景颜色的值。图形消隐的过程就是给帧缓冲器和Z缓冲器中相应单元填值的过程。在把显示对象的每个面上每一点的属性（颜色或灰度）值填入帧缓冲器相应单元前，要把这点的z坐标值和z缓冲器中相应单元的值进行比较。只有前者大于后者时才改变帧缓冲器的那一单元的值，同时z缓冲器中相应单元的值也要改成这点的z坐标值。如果这点的z坐标值小于z缓冲器中的值，则说明对应象素已经显示了对象上一个点的属性，该点要比考虑的点更接近观察点。对显示对象的每个面上的每个点都做了上述处理后，便可得到消除了隐藏面的图

(3)特点： 优点：

（1）算法复杂度(O(nN))：对于给定的图像空间，N是固定的，所以算法复杂度只会随着场 景的复杂度线性地增加

（2）无须排序：场景中的物体是按任意顺序写入帧缓冲器和z缓冲器的，无须对物体进行 排序，从而节省了排序的时间

（3）适合于任何几何物体：能够计算与直线交点 （4）适合于并行实现(硬件加速) 不足：

（1）z缓冲器需要占用大量的存储单元： 一个大规模复杂场景中：深度范围可能为106，一个像素需要24bit来存储其深度信息。 如果显示分辨率为1280×1024，那么深度缓冲器需 …… 此处隐藏：2018字，全部文档内容请下载后查看。喜欢就下载吧 ……