# 2020q3 Homework5 (render)

作業目標如下:
* 修正浮點數和定點數算繪程式展現的缺失，並提出改進 precision 及 accuracy 的方式
* 輸出算繪過程的 [frame rate](https://en.wikipedia.org/wiki/Frame_rate)，日後當我們進一步提升算繪程式的效率時，這會是效能評比的方式之一
* 利用 [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 以 C99/C11 (或 gnu99/gnu11) 重寫，允許在執行時期載入 fixed-point 和 floating-point 為基礎的 renderer
:::info
對照研讀 [Object-oriented techniques in C](https://dmitryfrank.com/articles/oop_in_c) 及 [Achieving polymorphism in C](https://www.codeproject.com/Articles/739687/Achieving-polymorphism-in-C)
:::
* 閱讀 Doom rendering engine 和 Casting Wolf3D-style Rays with an FPGA and Arduino，解釋 raycaster 運作原理，並探討後續的改進方案，例如更換彩色的貼圖素材 (texture)、引入遊戲元素 (sprite) 等等。

## [Ray-casting](https://en.wikipedia.org/wiki/Ray_casting) (光線投射)
將 viewpoint 視為光線起源 (ray origin)，透過追蹤光線撞擊到場景中的物體轉換為 3D 投影的方法

| Ray-casting | Ray-tracing |
| ----------- |:---------------- |
| Quality: 通常不太真實 | Quailty: 非常真實 |
| World: 有幾何形狀的限制 | World: 可以算繪出任何形狀 |
| Storage: 小，只會儲存map，image則是"執行時"算出而產生 | Storage: 事先儲存好 rendered image |

最主要的差別: ray-casting 因為幾何限制 (geometric constraints)，所以僅需較少的光線來追蹤

### Ray-casting step 1: create a world
* Geometric constraints:
1. 牆壁跟天花板垂直
2. 牆壁由相同大小的方塊組成
3. 天花板永遠是平坦的
* Gridmap of the world
* 座標系統

### Ray-casting step 2: DEFINING PROJECTION ATTRIBUTES
需要知道以下屬性 (attributes) 才能投影以及算繪
1. 玩家的高度, 視角 player's field of view (FOV)， position
* 玩家需要知道面前的東西是什麼，所以定義 FOV 決定可以看多寬
* 論文中的FOV為60度
* 玩家高度在這裡為 cube 的一半高度
* 定義玩家的 X,Y 座標以及玩家面向角度
->定義玩家的觀點

2. 投影平面的維度
* 將玩家的視野投影到投影面，也就是視窗大小，論文設為320x200 (pixels)
* 當玩家的視野被投影到投影面，就形成我們所看到的畫面

3. 玩家跟投影面的關係
藉由FOV跟投影面的大小，我們可以計算出玩家跟投影面的距離
以及每個光線之間的角度

所以我們目前有以下資訊
* Dimension of the Projection Plane = 320 x 200 pixels
* Center of the Projection Plane = (160,100)
* Distance to the Projection Plane = 277 pixels
* Angle between subsequent rays = 60/320 degrees

玩家到投影面的距離將會被用於 scaling.
### Ray-casting step 3: FINDING WALLS
可以將牆壁視為320條垂直線（或320條牆面切片）的集合。
這正是 geometrical constraints 的一種形式，適用於Ray-casting。FOV最左端的光線將被投影到投影平面的第0列，而最右邊的光線將被投影到投影平面的第319列。

### Ray-casting step 4: FINDING WALL DISTANCE
為了找到牆，我們需要檢查 Ray 跟每個 Grid 相交