# 2020q3 Homework5 (render)

contributed by < `hankluo6` >

## 程式原理

### `game`

用來紀錄程式內玩家的各式資訊(分別為當前 X 座標、Y 座標以及旋轉的弧度)，以及 `Move` 函式讓玩家移動。其座標範圍為 $0 \sim 30$ 單位，旋轉弧度範圍為 $0 \sim 2\pi$，超過的部份會被限制住。

特別要注意的是旋轉的座標軸是以逆時針方向增加：

### `render`

此程式用來將需要繪製的資訊儲存到 buffer 當中，而主要 raycasting 的部份則是由其成員 `_rc` 內的 `Trace` 函式進行。

首先會先透過 `_rc->Start` 初始化玩家資料，接著每次 `for` 迴圈都會對 Screen (指的是兩個畫面中的其中一個) 上的**每一個 column** 進行 `_rc->Trace`，並將相關參數回傳，這些參數代表螢幕上的這條 column 所要繪製的資訊。

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 的位置


從 `g_texture8[4096]` 可以知道箱子的 texture 大小為 64 * 64 pixel，並用前 6 個 bit 選取 y 軸，後 6 個 bit 選取 x 軸，但在遊戲中箱子大小會隨著遠近而改變，且可能超過 64 pixel，此時就需要將螢幕上的多個 pixel 共用同個 texture 上的 pixel，達成放大的效果。


如果仔細看 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` 則較小，自然對應後的值也會不同。

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 全為箱子的一部分，可以注意到天空與地板在畫面上佔有的空間的是相同的。

for (int y = 0; y < ws; y++) {
    *lb = GetARGB(96 + (HORIZON_HEIGHT - y));
    lb += SCREEN_WIDTH;
}

繪製天空的迴圈，`lb` 每次迴圈位置增加 `SCREEN_WIDTH`，表示往下移動一個 pixel。

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` 函式將會計算所需的參數：

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)，概念就是玩家從眼睛開始，能看到前方範圍的最大角度。我們需要將看到的視野投影到某個平面上，而這個平面就是我們在螢幕上看到的畫面，可以參考下圖：

而上述玩家視野為中心之向量指的是一從玩家 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 在平面上的交點與平面中心的差，在搭配上已知的視野角度，可以計算出要增加的角度應為：

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.

*textureX = (uint8_t)(256.0f * modff(hitOffset, &dum));
*textureNo = hitDirection;
*textureY = 0;
*textureStep = 0;

此段在上面 `textureX` 的部分有說明。

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$

而箱子在遊戲座標中高度為 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` 則記錄相對於該象限的旋轉角度：

uint16_t rayAngle =
        static_cast<uint16_t>(_playerA + LOOKUP16(g_deltaAngle, screenX));

此行與 `float` 版本的計算一樣，指示該對應的數值透過查表來取得。

    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，用來將角度取負值。

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` 中發現：

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`：

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` 的計算方式：

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 中對應的位置：

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` 當中

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` 才正確
:::

## 修正浮點數和定點數算繪程式展現的缺失

### 牆壁分割的問題

此為距離牆壁時才會發生的問題，且推測為中間 `screenY` 比真實值還小。從 `Trace` 中可發現 `*screenY = INV_FACTOR / distance;` 會發生 overflow 的問題，因 `distance 可能非常小。另外對於 `txs > SCREEN_HEIGHT` 時沒有對 `screenY` 做相對應的處理，比照 `fixed point` 版本增加 `*screenY = SCREEN_HEIGHT >> 1;` 此行。

 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 版本就能知道：

    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` 可以找出判斷式的差異，修改後的程式如下：

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 的內容：

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) 的例子來思考：

#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 看到此行時

constexpr std::array<int, TABLE_SIZE> table = Helper<>::table;

會先尋找對應到 `Helper<>` 的 Object，發現到

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` 到達我們特化的版本：

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) 的答案。
先看底下程式碼：

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}`：

unsigned square(unsigned a)
    return a * a;
    
template<unsigned... Is>
constexpr Table MagicFunction(seq<Is...>){
    return {{ square(Is)... }};
}

當 `MagicFunction` 的參數 `seq<Is...>` 準備好時，`return` 會展開成以下：

return {{ square(0), square(1), square(2), square(3) }};

:::warning
找不到相關文件說明此種用法...
:::

接著可以把 function 當成 parameter 傳入 template 中，就能解決需要計算不同 table 的問題：

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 版本的實作。

接著就是將上述功能實現：

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 提供了兩個高精度紀錄時間的函式：

Uint64 SDL_GetPerformanceCounter(void)
int64 SDL_GetPerformanceFrequency(void)

其中 `SDL_GetPerformanceCounter` 用系統內的 performance counter 紀錄次數，而 `SDL_GetPerformanceFrequency` 則紀錄了 1 秒內 counter 運行的次數。

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`