從零開始手敲次世代遊戲引擎（五十二）

來自專欄 高品質遊戲開發

在從零開始手敲次世代遊戲引擎（五十一）當中，我們通過切分法對任意三角形進行了像素化（離散化）計算。其實除此之外，還有別的像素化方法。比如利用三角形的重心坐標系進行像素化的方法。

重心法

重心法其實就是在對象三角形的AABB盒（平行於坐標軸的矩形包圍盒）當中的點使用三角形的重心公式進行逐點測試篩查。這種方法計算量較大，但是演算法本身非常簡單，比較適合固化成為硬體來進行處理。

圖1-1 重心法進行三角形像素化[i]

三角形重心法的核心（基本依據）是根據三角形的重心公式[1]的一種等價變形：如果選定三角形的任意一個頂點，那麼三角形內的任何點都可以通過以該頂點作為起點的兩條邊所對應的向量進行線性組合得到，且滿足組合的係數不為負且和小於等於1。

因此，我們首先通過分別比較三角形的三個頂點（V1, V2, V3）的x軸坐標與y軸坐標得到三角形在x軸和y軸上的最大最小值，這4個值排列組合形成了一個三角形的外接矩形，且這個矩形分別平行於x和y坐標軸。接下來我們對這個矩形進行像素化（離散化）並逐個測試所得的像素是否在三角形上。測試的方法是分別算出被測試的點到達以所選頂點為一個端點的兩條邊的距離，將這個距離除以對應邊上的三角形的高（其實就是在求該點的重心坐標）。得到兩個係數：s和t。當且僅當s >= 0, t >= 0 且s + t <= 1時，該點在三角形內。否則該點就在三角形外。

下面給出了該演算法的一種可能的C++實現：

代碼清單1-1 利用重心公式進行三角形像素化演算法的一種C++實現

Point2DList BaryCentricTriangleInterpolation(const Point2D& v1, const Point2D& v2, const Point2D& v3) { Point2DList result; auto minX = min({v1[0], v2[0], v3[0]}); auto maxX = max({v1[0], v2[0], v3[0]}); auto minY = min({v1[1], v2[1], v3[1]}); auto maxY = max({v1[1], v2[1], v3[1]}); Vector2f edge_1_2 = v2 - v1; Vector2f edge_1_3 = v3 - v1; for (int32_t col = (int32_t)round(minY); col <= (int32_t)round(maxY); col++) { for (int32_t row = (int32_t)round(minX); row <= (int32_t)round(maxX); row++) { Vector2f p = {(float)row, (float)col}; p = p - v1; float area1, area2; CrossProduct(area1, p, edge_1_2); CrossProduct(area2, edge_1_3, edge_1_2); auto s = area1 / area2; CrossProduct(area1, edge_1_3, p); auto t = area1 / area2; if (s >= 0.0f && t >= 0.0f && s + t <= 1.0f) { // the point is inside the triangle result.push_back(make_shared<Point2D>(p + v1)); } } } return result; }

為了便於比較，我們仍然使用上一篇的測試用例，執行的結果如下：

General Triangle Barycentric Rasterization: * ****** *********** ***************** *********************** ****************** ************** ********* **** *

可以看到，這個結果與從零開始手敲次世代遊戲引擎（五十一）是完全一樣的。

[1]關於三角形重心公式，可以參考https://en.wikipedia.org/wiki/Barycentric_coordinate_system

[i]Software Rasterization Algorithms for Filling Triangles (http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html)版權信息：GNU Free Document

推薦閱讀：