计算题试题

1767863680568.png

1767863872852.png

分辨率 ，总像素数先算清楚：

个像素。

可显示色彩 色 ⇒ 每个像素需要的位数是
bit/像素（因为 ）。

所以帧缓冲大小：

  • 总比特数： bit
  • 换算成字节： Byte
  • 换算成 KiB / MiB：
    KiB
    MiB

答案：帧缓冲至少需要 983,040 B = 960 KiB ≈ 0.94 MiB。

（现实硬件里通常会按 16 bit/像素对齐存储，那就会更大，但题目按理论最小值就是上面这个。）

1767863774058.png

该问题可视为绕点 的非均匀缩放变换。该变换可通过平移与缩放的复合实现，即先将该点平移至原点，执行缩放变换，再将坐标系平移回原位置。

相应的齐次坐标变换矩阵可表示为

其中

为快速得到等效单矩阵，可利用二维仿射变换在齐次坐标下的分块形式

其中 为线性部分， 为平移部分。由分块矩阵乘法可得复合规则

将 、、 分别写成分块形式，有

因此总体线性部分为

总体平移部分为

从而得到等效单矩阵

上述结果采用的是列向量表示下的左乘矩阵形式，即点坐标表示为列向量，几何变换通过矩阵左乘实现。在该表示下，复合变换的顺序与矩阵乘法顺序相反。若采用行向量表示，则变换矩阵需置于坐标向量右侧，相应的复合顺序与几何变换顺序一致，此时矩阵形式可由左乘矩阵取转置得到，两种表示方式在几何效果上是等价的。

1767863801550.png

先将旋转中心平移至原点，执行逆时针旋转 ，再将坐标系平移回原位置。

相应的齐次坐标变换矩阵可表示为

其中

代入 ，并对上述矩阵进行乘法运算，可得最终的复合变换矩阵

该矩阵实现了以点 为不动点的逆时针 旋转变换。

1767864803525.png
1767864848497.png
假设从种子设置为(5,4)

取种子点 。算法以栈 维护待处理像素：初始化 ；每轮从栈顶弹出像素 ，将其着色，并按“右、上、左、下”依次检查四邻域像素 。若 且尚未着色（并且未在栈内），则将 入栈。栈空时算法终止。由此可得到从 出发、在四连通意义下与之连通且不跨越边界 的所有内部像素被依次填充。

为记录“试填写堆栈的变化过程”，下面给出每次出栈并完成邻域检查后的栈内容（表示为“左底、右顶”）以及该步出栈像素：

  • 初始：
  1. 出栈 ，入栈 ；
  2. 出栈 ，依序入栈 ；
  3. 出栈 ，入栈 ；
  4. 出栈 ，入栈 ；
  5. 出栈 ，入栈 ；
  6. 出栈 ，入栈 ；
  7. 出栈 ，入栈 ；
  8. 出栈 ，入栈 ；
  9. 出栈 ，入栈 ；
  10. 出栈 ，入栈 ；
  11. 出栈 ，入栈 ；
  12. 出栈 ，依序入栈 ；
  13. 出栈 ，入栈 ；
  14. 出栈 ，无新入栈；
  15. 出栈 ，无新入栈；
  16. 出栈 ，无新入栈；
  17. 出栈 ，无新入栈；
  18. 出栈 ，入栈 ；
  19. 出栈 ，无新入栈；
  20. 出栈 ，无新入栈；（终止）

由上述过程可见，填充在有限步内终止（栈为空），并覆盖了所有与种子点 四连通可达且不穿越边界 的内部像素。若实现中允许重复入栈（仅在出栈时判“是否已填充”），则最终填充区域不变，但堆栈序列会出现冗余项，记录表也会更长,可以采用扫描线种子填充算法解决这个问题

1767864924125.png

该多边形为三角形，其顶点可由图读出为

采用扫描线填充的 ET/AET 构造约定：忽略水平边；每条边在 ET 中以 记录，并按 归入对应桶；AET 在每条扫描线 处先删除满足 的边，再插入 ET[y]，并按当前交点 升序维护；处理完该扫描线后令 以用于下一条扫描线。

三条边分别为：

  • ，，，；
  • ，，，；
  • ，，，。

因此边表 ET（按桶 ）为：

活动边表 AET 的演化（给出每条扫描线开始时的 AET，及该线结束后的 更新结果）如下：

  • 扫描线 ：插入 ，

    更新到下一线（）的交点：（第一条），（第二条）。
  • 扫描线 ：先删除 的边（即 对应那条），再插入 ，

    更新到下一线（）的交点：，。
  • 扫描线 ：删除 的边后 ，算法结束。