2020q3 Homework5 (render)

contributed by < sammer1107 >

tags: 進階電腦系統理論與實作

程式原理

Class Renderer

這個 class 負責根據一個 Game 物件的狀態來算繪遊戲場景。Renderer 內固定有一個 RayCaster，讓 Renderer 可以使用他來計算場景。

GetARGB 方法

inline static uint32_t GetARGB(uint8_t brightness)
{
    return (brightness << 16) + (brightness << 8) + brightness;
}

這個方法從一個亮度值來創造一個 ARGB 像素，ARGB 的值單純就只是複製亮度 brightness 而已。而 A,R,G 和 B 各用 8 bit 來表示，一起放在一個 32 bit 整數內，所以可以用 shift operator << 來設定。

TraceFrame

void TraceFrame(Game *g, uint32_t *frameBuffer);

這個方法根據傳遞的 Game 物件，會利用 RayCaster 計算場景，然後畫到 frameBuffer 上。

這裡 frameBuffer 是一個以一維型式儲存的二維陣列，大小為 SCREEN_WIDTH * SCREEN_HEIGHT。儲存方式為 row major。

_rc->Start(static_cast<uint16_t>(g->playerX * 256.0f),
               static_cast<uint16_t>(g->playerY * 256.0f),
               static_cast<int16_t>(g->playerA / (2.0f * M_PI) * 1024.0f));

首先開始算繪場景前，我們先將 RayCaster 初始化在玩家目前位置。這裡將 x,y 座標乘以 256 是為了轉成 fixed point 格式，如果 RayCaster 實作為浮點數版本，則會在 Start 內將格式還原為 floating point。

再來我們將掃過所有的 x ，在每個 x 把整條垂直線畫出來。再這之前，我們先看 Trace 方法回傳的變數們，這些變數提供我們畫出畫面中某條垂直線所需要的資訊：

for (int x = 0; x < SCREEN_WIDTH; x++) {
        uint8_t sso; // half of the height of the wall to draw in this vertical stripe
        uint8_t tc; // texture x coordinate, 2 bit fix point
        uint8_t tn; // texture number of hitted wall
        uint16_t tso; // texture y coord to start from, 10 bit fixed point
        uint16_t tst; // how many step in texture for each screen pixel, 10 bit fixed point
        uint32_t *lb = fb + x;
        
        _rc->Trace(x, &sso, &tn, &tc, &tso, &tst);
        ...

• 整個視窗的高度為 SCREEN_HEIGHT，SCREEN_HEIGHT/2 則為 HORIZON_HEIGHT。紅色線畫的就是畫面中線。
• sso 為在當前這個垂直線上，我們要繪製的牆壁頂點到畫面中線的距離，整個牆的高度就是 2*sso。牆的高度是可能會比畫面還高的，例如圖的右邊的部份。故我們有這一段 code:
  ​​​​int16_t ws = HORIZON_HEIGHT - sso;
  ​​​​if (ws < 0) {
  ​​​​    ws = 0;
  ​​​​    sso = HORIZON_HEIGHT;
  ​​​​}
  

  如果牆比畫面高，則設定 sso 為 HORIZON_HEIGHT，ws 則為畫面頂部到牆頂部的距離。
• tc 為 2 bit 小數的定點數，他告訴我們這一個 x 對應到的 texture x 座標。

  牆面的 texture 定義在 raycaster_data.h 中的 g_texture8，為

  $64\times 64$ 的亮度矩陣。

  因為我們的遊戲引擎非常簡單，人物不會站斜的，因此例如在繪製圖中第 1 條紫色線時，就只會用到 texture 中 x=0 的座標。
• tn: 為 texture 的編號，這裡是方便之後可以擴充出不同的牆面材質，所以回傳光線碰撞到的牆面種類。目前實作中並沒有不同的牆面，而是在與 x 軸垂直的牆面回傳 1 ，另一方向則回傳 0，如此我們可以畫出不同亮度的牆面（或是做其他操作）。
• tso 為 10 bit 定點數，他告訴我們在某條垂直線上，開始繪製牆面時的 texture y 軸座標從何開始。如果牆有完整出現再畫面中，如圖中兩條紫色線，則 tso=0。否則在牆不能容入畫面時，如圖中右邊， tso 必須從中間某個值開始。
• tst 也為 10 bit 定點數，他告訴我們在繪製牆面時，我每往下一個 screen pixel 時，對應到移動多少牆面的 pixel。這會與距離有關：
  • 假如牆很遠，則我們高 64 的牆面材質，可能只佔了畫面中 30 個 pixel，如此
    $\text{tst}=64/30$。
  • 牆很近時，一個牆壁的 pixel 可能會佔了畫面中好幾個 pixel，此時
    $\text{tst}<1$

有了這些資訊，我們就可以畫出一條垂直線了。

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

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

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

1. 第一個迴圈我們先畫天空的漸層。
2. 第二個迴圈畫牆面
   • 因為 to 與 ts 為 10 bit 定點數，所以要做 >> 10 的動作。
   • 因為 texture 為
     $64\times 64$，所以像素位置是取 ty*64 + tx 並且用 << 取代乘法。
   • 如果 texture number (tn) 為 1 ，我們就把亮度除以 2。如此來在與 x 軸垂直的牆面畫出暗面。
3. 第三個迴圈畫地板漸層

在每個 x 上畫完垂直線後，就完成整個畫面的繪製了。

Class RayCasterFloat

IsWall 方法

這個函數接收 rayX 與 rayY ，然後到地圖中查找這個位置是不是牆壁。

bool RayCasterFloat::IsWall(float rayX, float rayY, float rayA)
{
    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)));
}

