计算机图形学2022年总结

画线画圆 #

DDA #

• 因为在迭代算法中，每一轮循环的结果都是在上一轮循环的基础上加一个增量得到的，所以称为增量算法。
• 约定屏幕空间是一个二维坐标系的第一象限。
• 如果待扫描转换的线的k>1，那么y增长的比较快，否则x增长的比较快。我们选择增长比较快的那个量，让他每次有1的增量，然后另一个增长比较慢的量的增量根据块的那个量的增量算出。例如x增长快，那么 $x_i=1,y_i=k$；如果y增长快，那么 $y_i=1,x_i=\frac{1}{k}$。
  • 为什么让增长快的那个的增量=1？因为这样就能保证在增长快的那个方向上，拥有连续变化的像素。（因为增长1只会跨越1个像素）。因为像素的长度是1.
  • 而且，如果让增长慢的那个是1，那么快的那个的增量就会>1，就会导致在它的方向上，像素不再连续，造成直线断断续续的情况。
• 缺点：存在浮点运算，慢。（舍入取整）
  • 如何对一个浮点数进行取整？ (int)(x+0.5)即可。

Bresenham #

• 以 $0\leq k\leq 1$为例，此时根据DDA的思想，x是每次增量较大的那一个，所以取x为迭代器，每次+1.
• 设当前绘制了点 $(x_i,y_i)$ ，在+1的过程中，判断直线上的点 $F(x)$ 和两个候选点的中点 $(x_i+1,y_i+0.5)$的上下关系，如果 $F(x)$在中点的上方，则取点 $(x_i+1,y_i+1)（右上点）$，否则取 $(x_i+1,y_i)$（右边点）。
• 由直线方程，得到隐式方程 $y-kx-b=0$，而把点 $(x_i+1,y_i+0.5)$代入，如果隐式方程>0，则说明中点位于线下方；否则位于线上方，即可完成判断。
  • 即：观察判别式 $y_i+0.5-k(x_i+1)-b$的符号。
  • 设 $d=y_i+0.5-k(x_i+1)-b$.
• 改为递推（递增）
  • 需要根据上次画点的情况得到本次画点所需的误差项。
  • 如果上次画点 $(x_i,y_i)$，
    • 那么如果上次取下一个点为“右上”，那么本次的点的坐标实际上是 $(x_i+1,y_i+1)$，本次的中点就变成了 $(x_i+2,y_i+1.5)$，把 $(x_i+2,y_i+1.5)$代入隐式方程，整理得 $F(x_i+2,y_i+1.5)=d-k+1$，也就是本次画点需要得出新点的误差是d-k+1.
    • 如果上次取下一个点为“右”，那么本次的点的坐标实际上是 $(x_i+1,y_i)$，那么新点要参照的中点是 $(x_i+2,y_i+0.5)$，代入隐式方程，整理得 $F(x_i+2,y_i+0.5)=d-k$，也就是本次画点需要得出新点的误差是d-k.
  • 总结：如果上次画点右上，那么本次需要的误差是d-k**+1**否则是d-k（不用+1）。
  • d的初值是什么？将 $(x_0+1,y_0+0.5)$代入隐式方程，得 $F(x_0+1,y_0+0.5)=0.5-k$.也就是d应该取初值0.5-k。
• 摆脱浮点运算
  • 因为新d是老d-k+1，或老d-k，且d的初值是0.5-k，所以只需要把0.5和k这两个浮点数变成整数。因为我们只需要判断d的符号，所以任意乘一个倍数并不影响判断。因此乘2（消除0.5）再乘 $\Delta x$（消除k）。
  • 于是，把上述的算法中的d都乘 $2\Delta x$即可，其他不变（x还是每次都+1，y还是+0或+1，但是d的迭代变成了 $2d\Delta x-2\Delta y+ 2\Delta x$ 或 $2d\Delta x-2\Delta y$（也就是d的增量变成了原来的 $2\Delta x$倍。））

改进Bresenham算法 #

• 仍然以 $0\leq k\leq 1$为例，此时根据DDA的思想，x是每次增量较大的那一个，所以取x为迭代器，每次+1.
• 设刚才画了点 $(x_i,y_i)$，根据Bresenham思想，现在的任务是确定x取 $(x_i+1)$时y的取值是否+1。引入简洁误差d，表示待画的线在 $x=x_i+1$处的y值和 $y_i$的差值，设为d。如果 $d>0.5$，则下一个y取 $y_i+1$，否则取 $y_i$。注意，如果取了 $y_i+1$，那么需要让d再减去1。
• 改为递推（递增）
  • 显然，每次迭代，d会增加k。因为交点一直都在待画的直线上。因此我们获得了其增量=k。
  • 初始值=0，因为一开始假设直线和某个像素点正好相交，我们从这个交点开始画线。
• 摆脱浮点运算
  • 现在要比较d和0.5的大小关系，不如把他转化为只需要判断符号，这样我们才方便乘数字来消除浮点数。
  • 于是定义 $e=d-0.5$，那么很自然地 $e_0=-0.5$，增量仍然是k。如果 e>0，那么选右上点，否则选右点；如果选了右上的点，$e=e-1$。
  • 观察可知，和未改进的Bresenham类似，其中涉及的浮点数包括初始值-0.5和k，因此仍然可以乘 $2\Delta x$。
  • 于是定义 $e=2\Delta x(d-0.5)$，那么很自然地 $e_0=-\Delta x$，增量是 $2\Delta y$ 。如果 e>0，那么选右上点，否则选右点；如果选了右上的点，$e=e-2\Delta x$。

进行推广 #

