레이캐스팅과 miniLibX을 이용한 3D게임 만들기

Wolfenstein 3D

참고

lodev사이트 https://lodev.org/cgtutor/raycasting.html#Introduction

• 모든 개념들을 참고한 사이트

365kim님의 깃헙 https://github.com/365kim/raycasting_tutorial

• 로데브를 한글 번역한 사이트

https://harm-smits.github.io/42docs/libs/minilibx/introduction.html

• mlx 설명 사이트

프로젝트 개요 설명

벽으로 둘러싸인 2차원의 맵을 만든 후 벽과 아이템을 맵에 나타내고 유저를 중심으로 맵을 wsad키를 이용해서 돌아다닐수 있어야한다. 종료는 esc키와 창의 종료버튼을 이용해서 할수 있어야한다

맵을 만들때는 4방위에 따른 텍스쳐를 벽에 적용시키며 벽을 나타내는 알고리즘은 레이캐스팅을 이용하여
벽(숫자 1)을 확인하고 그에 따른 벽을 miniLibX를 이용하여 띄운 창에 이미지를 그려준다

벽의 유무를 판단하기 위해서는 유저를 중심으로 시야각을 향해 각 픽셀마다 광선을 쏘고 각 칸마다 벽의 존재를 확인하는 방식으로 진행한다 (DDA 알고리즘)
이때, 유저를 하나의 점으로 취급하면 어안렌즈효과로 벽이 둥글게 우는 효과가 생길수 있으므로 유저를 하나의 카메라 평면으로 취급해서 처리해야한다

맵)

0과 1, 2를 이용해서 만들며 1은 벽, 0은 공간, 2는 아이템을 의미한다 스페이스바는 외부 빈 공간으로 취급하며 1로 둘러싸이지 않은 외벽은 존재할수 없다 → 맵이 유효한 맵인지 검사해야한다

레이캐스팅

👉 wiki 정의

광선 투사(Ray casting)는 컴퓨터 그래픽스와 계산기하학의 다양한 문제를 해결하기 위해 광선과 표면의
교차검사를 사용하는 기법을 말한다. 
이 용어는 1982년 스코트 로스의 구조적 입체 기하학 모델을 렌더링하기 위한 기법을 묘사하는
컴퓨터 그래픽스 논문에서 처음 사용되었다

광선 투사 기법은 다양한 문제와 다양한 기법과 관련이 있다

- 광선에 처음으로 교차되는 물체를 가려내는 일반적인 문제
- 카메라로부터 이미지의 각 픽셀을 향한 광선 교차 검사를 통한 은면 제거(hidden surface removal)
- 기본적인 광선들만을 검사하는 비재귀적 광선 추적(ray tracing) 렌더링 알고리즘
- 볼륨 레이 캐스팅이라 불리는 직접적 볼륨 렌더링 기법
	이 기법은 광선이 물체에 직접적으로 관통해 물체 내부를 샘플링한 3D 스칼라장으로 뚫고 들어간다. 
	이 기법에서 광선은 반사되지 않는다.

다양한 광선 투사 기법중 내가 사용할 기법은 첫번째인 광선에 처음으로 교차되는 물체를 가려내는경우에 사용되는 기법이다

기본개념

• 2차원 정사각형의 그리드로된 맵이 있다
• 맵의 한 칸은 0또는 양수값을 갖는다
  • 0은 벽이 없음을 나타내고, 양수값은 벽이있으며 특정 색 또는 질감을 나타낸다
• 화면의 모든 x값(수직선)에 대해 플레이어 위치에서 시작하는 광선(Ray)을 쏜다
• 이때 광선은 벡터값으로 플레이어가 바라보는 방향을 가지며, 화면의 x좌표에 의존한다
• 광선은 맵 위에서 벽이 부딪히면, 유저와 벽간의 거리를 측정한다
• 해당 측정된 거리를 이용해서 부딪힌 벽의 높이를 얼마나 그릴지 결정한다 → 거리와 벽의 높이는 반비례관계