首先我們要先了解地圖與座標系統的運作，觀察此函式與 g_map 定義之後，我得出以下推論：

• 地圖定義在 raycaster_data.h 的 g_map 中。根據 MAP_X 與 MAP_Y 的定義，這個地圖為
  $32\times 32$ 大小。
• g_map 使用一個 bit 來代表某個位置
  $1\times 1$ 的方格內是不是牆壁塊。
• g_map 中每個元素為 uint8_t，4 個一組就是 x 方向的完整一排，共有 32 個 bit。每個 byte 中的 MSB 對應的 x 最小。所以整個 g_map 有
  $32\times 4$ 個元素。
• 所以看到程式 13 行的部份，根據 tileX 與 tileY 我們要查找對應的方塊，需將 tileX 除以 8(bit) ，加上 tileY 乘以 4 (一個 row 有 4 byte) 來找到對應的 byte。 然後再用 bitwise operation 抓出對應的 bit。但原程式應該是寫錯了，假如 tileX & 0x7 為 0，我們會作 g_map[...] & (1 << 8)，如此並不會抓到我們想要的 MSB。故 8 應改成 7。
• 另外這裡地圖邊界的判定 tileX >= MAP_X - 1 與 fixed point 實作不一致。若 tileX 為 31 ，我們仍應該到地圖查找而不是直接回傳，所以這裡應該改成 tile > MAP_X - 1。

修正後的實作

bool RayCasterFloat::IsWall(float rayX, float rayY, float rayA)
{
    int tileX = static_cast<int>(rayX);
    int tileY = static_cast<int>(rayY);

    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 << (7 - (tileX & 0x7)));
}

• 修正了上面提到的邊界判斷與 bitmap off-by-one 問題
• 因為編譯器一直抱怨 offsetX, offsetY 沒被用到，所以改為上面的實作。直接利用 float 轉 int 會 truncate 的性質。

Distance 方法

這個方法根據 playerX,playerY 與 rayA 來發射出光線，並回傳碰撞方向與位置，回傳資訊有兩種可能：

Distance	碰撞方向(hitDirection)	hitoffset
$>0$	碰撞面垂直 x 軸 (1)	碰撞點 y 值
$>0$	碰撞面垂直 y 軸 (0)	碰撞點 x 值

Distance	特殊情況
$=0$	因為浮點數計算誤差 導致撞不到方塊

地圖座標系統
在進入 Distance 的細節前，首先我們要了解 x, y, angle 的座標系統。 要注意的是這裡的角度從 y 軸出發，順時針繞一圈。

程式一開始先做了一些前置準備：

int tileStepX = 1;
int tileStepY = 1;
float tileX = 0;
float tileY = 0;
if (rayA > M_PI) {
    tileStepX = -1;
}
if (rayA > M_PI_2 && rayA < 3 * M_PI_2) {
    tileStepY = -1;
}

