这篇文章上次修改于 321 天前,可能其部分内容已经发生变化,如有疑问可询问作者。

计算题试题

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,及该线结束后的 更新结果)如下:

  • 扫描线 :插入 ,

    更新到下一线()的交点:(第一条),(第二条)。
  • 扫描线 :先删除 的边(即 对应那条),再插入 ,

    更新到下一线()的交点:,。
  • 扫描线 :删除 的边后 ,算法结束。