[cub3d] ray cast란?

J_JEON·2023년 2월 2일

cub3d

목록 보기

2/2

ray cast

광선을 직선으로 투사해 가장 먼저 닿은 물체와의 거리를 파악하는 기법

cub3d에서는 플레이어의 시야에 보이는 벽과의 거리를 파악하여 화면 높이와 벽의 높이를 거리에 따른 비율로 계산해 2D맵을 3D원근법으로 렌더링하기위해 사용

특징

그림자, 빛의 반사 등등을 모두 계산하는 ray tracing보다는 재현율이 떨어지지만 연산횟수는 크게 차이남

1000 * 1000크기의 화면이라면 x축 크기인 1000번의 연산만 하면 모든 벽과의 거리를 파악할 수 있음 (단 모든 벽은 수직, 바닥은 평평해야하고 벽은 모두 동일한 크기의 큐브형태여야 함)

기본 원리

플레이어 위치로부터 시야각 내에 포함되어있는 모든 x좌표로 ray를 발사함

ray는 좌표상 x 또는 y선분 위를 지날때마다 (DDA 알고리즘) 벽이 있는지 없는지를 검사하기 위해 매 반복시마다 일정 크기만큼 전진함

벽을 만났다면 해당 벽을 만날때 ray가 위치한 x, y좌표 와 플레이어의 위치를 사용해 ray가 x, y 방향으로 얼마나 전진했는지를 계산함, 또한 어안렌즈 효과를 방지하기위해 플레이어의 위치부터가 아닌 카메라 평면으로부터 거리를 계산해야하므로 달라지는 길이를 보정해줌

계산한 거리와 화면의 높이를 계산해 거리가 멀수록 가로 1픽셀의 짧은 세로선, 거리가 가까울 수록 가로 1픽셀의 긴 세로선을 그려줌

모든 x좌표를 검사하고 세로선을 그렸다면 이미지가 완성됨

