3) cub3D - Raycasting

sorikikikim·2021년 6월 6일

42Seoul RayCasting cub3d

cub3D

목록 보기

3/6

참고한 링크

365kim

Raycasting : 2차원 맵에서 3차원의 원근감을 만드는 렌더링 기술

레이캐스팅은 스크린의 모든 수직선에 대해 계산만 하면 돼서 속도가 빠르다.
컴퓨터가 지금보다 느려서 3D 엔진을 실시간으로 실행할 수 없던 과거에는 레이캐스팅이 최초의 해결책이었다.

Raycasting vs Raytracing

레이캐스팅(Raycasting)은 4MHz 그래픽 계산기에서도 실시간으로 작동하는 빠른 semi-3D 기술인 반면, 레이트레이싱 (RayTracing)은 실제 3D장면의 반사, 그림자를 지원해서 현실감있는 렌더링 기술이다.
나중에서야 컴퓨터가 빨라져서 꽤 높은 해상도와 복잡한 장면들을 실시간으로 처리할 수 있게되었다.

Raycasting 기본 개념

2차원 정사각형 그리드로 된 맵

맵
- 0은 벽이 없음을 나타낸다.
- 양수 값은 벽이 있으며, 특정 색상 또는 특정 질감을 나타낸다.
플레이어와 광선
- 화면의 모든 x값(수직선)에 대해 플레이어 위치에서부터 시작하는 광선(ray)을 쏜다.
- 광선은 2D맵 위에서 벽에 부딪힐 때까지 직진하다가, 벽에 부딪히면 적중 지점(hit point)으로부터 플레이어까지의 거리(perpendicular wall distance)를 계산한다.
- 이 거리에 따라 벽의 높이가 화면에 얼마만큼으로 그려져야 하는지 결정된다. 벽의 높이는 플레이어와 벽 사이의 거리가 멀수록 화면에 더 낮게, 가까울 수록 더 높게 표시된다.

이것들은 모두 2차원 계산으로 구할 수 있으며, 상단의 이미지는 위에서 내려다 본 2차원 평면도이다. 광선이 플레이어에서 시작해서 벽에 도달하는 것을 알 수 있다.

Raycasting 방법

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

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

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

광선의 위치에 일정한 값을 더해주며 반복하는 방식
레이캐스터는 보통 광선의 위치에 일정한 값을 더해주며 반복하는 방식으로 벽에 부딪혔는지 검사한다.
- 하지만 이 방법으로는 벽에 부딪혀도 이를 놓치고 벽에 부딪히지 않았다고 판단할 가능성도 있다.
- 예를 들어 상단 이미지의 광선에서 일정한 간격으로 떨어져있는 적색 점들에서 검사한 경우를 보면, 광선은 파란색 벽을 통과하여 직진하지만 컴퓨터는 빨간색 점이 있는 위치에서만 확인 했기 때문에 이를 감지하지 못했다.
- 더 많은 위치를 확인하면 컴퓨터가 벽을 놓칠 가능성은 줄어들지만 계산이 많아진다.
검사지점의 간격을 반으로 줄여서 검사하는 방식
검사지점의 간격(step distance)을 반으로 줄여서 광선이 벽에 통과했음을 확인할 수 있게 하지만 그래도 위치가 정확하지 않다는 문제가 있다.

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

DDA(Digital Differential Analysis) Algorithm

위의 방식으로 검사지점 간격을 무한히 줄이는 방법도 나쁘지 않지만 계산을 거의 하지 않고도 모든 벽을 감지할 수 있는 더 좋은 방법이 있다. 광선이 닿는 벽의 모든 면을 검사하는 방법이다.

이 방법으로는 정사각형 한 칸의 너비를 1로 지정하므로, 모든 벽면을 정수값으로 표현할 수 있다. 검사지점의 간격을 일정하게 하지 않고 다음 측면까지의 거리에 따라 검사지점의 간격을 다르게 한다. 이렇게 하면 광선은 우리가 원하는 위치에 정확하게 부딪힌다.

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

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

플레이어의 위치는 항상 벡터이다. 방향도 벡터로 표현하면 방향은 방향벡터의 x좌표, y좌표라는 두 값으로 결정된다.

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

- 카메라 평면

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

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

- 벡터 표현

벡터의 덧셈을 이용해서 다음과 같이 필요한 벡터를 표현할 수 있다.

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

- 광선의 방향

광선의 방향은 카메라 평면으로부터 구할 수 있다.

광선의 방향 : 방향벡터 + (카메라 평면 * 배수)
예를 들어 적색 선은 광선(ray)을 나타내는데, 카메라 평면의 오른쪽에서 길이의 약 1/3 지점을 통과하는 세번째 광선을 보면, 광선의 방향은 dir + plane * 1/3으로 구할 수 있다. 이 광선의 방향은 rayDir 벡터라고 하고, 벡터의 x, y값은 DDA 알고리즘에 사용된다.
바깥선 두개는 스크린의 왼쪽/오른쪽 경계이고, 두 선 사이의 각도를 FOV(Field of View)라고 한다.
- 1] 방향 벡터와 카메라 평면 벡터의 길이가 같은 경우, FOV는 90 °.
  방향벡터 길이 : 평면 길이 = 1 : 1
- 2] 방향 벡터가 카메라 평면보다 훨씬 길면 FOV가 90 °보다 훨씬 작다.
  시야가 좁아져서 더 자세한 내용을 볼 수 있고 깊이가 줄어들므로 확대와 동일하다.
  방향벡터 길이 : 평면 길이 = LONG : 1
- 3] 방향 벡터가 카메라 평면보다 짧으면 FOV가 90 °보다 커진다.
  시야가 좁아져서 더 자세한 내용을 볼 수 있고 깊이가 줄어들므로 확대와 동일하다.
  방향벡터 길이 : 평면 길이 = LONG : 1
예를 들어 적색 선은 광선(ray)을 나타내는데, 카메라 평면의 오른쪽에서 길이의 약 1/3 지점을 통과하는 세번째 광선을 보면,
광선의 방향 : dir + plane * 1/3
이 광선의 방향은 rayDir 벡터라고 하고, 벡터의 x, y값은 DDA 알고리즘에 사용된다.