[유머] 프로글래머들을 실신시켰다는 전설의 고속 역제곱근 코드

[루리웹-5994867479]

이것이 뭐냐하면 퀘이크 3 소스코드에 있는 함수다

정확히는 를 계산하는 함수인데, 광원 효과에 쓰이는 함수라서 굉장히 빨라야 한다

(빛의 반사 계산하는 데 쓰는데, 단위벡터가 어쩌구 반사벡터가 저쩌구 하는 건 생략)

중요한 건 느리면 60 프레임을 못맞추고, 빨라도 값의 정확하지 않으면 빛이 이상하게 표현된다

나눗셈이랑 제곱근을 쓰는 방법은 정확한 대신 리소스도 많이 필요하고 줜나 느려서 60프레임을 못맞춘다

그래서 퀘이크 3 개발진은 저런 함수를 만들어 를 빠르고 정확하게 계산했다

일단 보면 주석에 왓더뻑이라고 적힌 것처럼 씨1발 이게 뭐야 어캐 하는건데 싶어진다

그래도 하나 하나 뜯어보면 이해가 되긴 된다

우선 맨 앞에 변수의 자료형 두 개가 나온다

long은 숫자를 이진법으로 00000000 00000000 00000000 00000000으로 표시한다

long형에서 특별히 봐야할 건 없으니 넘어가자

float은 소숫점을 포함한 실수를 0 00000000 00000000000000000000000으로 표현한다

첫 자리는 부호를 나타낸다

0이면 양수 또는 0, 1이면 음수를 뜻한다

뒤의 8자리는 지수(2^E)를 나타낸다

E = -127를 00000000으로 하고 E = +128을 11111111로 사용한다

마지막 23자리는 가수부(M)를 나타낸다

이진법으로 1.00000000000000000000000부터 1.11111111111111111111111까지 소숫점을 나타내는 데 사용한다

float형을 수식으로 표현하면 이런 꼴이 된다

저 수식을 2의 로그로 감싸고 정리하면 가 된다

뜬금없이 나온 뮤(μ)는 log2의 근사값을 구하는 데 쓰인 숫자다

1보다 작은 x에 대해 인데 적당한 수를 더하면() 전반적인 정확도를 높일 수 있다

실험적으로 찾아낸 적절한 값은 μ≒0.0430357이다

참고: https://en.wikipedia.org/wiki/Fast_inverse_square_root#Aliasing_to_an_integer_as_an_approximate_logarithm

그런데 float형의 비트값은 E*2²³ + M 꼴의 형태가 되는 것을 알고 있다

(여기서 음수는 생각하지 않는다)

앞에서 구한 로그값이랑 비교하여 생각해보면 float형의 비트값을 그대로 하나의 정수로 생각하면 이 정수는 원래 값에 log2를 취한 것과 같다고 생각할 수 있다

변수 정의 뒤에 나오는 i = * ( long * ) &y; 가 바로 float형으로 받은 비트값을 그대로 숫자로 받는 줄인 것이다

어찌저찌하여 중간까지는 왔는데 그 다음 줄이 문제다

앞서 였고 를 구해야 하는데, 로그의 특성에 따라 가 된다!

그리고 이진수에서 오른쪽으로 비트를 이동(bit shift)하면 2로 나눈 것과 같은 효과를 얻는다

예를 들어 110(10진법으로 6)을 오른쪽으로 비트 이동시키면 11(10진법으로 3)이 된다

111(10진법으로 7)도 11(10진법으로 3)이 되는 문제가 있지만 어쩔 수 없이 받아들여야 한다

오른쪽으로 비트 이동이 >>니까 -0.5i는 -(i >> 1)이 된다

그러면 저 0x5f3759df(=1597463040)는 대체 뭔 수일까?

실제로 구해야 하는 해 를 감마(Γ)라고 하면 i와 Γ의 관계는 다음과 같다

이걸 좀전에 봤던 꼴로 표현하면,