float rayX = playerX;
float rayY = playerY;
float offsetX = modff(rayX, &tileX);
float offsetY = modff(rayY, &tileY);

• tileStepX, tileStepY 可以看成光線的 x,y 方向，如果光線角度 rayA
  $=\theta >\pi$，則 x 上是
  $-1$。如果
  $\frac{1}{2}\pi <\theta <\frac{3}{2}\pi$，則 y 方向是
  $-1$。反之方向為正則設為
  $+1$。
• tileX, tileY 為出發位置的座標的整數部份，offset 則為小數部份。e.g. rayX,rayY = 0.102, 23.75，則 tileX, tileY = 0,23， offsetX, offsetY = 0.102, 0.75

---

再來則計算此光線發射出去會最先碰到的垂直線(平行 y 軸)與水平線(平行 x 軸)。到達水平面要走的 x 距離為 startDeltaX,到達垂直面要走的 y 則為startDeltaY。

• 在上圖中可以看到所有與垂直線的交點為粉色，與水平線的交點則為紫色。
• startDeltaX 就是到第一個紫色的點要走的 x，可以算出來就是
  $(1-\text{offsetY})\cdot \tan (\theta )$。
• 而 startDeltaY 就是到第一個粉色的點要走的 x，可以算出來就是
  $(1-\text{offsetX})/\tan (\theta )$。
• 如果角度不一樣，可以依此類推。 e.g. 角度
  $\frac{1}{2}\pi <\theta <\frac{3}{2}\pi$ 時，兩個公式都改用 offset 計算即可。

再來我們可以看到每個紫色點之間的距離都是固定的，粉色也一樣。我們把紫色點之間的 x 差叫作 stepX，粉色之間的 y 差叫作 StepY。如下圖：

這部份對應的程式碼如下。interceptX 對應到紫色點的 x 座標，interceptY 對應到粉色點的 y。

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

float interceptX = rayX + startDeltaX;
float interceptY = rayY + startDeltaY;
float stepX = fabs(tan(rayA)) * tileStepX;
float stepY = fabs(1 / tan(rayA)) * tileStepY;

---

到這裡已經做好了讓光線開始前進的準備。這部份的 code 長這樣。

do {
    somethingDone = false;
    while (((tileStepY == 1 && (interceptY <= tileY + 1)) ||
            (tileStepY == -1 && (interceptY >= tileY)))) {
        //...
    }
    while (!verticalHit && ((tileStepX == 1 && (interceptX <= tileX + 1)) ||
                            (tileStepX == -1 && (interceptX >= tileX)))) {
        //...
    }
} while ((!horizontalHit && !verticalHit) && somethingDone);

• 最外層的迴圈告訴我們如果還沒撞到牆，而且我們都順利前進(somethingDone == true)的話，就繼續做。至於 somethingDone 存在的意義其實是為了處理浮點數運算的誤差，到後文會有更詳細的解說。
• 內層第一個 while 的意思是如果我們會先遇到垂直線的話就繼續做。
  • 例如我們我們開始在
    $(25.34,13.44)$ 位置往右上前進，並且我們算出來我們會在
    $(26,13.89)$ 遇到下一個垂直線。因為
    $13.89<14$，我們知道光線一定是先遇到垂直線，接下來才有可能撞到
    $y=14$。
  • 假如角度較接近水平的話，我們也有可能連續撞上好幾個垂直線，所以這裡是 while 迴圈。
  • ​​​​​​​​while (((tileStepY == 1 && (interceptY <= tileY + 1)) ||
    ​​​​​​​​        (tileStepY == -1 && (interceptY >= tileY)))) {
    ​​​​​​​​    somethingDone = true;
    ​​​​​​​​    tileX += tileStepX;
    ​​​​​​​​    if (IsWall(tileX, interceptY, rayA)) {
    ​​​​​​​​        verticalHit = true;
    ​​​​​​​​        rayX = tileX + (tileStepX == -1 ? 1 : 0);
    ​​​​​​​​        rayY = interceptY;
    ​​​​​​​​        *hitOffset = interceptY;
    ​​​​​​​​        *hitDirection = true;
    ​​​​​​​​        break;
    ​​​​​​​​    }
    ​​​​​​​​    interceptY += stepY;
    ​​​​​​​​}
    

  • 如果碰上垂直面，我們就把 tileX 移到下個 x 上，並察看這裡是不是牆壁。
  • 如果是牆壁，則 verticalHit = true，準備離開整個迴圈，我們已經找到牆壁了。
  • 不是牆壁的話，我們要找下一個 interceptY，讓迴圈可以再次判斷是不是接下來還是撞到垂直線。
