2020q3 Homework5 (render)

contributed by < guaneec >

tags: sysprog2020

Quick links:

• Problem description
• Submissions

Ray casting

Matt Godbolt did a video on Wolfenstein 3D's map renderer. It covers pretty much everything in the original repo.

Bugs

1. Faraway corner looks close

Fix

2. Uncapped frame rate (feature?)

3. Weird triangles

Fixed

4. Off-by-one error at x=30 and y=30

Fix

5. Walls too tall when viewed from large incident angles

Fix

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

Fix

Generating tables

I generated trig values in a header file generated in build time (commit). This works but we can do better.

In C++, there are constexprs – 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. Since C++17, return values of lambdas can be constant expressions.

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++ (and C).

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[].

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

jserv