研讀筆記: Raycasting

source

Introduction

Raycasting 是一個算繪的技巧，在 2D 呈現 3D 的視野。在電腦運算不夠快的時候是沒辦法跑 3D 引擎，這時候 raycasting 就是一個好辦法。

Raycasting 速度非常的快，因為只需要計算完螢幕上每個垂直的線就好，使用這個方法著名的遊戲 Wolfenstein 3D (德軍總部3D)。

The Basic Idea

基本的 raycasting 觀念是地圖是一個 2D 網狀方格，每一個方格都是 0 (= no wall) 或是正數 (= wall with a certain color or texture)。

在屏幕的每一個 x 座標發射出一個射線(ray)，從角色的位置到他看的方向，讓這個射線朝向 2D 的地圖直到碰到一個是牆壁的方格。

如果碰到牆壁，計算出從玩家到牆壁中間的距離 (hit point)，用這個距離計算出牆壁要畫在螢幕上的高度，越遠越小。

要找出射線遇到的第一個牆壁就必須每次都從角色的位置出發，如果碰到牆壁 (hit)，迴圈就可以停止並計算出距離，最後畫牆壁到對應高度。如果射線位置沒有碰到牆壁，就要繼續追蹤到更遠的地方，從現在射線的距離加上一個特定的值 (step size)，繼續檢查，直到最後碰到牆壁。

不過這樣有可能會出錯漏掉一些狀況，如下圖。

當然你把這個前進的距離設定的越小，就越不容易有錯誤。

有更好的解法是去確定每一個遇到的牆面，假設我們格子的大小是 1，每一個牆面就會是一個整數，這樣我們的 step size 就不會是一個常數。

這樣我們就不會錯過任何牆壁，可以應用上一個演算法基於 DDA (Digital Differential Analysis)，可以幫我們快速的找到碰到的牆壁。

有一些 raytracers 會用 Euclidean angles 去表示一個角色和射線的方向，用其他角度決定 FOV(Field Of View)，不過我發現如果用 vectors 跟一個相機 (camera) 更容易，玩家的位置就是一個向量 (x y 座標 position vector)，現在我們把方向也當作 vector，所以方向向量 (direction vector) 現在被 x y 座標決定。

這個方法需要額外的向量，camera plane vector，在真實的 3D 引擎也會有一個 camera plane，會有兩個向量 u v，但是 Raycasting 是 2D 地圖所以這邊的 camera plane 只是一條線，用一個向量表示，這個向量必須垂至於方向向量，camera plane 代表電腦的螢幕，

上圖中綠色的點就是位置向量(pos)，中間黑線結束在黑點上的是方向向量(dir)，所以黑點就是 pos+dir，從黑點到右邊藍點是 camera plane(plane)，所以左邊的藍點是 pos+dir-plane 右邊的藍點是 pos+dir+plane。

圖中其他的紅線就是射線，這些射線就可以很輕易的被計算出來。兩個最外圍的紅線所夾成的角度就是 FOV(Field Of Vision)，這個大小被 direction vector 和 plane 大小給決定。

如果玩家旋轉視角，camera 也會跟著旋轉，因此射線就會自動跟著轉。

旋轉一個向量可以透過把向量乘以 rotation matrix，可以參考 旋轉矩陣 wiki

[ cos(a) -sin(a) ]
[ sin(a)  cos(a) ]

Untextured Raycaster

從基本的開始做一個 Untextured Raycaster，這個包含 fps 和在移動時的碰撞旋轉。

cameraX 是 camera plane 的 x 座標，螢幕的最右邊是 1 中間是 0 最左邊是 -1。

 for(int x = 0; x < w; x++)
    {
      //calculate ray position and direction
      double cameraX = 2 * x / double(w) - 1; //x-coordinate in camera space
      double rayDirX = dirX + planeX * cameraX;
      double rayDirY = dirY + planeY * cameraX;

接下來是有關 DDA 演算法的計算。
mapX mapY 是代表目前射線所在的方格。射線的位置是一個浮點數，但是 mapX mapY 只是方格座標。
sideDistX sideDistY 是射線從一開始的位置需要往前走的距離，後面的程式會有點改變。
deltaDistX deltaDistY 是射線必須移動到下一個 x y 的距離。

這樣我們可以找到 deltaDistX deltaDistY 透過以下公式。

deltaDistX = sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX))
deltaDistY = sqrt(1 + (rayDirX * rayDirX) / (rayDirY * rayDirY))

經過化簡後。

deltaDistX = abs(1 / rayDirX)
deltaDistY = abs(1 / rayDirY)

      //which box of the map we're in
      int mapX = int(posX);
      int mapY = int(posY);

      //length of ray from current position to next x or y-side
      double sideDistX;
      double sideDistY;

       //length of ray from one x or y-side to next x or y-side
      double deltaDistX = std::abs(1 / rayDirX);
      double deltaDistY = std::abs(1 / rayDirY);
      double perpWallDist;

      //what direction to step in x or y-direction (either +1 or -1)
      int stepX;
      int stepY;

      int hit = 0; //was there a wall hit?
      int side; //was a NS or a EW wall hit?

接下來我們要找到，stepX stepY 就是行走的方向，還有計算 sideDistX sideDistY。

如果射線方向是負的 stepX -1 反之證的就是 +1，如果是 0 則沒關係。

再找到這些後就可以實行 DDA。

sideDistX sideDistY 會隨著每次前增加上 delta 的距離，mapX mapY 也會跟著增加，隨著 stepX stepY。

做完 DDA 後就會得到射線道牆的距離，就可以計算出牆壁對應的高度。

---

這邊我們不是用到角色的距離而是用到 camera plane 的距離，用來避免 fisheye effect，就是所有的牆壁都會變成圓形。

下面的圖顯示出為甚麼我們要用到 camera plane 的距離而不適到角色位置的距離。在這張圖，玩家會直接看到牆壁，但是紅色的射線會有不同的距離，會導致牆壁有不同的高度，所以會產生 rounded effect。