# 2020q3 Homework5 (render)
contributed by < `ccs100203` >

###### tags: `linux2020`
> [I07: render](https://hackmd.io/@sysprog/2020-render)

## Raycasting
raycasting 的原理是在 screen 範圍內打出一條條的光線，偵測物體距離，藉此把 2D 轉為 3D


在專案內 `renderer.cpp` 中的 `TraceFrame` 實現此原理
用 `x` 去模擬每一條光線

for (int x = 0; x < SCREEN_WIDTH; x++)

:::warning
嘗試將原理補充的更詳細
:::

## Fixing Bugs
### 1. 接近牆面時 floating-point 運算缺失 (Overflow)

floating-point 的計算主要由 `raycaster_float.cpp` 負責，`void RayCasterFloat::Trace` 即是負責計算每條光線 (每個 column)。由於這是在貼近牆面時出現的 bug，研判跟 `distance` (與牆面的距離) 有關聯，所以在程式中找尋使用到 `distance` 的地方。
接著在程式中發現以下問題，151 行的除法，很可能在 `distance` 是一個小於 1 的值出問題。觀察三個變數的 type，會發現當 `INV_FACTOR / distance` 大於 255 時就會發生 overflow，導致 render 錯誤。

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

uint8_t *screenY;
#define INV_FACTOR (float) (SCREEN_WIDTH * 95.0f / 320.0f)
float distance = lineDistance * cos(deltaAngle);

我不懂這裡的運作原理，只好純粹對 overflow 的問題做修正。
- 為了讓 `txs` 得到正確的值，我設立了一個 `tmp` 作為 `INV_FACTOR / distance` 的答案。這樣已經有效修正 `txs` 產生錯誤的情況
- 再來的問題是 `screenY` 應該設為多少
觀察 renderer.cpp 內的程式，其中 `sso` 即為 `screenY`，發現當 `sso` 大於 `HORIZON_HEIGHT` 時會被修正為 `HORIZON_HEIGHT`。而在 `Trace` 內會發生此情況，代表 `txs > SCREEN_HEIGHT` 成立，因為 `txs` 原先應為 `*screenY * 2.0f`，而 `HORIZON_HEIGHT` 又等同 `SCREEN_HEIGHT / 2`。所以在此條件成立時將 `screenY` 設為 `HORIZON_HEIGHT;`

int16_t ws = HORIZON_HEIGHT - sso;
if (ws < 0) {
    ws = 0;
    sso = HORIZON_HEIGHT;
}

以下是改良後的版本

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

- 改良後的結果


### 2. fixed-point 在角落往內看會出現奇怪牆面 (`else` Condition Missing)
因為跑到邊邊才能看到這個 bug，所以推斷是在 `distance` 處在邊界時才會發生

由 raycaster_fixed.cpp 處理 fixed-point 的計算，一樣在程式內尋找使用 `distance` 的地方。
- 在 `LookupHeight` 內有處理 `distance` 在邊界時的情況
發現在 76 行有判斷式不周全的情況，即便 `if (ds >= 256)` 成立也會在接下來的運算把正確的值覆蓋掉，所以把缺少的 else 補上

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

改良後的程式

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);
        }else {
            *height = LOOKUP8(g_farHeight, ds);
            *step = LOOKUP16(g_farStep, ds);
        }        
    } else {
        *height = LOOKUP8(g_nearHeight, distance);
        *step = LOOKUP16(g_nearStep, distance);
    }
}

- 改良後的結果


### 3. floating-point 在邊界往外看牆面會消失 (`delta` is wrong)


後來經過測試發現是在 `playerX` 或 `playerY` 有趨近 1.0 的情況時就會發生牆面消失，反之則不會


