42 Seoul

[cub3D] raycasting

jaewpark 2022. 7. 4. 20:55

레이캐스팅은 2차원 맵에서 3차원의 원근감을 만드는 렌더링 기술로 Wolfenstein 3D 와 같은 게임이 이것을 이용하여 3D처럼구현하였습니다. 3차원 환경이라고 이야기할 수 없는 이유는 Z축을 따라 회전할 수 없기 때문입니다.

레이캐스팅으로 이루어진 세계를 만들기 위해서 벽은 항상 바닥과 직각을 유지하고 벽은 정육면체로 만들어지며, 바닥은 항상 평평해야 한다는 조건으로 만들어 보겠습니다.

 

레이캐스팅 기본 개념

  • 한 칸에 0, 1로 맵이 있다는 가정하에 (0은 벽이 없고 1은 벽을 나타냅니다) 플레이어 는 해당 위치에서 광선 (Ray) 를 쏩니다.
  • 이 광선은 맵에 이루어진 벽이 부딪힐 때까지 직진하다가 적중 (hit) 되면 거리를 측정합니다.
  • 거리에 따라 벽의 높이를 결정합니다. (멀수록 벽이 더 낮게 표현)

 

이러한 광선은 플레이어가 이동/시점 변경이 있을 때마다 반복적으로 확인 해야 합니다.

광선이 벽에 닿았는 지 확인하는 방법으로는 일정 간격으로 벽을 통과했는지 확인을 할 수 있지만 정확하지 않기에 DDA(Digital Differential Analsis) 기반으로 하는 알고리즘으로 광선이 닿은 모든 벽을 검사하려 합니다.

 

플레이어 위치를 벡터(x좌표, y좌표)로 표현을하고 방향, 카메라평면 또한 벡터로 표현을 합니다.

그리고 플레이어가 시야가 회전 시, 방향벡터와 카메라 평면 벡터가 모두 회전해야 합니다.

Ray casting은 MiniRT에서 쓰이는 Ray tracing의 서브 클래스 입니다.

 레이 캐스팅이 레이 트레이싱보다 빠르기 때문에 이러한 구분이 이루어집니다. 이것은 레이 캐스팅이 렌더링 프로세스의 속도를 높이기 위해 일부 기하학적 제약 조건을 사용하기 때문에 가능합니다. 예를 들어: 벽은 항상 바닥과 수직입니다(Doom 또는 Wolfenstein 3D와 같은 게임에서 볼 수 있음). 그러한 제약이 없다면 레이캐스팅은 불가능할 것입니다. 예를 들어 임의의 스플라인을 레이캐스트하고 싶지는 않습니다. 이러한 모양에 대한 기하학적 제약을 찾기가 어렵기 때문입니다.

레이 캐스팅 게임에 거의 존재하는 한계는 Z축을 따라 시점을 회전할 수 없습니다.

위에서 언급된 것과 같이 기하학적인 제약 조건을 만들어 보겠습니다. 

  1. 벽은 64로 이루어진 정육면체
  2. 벽과 바닥은 직각을 유지
  3. 바닥은 항상 평평

 

그럼 여기서 조금 더 자세한 설명으로 들어가자면,

cub3D에서 사용되는 Ray casting으로만 설명을 하고자 합니다. 사용되는 것으로는

  • 플레이어의 초기 위치 벡터 posX, posY
  • 플레이어의 초기 방향 벡터 dirX, dirY
  • 플레이어의 카메라 평면 planeX, planeY
  • 카메라 평면 -1, 0, 1 으로 구분

 

더보기

deltaDistX 값을 할 때에는 피타고라스의 정리로 값을 구할 수 있습니다.

 

deltaDistX = sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX))
deltaDistY = sqrt(1 + (rayDirX * rayDirX) / (rayDirY * rayDirY))

이러한 식은 아래와 같이 단순화 시킬 수 있으며,

 

deltaDistX = abs(|rayDir| / rayDirX)
deltaDistY = abs(|rayDir| / rayDirY)

 

deltaDistX와 deltaDistY 사이의 *ratio*만이 아래에서 뒤따르는 DDA 코드에 중요하므로 다음을 얻습니다.

 

deltaDistX = abs(1 / rayDirX)
deltaDistY = abs(1 / rayDirY)

 

이로 인해 코드에 사용된 deltaDist 및 sideDist 값은 위 그림에 표시된 길이와 일치하지 않지만 상대적 크기는 모두 일치

sideDistX 및 sideDistY는 방향으로 이동할 때마다 deltaDistX로 증가하고 mapX 및 mapY는 각각 stepX 및 stepY로 증가

rayDir에 따른 sideDist의 값을 정하는 것은 중앙 기준으로 왼쪽과 오른 쪽이 다르기 때문인 거 같다.

사실 벽이라는 것은 (1,1) (0,0)과 같은 곳에 위치 했기 때문에, (1.47, 1)에 닿게 되었지만 정확히는 (1,1) 이라는 벽에 닿은 것이기에

 

sideDistX = (mapX + 1.0 - posX) * deltaDistX;

sideDistX = (posX - mapX) * deltaDistX;

 

 

(FOV는 2 * atan(0.66). /1.0)=66°, 1인칭 슈팅 게임에 적합

플레이어의 기준에서 광선을 쏜다고 하겠습니다. (광선 사용 횟수는 총 width 만큼)

