MIT 6.837:Rasterization 光栅化

MIT 6.837:Rasterization 光栅化

光栅化是渲染管线末端的环节,它将屏幕空间中由顶点定义的几何体转换为像素的颜色,生成最终呈现在用户眼前的画面。

直线的光栅化

直线的光栅化需要将给定端点连成的线段转化为一组屏幕中的像素。此处我们假设直线斜率 $m=\dfrac{\mathrm{d}y}{\mathrm{d}x}, 0 < m < 1$,其他情况均可通过对称等操作转化为此情况。

Naive 算法

29 - MIT 6.837:Rasterization 光栅化

将直线表达为方程 $y=y_1+m(x-x_1), m=\dfrac{y_2-y_1}{x_2-x_1}$,则可以对每个像素中心坐标 x 求出 y(x) 值,设置所有的像素 $(x, [y(x)])$ 即可。

但对于每一个像素横坐标 x 计算 y(x) 的值产生许多计算开销,由于像素 x 坐标之间差值固定为 1,故相邻像素的 y 坐标差值固定为斜率 m。这样,我们可以不必每次都计算直线的函数值,而是将 y 值自增 m 即可。

Bresenham 算法

30 - MIT 6.837:Rasterization 光栅化

由于我们将直线的斜率限制在 0~1 之间,已经设置像素右边的像素只有可能是图中的 E 和 NE 两个。我们通过判断在此像素 x 坐标位置直线是否穿过 E 和 NE 的邻边来判断应该设置哪一个像素。

31 - MIT 6.837:Rasterization 光栅化

直线方程可写为 $y=mx+b$,可将其改写为到直线的有向距离 $D(x,y)=y-mx-b$,此距离为正说明点在直线上方,否则在下方。我们可以通过图中邻边中心点 M 对应的有向距离正负来判断直线是否穿过邻边。

32 - MIT 6.837:Rasterization 光栅化

而在 Bresenham 算法中,我们用误差项 $e=-D(x,y)$ 表示到直线下方(即 y 不变)像素中心点的距离,如此距离大于 0.5,说明应设置上方像素,否则设置下方像素。每判断完一个像素后,x 增加 1,e 增加 m,而 y 通过此时像素设置情况觉得不增加或增加 1。

圆的光栅化

33 - MIT 6.837:Rasterization 光栅化

假设圆在第一象限的部分,且按顺时针进行光栅化,可以使用和直线相同的算法。

定义有向距离函数 $D(x,y) = x^2+y^2-R^2$ 和误差项 $e=-D(x,y)$。对于每一个 x 坐标,计算 y-1 坐标的误差项 e,如不小于 0.5 则应保持 y 不变,否则 y 变为 y-1 且 e 自增 1。当 x 增加 1 时,根据误差项式 e 应增加 2x+1。

上面提到的利用 $D(x,y)$ 和 $e=-D(x,y)$ 函数,通过 $e$ 的导数来更新值的方法被称为 DDA(离散微分分析器,Discrete Differential Analyzer) 方法。

三角形的光栅化

Naive 算法

34 - MIT 6.837:Rasterization 光栅化

对每一个像素中心计算三角形的三条直线,如在直线内侧则设置。可以用包围盒(如 AABB)来减小枚举像素的范围。

基于直线光栅化的改进

35 - MIT 6.837:Rasterization 光栅化

先对三条边光栅化,再设置每一对点之间的所有像素。

显示设备的方法

三角面通常较小,而如果先进行直线光栅化反而可能有更大的计算开销,因此不如回退到 AABB 优化的 Naive 方法,伪代码如下

For every triangle
  ComputeProjection
  Compute bbox, clip bbox to screen limits
  For all pixels in bbox
    Compute line equations
    If all line equations>0 //pixel [x,y] in triangle	
      Framebuffer[x,y]=triangleColor

而此算法可以进一步优化,在之前我们提到过直线方程的计算开销较大,可以考虑预处理包围盒边界的方程值,在扫描时根据导数来更新方程值,这样每次计算像素时只需要做加法运算即可,伪代码如下

For every triangle
  ComputeProjection
  Compute bbox, clip bbox to screen limits
  Setup line eq 
    compute aidx, bidy for the 3 lines
    Initialize line eq, values for bbox corner
      Li=aix0+biy+ci
  For all scanline y in bbox
    For 3 lines, update Li
    For all x in bbox
      Increment line equations: Li+=adx
    If all Li>0 //pixel [x,y] in triangle	
      Framebuffer[x,y]=triangleColor

Gouraud 着色

36 - MIT 6.837:Rasterization 光栅化

得到了三个顶点的颜色值后,我们可以使用 Gouraud 着色得到更平滑的颜色。这种方法是在三角面中对顶点的颜色进行线性插值。对于某一通道的颜色,记 $R=a_Rx+b_Ry+c_R$,则根据三顶点的颜色可解出三系数,实现与直线方程类似的插值即可。

另一方法是利用顶点的重心坐标进行插值。



发表评论

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据