• 我们只讨论了 $0\leq k\leq1$的情况。如果 k>1，那么把x、y关系反过来（也就是y是变化较快的那一个，故取y为迭代器）；如果k<0，那么让其中一个变化相反。

Bresenham八分画圆 #

• 因为圆具有良好的对称性，且任意位置的圆可以移动到(0,0)，绘制完成再移动回去。所以直接考虑八分一个原点处的圆即可。八分是因为圆可以被y=x，y=-x划分成8份，其他部分直接利用对称即可直接把点得到。无需计算。

• 思想和Bresenham画线完全一致：判断中点和待画的线的关系。也就是把中点代入隐式方程，判断符号即可。注意这里因为考虑从 $x=0$到 $y=x$这一段的圆弧，所以候选点是右边和右下。

• 改为递推（递增）

  • 和未改进Bresenham一样。设上一个画的点是 $(x_i,y_i)$。
    • 如果上次选了右，即本次是 $(x_i+1,y_i)$，那么下面俩候选点的中点是 $(x_i+2,y_i-0.5)$，代入隐式方程 $F(x,y)=x^2+y^2-R^2$，得到 $F(x_i+2,y_i-0.5)=(x_i+2)^2+(y_i-0.5)^2-R^R$，而旧的d是 $F(x_i+1,y_i)=(x_i+1)^2+y_i-R^R$，二者做差，得到 $\Delta d=2x_i+3$.
    • 同理，得到如果上次是右下点，则 $\Delta d=2(x_i-y_i)+5$.
  • 算初值： $F(1,R-0.5)=1.25-R$。

• 摆脱浮点运算

  • 观察初值和递推：其中如果R是整数，那么只有1.25是小数，而且之后的递推中也没有出现小数，那么只需要把1.25干掉就没有小数了。

  • 因此让d=d-0.25即可。这样就消除了小数了。

    • $d_0=1-R$，且判断d和0的关系改为判断d和0.25的关系。

  • 因为中间不可能产生任何小数了，所以“判断d和0.25的关系”也没有必要了，它不可能这么精确，因为只能是整数。

    因此可以直接改成判断d的符号。

    • 因为R的单位是像素，所以必然是整数。

多边形扫描转化 #

扫描线填充 #

• 算法流程
  • 定界：确定ymax，ymin，从而确定最高和最低扫描线
  • 求交：对扫描线和多边形的边进行求交
  • 排序：对边表中的边进行排序
  • 填色：交点配对然后填色
• 优化要点
  • 求交：利用了y方向上的连贯性：只与有效边求交，且利用增量计算求交点，并简化顶点判断（让新边表中相关的边的 $y_{max}$ 减1）
  • 排序：只在新边加入时才有必要排序
• NET和AET
  • 新边表（NET）
    • 是一个链表，其中每个节点对应一个y值。如果某多边形的范围是y=2到y=10，那么它的节点依次与y=2、3、4、5、6、7、8、9、10相关，这里我们称为桶。每个桶也都是链表头，该链表挂了所有y值为它的边。
    • 确定边对应的y值：我们从y=2到y=10进行扫描，按这种扫描顺序，每条边第一次被扫描到的y值作为其y值，放到该y值对应的桶中。
      • 因为y值是第一次扫描到他而确定的，所以才称为“新边”。
    • 每个桶后面挂的链表的节点结构如下
      • x：第一次扫描到这条边时的x值（即这条边y值较小的端点的x值），用于排序。
      • $y_{max}$：这条边扫描结束时的y值（即这条边y值较大的端点的y值），用于结束扫描他。
      • $\frac{1}{k}$：增量。因为我们以y为迭代器（扫描线沿y方向移动），所以增量是 $\frac{1}{k}$而不是k。可以类比DDA。用于增量求交、排序。
      • next：链表next域。
    • 每个桶后面挂的链表的排序规则
      • 是双关键字排序，首先按照x值升序，然后按照增量升序。
      • 这样就能保证在扫描线向上运动时，扫描线与这些边的交点的x值是升序的。于是才能从左扫描到右。
    • 扫描线刚好通过多边形边顶点的取舍问题
      • 则该顶点可以按0个、1个或2个来计。我们约定这个顶点代表的顶点个数=其连接的两条边位于扫描线上方的个数。如果两条边都在上方，那就是算作2个顶点，否则类似的有1个、0个。
      • 为了简化判断，让新边表中相关的边的 $y_{max}$ 减1。这样一来，就自动满足了上述的约定。可以举个例子试一试，简直精妙绝伦。
  • 活性边表（AET）
    • 活性边的定义
      • 当前与扫描线正在相交的那些边。
    • AET桶内链表节点的结构
      • 和NET的基本一样，只不过把x换成“与此y值的扫描线相交的x坐标”。
      • 可见，如果要把新边加入进来，只需要复制NET中的这个边的节点即可。因为“与此y值的扫描线相交的x坐标”就是“第一次扫描到这条边时的x值”。
    • AET的构造（利用增量进行计算）
      • 把y下的扫描线对应的活性边构成链表，存放在AET对应y值的桶中
      • 遍历每个处于ymin和ymax之间的扫描线，按照之前约定的排序规则，按照正确的顺序把该线对应的活性边都链接在里面。
      • 注意，虽然是遍历，但是下一个y值的桶要根据上一个y值的桶得到。所以实际上是一个迭代的过程。
        • 如果是ymin的桶，那么直接把NET中的ymin的桶复制过来。（因为相当于所有的边都是刚刚被扫描到）
        • 否则，复制上一个y值的桶，然后：
          • 如果没有边失效，或没有新边加入，那么就然后利用 $\frac {1}{k}$ 对各边进行增量计算，算出新的x填入，即可完成本y值桶的构造。
          • 如果有边失效，也就是当前的y值大于了节点中记录的该边的ymax，那么直接把他从该桶的链表中删除。
          • 如果新边生效，也就是当前的y值在NET的该y的桶的链表非空，那就在那个链表中直接把新边摘过来（或者说是复制过来），放到新AET中这个新构造的链表中**，然后重新为这些边排序**，也就是需要插入到这个新链表的合适位置。
      • 对每条扫描线都这么做，即可将AET构造完成。
      • AET中的每个桶，其带的链表都必然是偶数条边。（因为做了之前的ymax-1优化，解决了扫描线穿过顶点的问题），所以都能自然地完成配对。于是就可完成填色。

