오늘 Wolfenstein 3D 게임이 Linear Feedback Shift Register를 이용해 페이드 효과를 구현한 방법에 대한 흥미로운 글을 읽었습니다. 화면의 모든 픽셀이 의사 난수 방식으로 하나씩 빨간색으로 바뀌어, 결국 화면 전체가 빨갛게(게임 내 이벤트에 따라 다른 색이 될 수도 있습니다) 변하는 방식입니다. 구현 과정을 설명한 블로그 글은 여기에서 볼 수 있으며 읽어볼 만한 가치가 있습니다: http://fabiensanglard.net/fizzlefade/index.php

원래 코드가 왜 LFSR을 사용했는지, 혹은 제가 왜 setPixel(rand(),rand()) 같은 단순한 방식 대신 다른 접근법을 제안하는지 궁금하실 수 있습니다. 블로그 글에서도 언급했듯이 의사 난수 생성기로 이렇게 구현하면 느릴 뿐만 아니라 시각적으로도 매우 보기 좋지 않습니다. 이미 빨갛게 변한 픽셀이 많아질수록 아직 빨갛지 않은 새로운 픽셀을 맞출 확률이 점점 낮아지기 때문에, 마지막 픽셀들이 빨갛게 변하는 데 엄청나게 오랜 시간이 걸리기 때문입니다(옛 Spectrum, C64 시절이나 나중에 QBASIC이나 GWBasic으로 이 방식을 직접 시도해 보신 분들이 이 블로그 글을 읽는 분들 중에도 많을 거라고 *장담합니다*). 블로그 글 마지막 부분에서 저자는 이렇게 썼습니다:

“이 효과는 픽셀을 하나씩 찍어내는 방식으로 동작하기 때문에, 개발자들이 게임을 하드웨어 가속 GPU로 포팅하려고 할 때 재현하기가 어려웠습니다. 320x200보다 높은 해상도에 도달할 수 있는 LFSR 탭 구성을 찾아낸 Wolf4SDL을 제외하고는 어떤 포팅 버전도 피즐페이드를 제대로 재현하지 못했습니다.”

로켓 과학은 아니지만 다른 해상도에 적합한 LFSR을 찾는 것이 어려웠을 수도 있습니다. 하지만 다른 해상도에 맞는 적절한 LFSR을 찾는 일이 실제로 얼마나 복잡했든 간에, 포팅을 담당한 개발자들은 Feistel Network라 불리는 다른 기법을 이용하면 아주 간단하게 정확히 동일한 결과를 얻을 수 있었을 것입니다.

Feistel Network란 무엇인가?

암호학에서 흔히 사용되는 기본 구성 요소입니다. 하나의 비트열을 다른 비트열로 변환하는데, Feistel 네트워크 내부에서 어떤 종류의 비선형 변환을 사용하더라도 그 변환은 항상 역변환이 가능합니다. 실질적으로 예를 들면, Feistel 네트워크는 어떤 함수 F()에 따라 32비트 숫자 A를 다른 32비트 숫자 B로 변환할 수 있으며, 나중에 B에서 A로 언제나 되돌아갈 수 있습니다. 이 함수가 역변환 가능하다는 것은 곧 Feistel 네트워크가 모든 입력값에 대해 *서로 다른* 출력값을 생성한다는 의미입니다.

다음은 간단한 Feistel 네트워크를 의사 코드로 나타낸 것입니다:

Split the input into L and R halves (Example: L = INPUT & 0xFF, R = INPUT >> 8)
REPEAT for N rounds:
    next_L = R
    R = L XOR F(R)
    L = next_L
END
RETURN the value composing L and R again into a single sequence of bits: R<<8 | L

즉, (예를 들어) 16비트 정수를 8비트 정수 L과 R 두 개로 나누고, N번의 라운드 동안 모종의 변환을 수행한 뒤 다시 하나의 16비트 정수로 합쳐 출력으로 내보내는 방식입니다.

그렇다면 이것이 FizzleFade를 구현하려는 우리의 문제에 어떻게 도움이 될까요? 2차원 화면을 일렬로 늘어선 픽셀 배열이라고 상상해 보시면 됩니다. 원작 게임처럼 해상도가 320x200이라면 픽셀 0번부터 63999번까지가 있는 셈입니다. 따라서 0부터 63999까지의 모든 정수에 대해 단순히 하나씩 세어 나가면서 Feistel 네트워크가 반환하는 위치의 픽셀을 칠하면 무작위처럼 보이는 픽셀 위치를 생성할 수 있습니다. 문제는 Feistel 네트워크가 비트 단위로 동작하기 때문에 정확히 0부터 63999까지의 범위를 만들 수는 없고, 충분히 큰 2의 거듭제곱을 선택해야 한다는 점입니다. 이 경우 가장 가까운 것은 16비트입니다. 16비트라면 65536개의 정수 대 정수 변환을 만들 수 있는데, 몇몇 사이클은 실제 픽셀을 칠하는 데 사용되지 않겠지만 큰 낭비는 아닙니다.

따라서 Javascript로 작성한 우리의 Feistel 네트워크는 다음과 같이 생겼습니다:

/* Transforms the 16 bit input into another seemingly psenduo random number
 * in the same range. Every input 16 bit input will generate a different
 * 16 bit output. This is called a Feistel network. */
function feistelNet(input) {
    var l = input & 0xff;
    var r = input >> 8;
    for (var i = 0; i < 8; i++) {
        var nl = r;
        var F = (((r * 11) + (r >> 5) + 7 * 127) ^ r) & 0xff;
        r = l ^ F;
        l = nl;
    }
    return ((r<<8)|l)&0xffff;
}

제가 사용한 비선형 변환 “F”는 대부분 무작위로 고른 몇 개의 곱셈과 시프트 연산에 불과합니다. 더 나은 F 함수가 있다면 필요하지 않을 수도 있지만 8라운드를 사용했는데, 효과가 무작위처럼 보이기를 원했기 때문입니다(우연히도 픽셀을 무작위로 그리는 것은 자명한 분포 결함을 시각적으로 찾아내기에 꽤 괜찮은 방법이기도 합니다).

이를 Javascript 캔버스로 구현하려면 2D 컨텍스트를 얻고 픽셀을 찍기 위한 몇 가지 함수가 더 필요합니다.

최종 코드는 이 Gist에 있습니다: https://gist.github.com/antirez/6d58860b221a6ae5622ced8ccdddbe47

결과는 여기에서 확인하실 수 있습니다: http://antirez.com/misc/fizzlefade.html

이 글에서 탐구하려던 원래 문제는 다양한 해상도에서 이 효과를 구현할 방법을 찾는 것이었습니다. 따라서 320x200인 경우를 자명하게 확장한 것에 불과하지만, 예를 들어 1024*768로 같은 효과를 구현하고 싶다고 가정해 보겠습니다. 픽셀 수는 786432개이므로 2^20인 1048576개의 가능한 정수가 꽤 잘 맞습니다. L과 R 변수를 각각 10비트로 하여 Feistel 네트워크가 20비트 입출력을 갖도록 수정해야 하며, 그 외에는 거의 동일하지만 정지 조건(프레임 수를 확인하는 부분)도 함께 변경해야 한다는 점을 기억해야 합니다.

사실 Feistel 네트워크의 일대일 의사 난수 매핑 특성은 다른 맥락에서도 매우 유용합니다. 예를 들어 저는 제 radix tree 구현 테스트에서 이를 사용한 적이 있습니다(궁금하시다면 https://github.com/antirez/rax). 프로그래머의 머릿속 도구 상자에 넣어 두면 좋은 도구입니다.