# 2020q3 Homework5 (render) contributed by < `Holychung` > [2020q3 Homework5 (render) 題目](https://hackmd.io/@sysprog/2020-render) ## Outline [TOC] ## 背景知識 在開始 trace code 之前可以先閱讀 [Casting Wolf3D-style Rays with an FPGA and Arduino](http://www.dormando.me/post/fpga-raycaster/)，當中有提到要撰寫一個 ray casting engine 有兩個方法，其中一個比較直接明瞭的是 [Lode's Computer Graphics Tutorial](https://lodev.org/cgtutor/raycasting.html)，**強烈建議先讀完這篇**。 我在讀這篇的時候順便做了點筆記，因為篇幅太長就記錄到 [研讀筆記: Raycasting](https://hackmd.io/@Holy/BkDDrDe0w)。 ## 程式原理 這邊有用到 library [SDL](SDL)，全名是 Simple DirectMedia Layer，是一個跨平台的函式庫，透過 OpenGL、Direct3D 提供低階的存取對聲音、鍵盤、滑鼠等硬體，通常被用在影音軟體、模擬器、遊戲等。 ### `SDL API` ```cpp=68 if (SDL_Init(SDL_INIT_VIDEO) < 0) { printf("SDL could not initialize! SDL_Error: %s\n", SDL_GetError()); } ``` - [SDL_Init](https://wiki.libsdl.org/SDL_Init?highlight=%28%5CbCategoryAPI%5Cb%29%7C%28SDLFunctionTemplate%29) 初始化並且設定為 `SDL_INIT_VIDEO` 的 video file I/O 和 threading 的 subsystem。 ```cpp=71 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](https://wiki.libsdl.org/SDL_CreateWindow?highlight=%28%5CbCategoryAPI%5Cb%29%7C%28SDLFunctionTemplate%29) 開啟一個給定好的位置、大小的視窗。 - [SDL_Renderer](https://wiki.libsdl.org/SDL_Renderer?highlight=%28%5CbCategoryStruct%5Cb%29%7C%28SDLStructTemplate%29) 一個結構用來記錄算繪的狀態。 - [SDL_GetPerformanceFrequency](https://wiki.libsdl.org/SDL_GetPerformanceFrequency?highlight=%28%5CbCategoryAPI%5Cb%29%7C%28SDLFunctionTemplate%29) 取得特定平台 high resolution counter 每秒有幾個 count。 - [SDL_GetPerformanceCounter](https://wiki.libsdl.org/SDL_GetPerformanceCounter?highlight=%28%5CbCategoryAPI%5Cb%29%7C%28SDLFunctionTemplate%29) 取得特定平台 high resolution counter 目前的值。 - [SDL_CreateRenderer](https://wiki.libsdl.org/SDL_CreateRenderer) 創建 2D 算繪 (rendering) 的內容到給定的視窗當中。 ```cpp SDL_Texture* SDL_CreateTexture(SDL_Renderer* renderer, Uint32 format, int access, int w, int h) ``` - [SDL_Texture](https://wiki.libsdl.org/SDL_Texture?highlight=%28%5CbCategoryStruct%5Cb%29%7C%28SDLStructTemplate%29) 一個結構包含特定驅動裝置的像素資料表示。 - [SDL_CreateTexture](https://wiki.libsdl.org/SDL_CreateTexture) 創造一個 texture 給指定的 renderer。 - `fixedTexture`、`floatTexture` 給定的 format 都是 `SDL_PIXELFORMAT_ARGB8888`，表示 32 位元的各 8 bits 表示 ARGB，access 是 `SDL_TEXTUREACCESS_STREAMING`。 ```cpp=97 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](https://wiki.libsdl.org/SDL_RenderPresent) 用這個函式更新螢幕 ### `main.cpp` #### DrawBuffer 用來把 frame buffer 中的東西畫到 renderer 上面。在 108 109 行各呼叫了一次，一個是畫畫面左邊定點數，一個是右邊浮點數。 ```cpp= 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](https://wiki.libsdl.org/SDL_Event?highlight=%28%5CbCategoryStruct%5Cb%29%7C%28SDLStructTemplate%29) 一個 union 包含不同事件型態的結構，像是 SDL_WindowEvent、SDL_KeyboardEvent 等。 - [SDL_PollEvent](https://wiki.libsdl.org/SDL_PollEvent?highlight=%28%5CbCategoryAPI%5Cb%29%7C%28SDLFunctionTemplate%29) 用這個函式輪詢在等待的事件，並且透過 `ProcessEvent` 來處理事件，如果不是 exit 遊戲事件，事件分兩種 `moveDirection`、`rotateDirection`，移動事件就是前後 `UP`、`DOWN`，旋轉視角則是左右 `LEFT`、`RIGHT`。會更具對應的這四個事件去更新變數 `moveDirection`、`rotateDirection`，用正負來代表方向。 - 最後在呼叫 `game.Move(moveDirection, rotateDirection, seconds);` 來對角色移動。 ```cpp=34 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，用這樣的手法可以做到角色在碰到牆邊時，繼續按方向鍵，角色會緩慢的沿著牆壁滑動的效果。 ```cpp=7 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 的時候解釋。 ```cpp=5 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 軸的點開始畫圖。 ```cpp=11 for (int x = 0; x < SCREEN_WIDTH; x++){ ... } ``` 接下來看到迴圈中的變數，會透過 `Trace` 去計算要要如何繪圖，得到下列變數的值，這邊部分參考[sammer1107](https://hackmd.io/@sammer1107/hw5_render) 的說明。 ```cpp=12 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$。 有了這些資訊，我們就可以畫出一條垂直線了。 第一個迴圈是先畫背景最上面背景的部分。 ```cpp=30 for (int y = 0; y < ws; y++) { *lb = GetARGB(96 + (HORIZON_HEIGHT - y)); lb += SCREEN_WIDTH; } ``` 第二個迴圈是畫牆面的部份。 ```cpp= 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; } ``` 最後一個跟第一個同理，畫最底下背景的部分。 ```cpp= 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` 把小數點的部分記下來。 ```cpp= 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` 呼叫時傳進來的定點數格式先轉回去浮點數。 ```cpp= 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 兩者到邊界的最外圍牆面，離牆面的距離有明顯的不同。 ![](https://i.imgur.com/7Jfid3v.png) fixed 走到角落，到角落兩邊的邊界距離也不同。 ![](https://i.imgur.com/MhQjJAg.png) #### 修正問題 在 `raycaster.h` 這邊的定義可以看到，地圖大小是 32x32 總共 1024 個方格。 ```cpp= #define MAP_X (uint8_t) 32 #define MAP_Y (uint8_t) 32 ``` 在 `raycaster_data.h` 也可以看到地圖在這邊也是 1024 個，1 代表牆壁。 ```cpp= 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`。 ```cpp=20 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 的那一個邊界則是正常。 ```diff= 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 則是到牆邊發生了一點問題。 ![](https://i.imgur.com/WjyalFn.png) 這邊實驗後，發現 float 在計算「邊界」牆壁的距離時比 fixed 的版本還要小，非邊界的牆壁則是一樣的，所以推測是判斷牆壁的地方出錯了，所以看到 `raycaster_float.cpp` 的 `IsWall`。 ```cpp=15 if (tileX < 0 || tileY < 0 || tileX >= MAP_X - 1 || tileY >= MAP_Y - 1) { return true; } ``` 這邊的 `tileX` 不是大於等於，要改成 `tileX > MAP_X - 1`，不然計算到牆壁的算法，在最後邊界牆壁的地方，就會計算錯誤，提早了一個方格找到牆壁，也就是造成這個問題的原因，在對照 fixed 版本的也是沒有等於，所以修正這個錯誤。 ```diff= - 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) { ``` #### 修正前後比對 :negative_squared_cross_mark: 修正前 ![](https://i.imgur.com/7Jfid3v.png) :heavy_check_mark: 修正後 ![](https://i.imgur.com/pbExCa4.png) :negative_squared_cross_mark: 修正前 ![](https://i.imgur.com/MhQjJAg.png) :heavy_check_mark: 修正後 ![](https://i.imgur.com/rEJhHlb.png) ### 2. 接近牆面時 float 版本缺失 #### 問題描述 在角色貼近牆壁的時候，float 版本的牆面會壞掉如下圖，推測有可能是因為 overflow 導致牆壁高度變為 0 導致。 ![](https://i.imgur.com/44mYpbK.png) #### 修正問題 去找到運算牆壁高度 `sso` 的函式 `Trace`，再看到 `screenY` 的型態是 `uint8_t`，且等於 `INV_FACTOR / distance`，當 distance 在很小的時候在這邊有機會發生 overflow，並且在 txs 大於 SCREEN_HEIGHT 的時候，要把 screenY 的值設成 HORIZON_HEIGHT 才對。 ```cpp=151 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; } ``` 修正版本如下。 ```cpp= 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; } ``` #### 修正前後比對 :negative_squared_cross_mark: 修正前 ![](https://i.imgur.com/44mYpbK.png) :heavy_check_mark: 修正後 ![](https://i.imgur.com/F8ZZTqw.png) ### 3. 在外圍牆壁往地圖內看 fixed 會出現牆壁 #### 問題描述 在外圍牆壁往地圖內看 fixed 會出現牆壁，這邊推測應該是牆壁距離太遠所造成的問題。 ![](https://i.imgur.com/Zf6ebfg.png) #### 修正問題 查找到 `LookupHeight` 這個函式當中，發現 ds 大於等於 256 的這邊少了一個 else 的判斷，這樣進去 if 判斷完後出來又會在 LOOKUP 一次。 ```cpp=70 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); } } ``` 修正過後。 ```diff= 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); ``` #### 修正前後比對 :negative_squared_cross_mark: 修正前 ![](https://i.imgur.com/Zf6ebfg.png) :heavy_check_mark: 修正後 ![](https://i.imgur.com/qcJznYD.png) ## 輸出算繪過程的 frame rate 在 `main.cpp` 中可以看到一開始介紹的 SDL API 當中有提到 `SDL_GetPerformanceFrequency`、`SDL_GetPerformanceCounter`，透過這兩個 API 就可以計算出每次 while 迴圈相隔的時間，這個時間的倒數就是 frame rate(fps)。 ```cpp=119 const auto seconds = (nextCounter - tickCounter) / static_cast<float>(tickFrequency); ``` 印出來結果如下。 ![](https://i.imgur.com/OZ4oDk5.png)