본 포스팅은 Lode's Computer Graphics Tutorial: Raycasting(이하 레퍼런스)을 보고 정리한 글입니다.
또한, 창을 띄우고 그래픽을 랜더링하는 부분은 본 포스팅에서 다루지 않습니다.
개념
카메라에서 각 픽셀을 통과하는 가상의 광선을 쏘아 무엇이 보이는지 결정하는 기법이다.
이를 통해 2차원 맵에서 원근감을 포현한 3D 랜더링을 할 수 있다.
레이캐스팅 기술을 사용한 게임은 Wolfenstein 3D, Doom 등이 있다.
알고리즘
2차원 맵이 존재하고, 플레이어(카메라)의 위치에서 플레이어가 바라보는 방향으로 모든 x축 픽셀을 대상으로 가상의 광선을 쏜다.
광선이 벽과 충돌하면 수직의 벽을 그리는데, 플레이어와의 거리에 따라서 벽의 높이를 정한다.
벽의 높이를 구하면 모니터의 중앙을 기준으로 위, 아래를 똑같은 높이의 직선을 그려준다.
x축의 모든 픽셀을 대상으로 하면 그렸던 직선은 면이 되며, 거리에 따라 높이가 달라지므로 원근감이 표현된다.
시야각 (Field Of View)
플레이어가 보는 방향이 정해지면 플레이어의 시야가 얼마나 넓을지를 정해야 한다.
시야각이 넓으면 넓을 수록 더 많은 사물을 보게 된다.
레퍼런스에서는 카메라 평면(camera plane)과 벡터로 이를 구한다.
카메라 평면은 간단히 말하면 모니터 화면이다.
플레이어의 방향 벡터와 수직인 평면이지만, 레이캐스팅은 2차원에서 다루므로 직선으로 표시한다.
따라서 위의 그림에서 빨간색 중앙 선이라고 생각하면 된다.
방향 벡터는 단위 벡터로 길이가 동일하고, 카메라 평면에만 배수를 주어 시야각을 조절한다.
방향 벡터와 카메라 평면이 같은 길이라면, FOV는 90도가 될 것이다.
이 때, 광선의 방향 벡터는 파란색 실선에 충돌하는 벡터이며, 방향 벡터 + 카메라 평면 길이 * 배수 이다.
광선 (Ray)
광선이라고 표현해서 대단해 보일 수도 있지만, 사실은 2차원 평면에서 직선을 그리는 것이다.
직선을 그릴 때는 직선 알고리즘을 사용하면 되는데, 알고리즘을 채택할 때 주의할 점이 있다.
좌측의 그림처럼 직선에서 일정한 간격을 더하며 벽과의 충돌을 감지할 경우, 벽을 정확히 감지할 수 없다.
간격을 줄이면 줄일수록 정확도가 올라가긴 하지만,
더 좋은 방법은 우측 그림처럼 광선이 그리드의 경계선에 정확히 충돌했을 때만 감지한다면 더 효율적으로 벽을 정확히 감지할 수 있다.
직선 그리기 (DDA 알고리즘)
레퍼런스에서는 위의 문제를 해결하기 위해 DDA(Digital Differential Analysis) 알고리즘을 사용한다.
DDA 알고리즘을 사용하기 위해선 우선 다음의 개념이 필요하다.
플레이어 위치에서 한 방향으로 광선을 쏘았을 때,
광선이 제일 처음 만나는 정수인 x 까지의 길이가 sideDistX,
제일 처음 만나는 정수인 y 까지의 길이가 sideDistY 라고 칭하고
이후 계속 반복되는 이전 정수인 x부터 다음 정수인 x+1 까지의 길이를 deltaDistX,
이전 정수인 y부터 다음 정수인 y+1 까지의 길이를 deltaDistY 라고 칭한다.
sideDist를 구하기 위해서는 먼저 deltaDist를 구해야 한다.
deltaDist를 구하기 위한 방법은 아래와 같다.
deltaDistY를 예로 들자면,
deltaDistY의 시작점에서 y축에 수직인 직선과, 끝점에서 x축에 수직인 직선을 그어 교차점을 찍으면 삼각형이 만들어진다.
deltaDistY의 시작점에서 교차점까지의 길이는 아직 알 수 없어 알파(α)로 두고,
deltaDistY의 끝점에서 교차점까지의 길이는 무조건 1이다.
알파(α)를 구하기 위해서는 우리가 이미 알고있는 직선의 방향 벡터(이하 rayDir)를 사용한다.
rayDir을 위 그림처럼 임의로 찍고 deltaDistY처럼 각 축의 수직인 직선들을 그으면 똑같이 삼각형이 만들어진다.
두 삼각형은 모든 각이 같으므로 닮음 조건에 충족하여 비례식이 세워질 수 있다.
알파(α)를 구했으니 피타고라스 정리를 적용해 deltaDistY를 구할 수 있다.
deltaDist를 구했으니 sideDist도 구할 수 있다.
빨간색 식은 rayDirY가 음수냐 양수냐에 따라 달라진다.
양수의 경우 그림과 같이 mapPosY + 1 - playerPosY고,
음수의 경우 playerPosY - mapPosY로 계산한다.
이렇게 나뉘는 이유는 정수인 mapPos를 지나친 player의 경우 해당 좌표에 벽이 있으면 플레이어가 벽 안에 있다고 보기 때문인데,
따라서 벽 안에서는 광선을 해당 벽에 충돌시키지 않게 하기 위함이다.
무튼 위의 그림으로 보면 이 역시 삼각형의 닮음이라 비례식이 세워지며, sideDistY도 구할 수 있다.
마찬가지로 deltaDistX와 sideDistX도 구해줄 수 있고,
sideDist에 deltaDist를 더해가며 배열의 경계에 마주칠 때마다 직선이 벽에 충돌했는지 감지할 수 있다.
그리고 더해진 sideDist는 플레이어와 벽의 거리를 나타내기도 한다.
어안렌즈 효과 보정
지금까지 구했던 플레이어와 벽의 거리로 좌측 그림의 상황이라면, 우측의 그림처럼 랜더링 된다.
실제론 하나의 벽일지라도 모든 직선의 길이가 다르기 때문에 길이에 따라 벽의 높이가 다르게 나타나기 때문이다.
이를 어안렌즈 효과라고 칭하며, 이를 보정해줘야 사람의 시야처럼 랜더링할 수 있다.
이를 보정하기 위해서 레퍼런스에서는 광선이 충돌한 지점에서 카메라 평면까지의 수직선을 긋고
그 수직선의 길이(이하 perpWallDist)를 구해 벽의 높이를 구하는 방법이다.
더 쉬운 설명을 위해 위와 같이 플레이어가 회전한 상태의 상황이라고 예를 들어보자.
먼저 좌측 그림을 보면 x축과 수평인 선(이하 검은색 실선)을 그어 충돌지점과 수직인 가상의 선을 이으면 베타(β)를 가정할 수 있다.
그리고 playerDir 끝점에서 이와 수직인 가상의 선(이하 파란색 실선)을 그으면 sideDist와의 교점을 구할 수 있다.
이는 먼저 구했던 rayDir임을 알 수 있고, 이 rayDir에서 검은색 실선과 수직인 선을 내리면 rayDirY를 구할 수 있고,
이렇게 만들어진 두 개의 삼각형은 닮음이기에 비례식을 세울 수 있다.
그리고 우측 그림을 보면 카메라 평면과 perpWallDist으로 만들어진 삼각형과,
카메라 평면에서 rayDir까지 이은 점 (playerDir)으로 만들어진 삼각형이 닮음을 이루어 다음의 비례식을 만들 수 있다.
이렇게 만들어진 두 개의 비례식은 좌변이 같기 때문에 우변끼리 이어 다음의 식을 성립한다.
이를 풀어보면 다음과 같다.
우리는 베타(β)를 알고 있다. 광선이 충돌한 지점과 플레이어의 위치를 알기 때문이다.
따라서 다음의 식이 완성된다.
아까 전 위에서 sideDist를 구할 때, rayDirY가 양수인 경우 playerPosY에 1을 더해줬었는데,
이와 동일한 이유로 rayDirY가 음수일 때 playerPosY에 1을 더해주어야 한다.
벽 그리기
이렇게 perpWallDist를 구했으면 이제 벽을 그릴 수 있게 된다.
간단하게는 화면 크기의 높이를 perpWallDist로 나누어서 구할 수 있다.
이렇게 구한 벽의 높이를 화면의 중앙선을 기준으로 위, 아래로 반복하여 픽셀을 찍어주면 완성이다.
sideDist를 더해줄 때, x를 더했는지 y를 더했는지와 rayDir이 음수였는지 양수였는지에 따라서
벽의 어느 측면에 광선이 충돌했는지를 알 수 있고, 이를 이용해 벽마다 다른 색깔의 픽셀을 찍을 수도 있다.
텍스쳐
벽의 어느 부분에 광선이 충돌했는지도 알 수 있기 때문에 벽에 텍스쳐를 입힐 수 있다.
우리는 x축으로만 광선을 쏘기 때문에 벽의 충돌 지점의 x 좌표만 안다면, y축은 벽의 높이에 따라서만 잘 그려주면 된다.
아래는 벽의 충돌 지점 x 좌표를 구하는 방법이다.
perpWallDist를 구할 때 사용했던 비례식 하나를 재활용하고,
검은색 실선에서 플레이어 위치와 perpWallDist의 교점까지의 거리를 t라고 했을 때 다음과 같은 비례식이 만들어진다.
이 두 비례식 역시 좌변이 같기에 아래와 같은 비례식이 성사되고, 이를 풀면 t를 구할 수 있다.
t와 playerPosY를 더하면 맵의 첫 부분부터의 거리가 나오고,
이 거리에서 정수 부분을 빼준다면 텍스쳐의 x 좌표를 구할 수 있다.
이 때, 벽의 어느 방면에 충돌했는지에 따라 텍스쳐의 x좌표가 왼쪽부터 시작인지, 오른쪽부터 시작인지를 구별해야한다.
반대 방향일 경우 1에서 텍스쳐의 x 좌표를 빼줘야 한다.
이후 1픽셀마다 텍스쳐의 세로 길이를 벽의 높이로 나눈 만큼을 증가시키며 텍스쳐의 해당 x,y 좌표에 접근해 픽셀을 가져와 찍으면 된다.
이동 및 회전
이동은 playerPos를 변경해주며 다시 위의 과정을 재랜더링하면 되고
회전은 playerDir과 cameraPlane을 회전하여 위의 과정을 재랜더링하면 된다. 회전 행렬 참고.
마치며
본 포스팅에서는 따로 코드 구현을 진행하지 않는다.
코드가 궁금하다면 레퍼런스에 잘 소개되어 있으니 참고 바란다.
참고 자료
https://lodev.org/cgtutor/raycasting.html#Introduction
(번역) https://github.com/365kim/raycasting_tutorial/blob/master/4_textured_raycaster.md
개인 공부용 포스팅인 점을 참고하시고, 잘못된 부분이 있다면 댓글로 남겨주시면 감사드리겠습니다.