從零開始游戲開發——3.3 光柵化-有解無憂

　　在第2.5節中，通過光線追蹤的方式渲染了一個三角形，但由于速度太慢而不能直接用于實時渲染，主流方式通過光柵化的方式將圖元顯示到螢屏上，

　　在Windows上，螢屏空間坐標以左上角為（0,0）點，x軸正方向朝右，y軸正方向朝下，首先我們想要在螢屏上繪制一條線段，比較著名的時Bresenham繪直線演算法，下圖表達了當斜率小于1時，線段下一像素的位置，

在這里定義：

dx = x₁ - x₀， dy = y₁ - y₀，從而： s_i = (y₀ - y_i) + (dy / dx)(x_i + 1 - x₀)， s_i + t_i = 1，定義： d_i = dx(s_i - t_i)，從上圖中可以知道：　　當di >= 0時，距離線段最近點為(x_i + 1, y_i + 1)，此點為待繪制的點，　　當di < 0時，距離線段最近點為(x_i + 1, yi)，此點為待繪制點，實際使用時并不真接用di決定繪制點，而是通過迭代的方式減少光柵化時的浮點數計算，我們有： d_i+1 - d_i = dx(s_{i + 1} - t_{i + 1}) - dx(s_i - t_i) 　　　　　　　　　= dx(s_{i + 1} - (1 - s_{i + 1})) - dx(s_i - (1 - s_i)) = 2dx(s_{i + 1}- s_i) 　　　　　 = 2dy(x_{i + 1}- x_i) - 2dx(y_{i + 1}- y_i) 知道x_i+1 - x = 1，則d值可以通過迭代的方式進行計算： d_i+1 = d_i + 2dy ? 2dx(y_i+1 ? y_i) 這里d₀ = 2dy - dx，因此有：　　當d_i>=0，y_i+1 = y_i + 1，此時d_i+1=d_i + 2(dy - dx)，　　當di<0，y_i+1 = y_i，些時d_i+1 = d_i + 2dy，當斜率大于1時，需要計算的將是每次y值加1，下一個x的位置，具體代碼如下：

 1 void CRasterizer::DrawLine(int x0, int y0, int x1, int y1, const Color &c /* = Color(1, 0, 0, 0)*/)
 2 {
 3     // start point of the line
 4     int x = x0;
 5     int y = y0;
 6 
 7     // direction of line
 8     int dx = x1 - x0;
 9     int dy = y1 - y0;
10 
11     // Increment or decrement on direction of line
12     int sx = 0;
13     int sy = 0;
14     if (dx > 0)
15     {
16         sx = 1;
17     }
18     else if (dx < 0)
19     {
20         sx = -1;
21         dx = -dx;
22     }
23 
24     if (dy > 0)
25     {
26         sy = 1;
27     }
28     else if (dy < 0)
29     {
30         sy = -1;
31         dy = -dy;
32     }
33 
34     int ax = 2 * dx;
35     int ay = 2 * dy;
36 
37     if (dy <= dx)
38     {
39         // single step in x-direction
40         for (int decy = ay - dx; x += sx; decy += ay)
41         {
42             DrawPixel(x, y, c);
43             if (x == x1)
44             {
45                 break;
46             }
47             if (decy >= 0)
48             {
49                 decy -= ax;
50                 y += sy;
51             }
52         }
53     }
54     else
55     {
56         // single step in y-direction
57         for (int decx = ax - dy; y += sy; decx += ax)
58         {
59             DrawPixel(x, y, c);
60             if (y == y1)
61             {
62                 break;
63             }
64             if (decx >= 0)
65             {
66                 decx -= ay;
67                 x += sx;
68             }
69         }
70     }
71

　　三角形的繪制通常采用掃描線演算法，即從上到下依次進行水平掃描線方向進行光柵化操作，光柵化一個三角形，首先要計算的三角形邊上掃描線的起點和終點，這個些位置則可以通過上面的Bresenham演算法計算獲取，因為三角形是帶有頂點屬性的，

程序需要對頂點屬于進行插值計算，前面章節講到，頂點屬性在螢屏空間除以z值是線性插值的，因此這里還需要進行透視校正的計算，根據三角形的位置，需要有以下四種情況進行處理，分別為上三形、下三角形、左三角形、右三角形，

 1 void CRasterizer::DrawTriangle(Vector4f p[3], Vector3f n[3], Color c[3], Vector2f t[3])
 2 {
 3     int i0 = 0;
 4     int i1 = 1;
 5     int i2 = 2;
 6     //三角形退化為線
 7     if ((FLOAT_EQUAL(p[i0].y, p[i1].y) && FLOAT_EQUAL(p[i0].y, p[i2].y)) ||
 8         (FLOAT_EQUAL(p[i0].x, p[i1].x) && FLOAT_EQUAL(p[i0].x, p[i2].x)))
 9         return;
10 
11     //按y從小到大排序
12     if (p[i1].y < p[i0].y)
13     {
14         Utils::Swap(i0, i1);
15     }
16 
17     if (p[i2].y < p[i1].y)
18     {
19         Utils::Swap(i2, i1);
20     }
21 
22     if (p[i1].y < p[i0].y)
23     {
24         Utils::Swap(i0, i1);
25     }
26 
27     if (FLOAT_EQUAL(p[i0].y, p[i1].y))//bottom triangle
28     {
29         if (p[i1].x < p[i0].x)
30         {
31             DrawEdgeBuffer(i1, i2, p, n, c, t, _pMinEdgeBuffer);
32             DrawEdgeBuffer(i0, i2, p, n, c, t, _pMaxEdgeBuffer);
33         }
34         else
35         {
36             DrawEdgeBuffer(i0, i2, p, n, c, t, _pMinEdgeBuffer);
37             DrawEdgeBuffer(i1, i2, p, n, c, t, _pMaxEdgeBuffer);
38         }
39     }
40     else if (FLOAT_EQUAL(p[i1].y, p[i2].y)) //top triangle
41     {
42         if (p[i1].x < p[i2].x)
43         {
44             DrawEdgeBuffer(i1, i0, p, n, c, t, _pMinEdgeBuffer);
45             DrawEdgeBuffer(i2, i0, p, n, c, t, _pMaxEdgeBuffer);
46         }
47         else
48         {
49             DrawEdgeBuffer(i0, i2, p, n, c, t, _pMinEdgeBuffer);
50             DrawEdgeBuffer(i0, i1, p, n, c, t, _pMaxEdgeBuffer);
51         }
52     }
53     else
54     {
55         //p1點在掃描線位置與p0p2的交點x
56         float newX = p[i0].x + (p[i2].x - p[i0].x) * (p[i1].y - p[i0].y) / (p[i2].y - p[i0].y);
57 
58         if (p[i1].x < newX)
59         {
60             DrawEdgeBuffer(i0, i1, p, n, c, t, _pMinEdgeBuffer);
61             DrawEdgeBuffer(i1, i2, p, n, c, t, _pMinEdgeBuffer);
62             DrawEdgeBuffer(i0, i2, p, n, c, t, _pMaxEdgeBuffer);
63         }
64         else
65         {
66             DrawEdgeBuffer(i0, i2, p, n, c, t, _pMinEdgeBuffer);
67             DrawEdgeBuffer(i0, i1, p, n, c, t, _pMaxEdgeBuffer);
68             DrawEdgeBuffer(i1, i2, p, n, c, t, _pMaxEdgeBuffer);
69         }
70     }
71 
72 
73     int yMin =  MAX((int)p[i0].y, 0);
74     int yMax = MIN((int)p[i2].y, _bufferHeight - 1);
75     for (int y = yMin; y <= yMax; ++y)
76     {
77         EdgeBuffer &minEdge = _pMinEdgeBuffer[y];
78         EdgeBuffer &maxEdge = _pMaxEdgeBuffer[y];
79 
80         unsigned int offset = (unsigned int)(MAX(minEdge.X, 0) + (y - 1) * _bufferWidth);
81         unsigned int *addr = (unsigned int *)_pDrawBuffer + offset;
82         if (_pDepthBuffer)
83         {
84             float *zbuffer = _pDepthBuffer + offset;
85             if (_pSamplers)
86             {
87                 FillColor(addr, zbuffer, minEdge, maxEdge);
88             }
89             else
90             {
91                 FillColor(addr, zbuffer, minEdge, maxEdge);
92             }
93         }
94         else
95         {
96             FillColor(addr, nullptr, minEdge, maxEdge);
97         }
98     }
99 }

上述代碼是光柵化三角形的入口代碼，首先對三個頂點進行y值從小到大的排序，然后區分三角形的幾種情況記錄邊的資料，最后從最小到最大的執行掃描線演算法，DrawEdgeBuffer函式如下，利用頂點中的w值（儲存了世界坐標的z）進行透視校正并計算邊的頂點屬性，

  1 void CRasterizer::DrawEdgeBuffer(int i0, int i1, Vector4f p[3], Vector3f n[3], Color c[3], Vector2f t[3], EdgeBuffer *edgeBuffer)
  2 {
  3     int x0 = p[i0].x;
  4     int x1 = p[i1].x;
  5     int y0 = p[i0].y;
  6     int y1 = p[i1].y;
  7     float invz0 = p[i0].z;
  8     float invz1 = p[i1].z;
  9     float invw0 = 1.f / p[i0].w;
 10     float invw1 = 1.f / p[i1].w;
 11 
 12     // start point of the line
 13     int x = x0;
 14     int y = y0;
 15 
 16     // direction of line
 17     int dx = x1 - x0;
 18     int dy = y1 - y0;
 19 
 20     // Increment or decrement on direction of line
 21     int sx = 0;
 22     int sy = 0;
 23     if (dx > 0)
 24     {
 25         sx = 1;
 26     }
 27     else if (dx < 0)
 28     {
 29         sx = -1;
 30         dx = -dx;
 31     }
 32 
 33     if (dy > 0)
 34     {
 35         sy = 1;
 36     }
 37     else if (dy < 0)
 38     {
 39         sy = -1;
 40         dy = -dy;
 41     }
 42 
 43     int ax = 2 * dx;
 44     int ay = 2 * dy;
 45     
 46 
 47     float dx01 = (p[i1].x - p[i0].x) / (p[i1].y - p[i0].y);
 48     float rate = sqrt(1 + dx01 * dx01);
 49     
 50     float invDis = Utils::InvSqrt(dx * dx + dy * dy);
 51     float invdz = (invz1 - invz0) * invDis * rate;
 52     float invdw = (invw1 - invw0) * invDis * rate;
 53     float decz = invz0;
 54     float decw = invw0;
 55 
 56     Vector3f dn;
 57     Vector3f decn;
 58     Vector2f dt;
 59     Vector2f dect;
 60     Color dc;
 61     Color decc;
 62 
 63     if (n)
 64     {
 65         dn = (n[i1] * invw1 - n[i0] * invw0) * invDis * rate;
 66         decn  = n[i0] * invw0;
 67     }
 68     if (t)
 69     {
 70         dt.x = (t[i1].x * invw1 - t[i0].x * invw0) / dx;
 71         dt.y = (t[i1].y * invw1 - t[i0].y * invw0) / dy;
 72         dect = t[i0] * invw0;
 73     }
 74 
 75     if (c)
 76     {
 77         dc = (c[i1] * invw1 - c[i0] * invw0) * invDis * rate;
 78         decc =  c[i0] * invw0;
 79     }
 80 
 81     if (dy <= dx)
 82     {
 83         // single step in x-direction
 84         for (int decy = ay - dx; ;x += sx, decy += ay)
 85         {
 86             edgeBuffer[y].X = x;
 87             if (n)
 88             {
 89                 edgeBuffer[y].Normal = decn;
 90             }
 91 
 92             if (t)
 93             {
 94                 edgeBuffer[y].TexCoords = dect;
 95             }
 96 
 97             if (c)
 98             {
 99                 edgeBuffer[y].Color = decc;
100             }
101 
102             edgeBuffer[y].InvZ = decz;
103             edgeBuffer[y].InvW = decw;
104 
105             if (x == x1)
106             {
107                 break;
108             }
109 
110             if (decy >= 0)
111             {
112                 if (n)
113                 {
114                     decn = decn + dn;
115                 }
116 
117                 if (t)
118                 {
119                     dect.x += dt.x;
120                     dect.y += dt.y;
121                 }
122 
123                 if (c)
124                 {
125                     decc = decc + dc;
126                 }
127 
128                 decz += invdz;
129                 decw += invdw;
130                 
131                 decy -= ax;
132                 y += sy;
133             }
134             else
135             {
136                 if (t)
137                 {
138                     dect.x += dt.x;
139                 }
140             }
141         }
142     }
143     else
144     {
145         // single step in y-direction
146         for (int decx = ax - dy; ;y += sy, decx += ax)
147         {
148             edgeBuffer[y].X = x;
149 
150             if (n)
151             {
152                 edgeBuffer[y].Normal = decn;
153             }
154 
155             if (t)
156             {
157                 edgeBuffer[y].TexCoords = dect;
158             }
159 
160             if (c)
161             {
162                 edgeBuffer[y].Color = decc;
163             }
164 
165             edgeBuffer[y].InvZ = decz;
166             edgeBuffer[y].InvW = decw;
167 
168             if (y == y1)
169             {
170                 break;
171             }
172 
173             if (n)
174             {
175                 decn = decn + dn;
176             }
177 
178             if (t)
179             {
180                 dect.y += dt.y;
181             }
182 
183             if (c)
184             {
185                 decc = decc + dc;
186             }
187 
188             decz += invdz;
189             decw += invdw;
190 
191             if (decx >= 0)
192             {
193                 decx -= ay;
194                 x += sx;
195                 if (t)
196                 {
197                     dect.x += dt.x;
198                 }
199             }
200         }
201     }
202 }

最后利用FillColor填充掃描線顏色時，同樣要進行透視校正，當計算出當前像素處的頂點屬性插值后，將其傳入給FragmentShader處理程式：

void CRasterizer::FillColor(unsigned int *addr, float *zbuffer, const EdgeBuffer &minEdge, const EdgeBuffer &maxEdge)
{
    int count = maxEdge.X - minEdge.X;
    if (count < 0)
        count = -count;
    int x = minEdge.X;
    float invcount = 1.f / count;
    float dz = (maxEdge.InvZ - minEdge.InvZ) * invcount;
    float invz = minEdge.InvZ;
    float dw = (maxEdge.InvW - minEdge.InvW) * invcount;
    float invw = minEdge.InvW;
    Color dc = (maxEdge.Color - minEdge.Color) * invcount;
    Color c = minEdge.Color;
    Vector2f dt = (maxEdge.TexCoords - minEdge.TexCoords) * invcount;
    Vector2f t = minEdge.TexCoords;


    float realz;

    for (int i = 0; i < count; ++i)
    {
        if ((x >= 0) && (invz < *zbuffer) && (invz >= -1 && invz <= 1))
        {
            realz = 1.f / invw;
            // color + uv
            static float datas[4 + 2];
            Color &color = *((Color *)datas);
            color.a = c.a * realz;
            color.r = c.r * realz;
            color.g = c.g * realz;
            color.b = c.b * realz;
            Vector2f &texCoord = *(Vector2f *)(&color + 1);
            texCoord.x = t.x * realz;
            texCoord.y = t.y * realz;
            // fragment shader
            auto result = _OnFProgram(_pGlobalUniforms, _pUniforms, _pSamplers, datas);
            *addr = result.Get32BitColor();
            *zbuffer = invz;
        }

        x += 1;

        if (x >= _bufferWidth)
            break;
            
        invz += dz;
        invw += dw;
        c.a += dc.a;
        c.r += dc.r;
        c.g += dc.g;
        c.b += dc.b;
        t.x = t.x + dt.x;
        t.y = t.y + dt.y;

        if (x >= 0)
        {
            ++zbuffer;
            ++addr;
        }
    }
}

　　下圖為光柵化后的兩個三角形效果，光柵化三角形時，也可以采用不記錄邊的方式，將左、右三角形分割為上三角形和下角形，再執行掃描線演算法，這種方式省去了儲存邊的空間，具體代碼也上傳至了Github上，

本文來自博客園，作者：毅安，轉載請注明原文鏈接：https://www.cnblogs.com/primarycode/p/16611725.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/506141.html

標籤：其他

上一篇：acm可好玩了(6) 題解

下一篇：【人工智能基礎】鳶尾花分類 - 機器學習領域的Hello World