区域填充 #

• 四连通和八连通

  • 考虑一个九宫格。中间的点的上、下、左、右称为四连通；如果把剩下那四个也算上就是八连通。
  • 注意，八连通填充算法不能填充四连通边界表示的区域，因为会跨越出去。但是如果采用内点表示，就没有问题。因为前者通过判断扫描到的点是否是边界颜色来判断是否把新点入栈，但是后者通过判断是否是内点颜色。如果某点在区域外，那么它必然不会被入栈。

• 边界填充算法和泛填充算法

  • 给定种子点、边界颜色，则将该种子点入栈。

  • 即利用bfs的思想。根据是四连通还是八连通来决定每次要发现当前点周围的哪些点。能入栈的条件是对其颜色的判断（对于边界填充是否非边界颜色且未被置为目标颜色，或对于泛填充是否非内点颜色且未被置为目标颜色。）。区别是这里采用栈而不是队列，且没有vis数组，存在重复入栈的可能性。

  • 边界填充算法通常用于给区域着色。泛填充算法通常用于给区域

    重新

    着色。因为前者适用于边界表示，后者适用于内点表示。

    • 4连通边界填充算法
    • 8连通边界填充算法
    • 4连通泛填充算法
    • 8连通泛填充算法

• 改进的填充算法

  • 为了防止重复入栈。于是引入扫描线思想。
  • 每次一个点出栈，就向左、向右都进行填充（沿着当前y的扫描线），直到遇到边界为止。
  • 然后在刚才填充的这一段扫描线区间检查上、下两条扫描线的该横坐标区间区域，如果可以入栈，就把这个区间的**x最大的（即最右边的）**像素作为种子入栈。
  • 为什么要分区间？因为如果是凹多边形，会存在这样的问题。同一个y扫描线，可能穿过两对可以配对的交点。这种情况也就是俩区间了。当然还有更复杂的情况，例如一个梳子。

反走样 #

• 反走样带来的问题
  • 锯齿明显
  • 丢失细节（例如某较小的点（其宽度小于像素直径）位于两个像素之间），则它点不亮任何一个像素。
    • 如果这是一个动画，设想该点在进行平移，那么他会时隐时现。因为当它比较接近所在像素的中心的时候，才能点亮所在像素。
• 走样的本质
  • 用离散量表示连续量带来的失真，是光栅化的必然产物。
• 减轻走样
  • 提升分辨率
    • 并不能消除锯齿，而是只能让锯齿更加细腻。
  • 超采样（后滤波）
    • 用较高的分辨率，例如2倍于原来的分辨率，于是就能把原来的一个像素分成若干子像素，例如这里用2倍超采样，就能1分4。在这种虚拟的分辨率下进行计算（例如运行Bresenham），然后对原来每个像素的区域包含的4个子像素的亮度取平均值，得到该像素的亮度结果。
    • 例如上面采用了2倍超采样，那么每个像素的亮度级别就变成了5级。因为对4个子像素的亮度进行求均，可以得到0-4共5级，分别代表其中有几个子像素被点亮了。
  • 重叠超采样（常用）
    • 例如屏幕分辨率是m*n，那么就可以提升虚拟分辨率到(2m+1)*(2n+1)，这样就能让原本每个像素的中心都对应一个子像素，而该子像素被周围八个其他子像素所包围，成为一个类似于卷积核的中心，且超采样前原本相邻的像素，在超采样后，他们所在的九宫格会共享边上的3个子像素。
    • 这样的好处是原本相邻的像素在超采样后会进行互相影响（因为共享了3个子像素），解决了普通的超采样中颜色跳变的问题。像素之间能够实现更均匀的过渡。
    • 既然得到了九宫格，我们还能像卷积那样，对它进行加权平均来计算最终亮度。例如下面就是三种加权方式：
    • $$ \begin{bmatrix} 1&2&1\ 2&4&2\ 1&2&1 \end{bmatrix} \begin{bmatrix} 1&1&1\ 1&2&1\ 1&1&1 \end{bmatrix} \begin{bmatrix} 0&1&0\ 1&4&1\ 0&1&0 \end{bmatrix} $$
    • 通过加权，可以实现越靠近中心，对原本像素的影响越大。这样能进一步实现平滑！
  • 区域取样（前滤波）
    • 把直线看做一个条带，而并不是一条理想直线。于是该条带由于具有宽度，可以对像素进行一定面积的覆盖。则覆盖的面积越大，像素的颜色就越接近线的颜色，否则越接近底色。
    • 这个可以通过计算直线条覆盖该像素的面积来实现。
      • 给出一个像素，以及待计算直线条边界进入该像素区域的具体起始位置，以及该直线的k，即可算出。因为只有两种情况：可能是三角形覆盖区域，可能是梯形覆盖区域。
      • 或者可以继续采用超采样的思想：把像素进一步分割，然后计算子像素中心落入直线条内的子像素的个数，就能近似得出直线占该像素的面积了。
    • 效果不如超采样：因为它是基于覆盖面积来计算亮度，不能达到计算直线和像素中心的距离来得出亮度等级的目的。因为如果覆盖面积相同，不能保证该距离也相同。

