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

05-19

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

來自專欄高品質遊戲開發

三角形的像素化過程

正如大家所知，在一個二維平面當中，三角形是最為基本的面圖元（面積不為零的圖元）。因此，在大多數渲染流水線（包括GPU硬體加速的渲染流水線）當中，三角形的像素化是最為基本的像素化。最為經典的三角形像素化演算法是拆分法。

拆分法的基本思路是通過將任意三角形拆分成更為容易像素化的三角形，然後分別對這些三角形進行像素化然後再將結果進行組合得到結果。

常見的拆分方法是將任意三角形拆分成為一個底面平行於x軸的三角形和一個頂面平行於x軸的三角形。因為這樣的三角形其左右兩個腰在y軸方向的長度投影是一樣的。這樣的話我們只需要按y軸方向步進，然後根據兩腰的斜率遞增/遞減x軸方向的投影長度（也稱為掃描線，Scanline）即可。

圖1-1 拆分法示意圖[i]

讓我們首先來看看上三角形（圖1-1上方）的像素化過程。我們需要首先計算出三角形兩個腰的斜率，並求其倒數；然後我們從頂點（V1）往底邊方向（V2V3）沿y軸步進，並在x軸方向起點和終點兩端疊加預先計算的倒斜率，從而得到當前y位置的掃描線長度：

代碼清單1-1 底邊平行於x軸的上三角形的像素化方法

