raycasting

raycating 이란

레이캐스팅(raycasting)은 2차원 맵을 3차원으로 원근감있게 만드는 렌더링 기술입니다.
(실제로 raycasting을 이용해 2d map을 3d로 변환한 모습)

raycasting의 특징

• 레이캐스팅은 스크린의 모든 수직선에 대해 계산만하면 되기때문에 속도가 빠릅니다

raycasting의 기본적인 원리

• 2차원 정사각형 그리드로 된 맵이 있습니다.
• 맵의 한 칸은 벽이거나 벽이 아님을 나타냅니다
• 화면의 모든 수직선에 대해 플레이어 위치에서 부터 시작하는 광선(ray)을 쏩니다
• 광선의 방향은 플레이어가 바라보는 방향 그리고 화면의 x좌표에 의존합니다
• 광선은 2d맵 위에서 벽에 부딪힐 때까지 직진하다가 벽에 부딪히면 적중지점으로부터 플레이어까지의 거리를 계산합니다
• 계산된 거리를 이용하여 벽의 높이가 화면에 얼마만큼 그려져야 하는지 결정됩니다 벽의 높이는 플레이어와 벽 사이의 거리가 멀수록 화면에 더 낮게 가까울수록 더 높게 표시됩니다

광선(ray)이 처음으로 부딪히는 벽을 찾는 방법

• 광선이 처음으로 부딪히는 벽을 찾으려면 광선을 플레이어의 위치에서부터 출발시켜서 광선이 벽에 부딪혔는지를 반복적으로 검사해야 합니다
• 레이캐스터는 일반적으로 광선의 위치에 일정한 값을 더해주며 벽에 부딪혔는지를 검사합니다 이렇게 할 시 벽에 부딪혔는데도 이를 놓치고 벽에 부딪히지 않았다고 판단할 가능성이 있습니다
  
  광선에 더해주는 값이 너무 클 경우 벽을 지나치는 문제가 생길 수 있다
  
  광선에 더해주는 값을 작게 만들면 벽에 도달했다고 확인할 수 있지만 이때도 정확한 값은 아니다.
  정확한 정밀도를 얻기 위해서는 검사간격이 무한히 작아져야하고 그렇게 될 시 계산이 무수히 일어나게 될 것이다.
  
  광선이 닿는 벽의 모든 면을 검사하는 방법이다 정사각형 한 칸의 너비를 1이라 지정하면 모든 벽면을 정수값으로 표한할 수 있다.
  이제 광선의 일정한 값만큼 검사하는 것이 아니라 현재 검사위치에서 다음 광선이 벽면과 맞닿는 위치에 따라서 거리가 달라지게 된다.
  이 방식을 이용하면 빠르게 연산도 가능하면서 높은 정밀도를 얻을 수 있다.

DDA(Digital Differential Analysis)알고리즘

dda알고리즘은 2차원 그리드를 지나가는 선이 어떤 네모칸과 부딪히는지 찾을 때 일반적으로 사용되는 속도가 빠른 알고리즘입니다.
dda알고리즘을 사용하면 광선이 맵에서 어떤 네모칸이랑 부딪히는지 찾아낼 수 있고, 벽에 부딪힌 것이 확인되면 dda알고리즘이 중단됩니다.

레이캐스팅에 필요한 값

• 플레이어의 위치 벡터(x좌표, y좌표)

• 플레이어의 방향 벡터(x좌표, y좌표)

• 카메라 평면 벡터(x좌표, y좌표)

• • 전체 카메라 평면 중 방향 벡터의 끝점으로부터 오른쪽 카메라평면의 끝점까지
• • 카메라 평면은 항상 방향벡터에 수직입니다.
• • 화면에서 특정 x좌표의 특정 광선은 플레이어 위치에서 시작하여 카메라 평면을 통과하는 광선입니다

• 방향 벡터 끝점 = 위치 벡터 + 방향 벡터

• 오른쪽 카메라평면의 끝점 = 방향 벡터 끝점 + 카메라 평면 벡터

• 왼쪽 카메라 평면의 끝점 = 방향 벡터 끝점 - 카메라 평면 벡터

• 광선의 방향 벡터

• • 광선의 방향 벡터 구하는 방법
    방향 벡터 + (카메라평면 벡터 * 배수)
    ex.) 카메라 평면의 오른쪽에서 1/3지점을 통과하는 광선의 방향벡터 구하는 방법 : 방향 벡터 + 카메라 평면 벡터 * 1 / 3

• FOV(Field of View)

• • 스크린의 왼쪽, 오른쪽의 경계 사이의 각도를 FOV라고 합니다
• • FOV는 방향 벡터 길이 : 카메라 평면 길이의 비율로 결정됩니다
• • 방향 벡터와 카메라 평면의 길이가 같은경우(1 : 1) FOV = 90º
    
• • 방향 벡터가 카메라 평면보다 길 경우 (LONG : 1) FOV = 90º ↓ 시야가 좁아져서 더 자세한 내용을 볼 수 있습니다
    
• • 방향 벡터가 카메라 평면보다 짧은 경우 (1 : LONG) FOV = 90º ↑ 시야가 넓어져서 더 많은 내용을 볼 수 있습니다
    

방향을 돌리는 방법

플레이어가 방향을 돌리면 방향 벡터와 카메라 평면 벡터가 모두 회전해야 합니다.
벡터를 회전시키려면 회전행렬과 곱해주면 됩니다

(회전행렬)

DDA알고리즘에서 필요한 값

• side dist Y : 시작점 ~ 첫번째 Y면을 만나는 점 까지 광선의 이동 거리

• delta dist Y : 첫번째 Y면을 만나고 바로 다음 Y면 까지 광선의 이동 거리

• side dist X : 시작점 ~ 첫번째 X면을 만나는 점 까지 광선의 이동 거리

• delta dist X : 첫번째 X면을 만나고 바로 다음 X면 까지 광선의 이동 거리

• delta dist 구하는 방법 : abs(1 / ray dir y or x)
  이렇게 구할 수 있는 이유는 delta dist들의 비율이 필요하기 때문이다

delta dist공식 유도

• side dist 구하는 방법 : ray dir의 방향에 따라서 map위치에 +-1을 해주고 delta dist를 곱해서 구한다
  

DDA 알고리즘 방법

1. 광선이 벽에 닿을때까지 루프를 돌린다
2. side dist가 더 작은 방향으로 map을 한칸 이동시킨다
3. side dist에 delta dist를 더해준다
4. 이동한 위치가 벽인지 확인 후 벽이 아니면 2번으로 돌아간다

3d 왜곡 방지 방법

플레이어 위치에서 광선을 쏜걸로 계산하게 되면 모든 벽이 둥글게 보이는 왜곡이 일어납니다.
이러한 현상을 방지하게위해 카메라 평면에서 광선을 쏜것처럼 보정해주면 왜곡이 방지되는 효과가 있습니다.

카메라평면에서 쏜것처럼 보정하는 방법(x방향으로 부딪힌 경우) : perpWallDist = (mapX - posX + (1 - stepX) / 2) / rayDirX;

이동한거리 : mapX - posX + (1 - stepX) / 2
광선의 방향 : rayDirX;

광선이 양쪽 사이드로 갈수록 ray dir이 커지는 것을 이용하여서 간단하게 보정하는 방법입니다.