三角形填充演算法的主要實現細節和注意點是什麼？

填充時不考慮反走樣

主要是有共享邊的兩個三角形

必須保證共享邊上的像素不會同時屬於2個三角形

---

首先用Edge Equation做光柵化的時候的確是會出現兩個三角形各自的兩條邊同時覆蓋在同一個像素上的情況的。Edge Equation就是一個直線的方程，像素中心剛好壓在直線上的時候就會用這種情況了，尤其是光柵化都是在定點數空間做的，這種情況很常見。例如這張圖中的三角形。

為了避免同一個像素被相鄰的三角形畫兩次，這個問題用一個預先定義好的填充規則（Fill Rule）去特殊的處理壓在三角形邊上的像素就可以解決。

DirectX用的是Top-Left Fill Rule：Rasterization Rules (Windows)

Top-Left Fill Rule就是說當一個像素剛好壓在三角形邊上的時候，只有這條邊在三角形的左邊，或者上面的時候，才判定這個像素被三角形覆蓋(如上圖)。

上邊很好判斷，如果有一條邊是水平的，且邊的兩個頂點都高於第三個頂點，就是上邊。

左邊則是指不水平的，且在三角形左邊的邊。一個三角形可以有1個或者2個左邊。更具體的解釋上面的鏈接說的很清楚。這個規則實現起來比看起來容易很多，真的就是幾行代碼的邏輯。

因為三角形頂點的方向是一定的（順時針或者逆時針），所以一條邊在左邊或者是右邊只比較邊的兩個頂點的高度即可。假設逆時針三角形為正面，左邊的邊的第一個頂點的一定比第二個頂點高。上面的邊則是兩個頂點一樣高，但是第一個頂點肯定在第二個頂點右邊。貼個C++代碼：

int TopLeftEdge(Vector2i v1, Vector2i v2)
{
return ((v2.y &> v1.y) || (v1.y == v2.y v1.x &> v2.x)) ? 0 : -1;
}


然後在光柵化的時候用這個去Offset一下Edge Equation的值就可以了。

int EdgeEquation(Vector2i p, Vector2i v0, Vector2i v1)
{
// p為像素位置, v0和v1是邊的頂點
return B0 * (p.x - v0.x) + C0 * (p.y - v0.y) + TopLeftEdge(v0, v1);
}


這樣當像素壓在邊上EdgeEquation等於0的時候，Top Left規則也會保證將這一點包括在三角形中。

---

把三角形3條邊界定義為邊函數，填充像素需滿足三個，那麼相鄰的三角形也不會重繪或有空隙。詳情請參考[1]。

更新：@文刀秋二 是對的，還要解決剛在像素上的問題。[1] Pineda, Juan. "A parallel algorithm for polygon rasterization." ACM SIGGRAPH Computer Graphics. Vol. 22. No. 4. ACM, 1988. http://people.csail.mit.edu/ericchan/bib/pdf/p17-pineda.pdf

---

除了Milo大神的答案，題主可以參考下這篇博文。傳送門在此：Advanced Rasterization。

文章主要提到了以下方面：

1、如何採用Edge Fucntion決定像素是否在三角形內部。

2、如何採用Top-Left Fill Convention去避免共享邊的重複繪製問題。

3、如何解決Sub-pixel precision的問題。

4、如何將演算法進行block/tile based並行化。

該博文提供了代碼以及優化過程，相信其對題主寫光柵化器是一個良好的參考。

---

@文刀秋二 @王浩宇

Top-Left 在這種情況下，像素給幾號三角形

---

推薦閱讀：