# 2020q3 Homework5 (render)
contributed by < `OscarShiang` >

## 測試環境

$ 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` 函式中的實作：

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` 的部分

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 的數量

frame_count++;
sec_counter += seconds;

當 `sec_counter` 大於 1 時，將 `frame_counter` 中的數值作為 FPS 輸出，並清空

if (sec_counter >= 1.0f) {
    cout << "FPS = " << frame_count;
    sec_counter = 0;
    frame_count = 0;
}

得到的執行結果如下：

$ ./main
FPS = 44
FPS = 61
FPS = 60
FPS = 61
FPS = 61
FPS = 61

<...>

為了方便在測試的過程中，查看 FPS 的數值，我將這個結果改以顯示在遊戲視窗的標題中

所以我們需要將程式碼進行以下的修改

                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` 計算出來的表格輸出到檔案中，我們需要修改其實作的回傳值

 #pragma once

+#include <string>

 class RayCasterPrecalculator
 {
 public:
     RayCasterPrecalculator();
     ~RayCasterPrecalculator();
-    static void Precalculate();
+    static std::string Precalculate();
 };

接著實作 `table_generator` 將結果輸出到檔案中

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` 的實作如下

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

測試其產生的結果是否正確

$ ./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 --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` 這個表格產生出來後才開始進行編譯。

測試的結果如下

$ 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`