구현

 for(int x = 0; x < w; x++)
    {
      double cameraX = 2 * x / double(w) - 1; //카메라 평면상의 x
      double rayDirX = dirX + planeX * cameraX;
      double rayDirY = dirY + planeY * cameraX;
광선의 시작점은 플레이어 위치(posX, posY)로 합니다. 레이캐스팅 반복문에 필요한 변수를 선언하고 값을 계산합니다.

cameraX 는 for문의 x값(화면의 수직선)이 위치가 카메라평면에서 차지하는 x좌표 입니다. 이를 활용해서 광선의 방향을 계산할 것입니다.

for문의 x값이 0이면 (스크린의 왼쪽 끝이면) cameraX = -1
for문의 x값이 w/2이면 (스크린의 중앙이면) cameraX = 0
for문의 x값이 w이면 (스크린의 오른쪽 끝이면) cameraX = 1
2 * x를 해주는 이유는 -1 ~ 1 범위로 만들어주기 위함임

rayDirX, rayDirY 는 광선의 방향벡터 입니다. 앞서 설명한 것과 같이 광선의 방향은 ( 방향벡터 ) + ( 카메라평면 x 배수 ) 로 구할 수 있습니다. 벡터 x, y에 대해 각각 이 계산을 해줍니다.
cameraX는 plane의 길이가 1이라 가정시 분수로 표현되므로 가중치로 사용가능

이 반복문은 스크린의 모든 x값(수직선)에 대해서 계산할 뿐, 모든 픽셀에 대해서 계산하는 게 아니라 계산량이 얼마 안 됩니다!
int mapX = int(posX);
int mapY = int(posY);

//length of ray from current position to next x or y-side
double sideDistX;
double sideDistY;

//length of ray from one x or y-side to next x or y-side
double deltaDistX = std::abs(1 / rayDirX);
double deltaDistY = std::abs(1 / rayDirY);
double perpWallDist;
//what direction to step in x or y-direction (either +1 or -1)
int stepX;
int stepY;

int hit = 0; //was there a wall hit?
int side; //was a NS or a EW wall hit?
이제 DDA 알고리즘 과 관련된 변수를 선언하고 계산할 것입니다.

mapX, mapY 는 현재 광선이 충돌을 확인하고있는 한 칸(x,y) 입니다. 광선의 위치 자체는 부동소수점수로 표현돼서 광선이 맵상 어느 칸(square)에 있는지 그리고 그 한 칸 안에서 어디쯤 있는지까지 알 수 있지만, mapX, mapY 는 간단히 그 한 칸(square)의 좌표(정수)만 나타냅니다.

위의 이미지는 초기 sideDistX, sideDistY 및 deltaDistX, deltaDistY 를 보여줍니다.

sideDistX, Y 는 '시작점 ~ 첫번째 x, y면을 만나는 점'까지의 광선의 이동거리 입니다.
sideDistX, sideDistY 의미는 나중에 지금과 다른 의미로 약간 변경될 예정입니다.

deltaDistX, Y 는 '첫번째 x, y면 ~ 바로 다음 x, y면'까지의 광선의 이동거리 입니다. (이때 x, y는 각각 1만큼 이동)
deltaDist 공식 유도 (rayDirX가 1일때)

광선이 dist만큼 이동할 때
dist = √(rayDirX^2 + rayDirY^2)
dist^2 = rayDirX^2 + rayDirY^2

양 변을 rayDirX^2 로 나누어줌
-> dist^2 / rayDirX^2 = rayDirX^2 / rayDirX^2 + rayDirY^2 / rayDirX^2

(dist^2 / rayDirX^2) 은 deltaDistX^2
-> deltaDistX^2 = rayDirX^2 / rayDirX^2 + rayDirY^2 / rayDirX^2
-> deltaDistX = √(rayDirX^2 / rayDirX^2 + rayDirY^2 / rayDirX^2)
-> deltaDistX = √((rayDirX^2 + rayDirY^2) / rayDirX^2)

(rayDirX + rayDirY) 는 rayDir
-> deltaDistX = √(rayDir^2 / rayDirX^2)

rayDir은 단위벡터로 크기가 1
-> deltaDistX = √(1 / rayDirX^2)
-> deltaDistX = 1 / rayDirX
perpWallDist 는 나중에 광선의 이동거리를 계산하는 데 사용할 것입니다.

DDA 알고리즘은 반복문을 실행할 때마다 x방향 또는 y방향으로 딱 한 칸(square)씩 점프합니다. 광선의 방향에 따라 어느 방향으로 건너뛰는지 달라지는데 그 정보는 stepX, stepY 에 +1 또는 -1 로 저장됩니다. (주. stepX 또는 stepY 중 하나만 선택적으로 적용되는데 아래서 다시 설명 나와요)

마지막으로 벽의 x면 또는 y면과 부딪쳤는지 여부에 따라 루프를 종료할지 결정합니다. hit 은 벽과 부딪쳤는지 여부 (루프 종료조건) 입니다. 만약에 벽과 부딪혔고 그게 x면에 부딪힌 거라면 side 의 값은 0으로, y면에 부딪히면 1이 됩니다. x면, y면 은 두개의 칸(square)의 경계가 되는 부분의 선을 의미합니다.
 //calculate step and initial sideDist
if (rayDirX < 0)
{
  stepX = -1;
  sideDistX = (posX - mapX) * deltaDistX;
}
else
{
  stepX = 1;
  sideDistX = (mapX + 1.0 - posX) * deltaDistX;
}
if (rayDirY < 0)
{
  stepY = -1;
  sideDistY = (posY - mapY) * deltaDistY;
}
else
{
  stepY = 1;
  sideDistY = (mapY + 1.0 - posY) * deltaDistY;
}
DDA 알고리즘을 시작하기 전 stepX, stepY 의 초기값 을 구해줍니다.

만약 광선의 x방향 rayDirX 의 값이 양수라면 stepX 의 값은 +1 (좌표평면상 오른쪽) 로, 음수라면 -1 로 설정합니다. 만약 rayDirX 의 값이 0 라면, stepX 는 사용되지 않으므로 어떤 값을 갖든 상관없습니다. stepY 의 값도 똑같이 구해줍니다.

그리고 sideDistX, sideDistY 의 초기값 을 구해줍니다.

sideDistX 의 값은, rayDirX 의 값이 양수 일 경우, '광선의 시작점부터 오른쪽 으로 이동하다 처음 만나는 x면까지의 거리'입니다. 반대로 rayDirX 의 값이 음수 일 경우, '광선의 시작점부터 왼쪽 으로 이동하다 처음 만나는 x면까지의 거리'입니다. sideDistY 의 값도 마찬가지입니다. (시작점 기준 위쪽 또는 아래쪽 )

sideDistX, sideDistY 를 산출하기 위해 정수값인 mapX 와 실제 위치인 posX 가 사용하고, 광선의 방향에 따라 산출식을 알맞게 설정합니다. rayDirX 의 경우 양수 일 경우, sideDistX 는 mapX + 1 에서 실제위치 posX 를 빼주고 deltaDistX 값을 곱해서 구할 수 있습니다. rayDirX 가 음수 일 경우, sideDistX 는 posX 에서 mapX 를 빼주고 deltaDistX 값을 곱해서 구할 수 있습니다.
//perform DDA
while (hit == 0)
{
  if (sideDistX < sideDistY)
  {
      sideDistX += deltaDistX;
      mapX += stepX;
      side = 0;
  }
  else
  {
      sideDistY += deltaDistY;
      mapY += stepY;
      side = 1;
  }
//Check if ray has hit a wall
  if (worldMap[mapX][mapY] > 0) 
      hit = 1;
} 
이제 DDA 알고리즘을 시작 합니다.

이 while 반복문은 벽에 부딪힐 때까지 매번 x 또는 y방향으로 한 칸(square)씩 광선을 이동시키는 루프입니다.
반복할 때마다 stepX 를 사용하면 x방향으로 한 칸 또는 stepY 를 사용하면 y방향으로 한 칸 점프합니다. 항상 딱 한 칸씩만 점프합니다.
만약 광선의 방향이 x축 방향과 완전히 일치한다면, (y방향이 바뀌지는 않을테니) 반복문을 돌 때 x방향으로만 한 칸씩 점프하면 됩니다.
만약 광선이 y축 방향으로 아주 조금 기울어져 있으면 x방향으로 엄청 많이 점프하고나서야 y방향으로 1칸 점프할 것입니다.
만약 광선의 방향이 y축 방향과 완전히 일치한다면, x방향으는 점프할 필요가 없는 식으로 반복문이 진행됩니다.
광선이 점프할 때마다 sideDistX, sideDistY 는 deltaDistX, deltaDistY 가 더해지면서 다음 x, y선분 까지의 거리로 값이 업데이트됩니다.
광선이 점프할 때마다 mapX, mapY 는 stepX, stepY 가 더해지면서 값이 업데이트됩니다.
광선이 벽에 부딪히면 루프가 종료됩니다.

이 때, 변수 side 의 값이 0이면 벽의 x면에, 1이면 벽의 y면에 부딪혔다는 것을 알 수 있고, 또 mapX, mapY 로 어떤 벽(x,y)이랑 부딪힌 건지도 알 수 있습니다.
우리는 그 벽에서 정확히 어느 지점에서 부딪힌 건지는 알 수 없는데, 지금은 텍스쳐 없이 색상만 표현하기 때문에 몰라도 괜찮습니다.

벽을 만나 DDA가 완료되었으니 이제 광선의 시작점에서 벽까지의 이동거리 를 계산하겠습니다.

이 거리는 나중에 벽을 얼마나 높게 그릴지 알아내는데 사용됩니다.
어안렌즈 효과 (fisheye effect) 는 실제 거리 값을 사용했을 때 모든 벽이 둥글게 보여서 회전할 때 울렁거릴 수도 있는 현상을 말합니다.
이러한 어안렌즈 효과 를 피하기 위해, 플레이어 위치부터 벽까지의 유클리드 거리 대신에, 카메라 평면에서부터 벽까지의 거리 (또는 카메라 쪽으로 플레이어에 투사된 지점의 거리)를 사용할 것입니다.

위의 이미지는 플레이어 대신 카메라 평면까지 거리를 사용하는 이유를 보여줍니다. P는 플레이어의 위치, 흑색 선은 카메라평면을 나타냅니다.
플레이어 기준 왼쪽에 있는 적색 선은, 벽의 적중지점(hit point)에서 플레이어까지 유클리드 거리를 나타내는 광선을 나타냅니다.
플레이어의 오른쪽의 녹색 선은, 벽의 적중지점(hit point)에서 플레이어가 아닌 카메라 평면으로 바로 이동하는 광선을 나타냅니다. 이 녹색선의 길이가 바로 우리가 유클리드 거리(실제 거리) 대신 사용할 수직거리입니다.
이미지를 보시면, 플레이어는 벽을 정면으로 바라보고 있어 이 경우 벽의 윗선과 아랫선이 화면에서 완전히 수평을 이뤄야 합니다.
이때 적색 선의 길이를 적용하면 적색 선의 길이가 다 다르기 때문에 벽의 높이가 일정하지 않게되고 결국 벽이 둥글게 보이는 게 되는 것입니다.
반면에 오른쪽의 녹색 선은 모두 길이가 같아서 녹색 선을 적용하면 올바른 결과를 얻을 수 있습니다.
플레이어가 회전할 때 (카메라평면이 수평이 아니게 되고 녹색 선의 길이도 서로 달라지지만 서로 일정한 차이를 유지하면서 달라짐)에도 동일하게 적용되어 벽은 화면에 대각선이긴 하지만 직선으로 보이게 됩니다.
이 설명은 완벽하진 않지만 어느 정도의 이해를 돕습니다.
if (side == 0) perpWallDist = (mapX - posX + (1 - stepX) / 2) / rayDirX;
else           perpWallDist = (mapY - posY + (1 - stepY) / 2) / rayDirY;
여기서 사용되는 레이캐스팅 방법 은 광선의 이동거리를 계산하면서, 어안렌즈 효과를 보정하는 코드를 따로 추가하지 않고도 간단히 방지할 수 있는 방법입니다.

이 수직거리를 구하는 방식은 실제 이동거리를 구하는 방식보다 훨씬 쉽고, 벽에 어느 위치에 정확히 부딪혔는지 몰라도 구할 수 있습니다.
위의 예제코드에서, (1 - stepX) / 2 는 stepX 가 -1 이면 1, stepX 가 1 이면 0 이 됩니다. 이는 rayDirX < 0 일 때 길이에 1을 더해주기 위한 코드입니다. 위에서 sideDistX 의 초기값을 설정할 때 rayDirX의 방향에 따라 1을 더해주거나 말거나 했던 것과 같은 이유입니다.
수직거리를 계산하는 방법 은 다음과 같습니다.

만약 광선이 처음으로 부딪힌 면이 x면이라면, mapX - posX + (1 - stepX) / 2) 는 광선이 x방향으로 몇 칸이나 지나갔는지를 나타내는 수입니다 (정수일 필요는 없음).
만약 광선의 방향이 x면에 수직이면 이미 정확한 수직거리의 값이지만 대부분의 경우 광선의 방향이 있고 이 때 구해진 값은 실제 수직거리보다 큰 값이므로 rayDirX 로 나누어줍니다.
y면에 부딪힌 경우에도 같은 방식으로 계산해줍니다.
mapX - posX 가 음수이더라도 역시 음수인 rayDirX 로 나누어 계산된 값은 항상 양수가 됩니다.

