2020q3 Homework5 (render)

contributed by < Holychung >
2020q3 Homework5 (render) 題目

Outline

• 2020q3 Homework5 (render)
  • Outline
  • 背景知識
  • 程式原理
    • SDL API
    • main.cpp
    • game.cpp
    • renderer 物件
    • rayCaster_fixed.cpp
    • raycaster_float.cpp
  • 修正問題
    • 1. 邊界牆面距離大小不一
    • 2. 接近牆面時 float 版本缺失
    • 3. 在外圍牆壁往地圖內看 fixed 會出現牆壁
  • 輸出算繪過程的 frame rate

背景知識

在開始 trace code 之前可以先閱讀 Casting Wolf3D-style Rays with an FPGA and Arduino，當中有提到要撰寫一個 ray casting engine 有兩個方法，其中一個比較直接明瞭的是 Lode's Computer Graphics Tutorial，強烈建議先讀完這篇。

我在讀這篇的時候順便做了點筆記，因為篇幅太長就記錄到 研讀筆記: Raycasting。

程式原理

這邊有用到 library SDL，全名是 Simple DirectMedia Layer，是一個跨平台的函式庫，透過 OpenGL、Direct3D 提供低階的存取對聲音、鍵盤、滑鼠等硬體，通常被用在影音軟體、模擬器、遊戲等。

SDL API

if (SDL_Init(SDL_INIT_VIDEO) < 0) {
    printf("SDL could not initialize! SDL_Error: %s\n", SDL_GetError());
}

• SDL_Init 初始化並且設定為 SDL_INIT_VIDEO 的 video file I/O 和 threading 的 subsystem。

SDL_Window *sdlWindow =
    SDL_CreateWindow("RayCaster [fixed-point vs. floating-point]",
                     SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED,
                     SCREEN_SCALE * (SCREEN_WIDTH * 2 + 1),
                     SCREEN_SCALE * SCREEN_HEIGHT, SDL_WINDOW_SHOWN);

• SDL_CreateWindow 開啟一個給定好的位置、大小的視窗。
• SDL_Renderer 一個結構用來記錄算繪的狀態。
• SDL_GetPerformanceFrequency 取得特定平台 high resolution counter 每秒有幾個 count。
• SDL_GetPerformanceCounter 取得特定平台 high resolution counter 目前的值。
• SDL_CreateRenderer 創建 2D 算繪 (rendering) 的內容到給定的視窗當中。

SDL_Texture* SDL_CreateTexture(SDL_Renderer* renderer,
                               Uint32        format,
                               int           access,
                               int           w,
                               int           h)

• SDL_Texture 一個結構包含特定驅動裝置的像素資料表示。
• SDL_CreateTexture 創造一個 texture 給指定的 renderer。
• fixedTexture、floatTexture 給定的 format 都是 SDL_PIXELFORMAT_ARGB8888，表示 32 位元的各 8 bits 表示 ARGB，access 是 SDL_TEXTUREACCESS_STREAMING。

SDL_Texture *fixedTexture = SDL_CreateTexture(
    sdlRenderer, SDL_PIXELFORMAT_ARGB8888,
    SDL_TEXTUREACCESS_STREAMING, SCREEN_WIDTH, SCREEN_HEIGHT);
SDL_Texture *floatTexture = SDL_CreateTexture(
    sdlRenderer, SDL_PIXELFORMAT_ARGB8888,
    SDL_TEXTUREACCESS_STREAMING, SCREEN_WIDTH, SCREEN_HEIGHT);

• SDL_RenderPresent 用這個函式更新螢幕

main.cpp

DrawBuffer

用來把 frame buffer 中的東西畫到 renderer 上面。在 108 109 行各呼叫了一次，一個是畫畫面左邊定點數，一個是右邊浮點數。

