# 2020q3 Homework5 (render)
contributed by < `OscarShiang` >
## 測試環境
```shell
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="20.04 LTS (Focal Fossa)"
$ cat /proc/version
Linux version 5.4.0-47-generic (buildd@lcy01-amd64-014)
(gcc version 9.3.0 (Ubuntu 9.3.0-10ubuntu2))
```
## 作業要求
- [ ] 修正浮點數和定點數算繪程式展現的缺失，並提出改進 precision 及 accuracy 的方式
- [x] 輸出算繪過程的 [frame rate](https://en.wikipedia.org/wiki/Frame_rate)，日後當我們進一步提升算繪程式的效率時，這會是效能評比的方式之一
- [x] 利用 [tools/precalculator.cpp](https://github.com/sysprog21/raycaster/blob/master/tools/precalculator.cpp) 產生運算表格，修改相關程式碼，使得程式碼在編譯時期才去產生運算表格，後者以標頭檔案 (generated header) 的形式存在並編譯進入主程式。換言之，檔案 [raycaster_tables.h](https://github.com/sysprog21/raycaster/blob/master/raycaster_tables.h) 應自 repository 移除，改用編譯時期產生
- [ ] 解說現有 fixed-point 實作機制，並探討前述表格產生的機制，需要提及其中的考量點
- [ ] 參照 [C 語言：物件導向程式設計篇](https://hackmd.io/@sysprog/c-oop)，透過建立共用介面 (interface) 的手法，將 [raycaster](https://github.com/sysprog21/raycaster) 以 C99/C11 (或 gnu99/gnu11) 重寫，允許在執行時期載入 fixed-point 和 floating-point 為基礎的 renderer
## 輸出算繪過程的 frame rate
根據 [Frame rate - Wikipedia] 的描述
> Frame rate (expressed in frames per second or FPS) is the frequency (rate) at which consecutive images called frames appear on a display.
可以知道 FPS 就是每秒我們更新了多少次遊戲畫面。
而對應到 `raycaster` 中就是在一秒內，`main.cpp` 中的 game loop 跑了幾次。
所以我們可以先看到 `main.cpp:main` 函式中的實作：
```cpp
int main(int argc, char *args[])
{
<...>
while (!isExiting) {
floatRenderer.TraceFrame(&game, floatBuffer);
fixedRenderer.TraceFrame(&game, fixedBuffer);
DrawBuffer(sdlRenderer, fixedTexture, fixedBuffer, 0);
DrawBuffer(sdlRenderer, floatTexture, floatBuffer,
SCREEN_WIDTH + 1);
SDL_RenderPresent(sdlRenderer);
if (SDL_PollEvent(&event)) {
isExiting =
ProcessEvent(event, &moveDirection, &rotateDirection);
}
const auto nextCounter = SDL_GetPerformanceCounter();
const auto seconds = (nextCounter - tickCounter) /
static_cast<float>(tickFrequency);
tickCounter = nextCounter;
game.Move(moveDirection, rotateDirection, seconds);
}
<...>
}
```
在這個 while 迴圈之中，我們可以看到 `raycaster` 利用這個迴圈重複地進行算繪，並將 floating-point 與 fixed-point 的 buffer 利用 `SDL_RenderPresent` 顯示在視窗上，因此從這邊我們可以判斷這個迴圈就是 game loop
根據 SDL Wiki 上的說明，我們可以知道在這邊使用到的 `SDL_GetPerformanceCounter` 是用來取得 SDL 內建的 high resolution counter 的數值，而我們可以透過這個數值差來算出兩次 game loop 之間相差多久。
而在上述程式碼中可以看到在取得兩個 frame 之間的 counter 差值後，我們是透過 `tickFrequency` 來算出時間差的，而這個部分可以回推到 `main.cpp:93` 的部分
```cpp
const static auto tickFrequency = SDL_GetPerformanceFrequency();
```
`SDL_GetPerformanceFrequency` 這個函式在 SDL Wiki 中的描述是
> Returns a platform-specific count per second.
因此我們可以透過這個函式得知當前運行平台每秒對應到多少 count，透過這樣我們就可以從 `(nextCounter - tickCounter) /
static_cast<float>(tickFrequency)` 計算出產生這個 frame 所花費的時間。並從這邊推得 FPS 的數值。
在 FPS 的實作中，我使用兩個變數作為 counter，分別計算從上次更新 FPS 到目前的秒數以及產生的 frame 的數量
```cpp
frame_count++;
sec_counter += seconds;
```
當 `sec_counter` 大於 1 時，將 `frame_counter` 中的數值作為 FPS 輸出，並清空
```cpp
if (sec_counter >= 1.0f) {
cout << "FPS = " << frame_count;
sec_counter = 0;
frame_count = 0;
}
```
得到的執行結果如下：
```shell
$ ./main
FPS = 44
FPS = 61
FPS = 60
FPS = 61
FPS = 61
FPS = 61
<...>
```
為了方便在測試的過程中，查看 FPS 的數值，我將這個結果改以顯示在遊戲視窗的標題中
所以我們需要將程式碼進行以下的修改
```diff
frame_count++;
sec_counter += seconds;
if (sec_counter >= 1.0f) {
- cout << "FPS = " << frame_count;
+ stringstream title;
+ title << GAME_TITLE " FPS = " << frame_count;
+ SDL_SetWindowTitle(sdlWindow, title.str().c_str());
sec_counter = 0;
frame_count = 0;
```
而結果呈現如下紅框所示
## 利用 tools/precalculator.cpp 產生運算表格
因為 `raycaster_table.h` 中的數值是固定的，所以我們可以在編譯時期才產生
為了將在 `RayCasterPrecalculator::Precalculate` 計算出來的表格輸出到檔案中，我們需要修改其實作的回傳值
```diff
#pragma once
+#include <string>
class RayCasterPrecalculator
{
public:
RayCasterPrecalculator();
~RayCasterPrecalculator();
- static void Precalculate();
+ static std::string Precalculate();
};
```
接著實作 `table_generator` 將結果輸出到檔案中
```cpp
int main(int argc, char *argv[])
{
if (argc != 2) {
cout << "[ERR] Output filename is needed" << endl;
exit(-1);
}
string filename(argv[1]);
RayCasterPrecalculator calculator;
string data = calculator.Precalculate();
generate_table(filename, data);
return 0;
}
```
`generate_table` 的實作如下
```cpp
void generate_table(string filename, string data)
{
fstream out(filename, ios::out);
string macro_id;
for (int i = 0; i < filename.length(); i++) {
}
char marcro_id[filename.length() + 1];
for (int i = 0; i < filename.length(); i++) {
switch (filename[i]) {
case '.':
marcro_id[i] = '_';
break;
default:
marcro_id[i] = toupper(filename[i]);
}
}
marcro_id[filename.length()] = '\0';
string macro(marcro_id);
/* Add dependencies */
out << "#include \"raycaster.h\""
<< "\n\n";
/* Add protect marco */
out << "#ifndef " << macro << '\n';
out << "#define " << macro << "\n\n";
out << data;
out << "#endif /* " << macro << " */" << '\n';
out.close();
}
```
測試其產生的結果是否正確
```shell
$ ./table_generator raycaster_tables.h
$ cat raycaster_tables.h
#include "raycaster.h"
#ifndef RAYCASTER_TABLES_H
#define RAYCASTER_TABLES_H
const uint16_t LOOKUP_TBL g_tan[256] = {0,1,3,4,6,7,9,11,12,14,15,17,18,20,22,23,25,26,28,29,31,33,34,36,37,39,41,42,44,46,47,49,50,52,54,55,57,59,60,62,64,65,67,69,70,72,74,75,77,79,81,82,84,86,88,89,91,93,95,96,98,100,102,104,106,107,109,111,113,115,117,119,121,123,124,126,128,130,132,134,136,138,140,142,145,147,149,151,153,155,157,159,162,164,166,168,171,173,175,177,180,182,185,187,189,192,194,197,199,202,204,207,210,212,215,218,220,223,226,229,232,234,237,240,243,246,249,252,255,259,262,265,268,272,275,278,282,285,289,293,296,300,304,308,311,315,319,323,328,332,336,340,345,349,354,358,363,368,373,378,383,388,393,398,404,409,415,421,427,433,439,445,451,458,465,471,478,486,493,500,508,516,524,532,541,549,558,568,577,587,597,607,618,628,640,651,663,675,688,701,715,729,744,759,774,791,808,825,843,862,882,903,925,947,971,996,1022,1049,1077,1108,1140,1173,1209,1246,1286,1329,1374,1423,1475,1531,1591,1655,1725,1801,1884,1975,2075,2185,2308,2445,2599,2773,2972,3202,3470,3787,4166,4631,5210,5956,6950,8341,10428,13905,20859,41720};
const uint16_t LOOKUP_TBL g_cotan[256] = {0,41720,20859,13905,10428,8341,6950,5956,5210,4631,4166,3787,3470,3202,2972,2773,2599,2445,2308,2185,2075,1975,1884,1801,1725,1655,1591,1531,1475,1423,1374,1329,1286,1246,1209,1173,1140,1108,1077,1049,1022,996,971,947,925,903,882,862,843,825,808,791,774,759,744,729,715,701,688,675,663,651,640,628,618,607,597,587,577,568,558,549,541,532,524,516,508,500,493,486,478,471,465,458,451,445,439,433,427,421,415,409,404,398,393,388,383,378,373,368,363,358,354,349,345,340,336,332,328,323,319,315,311,308,304,300,296,293,289,285,282,278,275,272,268,265,262,259,256,252,249,246,243,240,237,234,232,229,226,223,220,218,215,212,210,207,204,202,199,197,194,192,189,187,185,182,180,177,175,173,171,168,166,164,162,159,157,155,153,151,149,147,145,142,140,138,136,134,132,130,128,126,124,123,121,119,117,115,113,111,109,107,106,104,102,100,98,96,95,93,91,89,88,86,84,82,81,79,77,75,74,72,70,69,67,65,64,62,60,59,57,55,54,52,50,49,47,46,44,42,41,39,37,36,34,33,31,29,28,26,25,23,22,20,18,17,15,14,12,11,9,7,6,4,3,1};
<...>
#endif /* RAYCASTER_TABLES_H */
```
並將 `table_generator` 整合到 `Makefile` 中
```diff
diff --git a/Makefile b/Makefile
index e554d48..67d0780 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,12 @@
BIN = main
+TBL_GEN = table_generator
CXXFLAGS = -std=c++11 -O2 -Wall -g
+LOOKUP_TBL := raycaster_tables.h
+
+TOOLS_DIR := tools
+
# SDL
CXXFLAGS += `sdl2-config --cflags`
LDFLAGS += `sdl2-config --libs`
@@ -18,7 +23,7 @@ endif
GIT_HOOKS := .git/hooks/applied
.PHONY: all clean
-all: $(GIT_HOOKS) $(BIN)
+all: $(GIT_HOOKS) $(LOOKUP_TBL) $(BIN)
$(GIT_HOOKS):
@scripts/install-git-hooks
@@ -32,14 +37,29 @@ OBJS := \
main.o
deps := $(OBJS:%.o=.%.o.d)
+TBL_GEN_OBJS := \
+ tools/precalculator.o \
+ tools/table_generator.o
+deps := $(TBL_GEN_OBJS:%.o=.%.o.d)
+
%.o: %.cpp
+ @mkdir -p .$(TOOLS_DIR)
$(VECHO) " CXX\t$@\n"
$(Q)$(CXX) -o $@ $(CXXFLAGS) -c -MMD -MF .$@.d $<
$(BIN): $(OBJS)
- $(Q)$(CXX) -o $@ $^ $(LDFLAGS)
+ $(Q)$(CXX) -o $@ $^ $(LDFLAGS)
+
+$(TBL_GEN): $(TBL_GEN_OBJS)
+ $(VECHO) " CXX\t$@\n"
+ $(Q)$(CXX) -o $@ $^
+
+$(LOOKUP_TBL): $(TBL_GEN)
+ $(VECHO) " GEN\t$@\n"
+ $(Q)eval "./$^ $@"
clean:
- $(RM) $(BIN) $(OBJS) $(deps)
+ $(RM) $(BIN) $(OBJS) $(TBL_GEN) $(TBL_GEN_OBJS) $(deps)
+ rm -rf .$(TOOLS_DIR)
-include $(deps)
```
在 `all` 這個 target 中調整順序就可以確保在編譯 raycaster 前會先將 `raycaster_tables.h` 這個表格產生出來後才開始進行編譯。
測試的結果如下
```shell
$ make
CXX tools/precalculator.o
CXX tools/table_generator.o
CXX table_generator
GEN raycaster_tables.h
CXX game.o
CXX raycaster_fixed.o
CXX raycaster_float.o
CXX renderer.o
CXX main.o
```
## 參考資料
###### tags: `sysprog2020`
Sign in with Wallet
Connect another wallet