z-buffer扫描线（区间扫描线消隐算法） #

• 适用于多个多边形，在屏幕上有重叠的情况。该算法基于扫描线填充算法。
• 扫描线各交点把扫描线分成了很多区间，对于每个区间，如果该区间仅与1个多边形有关，那么填它的颜色；如果与多个多边形有关，则需要进行深度测试，决定该填谁的。
• 扫描线只要遇到多边形的边就会生成交点。因此可能会有多段连续的区间产生，而这些区间首尾相接。这种情况必然会需要深度测试。

几何造型技术 #

参数连续性 #

• n阶参数连续性即在连接处的从0到n阶导数值相等。
• 例如 $C^2$连续性指的是在连接处相连，且1、2阶导数值相等。

几何连续性 #

• n阶几何连续性保证在连接处的从0到n阶导数成比例，体现在几何上就是切向量的方向相等，而长度不要求相同。
• $G^0$等价于 $C^0$。

贝塞尔曲线 #

• 特点

  • 曲线通过第一个控制点和最后一个控制点
  • 曲线第1个控制点处的切线与第1、2控制点连线共线；曲线最后一个控制点与倒数第1个、倒数第2个控制点连线共线
  • 在凸包内

• 伯恩斯坦基

  • $B_i^{(n)}(t)=C_n^it^i(1-t)^{n-i}$.

• 曲线上的点

  • $[x,y,z]=\sum\limits_{i=0}^nB_i^{(n)}\cdot[x_i,y_i,z_i]$.
  • 也就是各自乘伯恩斯坦基的一项，作为一种权重，进行混合。

• 伯恩斯坦基的性质

  • 权性

    • 因为伯恩斯坦基函数可以看做是$[t+(1-t)]^n$的展开式，所以在u取任何值的时候，各项相加必然是1.而且u的取值一定要是在 $[0,1]$才符合这个要求。
      • 这样一来，就能当成权重去使用了，也就是给每个控制点分配一个这样的“项”。于是，把他们分别当做权重，**利用这种权重对各控制点进行加权平均，**就能画出贝塞尔曲线上的点。
      • 坏处就是有多少点，就有多少点参与其中进行加权，会牵一发动全身。
      • 可以使两个点重合实现加权。

  • 凸包性

    • 因为是加权混合而来，所以必然在凸包内。

  • 升阶

    • $B^n_i(t)=(1-t)B^{(n-1)}i(t)+tB^{(n-1)}{i-1}(1-t)$.

    • 利用两个基函数的项可生成一个比他高一阶的基函数的项。

    • 原理：$C_n^i=C_{n-1}^i+C_{n-1}^{i-1}$.

    • 对贝塞尔曲线进行升阶

      • 可以做到曲线形状完全不变，但是多出来一个控制点。

    • 应用：De Casteljau算法

      • 考虑从0阶开始升阶。每次都利用伯恩斯坦基的升阶公式得到一个更高阶的基。

      • 从而贝塞尔曲线具有了 $b^{(r)}_i=(1-t)b^{(r-1)}i+tb^{(r-1)}{i+1}$的性质。**注意这里的b是贝塞尔曲线上的点，而不是基函数。**也就是说，用两个低一阶的贝塞尔曲线上的点可以线性组合出高一阶的贝塞尔曲线上的点。

      • 所以，可以像动态规划一样，从0阶开始，依次计算出0阶上的几个点，然后让他们组合依次计算出1阶上的，以此类推。其中，0阶的点实际上就是给定的几个控制点。

      •   for r=1..n
              for i=0..n-r
                  b[r][i]=(1-t)b[r-1][i]+tb[r-1][i+1]
          return b[n][0];
        

• 贝塞尔曲线的拼接条件

  • C1：保证三点共线，且拼接点是其他两个控制点的中点。
  • G1：和C1一样，但是不用保证中点。

B样条曲线 #

• 基函数

  • $N^1_i(t)=\cases{1,(t\in [i,i+1])\0,otherwise}$.可见，它的作用范围是i到i+1这段区间。它属于一个1阶（也就是0次）基函数。后续的高阶基函数都要以它为依据升阶得到。显然他是具有权性的：在它管辖的区间内，是1.

  • 之后，取 $N^k_i(t)=\frac{t-i}{(i+k-1)-i}N^{k-1}

    i(t)+\frac{(i+k)-t}{(i+k)-(i+1)}N^{k-1}

    {i+1}(t)$.于是可以通过这种方式进行两两组合，从而升阶。

    • de boor算法就是利用的这个公式。
    • 每升一阶，管辖的区间长度+1.以1阶升2阶（即0次升1次）来说，显然要合并[i,i+1]和[i+1,i+2]，合并完了就是[i,i+2]，长度+1.然后继续升，则是[i,i+2]和[i+1,i+3]合并，完了是[i,i+3]。

• 节点向量

  • 对于均匀B样条，实际上节点向量没那么重要，因为它无非就是 $[0,1,2,3,…]$，但是对于非均匀B样条，它记录了每个节点所取的参数！因为对于k阶曲线来说，它的基函数管辖长度为k的区间，设有从 $d_0$到 $d_n$共n+1个控制顶点， 则k阶B样条的节点向量有n+k+1个元素，即 $[t_0,t_1,…,t_{n+k}]$.