• 第二個迴圈不斷判斷接下來是不是先遇到水平線，然後做類似的動作。
• 如果我們有順利找到牆壁，則可以計算距離並回傳：

float deltaX = rayX - playerX;
float deltaY = rayY - playerY;
return sqrt(deltaX * deltaX + deltaY * deltaY);

如此就完成 Distance 了。

somethingDone 與 Bug

如果我們從任何一方格出發，則我們不是先遇到垂直線，就是先遇到水平線，不可能兩個都遇不到。故從邏輯上， 不可能會出現 somethingDone=false 跳出迴圈的情況。但在下面兩種情況，真的有可能會發生這樣的情況。

startDelta 的計算 bug

我一開始觀察到如果將人物生成在 x,y 皆為整數的地方（0~31 都可以被浮點數 exact 表示），則會出現

$\frac{3}{4}$ 個世界全部消失的現象。如果只有其中一個是整數，則有半個世界會消失。

回到上面 startDelta 的計算：

if (offsetX == 0) {
    startDeltaY = (1) / fabs(tan(rayA));
} else {
    startDeltaY = (offsetX) / fabs(tan(rayA));
}

我們對 offset=0 也就是人物在整數上面都有做特別的處理，我們會忽略現在身在的邊界，而去尋找下一個邊界當作第一個碰撞點。但這會造成問題。以下圖為例：

現在 interceptX < tileX ，且 interceptY < tileY，就造成了 somethingDone = false。
解決辦法就是不要偷吃步，從當前邊界做起：

如此 interceptY > tileY，就會進去第一個迴圈而不會 somethingDone = false 了。這在程式碼中只要把原本對 offset == 0 的額外處理拿掉就可以了：

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

浮點數計算誤差

• 就算解決了上面的問題，還是會有少數出現
  somethingDone = false 的情況。這是由於浮點數的誤差造成，當 interceptX 或 interceptY 很靠近整數時，可能會發生明明會在方格內碰撞，卻跳到方格外一點的情況，造成兩邊條件都不成立。
• 我一開始嘗試在判斷加入一個容許誤差範圍：
  ​​​​while (((tileStepY == 1 && (interceptY <= tileY + 1 + DELTA)) ||
  ​​​​    (tileStepY == -1 && (interceptY >= tileY - DELTA)))) {
  ​​​​    //...
  ​​​​}
  

  • 但我想這並不完全安全，假如今天地圖更大，有可能會因為累加更多次，造成誤差更大。
  • 再來如果 DELTA 過大，事實上會造成判斷扭曲，影響原本的畫面。
• 因此後來決定假如發生 somethingDone = false，我才在 interceptX 與 interceptY 來加入一個補償值，讓判斷能夠正常。
  ​​​​do {
  ​​​​    bool somethingDone = false;
  ​​​​    while (((tileStepY == 1 && (interceptY <= tileY + 1)) ||
  ​​​​            (tileStepY == -1 && (interceptY >= tileY)))) {
  ​​​​        //...
  ​​​​    }
  ​​​​    while (!verticalHit && ((tileStepX == 1 && (interceptX <= tileX + 1)) ||
  ​​​​                            (tileStepX == -1 && (interceptX >= tileX)))) {
  ​​​​        //...
  ​​​​    }
  ​​​​    if (!somethingDone) {
  ​​​​        interceptX += -tileStepX * DELTA;
  ​​​​        interceptY += -tileStepY * DELTA;
  ​​​​    }
  ​​​​} while ((!horizontalHit && !verticalHit));
  

  如此就不會發生因為誤差而 distance = 0 的情況了，雖然影響不大。但是在邊界上，還是有可能 distance = 0。

Trace 方法

這個方法根據先前 start 得到的 playerX, playerY, playerA (角度)，從 screenX 這個位置射出 ray，來得到要畫的 牆壁高度、texture 亮度與 texture 座標。

