# 2020q3 Homework5 (render)
contributed by < `hankluo6` >
## 程式原理
### `game`
用來紀錄程式內玩家的各式資訊(分別為當前 X 座標、Y 座標以及旋轉的弧度),以及 `Move` 函式讓玩家移動。其座標範圍為 $0 \sim 30$ 單位,旋轉弧度範圍為 $0 \sim 2\pi$,超過的部份會被限制住。
特別要注意的是旋轉的座標軸是以逆時針方向增加:
![](https://i.imgur.com/SBr8KON.png)
### `render`
此程式用來將需要繪製的資訊儲存到 buffer 當中,而主要 raycasting 的部份則是由其成員 `_rc` 內的 `Trace` 函式進行。
首先會先透過 `_rc->Start` 初始化玩家資料,接著每次 `for` 迴圈都會對 Screen (指的是兩個畫面中的其中一個) 上的**每一個 column** 進行 `_rc->Trace`,並將相關參數回傳,這些參數代表螢幕上的這條 column 所要繪製的資訊。
```cpp
for (int x = 0; x < SCREEN_WIDTH; x++) {
uint8_t sso;
uint8_t tc;
uint8_t tn;
uint16_t tso;
uint16_t tst;
uint32_t *lb = fb + x;
_rc->Trace(x, &sso, &tn, &tc, &tso, &tst);
```
* `sso` 為箱子範圍的一半
* `tc` 為箱子的 texture 在該 x 位置的值
* `tn` 用來標示箱子為亮面或暗面
* `tso` 為箱子的 texture 在該 y 位置的值
* `tst` 用來計算箱子 texture 上相同紋理要重複的次數
* `lb` 為要繪製 pixel 的位置
![](https://i.imgur.com/6Otc5R1.png)
從 `g_texture8[4096]` 可以知道箱子的 texture 大小為 64 * 64 pixel,並用前 6 個 bit 選取 y 軸,後 6 個 bit 選取 x 軸,但在遊戲中箱子大小會隨著遠近而改變,且可能超過 64 pixel,此時就需要將螢幕上的多個 pixel 共用同個 texture 上的 pixel,達成放大的效果。
![](https://i.imgur.com/jRKeu2l.png)
如果仔細看 256 pixel 的 texture,會發現其中 x 與 y 座標有 4 個 pixel 在 4x4 的方格中都相同。
假設現在需要繪製 128 pixel 的箱子高度,`screenY = 64`,`txs = 128`,則 `textureStep = (256 / 128) * 256 = 512`,接著 `TraceFrame` 中可看到 `(to >> 10)` 可知道 1024 以下的數值會被 round 掉,表示 `to += ts;` 此行需跑 2 次才會更新成新的 texture pixel,此即為 `tst` 也就是 `textureStep` 的作用。
而 `textureX` 重複次數與 `textureY` 計算不同,程式的目標是把 $0 \sim 1$ 的 `hitoffset` 對應到 $0 \sim 64$ 的 texture coordinate 上,可以先看到 `*textureX = (uint8_t)(256.0f * modff(hitOffset, &dum))` 將一個範圍為 $0 \sim 1$ 的數值乘上 $256$,接著在 `TraceFrame` 中 `const auto tx = static_cast<int>(tc >> 2);` 會再將此結果除上 $4$,所以最後會得到 `hitOffset * 64`,也就是將 $0 \sim 1$ 映射到 $0 \sim 64$ 並去除掉後面兩個 bit,這樣當有箱子較近時,兩個相鄰的 column 上 `hitoffset` 會相近,對應要 $0 \sim 64$ 也會是相同的值;箱子較遠時 `hitoffset` 則較小,自然對應後的值也會不同。
```cpp
const auto tx = static_cast<int>(tc >> 2);
int16_t ws = HORIZON_HEIGHT - sso;
if (ws < 0) {
ws = 0;
sso = HORIZON_HEIGHT;
}
uint16_t to = tso;
uint16_t ts = tst;
```
因為 `HORIZON_HEIGHT` 為一半的 `SCREEN_HEIGHT`,所以 `ws` 為繪製天空及地板的長度,如果 `ws` 為 0 則表示該 column 上的 pixel 全為箱子的一部分,可以注意到天空與地板在畫面上佔有的空間的是相同的。
```cpp
for (int y = 0; y < ws; y++) {
*lb = GetARGB(96 + (HORIZON_HEIGHT - y));
lb += SCREEN_WIDTH;
}
```
繪製天空的迴圈,`lb` 每次迴圈位置增加 `SCREEN_WIDTH`,表示往下移動一個 pixel。
```cpp
for (int y = 0; y < sso * 2; y++) {
// paint texture pixel
auto ty = static_cast<int>(to >> 10);
auto tv = g_texture8[(ty << 6) + tx];
to += ts;
if (tn == 1 && tv > 0) {
// dark wall
tv >>= 1;
}
*lb = GetARGB(tv);
lb += SCREEN_WIDTH;
}
```
繪製箱子的程式在上面有介紹過了,要注意的是當 `tn` 為 1 時要畫暗色的牆壁,做法為將 pixel 上的數值除 2,這是因為 `GetARGB` 上每個 8 bit 的值皆代表其顏色的亮度。
而繪製地板的步驟則與天空同理。
### `raycaster_float`
因為在 `renderer` 中呼叫 `Start` 函式時已經將數值轉為 fixed point 形式,故這邊要在轉換回 floating point。
`Distance` 函式因其他同學有很好的解釋,故不再贅述,此函式會回傳離目標最近的箱子之距離,這邊目標將會從 `column 0` 計算到 `column SCREEN_WIDTH`,對每一個 column 我們都發射一條看不見的 ray (射線),並透過此射線判斷撞擊時的位置、距離等資訊。
`Trace` 函式將會計算所需的參數:
```cpp
float hitOffset;
int hitDirection;
float deltaAngle = atanf(((int16_t) screenX - SCREEN_WIDTH / 2.0f) /
(SCREEN_WIDTH / 2.0f) * M_PI / 4);
float lineDistance = Distance(_playerX, _playerY, _playerA + deltaAngle,
&hitOffset, &hitDirection);
float distance = lineDistance * cos(deltaAngle);
```
* `hitOffset` 會紀錄 ray 與箱子間 intersect 的位置
* `hitDirection` 紀錄為亮面或暗面(根據 ray 與箱子 intersect 為箱子的垂直面或水平面決定,與真實光線無關)
* `deltaAngle` 為 ray 與玩家視角為中心之向量角度差
* `lineDistance` 為 ray 投射最近的箱子之間的距離
* `distance` 則為 `lineDistance` 對玩家視角中心之向量的投影長度
先來理解螢幕是如何繪出畫面的,玩家會有一個視野範圍稱為 [field of view (fov)](https://en.wikipedia.org/wiki/Field_of_view),概念就是玩家從眼睛開始,能看到前方範圍的最大角度。我們需要將看到的視野投影到某個平面上,而這個平面就是我們在螢幕上看到的畫面,可以參考下圖:
![](https://i.imgur.com/hfkjUdz.jpg)
而上述玩家視野為中心之向量指的是一從玩家 Camera 到 Near plane 中心之向量。
`deltaAngle` 為目前要處理的 ray 與玩家視角間的角度,我們可以先從 `raycaster.h` 中知道 fov 為 $\frac{\pi}{2}$ 弧度,所以其一半範圍為 $\frac{\pi}{4}$ 弧度,根據 $\arctan{(\frac{\pi}{4})}=1$ 可以知道 `SCREEN_WIDTH / 2.0f` 與玩家到平面的距離相等。
而 `screenX - SCREEN_WIDTH / 2.0f` 為目前 ray 在平面上的交點與平面中心的差,在搭配上已知的視野角度,可以計算出要增加的角度應為:
```cpp
atanf((int16_t) screenX - SCREEN_WIDTH / 2.0f) / (SCREEN_WIDTH / 2.0f);
```
$$\Delta\theta = \arctan(\frac{x - W/2}{D})=\arctan(\frac{x-W/2}{W/2})$$
我認為這邊 `M_PI / 4` 是多餘的,但因為此角度對 `Distance` 的影響不大(只會影響到有象限交換時的判斷),且 `M_PI / 4` 與 `1` 差距沒有很大,目前看不出有明顯的差異。
另外我們需要對與箱子的距離 `lineDistance` 計算其與平面垂直的分量長度: `float distance = lineDistance * cos(deltaAngle);`,這是為了要解決 fisheye effect 的問題。
>根據 [Lode's Computer Graphics Tutorial](https://lodev.org/cgtutor/raycasting.html)
>
>The fisheye effect is an effect you see if you use the real distance, where all the walls become rounded, and can make you sick if you rotate.
```cpp
*textureX = (uint8_t)(256.0f * modff(hitOffset, &dum));
*textureNo = hitDirection;
*textureY = 0;
*textureStep = 0;
```
此段在上面 `textureX` 的部分有說明。
```cpp
if (distance > 0) {
*screenY = INV_FACTOR / distance;
auto txs = (*screenY * 2.0f);
if (txs != 0) {
*textureStep = (256 / txs) * 256;
if (txs > SCREEN_HEIGHT) {
auto wallHeight = (txs - SCREEN_HEIGHT) / 2;
*textureY = wallHeight * (256 / txs) * 256;
}
}
} else {
*screenY = 0;
}
```
這邊主要計算要繪製的 y 軸範圍,可以從下圖看到我們需要求出螢幕上要顯示的高度 $h$
![](https://i.imgur.com/0GkHxd0.png)
而箱子在遊戲座標中高度為 1,其一半為 0.5,透過相似三角形公式:
$$
\frac{Width/2}{distance}=\frac{h}{0.5}\\
h=\frac{Width/2}{0.5} \times \frac{1}{D}
$$
因為 $h$ 的前項為常數,可以透過 marco 預先計算,此即為 `INV_FACTOR` 的值。
:::info
上述計算出來的 `INV_FACTOR` 應該為 80,但程式內設定為 95,不知道哪邊推論錯誤。
:::
接著 `if` 部份計算依照 $h$ 的大小決定要繪製細節的程度,箱子越靠近玩家則需要繪製的紋理節點就越多,反之則越少。
### `raycaster_fixed`
`Trace` 所需參數與 `raycaster_point` 一樣,但其內部使用定點數來表示小數,用 16 bit 的 整數儲存,前 8 bit 為小數的整數部分,後 8 bit 為小數部分,而角度的部分將原本 $0 \sim 2\pi$ 映射到 $0 \sim 1024$,另外使用 `viewQuarter` 紀錄當前旋轉角度的象限、`viewAngle` 則記錄相對於該象限的旋轉角度:
```cpp
uint16_t rayAngle =
static_cast<uint16_t>(_playerA + LOOKUP16(g_deltaAngle, screenX));
```
此行與 `float` 版本的計算一樣,指示該對應的數值透過查表來取得。
```cpp
switch (rayAngle % 256) {
case 1:
case 254:
rayAngle--;
break;
case 2:
case 255:
rayAngle++;
break;
}
rayAngle %= 1024;
```
:::warning
研究中...
:::
`CalculateDistance` 與 `Distance` 的概念一樣,會回傳 ray 碰觸到的牆壁之間的 x 距離與 y 距離,將結果分別存到 `delatX` 與 `deltaY`,要注意的是內部有用到小數的部分皆為 fixed point,其中的加 256 就是 float point 中加 1 的步驟。
函式內還特別將角度為 0, 90, 180, 270 的部分拆開來算,這是因為角度為 0 不需要計算到三角函數,只需簡單的迴圈就能計算,分開運算較能提升效能。
接著計算玩家與箱子間的歐幾里德距離,與 float 版本不同的是,去除掉根號操作(效能較差),而用三角函數計算:
$$
distance = \Delta Y \times \cos \theta + \Delta X \times \sin \theta
$$
而底下的兩個 `if` 判斷式就是就是在算 `distance`,根據不同象限來計算,裡面 `INVERT` 在做 2's complement,用來將角度取負值。
```cpp
if (distance >= MIN_DIST) {
*textureY = 0;
LookupHeight((distance - MIN_DIST) >> 2, screenY, textureStep);
} else {
*screenY = SCREEN_HEIGHT >> 1;
*textureY = LOOKUP16(g_overflowOffset, distance);
*textureStep = LOOKUP16(g_overflowStep, distance);
}
```
先依據 `distance` 的值分成兩種情形,`MIN_DIST` 經過計算為 `187.5`,而 fixed point 中數值 1 代表實際數值 256,可以知道 `else` 為與箱子距離過近時的情形。當距離過近時,對應到 float 版本的 `if (txs > SCREEN_HEIGHT)`,該 column 需全部繪製箱子,所需繪製的一半高度就為 `SCREEN_HEIGHT >> 1`,而 `textureY` 與 `textureStep` 可以從 `precalculater` 中發現:
```cpp
for (int i = 1; i < 256; i++) {
auto txs = ((INV_FACTOR_INT / (float) (i / 2.0f)));
auto ino = (txs - SCREEN_HEIGHT) / 2;
g_overflowStep[i] = (256 / txs) * 256;
g_overflowOffset[i] = ino * (256 / txs) * 256;
}
```
計算方式與 float 版本一樣,其中 `i` 為 `distance`,因為原本判斷式已經限制 `distance < 256`,所以這邊計算 $1 \sim 255$ 就能涵蓋到所有此情形的數值。要特別注意的是 `INV_FACTOR_INT` 與 `i` 皆為定點數表示,而兩個定點數相除後的結果 `txs` 為**浮點數**,因為定點數的 MSB 8 bit 相除就抵銷掉原先位移的效果,所以可以直接利用 `txt` 計算 `textureY` 與 `textureStep`。
`LookupHeight` 會先將 `(distance - MIN_DIST) >> 2` 傳入到 `distance`:
```cpp
void RayCasterFixed::LookupHeight(uint16_t distance,
uint8_t *height,
uint16_t *step)
{
if (distance >= 256) {
const uint16_t ds = distance >> 3;
if (ds >= 256) {
*height = LOOKUP8(g_farHeight, 255) - 1;
*step = LOOKUP16(g_farStep, 255);
}
*height = LOOKUP8(g_farHeight, ds);
*step = LOOKUP16(g_farStep, ds);
} else {
*height = LOOKUP8(g_nearHeight, distance);
*step = LOOKUP16(g_nearStep, distance);
}
}
```
根據 `distance` 的值分成較近距離的情形與遠距離的情形,先看 `nearHeight` 與 `farHeight` 的計算方式:
```cpp
for (int i = 0; i < 256; i++) {
g_nearHeight[i] = static_cast<uint8_t>(
(INV_FACTOR_INT / (((i << 2) + MIN_DIST) >> 2)) >> 2);
g_farHeight[i] = static_cast<uint8_t>(
(INV_FACTOR_INT / (((i << 5) + MIN_DIST) >> 5)) >> 5);
}
```
如果仔細看 `LookupHeight` 會發現計算 `farHeight` 前會將 `distance` 右移 5 bit(呼叫參數時 2 bit + `ds` 3 bit) 且減去 `MIN_DIST`,對應到上面程式中的 `(i << 5) + MIN_DIST`,因此處計算需要真實的 `distance`,而非 $0 \sim 256$;`nearHeight` 也一樣要把位移的 2 bit 給補回去。而 `MIN_DIST` 後方的兩次 shift 推測是做 round 的動作。
`nearStep` 與 `farStep` 就很簡單了,計算方式與 float 版本一樣,將 `farHeight` 或 `nearHeight` 的值 * 2,並計算在 texture 中對應的位置:
```cpp
for (int i = 0; i < 256; i++) {
auto txn =
((INV_FACTOR_INT / (((i * 4.0f) + MIN_DIST) / 4.0f)) / 4.0f) * 2.0f;
if (txn != 0) {
g_nearStep[i] = (256 / txn) * 256;
}
auto txf =
((INV_FACTOR_INT / (((i * 32.0f) + MIN_DIST) / 32.0f)) / 32.0f) *
2.0f;
if (txf != 0) {
g_farStep[i] = (256 / txf) * 256;
}
}
```
:::info
為甚麼要這麼麻煩分成三段距離來算同樣的數值呢?因為對於越遠的牆壁,我們所需要的精度越低,對應到 fixed point 的 LSB 8 bit,越遠的牆壁可以將之位移去除掉部分精度。
:::
再回頭看 `LookupHeight` 應該就能理解了,而對於過遠的牆壁沒紀錄在表格內的數值,需要特別將他壓縮到 `ds = 255` 內以對應表格中最遠距離。
:::warning
`LookupHeight` 當中
```cpp
if (ds >= 256) {
*height = LOOKUP8(g_farHeight, 255) - 1;
*step = LOOKUP16(g_farStep, 255);
}
*height = LOOKUP8(g_farHeight, ds);
*step = LOOKUP16(g_farStep, ds);
```
下方應補上 `else` 才正確
:::
## 修正浮點數和定點數算繪程式展現的缺失
### 牆壁分割的問題
![](https://i.imgur.com/z7teJoa.png)
此為距離牆壁時才會發生的問題,且推測為中間 `screenY` 比真實值還小。從 `Trace` 中可發現 `*screenY = INV_FACTOR / distance;` 會發生 overflow 的問題,因 `distance 可能非常小。另外對於 `txs > SCREEN_HEIGHT` 時沒有對 `screenY` 做相對應的處理,比照 `fixed point` 版本增加 `*screenY = SCREEN_HEIGHT >> 1;` 此行。
```cpp
if (distance > 0) {
uint16_t t = INV_FACTOR / distance;
*screenY = t;
auto txs = (t * 2.0f);
if (txs != 0) {
*textureStep = (256 / txs) * 256;
if (txs > SCREEN_HEIGHT) {
*screenY = SCREEN_HEIGHT >> 1;
auto wallHeight = (txs - SCREEN_HEIGHT) / 2;
*textureY = wallHeight * (256 / txs) * 256;
}
}
} else {
*screenY = 0;
}
```
### 牆壁消失的問題
比對 fixed point 與 float point 版本就能知道:
```cpp
if (rayA <= M_PI_2) {
startDeltaX = (1 - offsetY) * tan(rayA);
startDeltaY = (1 - offsetX) / tan(rayA);
} else if (rayA <= M_PI) {
if (offsetY == 0) {
startDeltaX = (1) * fabs(tan(rayA));
} else {
startDeltaX = (offsetY) *fabs(tan(rayA));
}
startDeltaY = -(1 - offsetX) / fabs(tan(rayA));
} else if (rayA < 3 * M_PI_2) {
if (offsetY == 0) {
startDeltaX = -(1) * fabs(tan(rayA));
} else {
startDeltaX = -(offsetY) *fabs(tan(rayA));
}
if (offsetX == 0) {
startDeltaY = -(1) / fabs(tan(rayA));
} else {
startDeltaY = -(offsetX) / fabs(tan(rayA));
}
} else {
startDeltaX = -(1 - offsetY) * fabs(tan(rayA));
if (offsetX == 0) {
startDeltaY = (1) / fabs(tan(rayA));
} else {
startDeltaY = (offsetX) / fabs(tan(rayA));
}
}
```
`offsetX` 的對於 0 的判斷可以去除,當站在表格邊界上時,應要以當前表格邊界開始投射 ray,而非下個表格。
### 牆面比例不同的問題
可以發現外牆兩邊的比例不同,透過下面這張圖推測應為 fixed point 出錯,對照兩個版本的 `isWall` 可以找出判斷式的差異,修改後的程式如下:
```cpp
inline bool RayCasterFixed::IsWall(uint8_t tileX, uint8_t tileY)
{
if (tileX >= MAP_X - 1 || tileY >= MAP_Y - 1) {
return true;
}
return LOOKUP8(g_map, (tileX >> 3) + (tileY << (MAP_XS - 3))) &
(1 << (8 - (tileX & 0x7)));
}
```
### 牆壁錯位的問題
此問題在上面分析程式碼時就發現了,此處只是利用 `distance >= 256` 時的情況重現此 bug。當 `distance >= 256` 時,`LOOKUP(g_farXXXX, dx)` 將會取值到不屬於該 array 的內容:
```cpp
if (distance >= 256) {
const uint16_t ds = distance >> 3;
if (ds >= 256) {
*height = LOOKUP8(g_farHeight, 255) - 1;
*step = LOOKUP16(g_farStep, 255);
}
else {
*height = LOOKUP8(g_farHeight, ds);
*step = LOOKUP16(g_farStep, ds);
}
} else {
*height = LOOKUP8(g_nearHeight, distance);
*step = LOOKUP16(g_nearStep, distance);
}
```
:::warning
特別注意 C 及 C++ 不會有 Out Of Bounds Error,而是 Undefined Behavior!
:::
## 在編譯時期產生運算表格
使用 C++ 的 template 實現 [Template metaprogramming](https://en.wikipedia.org/wiki/Template_metaprogramming),使用 template 的技巧來讓 compiler 在編譯時期計算結果。
我們需要使用 template 來實現 loop 並產生資料,可以先從 [Wikipedia](https://en.wikipedia.org/wiki/Template_metaprogramming#Static_Table_Generation) 的例子來思考:
```cpp=
#include <iostream>
#include <array>
constexpr int TABLE_SIZE = 10;
/**
* Variadic template for a recursive helper struct.
*/
template<int INDEX = 0, int ...D>
struct Helper : Helper<INDEX + 1, D..., INDEX * INDEX> { };
/**
* Specialization of the template to end the recursion when the table size reaches TABLE_SIZE.
*/
template<int ...D>
struct Helper<TABLE_SIZE, D...> {
static constexpr std::array<int, TABLE_SIZE> table = { D... };
};
constexpr std::array<int, TABLE_SIZE> table = Helper<>::table;
enum {
FOUR = table[2] // compile time use
};
int main() {
for(int i=0; i < TABLE_SIZE; i++) {
std::cout << table[i] << std::endl; // run time use
}
std::cout << "FOUR: " << FOUR << std::endl;
}
```
要看懂上面程式之前,需先理解 [Variadic template](https://en.wikipedia.org/wiki/Variadic_template) 以及 [Partial template specialization](https://en.wikipedia.org/wiki/Partial_template_specialization),網路上相關資料很多,這邊就不再贅述。
當 compiler 看到此行時
```cpp=20
constexpr std::array<int, TABLE_SIZE> table = Helper<>::table;
```
會先尋找對應到 `Helper<>` 的 Object,發現到
```cpp=9
template<int INDEX = 0, int ...D>
struct Helper : Helper<INDEX + 1, D..., INDEX * INDEX> { };
```
此 object 為符合呼叫之結構,而需要回傳此結構前需先建構此 `struct`,故需要先繼承 `Helper<INDEX + 1, D..., INDEX * INDEX>`,而 variadic template 會自動將後方的 `INDEX * INDEX` 放入 `D...` 中呼叫(才能對應到合適的 template),持續此步驟直到 `INDEX + 1` 到達我們特化的版本:
```cpp=15
template<int ...D>
struct Helper<TABLE_SIZE, D...> {
static constexpr std::array<int, TABLE_SIZE> table = { D... };
};
```
這是因為 compile 會優先配對已有 specialization 的 template 版本,第 17 行會在此 `struct`(注意為 `struct Helper<TABLE_SIZE, D...>` 這個 object,而非 `struct Helper`) 中宣告一個 `std::array` 並將之前的所有 `INDEX + 1` 放入,建立一個 `{0, 1, 4. .... 81}` 內容的 `table` 變數。
而因為我們呼叫的 `struct Helper<>` 一直繼承到 `struct Helper<TABLE_SIZE, D...>`,故也會擁有 `table` 變數,此 `table` 即為我們的目標,且以上行為皆在 compile time 內完成。
但當我要把上述程式應用到 raycaster 中時遇到許多問題:
1. 需要計算多個 table,需要為每個 table 都建立 template 與 struct 讓程式碼雜亂
2. 有些 table 的 type 不同
3. C++11 對於 compile time 的計算有許多限制並未放寬
因為 Makefile 內定義使用 C\+\+11 來編譯,我以盡量不改動為原則來修改程式碼 (C++14 以上可使用 `constexpr` 搭配 `for` 迴圈來產生 table),
以下概念來自 stack overflow 上的 [Xeo](https://stackoverflow.com/a/13315884/819272), [TemplateRex](https://stackoverflow.com/a/19023500) 及 [dyp](https://stackoverflow.com/a/19016627) 的答案。
先看底下程式碼:
```cpp
template<unsigned... Is> struct seq{};
template<unsigned N, unsigned... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>{};
template<unsigned... Is>
struct gen_seq<0, Is...> : seq<Is...>{};
template<unsigned... Is>
constexpr Table MagicFunction(seq<Is...>){
return {{ whichCategory(Is)... }};
}
constexpr Table MagicFunction(){
return MagicFunction(gen_seq<128>{});
}
```
與上方一開始介紹的方法很像,差別在於我們不需要使用成員變數來存參數,而是將參數儲存在 `struct seq` 的 **`Parameter Pack`** 當中,而當我們要使用這些參數時,呼叫 `whichCategory(Is)...` 會將 parameter pack 展開並對每個參數執行 `whichCategory`。
以下舉個例子,假設現在 parameter pack 中儲存參數 `Is...` 為 `{0, 1, 2, 3}`:
```cpp
unsigned square(unsigned a)
return a * a;
template<unsigned... Is>
constexpr Table MagicFunction(seq<Is...>){
return {{ square(Is)... }};
}
```
當 `MagicFunction` 的參數 `seq<Is...>` 準備好時,`return` 會展開成以下:
```cpp
return {{ square(0), square(1), square(2), square(3) }};
```
:::warning
找不到相關文件說明此種用法...
:::
接著可以把 function 當成 parameter 傳入 template 中,就能解決需要計算不同 table 的問題:
```cpp
template<typename Generator, std::size_t... Is>
constexpr auto MagicFunction(Generator g, seq<Is...>)
-> std::array<decltype(g(std::size_t{})), sizeof...(Is)>
{
return {{g(Is)...}};
}
call MagicFunction(g, gen_seq<5>{});
```
上面程式碼將自定義 function `g` 傳入,並使用 Arrow operator 來回傳參數,這樣可以根據 function `g` 決定需要的參數,解決 type 不同的問題,[`sizeof...`](https://en.cppreference.com/w/cpp/language/sizeof...) 則用來取得 Parameter pack 中的**參數數量**。
:::info
C++11 對 function declaration 引入新的語法:
`auto` identifier `(` argument-declarations... `)` `->` return_type
:::
C++14 提供了兩個神奇的 template class: [`std::index_sequence`](https://en.cppreference.com/w/cpp/utility/integer_sequence) 及 `std::make_index_sequence`,其中 `std::make_index_sequence<>` 等同於上方 `gen_seq<>`;而 `std::index_sequence<>` 則相當於上方的 `seq<>`,差別在於 `std::index_sequence<>` 內部已經處理完中間 recursive 的部分,直接回傳最後的 parameter pack。
雖然這些是 C++14 才有的功能,但能在 [Boost](https://gitlab.com/redistd/integer_seq/blob/master/integer_seq.h) 內找到 C\+\+11 版本的實作。
接著就是將上述功能實現:
```cpp
template<class Function, std::size_t... Indices>
constexpr auto make_array_helper(Function f, std::index_sequence<Indices...>)
-> std::array<typename std::result_of<Function(std::size_t)>::type, sizeof...(Indices)>
{
return {{ f(Indices)... }};
}
template<int N, class Function>
constexpr auto make_array(Function f)
-> std::array<typename std::result_of<Function(std::size_t)>::type, N>
{
return make_array_helper(f, std::make_index_sequence<N>{});
}
```
[`std::result_of<>::type`](https://en.cppreference.com/w/cpp/types/result_of) 與 [`decltype`](https://en.cppreference.com/w/cpp/language/decltype) 的用法差不多,這邊使用 `std::result_of<>` 來減少程式碼。要建立 table 時只需將 function `f` 以及 table 的 entry 數量 `N` 傳入 `make_array` 當中,就會回傳所需的 `std::array` 物件,注意到我們只需兩個 template function 以及所需 table 的計算 function 就好。
因為 table 改成 `std::array` 而非 c type array,故 `raycaster_fixed.cpp` 中的 `MulTan` 以及 `AbsTan` 參數也需一併修改。
要注意 C++11 中 `constexpr function` 的[限制](https://en.cppreference.com/w/cpp/language/constexpr):
>the function body must be either deleted or defaulted or contain only the following:
>* null statements (plain semicolons)
>* static_assert declarations
>* typedef declarations and alias declarations that do not >* define classes or enumerations
>* using declarations
>* using directives
>* if the function is not a constructor, exactly one return statement
在 raycaster 中計算 Table 的方法都很單純,使用 conditional operator `?:` 都能解決。
最後只需將此產生 table 的程式碼在編譯時期產生,我將程式碼全部放入 Makefile 中,並在編譯時期透過 Makefile 產生 `raycaster_tables.h` 檔案並接著編譯此檔案。
以上實作已提交到 [Github](https://github.com/hankluo6/raycaster/commit/59e5eac2d235663d5f5302c82a39a5b303f47c4b) 上,並移除 `raycaster_tables.h` 檔案,可以透過 `make` 來觀看產生檔案的結果,==注意 `make` 前必須沒有 `raycaster_tables.h` 存在,可使用 `make clean` 移除==。
最後,可以將資料依照 `precalculator.cpp` 輸出成表格,並使用指令 `cmp raycaster_tables.h my_table.h` 比較兩者是否有差異。
:::info
`raycaster_tables.h` 將內部含有 `<cmath>` 中 built in function 的 function 設定為 `constexpr`,但 `<cmath>` 定義的這些 function 卻不是 `constexpr`,原則上應該會造成編譯錯誤。但 `gcc` 能夠將某些 builtin function 視為 constexpr,故不會產生錯誤。
參考:
* [Is gcc considering builtins of non-constant expression functions to be constant expressions](https://stackoverflow.com/questions/22182432/is-gcc-considering-builtins-of-non-constant-expression-functions-to-be-constant#comment44214059_27906899)
* [Is it a conforming compiler extension to treat non-constexpr standard library functions as constexpr?](https://stackoverflow.com/questions/27744079/is-it-a-conforming-compiler-extension-to-treat-non-constexpr-standard-library-fu)
* [Bug 49813 - [C++0x] sinh vs asinh vs constexpr](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49813)
:::
## 輸出算繪過程的 frame rate
可以先找到程式中主要進行迴圈的部份,其紀錄迴圈的間隔時間就是 fps,SDL 提供了兩個高精度紀錄時間的函式:
```cpp
Uint64 SDL_GetPerformanceCounter(void)
int64 SDL_GetPerformanceFrequency(void)
```
其中 `SDL_GetPerformanceCounter` 用系統內的 performance counter 紀錄次數,而 `SDL_GetPerformanceFrequency` 則紀錄了 1 秒內 counter 運行的次數。
```cpp
while (!isExiting) {
...
const auto nextCounter = SDL_GetPerformanceCounter();
const auto seconds = (nextCounter - tickCounter) /
static_cast<float>(tickFrequency);
printf("%2.4f fps\n", 1 / seconds);
...
}
```
所以原程式內的 `seconds` 已是紀錄前次迴圈與這次迴圈運行的時間,其倒數就為 frame rate。
###### tags: `linux2020`