perpWallDist 은 벽의 적중지점(hit point)와 플레이어의 카메라평면을 사용해서, 점에서 선까지의 거리를 구하는 공식을 적용해서 계산할 수도 있습니다. 하지만 이 공식은 앞의 더 간단한 공식보다는 계산량이 많습니다. 위의 이미지는 더 간단한 공식이 어떻게 도출되는지 보여줍니다.
이 설명은 y면에 부딪힌 경우(side == 1) 를 보여줍니다. x면에 부딪힌 경우도 같은 원리로 설명할 수 있습니다.
perpWallDist 공식 유도

직각삼각형의 닮음으로 인해 삼각형 PBH와 PCD,  PAH와 PDE는 서로 닮음임 따라서 

PH : PD = HB : DC
-> Euclidean : raydir = yDist : raydirY
-> Euclidean * raydirY = raydir * yDist
-> Euclidean / raydir = yDist / raydirY

PH : PD = AH : DE 
-> Euclidean : raydir = PerpWallDist : dir
-> Euclidean * dir = raydir * PerpWallDist
-> Euclidean / raydir = PerpWallDist / dir

두 식을 합하게되면
-> yDist / raydirY = PerpWallDist / dir

이때 dir은 단위벡터로 크기가 1임
-> yDist / raydirY = PerpWallDist
-> (mapY - posY + (1 - stepY) / 2) / raydirY = PerpWallDist
//Calculate height of line to draw on screen
int lineHeight = (int)(SCREEN_HEIGHT / perpWallDist);

