cub3D(1) - 레이캐스팅(Ray Casting)

레이캐스팅(Ray Casting)이란?

레이캐스팅(Ray casting)은 컴퓨터 그래픽스와 계산기하학의 다양한 문제를 해결하기 위해 광선과 표면의 교차검사를 사용하는 기법을 말합니다.
이 용어는 1982년 스코트 로스의 구조적 입체 기하학 모델을 렌더링하기 위한 기법을 묘사하는 컴퓨터 그래픽스 논문에서 처음 사용되었습니다.
즉, 레이캐스팅은 2차원 맵에서 3차원의 원근감을 구현하기 위한 렌더링 기술

90년대 초에 큰 반향을 일으켰던 울펜슈타인 3D이 화면 렌더링 방식을 레이캐스팅으로 이용하는 가장 잘 알려진 게임입니다.

레이캐스팅과 레이트레이싱의 차이

레이트레이싱은 빛이 해당 물체의 표면에 닿은 후, 현실처럼 빛이 다시 재귀적으로 반사되어 결과물을 렌더링 하는 방식이지만,
레이캐스팅은 해당 물체에 닿으면 일회성으로 사용되고 더 이상 연산을 수행하지 않습니다.

Ray(빛) + Casting(쏘다)

레이캐스팅은 말 그대로 빛을 쏘아서 부딪힌 물체의 표면을 감지하는 기술이다. 빛에서부터 물체까지의 거리를 바탕으로 얼마나 가까이 렌더링해야하는지를 결정합니다.

화면의 X축으로 모든 픽셀마다 카메라가 바라보고 있는 방향으로 광선을 투사한 후 벽까지의 거리를 구하는데, 벽 까지의 거리가 멀면 가로 1픽셀 짜리 짧은 세로줄을 해당 X위치에 그리고 벽 까지의 거리가 가까우면 가로 1픽셀 짜리 긴 세로줄을 해당 X위치에 그리는 방식으로 3D같은 입체감을 줄 수 있습니다.

레이캐스팅이 게임에 처음 활용된 곳이 바로 FPS 게임입니다.
예전에는 컴퓨터 성능이 지금 만큼 좋지 않았기 때문에, 3D 게임은 상상조차 할 수 없는 시대였습니다. 그래서 수학적 계산의 부하를 줄이기 위해 게임 공간은 2D로 구성되었으며, 여기에 3D 같은 사실감을 주기 위해 레이캐스팅 기법을 사용해서 원근감을 더했습니다.

Ray(빛) + Tracing(추적하다)

레이트레이싱은 레이케스팅처럼 빛을 쏘되, 빛이 해당 물체의 표면에 닿은 후 현실처럼 빛이 다시 재귀적으로 반사되어 결과물을 렌더링 하는 방식입니다.

X축인 수평선으로만 쏘는 것이 아닌 화면의 모든 픽셀마다 빛을 쏘아서 충돌에 따라 해당 픽셀을 색칠하는 방식입니다. 화면의 모든 픽셀마다 빛을 쏜다고 하였지만 엄밀히 말하면 모눈종이처럼 되어 있는 캔버스에 빛을 쏘는 것인데, 캔버스의 각 픽셀이 모니터의 픽셀을 구성하게 됩니다.

레이캐스팅은 해당 물체에 닿으면 일회성으로 사용되고 더 이상 연산을 수행하지 않는 반면, 레이트레이싱은 계속해서 빛을 반사시켜서 어디에 부딪히는 지를 추적한다는 차이점이 있습니다.

레이캐스팅의 원리

레이캐스팅 의 기본개념은 다음과 같습니다.

2차원 정사각형 그리드로 된 맵 이 있습니다.

