# 2020q3 Homework5 (render)
contributed by < [stonelin](https://github.com/StoneLin0708) >

###### tags: `sysprog2020`

---

* [ ] 在 GitHub 上 fork raycaster，目標如下:
* [X] [修正浮點數算繪程式展現的缺失](https://hackmd.io/pIvOfBb5TF-tM6EStuxP0Q#The-floating-point-rendering-bug)
* [ ] 定點數算繪程式展現的缺失
* [ ] 並提出改進 precision 及 accuracy 的方式
* [X] [輸出算繪過程的 frame rate，日後當我們進一步提升算繪程式的效率時，這會是效能評比的方式之一](https://hackmd.io/pIvOfBb5TF-tM6EStuxP0Q#Draw-FPS)
* [X] [利用 tools/precalculator.cpp 產生運算表格，修改相關程式碼，使得程式碼在編譯時期才去產生運算表格，後者以標頭檔案 (generated header) 的形式存在並編譯進入主程式。換言之，檔案 raycaster_tables.h 應自 repository 移除，改用編譯時期產生](https://hackmd.io/pIvOfBb5TF-tM6EStuxP0Q?both#Compile-time-table-generation)
* [ ] 解說現有 fixed-point 實作機制，並探討前述表格產生的機制，需要提及其中的考量點
* [ ] 參照 C 語言：物件導向程式設計篇，透過建立共用介面 (interface) 的手法，將 raycaster 以 C99/C11 (或 gnu99/gnu11) 重寫，允許在執行時期載入 fixed-point 和 floating-point 為基礎的 renderer
* [ ] 對照研讀 Object-oriented techniques in C 及 Achieving polymorphism in C

* [ ]閱讀 Doom rendering engine 和 Casting Wolf3D-style Rays with an FPGA and Arduino，解釋 raycaster 運作原理，並探討後續的改進方案，例如更換彩色的貼圖素材 (texture)、引入遊戲元素 (sprite) 等等。

---

# code understanding
[Wikipedia](https://en.wikipedia.org/wiki/Ray_casting) Helps a lot.
> 
> Wolfenstein 3D
The world in the famous video game Wolfenstein 3D is built from a square based grid of uniform height walls meeting solid coloured floors and ceilings. In order to draw the world, a single ray is traced for every column of screen pixels and a vertical slice of wall texture is selected and scaled according to where in the world the ray hits a wall and how far it travels before doing so.
>
> from Ray casting Wikipedia

### FOV

graph{
node[shape=plaintext]
Sl[label=L]
Sm[label="Screen W"]
Sr[label="R"]
Sl--Sm--Sr;
{rank=same;Sl,Sm,Sr}
P[label=Player]
P--Sl
P--Sm[label=D]
P--Sr
}

### $fov=\angle_{L,Player,R}$

### $\overrightarrow{X^+}=\overrightarrow{LR}$

:::warning
改用 Graphviz 或其他語法來展現
:notes: jserv
:::
:::info
I didn't find a good solution other than upload an image. graphviz is limited too.
:::

$\dfrac{fov}{2}=tan^{-1}(\dfrac{\dfrac{W}{2}}{D})$
$tan(\dfrac{fov}{2})=\dfrac{\dfrac{W}{2}}{D}$
$D=\dfrac{\dfrac{W}{2}}{tan(\dfrac{fov}{2})}$

float deltaAngle = atanf(((int16_t) screenX - SCREEN_WIDTH / 2.0f) /
                         (SCREEN_WIDTH / 2.0f) * M_PI / 4);

$\Delta{Angle}=tan^{-1}(\dfrac{X-W/2}{D})\\
=>\Delta{Angle}=tan^{-1}(\dfrac{X-W/2}{\dfrac{W/2}{tan(fov/2)}})\\
=>\Delta{Angle}=tan^{-1}(\dfrac{X-W/2}{W/2}tan(fov/2))$

$fov\approx76^o$

### The floating point rendering bug


First the player spawn point move to [21.9, 7.9, 0] to reproduce the bug at start.

playerX = 21.9;
playerY = 7.9;
playerA = 0

Clue:

* close to the wall
* happend if wall rendering out of screen
* it's repeating the wall texture

Looks like an integer overflow.
At first, I thought it must be caused by the tangent function to calculate the distance, but after some testing, it is not (at least not the rendering problem here).
After that I went to **RayCasterFloat::Trace** and found the answer, **screenY** which is 8 bit unsigned integer overflowed by **INV_FACTOR / distance**

// RayCasterFloat::Trace(...){
// ...
    res.screenY = std::min<int>(INV_FACTOR / distance, SCREEN_HEIGHT/2);
    auto txs = (INV_FACTOR / distance * 2.0f);
    if (txs != 0) {
        res.textureStep = (256 / txs) * 256;
        if (txs > SCREEN_HEIGHT) {
            auto wallHeight = (txs - SCREEN_HEIGHT) / 2;
            res.textureY = wallHeight * (256 / txs) * 256;
        }
    }
//...
//}


# Draw FPS


# Compile time table generation

Using constexpr math library (template based) to compute table at compile time.
[Generalized Constant Expression Math](https://github.com/kthohr/gcem/tree/3ad1616c25fb0c9748d424b71bcead8f8cfe8a19)

constexpr auto g_sin = []() constexpr
{
    std::array<uint8_t, 256> g_sin{};
    for (int i = 0; i < 256; i++) {
        g_sin[i] =
            static_cast<uint8_t>(256.0f * gcem::sin(i / 1024.0f * 2 * M_PI));
    }
    return g_sin;
}
();

Using template to handle type changing of the table (from pointer to std::array).

template <typename Table>
inline int16_t AbsTan(uint8_t quarter, uint8_t angle, const Table &lookupTable)
{
    return lookupTable[quarter & 1 ? INVERT(angle) : angle];
}