벡터와 카메라를 이용

• 유저의 위치는 항상 벡터이다 (x, y)
• 방향또한 벡터로 표현된다. 즉 방향은 방향벡터의 x좌표, y좌표 두값으로 결정된다
  • 플레이어가 바라보는 방향으로 선을 그릴경우, 그 선위의 모든 점들은 플레이어의 위치(좌표) + 방향벡터의 배수의 합이다
• 카메라 평면

• 위 이미지에서 카메라평면(보라색 선)은 컴퓨터의 화면을 나타내고 방향벡터(검정)는 화면 내부를 가르킨다

  • 카메라 평명은 방향벡터에 항상 수직이다
  • 초록점인 플레이어 위치는 카메라 평면보다 앞에 있다(front)

• 주요값들의 벡터의 덧셈을 이용한 표현

  • pos 벡터 : 플레이어의 위치 (초록 점)
  • dir 벡터 : 방향 벡터 (검은색 선)
  • plane 벡터 : 전체 카메라평면(보라 선) 중 방향벡터의 끝점인 검정점으로 부터 오른쪽의 카메라 평면 끝까지를 의미
  • 방향 벡터의 끝점 (검정 점) : pos + dir
  • 오른쪽 카메라 평면의 끝점 : (pos + dir) + plane
  • 왼쪽 카메라 평면의 끝점 : (pos + dir) - plane

• 유저를 중심으로 카메라 평면을 향해 쏘는 광선의 다발들에 대해 광선의 방향을 쉽게 구할 수 있다

• 계산 방법 : 방향벡터 + 카메라 평면 X 배수

  • 위 이미지에서 적색 선이 광선을 의미하는데, 카메라 평면상의 오른쪽길이의 1/3 지점을 통과하는 광선을
    dir + (plane X 1/3) 으로 표현할 수 있다
  • 해당 광선의 방향을 rayDir 벡터라고 하고, 벡터의 x, y값은 DDA알고리즘에 사용된다

• 유저가 방향을 돌리면 시야가 같이 회전해야하므로 방향벡터와 카메라 평면벡터 모두 회전해야한다

  • 광선다발은 방향벡터와 카메라평면에 의존적이므로 따라서 회전된다
  • 벡터를 회전시키기 위해선 벡터좌표와 회전행렬과 곱해주면된다
  • x = $x * cos(a) + x * -sin(a)$
  • y = $y * sin(a) + y * cos(a)$

회전행렬

DDA알고리즘

DDA 알고리즘은 2차원 좌표를 지나가는 광선(Ray)이 어떤 네모칸과 부딪히는지 찾을 때 사용되는, 속도가 빠른 알고리즘이다

이를 통해 부딪힌 벽의 거리를 계산해서 해당 거리를 이용해서 벽의 높이를 설정해준다

DDR 알고리즘을 위한 변수 설명

위 이미지는 sideDistX, sideDistY, deltaDistX, deltaDistY를 보여준다

• sideDistX : 시작점 ~ 첫번째 x면을 만나는 점까지의 광선의 이동거리
• sideDistY : 시작점 ~ 첫번째 y면을 만나는 점까지의 광선의 이동거리
• deltaDistX : 첫번째 x면 ~ 바로 다음 만나는 x면 까지의 광선의 이동거리 (x는 1증가 (블럭 크기가 1))
• deltaDistY : 첫번째 y면 ~ 바로 다음 만나는 y면 까지의 광선의 이동거리 (y는 1증가 (블럭 크기가 1))

rayDir : 광선의 방향벡터 (빨간 선)

• rayDirX : 방향 벡터 + 카메라 평면 x 배수 → dirX + (planeX * cameraX) ↔ Y는 Y로 하면된다

deltaDistX = |1 / rayDirX| - 피타고라스의 정리를 이용하여 산출한 식 ↔ Y또한 그대로 하면된다

