2020q3 Homework5 (render)

contributed by < ccs100203 >

tags: linux2020

I07: render

Raycasting

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

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

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

嘗試將原理補充的更詳細

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 去釐清原理。

在 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)\ast 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