# 2020q3 Homework5 (render)
contributed by < `sammer1107` >
###### tags: `進階電腦系統理論與實作`
# 程式原理
## Class Renderer
這個 class 負責根據一個 Game 物件的狀態來算繪遊戲場景。Renderer 內固定有一個 RayCaster，讓 Renderer 可以使用他來計算場景。
### GetARGB 方法
```c=
inline static uint32_t GetARGB(uint8_t brightness)
{
return (brightness << 16) + (brightness << 8) + brightness;
}
```
這個方法從一個**亮度值**來創造一個 ARGB 像素，ARGB 的值單純就只是複製亮度 `brightness` 而已。而 A,R,G 和 B 各用 8 bit 來表示，一起放在一個 32 bit 整數內，所以可以用 shift operator `<<` 來設定。
### TraceFrame
```c
void TraceFrame(Game *g, uint32_t *frameBuffer);
```
這個方法根據傳遞的 Game 物件，會利用 RayCaster 計算場景，然後畫到 frameBuffer 上。
:::info
這裡 **frameBuffer** 是一個以一維型式儲存的二維陣列，大小為 `SCREEN_WIDTH * SCREEN_HEIGHT`。儲存方式為 row major。
:::
```c=3
_rc->Start(static_cast<uint16_t>(g->playerX * 256.0f),
static_cast<uint16_t>(g->playerY * 256.0f),
static_cast<int16_t>(g->playerA / (2.0f * M_PI) * 1024.0f));
```
首先開始算繪場景前，我們先將 RayCaster 初始化在玩家目前位置。這裡將 x,y 座標乘以 256 是為了轉成 fixed point 格式，如果 RayCaster 實作為浮點數版本，則會在 Start 內將格式還原為 floating point。
再來我們將掃過所有的 x ，**在每個 x 把整條垂直線畫出來**。再這之前，我們先看 Trace 方法回傳的變數們，這些變數提供我們畫出畫面中某條垂直線所需要的資訊：
```c=7
for (int x = 0; x < SCREEN_WIDTH; x++) {
uint8_t sso; // half of the height of the wall to draw in this vertical stripe
uint8_t tc; // texture x coordinate, 2 bit fix point
uint8_t tn; // texture number of hitted wall
uint16_t tso; // texture y coord to start from, 10 bit fixed point
uint16_t tst; // how many step in texture for each screen pixel, 10 bit fixed point
uint32_t *lb = fb + x;
_rc->Trace(x, &sso, &tn, &tc, &tso, &tst);
...
```
+ 整個視窗的高度為 **SCREEN_HEIGHT**，SCREEN_HEIGHT/2 則為 **HORIZON_HEIGHT**。紅色線畫的就是畫面中線。
+ **sso** 為在當前這個垂直線上，我們要繪製的牆壁頂點到畫面中線的距離，整個牆的高度就是 `2*sso`。牆的高度是可能會比畫面還高的，例如圖的右邊的部份。故我們有這一段 code:
```c
int16_t ws = HORIZON_HEIGHT - sso;
if (ws < 0) {
ws = 0;
sso = HORIZON_HEIGHT;
}
```
如果牆比畫面高，則設定 sso 為 HORIZON_HEIGHT，ws 則為畫面頂部到牆頂部的距離。
+ **tc** 為 **2 bit 小數的定點數**，他告訴我們這一個 x 對應到的 texture x 座標。
:::info
牆面的 texture 定義在 **raycaster_data.h** 中的 **g_texture8**，為 $64\times 64$ 的亮度矩陣。
:::
因為我們的遊戲引擎非常簡單，人物不會站斜的，因此例如在繪製圖中第 1 條紫色線時，就只會用到 texture 中 x=0 的座標。
+ **tn**: 為 texture 的編號，這裡是方便之後可以擴充出不同的牆面材質，所以回傳光線碰撞到的牆面種類。目前實作中並沒有不同的牆面，而是在與 x 軸垂直的牆面回傳 1 ，另一方向則回傳 0，如此我們可以畫出不同亮度的牆面（或是做其他操作）。
+ **tso** 為 **10 bit 定點數**，他告訴我們在某條垂直線上，開始繪製牆面時的 texture y 軸座標從何開始。如果牆有完整出現再畫面中，如圖中兩條紫色線，則 `tso=0`。否則在牆不能容入畫面時，如圖中右邊， tso 必須從中間某個值開始。
+ **tst** 也為 **10 bit 定點數**，他告訴我們在繪製牆面時，我每往下一個 screen pixel 時，對應到移動多少牆面的 pixel。這會與距離有關：
+ 假如牆很遠，則我們高 64 的牆面材質，可能只佔了畫面中 30 個 pixel，如此 $\text{tst} = 64/30$。
+ 牆很近時，一個牆壁的 pixel 可能會佔了畫面中好幾個 pixel，此時 $\text{tst} < 1$
有了這些資訊，我們就可以畫出一條垂直線了。
```c=
// paint background gradient (upper)
for (int y = 0; y < ws; y++) {
*lb = GetARGB(96 + (HORIZON_HEIGHT - y));
lb += SCREEN_WIDTH;
}
for (int y = 0; y < sso * 2; y++) {
// paint texture pixel
auto ty = static_cast<int>(to >> 10);
auto tv = g_texture8[(ty << 6) + tx];
to += ts;
if (tn == 1 && tv > 0) {
// dark wall
tv >>= 1;
}
*lb = GetARGB(tv);
lb += SCREEN_WIDTH;
}
// render background gradient (lower)
for (int y = 0; y < ws; y++) {
*lb = GetARGB(96 + (HORIZON_HEIGHT - (ws - y)));
lb += SCREEN_WIDTH;
}
```
1. 第一個迴圈我們先畫天空的漸層。
2. 第二個迴圈畫牆面
+ 因為 to 與 ts 為 10 bit 定點數，所以要做 `>> 10` 的動作。
+ 因為 texture 為 $64\times 64$，所以像素位置是取 `ty*64 + tx` 並且用 `<<` 取代乘法。
+ 如果 texture number (tn) 為 1 ，我們就把亮度除以 2。如此來在與 x 軸垂直的牆面畫出暗面。
3. 第三個迴圈畫地板漸層
**在每個 x 上畫完垂直線後，就完成整個畫面的繪製了。**
## Class RayCasterFloat
### IsWall 方法
這個函數接收 rayX 與 rayY ，然後到地圖中查找這個位置是不是牆壁。
```c=
bool RayCasterFloat::IsWall(float rayX, float rayY, float rayA)
{
float mapX = 0;
float mapY = 0;
float offsetX = modff(rayX, &mapX);
float offsetY = modff(rayY, &mapY);
int tileX = static_cast<int>(mapX);
int tileY = static_cast<int>(mapY);
if (tileX < 0 || tileY < 0 || tileX >= MAP_X - 1 || tileY >= MAP_Y - 1) {
return true;
}
return g_map[(tileX >> 3) + (tileY << (MAP_XS - 3))] &
(1 << (8 - (tileX & 0x7)));
}
```
首先我們要先了解地圖與座標系統的運作，觀察此函式與 g_map 定義之後，我得出以下推論：
+ **地圖**定義在 **raycaster_data.h** 的 g_map 中。根據 `MAP_X` 與 `MAP_Y` 的定義，這個地圖為 $32\times 32$ 大小。
+ g_map 使用一個 bit 來代表某個位置 $1\times 1$ 的方格內是不是牆壁塊。
+ g_map 中每個元素為 uint8_t，4 個一組就是 x 方向的完整一排，共有 32 個 bit。每個 byte 中的 MSB 對應的 x 最小。所以整個 g_map 有 $32\times 4$ 個元素。
+ 所以看到程式 ==13== 行的部份，根據 tileX 與 tileY 我們要查找對應的方塊，需將 tileX 除以 8(bit) ，加上 tileY 乘以 4 (一個 row 有 4 byte) 來找到對應的 byte。 然後再用 bitwise operation 抓出對應的 bit。**但原程式應該是寫錯了**，假如 `tileX & 0x7` 為 0，我們會作 `g_map[...] & (1 << 8)`，如此並不會抓到我們想要的 MSB。**故 8 應改成 7。**
+ 另外這裡地圖邊界的判定 `tileX >= MAP_X - 1` 與 fixed point 實作不一致。若 tileX 為 31 ，我們仍應該到地圖查找而不是直接回傳，所以這裡應該改成 `tile > MAP_X - 1`。
#### 修正後的實作
```c=
bool RayCasterFloat::IsWall(float rayX, float rayY, float rayA)
{
int tileX = static_cast<int>(rayX);
int tileY = static_cast<int>(rayY);
if (tileX < 0 || tileY < 0 || tileX > MAP_X - 1 || tileY > MAP_Y - 1) {
return true;
}
return g_map[(tileX >> 3) + (tileY << (MAP_XS - 3))] &
(1 << (7 - (tileX & 0x7)));
}
```
+ 修正了上面提到的邊界判斷與 bitmap off-by-one 問題
+ 因為編譯器一直抱怨 offsetX, offsetY 沒被用到，所以改為上面的實作。直接利用 float 轉 int 會 truncate 的性質。
### Distance 方法
這個方法根據 playerX,playerY 與 rayA 來發射出光線，並回傳碰撞方向與位置，回傳資訊有兩種可能：
| Distance | 碰撞方向(hitDirection) | hitoffset |
| -------- | ------------------------------------ | -----------:|
| $>0$ | 碰撞面垂直 x 軸 (1) | 碰撞點 y 值 |
| $>0$ | 碰撞面垂直 y 軸 (0) | 碰撞點 x 值 |
| Distance | 特殊情況 |
|-- |-- |
| $=0$ | 因為浮點數計算誤差<br>導致撞不到方塊 |
:::info
**地圖座標系統**
在進入 Distance 的細節前，首先我們要了解 x, y, angle 的座標系統。 要注意的是這裡的角度從 y 軸出發，順時針繞一圈。
:::
程式一開始先做了一些前置準備：
```c=
int tileStepX = 1;
int tileStepY = 1;
float tileX = 0;
float tileY = 0;
if (rayA > M_PI) {
tileStepX = -1;
}
if (rayA > M_PI_2 && rayA < 3 * M_PI_2) {
tileStepY = -1;
}
float rayX = playerX;
float rayY = playerY;
float offsetX = modff(rayX, &tileX);
float offsetY = modff(rayY, &tileY);
```
+ **tileStepX, tileStepY** 可以看成光線的 x,y 方向，如果光線角度 rayA$=\theta > \pi$，則 x 上是$-1$。如果 $\frac{1}{2}\pi < \theta < \frac{3}{2}\pi$，則 y 方向是$-1$。反之方向為正則設為 $+1$。
+ **tileX, tileY** 為出發位置的座標的整數部份，**offset** 則為小數部份。e.g. rayX,rayY = 0.102, 23.75，則 tileX, tileY = 0,23， offsetX, offsetY = 0.102, 0.75
---
再來則計算此光線發射出去**會最先碰到的垂直線(平行 y 軸)與水平線(平行 x 軸)**。到達水平面要走的 x 距離為 **startDeltaX**,到達垂直面要走的 y 則為**startDeltaY**。
<br>
+ 在上圖中可以看到所有與垂直線的交點為粉色，與水平線的交點則為紫色。
+ **startDeltaX** 就是到第一個紫色的點要走的 x，可以算出來就是 $(1 - \text{offsetY})\cdot \tan(\theta)$。
+ 而 **startDeltaY** 就是到第一個粉色的點要走的 x，可以算出來就是 $(1 - \text{offsetX}) / \tan(\theta)$。
+ 如果角度不一樣，可以依此類推。 e.g. 角度 $\frac{1}{2}\pi < \theta < \frac{3}{2}\pi$ 時，兩個公式都改用 offset 計算即可。
再來我們可以看到每個紫色點之間的距離都是固定的，粉色也一樣。我們把紫色點之間的 x 差叫作 **stepX**，粉色之間的 y 差叫作 **StepY**。如下圖：
<br>
這部份對應的程式碼如下。**interceptX** 對應到紫色點的 x 座標，**interceptY** 對應到粉色點的 y。
```c=
float startDeltaX, startDeltaY;
if (rayA <= M_PI_2) {
startDeltaX = (1 - offsetY) * tan(rayA);
startDeltaY = (1 - offsetX) / tan(rayA);
} else if (rayA <= M_PI) {
//...
} else if (rayA < 3 * M_PI_2) {
//...
} else {
//...
}
float interceptX = rayX + startDeltaX;
float interceptY = rayY + startDeltaY;
float stepX = fabs(tan(rayA)) * tileStepX;
float stepY = fabs(1 / tan(rayA)) * tileStepY;
```
---
到這裡已經做好了讓光線開始前進的準備。這部份的 code 長這樣。
```c
do {
somethingDone = false;
while (((tileStepY == 1 && (interceptY <= tileY + 1)) ||
(tileStepY == -1 && (interceptY >= tileY)))) {
//...
}
while (!verticalHit && ((tileStepX == 1 && (interceptX <= tileX + 1)) ||
(tileStepX == -1 && (interceptX >= tileX)))) {
//...
}
} while ((!horizontalHit && !verticalHit) && somethingDone);
```
+ 最外層的迴圈告訴我們如果還沒撞到牆，而且我們都順利前進(`somethingDone == true`)的話，就繼續做。至於 `somethingDone` 存在的意義其實是為了處理浮點數運算的誤差，到後文會有更詳細的解說。
+ 內層第一個 while 的意思是如果我們會先遇到垂直線的話就繼續做。
+ 例如我們我們開始在 $(25.34, 13.44)$ 位置往右上前進，並且我們算出來我們會在 $(26, 13.89)$ 遇到下一個垂直線。因為 $13.89 < 14$，我們知道光線一定是先遇到垂直線，接下來才有可能撞到 $y=14$。
+ 假如角度較接近水平的話，我們也有可能連續撞上好幾個垂直線，所以這裡是 while 迴圈。
+ ```c
while (((tileStepY == 1 && (interceptY <= tileY + 1)) ||
(tileStepY == -1 && (interceptY >= tileY)))) {
somethingDone = true;
tileX += tileStepX;
if (IsWall(tileX, interceptY, rayA)) {
verticalHit = true;
rayX = tileX + (tileStepX == -1 ? 1 : 0);
rayY = interceptY;
*hitOffset = interceptY;
*hitDirection = true;
break;
}
interceptY += stepY;
}
```
+ 如果碰上垂直面，我們就把 tileX 移到下個 x 上，並察看這裡是不是牆壁。
+ 如果是牆壁，則 `verticalHit = true`，準備離開整個迴圈，我們已經找到牆壁了。
+ 不是牆壁的話，我們要找下一個 interceptY，讓迴圈可以再次判斷是不是接下來還是撞到垂直線。
+ 第二個迴圈不斷判斷接下來是不是先遇到水平線，然後做類似的動作。
+ 如果我們有順利找到牆壁，則可以計算距離並回傳：
```c
float deltaX = rayX - playerX;
float deltaY = rayY - playerY;
return sqrt(deltaX * deltaX + deltaY * deltaY);
```
如此就完成 Distance 了。
#### somethingDone 與 Bug
如果我們從任何一方格出發，則我們不是先遇到垂直線，就是先遇到水平線，不可能兩個都遇不到。故從邏輯上， 不可能會出現 `somethingDone=false` 跳出迴圈的情況。但在下面兩種情況，真的有可能會發生這樣的情況。
#### startDelta 的計算 bug
我一開始觀察到如果將人物生成在 x,y 皆為整數的地方（0~31 都可以被浮點數 exact 表示），則會**出現 $\frac{3}{4}$ 個世界全部消失的現象**。如果只有其中一個是整數，則有半個世界會消失。
回到上面 startDelta 的計算：
```c
if (offsetX == 0) {
startDeltaY = (1) / fabs(tan(rayA));
} else {
startDeltaY = (offsetX) / fabs(tan(rayA));
}
```
我們對 offset=0 也就是人物在整數上面都有做特別的處理，我們會忽略現在身在的邊界，而去尋找下一個邊界當作第一個碰撞點。但這會造成問題。以下圖為例：
現在 interceptX < tileX ，且 interceptY < tileY，就造成了 `somethingDone = false`。
解決辦法就是不要偷吃步，從當前邊界做起：
如此 interceptY > tileY，就會進去第一個迴圈而不會 `somethingDone = false` 了。這在程式碼中只要把原本對 offset == 0 的額外處理拿掉就可以了：
```c
if (rayA <= M_PI_2) {
startDeltaX = (1 - offsetY) * tan(rayA);
startDeltaY = (1 - offsetX) / tan(rayA);
} else if (rayA <= M_PI) {
startDeltaX = (offsetY) *fabs(tan(rayA));
startDeltaY = -(1 - offsetX) / fabs(tan(rayA));
} else if (rayA < 3 * M_PI_2) {
startDeltaX = -(offsetY) *fabs(tan(rayA));
startDeltaY = -(offsetX) / fabs(tan(rayA));
} else {
startDeltaX = -(1 - offsetY) * fabs(tan(rayA));
startDeltaY = (offsetX) / fabs(tan(rayA));
}
```
#### 浮點數計算誤差
+ 就算解決了上面的問題，還是會有少數出現
`somethingDone = false` 的情況。這是由於浮點數的誤差造成，當 interceptX 或 interceptY 很靠近整數時，可能會發生明明會在方格內碰撞，卻跳到方格外一點的情況，造成兩邊條件都不成立。
+ 我一開始嘗試在判斷加入一個容許誤差範圍：
```c
while (((tileStepY == 1 && (interceptY <= tileY + 1 + DELTA)) ||
(tileStepY == -1 && (interceptY >= tileY - DELTA)))) {
//...
}
```
+ 但我想這並不完全安全，假如今天地圖更大，有可能會因為累加更多次，造成誤差更大。
+ 再來如果 DELTA 過大，事實上會造成判斷扭曲，影響原本的畫面。
+ 因此後來決定假如發生 `somethingDone = false`，我才在 interceptX 與 interceptY 來加入一個補償值，讓判斷能夠正常。
```c
do {
bool somethingDone = false;
while (((tileStepY == 1 && (interceptY <= tileY + 1)) ||
(tileStepY == -1 && (interceptY >= tileY)))) {
//...
}
while (!verticalHit && ((tileStepX == 1 && (interceptX <= tileX + 1)) ||
(tileStepX == -1 && (interceptX >= tileX)))) {
//...
}
if (!somethingDone) {
interceptX += -tileStepX * DELTA;
interceptY += -tileStepY * DELTA;
}
} while ((!horizontalHit && !verticalHit));
```
如此就不會發生因為誤差而 distance = 0 的情況了，雖然影響不大。但是在邊界上，還是有可能 distance = 0。
### Trace 方法
這個方法根據先前 start 得到的 playerX, playerY, playerA (角度)，從 screenX 這個位置射出 ray，來得到要畫的 牆壁高度、texture 亮度與 texture 座標。
```c=
void RayCasterFloat::Trace(uint16_t screenX,
uint8_t *screenY,
uint8_t *textureNo,
uint8_t *textureX,
uint16_t *textureY,
uint16_t *textureStep)
{
float hitOffset;
int hitDirection;
float deltaAngle = atanf(((int16_t) screenX - SCREEN_WIDTH / 2.0f) /
(SCREEN_WIDTH / 2.0f) * M_PI / 4);
float lineDistance = Distance(_playerX, _playerY, _playerA + deltaAngle,
&hitOffset, &hitDirection);
float distance = lineDistance * cos(deltaAngle);
float dum;
*textureX = (uint8_t)(256.0f * modff(hitOffset, &dum));
*textureNo = hitDirection;
*textureY = 0;
*textureStep = 0;
if (distance > 0) {
*screenY = INV_FACTOR / distance;
auto txs = (*screenY * 2.0f);
if (txs != 0) {
*textureStep = (256 / txs) * 256;
if (txs > SCREEN_HEIGHT) {
auto wallHeight = (txs - SCREEN_HEIGHT) / 2;
*textureY = wallHeight * (256 / txs) * 256;
}
}
} else {
*screenY = 0;
}
}
```
+ **deltaAngle** 解說：
+ delta 要算的角度就是下圖中的 delta，紅點為玩家，上平面為 screen 平面，垂直中線則為玩家視線正中間。
令垂直中線長度為 $d$，SCREEN_WIDTH 為 $w$，FOV 為 $\phi$ (角度包含左右)。 且當 $x < \frac{w}{2}$ 時，$\delta$ (delta) 為負，$x > \frac{w}{2}$ 時 $\delta$ 為正角。
則我們可以看出 $d = \frac{w}{2}\frac{1}{\tan(\frac{\phi}{2})}$，而
\begin{align}
\delta &= \arctan(\frac{x-\frac{w}{2}}{d}) \\
&= \arctan(\frac{x-\frac{w}{2}}{\frac{w}{2}}\tan(\frac{\phi}{2}))
\end{align}
所以我想原本應該是寫錯了，**這一段 code 應該寫成這樣才對**：
```c
float deltaAngle = atanf(((int16_t) screenX - SCREEN_WIDTH / 2.0f) /
(SCREEN_WIDTH / 2.0f) * tan(FOV / 2));
```
+ **lineDistance**： 上面已經解說過 Distance method 的運作，這個就是從玩家到牆面的直線距離。
+ **distance**： 這裡把到玩家的距離轉成到 screen 平面的距離，如此畫面才不會看起來有 fisheye effect。
+ **textureX**： 這裡我們根據 hit 的位置決定 texture 的 X
+ `modff(hitOffset, &dum)`，得到座標的小數部份
+ 而這裡不是乘以 64 而是乘以 256 是為了充份利用uint8_t 的 8 個 bit。如此可以先以定點數儲存，如果哪天需要用到 textureX 的小數點就可以用。
+ 如果 distance 等於 0，代表 Distance 有錯誤或是離物體已經太近，就乾脆不畫
+ 如果 **distance** 有正常值我們就：
1. 根據距離算出牆壁在畫面上的大小。這裡是根據 INV_FACTOR 直接計算。這個大小是一半，整面牆的大小就是 txs。
2. 根據在畫面上的大小決定 textureStep。前面以解說過 textureStep = `64 / txs`。而這裡因為要轉成 10 bit fixed point，所以多乘了 $1024$ 變成 `256 / txs * 256`。
3. 如果牆壁比畫面還高，我們還得設定 textureY。wallHeight 為超出畫面的高度，這個高度乘以 textureStep 就知道要從哪裡開始了。但 textureStep 已經被轉成定點數，所以用浮點數這裡重算。
#### INV_FACTOR
$\newcommand{\fov}{\text{FOV}}$
要從牆壁的高度計算畫面上的高度，我們要先知道垂直方向的 $\fov_v$。假設在角度 $\fov_h$ 在某距離可以看到寬度 $W$ 的範圍且在角度 $\fov_v$ 下可以看到高度 $H$。而我們的 $\frac{H}{W} = \frac{\text{SCREEN_HEIGHT}}{
\text{SCREEN_WIDTH}}$。
所以我們若令中線距離為 $d$ 則
\begin{align}
\tan(\frac{\fov_h}{2}) &= \frac{W}{2d} \\
\tan(\frac{\fov_v}{2}) &= \frac{H}{2d} \\
&= \tan(\frac{\fov_h}{2})\frac{H}{W} \\
&= \tan(\frac{\fov_h}{2})\frac{\text{SCREEN_HEIGHT}}{
\text{SCREEN_WIDTH}} \\
\end{align}
再來假設牆面距離玩家 $D$，則透過這個 $\fov_v$ 我們可以看到的遊戲場景一半高就是 $D\tan(\frac{\fov_v}{2})$ (在遊戲中的座標)，而牆的一半高度是 0.5。若我們令半牆的 pixel 高度為 $h$ 則牆佔畫面的比例為
\begin{align}
\frac{h}{\text{SCREEN_HEIGHT}/2} = \frac{0.5}{D\tan(\frac{\fov_v}{2})}
\end{align}
所以把 $\tan(\frac{\fov_v}{2})$ 用上面的式子取代之後得到 $h = \frac{\text{SCREEN_WIDTH}}{4\tan(\frac{\fov_h}{2})}\frac{1}{D}$。
**所以假如要讓 INV_FACTOR 隨著 FOV 自動調整的話，需要改為這樣**：
```c
#define INV_FACTOR (float) (SCREEN_WIDTH / (4.0f * tanf(FOV / 2)))
```
---
**實測 floating point 不一樣的 FOV**：
左邊仍為舊的 fixed point (90 度 FOV)。
1. 45 度
2. 120 度
#### Trace overflow bug
原本的程式碼中這一段
```c
*screenY = INV_FACTOR / distance;
auto txs = (*screenY * 2.0f);
if (txs != 0) {
*textureStep = (256 / txs) * 256;
if (txs > SCREEN_HEIGHT) {
auto wallHeight = (txs - SCREEN_HEIGHT) / 2;
*textureY = wallHeight * (256 / txs) * 256;
}
}
```
`screenY` 為 8bit unsigned，而且當我們很靠近牆時，算出來的高度可能是畫面半高(128)的好幾倍，所以可能會遇到 overflow 的問題。解決辦法是先用 `float txs` 儲存結果，等判斷完範圍之後，再設定 `screenY`:
```c
float txs = 2 * INV_FACTOR / distance;
if (txs != 0) {
*textureStep = (256 / txs) * 256;
if (txs > SCREEN_HEIGHT) {
auto wallHeight = (txs - SCREEN_HEIGHT) / 2;
*textureY = wallHeight * (256 / txs) * 256;
*screenY = SCREEN_HEIGHT >> 1;
} else {
*screenY = txs / 2;
}
}
```
# Render 的運算缺點
當走近牆面的時候，會發現定點數與浮點數的差異。
牆面上半部：
牆面下半部：
+ 定點數的結果雖然比較粗糙但也平滑穩定，不會有毛刺
+ 浮點數在畫面上半部毛刺還不嚴重，但畫到下半部就會出現**毛毛刺刺的現象**，太神奇了，我想是因為**不斷累加 textureStep** 導致浮點數的誤差被放大了。
+ 我想到一個解決辦法是因為其實牆面的中間一定是在畫面中間，所以中間要用什麼 texture 其實早就知道了。因此，我們可以從畫面中間開始畫，往上或往下累加 texture step，如此中間的畫面會比較穩定且可減少累加次數，增加穩定性。
+ 我將 render 畫牆壁的程式改成如下：
```c=
// render upper wall
uint16_t to = (32 << 10) - (tst >> 1);
lb += (sso - 1) * SCREEN_WIDTH;
for (int y = 0; y < sso; y++) {
auto ty = static_cast<int>(to >> 10);
auto tv = g_texture8[(ty << 6) + tx];
to -= tst;
if (tn == 1 && tv > 0) {
// dark wall
tv >>= 1;
}
*lb = GetARGB(tv);
lb -= SCREEN_WIDTH;
}
// render lower wall
to = (32 << 10) + (tst >> 1);
lb += sso * SCREEN_WIDTH;
for (int y = 0; y < sso; y++) {
auto ty = static_cast<int>(to >> 10);
auto tv = g_texture8[(ty << 6) + tx];
to += tst;
if (tn == 1 && tv > 0) {
// dark wall
tv >>= 1;
}
*lb = GetARGB(tv);
lb += SCREEN_WIDTH;
}
```
+ 我的 to 改成以 $32\pm \frac{\text{tst}}{2}$ 出發，會加上 $\frac{\text{tst}}{2}$ 是因為這樣相當於是根據像素中心的位置來選 texture。
+ 如此以浮點數畫出來的結果，比起上面的毛刺邊有大幅的改善(左定點、右浮點)：
舊：
新：
# 定點數的運算缺失
走到特定點的時候，會出現奇怪的東西。我想是因為距離太遠有東西 overflow 的緣故。我去追查定點數實作中跟距離有關的部份，找到查表的函式 **LookupHeight**：
```c=
void RayCasterFixed::LookupHeight(uint16_t distance,
uint8_t *height,
uint16_t *step)
{
if (distance >= 256) {
const uint16_t ds = distance >> 3;
if (ds >= 256) {
*height = LOOKUP8(g_farHeight, 255) - 1;
*step = LOOKUP16(g_farStep, 255);
}
*height = LOOKUP8(g_farHeight, ds);
*step = LOOKUP16(g_farStep, ds);
} else {
*height = LOOKUP8(g_nearHeight, distance);
*step = LOOKUP16(g_nearStep, distance);
}
}
```
+ 首先他判斷了距離是不是大於某個值，如果是就到 farHeight 去查表，如果距離近的話則是用 nearHeight 查表。
+ 再來又判斷如果距離還是太遠，就一律取 farHeight 最遠的值再減 1 來當作牆壁的半高。
+ 但這裡有個陷阱就是如果 `ds >= 256` ，進入 if 查表後，出來竟然又查了一次，而且存取到 array 長度之外的位置。所以我們只要把 else 正確的補上即可：
```c=7
if (ds >= 256) {
*height = LOOKUP8(g_farHeight, 255) - 1;
*step = LOOKUP16(g_farStep, 255);
} else {
*height = LOOKUP8(g_farHeight, ds);
*step = LOOKUP16(g_farStep, ds);
}
```
Sign in with Wallet
Connect another wallet