• 性质

  • 基函数只在其管辖区间内非0，都是从其管辖区间开始时的参数 $t_i$到 $t_{i+k}$结束。（也就解释了节点向量下标最大值为什么是n+k，因为最后一个的区间是这样的。）
  • 如果一段曲线受到k个点的控制，那就是k阶B样条，也就是k-1次B样条，也就是控制它的样条基有k个（因为每个点都乘这个基来进行加权）。
  • 不同段的B样条之间的连接处的连续性是 $C^{k-2}$的。例如使用3次B样条（即4阶B样条），它的k=4，那么能够做到拼接处自动拥有了 $C^2$的连续性。因此，我们使用3次B样条会比较多一些。因为连续性能达到要求，而且计算代价又没那么大。
  • 如果某点处出现控制点重合，设其重数是m，那么此连接处的连续性是 $C^{k-m-1}$，也就是每重合一次，连续性就在原来的基础上再减去1.于是可以利用这种性质来构造尖点，或控制光滑性。
  • 对于k阶B样条，如果首、末控制点的重数都是k重，那么B样条曲线退化为k阶贝塞尔曲线。（注意，都得是k重才可以。）（样条基退化成了贝塞尔基。）

• de boor算法

  • 通过降阶，把 $N^k_i(t)=\frac{t-i}{(i+k-1)-i}N^{k-1}i(t)+\frac{(i+k)-t}{(i+k)-(i+1)}N^{k-1}{i+1}(t)$.化成与点有关的式子。
  • 它的割角法和贝塞尔的很类似，只不过是在被管线区间内的那些点进行而已。

裁剪 #

Cohen-Sutherland算法 #

• 裁剪的思想：简取、简弃、分治
  • 简取：如果线段的两个端点都在屏幕空间，就可以完全保留这条线，并结束算法；
  • 简弃：如果两个端点同时在屏幕左、同时在屏幕右、同时在屏幕上、同时在屏幕下，就可以丢弃这条线，并结束算法；
    • 注意，一定得是**“同时都在”**，否则不能保证其是否有中间的部分穿过屏幕空间，这样也就不能“简弃”了。
  • 分治
    • 如果不能简取也不能简弃，则需要与屏幕求交，按得到的交点分段，然后对这些线段重新跑Cohen-Sutherland。
    • 因为对这些线段又跑这个算法，所以这是分而治之。
• 核心思想：编码
  • 把屏幕和其八连通区域当成9宫格。每个宫格都对应着自己的编码。其中，屏幕空间的编码是0000。
  • 四位二进制：上下右左。例如一个端点在屏幕之外的右上区域，那就是1010.
  • 现在对线段的端点进行这样的编码处理。
    • 如果C1|C2==0，那么一定全是0，那么简取。
    • 如果C1&C2!=0，那么一定存在至少一位都是1，那么简弃。
    • 否则，分而治之：按左下右上的顺序与屏幕边界求交。分成若干条线段，重复上述过程。
• 优点
  • 对窗口很大或窗口很小的情况有很高的效率。因为可以直接保留或放弃。
• 缺点
  • 如果不能简取、简弃，就只能求交，略慢。

改进Cohen-Sutherland算法 #

• 对算法的缺点给出改进：不再求交，而是使用二分逼近交点。

Liang-Barsky算法 #

• 核心思想
  • 将直线的连续性应用进来：即它不可能从中间断掉，所以可以利用其连续性。
  • 把直线穿过屏幕空间分成四个过程：靠近、进入、离开、远离。
    • 例如从上界靠近，从左界进入，从右界俩开，从下界远离。可以想象，这是一个斜率绝对值很小的直线。
    • 注意，这里的屏幕“界”是直线，而不是线段。因此才能做到“靠近”、“远离”的过程。
    • 注意，这里的“线”也不是待裁剪的线段，而是这个线段所在的直线。因此才能做到“靠近”、“远离”的过程。然而，实际的待裁剪的线段并不一定能走完“靠近、进入、离开、远离”四个过程，它可能从任意一个环节才开始，或者从某一个环节就提前离开。
    • 因此，最终的输出要么是线段的端点，要么是它的“靠近/进入/离开/远离”点。虽然后者一定是从"进入/离开"两种点中取，但是为了判断方便，我们从这四个里面找即可。
• 给直线指定方向
  • 于是，把这六个候选点分成两个组，分别是进入组和离开组。以进入组为例，它由直线的进入端点、靠近点和进入点构成。
  • 为了方便，我们要求线都是从x小向x大的方向走的，因此我们规定x较小的那个端点是 $(x_1,y_1)$，x较大的那个端点是 $(x_2,y_2)$。 这样就可以很方便地区分到底哪三个点是进入组了。从而，只需对进入组的三个点取x最大的那个，对离开组取x最小的那个，并保证进入组的结果的x小于离开组的结果的x（否则这条线实际上并不在屏幕内）即可。
  • 如何给予线段所在直线这样的方向性？使用参数方程表示即可。即：写成关于两个端点 $(x_1,y_1),(x_2,y_2)$的方程（注意，这里是参数方程，而不是两点式）。即 $\cases{x=x_1+u\cdot (x_2-x_1)\y=y_1+u\cdot (y_2-y_1)}$，显然，应当满足 $u\in [0,1]$，因为我们在这个直线规定的方向上的增量是用两点坐标的差值来表示的，那么最大的差值就是真正的那个差值，否则在两个点之间，其差值必然比两点之间的那个差值小。