static void DrawBuffer(SDL_Renderer *sdlRenderer,
                       SDL_Texture *sdlTexture,
                       uint32_t *fb,
                       int dx)
{
    int pitch = 0;
    void *pixelsPtr;
    if (SDL_LockTexture(sdlTexture, NULL, &pixelsPtr, &pitch)) {
        throw runtime_error("Unable to lock texture");
    }
    memcpy(pixelsPtr, fb, SCREEN_WIDTH * SCREEN_HEIGHT * sizeof(uint32_t));
    SDL_UnlockTexture(sdlTexture);
    SDL_Rect r;
    r.x = dx * SCREEN_SCALE;
    r.y = 0;
    r.w = SCREEN_WIDTH * SCREEN_SCALE;
    r.h = SCREEN_HEIGHT * SCREEN_SCALE;
    SDL_RenderCopy(sdlRenderer, sdlTexture, NULL, &r);
}

ProcessEvent

• SDL_Event 一個 union 包含不同事件型態的結構，像是 SDL_WindowEvent、SDL_KeyboardEvent 等。
• SDL_PollEvent 用這個函式輪詢在等待的事件，並且透過 ProcessEvent 來處理事件，如果不是 exit 遊戲事件，事件分兩種 moveDirection、rotateDirection，移動事件就是前後 UP、DOWN，旋轉視角則是左右 LEFT、RIGHT。會更具對應的這四個事件去更新變數 moveDirection、rotateDirection，用正負來代表方向。
• 最後在呼叫 game.Move(moveDirection, rotateDirection, seconds); 來對角色移動。

static bool ProcessEvent(const SDL_Event &event,
                         int *moveDirection,
                         int *rotateDirection)
{
    if (event.type == SDL_QUIT) {
        return true;
    } else if ((event.type == SDL_KEYDOWN || event.type == SDL_KEYUP) &&
               event.key.repeat == 0) {
        auto k = event.key;
        auto p = event.type == SDL_KEYDOWN;
        switch (k.keysym.sym) {
        case SDLK_ESCAPE:
            return true;
            break;
        case SDLK_UP:
            *moveDirection = p ? 1 : 0;
            break;
        case SDLK_DOWN:
            *moveDirection = p ? -1 : 0;
            break;
        case SDLK_LEFT:
            *rotateDirection = p ? -1 : 0;
            break;
        case SDLK_RIGHT:
            *rotateDirection = p ? 1 : 0;
            break;
        default:
            break;
        }
    }
    return false;
}

game.cpp

Game 這個物件是用來記錄角色的位置跟視角，playerX, playerY, playerA。

第 13 的迴圈是判斷視角是否在

$0\to 2\pi$ 之間，沒有就 mod

$2\pi$。

第 20 行則是判斷位置是否到達地圖邊界，如果超過地圖邊界就往回推 0.01，用這樣的手法可以做到角色在碰到牆邊時，繼續按方向鍵，角色會緩慢的沿著牆壁滑動的效果。

void Game::Move(int m, int r, float seconds)
{
    playerA += 0.05f * r * seconds * 25.0f;
    playerX += 0.5f * m * sin(playerA) * seconds * 5.0f;
    playerY += 0.5f * m * cos(playerA) * seconds * 5.0f;

    while (playerA < 0) {
        playerA += 2.0f * M_PI;
    }
    while (playerA >= 2.0f * M_PI) {
        playerA -= 2.0f * M_PI;
    }

    if (playerX < 1) {
        playerX = 1.01f;
    } else if (playerX > MAP_X - 2) {
        playerX = MAP_X - 2 - 0.01f;
    }
    if (playerY < 1) {
        playerY = 1.01f;
    } else if (playerY > MAP_Y - 2) {
        playerY = MAP_Y - 2 - 0.01f;
    }
}

renderer 物件

會有一個指向 RayCaster 的指標 _rc，還有一個 TraceFrame 的方法。

TraceFrame

這邊一開始呼叫的 _rc->Start，會先把 playerX、playerY、playerA 變成定點數的格式，playerX、playerY 乘上 256.0f，在轉成 uint16_t，這樣就是用 uint16_t 前面 8 位元存整數部分，後面 8 位元存小數部分。playerA 是用代表角色的方向，範圍是

$0\to 2\pi$，這邊會除上

$2\pi$ 在乘以 1024，以方便後面定點數的表示，會在 fixed point 的時候解釋。

void Renderer::TraceFrame(Game *g, uint32_t *fb)
{
    _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));

再來用一個迴圈對屏幕每一個 x 軸的點開始畫圖。

for (int x = 0; x < SCREEN_WIDTH; x++){
...
}