cameraX : 화면의 수직선(시야각에 존재하는 수직선)들의 x값이 카메라 평면에서 나타내는 x좌표이다

• x값이 0이면 (스크린 왼쪽 끝) → cameraX = -1
• x값이 w(화면폭) / 2 이면 (스크린 중앙) → cameraX = 0
• x값이 w(화면폭)이면 (스크린 오른쪽 끝) → cameraX = 1
• 식 : cameraX = 2 * (x / w) - 1

DDA알고리즘은 각 수직선을 계산할 때마다 x방향 or y방향으로 딱 한 칸씩 점프한다

• 광선의 방향에 따라 오른쪽위인지 왼쪽위인지 정해야하는데 그 정보는 stepX, stepY에 +1, -1로 담아둔다

벽의 x면, y면에 부딪혔는지의 여부에 따라 하나의 수직선이 벽을 찾는 루프문이 종료된다

• hit : 부딪힌 여부에 대한 정보
• x면에 부딪히면 side를 0, y면에 부딪히면 side를 1로 저장

stepX : rayDriX의 값에 따라 정해지는데 양수면 +1, 음수면 -1이다 (y또한 같다)

sideDistX의 값 산출

rayDirX가 양수면 오른쪽으로 가다 만난 x면까지의 거리이고
rayDirY가 음수이면 왼쪽으로 가다 만난 x면의 거리이다 ↔ sideDistY는 위아래로 생각하면된다

rayDirX가 양수 일 경우 : sideDistX = (mapX + 1 - posX ) x deltaDistX

rayDirX가 음수 일 경우 : sideDistX = (posX - mapX) x deltaDistX

posX는 시작점의 칸에서도 어느 x좌표에 있는지 알려주는 것이고 mapX는 시작점이 존재하는 칸의 x좌표이다

어안렌즈효과 방지

유저를 중심으로 광선을 쏘게 되면 하나의 평면상의 벽도 볼록 렌즈로 보는것처럼 둥그렇게 울어서 보일수 있다. 따라서 유저가 속한 카메라 평면에서 수직의 선을 피사체에 그어서 해당 거리를 가지고 계산한다

side == 0 일 경우 (x면에 부딛힌경우)
-> perpWallDist = (mapX - posX + (1 - stepX) / 2) / rayDriX

side == 1 일 경우 (y면)
-> perpWallDist = (mapY - posY + (1 - stepY) / 2) / rayDirY

(*) (1 - stepX) / 2 부분은 stepX가 -1, 1 인지에 따라 1, 0이 되는데 이는 rayDirX < 0 일 때
길이에 1을 더해주기 위함이다
즉 rayDirX < 0 이면 -> (mapX - posX + 1) / rayDirX 이다

위 식을 통해 카메라 평면에서 피사체의 수직선까지의 수직거리를 구할수 있다

유저의 카메라평면으로 부터 해당 벽의 거리의 수직 거리(perpWallDist)를 이용해서 화면에 그려야할 선의 높이를 구하자

lineHeight = 스크린의 높이 / perpWallDist
거리가 멀~~~어질수록 스크린 대비 높이는 낮아진다

스크린 높이의 중앙부 기준으로 시작과 끝은 잡는다
drawStart = (-lineHeight / 2) + 스크린높이/2  if (시작점이 0보다 작다면 0으로 고정)
drawEnd = (lineHeight / 2) + 스크린높이/2  if (끝점이 스크린 높이보다 크다면 스크린 높이로 고정)

miniLibX 라이브러리

mlx 라이브러리

키 핸들링, 이벤트 핸들링, 새 창 생성 및 이미지 생성을 위해 사용하는 라이브러리이다

정의

MiniLibX는 X-Window 및 Cocoa에 대한 지식없이 화면에서 무언가를 렌더링하기 위한 가장 기본적인 작업을할 수 있는 작은 그래픽 라이브러리입니다. 소위 단순한 창 생성, 의심스러운 그리기 도구, 반쪽짜리 이미지 기능 및 이상한 이벤트 관리 시스템을 제공합니다