• 判断直线上点与窗口的位置关系（参数方程代入，与窗口边界进行比较）
  • 于是，对于点 $(x,y)$，其在窗口内的条件是： $\cases{wxl\leq x\leq wxr\wyb\leq y\leq wyt}$(注意，wxl的意思是window x left，其他的类似。)，也就是 $\cases{wxl\leq x_1+u\cdot (x_2-x_1)\leq wxr\wyb\leq y_1+u\cdot (y_2-y_1)\leq wyt}$.因此，有 $\cases{u(x_2-x_1)\geq wxl-x_1\u(x_2-x_1)\leq wxr-x_1\ u(y_2-y_1)\geq wyb-y_1\ u(y_2-y_1)\leq wyt-y_1}$，然后统一不等号的方向，有 $\cases{u(x_1-x_2)\leq -wxl+x_1\u(x_2-x_1)\leq wxr-x_1\ u(y_1-y_2)\leq -wyb+y_1\ u(y_2-y_1)\leq wyt-y_1}$，为了表示方便，尝试把他们表示成统一的形式，即有 $u\cdot p_k\leq q_k\ (k=1,2,3,4)$，其中约定 $\cases{p_1=-p_2\p_2=x_2-x_1\p_3=-p_4\p_4=y_2-y_1}$,且 $\cases{q_1=-wxl+x_1\q_2=wxr-x_1\q_3=-wyb+y_1\q_4=wyt-y_1}$.
• 特殊点
  • 若上述方程组中的任一方程取得“=”，那么该点就是交点。根据k值的不同（刚才说k=1，2，3，4），这个就是线段所在直线与四个边界所在直线之一的交点。每个k代表一个边界直线。
  • 若u=0或1，那么就是两个端点。（刚才说了，该直线是利用端点差值进行定义）
• 求交，分组
  • 观察知，$p_1=-p_2,p_3=-p_4$。因此他们各自是相反数。现在我们让不等式组中每一条分别取“=”，从而解出四个交点。
  • 然后，我们把解出的四个点与俩端点进行分组（分进入组和离开组）：可以把u=0和两个小于0的p的点分到进入组（分别是线段起点、靠近交点和进入交点），可以把u=1和两个大于0的p的点分到离开组（分别是线段终点、离开交点和远离交点）（为什么这么分？因为如果$p_k<0\ (k=1,2,3,4)$，那么它必然比线段的起始还要靠左，所以肯定分到进入组。）
• 进行裁剪
  • 现在拿到了两个组，分别有三个候选点。对进入组取x最大的哪个，离开组取x最小的那个，那么这两个x值之间那段就是裁剪结果。
• 特殊情况：与窗口平行
  • 如果 $p_1=0$，那么 $p_2$必然也等于0（因为是相反数），此时与窗口的竖向平行。同理，如果 $p_3=p_4=0$，那么与窗口的横向平行。
  • 此时进入组、离开组都少了一个候选点。减少了运算量。

Sutherland-Hodgeman算法 #

• 多边形裁剪的难点

  • 输出结果应该是一个新的多边形，它应该是封闭的，可以上色的，而不能是支离破碎的线段。
  • **如果是凹多边形，Sutherland-Hodgeman会产生多余的边。**例如裁剪一个骆驼，它的两个驼峰在可见区域内，其他部分都不可见，那么裁剪完毕后，在窗口边界上，两个驼峰间，会有一条多余线段。

• 算法思想

  • 按左下右上的顺序进行逐边裁剪（逐边裁剪是指逐屏幕边界！），每次裁剪完一个屏幕边界，就输出一个描述剩余多边形的点集，作为下一次根据另一条边界裁剪的输入。

  • 把空间

    利用当前依据的屏幕边界所在直线

    分为可见侧和不可见侧。

    • 如果一条边的两个端点分别在可见侧和不可见侧，就求交，然后只把可见侧的点和交点加入输出点集。
    • 如果一条边的两个端点都在可见侧，就把他们都加入输出点集。
    • 如果一条边的两个端点都在不可见侧，就什么都不做。

  • 把输出点集作为下一次裁剪的输入。把四个边界都走完了就结束。

• 修复凹多边形情况下的bug

  • 可以把凹多边形分割成两个凸多边形，然后再分别运行算法。
  • 也可以再次检查输出顶点，像扫描线算法那样，正确地对顶点进行配对。

Weiler-Atherton算法 #

• 解决了Sutherland-Hodgeman中，凹多边形产生的bug。
• 算法思想
  • 顺时针遍历待裁剪多边形的各点：
    • 如果当前点在不可见侧，下一点在可见侧，就求交，并把交点和可见侧之间的边输出；
    • 如果当前点在可见侧，下一点在不可见侧，就求交，并把交点和可见侧之间的边输出；但是还要做一步，来处理凹多边形bug：按顺时针从交点开始遍历屏幕边缘，找到最近的其他交点，把这个交点和当前交点连线并输出。
    • 如果当前点和下一点都在可见侧，则输出；如果如果当前点和下一点都在不可见侧，则什么也不做。
  • 于是，如果输入一个凹多边形，可能会输出很多个小的多边形，而且因为顺时针找最近的交点，能保证他们都是封闭图形。这是我们想要的结果。

消隐 #

• 消除隐藏线、消除隐藏面。
• 按消隐对象分类
  • 线消隐
  • 面消隐
• 按消隐空间分类
  • 物体空间消隐算法：对每个物体逐一比较，确定可见部分
    • Robert算法：自消隐，然后互相消隐
  • 图像空间的消隐算法：
    • 光线投射算法
