# 2020q3 Homework5 (render)
contributed by < `WeiCheng14159` >
###### tags: `sysprog2020`

## Introduction
**Raycasting is not the same as raytracing!** Raycasting is a fast semi-3D technique that works in realtime even on 4MHz graphical calculators, while **raytracing is a realistic rendering technique** that supports reflections and shadows in true 3D scenes, and only recently computers became fast enough to do it in realtime for reasonably high resolutions and complex scenes.

## Floating Point raycaster explanation
### Game::Move
- `game.cpp`
- `m` is an integer variable.
- `m=1` moving forward.
- `m=0` not moving.
- `r` is an integer variable.
- `m=-1` turn to the left.
- `m=1` turng to the right.
- `m=0` not turning.
- `seconds` is the time duration (in sec) between this frame update and the previous one
- `playerA` is the line of sight of the player.
- Range from $- 2 \pi$ to $2 \pi$
- `playerX` and `playerY` is the current x,y coordinate of a player in the map

void Game::Move(int m, int r, float seconds)
{
    playerA += 0.05f * r * seconds * 25.0f;
    playerX += 0.5f * m * sin(playerA) * seconds * 5.0f;
    playerY += 0.5f * m * cos(playerA) * seconds * 5.0f;

    while (playerA < 0) {
        playerA += 2.0f * M_PI;
    }
    while (playerA >= 2.0f * M_PI) {
        playerA -= 2.0f * M_PI;
    }
    ...
}

### Renderer::TraceFrame
- `TraceFrame` function
- Call `Start` member function of `RayCaster` class.
- This initialized the initial position and direction of a player.
- Call `Trace` member function of `RayCaster` class.
- This trace many rays in the view of player

void Renderer::TraceFrame(Game *g, uint32_t *fb)
{
    _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));

    for (int x = 0; x < SCREEN_WIDTH; x++) {
        uint8_t sso;
        uint8_t tc;
        uint8_t tn;
        uint16_t tso;
        uint16_t tst;
        uint32_t *lb = fb + x;

        _rc->Trace(x, &sso, &tn, &tc, &tso, &tst);
        ...
    }
}

### RayCasterFloat::Trace
- `Trace` member function. This function is called `SCREEN_WIDTH` times for every frame.
- Each red ray in LHS of the following picture represents a function call to the `Trace` function. This function calculates the distance to the wall along the ray direction.
- 
- `deltaAngle` is the angle between a ray and the central point of view of a player (range: $- \frac{\pi}{4}$ to $\frac{\pi}{4}$)
- `lineDistance` is the wall height seen by the player. The function call `Distance` will be explained later.
- `distance` is the undistorted wall height with fisheye correction. In short, fisheye effect is common in raycasting application and can be fixed by a cosine function. Detail explanation can be found [here](https://youtu.be/gYRrGTC7GtA?t=874)
- The following figure shows the fisheye effect (with the cosine correction removed). Which is due to the lengths of ray on both sides are longer than the one in the center. 

    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) * FOV / 2);
        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 > 255.0f) ? 255 : 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;
        }
    }

### RayCasterFloat::Distance
- `Distance` member function. Given the current x (playerX) and y (playerY) position in the map and the orientation (rayA) of a player. Return the distance to the nearest obstacles along that ray.
- **The key idea of raycasting happens here: The returned distance will be used to determine the wall height drawn in the window. Which makes our eyes believe this 2D game view looks like 3D. (An object that's away from us shall look smaller than the one that's closer to us.)**
- `rayA` is the orientation. It will be converted to the value between 0 and $2 \pi$
- `rayX` and `rayY` is the starting point of a ray (in float). Both are initialized to the x, y position of a player.
- `tileX` and `tileY` are the integer part of a player's position
- `offsetY` and `offsetY` are the fraction part of a player's position
- Given `offsetX`, we can calculate the y-direction distance (`startDeltaY`) to the closest intercept of horizontal line. Similarly, given `offsetY`, we can calculate the x-direction distance (`startDeltaX`) to the closest intercept of vertical line.

    float RayCasterFloat::Distance(float playerX,
                                   float playerY,
                                   float rayA,
                                   float *hitOffset,
                                   int *hitDirection)
    {
        while (rayA < 0) {
            rayA += 2.0f * M_PI;
        }
        while (rayA >= 2.0f * M_PI) {
            rayA -= 2.0f * M_PI;
        }

        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);

        float startDeltaX, startDeltaY;
        ...