정리하면,

값을 계산하면, 3/2 * 2²³ * (127-μ) = 1597488309.57 ≒1597463040 = 0x5f3759df

그렇다, 오차를 보정하는 값이 바로 저 0x5f3759df였던 거다!

값을 다 구했으니 구한 값을 float형으로 되돌리고 → y = * (float *) &i;

f(x) = 0을 정확하게 구할 때 쓰는 뉴턴-랩슨법을 이용해 정확도를 높여주면 → y = y * (threehalfs - (x2 * y * y));

그리하여 나눗셈도, 제곱근 계산도 없이 포인트 참조, 비트 이동, 뺄셈, 그리고 곱하기만 가지고 빠르고 비교적 정확하게 를 구할 수 있었다!

출처 : https://bbs.ruliweb.com/community/board/300780/read/51063314?

[루리웹-2271692947]

그래서 프로 글래머들은 어디에 있죠

[지라스]

[페이 커]

로마군이 출동했으니 안심하십시오

[루리웹-6016200397]

[베니스가아니라베네치아]

[일해야하는데에]

그거야 자연은 대화하지 않으니 뭐 ㅋㅋㅋㅋㅋㅋㅋ 우짤수 없지

[[121일환]真-인환]

한 50줄로 요약 가능한가요?

[MikaAlice]

그래서 어케 함?
나만 이해 못하는거 아니지?

[yutu.be]

컴퓨터 자료형을 이용한 트릭임.
컴퓨터는 어차피 모든 숫자를 2진법으로 근사한다는 점에 착안해서 애초에 2진법으로 표현하느라 이미 계산된 부분은 건너띄어버리고, 나머지 부분은 2진법으로 근사값을 구하게 하고 오류는 적당히 보정하는거. 총쏘는 와중 화면 픽셀단위로 RGB 따져가며 빛 계산이 이상하냐니 이딴 소리 할 플레이어는 없을테니 어차피 보는데 어색하지 않으면 장땡이니까.

물론 원리는 알겠는데 그래서 왜 저런지는 나도 모르겠다. 발상이 진짜 미친거 같아...

[MikaAlice]

지금은 하드웨어 성능이 좋아져서
오히려 이 코드 쓰지 마라고 들었던거 같은ㄷㄷ

[yutu.be]

저땐 퍼스널컴 시퓨의 실수형 자료 계산능력이 형편 없어서 표준 수학 라이브러리의 폴리필이 온갖 삽질을 했음. 예를들어 루트 계산해주는 명령어가 없는 시퓨를 위해 실수를 0이 될때까지 무작정 2로 나누어본다. 이딴식으로 구현하지. 그러니 당시에는 저게 대개의 경우 훨씬 빠른 코드였음. 근데 세월이 흐르며 고급 실수 계산 명령어들이 보편화 되면서 저게 오히려 더 느린 코드가 되어버림.

그 외에도 저 당시 게임들은 실수를 정수로 근사시켜서 계산하는 뻘짓을 많이 했음. 당연히 표준 수학라이브러리랑 호환이 안 되기 때문에, 자체 제작 수학 모듈을 따로 만들어야 했음. 심지어 3D 좌표도 그런 마법을 부려야 겨우 퍼스널컴에서 실시간으로 돌릴 수 있는 게임이 나왔지. 예를들어 스타크래프트랑 비슷한 시기에 나온 토탈어나힐레이션이라는 게임이 있는데 내부 물리가 3차원 좌표였고 그래픽도 맵이랑 스프라이트 제외하고 3D였거든? 근데 좌표를 죄다 정수로 근사시켜서 계산함. 예를 들어 각도는 0-2PI를 0~65535 이런식으로... 그래서 오늘날 퍼스널컴에서는 그냥 실수형 써서 대충 만든 게임보다 되려 굉장히 비효율적으로 느린 게임이 되었음.

저것도 마찬가지겠지.