Point2DList BottomFlatTriangleInterpolation(const Point2D& v1, const Point2D& v2, const Point2D& v3) { Point2DList result; assert(v2[1] == v3[1]); // the bottom must be flat assert(v1[1] < v2[1]); // v1 must be the top vertex auto invslope1 = (v2[0] - v1[0]) / (v2[1] - v1[1]); auto invslope2 = (v3[0] - v1[0]) / (v3[1] - v1[1]); auto start_x = v1[0]; auto end_x = v1[0]; for (int32_t scanline_y = (int32_t)round(v1[1]); scanline_y < (int32_t)round(v2[1]); scanline_y++) { for (int32_t scanline_x = (int32_t)round(start_x); scanline_x <= (int32_t)round(end_x); scanline_x++) { result.push_back(make_shared<Point2D>(Point2D({(float)scanline_x, (float)scanline_y}))); } start_x += invslope1; end_x += invslope2; } return result; }

接下來我們寫一個簡單的測試用例，用上面的演算法來像素化一個上三角形（V1V2V3）

代碼清單1-2 上三角形像素化測試用例

// raster a bottom flat triangle Point2D v1 = {5.0f, 0.0f}; Point2D v2 = {0.0f, 8.0f}; Point2D v3 = {21.0f, 8.0f}; points = BottomFlatTriangleInterpolation(v1, v2, v3); visualize(points, "Bottom Flat Triangle");

編譯執行這個測試用例，輸出結果如下：

代碼清單1-3 上三角形像素化測試用例輸出結果

Bottom Flat Triangle: * **** ****** ********* *********** ************** ***************** *******************

類似地，我們可以快速實現下三角形像素化的演算法：

代碼清單1-4 頂邊平行於x軸的下三角形像素化方法

Point2DList TopFlatTriangleInterpolation(const Point2D& v1, const Point2D& v2, const Point2D& v3) { Point2DList result; assert(v1[1] == v2[1]); // the top must be flat assert(v1[1] < v3[1]); // v3 must be the bottom vertex auto invslope1 = (v1[0] - v3[0]) / (v1[1] - v3[1]); auto invslope2 = (v2[0] - v3[0]) / (v2[1] - v3[1]); auto start_x = v1[0]; auto end_x = v2[0]; for (int32_t scanline_y = (int32_t)round(v1[1]); scanline_y <= (int32_t)round(v3[1]); scanline_y++) { for (int32_t scanline_x = (int32_t)round(start_x); scanline_x <= (int32_t)round(end_x); scanline_x++) { result.push_back(make_shared<Point2D>(Point2D({(float)scanline_x, (float)scanline_y}))); } start_x += invslope1; end_x += invslope2; } return result; }

接下來我們寫一個簡單的測試用例，用上面的演算法來像素化一個下三角形（V1V2V3）

代碼清單1-5 下三角形像素化測試用例

// raster a top flat triangle v1 = {0.0f, 0.0f}; v2 = {21.0f, 0.0f}; v3 = {12.0f, 8.0f}; points = TopFlatTriangleInterpolation(v1, v2, v3); visualize(points, "Top Flat Triangle");

下面的是用例執行的結果：

代碼清單1-6 下三角形像素化測試用例輸出結果

Top Flat Triangle:********************** ******************* ***************** ************** ************ ******** ****** *** *

好了。接下來讓我們看看如何將一個更為一般的三角形拆開稱為這兩種特殊三角形。其實對於任意一個三角形，如果我們將其頂點按照y軸大小進行排序，如果存在兩個頂點的y軸坐標一樣，那麼這個三角形就是上面所研究過的兩種情況之一。如果不存在y軸坐標一樣的頂點，那麼很容易知道一定存在一個頂點位於另外兩個頂點的y軸坐標之間，通過這個頂點作於x軸平行的直線，則將三角形切分成了上面所討論過的一個上三角形和一個下三角形。如下圖所示：

圖1-2 任意三角形的平底（上三角形）+平頂（下三角形）剖分[ii]

所以，我們只需要求出V4，然後分別對上三角形（V1V2V4）以及下三角形（V2V3V4）進行像素化就可以了。下面的程序清單給出了一種可能的實現：

代碼清單1-7 一種通過拆分法實現任意三角形的像素化的方法

void SortTriangleVerticesAccording2YAscend(Point2DPtr& pV1, Point2DPtr& pV2, Point2DPtr& pV3) { if (pV2->data[1] < pV1->data[1]) { swap(pV1, pV2); } if (pV3->data[1] < pV1->data[1]) { swap(pV1, pV3); } if (pV3->data[1] < pV2->data[1]) { swap(pV2, pV3); } } Point2DList TriangleInterpolation(const Point2D& v1, const Point2D& v2, const Point2D& v3) { Point2DList result; Point2DPtr pV1 = make_shared<Point2D>(v1); Point2DPtr pV2 = make_shared<Point2D>(v2); Point2DPtr pV3 = make_shared<Point2D>(v3); SortTriangleVerticesAccording2YAscend(pV1, pV2, pV3); // now v1.y <= v2.y <= v3.y if (pV1->data[1] == pV2->data[1]) { result = TopFlatTriangleInterpolation(*pV1, *pV2, *pV3); } else if (pV2->data[1] == pV3->data[1]) { result = BottomFlatTriangleInterpolation(*pV1, *pV2, *pV3); } else { Point2D v4 = *pV2; v4[0] = pV1->data[0] + ((pV2->data[1] - pV1->data[1]) / (pV3->data[1] - pV1->data[1])) * (pV3->data[0] - pV1->data[0]); Point2DPtr pV4 = make_shared<Point2D>(v4); if (pV4->data[0] < pV2->data[0]) { swap(pV2, pV4); } auto result1 = BottomFlatTriangleInterpolation(*pV1, *pV2, *pV4); auto result2 = TopFlatTriangleInterpolation(*pV2, *pV4, *pV3); result.reserve(result1.size() + result2.size()); result.insert(result.end(), result1.begin(), result1.end()); result.insert(result.end(), result2.begin(), result2.end()); } return result; }

接下來我們寫一個簡單的測試用例，用上面的演算法來像素化一個普通的三角形（V1V2V3）

代碼清單1-8 使用切分法進行普通三角形像素化測試用例

// raster a normal triangle v1 = {1.0f, 0.0f}; v2 = {16.0f, 9.0f}; v3 = {30.0f, 4.0f}; points = TriangleInterpolation(v1, v2, v3);visualize(points, "General Triangle");

下面是這個用例實際執行的結果：

代碼清單1-9 代碼清單4-12測試結果

General Triangle: * ****** ************* ****************** *********************** ******************* ************** ********** ****** *

在實際編寫這個代碼的時候，有幾個需要注意的地方：

1. 計算出的V4可能位於V2的左側或者右側，所以需要判斷一下，需要的話交換一下V2和V4；

2. 如果直接使用上面的上三角像素化和下三角像素化代碼，併合並結果的話，切分的地方會在兩個三角形當中各自像素化一次，合併的時候需要過濾掉一條掃描線。或者，就如同代碼清單4-11展示的那樣，將上三角y軸步進的結束條件修改為不包括底邊。

[i]圖片來源：Software Rasterization Algorithms for Filling Triangles (http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html)版權信息： Copyright (c) 2015 Bastian Molkenthin Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

[ii]圖片來源：Software Rasterization Algorithms for Filling Triangles (http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html)版權信息：同上