- The following diagram illustrates the case when $0 \leq \theta \leq \frac{\pi}{4}$ in the map (top view) coordinate.
- In this floating point caster, black lines are the integer coordinate.
- 
- Or as illustrated in this [video](https://youtu.be/gYRrGTC7GtA?t=471) where `rx` means `interceptX` and `ry` means `interceptY`, `xo` means `startDeltaX` and `yo` means `startDeltaY` in our code.
- 
- Continue on the `Distance` function, the following code calculates the distance to the nearest wall in the ray direction starting at the current position of the player
- `interceptX` and `interceptY` are the first intercept coordinate
- `stepX` and `stepY`
- The walls (or any obstacles) in the game are placed on the integer coordinate in the map. By checking the intercept point along the ray direction, we can find a wall in a very efficient way. Detail information can be found in this [article](https://lodev.org/cgtutor/raycasting.html)
- The nested while loop first search for a `verticalHit` (a ray intercept with the vertical line) then search for a `horizontalHit` (a ray intercept with the horizontal line).
- `IsWall` function detect a wall, will be explained later

        ...
        float interceptX = rayX + startDeltaX;
        float interceptY = rayY + startDeltaY;
        float stepX = fabs(tan(rayA)) * tileStepX;
        float stepY = fabs(1 / tan(rayA)) * tileStepY;
        bool verticalHit = false;
        bool horizontalHit = false;
        bool somethingDone = false;

        do {
            somethingDone = false;
            while (((tileStepY == 1 && (interceptY <= tileY + 1)) ||
                    (tileStepY == -1 && (interceptY >= tileY)))) {
                somethingDone = true;
                tileX += tileStepX;
                if (IsWall(tileX, interceptY)) {
                    verticalHit = true;
                    rayX = tileX + (tileStepX == -1 ? 1 : 0);
                    rayY = interceptY;
                    *hitOffset = interceptY;
                    *hitDirection = true;
                    break;
                }
                interceptY += stepY;
            }
            while (!verticalHit && ((tileStepX == 1 && (interceptX <= tileX + 1)) ||
                                    (tileStepX == -1 && (interceptX >= tileX)))) {
                somethingDone = true;
                tileY += tileStepY;
                if (IsWall(interceptX, tileY)) {
                    horizontalHit = true;
                    rayX = interceptX;
                    *hitOffset = interceptX;
                    *hitDirection = 0;
                    rayY = tileY + (tileStepY == -1 ? 1 : 0);
                    break;
                }
                interceptX += stepX;
            }
        } while ((!horizontalHit && !verticalHit) && somethingDone);

        if (!somethingDone) {
            return 0;
        }

        float deltaX = rayX - playerX;
        float deltaY = rayY - playerY;
        return sqrt(deltaX * deltaX + deltaY * deltaY);
    }

### RayCasterFloat::IsWall
- `IsWall` member function
- Given the position in the map coordinate, return whether there exist a wall

bool RayCasterFloat::IsWall(float rayX, float rayY)
{
    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 << (8 - (tileX & 0x7)));
}

## Fixed Point raycaster
### RayCasterFixed::Start
- `Start` member function initialize required variables
- In the fixed point notation, $2 \pi$ radian is represented by 1024 (11 bit binary) stored in `int16_t` datatype
- `_viewQuarter` is the quarter of view angle. Since 360 deg is divided into 4 quarters, `_viewQuarter` is the 9-th and 10-th bit of `playerA`
- `_viewAngle` is the angle in each quarter, which is the lower 8 bit of `playerA`