接下來看到迴圈中的變數，會透過 Trace 去計算要要如何繪圖，得到下列變數的值，這邊部分參考sammer1107 的說明。

uint8_t sso;    // screenY  
uint8_t tc;     // textureX 
uint8_t tn;     // textureNo Horozontal hit: 0  Vertical hit: 1
uint16_t tso;   // textureY 
uint16_t tst;   // textureStep 

整個視窗的高度為 SCREEN_HEIGHT，SCREEN_HEIGHT/2 則為 HORIZON_HEIGHT，也就是中間的水平線。

• sso 是牆壁頂點到畫面中線的距離，不過牆的高度是可能會比畫面還高的，所以如果超過的話 sso = HORIZON_HEIGHT。
• tn textureNo 代表不同的材質，這邊只有 0 和 1，如果是 Vertical hit 為 1，其餘為 0。
• tc 對應 x 軸的 texture x。
• tso 對應 y 軸的 texture y。
• tst 代表在畫牆面時下一個 y 軸位置要走多遠，假如牆很遠，則我們高 64 的牆面材質，可能只佔了畫面中 30 個 pixel，那
  $tst=64/30$。

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

第一個迴圈是先畫背景最上面背景的部分。

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

最後一個跟第一個同理，畫最底下背景的部分。

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

rayCaster_fixed.cpp

Start

用來初始化物件的變數，這邊在 TraceFrame 呼叫的時候會先做處理轉成 uint16_t 的定點數格式，_viewQuarter 則是用來判斷現在的角度在第幾象限，一開始先把角度 A 除以

$2\pi$ 範圍就會坐落在 0~1 之間，這邊其實只要乘以 256 也就可以轉乘定點數的格式，但是要用來判斷第幾象限的話，把他多乘上一個 4，也就變成乘以 1024，最只要透過 playerA >> 8，就可以得到是在 0 1 2 3 得以判斷象限，再用 _viewAngle 把小數點的部分記下來。

void RayCasterFixed::Start(uint16_t playerX, uint16_t playerY, int16_t playerA)
{
    _viewQuarter = playerA >> 8;
    _viewAngle = playerA % 256;
    _playerX = playerX;
    _playerY = playerY;
    _playerA = playerA;
}

raycaster_float.cpp

Start

用來初始化物件的變數，這邊因為是用浮點數，所以需要把前面 TraceFrame 呼叫時傳進來的定點數格式先轉回去浮點數。

void RayCasterFloat::Start(uint16_t playerX, uint16_t playerY, int16_t playerA)
{
    _playerX = (playerX / 1024.0f) * 4.0f;
    _playerY = (playerY / 1024.0f) * 4.0f;
    _playerA = (playerA / 1024.0f) * 2.0f * M_PI;
}

修正問題

1. 邊界牆面距離大小不一

問題描述

可以看到下圖 fixed floating 兩者到邊界的最外圍牆面，離牆面的距離有明顯的不同。

fixed 走到角落，到角落兩邊的邊界距離也不同。

修正問題

在 raycaster.h 這邊的定義可以看到，地圖大小是 32x32 總共 1024 個方格。

#define MAP_X (uint8_t) 32
#define MAP_Y (uint8_t) 32

在 raycaster_data.h 也可以看到地圖在這邊也是 1024 個，1 代表牆壁。

const uint8_t LOOKUP_TBL g_map[] = {
    0b00000000, 0b10000000, 0b00000000, 0b00000000, 0b01111010, 0b10111111,
    0b11111111, 0b00000000, 0b00111000, 0b10100000, 0b00001000, 0b01001100,
    0b01000001, 0b00000100, 0b00100100, 0b00001100, 0b00000000, 0b10001010,
    0b00000010, 0b01011100, 0b10000001, 0b11000100, 0b00000110, 0b00001100,
    0b00000000, 0b11010010, 0b00010000, 0b00001100, 0b01001100, 0b10010000,
    0b00000000, 0b00111100,

    0b00100011, 0b10100100, 0b00000100, 0b00001100, 0b00000000, 0b11000001,
    0b10001000, 0b00001100, 0b00110000, 0b10011100, 0b00111000, 0b01111100,
    0b00000011, 0b00000000, 0b00000000, 0b00001100, 0b00011111, 0b11111110,
    0b11111111, 0b11111100, 0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000,

    0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000,

    0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000};