研判是在計算 distance 時出現問題，為了了解 distance 計算方式，從 [Wolfenstein 3D's map renderer](https://www.youtube.com/watch?v=eOCQfxRQ2pY) 去釐清原理。

在 raycaster_float.cpp 中測試，經過實驗發現在 `offsetX` 或 `offsetY` 等於 0 時會發生此情形。影片中 $xIntercept = x + dx + -dy / \tan(\theta)$ 對應到程式內的 `float interceptX = rayX + startDeltaX;`。而 `offset` 是影響到 `startDelta` 的關鍵，所以在決定 `startDeltaX` 和 `startDeltaY` 的值時出問題。

這邊看到程式在 offset 為 0 時會特別處理

if (offsetY == 0) {
    startDeltaX = (1) * fabs(tan(rayA));
} else {
    startDeltaX = (offsetY) *fabs(tan(rayA));
}

我認為這樣很奇怪，按照式子來看 $-dy / \tan(\theta)$ 應該為 0，這邊卻是 $(1) * fabs(\tan(\theta))$。所以對式子進行修正，將 1 改為 0

if (offsetY == 0) {
    startDeltaX = (0) * fabs(tan(rayA));
} else {
    startDeltaX = (offsetY) *fabs(tan(rayA));
}

發現原本的問題解決了，於是接著精簡程式碼。當 if 成立時 offset 必定是 0，所以整個判斷式變得多餘，直接保留 else 內部的運算就好。

這邊是全部修改完的程式

float startDeltaX, startDeltaY;
if (rayA <= M_PI_2) {
    startDeltaX = (1 - offsetY) * tan(rayA);
    startDeltaY = (1 - offsetX) / tan(rayA);
} else if (rayA <= M_PI) {
    startDeltaX = (offsetY) *fabs(tan(rayA));
    startDeltaY = -(1 - offsetX) / fabs(tan(rayA));
} else if (rayA < 3 * M_PI_2) {
    startDeltaX = -(offsetY) *fabs(tan(rayA));
    startDeltaY = -(offsetX) / fabs(tan(rayA));

} else {
    startDeltaX = -(1 - offsetY) * fabs(tan(rayA));
    startDeltaY = (offsetX) / fabs(tan(rayA));
}

- 修改後的結果


### 4. 在邊界的牆面比例不同 (wall position is wrong)


經過實驗後發現只有在 `playerX` 或 `playerY` 為最大值 (約 30) 時會發生這種情形，也就是圖上的紅色牆面，而在綠色牆面是正常的。


藉由這張圖發現 fixed-point 判斷邊界牆面的位置時出現問題，明顯可以看出左邊的牆面 (邊界)，應往內 (右) 一格。


已經知道問題是判斷牆面的位置出錯，所以去找程式內的 `IsWall`，來比較一下 fixed-point 與 floating-point 的 `IsWall`

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

- raycaster_float.cpp

bool RayCasterFloat::IsWall(float rayX, float rayY)
{
    float mapX = 0;
    float mapY = 0;
    float offsetX = modff(rayX, &mapX);
    float offsetY = modff(rayY, &mapY);
    int tileX = static_cast<int>(mapX);
    int tileY = static_cast<int>(mapY);

    if (tileX < 0 || tileY < 0 || tileX >= MAP_X - 1 || tileY >= MAP_Y - 1) {
        return true;
    }
    return g_map[(tileX >> 3) + (tileY << (MAP_XS - 3))] &
           (1 << (8 - (tileX & 0x7)));
}

因為已經知道會在 X 或 Y 在最大值時出現問題，於是推斷在與 `MAP_X` 或 `MAP_Y` 比較時有錯誤，因為這兩個變數代表著地圖的右邊界與上邊界。

繼續觀察可以發現兩份程式的判斷式不同，一個是 `>` 一個是 `>=`，顯然這就是造成牆面位置相差 1 的原因。

// fixed
if (tileX > MAP_X - 1 || tileY > MAP_Y - 1)
// float
if (tileX < 0 || tileY < 0 || tileX >= MAP_X - 1 || tileY >= MAP_Y - 1)

因為現在出問題的是 fixed-point 的牆面，所以把他的判斷式修正成 `>=`，下面是修正後的程式

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

- 修正後的結果


#### 解釋為什麼認為出問題的是 fixed-point 而不是 floating-point

觀察以下的圖片



第一張是綠色的牆面，也就是正常的牆面
第二張是紅色的牆面，也就是異常的牆面

可以看出牆面在畫面中的比例，floating-point 是維持一致的，但是 fixed-point 的牆面比例明顯改變，故我認為判斷條件寫錯的是 fixed-point。

## 在編譯時期產生 Table

TODO