void RayCasterFloat::Trace(uint16_t screenX,
                           uint8_t *screenY,
                           uint8_t *textureNo,
                           uint8_t *textureX,
                           uint16_t *textureY,
                           uint16_t *textureStep)
{
    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);
    float dum;
    *textureX = (uint8_t)(256.0f * modff(hitOffset, &dum));
    *textureNo = hitDirection;
    *textureY = 0;
    *textureStep = 0;
    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;
    }
}

• deltaAngle 解說：
  • delta 要算的角度就是下圖中的 delta，紅點為玩家，上平面為 screen 平面，垂直中線則為玩家視線正中間。
    
    
    令垂直中線長度為
    $d$，SCREEN_WIDTH 為
    $w$，FOV 為
    $\varphi$ (角度包含左右)。 且當
    $x<\frac{w}{2}$ 時，
    $\delta$ (delta) 為負，
    $x>\frac{w}{2}$ 時
    $\delta$ 為正角。
    則我們可以看出
    $d=\frac{w}{2}\frac{1}{\tan (\frac{\varphi }{2})}$，而
    
    $$\begin{array}{rl}\delta & =\arctan (\frac{x-\frac{w}{2}}{d})\\ & =\arctan (\frac{x-\frac{w}{2}}{\frac{w}{2}}\tan (\frac{\varphi }{2}))\end{array}$$
    所以我想原本應該是寫錯了，這一段 code 應該寫成這樣才對：
    ​​​​​​​​float deltaAngle = atanf(((int16_t) screenX - SCREEN_WIDTH / 2.0f) /
    ​​​​​​​​                     (SCREEN_WIDTH / 2.0f) * tan(FOV / 2));
    

• lineDistance： 上面已經解說過 Distance method 的運作，這個就是從玩家到牆面的直線距離。
• distance： 這裡把到玩家的距離轉成到 screen 平面的距離，如此畫面才不會看起來有 fisheye effect。
• textureX： 這裡我們根據 hit 的位置決定 texture 的 X
  • modff(hitOffset, &dum)，得到座標的小數部份
  • 而這裡不是乘以 64 而是乘以 256 是為了充份利用uint8_t 的 8 個 bit。如此可以先以定點數儲存，如果哪天需要用到 textureX 的小數點就可以用。
• 如果 distance 等於 0，代表 Distance 有錯誤或是離物體已經太近，就乾脆不畫
• 如果 distance 有正常值我們就：
  1. 根據距離算出牆壁在畫面上的大小。這裡是根據 INV_FACTOR 直接計算。這個大小是一半，整面牆的大小就是 txs。
  2. 根據在畫面上的大小決定 textureStep。前面以解說過 textureStep = 64 / txs。而這裡因為要轉成 10 bit fixed point，所以多乘了
     $1024$ 變成 256 / txs * 256。
  3. 如果牆壁比畫面還高，我們還得設定 textureY。wallHeight 為超出畫面的高度，這個高度乘以 textureStep 就知道要從哪裡開始了。但 textureStep 已經被轉成定點數，所以用浮點數這裡重算。

INV_FACTOR

$$
要從牆壁的高度計算畫面上的高度，我們要先知道垂直方向的

${\text{FOV}}_v$。假設在角度

${\text{FOV}}_h$ 在某距離可以看到寬度

$W$ 的範圍且在角度

${\text{FOV}}_v$ 下可以看到高度

$H$。而我們的

$\frac{H}{W}=\frac{\text{SCREEN\_HEIGHT}}{\text{SCREEN\_WIDTH}}$。

所以我們若令中線距離為

$d$ 則

$$\begin{array}{rl}\tan (\frac{{\text{FOV}}_h}{2})& =\frac{W}{2d}\\ \tan (\frac{{\text{FOV}}_v}{2})& =\frac{H}{2d}\\ & =\tan (\frac{{\text{FOV}}_h}{2})\frac{H}{W}\\ & =\tan (\frac{{\text{FOV}}_h}{2})\frac{\text{SCREEN\_HEIGHT}}{\text{SCREEN\_WIDTH}}\end{array}$$

再來假設牆面距離玩家

$D$，則透過這個

${\text{FOV}}_v$ 我們可以看到的遊戲場景一半高就是