推測應該是在角色移動的判斷寫錯了，所以到 game.cpp 當中查看 Move 的函式，這邊會對 playerX、playerY 進行判斷，小於一了話就會回到 1.01，大於 MAP_X-2 就會 MAP_X - 2 - 0.01f。

    if (playerX < 1) {
        playerX = 1.01f;
    } else if (playerX > MAP_X - 2) {
        playerX = MAP_X - 2 - 0.01f;
    }

這邊的判斷應該是大於 MAP_X - 1 然後回到 MAP_X - 1 - 0.01f，這邊也就可以很明顯看出，X Y 的範圍是 0-31 ，在 X Y 接近邊界 31 的時候就會離比較遠，而 0 的那一個邊界則是正常。

     if (playerX < 1) {
         playerX = 1.01f;
-    } else if (playerX > MAP_X - 2) {
-        playerX = MAP_X - 2 - 0.01f;
+    } else if (playerX > MAP_X - 1) {
+        playerX = MAP_X - 1 - 0.01f;
     }
     if (playerY < 1) {
         playerY = 1.01f;
-    } else if (playerY > MAP_Y - 2) {
-        playerY = MAP_Y - 2 - 0.01f;
+    } else if (playerY > MAP_Y - 1) {
+        playerY = MAP_Y - 1 - 0.01f;
     }
 }

修正完後測試如下，fixed 的版本修正成功，但是 float 則是到牆邊發生了一點問題。

這邊實驗後，發現 float 在計算「邊界」牆壁的距離時比 fixed 的版本還要小，非邊界的牆壁則是一樣的，所以推測是判斷牆壁的地方出錯了，所以看到 raycaster_float.cpp 的 IsWall。

    if (tileX < 0 || tileY < 0 || tileX >= MAP_X - 1 || tileY >= MAP_Y - 1) {
        return true;
    }

這邊的 tileX 不是大於等於，要改成 tileX > MAP_X - 1，不然計算到牆壁的算法，在最後邊界牆壁的地方，就會計算錯誤，提早了一個方格找到牆壁，也就是造成這個問題的原因，在對照 fixed 版本的也是沒有等於，所以修正這個錯誤。

-    if (tileX < 0 || tileY < 0 || tileX >= MAP_X - 1 || tileY >= MAP_Y - 1) {
+    if (tileX < 0 || tileY < 0 || tileX > MAP_X - 1 || tileY > MAP_Y - 1) {

修正前後比對

修正前

修正後

修正前

修正後

2. 接近牆面時 float 版本缺失

問題描述

在角色貼近牆壁的時候，float 版本的牆面會壞掉如下圖，推測有可能是因為 overflow 導致牆壁高度變為 0 導致。

修正問題

去找到運算牆壁高度 sso 的函式 Trace，再看到 screenY 的型態是 uint8_t，且等於 INV_FACTOR / distance，當 distance 在很小的時候在這邊有機會發生 overflow，並且在 txs 大於 SCREEN_HEIGHT 的時候，要把 screenY 的值設成 HORIZON_HEIGHT 才對。

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

修正版本如下。

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

修正前後比對

修正前

修正後

3. 在外圍牆壁往地圖內看 fixed 會出現牆壁

問題描述

在外圍牆壁往地圖內看 fixed 會出現牆壁，這邊推測應該是牆壁距離太遠所造成的問題。

修正問題

查找到 LookupHeight 這個函式當中，發現 ds 大於等於 256 的這邊少了一個 else 的判斷，這樣進去 if 判斷完後出來又會在 LOOKUP 一次。

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

修正過後。

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

修正前後比對

修正前

修正後

輸出算繪過程的 frame rate

在 main.cpp 中可以看到一開始介紹的 SDL API 當中有提到 SDL_GetPerformanceFrequency、SDL_GetPerformanceCounter，透過這兩個 API 就可以計算出每次 while 迴圈相隔的時間，這個時間的倒數就是 frame rate(fps)。

const auto seconds = (nextCounter - tickCounter) /
                     static_cast<float>(tickFrequency);

印出來結果如下。