void RayCasterFixed::Start(uint16_t playerX, uint16_t playerY, int16_t playerA)
{
    _viewQuarter = playerA >> 8;
    _viewAngle = playerA % 256;
    _playerX = playerX;
    _playerY = playerY;
    _playerA = playerA;
}

### RayCasterFixed::Trace
- Given the `g_deltaAngle` and current `screenX` coordinate, a arctan lookup table `g_deltaAngle` is used to get the `rayAngle` directly

uint16_t rayAngle =
        static_cast<uint16_t>(_playerA + LOOKUP16(g_deltaAngle, screenX));

### RayCasterFixed::CalculateDistance
## Show FPS count
- Print out the FPS in the console in this [commit](https://github.com/WeiCheng14159/raycaster/commit/ad98e1e2f5566356ceded5aa50266b5aa5721dd7)

## Rendering issue
- Broken wall issue
- 
- Pointed out by RinHizakura in this [pull request](https://github.com/sysprog21/raycaster/pull/1), the "breaking wall" is caused by the numberical overflow problem by this line of code `*screenY = INV_FACTOR / distance;` When the player walk near the wall, the distance to a wall along the ray direction is very small. Thus, the value `INV_FACTOR / distance` exceeds 255, which is the limit for `screenY` that has type `uint8_t`
- Fix in this [commit](https://github.com/WeiCheng14159/raycaster/commit/143021a05393073f63486ce1822b759ab0aa1cfc)
- Wall ratio issue
- 
- The wall height looks different between two versions when a player walks near the wall. Point out by RinHizakura, this problem is caused by the inconsistent logic in the `IsWall` function
- Fix in this [commit](https://github.com/WeiCheng14159/raycaster/commit/ed0519dcedc6671b0f3521e9e91b8a644361df57)
- Missing wall & Wrong wall issue
- Missing wall 
- Wrong wall 
- This issue is reported by many students, I choose to rewrite the whole function to solve this problem because I found the original implementation hacky and hard to debug. I rewrite the `RayCasterFloat::Distance` function by decoupling find vertical hit and find horizontal hit. Which is the raycasting method I found in this [repository](https://github.com/3DSage/OpenGL-Raycaster_v1) and explained in this [video](https://www.youtube.com/watch?v=gYRrGTC7GtA) This solve both missing wall and wrong wall issue
- Code in this [commit](https://github.com/WeiCheng14159/raycaster/commit/b52f36c0e058a1775ae46d2a49ec7b076e1a626b)
- Also, I ceate this diagram to explain the logic of my code 

## Code cleanup & refactor
- Remove unused variable in this [commit](https://github.com/WeiCheng14159/raycaster/commit/e30cf2075ba05c63fed525361ca3ad2b111f49fe)
- Find a proper use of FOV marco in this [commit](https://github.com/WeiCheng14159/raycaster/commit/059f41b47979604a9411396f89e56412e5f79d17)
- Add missing big parentheses [commit](https://github.com/WeiCheng14159/raycaster/commit/a81595ef5f0c5b63d64f9123e1f6a68c490cf16e)

## Reference:
- https://lodev.org/cgtutor/raycasting.html
- http://www.dormando.me/post/fpga-raycaster/
- https://www.youtube.com/watch?v=gYRrGTC7GtA

## Goal
- 修正浮點數和定點數算繪程式展現的缺失，並提出改進 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](https://github.com/sysprog21/raycaster) 以 C99/C11 (或 gnu99/gnu11) 重寫，允許在執行時期載入 fixed-point 和 floating-point 為基礎的 renderer
- 對照研讀 [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](https://doom.fandom.com/wiki/Doom_rendering_engine) 和 [Casting Wolf3D-style Rays with an FPGA and Arduino](http://www.dormando.me/post/fpga-raycaster/)，解釋 [raycaster](https://github.com/sysprog21/raycaster) 運作原理，並探討後續的改進方案，例如更換彩色的貼圖素材 (texture)、引入遊戲元素 (sprite) 等等。