前言
本文是對之前實作的軟光栅渲染器中光栅化算法的進一步講解與優化，這裡放上前文的傳送門：https://zhuanlan.zhihu.com/p/95621444
在之前的文章中，我使用的是掃描線算法來對三角形進行光栅化，這種方法非常直覺，效率也還不錯，但并不是現代GPU和CPU上使用的算法。本文将基于使用更廣泛的重心法進行講解，在學習過程中我主要參考了下面兩篇文章，并補充了一些細節，如果英語水準過關的話建議先閱讀下面的文章哦。
重心的計謀
加速半空間三角形光栅化
回顧
前文中我們實作的是掃描線算法，這種算法的原理是以三角形的長邊為底，一行一行向上/向下繪制像素點。
3、4可視為一種（一般三角形）
具體到操作上，該算法步驟為：
- 判斷三個頂點的相對位置，确定是平頂/平底還是一般三角形
- 将一般三角形以中間的頂點橫向拆分為一個平底和一個平頂三角形
- 通過插值在長邊上生成新的邊界點
- 分别對上部/下部三角形運作平底/平頂光栅化算法
- 每次繪制一行，通過插值生成兩個邊界點，繪制邊界點之間部分
掃描線算法的缺點在于難以并行化（畢竟操作的機關是一條線）。此外，在實作時還存在由于多次插值的精度損失導緻的多個三角形間存在接縫的問題。需要說明的是，這些問題并不是沒法解決，我查到的資料中還是有遊戲實際應用了這種算法的，隻不過現在大家都換用更加适合并行的算法了。單線程情況下掃描線算法的效率并不算低，用CPU渲染的話瓶頸更多的是在插值和片段着色上。
邊界函數算法（Edge-Function）
邊界函數算法，又叫半空間（half-space）光栅化算法，其基本原理在于，每一條直線都可以将平面分為左右（上下）兩個半空間。三角形三條邊的半空間交集可以定義三角形的内部區域
三角形半空間
如果我們有一個點P，該如何判斷點P是否在三角形内部呢？以上圖為例，
AP向量在
AC向量的右側，
AP向量在
BA向量的右側，
AP向量在
CB向量的右側，也就是說，将三角形的邊向量按照同一個旋向定義（
AC CB BA或是
AB BC CA），在三角形内部的點與（AP BP CP）的位置關系應該是一緻的。
這個判斷我們可以用叉乘來做，按照右手定則，由AC/CB/BA握向AP/CP/BP，拇指的指向是相同的。以坐标表示如下
這個Fab(P)就是我們的邊界函數了，它實際上就是AB與AP的叉乘，對于逆時針頂點順序三角形，在内部的點求得的三個F值都應大于等于0（順時針都小于等于0）。
基礎的邊界函數算法的實作僞代碼如下
//求出三角形的包圍盒(minX,minY,maxX,maxY)
上面的寫法适用于逆時針頂點順序，也就是我們一般認為的正向面，對于順時針頂點順序三角形，在計算之前交換任意兩個頂點順序即可。
優化考慮
我們的邊界函數可以改寫一下：
可以看到這個函數對于Px Py都是完全線性的，兩格之間的內插補點是固定值。
那麼我們在周遊的時候根本就不需要每次計算三個邊界函數值了，隻需要計算起點處的三個初始值，每移動一格就加上固定內插補點即可。優化後的僞代碼如下：
其中
//求出三角形的包圍盒(minX,minY,maxX,maxY)
這樣優化以後，整個像素周遊内循環就不再需要做乘法運算，運算速度更快。此外，由于對循環内的每個像素執行的操作都一樣，我們還可以使用SIMD指令對整個流程進行加速，同時對四個像素進行操作，一次執行4個像素的加法操作。
分塊
上面的算法優化了邊界函數的計算，但還有一個很嚴重的問題沒有解決，那就是該如何減少周遊的空像素數量。三角形的面積最多隻有包圍盒的一半，這意味着逐像素周遊我們始終要周遊大于一半的空像素。是以便有了分塊的優化算法。
分塊算法
如上圖所示，将多個像素組合成正方形的像素塊，每次逐塊周遊，檢測每個塊的左下角和右上角是否在三角形内，并可分為圖中綠塊表示的三種類型：
- 完全在三角形内
- 部分在三角形内
- 完全在三角形外
對于1和3，我們就不需要再為塊中每個像素計算邊界函數了，直接對整個塊進行渲染或是丢棄。對于2，我們再使用剛才的逐像素邊界函數算法進行繪制。此方法對于占螢幕面積較大的三角形優化效果明顯，但如果是小三角形或是斜長的細三角形，反而不如不分塊來得快。此外，太大的分塊會進一步降低小三角形的繪制效率，而太小的分塊又變回了逐像素算法，是以分塊的大小需要仔細的權衡。
還有一件事
上述算法隻做到了判斷某個像素是否在三角形内，但真正要繪制像素點還需要運作片段着色器。我們原來的掃描線算法在光栅化的時候就做好了插值，但現在去哪裡找法線和深度資訊呢？這時候就需要重心坐标出馬了。
這裡我放一篇知乎上寫重心坐标的文章：三角形重心坐标 by @二圈妹
借用一下配圖進行推導
使用三個頂點的資訊按照(1-u-v,u,v)的權重進行線性插值，即可獲得P點處的資訊，此處的資訊可以是一切線性資訊（包括深度，透視除法後的法線、紋理坐标、世界坐标等等等）。
那麼，這個插值權重該如何擷取呢？
我們知道三角形的面積等于
，這實際上是兩條邊向量叉乘模長的一半。
取兩條邊
AB和
AC，可得三角形面積為 （把叉乘行列式拆開）
我們回頭看一下邊界函數，發現
三個邊界函數之和正好是三角形面積的兩倍，那麼：
于是
就是我們要找的重心坐标
令
則可以得出插值公式 ：
這個插值公式在像素間的內插補點同樣是定值，是以我們同樣可以将插值工作轉化為加法操作，加快運算的速率。
由于：
是以 ：
加入了插值的光栅化算法僞代碼如下：
//這裡的頂點資訊已經經過了透視除法
寫在最後
看到這裡相信你已經三角形的光栅化有一定了解了，希望這篇文章能夠幫到你。不過在最後我想吐槽的是，在CPU單線程條件下上述算法的改進實在是聊勝于無。如果不運作片段着色器，僅插值深度（Intel就弄了一個在CPU上光栅化深度圖的軟體，可以加速顯示卡渲染：軟體遮擋剔除），能夠提升30%以上的速度，一旦改成完整的渲染流程，幀數則幾乎沒有變化，可見瓶頸并不在這裡。想要更進一步的提升，就必須考慮并行化了，包括使用SSE、AVX等SIMD指令，以及使用多線程等。
單線程的極限差不多就這樣了
下一期打算寫紋理相關的内容，這期就寫到這裡吧