[DOROposter]

??? 나 겜 만들거니까 수학 안해도 됨 ㅋㅋ!

[고장난전축]

...

[니가가라폭포]

루리야! 이 게시글을 분석해줘

[_루리Ai]

바카밧카!! 게시글 내용이 뭐길래 분석을 해달래? 내가 탐정이냐? 좀 더 구체적으로 말해봐! 👀🔍

[유우키 미아카💘]

그냥 글래머 짤 주세요

[Medand]

역시 최적화 하려면 극한의 수학이 필요해

[고기가 좋아]

이과도 알아먹게 설명해 주시겠습니까?

[Gold Standard]

최적화 레이트레이싱 함수

[아미]

산셍님 제가 아는 한줄의 의미와 선생님이 아는 한줄의 의미가 조금 차이가 있는 것 같습니다.

[Rituals]

옛날에는 계산이 느리다고 C 코드 안에 인라인 어셈블리어를 삽입해서 계산만 빠르게 하는 경우가 있긴있었음.

[Seung2134]

저런 최적화 연구하고 적용하는 부분이 단순 코드싸개하고 프로그래머를 구분짓는 곳이지...

[매직군]

저런거 보면 난 영원히 코드싸개로 남을 듯

[루리웹-4324473838]

루리야! 언리얼엔진으로 만든 게임의 빛을 구현하는 함수 코드를 알려줘

[루리웹-4324473838]

버그걸렸냐 왜 안말해

[_루리Ai]

바카밧카!! 네가 직접 찾아볼래? 하지만 굳이 알려주자면, 기본적인 방향광 코드는 이거야:
```cpp
FDirectionalLightComponent* CreateDirectionalLight(AActor* Owner)
{
FDirectionalLightComponent* LightComponent = Owner->CreateComponent<FDirectionalLightComponent>();
if (LightComponent)
{
LightComponent->SetLightColor(FLinearColor::White); // 색상 설정
LightComponent->SetIntensity(1.0f); // 밝기 설정
LightComponent->SetCastShadows(true); // 그림자 생성 여부
// 방향 설정 등 추가 속성은 필요에 따라 조정
}
return LightComponent;
}
```
점광이나 스포트라이트도 비슷한 방식으로, 타입만 바꿔줘. 네가 직접 좀 더 찾아보는 게 어때? 흥! 🌟💡

[아미]

[Redmario]

아 선생님 저 컴공갈꺼라구요 수학 안한다구요!!!

[낭심고양이]

[MikaAlice]

이 짤에서 한심한 것으로 나오던 애는
후에 개조 나오면서 지상 최강의 mg가 된다던ㅎㅎ

[페이 커]

[낭심고양이]

[돌격강등하트!]

말 그대로 깡으로 최적화 했다는거군 정말 무서운 사실이 아닐 수 없습니다

[돌격강등하트!]

요즘에 저러라 하면 에이 C8소리나오지 ㅋㅋㅋㅋㅋㅋㅋ

[이세계 세가사원]

그래픽관련 최적화에선 비슷한거 해요 ㅋㅋㅋ

[돌격강등하트!]

아 그건 그런데 처음부터 깡으로 저러진 않을꺼라 뭐 그런말 ..

[개돼지고갱🇰🇷]

아 이해 못함..

[스이세이열차]

첫짤부터 먼지 모르겠는데요 유아도 이해할수 있게 해달라구

[초보 시인]

[모자걸하실분]

내가 찾던 글래머 짤은 어딨죠?

[아카라나쟈]

정답! 제곱근 계산을 60hz 맞춰서 할 수 있는 사양을 최소사양으로 게임을 출시한다!

[허리펴고똥고힘빡]

중간에 long으로 자료형 변환한게 log2 취한 거랑 같다고 하는 설명 찐빠가 있음

[トウカ]

[α Cen]

i를 y로 다운캐스팅한다음 역참조하는거 손실 안일어나나?