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

而上述玩家視野為中心之向量指的是一從玩家 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);

$$\mathrm{\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

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，透過相似三角形公式：

$$\begin{gathered} \frac{Width/2}{distance}=\frac{h}{0.5} \\ h=\frac{Width/2}{0.5}\times \frac{1}{D} \end{gathered}$$
因為

$h$ 的前項為常數，可以透過 marco 預先計算，此即為 INV_FACTOR 的值。

上述計算出來的 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;

研究中…

CalculateDistance 與 Distance 的概念一樣，會回傳 ray 碰觸到的牆壁之間的 x 距離與 y 距離，將結果分別存到 delatX 與 deltaY，要注意的是內部有用到小數的部分皆為 fixed point，其中的加 256 就是 float point 中加 1 的步驟。

函式內還特別將角度為 0, 90, 180, 270 的部分拆開來算，這是因為角度為 0 不需要計算到三角函數，只需簡單的迴圈就能計算，分開運算較能提升效能。

接著計算玩家與箱子間的歐幾里德距離，與 float 版本不同的是，去除掉根號操作(效能較差)，而用三角函數計算：

$$distance=\mathrm{\Delta }Y\times \cos \theta +\mathrm{\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;
    }
}

為甚麼要這麼麻煩分成三段距離來算同樣的數值呢？因為對於越遠的牆壁，我們所需要的精度越低，對應到 fixed point 的 LSB 8 bit，越遠的牆壁可以將之位移去除掉部分精度。

再回頭看 LookupHeight 應該就能理解了，而對於過遠的牆壁沒紀錄在表格內的數值，需要特別將他壓縮到 ds = 255 內以對應表格中最遠距離。

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);
}

特別注意 C 及 C++ 不會有 Out Of Bounds Error，而是 Undefined Behavior！

在編譯時期產生運算表格

使用 C++ 的 template 實現 Template metaprogramming，使用 template 的技巧來讓 compiler 在編譯時期計算結果。

我們需要使用 template 來實現 loop 並產生資料，可以先從 Wikipedia 的例子來思考：

#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 以及 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, TemplateRex 及 dyp 的答案。
先看底下程式碼：

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) }};

找不到相關文件說明此種用法…

接著可以把 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... 則用來取得 Parameter pack 中的參數數量。

C++11 對 function declaration 引入新的語法：
auto identifier ( argument-declarations… ) -> return_type

C++14 提供了兩個神奇的 template class： std::index_sequence 及 std::make_index_sequence，其中 std::make_index_sequence<> 等同於上方 gen_seq<>；而 std::index_sequence<> 則相當於上方的 seq<>，差別在於 std::index_sequence<> 內部已經處理完中間 recursive 的部分，直接回傳最後的 parameter pack。

雖然這些是 C++14 才有的功能，但能在 Boost 內找到 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 與 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 的限制：

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 上，並移除 raycaster_tables.h 檔案，可以透過 make 來觀看產生檔案的結果，注意 make 前必須沒有 raycaster_tables.h 存在，可使用 make clean 移除。

最後，可以將資料依照 precalculator.cpp 輸出成表格，並使用指令 cmp raycaster_tables.h my_table.h 比較兩者是否有差異。

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
• Is it a conforming compiler extension to treat non-constexpr standard library functions as constexpr?
• Bug 49813 - [C++0x] sinh vs asinh vs constexpr

輸出算繪過程的 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