$D\tan (\frac{{\text{FOV}}_v}{2})$ (在遊戲中的座標)，而牆的一半高度是 0.5。若我們令半牆的 pixel 高度為

$h$ 則牆佔畫面的比例為

$$\begin{array}{r}\frac{h}{\text{SCREEN\_HEIGHT}/2}=\frac{0.5}{D\tan (\frac{{\text{FOV}}_v}{2})}\end{array}$$
所以把

$\tan (\frac{{\text{FOV}}_v}{2})$ 用上面的式子取代之後得到

$h=\frac{\text{SCREEN\_WIDTH}}{4\tan (\frac{{\text{FOV}}_h}{2})}\frac{1}{D}$。

所以假如要讓 INV_FACTOR 隨著 FOV 自動調整的話，需要改為這樣：

#define INV_FACTOR (float) (SCREEN_WIDTH / (4.0f * tanf(FOV / 2)))

---

實測 floating point 不一樣的 FOV：
左邊仍為舊的 fixed point (90 度 FOV)。

1. 45 度
   
   
2. 120 度
   
   

Trace overflow bug

原本的程式碼中這一段

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

screenY 為 8bit unsigned，而且當我們很靠近牆時，算出來的高度可能是畫面半高(128)的好幾倍，所以可能會遇到 overflow 的問題。解決辦法是先用 float txs 儲存結果，等判斷完範圍之後，再設定 screenY:

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

Render 的運算缺點

當走近牆面的時候，會發現定點數與浮點數的差異。
牆面上半部：

牆面下半部：

• 定點數的結果雖然比較粗糙但也平滑穩定，不會有毛刺
• 浮點數在畫面上半部毛刺還不嚴重，但畫到下半部就會出現毛毛刺刺的現象，太神奇了，我想是因為不斷累加 textureStep 導致浮點數的誤差被放大了。
• 我想到一個解決辦法是因為其實牆面的中間一定是在畫面中間，所以中間要用什麼 texture 其實早就知道了。因此，我們可以從畫面中間開始畫，往上或往下累加 texture step，如此中間的畫面會比較穩定且可減少累加次數，增加穩定性。
• 我將 render 畫牆壁的程式改成如下：

// render upper wall
uint16_t to = (32 << 10) - (tst >> 1);
lb += (sso - 1) * SCREEN_WIDTH;
for (int y = 0; y < sso; y++) {
    auto ty = static_cast<int>(to >> 10);
    auto tv = g_texture8[(ty << 6) + tx];

    to -= tst;

    if (tn == 1 && tv > 0) {
        // dark wall
        tv >>= 1;
    }
    *lb = GetARGB(tv);
    lb -= SCREEN_WIDTH;
}

// render lower wall
to = (32 << 10) + (tst >> 1);
lb += sso * SCREEN_WIDTH;
for (int y = 0; y < sso; y++) {
    auto ty = static_cast<int>(to >> 10);
    auto tv = g_texture8[(ty << 6) + tx];

    to += tst;

    if (tn == 1 && tv > 0) {
        // dark wall
        tv >>= 1;
    }
    *lb = GetARGB(tv);
    lb += SCREEN_WIDTH;
}

• 我的 to 改成以
  $32\pm \frac{\text{tst}}{2}$ 出發，會加上
  $\frac{\text{tst}}{2}$ 是因為這樣相當於是根據像素中心的位置來選 texture。
• 如此以浮點數畫出來的結果，比起上面的毛刺邊有大幅的改善(左定點、右浮點)：
  舊：
  
  
  新：
  
  

定點數的運算缺失

走到特定點的時候，會出現奇怪的東西。我想是因為距離太遠有東西 overflow 的緣故。我去追查定點數實作中跟距離有關的部份，找到查表的函式 LookupHeight：

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

• 首先他判斷了距離是不是大於某個值，如果是就到 farHeight 去查表，如果距離近的話則是用 nearHeight 查表。
• 再來又判斷如果距離還是太遠，就一律取 farHeight 最遠的值再減 1 來當作牆壁的半高。
• 但這裡有個陷阱就是如果 ds >= 256 ，進入 if 查表後，出來竟然又查了一次，而且存取到 array 長度之外的位置。所以我們只要把 else 正確的補上即可：

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