---
# System prepended metadata

title: 2020q3 Homework5 (render)
tags: [linux2020]

---

---
title: '2020q3 Homework5 (render)'
tags: linux2020
---
# 2020q3 Homework5 (render)
contributed by < `ChongMingWei` >

## Outline
[TOC]
## 環境
```shell
$ uname -a
Linux cmw-System-Product-Name 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
```

## Ray Casting Explaination
> Reference: 
> [Ray Casting Tutorial](https://permadi.com/1996/05/ray-casting-tutorial-4/)
> [Video:Wolfenstein 3D's map renderer](https://www.youtube.com/watch?v=eOCQfxRQ2pY&ab_channel=MattGodbolt)

這是我們設計的遊戲世界地圖，由一個一個的方格 (grid)所組成，可移動範圍為黑色區域，深藍色區域則為牆壁，玩家則是圖中的小白點，會在地圖中移動，紅線部份指的是目前玩家的視角 (某一個角度)
![](https://i.imgur.com/AInNIDv.png)
然而，玩家的視角不只是正前方的單一一線，而是有一個範圍的 FOV 存在，如下圖紅線部份
![](https://i.imgur.com/kpEcFuL.png)
==Ray casting== 就是一種演算法，能夠將玩家 FOV 中的牆壁以及天空和地板所畫出來，就像上圖右邊所顯示的部份。

假設我們的顯示視窗是下圖，在還沒有開始做 ray casting 之前，會是全黑的：![](https://i.imgur.com/gzLV7t6.png)

當使用 ray casting 演算法做了第一個 column 之後，會得到結果：![](https://i.imgur.com/0bJ4puf.png)
當視窗寬度的所有 column 都處理過後，才是顯現在我們眼前的樣子：![](https://i.imgur.com/rDHIwJ2.png)
### Ray casting 演算法說明

#### 針對每一個 column ，我們會有以下的資訊：
1. 玩家目前的位置
2. 該個 column 的 POV (point of view)

- 針對第2項資訊，在此說明：
首先玩家自己會有一個 POV ，看向螢幕的正中間 (如下圖紅線處)，這個角度就是最中間 column 的 POV ，其他 column 的 POV 則依視窗大小和 FOV 大小決定。

    舉例來說，當 FOV 為60^o^，螢幕寬度為256，那麼每個 column 的 POV 差距就會是$\dfrac{60^o}{256}$
假設螢幕正中間的 POV 是 50^o^，
那麼第一個 column (如下圖黃線處)的 POV 就會是$20^o(50^o - \dfrac{128 \times 60^o}{256})$
![](https://i.imgur.com/YE4uL3b.png)


#### 對於每一個 column ，我們要做的事情有以下2項:
1. 找出該 POV 方向，和牆壁的交點
2. 計算該座標到玩家座標的距離，並且取 cos 值

- 針對第1點，如圖所示，紅點為欲尋找目標
![](https://i.imgur.com/VyTsA5P.png)

    以下解釋如何尋找和牆壁的交點:
    1. 根據該 POV 方向，我們會交錯穿過網格中的**水平線**以及**垂直線**，如圖中的綠線和藍線：
    ![](https://i.imgur.com/Ncb1F7j.png)
    2. 判斷觸碰到的水平線 (or 垂直線)所代表的網格是否為牆壁，對事先準備好的遊戲地圖進行查表即可完成此項任務。
- 針對第2點，我們只要將玩家的座標和牆壁交點座標用距離公式，就可以計算出兩者之間的距離，然而，這樣的計算方式卻會造成 "fishbowl effect" ，在視野的邊緣兩側會有變形的產生：
![](https://i.imgur.com/D168a5K.png)
為解決變形，我們需要計算，將該條視線的距離乘上和中心視線夾角的 cos 值：
![](https://i.imgur.com/psDuEip.png)

- 事實上，前面帶過的尋找牆壁交點中，交叉穿過水平線和垂直線是有一套演算法來實行的，詳情如下：
    - 首先，玩家的座標會和身處的網格有 x 方向以及 y 方向的 offset
![](https://i.imgur.com/tB6c8rE.png)
可以得到和第一條水平線交點為$(x+dx, y-dy), dx = \dfrac{dy}{tan\theta}$
![](https://i.imgur.com/TpP9Och.png)

    - 會碰觸到的所有水平線 (途中紅箭頭所指處)中，前後條的距離是相當的 (垂直線亦然)，如圖所示，其垂直方向的差距為1，水平方向的差距為δy
![](https://i.imgur.com/wf3bgdQ.png)
而δy又可以被表示成$\dfrac{1}{tan\theta}$
![](https://i.imgur.com/0fA911U.png)
同理亦可被套用到垂直線中，可看到水平方向的差距為1，此時垂直方向的差距δx可被表示成 $tan\theta$
![](https://i.imgur.com/T5NyM8R.png)
因此，只要事先將 tan 以及 cot 的三角函數值表建好，這邊每次找下一個水平/垂直線時，只需要用查表方法以及考慮不同角度，就可以快速的用加減法得到下一個水平/垂直線和該 POV 的交點座標

- 計算玩家座標和牆壁交點的距離也有簡化的公式，如圖：
![](https://i.imgur.com/Ceg6EUU.png)
$p=dcos(\phi)\\
\phi=\theta-\beta\\
p=dcos(\theta-\beta)\\
p=d[cos(\theta)cos(\beta)+sin(\theta)sin(\beta)]\\
p=dcos(\theta)cos(\beta)+dsin(\theta)sin(\beta)\\
p = Δxcos(\beta)+Δysin(\beta)$
其中，β 就是玩家的 POV ，是一個固定已知值，這樣一來即可省去計算距離公式中，平方以及取平方根的計算。

#### 每一個 column 計算完和牆壁的距離之後，就可以針對牆壁來做 **scaling**
![](https://i.imgur.com/EPZzcDc.png)

- Annotation:
    - $h_p$: projected wall height 
    - $h_a$: actual wall height
    - $d_{pp}$: distance of player to projection plane
    - $d_{pw}$: distance of player to the wall
- 根據上圖，可得到公式如下:
$\dfrac{h_p}{d_{pp}} = \dfrac{h_a}{d_{pw}}\\ h_p=\dfrac{d_{pp}*h_a}{d_{pw}}\\
h_p = \dfrac{d_{pp}*1}{d_{pw}}$
其中 $d_{pp}$ 跟 FOV 又有關係:
以下圖為例，螢幕寬為320， FOV 為80^o^時，$d_{pp}$ 約為190
![](https://i.imgur.com/ycctWx0.png)
這邊提到的$d_{pp}$對應到`raycaster.h`內的參數  `INV_FACTOR`:
    - `INV_FACTOR`: 上面算式中的分子部份，但根據 `INV_FACTOR` 計算得到的牆壁高度只有原來的一半 (`renderer.h` 中的 `sso`)，所以 `INV_FACTOR` = 0.5\*$d_{pp}$。
    ```cpp=12
    #define INV_FACTOR (float) (SCREEN_WIDTH * 95.0f / 320.0f)
    ```
    > 怎麼那麼剛好，舉個80^o^的例子，就和我們使用的參數一致了?
    
    當然，世界上沒有那麼多的偶然，作業裡面的 FOV 就正好大約為80^o^。

    在 `raycaster_tables.h` 中可以看到 `g_deltaAngle[255]` 的值為 108，將其換算後，$\dfrac{108}{256} \times 90^o = 37.96875^o$
也就是說 FOV 應為 75.9375^o^ (和80^o^仍有些誤差)

    接著我們看到 `tools/precalculator.cpp` ，計算 `g_deltaAngle`的程式碼為:
    > 在`raycaster_float.cpp`中也用了相同的計算方式
    ```cpp
    float deltaAngle = atanf(((int16_t) screenX - SCREEN_WIDTH / 2.0f) /
                             (SCREEN_WIDTH / 2.0f) * M_PI / 4);
    ```
    ```cpp=42
        for (int i = 0; i < SCREEN_WIDTH; i++) {
            float deltaAngle = atanf(((int16_t) i - SCREEN_WIDTH / 2.0f) /
                                     (SCREEN_WIDTH / 2.0f) * M_PI / 4);
            int16_t da = static_cast<int16_t>(deltaAngle / M_PI_2 * 256.0f);
            if (da < 0) {
                da += 1024;
            }
            g_deltaAngle[i] = static_cast<uint16_t>(da);
        }
    ```
    其中的 line43-44可用以下圖解說明 (假設此時 i=240):
    ![](https://i.imgur.com/gBu7S0N.png)
    欲求deltaAngle，就必須要得到其對應的鄰邊以及對邊，其中鄰邊在已知螢幕寬度和 FOV 時可算出來，而對邊在已知螢幕寬度和目前的 column 也可算出:
$deltaAngle=atanf(\dfrac{i-\dfrac{W}{2}}{2*tan\dfrac{FOV}{2}})$
透過這個公式可以算得 FOV ，可以看到結果並不是`raycaster.h`中的 90^o^。
$tan\dfrac{FOV}{2}=\dfrac{\pi}{4}\\\dfrac{FOV}{2}\approx38.146^o\\FOV\approx76.292^o(和80^o仍有些誤差)$
由以上過程可以看到，原始給定的參數，所展現出來的效果是有誤差存在的。
- 圖片支援
    - FOV: 75.9375^o^(original) v.s. 90^o^(實際上的90^o^ FOV 看起來會比原始的還要寬一點)
    ![](https://i.imgur.com/c0Oiuwx.png)
    - FOV: 75.9375^o^(original) v.s. 76^o^(調整到76^o^，視覺上差異不大，表示原始的畫面 FOV 約略為這個數字)
    ![](https://i.imgur.com/w1SFQ5M.png)




    這邊我認為，`raycaster.h`裡面的`INV_FACTOR` 這個參數，要改成和 `FOV` 相關，才能使誤差降低，且可以隨著 `FOV` 的修改而改動，定義應如下:
    `INV_FACTOR` = $\dfrac{1}{2}*\dfrac{W}{2tan\dfrac{FOV}{2}}$

    
## raycaster.h
```cpp=8
#define SCREEN_WIDTH (uint16_t) 320
#define SCREEN_HEIGHT (uint16_t) 256
#define SCREEN_SCALE 2
#define FOV (double) (M_PI / 2)
#define INV_FACTOR (float) (SCREEN_WIDTH * 95.0f / 320.0f)
#define LOOKUP_TBL
#define LOOKUP8(tbl, offset) tbl[offset]
#define LOOKUP16(tbl, offset) tbl[offset]

#define MAP_X (uint8_t) 32
#define MAP_XS (uint8_t) 5
#define MAP_Y (uint8_t) 32
#define INV_FACTOR_INT ((uint16_t)(SCREEN_WIDTH * 75))
#define MIN_DIST (int) ((150 * ((float) SCREEN_WIDTH / (float) SCREEN_HEIGHT)))
#define HORIZON_HEIGHT (SCREEN_HEIGHT / 2)
#define INVERT(x) (uint8_t)((x ^ 255) + 1)
#define ABS(x) (x < 0 ? -x : x)
```
Explaination of each macro

## renderer.cpp
這邊做的事情是前面提 Raycasting 演算法時講到，將每一個 column 做 render 的部份
- 給予目前玩家的座標位置和 POV
```cpp
    _rc->Start(static_cast<uint16_t>(g->playerX * 256.0f),
               static_cast<uint16_t>(g->playerY * 256.0f),
               // now,  the range is changed from [0, 2*pi) to [0, 1024)
               static_cast<int16_t>(g->playerA / (2.0f * M_PI) * 1024.0f));
```
- One column computation for each for loop.
```cpp
    // Draw pixel of column x
    for (int x = 0; x < SCREEN_WIDTH; x++) {
        uint8_t sso;
        uint8_t tn;
        uint8_t tc;
        uint16_t tso;
        uint16_t tst;
        uint32_t *lb = fb + x;   
```
Parameters:
- sso: Half height of wall (in y direction)
- tn: The texture number, used for different texture (if available)
- tc: The initial x coordinate of texture
- tso: The initial y coordinate of texture
- tst: The step of pixel moving in texture.
E.g. 
Each wall on the screen takes 32 pixels height, tst = 64 / 32 
Each wall on the screen takes 64 pixels height, tst = 64 / 64
(The next row on screen should take texture[cur + tst\*64])
- lb: The pointer to buffer which is used for rendering. We assign value (data type: uint32_t for ARGB) for all (SCREEN_WIDTH \* SCREEN_HEIGHT) elements.
- E.g.
For first column, 
    - the wall height is greater than screen height. Set `sso=128`.
    - the wall parallels to x-axis. Set `tn=0`.
    - right shift `tc` 10 bits to get `tx` (the xth column in texture file: `g_texture8 in ray_caster.h`)
    - right shift tso 10 bits to get `ty` (the yth row in texture file)
![](https://i.imgur.com/3fceTri.png)

- Get the parameters mentioned above.
```cpp
        _rc->Trace(x, &sso, &tn, &tc, &tso, &tst);
```
- `HORIZON_HEIGHT` is half of `SCREEN_HEIGHT` (128). If `sso` is greater than 128, assign `sso` 128 and `ws` 0. `ws` is the height for both sky and floor.
```cpp
        int16_t ws = HORIZON_HEIGHT - sso;
        if (ws < 0) {
            ws = 0;
            sso = HORIZON_HEIGHT;
        }
```
- First sub for loop: Draw sky
```cpp
        for (int y = 0; y < ws; y++) {
            *lb = GetARGB(96 + (HORIZON_HEIGHT - y), 0);
            lb += SCREEN_WIDTH;  // Move to next row
        }
```
- Second sub for loop: Draw wall
```cpp
        uint16_t to = tso;
        uint16_t ts = tst;
        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]; // column: tx, row: ty

            to += ts;

            if (tn == 1 && tv > 0) {
                // dark wall
                tv >>= 1;
            }
            *lb = GetARGB(tv, 1);
            lb += SCREEN_WIDTH;  // Move to next row
        }
```
- Last sub for loop: Draw floor
```cpp
        for (int y = 0; y < ws; y++) {
            *lb = GetARGB(96 + (HORIZON_HEIGHT - (ws - y)), 2);
            lb += SCREEN_WIDTH;  // Move to next row
        }
```
## 座標系
![](https://i.imgur.com/GqSh2Uw.png)


## raycaster_fixed.cpp
### int16_t RayCasterFixed::MulS
Multiply the trigonometric function value `v` and deltaX/deltaY which is computed in `CalculateDistance` function
```cpp=
int16_t RayCasterFixed::MulS(uint8_t v, int16_t f)
{
    const uint16_t uf = MulU(v, static_cast<uint16_t>(ABS(f)));
    if (f < 0) {
        return ~uf + 1;
    }
    return uf;
}
```
### uint16_t RayCasterFixed::MulU
Here, v is trigonometric function value. Actually, v is not real trigonometric function value. The real value is $\dfrac{v}{256}$.

In other words, the result is $\dfrac{v*f}{256}$.

The result (`hm + (lm >> 8)`) equls to $\dfrac{v*f}{256}$.
> $\dfrac{v*f}{256} \\= \dfrac{v*(f\_h*256+f\_l)}{256}\\=\dfrac{v*f\_h*256}{256}+\dfrac{v*f\_l}{256}\\=hm + \dfrac{lm}{256}$
```cpp=
uint16_t RayCasterFixed::MulU(uint8_t v, uint16_t f)
{
    const uint8_t f_h = f >> 8; 
    const uint8_t f_l = f % 256; 
    const uint16_t hm = v * f_h;
    const uint16_t lm = v * f_l;
    return hm + (lm >> 8);
}
```

### inline int16_t RayCasterFixed::AbsTan
Get |tanθ| or |cotθ|, depending on `lookupTable` we pass.

```cpp=
inline int16_t RayCasterFixed::AbsTan(uint8_t quarter,
                                      uint8_t angle,
                                      const uint16_t *lookupTable)
{
    if (quarter & 1) {
        return LOOKUP16(lookupTable, INVERT(angle));
    }
    return LOOKUP16(lookupTable, angle); 
}
```
Suppose we want to get tangent value here.
If quarter is 0 or 2, return tan(angle).
![](https://i.imgur.com/DrBTuSv.png)
If quarter is 1 or 3, return tan(256-angle).
![](https://i.imgur.com/2PE68XQ.png)

### void RayCasterFixed::LookupHeight
According to the distance between player and wall, lookup the tables to get wall height and texture step. It's observed that height and texture step are constants when the distance is greater than a number (line8-9).
```cpp=
void RayCasterFixed::LookupHeight(uint16_t distance,
                                  uint8_t *height,
                                  uint16_t *step)
{
    if (distance > 255) {
        const uint16_t ds = distance >> 3;
        if (ds > 255) {
            *height = LOOKUP8(g_farHeight, 255);
            *step = LOOKUP16(g_farStep, 255);
        } else {
            *height = LOOKUP8(g_farHeight, ds);
            *step = LOOKUP16(g_farStep, ds);
        }
    } else {
        *height = LOOKUP8(g_nearHeight, distance);
        *step = LOOKUP16(g_nearStep, distance);
    }
}
```
## raycaster_float.cpp
理解了 Raycasting 的原理之後，開始著手解釋使用浮點數版本的程式碼


## Problems
### Wrong wall judgment and map display
> Rererence: [sammer1107](https://hackmd.io/@sammer1107/hw5_render)
- As figure shown below, the view using fixed-point raycaster looks farther from player. This problem occurs when player reaches two borders which do not include origin point
![](https://i.imgur.com/EU25zpy.png)
![](https://i.imgur.com/YTJqa2D.png)
- Also, the map showed on the window and the map given in `raycaster_data.h` do not match.
Standing at position (1, 1) and view angle is 0^o^. We can see that there is an additional aisle.
![](https://i.imgur.com/Ib6A2Lx.png)
Standing at position (26, 1) and view angle is 90^o^. We can see that original space is replaced by wall.
![](https://i.imgur.com/Ej0Ednp.png)


We need to change the conditional statement in `raycaster_fixed.cpp` 
```cpp=61
inline bool RayCasterFixed::IsWall(uint8_t tileX, uint8_t tileY)
{
    if (tileX > MAP_X - 1 || tileY > MAP_Y - 1) {
        return true;
    }
    return LOOKUP8(g_map, (tileX >> 3) + (tileY << (MAP_XS - 3))) &
           (1 << (8 - (tileX & 0x7)));
}
```
and `raycaster_float.cpp`
```cpp=6
bool RayCasterFloat::IsWall(float rayX, float rayY)
{
    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)));
}
```

Now, as we know that 2 functions are responsible for same thing. We only take one to explain.

In `raycaster_fixed.cpp`, first we need to make sure that the space outside the given map is recognized as wall. (g_map is given in `raycaster_data.h`).

We modify line 64 as below:
```cpp=61
inline bool RayCasterFixed::IsWall(uint8_t tileX, uint8_t tileY)
{
    // Check available space
    if (tileX < 0 || tileY < 0 || tileX > MAP_X - 1 || tileY > MAP_Y - 1) {
        return true;
    }
    return LOOKUP8(g_map, (tileX >> 3) + (tileY << (MAP_XS - 3))) &
           (1 << (8 - (tileX & 0x7)));
}
```
Then, we need to check if each grid is wall in the available space.
Take a look at ==g_map==. We can find that it is a 32\*32 square. 

Here, ==1== represents the wall.
```cpp
const uint8_t LOOKUP_TBL g_map[] = {
    0b00000000, 0b10000000, 0b00000000, 0b00000000, 
    0b01111010, 0b10111111, 0b11111111, 0b00000000, 
    0b00111000, 0b10100000, 0b00001000, 0b01001100,
    0b01000001, 0b00000100, 0b00100100, 0b00001100, 
    0b10000000, 0b10001010, 0b00000010, 0b01011100, 
    0b00000001, 0b11000100, 0b00000110, 0b00001100,
    0b00000000, 0b11010010, 0b00010000, 0b00001100, 
    0b01001100, 0b10010000, 0b00000000, 0b00111100,

    0b00100011, 0b10100100, 0b00000100, 0b00001100, 
    0b00000000, 0b11000001, 0b10001000, 0b00001100, 
    0b00110000, 0b10011100, 0b00111000, 0b01111100,
    0b00000011, 0b00000000, 0b00000000, 0b00001100, 
    0b00011111, 0b11111110, 0b11111111, 0b11111100, 
    0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 
    0b00000000, 0b00000000, 0b00000000, 0b00000000,

    0b00000000, 0b00000000, 0b00000000, 0b00000000, 
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 
    0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 
    0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 
    0b00000000, 0b00000000, 0b00000000, 0b00000000,

    0b00000000, 0b00000000, 0b00000000, 0b00000000, 
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 
    0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 
    0b00000000, 0b00000000, 0b00000000, 0b00000000, 
    0b00000000, 0b00000000, 0b00000000, 0b00000000,
    0b00000000, 0b00000000, 0b00000000, 0b00000100, 
    0b00000000, 0b00000000, 0b00000000, 0b00000001};
```

For example, if we want to check whether coordinate (16, 16) is wall or not, we need to check bit7 of  g_map[62]
> bit 7 6 5 4 3 2 1
> 0b  0 0 0 0 0 0 0

Consider how to get the index of the array value and bit of the chosen value of (x, y):

- The index of the array = ==x / 8 + y * 4==
(See the array above, each value has 8 bits. 4 values are in a row.)
- The bit of the chosen value:
For each x, the chosen bit table as shown below:

    | bit | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
    | - | - | - | - | - | - | - | - | - |
    | x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
    | x | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
    | x | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
    | x | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
    In order to check the bit is 0 or not, we can use a mask to do it.

    Observe the table above, we can get ==mask = 1 << (7 - x & 0x7)==

Convert the conversion formula mentioned above to code, we modify line 67:
```cpp=61
inline bool RayCasterFixed::IsWall(uint8_t tileX, uint8_t tileY)
{
    // Check available space
    if (tileX < 0 || tileY < 0 || tileX > MAP_X - 1 || tileY > MAP_Y - 1) {
        return true;
    }
    return return g_map[(tileX >> 3) + (tileY << 2)] & (1 << (7 - (tileX & 0x7)));
}
```
and modify the function in raycaster_float.cpp:
```cpp=6
bool RayCasterFloat::IsWall(float rayX, float rayY)
{
    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 << 2)] & (1 << (7 - (tileX & 0x7)));
}
```
- Result
The display of border in two version are the same.
![](https://i.imgur.com/wI2lUUn.png)
The redundant aisle disappears.
![](https://i.imgur.com/UZ26Vut.png)
The missing space appears.
![](https://i.imgur.com/FRQGiy1.png)

### Wall disappears when player is too close to border
> Rererence: [sammer1107](https://hackmd.io/@sammer1107/hw5_render)

- Standing at position (1.00186, 1.0053) and view angle is 4.02641. We can see the wall disappears. 
![](https://i.imgur.com/8X21Yq8.png)
Take a look at `raycaster_float.cpp`:
If the distance is not greater than zero, the variables for wall rendering will be set to 0.
    ```cpp=150
        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;
        }
    ```
    And why the distance is 0?

    See function `float RayCasterFloat::Distance`:
`startDeltaX` 和 `startDeltaY` 是為了讓我們得到第一條水平/垂直線上交點位置，用以接下來判斷該位置所處的網格是否為牆壁。

    這邊的寫法會使得 x 或 y 座標為整數時，跳過檢查一開始的網格，直接往 x±1 或 y±1 座標的網格做檢查。
    ```cpp=52
        if (rayA <= M_PI_2) {
            startDeltaX = (1 - offsetY) * tan(rayA);
            startDeltaY = (1 - offsetX) / tan(rayA);
        } else if (rayA <= M_PI) {
            if (offsetY == 0) {
                startDeltaX = (1) * fabs(tan(rayA));
            } else {
                startDeltaX = (offsetY) *fabs(tan(rayA));
            }
            startDeltaY = -(1 - offsetX) / fabs(tan(rayA));
        } else if (rayA < 3 * M_PI_2) {
            if (offsetY == 0) {
                startDeltaX = -(1) * fabs(tan(rayA));
            } else {
                startDeltaX = -(offsetY) *fabs(tan(rayA));
            }
            if (offsetX == 0) {
                startDeltaY = -(1) / fabs(tan(rayA));
            } else {
                startDeltaY = -(offsetX) / fabs(tan(rayA));
            }
        } else {
            startDeltaX = -(1 - offsetY) * fabs(tan(rayA));
            if (offsetX == 0) {
                startDeltaY = (1) / fabs(tan(rayA));
            } else {
                startDeltaY = (offsetX) / fabs(tan(rayA));
            }
        }
    ```
    於是將`startDeltaX` 和 `startDeltaY` 整數時會跳到下一個整數的部份移除，此問題就可以解決
    ```cpp
        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));
        }
    ```

- Result
![](https://i.imgur.com/cIgpYzS.png)

## Wrong wall appearing
- Standing at position (3.16511, 14.3508) and view angle is 1.03001. We can see wrong wall appears.
![](https://i.imgur.com/87d83P4.png)
Take a look at `raycaster_fixed.cpp`:
    ```cpp
        if (distance >= MIN_DIST) {
            *textureY = 0;
            LookupHeight((distance - MIN_DIST) >> 2, screenY, textureStep);
        } else {
            *screenY = SCREEN_HEIGHT >> 1;
            *textureY = LOOKUP16(g_overflowOffset, distance);
            *textureStep = LOOKUP16(g_overflowStep, distance);
        }
    ```

    Here, we determine the height of wall using `LookupHeight` function if the distance is greater than MIN_DIST.

    In function `LookupHeight`, we can see if the distance is greater than 255, we will use `g_farHeight` table to find the value of `*height`, otherwise table `g_nearHeight` will be used.

    If the distance is greater than 255, we use `ds`. If `ds` is greater than 255, we set `*height` as a constant. (NO matter how far the distance is, the wall keep the same height.)
    
    However, we can see after line 10, we re-assign value to `*height`. This make the assignment for condition (ds >= 256) fail. And because ds is greater than 255, the index we access will exceed the range of `g_farHeight` table.
    
    Finally, the wrong number may be assigned.
    ```cpp=
    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);
        }
    }
    ```
    
    Hence, adding else conditional statement so that the value in condition (ds >= 256) may not be assign again.
    ```cpp=
    void RayCasterFixed::LookupHeight(uint16_t distance,
                                      uint8_t *height,
                                      uint16_t *step)
    {
        if (distance > 255) {
            const uint16_t ds = distance >> 3;
            if (ds > 255) {
                *height = LOOKUP8(g_farHeight, 255) ;
                *step = LOOKUP16(g_farStep, 255);
            } else{
            *height = LOOKUP8(g_farHeight, ds);
            *step = LOOKUP16(g_farStep, ds);
            }
        } else {
            *height = LOOKUP8(g_nearHeight, distance);
            *step = LOOKUP16(g_nearStep, distance);
        }
    }
    ```
- Result
![](https://i.imgur.com/KvJZNSW.png)
