개요
최근 고정 소수점 기반으로 게임을 만들고 있다. 요즘에서는 고정 소수점이 일종의 잃어버린 기술가 되어서 참고할 자료가 많지 않더라. Fixed-point arithmetic를 읽어보다 DOOM이 보여서 둠은 어떤식으로 구현했나 코드를 뒤져봤다.
Doom was the last first-person shooter title by id Software to use a 16.16 fixed point representation for all of its non-integer computations, including map system, geometry, rendering, player movement etc. This was done in order for the game to be playable on 386 and 486SX CPUs without an FPU. For compatibility reasons, this representation is still used in modern Doom source ports.
Binary Angle Measurement (BAM)
각도는 일반적인 정수/부동소수 연산과 다르다. 가장 큰 차이점이라면 주기가 있다는 점이다. 0도, 360도, 720도, …는 전부 같은 각도이다. 그래서 각도의 사칙연산을 수행한 다음에는 원하는 범위로 보정하기도 한다.
아래의 코드는 FixMath.NET의 Sine 함수이다. 인자로 넘어온 각도가 일정 범위를 벗어나지 않도록 보정하는 코드가 포함되어 있다.
public static Fix16 Sin(Fix16 inAngle) {
var tempAngle = inAngle % (Pi << 1);
if (tempAngle < Zero)
tempAngle += Pi << 1;
if (tempAngle >= Pi) {
tempAngle -= Pi;
if (tempAngle >= (Pi >> 1))
tempAngle = Pi - tempAngle;
...
}
if (tempAngle >= (Pi >> 1))
tempAngle = Pi - tempAngle;
....
}이로 인해 int, float를 그대로 각도로 쓰면 몇가지 문제점이 있다.
- 일점 범위를 벗어나지 않도록 값을 확인하고 보정해야 한다.
- 예: 180도 + 181도 = 361도, 361도는 0~360도에서 벗어났기때문에 360을 빼서 1도로 바꿈
- int, float 표현범위상에 중복되는 각도가 존재한다. 매우 정밀한 각도라고 말할 수 없다
- 예: int(0) == int(360) == int(720) …
- 예: float(0) == float(2PI) == float(4PI) …
DOOM에서는 Binary Angle Measurement (BAM) 이라는 기법을 이용해서 위의 문제를 해결했다. 코드는 다음과 같다.
// Binary Angle Measument, BAM.
#define ANG45 0x20000000
#define ANG90 0x40000000
#define ANG180 0x80000000
#define ANG270 0xc0000000
typedef unsigned angle_t;- 각도를 표현할 목적의 새로운 타입을 정의했다. 이를
angle_t라고 부르며unsigned int와 동일하다. - 0도=
0x0, 359.999999…도=0xffffffff으로 맵핑한다.
BAM 기법을 이용하면 각도가 일정 범위에서 벗어나지 않도록 보정할 필요가 없다.
각도의 사칙 연산도중에 범위를 벗어나는 각도(-24도, 730도)가 나오면 오버플로우에 의해서 올바른 범위로 알아서 보정된다.
예를 들어 180도(0x8000 0000)와 270도(0xc000 0000)를 더하면 450도(0x1 4000 0000)가 될텐데 오버플로우에 의해서 앞자리가 사라지고 90도(0x4000 0000)가 된다.
또한 매우 높은 정밀도로 각도를 표현할수 있다.
0x0 ~ 0xffffffff는 모두 다른 각도를 표현한다. 4바이트를 전부 사용해서 정밀하게 각도를 표현할수 있다.
sin()
lookup table을 이용하면 sine을 구현할수 있다. 그런데 lookup table은 어떻게 만들것인가? DOOM의 BAM은 잊고 360도 세상에서 sine lookup table을 구현해보자.
가장 간단한 방법은 크기 360의 배열을 만들어서 sine을 저장하는 것이다.
룩업 테이블에서의 인덱스는 (int)(degree * 1)이다.
- 0 ~ 0.9999도 = sine_table[0]
- 1 ~ 1.9999도 = sine_table[1]
- …
구현해놓고 써보니까 sine값 360개로는 정밀도가 낮더라. 조금더 높은 정밀도를 얻으려면 어떻게 하면 될까?
제일 단순한 방법은 테이블을 크게 만드는거다. 룩업 테이블의 크기를 3600으로 올려보자.
이때 룩업 테이블에서의 인덱스는 (int)(degree * 10)이다.
- 0.0 ~ 0.0999도 = sine_table[0]
- 0.1 ~ 0.1999도 = sine_table[1]
- 0.2 ~ 0.2999도 = sine_table[2]
- …
룩업 테이블의 크기가 10개 커지면 각도 구간을 10배 더 자세하게 표현할 수 있다. 각도에서 소수점 x번째 자리까지의 값을 이용하면 룩업 테이블에서의 인덱스를 얻을수 있다.
이 방법을 그대로 Binary Angle Measurement 적용해보자. 32bit unsigned int를 13bit + 19bit로 나눈다. 상위 13bit를 룩업 테이블에서의 인덱스로 사용한다. sine lookup table의 크기는 8192(2 ** 13)이다. 만약 더 정밀한 sine lookup table을 얻고싶으면 13비트 대신 14bit를 쓰면 되는거다.
// table.h
#define FINEANGLES 8192
#define FINEMASK (FINEANGLES-1)
// 0x100000000 to 0x2000
#define ANGLETOFINESHIFT 19
// Effective size is 10240.
extern fixed_t finesine[5*FINEANGLES/4];lookup table에서 sine을 계산하고 싶은 각도 앞뒤의 sine값을 얻은 다음 적절히 보간하는 방법도 있겠지만 486에서는 그런 사치를 부리지 못하나보다. DOOM에서 sine이 사용된 코드를 보면 BAM에 shift 연산을 적용한 다음 룩업 테이블을 조회한다. 추가 계산? 보간? 그런거 없더라.
// r_segs.c
sineval = finesine[offsetangle >>ANGLETOFINESHIFT];cos()
sin() 이 있으면 cos()는 간단히 구현할 수 있다.
cos(x)를 구하고 싶으면 sin(x + 90도) 를 계산하면 된다.
그런데 DOOM은 sine계산에는 lookup table 조회 한번이면 충분한데 cosine 계산에는 덧셈도 필요한게 성능을 까먹는다고 생각했는지 재밌는 기법을 이용했다.
- sine lookup table은 0~360도 구간이 아니라 90도를 더 계산해서 450도까지 계산한다.
finesine[5*FINEANGLES/4] - cosine lookup table의 주소값은 sine lookup table보다 90도 만큼 뒤를 가르킨다.
- sine 쓰듯이 cosine을 쓰면 된다.
// table.h
// Re-use data, is just PI/2 pahse shift.
extern fixed_t* finecosine;
// r_main.c
fixed_t* finecosine = &finesine[FINEANGLES/4];