• 맵의 한 칸(square)은 0 또는 양수 값을 갖습니다.
• 0은 벽이 없음을 나타냅니다.
• 양수값은 벽이 있음을 나타내고, 특정 색상 또는 특정 질감을 나타냅니다.
• 화면의 모든 x값(수직선) 에 대해 플레이어 위치에서부터 시작하는 광선(Ray) 을 쏩니다.
• 이 때 광선의 방향은 플레이어 가 바라보는 방향, 그리고 화면의 x좌표에 의존합니다.
• 이 광선은 2D맵 위에서 벽에 부딪힐 때까지 직진하다가, 벽에 부딪히면 적중지점(hit point)으로부터 플레이어까지의 거리 를 잽니다.
• 이 거리에 따라 벽의 높이 가 화면에 얼마만큼으로 그려져야 하는지 결정됩니다. 벽의 높이는 플레이어와 벽 사이의 거리가 멀수록 화면에 더 낮게, - 가까울 수록 더 높게 표시됩니다.
• 이것들은 모두 2차원 계산으로 구할 수 있는 것들입니다.
• 상단의 이미지에서 위에서 내려다 본 2차원 평면도입니다.
• 광선(red line)이 플레이어(green spot)에서 시작해서 벽(blue square)에 도달하는 것을 보여줍니다.

광선이 처음으로 부딪히는 벽을 찾으려면, 광선을 플레이어의 위치에서부터 출발시켜 광선이 벽에 포함되는지 반복적으로 검사 해야합니다.

• 광선이 벽에 포함되는 것(hit)으로 확인되면, 벽에 포함되는지 확인하던 loop는 멈추게 되고, 거리를 측정해서 알맞은 높이로 벽을 표현해줍니다.
• 반대로 광선이 벽에 포함되지 않는 것으로 확인되면, 계속해서 추적합니다. 광선 방향에 맞는 새로운 위치에서 벽에 포함되는지 다시 검사합니다.
• 벽에 부딪힐 때까지 계속해서 반복합니다.

광선이 어디서 벽에 부딪히는지 한눈에 알 수 있는 사람과는 다르게, 컴퓨터는 광선의 경로 상에 있는 한정된 지점들만 검사할 수 있기 때문에 공식하나로 뚝딱 알아낼 수 없습니다.

레이캐스터 는 보통 광선의 위치에 일정한 값 을 더해주며 반복하는 방식으로 벽에 부딪혔는지 검사합니다.

• 이렇게하면 벽에 부딪혔는데도 이를 놓치고 벽에 부딪히지 않았다고 판단할 가능성도 있습니다!
• 예를 들어 상단 이미지의 광선(red line)에서, 일정한 간격으로 떨어져있는 적색 점들에서 검사한 경우를 봅시다.
• 보시는 것처럼 광선은 파란색 벽을 통과하여 직진하지만 컴퓨터는 빨간색 점이있는 위치에서만 확인했기 때문에 이를 감지하지 못했습니다.
• 더 많은 위치를 확인하면 컴퓨터가 벽을 놓칠 가능성이 줄어들지만 더 많은 계산이 필요합니다.

이번에는 검사지점의 간격(step distance) 이 반으로 줄여서 광선이 벽을 통과했음을 확인할 수 있게됩니다. 그래도 위치가 정확하지 않다는 문제가 있습니다.

이 방법(광선의 위치에 일정한 값을 더해주며 반복하는 방법)을 사용하면서 무한한 정밀도(infinite precision)를 얻기 위해서는, 검사지점이 간격이 무한히 작아져야 하고 그렇게 되면 무한한 수의 계산이 필요하게 됩니다!

그것도 나쁘지않지만 계산을 거의 하지않고도 모든 벽을 감지할 수 있는 더 좋은 방법이 있습니다. 광선이 닿는 벽의 모든 면 을 검사하는 방법입니다.

• 정사각형 한 칸(square) 너비를 1이라 하면 지정하므로, 모든 벽면을 정수값으로 표현할 수 있습니다.
• 이제는 검사지점의 간격이 일정하지 않고 다음 측면까지의 거리에 따라 달라집니다.
• 상단 이미지에서 보시다시피 광선은 우리가 원하는 위치에 정확하게 부딪힙니다.

이 튜토리얼에서는 DDA(Digital Differential Analysis) 기반으로 하는 알고리즘이 사용됩니다.

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

일부 레이트레이서 는 유클리드 각도를 활용해서 플레이어의 방향과 광선을 나타내며 시야(Field Of View) 를 결정하지만 벡터와 카메라 로 작업하는 것이 훨씬 쉽습니다.

플레이어의 위치는 항상 벡터(x좌표, y 좌표)입니다.

이제는 방향도 벡터로 표현하겠습니다. 즉, 방향은 방향벡터 (direction vector) 의 x좌표, y좌표라는 두 값으로 결정됩니다. 방향벡터는 다음과 같습니다.

