---
tags: Linux2020
---
# 2020q3 Homework5 (render)
contributed by < `YLowy` >

## raycaster 程式碼
額外整理成此篇 [raycaster 程式碼解釋](https://hackmd.io/@YLowy/ry-B-5x_w)

- [ ] 修正浮點數和定點數算繪程式展現的缺失，並提出改進 precision 及 accuracy 的方式
### float-point 運算缺失


:::info
分析問題點 :

只有在距離牆壁很近的情況會發生，中間的牆壁大小突然變成 0 ，所以可以朝這點觀察關於 `sso` 的程式碼。
另外變形牆壁的起點也有問題，其中`tso`也是需要觀察的地方
:::
觀察計算 sso 大小的程式碼 Trace method

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

第`51`行中，會透過計算物件與角色距離計算`*screenY ` ，也就是 sso。基本上問題點就是在段，畢竟這就是唯一計算與物體距離的程式碼。

在`distance` 無限小但不是 0 的情況下，`uint8_t` 的`*screenY `會是一個很大的數值，但是該數值最大值只能達到 255

之後的計算均會用到 ${\frac{畫在視窗牆壁大小}{視窗大小}}$ 這個比例值，然而在原始程式碼中接近至一個距離後，該比例只會為 `uint8_t`最大值 = 255，造成後面計算 `*textureStep` `*textureY`的計算出錯

#### 程式碼改進
需要改進部分有兩點 :
1. `*screenY` 為外部要牆壁的線條長度，由於需要計算多少像素，所以回傳的型態為`uint8_t`，但是當把實際 `INV_FACTOR / distance` 的時候，他已經失去原先浮點數計算該可以含括範圍，尤其在非常接近物體`distance`非常小的情況下`*screenY` 只能顯示到 255，為了確保精度應該將`INV_FACTOR / distance` 指派給一個浮點值
2. 當牆壁物件全部進入視窗時候 `sso` 應該為佔全部的視窗大小`SCREEN_HEIGHT >> 1`

修改過後 :

    if (distance > 0) {
        *screenY = INV_FACTOR / distance;
        auto txs = (INV_FACTOR / distance * 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;
    }

以上程式碼會遇到個問題 `INV_FACTOR / distance` 計算會被重複用到太多次 以及 `256 / txs`浮點數除法運算

這兩點都會造成效能低落降低 (不考慮 gcc 編譯最佳化 `-O2`)

以下為針對上述修改程式精簡版本 :

if (distance > 0) {
        
	float Screenrate = INV_FACTOR / distance;
	*screenY = static_cast<int8_t>(Screenrate);
        auto txs = (Screenrate * 2.0f);
        if (txs != 0) {
            *textureStep = (256 / txs) * 256;
            if (txs > SCREEN_HEIGHT) {
		*screenY = HORIZON_HEIGHT;
                auto wallHeight = Screenrate - HORIZON_HEIGHT;
                *textureY = wallHeight * (256 / txs) * 256;
            }
        }
    } else {
        *screenY = 0;
    }

修改過後 floating point 近處的變形已經完成


### fixed-point 邊界問題

正確情況應該要像右圖，牆壁應該要接在一起

問題分析 : 程式碼中 IsWall() 判斷邊界部分出錯

#### 程式碼改進:
`(tileX > MAP_X - 1 || tileY > MAP_Y - 1)` 改成 `(tileX >= MAP_X - 1 || tileY >= MAP_Y - 1)` 即可

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


改動完上述程式碼可以發現邊界牆壁已正確

- [ ] 輸出算繪過程的 frame rate，日後當我們進一步提升算繪程式的效率時，這會是效能評比的方式之一
## 新增 frame rate 畫面

修改部分可以看 : [GitHub](https://github.com/YLowy/raycaster)

考慮 `DrawBuffer()`對相同大小的 buffer 做繪製，該執行時間都相同，所以只需要分別測兩者 `Trace` method ，透過 bench 測得 float 以及 fixed 的 Trace 進行測量計算時間即可

這邊我做了點好玩的事，做了個frame rate 的比較圖，這樣不管角色移動到哪裡都可以透過另外的視窗觀察兩者差異
SDL 繪圖 顯示 renderer 視窗分別所需要花費時間，加上 Homework 6 提到 [Ring Buffer](https://hackmd.io/@YLowy/SkDR4AIDD#%E6%B8%AC%E9%A9%97%E4%BA%8C-ring-buffer-%E5%AF%A6%E4%BD%9C) 的概念實作下圖這樣的顯示介面 (上面為 float 下方為 fixed)

可以在模擬器中分別看出當前場景以及之前的場景在 float 以及 fixed raycaster 所需時間

透過上述程式可以清楚觀察到，在 **float 計算遠處場景時**所消耗時間會突然上升到 **顯示近處所需時間 * 1.25**，其他倒是挺穩定的

也許可以嘗試近處使用 float 計算，遠處使用 fixed 計算，不過如何判斷遠近是個問題。

:::info
這裡只做到陽春的執行時間比較，畢竟 **花費時間比較** 可能才是想知道的

之後會補這些 :
1. 座標軸以及單位
2. 框架文字
3. 改成折線圖，這樣比較有感覺
4. 修改取樣時間
:::

- [ ] 利用 tools/precalculator.cpp 產生運算表格，修改相關程式碼，使得程式碼在編譯時期才去產生運算表格，後者以標頭檔案 (generated header) 的形式存在並編譯進入主程式。換言之，檔案 raycaster_tables.h 應自 repository 移除，改用編譯時期產生

## 初始化時期產生 Table

在 fixed 的計算中常常利用到查表以獲得該距離，這個表格是透過 precalculator.cpp 產生的

:::info
你的程式碼應該透過程式碼寫出來 -不知道誰講過這句話
:::

所以若希望移除 raycaster_tables.h ，則需要透過在程式碼初始化時期先創立空間以先寫入陣列

這邊我創立一個提供查表物件 `Precal_table`

class Precal_table
{
public:
    uint16_t g_tan[256];
    uint16_t g_cotan[256];
    uint8_t g_sin[256];
    uint8_t g_cos[256];
    uint8_t g_nearHeight[256];
    uint8_t g_farHeight[256];
    uint16_t g_nearStep[256];
    uint16_t g_farStep[256];
    uint16_t g_overflowOffset[256];
    uint16_t g_overflowStep[256];
    uint16_t g_deltaAngle[SCREEN_WIDTH];

    void Precal_table_Init();

    Precal_table();
    ~Precal_table();
};

在 `main.cpp` 中會在執行遊戲前進行 `
pctable.Precal_table_Init();` 完成初始化，將查表資料寫入該物件的陣列中

之後 `raycaster_fixed.cpp` 中透過 `extern` 引用外部文件的公共變數

[GitHub](https://github.com/YLowy/raycaster) 目前已經把 raycaster_tables.h 以及 tools檔案移除，透過程式在initialize 執行時期建立所有表格資料

- [ ] 解說現有 fixed-point 實作機制，並探討前述表格產生的機制，需要提及其中的考量點

參考 [程式碼解釋](https://hackmd.io/@YLowy/ry-B-5x_w)

- [ ] 參照 C 語言：物件導向程式設計篇，透過建立共用介面 (interface) 的手法，將 raycaster 以 C99/C11 (或 gnu99/gnu11) 重寫，允許在執行時期載入 fixed-point 和 floating-point 為基礎的 renderer

- [ ] 閱讀 Doom rendering engine 和 Casting Wolf3D-style Rays with an FPGA and Arduino，解釋 raycaster 運作原理，並探討後續的改進方案，例如更換彩色的貼圖素材 (texture)、引入遊戲元素 (sprite) 等等。