• z-buffer算法
  • 屏幕带有2个缓冲：帧缓冲和z-buffer缓冲。
  • 对三维空间中会投射到屏幕该像素处的点比较z值，从而只取那个z值最大的点的颜色。（因为相机看向-z）。
  • 当且仅当该点的z是比z-buffer中该点的值还要大，才会把该点的颜色写入到帧缓冲的对应点处，并更新z-buffer在该处的值。
  • 最后要显示时，如果某点的z-buffer仍然为初始值，则以背景色显示，否则显示帧缓冲该处的颜色。
• 判断一个点是否处在多边形内
  • 射线法：向-y做射线，如果奇数交点则是在内，否则在外。
  • 弧长法：做单位圆，把各边投影到单位圆上，
    • 如果弧长和（注意逆时针旋转为正）是360度，那么在内部；
    • 如果是180，就在边上；
    • 如果为0，则在外部。
  • 简化弧长算法：以待判断的点为原点建立坐标系。
    • 选取多边形的一个点开始判断：同一象限+0，逆时针跨越一个象限+ $\frac{\pi}{2}$，顺时针跨越一个象限- $\frac{\pi}{2}$。最后如果是0则在内部。（结论和弧长法一样。）
    • 效率最高的算法。

真实感图形学 #

颜色模型 #

• 如何表示现实中的颜色（如何表示可见光谱中的颜色）

  • 颜色纺锤体
    • 由上下两个圆锥对着肚子组成。
    • 半径越大，饱和度越大；垂直轴线的高度越大，明度越大（>0是偏白，<0是偏黑）；在不同的圆心角，对应不同的色调。
    • 黑色和白色都在半径=0的地方，且分别位于轴线最高处和最低处（也就是两个圆锥尖）
  • CIE色度图（马蹄图）（CIE：国际照明委员会）
    • 其中的舌形边界，是可见光的轨迹。
    • x表示r，y表示g，而b=1-x-y。它是一个二维图形，而约定z可以通过1-x-y算出。所以他用二维表示了三个颜色分量。
    • 白色在(0.33,0.33)。

• 颜色模型（

  只能表示上述能表示颜色的子集

  ，因为上面那俩是自然界所有可见光颜色，而下面的颜色模型只是供人类、设备使用的颜色模型）

  • 面向设备
    • RGB
      • B是竖着的轴。
      • 黑色在原点，因为是加色模型。自然(1,1,1)就是白色。
    • CMY
      • 和RGB的转化：对每个分量取对1的补。即C=1-R，…。
  • 面向用户
    • HSV（色调-浓度-明度）
      • 从(1,1,1)到(0,0,0)引一个向量，沿着这个向量观察RGB立方体，就可以看到一个正六边形。这就是HSV的截面（颜色六边形）。
      • HSV是一个倒着放（尖朝下）的六棱锥。黑色在锥尖，白色在锥底面中心。
      • 和纺锤体类似。只不过它不是两个对一起，而是只有一个；且它是一个六边形的底面，所以表示的范围比纺锤体小。
    • HSI、HSL（色相-饱和度-亮度）
      • 纺锤体翻版。它和纺锤体完全一致。

Phong模型 #

• Ambient
  • 光源来自各个方向，同时也均匀地反射向各个方向。因此它不仅与片元所处位置无关，也与视点位置无关。
  • $K_a$：物体对环境光的反射系数
  • $I_a$：环境光强度
  • 因此，$I_a=K_a\cdot I_a$.
• Diffuse
  • 光源来自一个方向，但是漫反射光均匀地射向各个方向。因此它片元所处位置有关，而与视点位置无关。（与片元位置有关是因为法向量）
  • $I_P$：入射光强
  • $K_d$：漫反射系数。规定 $K_d \in [0,1]$，由物体表面性质和入射光波长决定。
  • $\theta$：入射方向和法向的夹角，规定 $\theta\in [0,\frac{\pi}{2}]$.
    • 根据Lambert余弦定理，$I_p\cdot cos\theta$就是漫反射光强度了。
  • 因此，漫反射光强 $I_d= K_d\cdot I_P cos\theta$.
  • 如果设点光源入射向量L（已规格化），法向量N（已规格化），那么 $L\cdot N=cos\theta$.于是有 $I_d=K_d\cdot I_p(L\cdot N)$.
  • 如果有多个点光源，那么就粗暴地对他们分别应用上式，并求和即可。
• Specular
  • 当观察方向接近镜面反射方向时，会看到非常亮的光斑。当逐渐偏离，光斑的光强会急剧下降。但是只要差的不大，都能看到一个光斑的。因此它与片元位置和视点位置都有关。（与片元位置有关是因为法向量）
  • $I_p$：入射光强（和diffuse共用）
  • $K_s$：镜面反射系数（和物体表面是光滑还是粗糙有关）
  • $\alpha$：视点和反射点构成的向量和反射光向量的夹角（锐角）。
  • $n$：反射指数（和物体表面是光滑还是粗糙有关，指数越大，光斑越小但是越清晰）。
  • 则有 $I_s=I_p\cdot K_scos^n\alpha$.
  • 如果设视点到反射点的向量是V（已规格化），反射光方向向量R，那么有 $I_s=I_p\cdot K_s(R\cdot V)^n$.
• 综合起来
  • $I=K_a\cdot I_a+K_d\cdot I_P(N\cdot L)+K_s\cdot I_P(V\cdot R)^n$.
  • 注意里面涉及到两种光强：入射光强 $I_P$负责漫反射和高光；环境光强 $I_a$负责环境光。而且写的时候都要先写K！而且后两个的格式都是和角度有关（乘个cos值）！

Blinn-Phong模型 #