이 광선을 벽에 부딪힐 때까지 진행됩니다. (cub3D에서 벽으로 둘러쌓여 있는 이유일 겁니다)

벽까지의 거리를 기록합니다. 

 

여기서 벽까지의 거리를 기록할 때, 부딪히는 것을 확인하려면 x축과 y축 닿는 점을 확인하여 더 가까운 거리를 선택하면 됩니다.

해당 거리를 측정할 때에는 x축이 닿는 곳은 PX, y축이 닿는 곳을 PY로 표현하겠습니다.

두 가지의 방법으로 구할 수 있게 됩니다.

이러한 방법을 통해서 거리를 측정해서 벽을 그리게 되면 어안렌즈와 같은 느낌으로 벽의 왜곡이 발생하게 됩니다.

극좌표와 데카르트 좌표를 혼합하여 사용하면서 발생되는 것으로 보정할 수 있는 공식을 추가로 넣고 벽을 그려야만 합니다.

여기서 보정을 할 때, 카메라 시점으로 -1 0 1 구분을 지어서  (0일때는 스크린의 중앙)

스크린 중앙이 아닌 경우 보정을 해주면 됩니다. 

현재 스트라이프를 채울 가장 낮은 픽셀과 가장 높은 픽셀을 표시

상수값으로 표기를 하지만, 정확히는 정수값을 나타내는 벽들이기에 보정을 해줘야 한다. 

//Calculate distance of perpendicular ray (Euclidean distance would give fisheye effect!)
if(side == 0) perpWallDist = (sideDistX - deltaDistX);
else          perpWallDist = (sideDistY - deltaDistY);

//Calculate height of line to draw on screen
int lineHeight = (int)(h / perpWallDist);

//calculate lowest and highest pixel to fill in current stripe
int drawStart = -lineHeight / 2 + h / 2;
if(drawStart < 0) drawStart = 0;
int drawEnd = lineHeight / 2 + h / 2;
if(drawEnd >= h) drawEnd = h - 1;

 

그리고 회전을 하게 되면, 카메라 평면과 캐릭터가 보는 시야각이 변경되는데, 특정 각도만큼 백터가 움직이게 되는데, 회전행렬을 통해서

공식을 그대로 쓰게 되면 특정 각도만큼의 좌표를 변경할 수 있게 됩니다. 

 

이렇게 보정이 끝났으면 타일에 맞게 배율을 맞춰서 그리면 됩니다.

감이 잘 안온다 싶으면 참고 사이트를 번갈아가면서 읽다보면 이런 의미라는 걸 깨닫게 되었고 마무리가 되어 갔습니다.

사실은 이미 만들어진 게임을 그대로 구현하기 때문에, 이해만 하게된다면 쉽게 따라하고 코드가 눈에 익혀지게 될 것입니다.

 

/*
** 필요 데이터
** player	: 1. position (X, Y) 2. direction (X, Y)
** camera	: cameraX, x-coordinate in camera space
** 		(left of screen = -1, center of screen = 0, right of screen = 1)
** plane	: the 2d raycaster version of camera plane (X, Y)
** 		(the player's camera plane)
** hit		: check if Rays collides with the wall
** step	: Depending on the direction of the Rays, the information is stored in stepX, stepY as +1 or -1
** sideDist	: The distance of the Rays from the starting point to the point where it meets the first x(y)-axis (X, Y)
** deltaDist	: This is the travel distance of the ray when it's increased by 1 on the first x(y)-axis. (X, Y)
** * perWallDist		:  Calculate distance projected on camera direction
** rayDirection	: X, Y (rayDirX(Y) = directionX(Y) + planeX(Y) * cameraX)
** DDA algorithm	: Depending on the direction of the Rays, the information is stored in stepX, stepY as +1 or -1
*/
/*
** 필요 지식
** wall_x		: Mark exactly where you hit the wall in double-type coordinates, not int-type coordinates.
** tex.x		: the x-coordinates of the texture
** tex.step	: Determine how much the coordinates of the texture should be increased to the coordinates on the vertical line
** tex.pos		: The area to draw in texture
*/

 

사실 과제를 통해서 수학 공식의 이해하면서 보기보다는 큰 구조를 보고 이게 왜 필요로 한건지 하나하나 어떻게 쓰이는 건지 이해를 하니 조금은 이해가 빨리 되었던 거 같습니다.

 

mlx 라이브러리를 사용하면서

mlx_get_data_addr 함수에 대해서 알아두어야 할 구조

endian unsigned int color = 0x12345678; 를 선언하면 메모리에 반대로 리틀인디안 형식으로 저장된다. 엔디언은 숫자를 1바이트씩 쪼개서 저장할 때 작은 자릿수가 앞에 저장 (리틀엔디언) 읽는 방식이랑 반대라서 생소하게 보이지만, 우리가 보통 사용하는 x86(x86-64) 계열 CPU는 다 리틀 엔디언 방식

첫 번째 줄과 두 번째 줄의 간격이 바로 size_line

get_data_addr 함수에서 bpp값(32)을 주고 있고 이런 것을 종합해서 해당 이미지의 정보를 가져와서 값을 사용하면 됩니다.

(x * all->mlx.bpp / 8) + (y * all->mlx.line_l)

 

참고1
참고2

참고3

 

참고1

참고2