• 플레이어가 보는 방향으로 선을 그릴 경우, 그 선 위의 모든 점들은 '플레이어의 위치 + 방향벡터의 배수'의 합입니다 (아래서 설명)
• 방향벡터의 방향만 중요하고 길이는 크게 중요하지 않습니다. x랑 y에 같은 값을 곱하면 길이는 바뀌더라도 같은 방향을 나타냅니다.

이렇게 벡터를 이용하는 방법에는 방향벡터 외에 카메라평면 도 필요합니다.

• 상단의 이미지에서 카메라평면(blue)은 컴퓨터 화면의 표면을 나타내고 방향벡터(black)는 화면 내부 쪽을 가리킵니다.
• 카메라평면은 항상 방향벡터에서 수직 입니다.
• 점으로 표현되는 플레이어의 위치 는 카메라 평면보다 앞에 있습니다.
• 화면에서 특정 x 좌표의 특정 광선은 이 플레이어 위치에서 시작하여 화면의 해당 위치 또는 카메라 평면을 통과하는 광선입니다.
• 진짜 3D 엔진은 3차원을 다루므로 벡터 2개가 필요하지만. 2차원 맵을 다루는 레이캐스팅 은 카메라평면이 진짜 평면이 아니고 선이므로 벡터 1개로 표시합니다.

벡터의 덧셈을 이용해서 다음과 같이 필요한 벡터를 표현 해보겠습니다.

• pos 벡터 : 플레이어의 위치(green spot)
• dir 벡터 : 방향벡터(black line)
• plane 벡터 : 전체 카메라평면(blue line) 중 방향벡터의 끝점(black spot)부터 오른쪽 카메라평면의 끝점(blue spot)까지
• 방향벡터 끝점(black spot) : pos + dir
• 오른쪽 카메라평면의 끝점(right blue spot) : (pos + dir) + plane
• 왼쪽 카메라평면의 끝점(left blue spot) : (pos + dir) - plane

이제 광선의 방향 은 카메라평면으로부터 쉽게 구할 수 있습니다.

• 계산방법은 ( 방향벡터 ) + ( 카메라평면 x 배수 ) 입니다.
• 예를 들어 이미지에서 적색 선은 광선(Ray)를 나타내는데, 카메라평면의 오른쪽에서 길이의 약 1/3 지점을 통과하는 세 번째 광선을 보겠습니다.
• 광선의 방향 : dir + plane * 1/3
• 이 광선의 방향은 rayDir 벡터 라고 하고, 벡터의 X, Y값은 DDA 알고리즘에 사용됩니다.

바깥쪽 선 두개는 스크린의 왼쪽/오른쪽 경계이고, 두 선 사이의 각도를 FOV (Field of View) 라고 합니다.

• FOV는 " 방향벡터 길이 : 평면 길이 " 의 비율로 결정됩니다.
• 다른 FOV 의 몇 가지 예는 다음과 같습니다.
• 1] 방향 벡터와 카메라 평면 벡터의 길이가 같은 경우, FOV는 90 °입니다. (좌측 이미지)
  - 방향벡터 길이 : 평면 길이 = 1 : 1
• 2] 방향 벡터가 카메라 평면보다 훨씬 길면 FOV가 90 °보다 훨씬 작아집니다. (중앙 이미지)
  - 시야가 좁아져서 더 자세한 내용을 볼 수 있고 깊이가 줄어들므로 확대와 동일합니다.
  - 방향벡터 길이 : 평면 길이 = LONG : 1
• 3] 방향 벡터가 카메라 평면보다 짧으면 FOV가 90 °보다 커집니다.(우측 이미지)
  - 방향 벡터가 0에 가까울 경우 180 °가 최대입니다.
  - 축소와 같이 훨씬 넓은 시야를 갖게됩니다.
  - 방향벡터 길이 : 평면 길이 = 1 : LONG

플레이어가 방향을 돌리면 시야가 따라서 회전해야 하므로 방향벡터와 카메라평면벡터가 모두 회전해야합니다.

• 그러면 모든 광선도 따라서 회전시킬 수 있습니다
• 벡터를 회전 시키려면 회전행렬과 곱해주세요
  - [cos (a) -sin (a)]
  - [sin (a) cos (a)]

회전행렬에 대한 수식은 위 이미지를 참고하면 이해가 수월합니다.