//calculate lowest and highest pixel to fill in current stripe
int drawStart = -lineHeight / 2 + SCREEN_HEIGHT / 2;
if(drawStart < 0)drawStart = 0;
int drawEnd = lineHeight / 2 + SCREEN_HEIGHT / 2;
if(drawEnd >= h)drawEnd = SCREEN_HEIGHT - 1;
이제 계산한 거리 (perpWallDist)로, 화면에 그려야하는 선의 높이 를 구할 수 있습니다.

perpWallDist 를 역수로 취하고, 픽셀단위로 맞춰주기 위해 픽셀 단위의 화면높이 SCREEN_HEIGHT 를 곱해서 비율(lineHeight)을 구할 수 있습니다.
벽을 더 높게 그리거나 낮게 그리거나 하고 싶으면 5 + SCREEN_HEIGHT와 같은 다른 값을 넣을 수도 있습니다.
SCREEN_HEIGHT값은 일정한 벽의 높이, 너비 및 깊이를 가진 박스처럼 보이게 해주고, 값이 클수록 높이가 높은 박스를 만들어줍니다.
이렇게 구한 lineHeight (화면에 그려야 할 수직선의 높이)에서, 실제로 선을 그릴 위치의 시작 및 끝 위치를 알 수 있습니다.
벽의 중심은 화면의 중심에 있어야 하고, 이 중심점이 화면 범위 아래에 놓여있다면 0 으로, 화면 범위 위에 놓여있다면 SCREEN_HEIGHT-1으로 덮어씌웁니다.

도움 받은곳과 출처

https://lodev.org/cgtutor/raycasting.html
https://365kim.tistory.com/44
https://chichoon.tistory.com/m/425

J_JEON

늅늅

이전 포스트

[cub3d] ray cast란?

cub3d

ray cast

특징

기본 원리

구현

도움 받은곳과 출처

[cub3d] cub3d

0개의 댓글