# 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
```graphviz
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})}$
```cpp
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.
```cpp
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**
```cpp
// 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)
```cpp
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).
```cpp
template <typename Table>
inline int16_t AbsTan(uint8_t quarter, uint8_t angle, const Table &lookupTable)
{
return lookupTable[quarter & 1 ? INVERT(angle) : angle];
}
```