👉 기본적인 mlx라이브러리 사용법을 아래 링크를 통해 확인 할 수 있다

Introduction

void *mlx_init(void)

• 소프트웨어와 디스플레이 사이의 연결을 초기화한다
• 이 연결이 생성되어야 다른 mlx함수들을 사용할 수 있다
• 반환값인 포인터는 프로그램 종료시 까지 유지해야 한다
• 오류 발생시 널 포인터를 반환한다

void *mlx_new_window(void mlx_ptr, int size_x, int size_y, char title)

• size_x * size_y 사이즈의 윈도우를 생성 및 화면에 표시해준다
• title은 제목 표시줄에 위치한다
• 오류 발생시 널 포인터를 반환한다

int mlx_pixel_put(void *mlx_ptr, void *win_ptr, int x, int y, int color)

• win_ptr에 해당되는 창의 (x, y)좌표에 color색으로 한 픽셀을 채운다
• 매우 느리므로 사용을 지양하자

void *mlx_new_image(void *mlx_ptr, int width, int height)

• width * height 사이즈의 빈 이미지 생성 및 이미지 포인터를 반환한다
• 이미지 정보 수정은 mlx_get_data_addr 함수를 통해서 받은 배열에서 가능하다
• 오류 발생시 널 포인터를 반환한다

void *mlx_xpm_file_to_image(void *mlx_ptr, char *filename, int *width, int *height)

• filename과 int형 변수의 주소값을 넘겨주면 xpm파일을 이미지로 변환 후 해당 이미지 포인터를 반환한다
  int형 변수에는 해당 이미지의 width, height가 저장된다
• 이미지 정보 수정은 mlx_get_data_addr 함수를 통해서 받은 배열에서 가능하다

char *mlx_get_data_addr(void *img_ptr, int *bits_per_pixel, int *size_line, int *endian)

• img_ptr과 int형 변수의 주소들을 넘겨주면 char형 배열의 주소 변환
• bits_per_pixel : 한 픽셀을 표현하는데 필요한 비트 수
• size_line : 이미지의 width를 표현하는데 필요한 바이트 수
• endian : 리틀 엔디언이면 0, 빅 엔디언 이면 1
• 해당 배열에 접근하여 이미지 정보 수정가능
• 오류 발생시 널 포인터 반환

int mlx_put_image_to_window(void * mlx_ptr, void *win_ptr, void *img_ptr, int x, int y)

• win_ptr에 해당되는 창의 (x, y)에 이미지를 그린다 (이미지의 좌상단 부터)

int mlx_loop(void *mlx_ptr)

• 이벤트 입력을 대기하며 절대 반환되지 않는 무한루프
• 루프 종료를 위해선 exit()함수 사용

int mlx_hook(void *win_ptr, int x_event, int x_mask, int (*funct)(), void *param)

• 사용자 정의 이벤트 핸들러 (전달한 함수로 처리한다)
• x_event : 키 press, release, x버튼 press 등 원하는 이벤트 설정 가능
• x_mask : 무시한다 (0으로 놔둠)
• (*funct)() : 원하는 기능의 함수 포인터
• param : 함수로 넘겨줄 변수

int mlx_loop_hook(void *mlx_ptr, int(*funct)(), void *param)

• 아무 이벤트도 발생하지 않았을 때 전달된 함수를 실행한다
• (*funct)() : 원하는 기능의 함수 포인터
• param : 함수로 넘겨줄 변수

int mlx_get_screen_size(void *mlx_ptr, int *sizex, int *sizey)

• 현재 스크린의 사이즈를 구하는 함수
  mlx_get_screen_size

@param void *mlx_ptr : the mlx instance
@param int *sizex : the screen width
@param int *sizey : the screen height
@return int : has no return value
*/

실제 코드 구현하기