图形学基础笔记II：多边形光栅化算法和显卡三角形光栅算法

为什么三角形就够了

实际对于 3D 来说肯定全是基于三角形的 geometry - OpenGL: Is it more efficient to use GL_QUADS or GL_TRIANGLES? - Stack Overflow，显卡也全部用重心坐标和 AABB 来填充三角形的。

三角形线框模式和非三角形线框模式（GUI、CAD），也很容易实现，使用 bresenham 中点算法就行了。

点就更简单了，如果没有涉及 Anti A 直接取整写显存就行了。

整理一下就是说:

• 线框模式各种形状：应用的话比如 CAD，GUI，不管什么多边形，什么样子都能用 bresenham 画线给你画出来。对于圆的话也是用 bresenham（midpoint）。
• 实体填充各种形状：由于屏幕像素是离散的，所以三角形足够拟合各种形状，只需要 AABB 重心填充算法。

所以下面讲的多边形扫描填充算法不是一个必要的东西（然而考试还是占挺多分值的，就当学一个算法+数据结构思路吧）。然而，他在 GUI 和 CAD 还是有用处的，不过是 GUI 里面基本都是用的盒子模型，最多多一个圆角，其实更多是矩形+圆角处理，所以纯粹的矩形扫描线就够用了。而画图软件的填充算法常用的是边界填充或者 flood-fill（DFS、BFS，O(n) 本来就是必要的）。

扫描线的问题在于他并行度有限，用了 ET + AET 的话数据依赖更加是拉跨，CPU 能撑起来，对于适合 SIMD 的 GPU 来说，还是用基于 AABB 的三角形的重心坐标比较靠谱（快）。而且求中心坐标的过程能同时完成三角形的 uv 纹理插值、颜色插值、法线插值等（总之就是插值各种属性），反而一举两得。

UE5 NANITE

Unreal Engine 5 的最新软光栅 nanite 技术（这个软不是指 CPU 运算，而是指用显卡的通用运算而不是管线自带的不可变成的光栅模块）是基于这样的事实：小三角形可能刚好一个 quad，这样的话每次为了求 mipmap 要用的那个梯度信息仍然要基于一个 quad 来光栅化，反而导致每次四倍的内存消耗。

首先要讲一下 compute shader ，这个东西是新显卡引入的通用计算单元在 OpenGL 里面的模块。就像 OpenGL 和 CUDA 能够请求通用计算那样。（其实在 D3D 里面 shader 多种多样，还有 mesh shader、primitive shader 各种名字的 shader）。

如果不基于 quad 来求梯度的话，就要用别的并发，nanite 用的是在渲染好的 buffer 进行差分。Visibility Buffer Rendering with Material Graphs – Filmic Worlds 具体这里不看了。

多边形光栅化填充算法

矩形填充要点

• 共享边界问题：左闭右开，下闭上开
• 原理都是常识

多边形扫描线填充算法

• 逐点射线法：偶数交点说明在外面，奇数说明在里面。没用太慢了。
• 步骤：
  • 求交：计算扫描线与多边形各边的交点；
  • 排序：把所有交点按x值递增顺序排序；
  • 配对：每两个点进行线性填充。

• 扫描边界确定：顶点重复计数，仍然是半闭半开原则。（每个顶点都有两条边，如果顶点在扫描线上会重复计数）。但是可以发现，重复的时候虽然 x 是一样的，y 是不一样的，此时只取 P1 P0 的边的结果因为 P0 更大，或者只取。

• 边界重复扫描：左闭右开。

• 内部取点：收缩取整

Edge table  和 Active edge table

• 基于这样的事实引入的增量算法：

• 1     2     3     4     5     6     7     8     9    10    11    12

  void polyfill (polygon, color) {      //建立全局边表ET;         for (各条扫描线i )  { 把ymin == i 的边结构－>边表ET [i]  }      将扫描线i的初值置为ET中非空元素的最小序号；      初始化活动边表AET为空；      for (各条扫描线i )     {         (1) 把边表ET[i]中的边结点插入AET表;             (2) 遍历AET表，把y max== i 的结点从AET中删除，并按x坐标值增序排列各边；             (3) 把配对交点区间(左闭右开)上的象素(x, i)，用WritePixel (x, i, color)改写颜色值；             (4) 把AET中每条边结点的x值递增△x；             (5) i++;         } }