2020q3 Homework5 (render)

contributed by < quantabase13 >

修正 Raycaster( floating point part )

• overflowing problem

在 void RayCasterFloat::Trace 中的程式碼：

*screenY = INV_FACTOR / distance;

screenY 是指向 uint8_t type 的 pointer，而 INV_FACTOR 和 distance 卻是 float type，這造成當 INV_FACTOR / distance 大於 256 時會出現 overflow 的情況，連帶影響到後面的程式碼

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

我修正的方式是先檢查 INV_FACTOR / distance 是否大於 256，如果是的話就直接使用 INV_FACTOR / distance 計算 txs 。

float f =  INV_FACTOR / distance;  
        if (f > 256) {
        *screenY = SCREEN_HEIGHT >> 1; 
        auto txs = (  INV_FACTOR / distance  * 2.0f);
        if (txs != 0) {
            *textureStep = (256 * distance / INV_FACTOR /2.0f) * 256 ;
            if (txs > SCREEN_HEIGHT) {          
                auto wallHeight = (txs - SCREEN_HEIGHT) / 2; 
                Height = wallHeight;
                *textureY = wallHeight * (256 / txs) * 256 ;
            }
        }
            return;
        }

修正 Raycaster( fixed point part )

寫這個部份作業時，觀察到以下程式碼

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

從觀察 float point 的程式碼經驗，推測可能是與牆面的距離計算出現問題。

可以發現程式將

$2\pi$ 弧度 分成 1024 等份。
另外，觀察 ray_caster_table.h 裡的 g_tan[256] ，再另外觀察 C 內建的 tan() 輸出的結果，可以發現 g_tan[256] 記的就是 tan(0) 到 tan(90) (單位：degree )的值乘上 256 的結果。
根據以上，再觀察 void RayCasterFixed::CalculateDistance 的程式碼，可以了解 fixed point 的實作是如何計算 distance 的：

1. 求 offsetX、offsetY

    const uint8_t offsetX = rayX % 256;
    const uint8_t offsetY = rayY % 256;

2. 根據 offsetX、offsetY 算出 interceptX、interceptY
   在這裡程式碼會根據角度所屬 quarter 的不同，調整計算方式。程式碼中角度方向與座標軸增長方向的對應圖如下：
   

最後我發現距離計算出現問題的部份，都是在 OffsetY/X 很小，而 rayAngle % 256接近255的情況。
下面這張圖是理想中的計算結果：

下面這張圖是實際計算出的結果：

注意到使用 Offset = 4 算出的值 217 低於正常的 282。
之所以會造成這種結果， 原因是tan(angle) 在 angle 接近 90 度的範圍內變化程度遠大於小角度範圍內的變化程度，導致把 90度 分成 256 等分的作法會在高角度時出現大的誤差。
目前我對此並沒有好的解決方式。參考 guaneec 的方法，把該方法的思路整理如下：
這是原來的實作：

        for (;;) {
            while ((tileStepY == 1 && (interceptY >> 8 < tileY)) ||
                   (tileStepY == -1 && (interceptY >> 8 >= tileY))) {
                tileX += tileStepX;
                if (IsWall(tileX, tileY)) {
                    goto VerticalHit;
                }
                interceptY += stepY;
            }                  
            while ((tileStepX == 1 && (interceptX >> 8 < tileX)) ||
                   (tileStepX == -1 && (interceptX >> 8 >= tileX))) {
                tileY += tileStepY;
                if (IsWall(tileX, tileY)) {
                    goto HorizontalHit;
                }
                interceptX += stepX;
            }
        }

這是改善後的版本：

        for (;;) {
             auto ty = (tileY - tileStepY) * 256;
            if ((tileStepY == -1 && ty < interceptY) ||
                (tileStepY == 1 && ty > interceptY))
                interceptY = ty;

            while ((tileStepY == 1 && (interceptY >> 8 < tileY)) ||
                   (tileStepY == -1 && (interceptY >> 8 >= tileY))) {
                tileX += tileStepX;
                if (IsWall(tileX, tileY)) {
                    goto VerticalHit;
                }
                interceptY += stepY;
            }
            auto tx = (tileX - tileStepX) * 256;
            if ((tileStepX == -1 && tx < interceptX) ||
                (tileStepX == 1 && tx > interceptX)){
                    interceptX = tx;
                }                    
            while ((tileStepX == 1 && (interceptX >> 8 < tileX)) ||
                   (tileStepX == -1 && (interceptX >> 8 >= tileX))) {
                tileY += tileStepY;
                if (IsWall(tileX, tileY)) {
                    goto HorizontalHit;
                }
                interceptX += stepX;
            }
        }

這是程式碼想法的圖解：

在尋找障礙物的時候，每當行進方向改變，為了確保之後使用的 interceptX/Y 不會是錯誤的值，會先根據此時所在的格子位置計算出 intercept 的近似值。如果發現近似值與現在的 intercept 值大小順序與理論不符，代表 intercept 有誤，就使用近似值修正。

TODO

• 輸出算繪過程的 frame rate
• 利用 tools/precalculator.cpp 產生運算表格，修改相關程式碼，使得程式碼在編譯時期才去產生運算表格
• 解說現有 fixed-point 實作機制，並探討前述表格產生的機制
• 參照 C 語言：物件導向程式設計篇，透過建立共用介面 (interface) 的手法，將 raycaster 以 C99/C11 (或 gnu99/gnu11) 重寫，允許在執行時期載入 fixed-point 和 floating-point 為基礎的 renderer