레이케스팅 게임: 킬러 바나나

April 15, 2024

프로젝트 소개

이드 소프트웨어 시절, 존 카맥

요구 사항

이 프로젝트는 에꼴 42 과제로 시작되었다. 따라서 과제의 요구사항은 간단히 다음과 같다.

C 언어로 레이케스팅 기법을 구현할 것(C99 컴파일러).
키보드 이벤트를 받아 시점조작이 가능할 것.
80자 25줄 제한의 프로시저
- 보통 함수라고 하는데 C 언어로 구조적 프로그래밍을 익히는 과제이니 프로시저라고 부르는게 바람직하다.
허용 함수
- open, close, read, write, printf, malloc, free, perror, strerror, exit, math 라이브러리 함수들
MinilibX 라이브러리
- MinilibX는 C언어로 그래픽 어플리케이션을 만들 수 있도록 설계된 경량 그래픽 라이브러리이다. 복잡한 X11 라이브러리의 윈도우 시스템을 간단하게 추상화하여, 윈도우 생성, 이벤트 처리, 픽셀, 이미지 등의 기능을 사용할 수 있다. 다른 라이브러리에 비해 설정이 간단하고 사용이 쉬워 교육 목적으로 사용되는 라이브러리이다.
이외의 라이브러리 금지
지정된 맵파일 포맷
벽 텍스쳐 지원(xpm, png 포맷)
천장, 바닥 단색 지원(RGB값)

개인적 아쉬움, 빌게이츠 의장님도 혀를 내두를 상황

가장 큰 문제는 외부라이브러리가 허용되지 않아 싱글스레드 이상의 POSIX API를 자유롭게 사용하지 못한다는 것이다. 레이케스팅으로 4K 144fps를 지원해보고 싶다는 생각이 들었지만, 아무리 레이케스팅 병목이 적더라도 싱글스레드로 800만개의 픽셀을 순회하면서 버퍼의 데이터를 6.9ms안에 업데이트 해주는 것은 어려울 것이라고 생각되었다.

각 픽셀을 0.86나노초 안에 작업이 완료되어야하는데, 3GHz CPU로 단순 계산을 해보았을 때, 각 픽셀을 2.57 클럭 사이클안에 수행해야 한다.

예를 들어 int a = 3 + 5; 이것만해도 1~2 사이클 아닌가?

텍스쳐파일에서 픽셀값을 가져와, 이미지 버퍼에 넣는 작업을 2.57 클럭 사이클안에 하는 건 빌게이츠의 할아버지가 와도 방법이 없다고 하실 것 같다. MinilibX에서 지원하는 기능이 제한적이다 보니, C로 레이케스팅을 구현해볼 수 있다는 점에서 의의를 두어야할 것 같다.

레이케스팅이란?

핵심개념

레이케스팅(raycasting)은 1980년대 3D 컴퓨터 그래픽스에서 등장한 기법이다. 정확히는 실시간 렌더링 때문에 등장한 개념인데, 게임은 사전에 렌더링할 수 없다. 사용자가 어떻게 조작할 줄 알고 미리 렌더링하겠는가? 당시 영화쪽 3D 그래픽스 기술은 볼만한 그래픽이었지만 실시간 렌더링이 필요한 게임 분야에서는 렌더링이 오래걸리는 문제가 큰 문제였다. 이러한 문제를 해결하기 위해 등장한 개념이 레이케스팅이다.

레이케스팅은 시점에서 시야에 들어오는 물체들, 즉 모니터로 보여야할 물체들에 대해 가상의 광선을 쏴서 거리를 계산하는 기법이다. 각 광선이 모니터 가로폭만큼의 픽셀별로 발사되고, 광선이 충돌하는 지점을 찾아 그 지점과의 거리를 구한다. 멀리 있는 물체일수록 작게 보이는 원근감을 이용해 입체처럼 보이도록 거리에 따라 물체의 크기를 반비례하게 렌더링한다. 멀리 있는 물체는 작게 렌더링하고, 가까이에 있는 물체를 크게 렌더링하면 원근감이 발생해, 입체처럼 보이게 된다.

왜 쓰인걸까

이 기술의 가장 큰 장점은, 극한의 효율이다. 레이트레이싱(레이케스팅과 다른 개념임)과 다르게 입체를 표현하기 위한 최소한의 계산이 이루어지다보니 1980년대 PC에서도 작동이 어느정도 가능하다는 희망을 가져다 주었다.

1980년대와 1990년대 초반, 대부분의 PC와 게임 콘솔은 성능이 좋지 않았음에도 불구하고 레이케스팅 기법 덕분에 실시간 3D 렌더링이 가능해졌다. 이는 플레이어에게 하여금 2D에서 3D 세계로 확장시켜준, 말 그대로 ‘새로운 차원’의 경험을 시켜주었다. 게임 역사에서 얼마나 큰 도약이었을지 상상해보면 심장이 뛴다.

레이케스팅 vs 레이트레이싱

레이케스팅

레이트레이싱

이름이 비슷해 보이지만, 차이가 크다. 레이트레이싱은 레이케스팅보다 훨씬 고급진 결과물을 보여준다. 두 기술 모두 광선을 사용한다는 점에서 ‘레이-‘라는 접두사가 사용된다.

차이점은 복잡성이다. 레이케스팅은 모니터 가로폭 픽셀 수만큼만 광선을 쏘는 방면 레이트레이싱은 픽셀 전체 개수만큼 광선을 쏴야한다. 벌써 O(N)에서 O(N^2)이 된 느낌이다. 그리고 더 나아가 발사한 광선이 물체에 부딪혔을때 튕겨져나오는 빛을 방향을 계산하고 고유한 색상(Diffuse 혹은 Albedo 색상)과의 복잡한 계산이 필요하다. 튕겨져 나온 빛은 하나가 아니라 분산되기 때문에 각 광선을 계속 추적해야한다. 상상만해도 어머어마한 연산량이 필요하다. 이 둘은 얼마나 다른지 복잡성 하나로 설명할 수 있을 것 같다.

따라서 레이트레이싱은 영화 CG에서나 사전에 렌더링할 수 있는 분야에서만 사용되었다. (요즘은 게임에도 레이트레이싱 기술이 적용된다. 무서운 발전이지만 요즘 그래픽카드 가격이 더 무서운 것 같다)

설계

데이터 구조

typedef struct s_map
{
    char **arr;
    int size_x;
    int size_y;
}    t_type;

typedef struct s_player
{
  vec2f pos;
  vec2f dir;
}

알고리즘

레이케스팅 알고리즘을 사용하여 각 레이가 벽에 부딪힐 때까지 연장하고, 부딪히는 점의 거리를 계산하여 벽의 높이를 도출한다.
텍스처 매핑을 위해 텍스처 좌표를 계산하고, 벽에 그린다.

기술 스택:

C 언어(C99)
MinilibX 라이브러리