• 为了实际实现Phong模型，给出一些近似：（做了近似处理的Phong模型即Blinn-Phong模型。）
  • 光源在无穷远处，视点也在无穷远处（这样一来，L、V向量都是不变的了。）
  • 于是，就可以简化高光计算：对于多光源情况，对于每个高光，因为V是常量，所以只需要计算一次夹角。
  • 引入半程向量H：它是V和L（也就是上面那两个变成常量的向量）的角平分线方向向量，现在只需要计算H和N的夹角，就能得出原来V和R的夹角。可以证明H和N的夹角总是V和R夹角的一半。所以他们满足线性关系，这是一个无损近似。
    • 因此，新得到的效果下，视点方向和反射方向夹角变化只是原来变化的一半，这会导致光斑增大。于是可以通过增大n的方式来弥补。
  • 因此，把Phong模型的高光部分稍作修改（改为使用半程向量表示的形式），就得到了Blinn-Phong模型：
  • $I=K_a\cdot I_a+K_d\cdot I_P(L\cdot N)+K_s\cdot I_P(H\cdot N)^n$
• 多光源
  • 各个光源的效果粗暴相加即可。但是要注意设置目标物体的亮度上限。
• 光衰减
  • 一般认为光随着距离呈二次函数反比例衰减。但是如果粗暴地使用 $\frac{1}{d^2}$，会在过远时衰减过慢，过近时衰减过快。于是采用下面的函数： $f(d)=min(1,\frac{1}{c_0+c_1d+c_2d^2})$.
  • 然后，给Blinn-Phong模型的漫反射和高光项乘上这个衰减函数即可。（环境光不需要衰减。）
  • $I=K_a\cdot I_a+f(d)K_d\cdot I_P(N\cdot L)+f(d)K_s\cdot I_P(N\cdot H)^n$.
• RGB实现
  • 对R、G、B的强度分别算一遍。可以为这三个分量分别规定K值，通过这种方式可以控制物体的颜色。

增量式光照模型（Gouraud明暗处理、Phong明暗处理） #

• 和简单光照模型的区别

  • 能够解决马赫带效应。因为如果粗暴地给多边形上同一种颜色（因为法向量是相同的），就会出现颜色跳变，不够真实。

• Gouraud明暗处理（对

  光强

  做双线性差值明暗处理，又称

  双线性光强差值

  ）

  • 过程
    • 计算所在三角形顶点的平均法向。
    • 利用该法向计算三角形三个点的光照情况（Phong模型）。
    • 利用双线性差值的方法计算三角形内任一点的光照情况（对三个顶点的光照进行差值。具体参照Phong处理。非常类似，只是差值对象这里是光照强度。）
    • 也可采用增量式算法：在第一次差值时的增量是 $\frac{I_1=I_2}{y_1-y_2}$（可见是y方向的），第二次差值时的增量是 $\frac{I_B-I_A}{x_b-x_a}$(可见是x方向的)。
  • 缺点
    • 不能处理高光（镜面反射），因为它通过差值把光强进行了扩大和柔和。

• Phong明暗处理（对

  法向量

  做双线性差值明暗处理，又称

  双线性法向差值

  ）

  • 过程
    • 求得三角形三个顶点的法向量后，通过一次线性差值求得扫描线与边的两个交点的法向量，然后通过这两个交点的法向量再进行差值求得扫描线上任一点的法向量。然后就可以对该点使用Phong模型进行计算，（因为有法向量了。）
  • 缺点
    • 比较慢。因为需要对多边形内部每个点都计算一次光照结果（利用Phong）。

Whitted光透射模型 #

• $K_t\cdot I_t$：光透射项。（给自己加料。）在全局光照中，如果这个物体是半透明的，那么应该能看到它折射后的它后面的物体。
• $K_r\cdot I_r$：光反射项。（来自其他物体。）在全局光照中，会接收其他物体反射后照射过来的光照。
• 于是有：$I=K_a\cdot I_a+K_d\cdot I_P(L\cdot N)+K_s\cdot I_P(H\cdot N)^n+K_t\cdot I_t+K_r\cdot I_r$.
  • 因此，Whitted光透射模型是Blinn-Phong加了两个项。
  • **因为全局光照=局部光照+间接光照。**而Phong模型是局部光照，于是Whitted加上了这两个项代表了间接光照。
• 光线投射算法（Ray Casting）
  • 从屏幕空间的每个像素都向场景中发射一条射线，这条射线先被哪个物体挡住就去计算哪个物体。（仅采用Blinn-Phong计算局部光照的结果）
• 光线追踪算法（Ray Tracing）
  • 采用了光线投射的思想，从像素向空间发射射线，找到最近的相交物体的交点。
  • 如果这个点来自纯漫反射表面，则仅采用Blinn-Phong计算，然后直接返回结果。
  • 如果这个点来自非纯漫反射表面，则需要进行递归追踪：
    • 从该点向其反射方向、折射方向继续运行光线追踪算法（只是这里的起始点不是屏幕空间像素点，而是表面上那个点。）
    • 递归的结束条件是：遇到纯漫反射表面，或追到了光源，或追出了场景，或达到最大设定递归深度。
    • 当递归最终返回，就可以利用反射方向的追踪返回结果填写 $I_r$，利用折射（透射）方向的追踪返回结果填写 $I_t$。
    • 然后，利用Whitted透射模型计算返回。
• 路径追踪算法（Path Tracing）
  • 把所有物体都看成非纯漫反射体。然后利用蒙特卡洛方法从概率的角度适当地减少一些方向上的光线追踪。
• 这几种方法的关系
  • 光线追踪=光线投射+递归追踪
  • 路径追踪=光线追踪+蒙特卡洛方法