[📜일지] 아재들의 첫 FPS, 울펜슈타인3D을 구현해보자.

[닥터휴버트(drhubert)]

이번에 소개할 내용은 Raycast라는 역시 아주 오래된 테크닉이야.

이 기법을 사용한 가장 유명한 게임으로는 역시 id 소프트의 울펜슈타인3D가 아닐까

https://youtu.be/7P_dic-pSKo

이건 직접 구현한 화면. 용량을 줄이려고 FPS를 10fps로 맞추니 끊겨 보이네 ㅎ

폴리곤도 아닌데 이런 3D 효과를 어떻게 구현했는지 핵심 알고리즘 위주로 소개해볼께.

1. 관찰자로부터 2차원 TopView에서 Ray를 쏘아 벽(검게 칠해진 부분)과 교차점을 구한다.

2. 교차점과 관찰자의 거리를 기반으로 벽의 수직선을 화면에 투영.

대충 의사코드도 적어봤어.

이제 좀 더 자세히 하나씩 살펴보자.

먼저 교차점 구하기부터.

우리는 몇가지 제한점을 가지고 있는데,

1. 벽과 빈공간만 있는 사실상 2D월드

2. 벽은 Grid로 일정한 간격과 일정한 크기로 존재한다.

3. 카메라의 좌우회전만(yaw) 허용한다.(pitch, roll 안됨)

위 제한을 바탕으로 Ray와 벽의 교차는 2D에서 격자단위로 처리하면 된다는 것을 알 수 있어.

즉, 교차점은 항상 일정한 간격으로 있는 Grid 선 위에'만' 존재함.

이런 상황에서 빠르게 교차점을 구할 수 있는 알고리즘이 있는데 그것을 DDA(Digital differential analyzer) 알고리즘이라고 불러.

교차점 A~F 모두 간격이 1인 Grid 선분 위에 있음.

교차는 A->B->C->D->E->F 와 같은 순서로 교차되는데, 이것을 어떻게 빠르게 구할 수 있을까?

먼저 Grid의 선분을 수직선과 수평선으로 나누어서 생각해보자.

수직선의 경우,

수직선의 경우 위와같이 ray의 xdelta 길이마다 한 점씩 교차하는 것을 알 수 있음 (Grid 간격은 1.0)

ray의 원래 길이가 1(ray.dir은 단위벡터)이라면 삼각형비로 쉽게 xdelta를 구할 수 있다.

수평선도 마찬가지 방법으로 구할 수 있음.

xdelta와 ydelta를 알면 다음 x교차점과 다음 y교차점을 쉽게 찾을 수 있음.

다음 x교차점 = 현재x교차점 거리(xdist) + xdelta

다음 y교차점 = 현재y교차점 거리(ydist) + ydelta

그럼 최초의 x교차점과 y교차점은 어떻게 구하면 될까?

xdelta와 ydetal의 의미는 각각 1만큼 이동했을 때 ray의 거리.

따라서 온전히 1이 아니라 처음 그리드 간격에(xoffset, yoffset)에 xdelta와 ydelta를 곱하면 최초의 x교차점 거리와 y교차점 거리를 구할 수 있어.

이제 필요한 정보는 다 알았으니 순서를 따져가며 살펴보자.

1. xdelta, ydelta, xdist, ydist를 구한다.

2. ydist < xdist이다. A가 교차점이 된다. 여기서 ydist = ydist + ydelta로 갱신한다.

3. ydist < xdist이다. B가 교차점이 된다. 다시 ydist= ydist + ydelta로 갱신

4. xdist < ydist, 이제 xdist가 더 짧다. 따라서 C가 교차점이된다. 다음 수직선과의 교차점과의 거리로 갱신한다. xdist = xdist + xdelta

5. ydisy < xdist, D가 교차점이 된다. 다음 수평선과의 교차거리는 ydist = ydist + ydelta이다.

6. 여전히 ydist와 교차하는 수평선 위 교점과의 거리가 xdist로 교차하는 수직선 위 교점과의 거리보다 짧다. 따라서 E가 교차점이 된다.
ydist = ydist + ydelta

7. xdist < ydist, F가 교차점이 된다. 그런데 현재 교차점이 있는 곳의 위치는 (2,1)이고 이곳은 벽이다. 여기서 raycast를 마친다.

이걸로 ray와 벽의 거리를 구하는 것까지 살펴보았는데, 이제 남은 것은 이 거리를 기반으로 벽의 수직선을 그려주면 됨.

그런데, 여기서 한가지 주의할 점은 교차점과 카메라의 거리를 그대로 써버리면 어안렌즈와 같이 되어버려.

벽을 바로 정면에서 바라보았을 때 C,D,E가 화면상 평평하게 보이기를 기대하지만 ray의 거리가 C와 E가 D에 비해서 더 길기 때문에

위와 같이 왜곡되어 보여짐.

이것을 피하기 위해 파란선과 같이 카메라 정중앙의 방향에 따른 ray의 길이(내적으로 간단히 계산 가능)를 계산하면

어안렌즈 현상을 피할 수 있음.

이걸로 벽그리기 까지 끝.

지금까지 맵을 그렸다면 남은 것은 물체에 해당하는 스프라이트 그리기.

스프라이트는 벽을 다 그린 후 그리게 되는데 문제는 벽에 가려진 경우는 어떻게 하면 될까?

스프라이트가 벽 뒤에 있고 관찰자에게는 일부만 보임.

이와 같이 벽에 가려진 부분은 그려지지 않게 하기 위해서 현대의 깊이버퍼와 같은 것을 1차원으로 만들어서 처리함.

스프라이트도 벽과 마찬가지로 수직선 방향으로 쪼개서 하나씩 그리게 되는데,

우리가 앞서 계산한 CamFwd 기준 거리를 1차원 깊이 버퍼에 저장하고 스프라이트의 거리가 그 깊이버퍼보다 작을 때만 그리게 하면 끝.

여기까지 raycast의 핵심적인 알고리즘을 소개해보았음..

디테일한 내용과 코드가 궁금하다면 아래 참고 사이트를 참고하시길 바람.

깃허브도 뒤져보시면 울펜슈타인3D 소스 코드를 쉽게 찾을 수 있으니 그것도 한번 참고하시면 좋을 것 같아.

다음에 기회가 되면 문 그리기, 숨겨진 벽그리기 등에 대해서도 정리해볼께.

내용들이 점점 복잡해지니 쓰는 것도 일이구만. 되도록 한번에 끝내고 싶은데 다음에는 쪼개서 써야하나 고민중.

참고 사이트 :

https://lodev.org/cgtutor/raycasting.html

[루돌프돌프건도르건돌(penguinnom)]

오오 ㄷ ㄷ ㄷ ㄷ 장난아니네요

[익명(118.32)]

개추

[익명(usnned)]

굳

[뒤뚱(175.112)]

씹굳

[익명(59.5)]

렌더링 하는 놈들은 진짜 공부 열심히 했구나... 미쳤다 진짜

[익명(124.57)]

십고수

[GMP(growy920)]

이정도면 마인크래프트도 만들 수 있는 수준 아니노

[익명(112.156)]

마인크는 고인물들 하루면 만들고 그러더라 ㅋㅋ

[익명(59.18)]

명암 표현하는게 개어렵겠네