這篇要講的是當我們有個三點構成的三角形，如何取得三角形內的所有點。
參考上圖，假設有 A、B、C三點，我們想填滿 (或是說取得) 三角形內的所有點，最簡單的做法是
- 取得從 A 到 B 的所有點
- 取得從 A 到 C 的所有點
- 從 A 開始，一次往下一層，從 A 到 B 取同高的一點，從 A 到 C 取同高的一點，由最左到最右畫一條水平線。
第三點強調 “最左” 和 “最右” 是因為常常一條水平線上有超過二個以上的點，需要找到最靠二端的點再畫。
從上到下一行行掃描下去，就能畫出整個三角形了。取得 A 到 B 或是 A 到 C 的所有點可以利用上一章的 Bresenham Line’s Algorithm，畫水平線時也同樣使用 Bresenham。
在實際操作上，我們先從高到低將三個點排序，以三個點來說，會有以下幾種可能。
Case 1: 三點同高 (水平線)
直接用 Bresanham 畫一條直線。
Case 2: 三點不同高
參考右圖，先算出 A 到 B 、A 到 C 和 B 到 C 的所有點，
第一步先從 A 點開始，將上半部三角形 ABD 填滿。接下來再將三角形 BDC 填滿。
Case 3: 最高二點同高
忽略 Case 2 的上半部三角形，直接填滿下半部。
Case 4: 最低二點同高
忽略 Case 2 的下半部三角形，直接填滿上半部。
這部分的程式太長，如果需要可以參考 utility.hpp。
inline static void rasterize_triangle(
Point pt1,
Point pt2,
Point pt3,
std::vector<Point>& out)
{
...
}
測試可以參考在 unittest.cpp 的 Sample_2。
Sample_2::Sample_2()
{
// vertices for a face (triangle)
face_.set(
PointF(1, 0, 0),
PointF(-1, 1, 0),
PointF(-1, -1, 0)
);
rotate_degree_ = 0;
}
void Sample_2::paintFace(BYTE* buf, LONG width, LONG height, WORD bytePerPixel)
{
...
}
結果如下，一個轉個不停的白色三角型。
取得三角型內的所有點其實理論很簡單，但是要處理的例外情況較多，導至整個程式看起來有點長。最理想的狀況是大家完全不要看上面的二個程式，自己寫一次會清楚很多。
接下來的章節算是中場休息，我們先不管這些向量三角函數或是演算法，直接拿個工具做一隻猴子的臉出來吧。