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

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

整個視窗的高度為 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，如此
  $tst = 64 / 30$ 。
- 牆很近時，一個牆壁的 pixel 可能會佔了畫面中好幾個 pixel，此時
  $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;
}

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

在每個 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
$= θ > π$ ，則 x 上是
$- 1$ 。如果
$\frac{1}{2} π < θ < \frac{3}{2} π$ ，則 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 - offsetY) \cdot \tan (θ)$ 。
而 startDeltaY 就是到第一個粉色的點要走的 x，可以算出來就是
$(1 - offsetX) / \tan (θ)$ 。
如果角度不一樣，可以依此類推。 e.g. 角度
$\frac{1}{2} π < θ < \frac{3}{2} π$ 時，兩個公式都改用 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 為
  $ϕ$ (角度包含左右)。且當
  $x < \frac{w}{2}$ 時，
  $δ$ (delta) 為負，
  $x > \frac{w}{2}$ 時
  $δ$ 為正角。
  則我們可以看出
  $d = \frac{w}{2} \frac{1}{\tan (\frac{ϕ}{2})}$ ，而
  
  $\begin{aligned} δ & = \arctan (\frac{x - \frac{w}{2}}{d}) \\ = \arctan (\frac{x - \frac{w}{2}}{\frac{w}{2}} \tan (\frac{ϕ}{2})) \end{aligned}$
  所以我想原本應該是寫錯了，這一段 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

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

{FOV}_{v}

。假設在角度

{FOV}_{h}

在某距離可以看到寬度

W

的範圍且在角度

{FOV}_{v}

下可以看到高度

H

。而我們的

\frac{H}{W} = \frac{SCREEN_HEIGHT}{SCREEN_WIDTH}

。

所以我們若令中線距離為

d

則

\begin{aligned} \tan (\frac{{FOV}_{h}}{2}) & = \frac{W}{2 d} \\ \tan (\frac{{FOV}_{v}}{2}) & = \frac{H}{2 d} \\ = \tan (\frac{{FOV}_{h}}{2}) \frac{H}{W} \\ = \tan (\frac{{FOV}_{h}}{2}) \frac{SCREEN_HEIGHT}{SCREEN_WIDTH} \end{aligned}

再來假設牆面距離玩家

D

，則透過這個

{FOV}_{v}

我們可以看到的遊戲場景一半高就是

D \tan (\frac{{FOV}_{v}}{2})

(在遊戲中的座標)，而牆的一半高度是 0.5。若我們令半牆的 pixel 高度為

h

則牆佔畫面的比例為

\begin{array}{r} \frac{h}{SCREEN_HEIGHT / 2} = \frac{0.5}{D \tan (\frac{{FOV}_{v}}{2})} \end{array}

所以把

\tan (\frac{{FOV}_{v}}{2})

用上面的式子取代之後得到

h = \frac{SCREEN_WIDTH}{4 \tan (\frac{{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)。

45 度
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{tst}{2}$ 出發，會加上
$\frac{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);
}