# 2020q3 Homework5 (render)
contributed by < `guaneec` >

###### tags: `sysprog2020`

Quick links:
* [Problem description](https://hackmd.io/@sysprog/2020-render)
* [Submissions](https://hackmd.io/@sysprog/2020-homework5)

## Ray casting
Matt Godbolt did [a video](https://www.youtube.com/watch?v=eOCQfxRQ2pY) on Wolfenstein 3D's map renderer. It covers pretty much everything in the [original repo](https://github.com/rohatsu/raycaster).

## Bugs

### 1. Faraway corner looks close
:::success
[Fix](https://github.com/guaneec/raycaster/commit/7ed13c2b810b3710bdb9b232f763ce7bfdb28035)
:::

### 2. Uncapped frame rate (feature?)

### 3. Weird triangles
:::success
[Fixed](https://github.com/guaneec/raycaster/commit/d541b804f8fb1d38e677747297776e605ebb1246)
:::

### 4. Off-by-one error at x=30 and y=30
:::success
[Fix](https://github.com/guaneec/raycaster/commit/96f137eb089f5d0aa9ac6f8654de5cc884d81204)
:::

### 5. Walls too tall when viewed from large incident angles

:::success
[Fix](https://github.com/guaneec/raycaster/commit/9ec596118b1d0e7cb0fab00fc82a45578019c46c)
:::

This is a tricky one. In the mathematical world, the algorithm of intercepts is sound. However, we are dealing with finite precision machine numbers. An implication of this is instead of a nice single ray, we actually are processing two rays in parallel. For most angles, the difference between the two rays too small to be noticeable. With small angles however, the difference can cause the intercept points to be processed in the wrong order and mess up our calculation of coordinates.

The fix I did feels hacky. What I did is I manually reassign the intercept point if a misordering is detected. This introduces a small error but at least the ordering is correct now and the artefacts are gone.

TODO: add figures.

In the original repo, the author attempted to deal with the artefacts by pushing the small angles to the non-problematic ones:

// neutralize artefacts around edges
switch (rayAngle % 256) {
case 1:
case 254:
    rayAngle--;
    break;
case 2:
case 255:
    rayAngle++;
    break;
}
rayAngle %= 1024;

However, as seen above, the artefacts are still present.

### 6. Bent walls

### 7. Wall vanishing when player is on integer x or y
:::success
[Fix](https://github.com/guaneec/raycaster/commit/81c60f783856be942c1d2ab04cad61f423f8416f)
:::

## Generating tables

I generated trig values in a header file generated in build time ([commit](https://github.com/guaneec/raycaster/commit/7e35ffb8da66efbc1215b8aecf691d0627779e81)). This works but we can do better.

In C++, there are `constexpr`s -- constant expressions whose value can be evaluated in compile time. Instead of stitching together header files with tools, we can simply pre-calculate the values in compile time.

For initialization of complex objects, [it's recommended to wrap the initialization process in a lambda expression](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Res-lambda-init). Since C++17, [return values of lambdas can be constant expressions](https://timsong-cpp.github.io/cppwp/n4659/expr.prim.lambda#closure-4).

There are also additional benefits that comes with this. Since undefined behaviors are not constexpr, the compiler will refuse to compile if generating the tables involves UBs. For example, in the generation of `g_cotan`:

static constexpr const std::array<uint16_t, 256> g_cotan_stda = ([]() constexpr {
    std::array<uint16_t, 256> out{};
    for (int i = 0; i < 256; ++i) {
        out[i] = static_cast<uint16_t>((256.0f / tan(i * M_PI_2 / 256.0f)));
    }
    return out;
})();

constexpr const uint16_t* g_cotan = g_cotan_stda.data();

The `precalculator` version compiles but our constexpr version doesn't:

The compiler detects a division-by-zero at compile time!

In a similar fashion, in the computation of `g_cos`:

static constexpr const std::array<uint8_t, 256> g_cos_stda = ([]() constexpr {
    std::array<uint8_t, 256> out{};
    for (int i = 0; i < 256; ++i) {
        out[i] = static_cast<uint8_t>(256.0f * cos((i) / 1024.0f * 2 * M_PI));
    }
    return out;
})();

constexpr const uint8_t *g_cos = g_cos_stda.data();

an error is thrown since `256.0f` to uint8_t conversion is undefined in [C++][2] (and [C][1]).

[1]: https://port70.net/~nsz/c/c11/n1570.html#6.3.1.4p1
[2]: https://timsong-cpp.github.io/cppwp/n4659/conv.fpint#1

## The map
The map is stored in a flattened bitstring `g_map` in `raycaster_data.h`. Its content is pretty-printed below for reference:

     yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
     ================================
     00000000001111111111222222222233
     01234567890123456789012345678901
x=00 ................................
x=01 .....#..........................
x=02 .#.#...#........................
x=03 .##.....#.#.....................
x=04 .##.......#.#...................
x=05 .##....#....#...................
x=06 .......#....#...................
x=07 .#......#..##...................
x=08 ................................
x=09 ###.#######.#...................
x=10 .....##..#..#...................
x=11 .##.....#...#...................
x=12 .#....##..#.#...................
x=13 .#..#.....#.#...................
x=14 .#.#.#..#.#.#...................
x=15 .#..#.#.....#...................
x=16 ................................
x=17 .#.......#..#...................
x=18 .#..........#...................
x=19 .#.#......#.#...................
x=20 .#....#...#.#...................
x=21 .##......##.#...................
x=22 .#.#.#..#...#...................
x=23 .#..##......#...................
x=24 ................................
x=25 ............#...................
x=26 ..#.#.....#.#...................
x=27 .......#..#.#...................
x=28 ....#..#..#.#...................
x=29 ..###########...................
x=30 ..###########...................
x=31 ................................

## Colored textures

Adding colored texture is simple. The texture created by the game accepts 32 bits for each pixel (`SDL_PIXELFORMAT_ARGB8888`). To use colored textures, simply replace the original texture data `uint8_t[]` with `uint32_t[]`.


:::warning
Nice! Finally, you figured out this. Then, can you minimize the memory usage assocated with the texture? That is, avoid using ARGB color space.
:notes: jserv
:::