이것이 뭐냐하면 퀘이크 3 소스코드에 있는 함수다
정확히는 를 계산하는 함수인데, 광원 효과에 쓰이는 함수라서 굉장히 빨라야 한다
(빛의 반사 계산하는 데 쓰는데, 단위벡터가 어쩌구 반사벡터가 저쩌구 하는 건 생략)
중요한 건 느리면 60 프레임을 못맞추고, 빨라도 값의 정확하지 않으면 빛이 이상하게 표현된다
나눗셈이랑 제곱근을 쓰는 방법은 정확한 대신 리소스도 많이 필요하고 줜나 느려서 60프레임을 못맞춘다
그래서 퀘이크 3 개발진은 저런 함수를 만들어 를 빠르고 정확하게 계산했다
일단 보면 주석에 왓더뻑이라고 적힌 것처럼 씨1발 이게 뭐야 어캐 하는건데 싶어진다
그래도 하나 하나 뜯어보면 이해가 되긴 된다
우선 맨 앞에 변수의 자료형 두 개가 나온다
long은 숫자를 이진법으로 00000000 00000000 00000000 00000000으로 표시한다
long형에서 특별히 봐야할 건 없으니 넘어가자
float은 소숫점을 포함한 실수를 0 00000000 00000000000000000000000으로 표현한다
첫 자리는 부호를 나타낸다
0이면 양수 또는 0, 1이면 음수를 뜻한다
뒤의 8자리는 지수(2E)를 나타낸다
E = -127를 00000000으로 하고 E = +128을 11111111로 사용한다
마지막 23자리는 가수부(M)를 나타낸다
이진법으로 1.00000000000000000000000부터 1.11111111111111111111111까지 소숫점을 나타내는 데 사용한다
float형을 수식으로 표현하면 이런 꼴이 된다
뜬금없이 나온 뮤(μ)는 log2의 근사값을 구하는 데 쓰인 숫자다
1보다 작은 x에 대해 인데 적당한 수를 더하면() 전반적인 정확도를 높일 수 있다
실험적으로 찾아낸 적절한 값은 μ≒0.0430357이다
그런데 float형의 비트값은 E*223 + 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 * 223 * (127-μ) = 1597488309.57 ≒1597463040 = 0x5f3759df
그렇다, 오차를 보정하는 값이 바로 저 0x5f3759df였던 거다!
값을 다 구했으니 구한 값을 float형으로 되돌리고 → y = * (float *) &i;
f(x) = 0을 정확하게 구할 때 쓰는 뉴턴-랩슨법을 이용해 정확도를 높여주면 → y = y * (threehalfs - (x2 * y * y));
그리하여 나눗셈도, 제곱근 계산도 없이 포인트 참조, 비트 이동, 뺄셈, 그리고 곱하기만 가지고 빠르고 비교적 정확하게 를 구할 수 있었다!
수정1: 오타랑 수식 잘못 집어넣은 부분 정정
하 이게 프로그래밍이지 ㅋㅋㅋ 최적화하려면 저 정도 수준까지 알아야하는구나
그러니까 저거 복사해서 쓰면되는거지?
저래서 수학 고인물이 필요하댔나
압도적인 성능을 기반으로 처리능력이 딸리면 구린 컴퓨터 쓰는 유저탓을 함
완벽하게 이해했어
ㅁㅊ 이게됨?
허용범위 내의 오차가 있지만 그대신 무지막지하게 연산이 줄어드는 기법들 보다보면 전 그냥 ㅂㅅ이구나 라는것만 느끼게 됬죠. 대학 과목중에 이게 있어서 3개월은 ㅂㅅ된 기분이었는데
요샌 그냥 컴파일러가 알아서 저런 코드로 바꿔줌. 저런 거 하느라 생산성 낭비하느니 그냥 다른 코드 한줄을 추상적으로 더 짜고 최적화는 대부분 컴파일러한테 떠넘기면 됨. 오히려 어줍잖게 최적화한다고 깝치면 컴파일러 최적화가 제대로 안 돌아서 더 느릴수도 있음
https://ko.wikipedia.org/wiki/%EA%B3%A0%EC%86%8D_%EC%97%AD_%EC%A0%9C%EA%B3%B1%EA%B7%BC "이 알고리즘은 1990년대 초에 실리콘 그래픽스에서 개발한 것으로 추정되며, 1999년에 퀘이크 3 아레나의 소스 코드에 쓰인 것이 가장 유명하다." 카맥이 만든게 아님. "이 알고리즘은 뉴턴의 방법을 사용하여 비교적 정확한 결과를 만들어 내지만, 소수점의 손실 때문에 부정확하고 1999년부터 도입된 x86 SSE의 rsqrtss에 비해 훨씬 느리다." 요새는 FPU가 더 빠르고 정확해서 안 씀
https://youtu.be/DEqXNfs_HhY 이런거 보면 수학하시는 분들 존경스러움
ㅁㅊ 이게됨?
완벽하게 이해했어
야황 육손
그러니까 저거 복사해서 쓰면되는거지?
ㅔ
저래서 수학 고인물이 필요하댔나
하 이게 프로그래밍이지 ㅋㅋㅋ 최적화하려면 저 정도 수준까지 알아야하는구나
굳이 정확히 말하자면, 저건 걍 수학에 가까움... 수학계산을 프로그래밍 언어로 옮겨 놓은 거 뿐이고... 쉽게 말하면, 프로그래밍 잘하는 사람들에게 저걸 보여주면 이해할사람이 거의 없겠지만, 프로그래밍은 c기초만 아는 사람이라도 수학자에게 보여주면 저거 다 이해할수 있는 문제라... 그리고 요즘 와선 최고수준의 퍼포먼스를 보여주는 게임을 만드는 회사도 저런 코드 쓸일은 사실상 없음...
what the f■ck?
간케
맞음. Q3 코드도 카멕형이함
참고로 저거 99년 게임이고 C로 짜진 엔진이다.
간케
개발은 혼자 다 하면 되니 사람 숫자 늘려서 의사소통에 시간 낭비하면 안된다고 하던 양반이니 직접 다 했겠지
간케
존 카멕이 둠 3에 들어간 광원효과도 직접 다 코딩했음
역시 과메기형
그래서 주석에 시X 저기 머꼬? 라는게 적혀있잖음ㅋㅋㅋㅋㅋ
주석 단 사람 심정 ㅋㅋㅋㅋ
ㅋㅋㅋㅋㅋㅋ
ㄷㄷ 역시 128류 개발자
암튼 게임 만드는데 수학자가 필요하다는거지?
수학자보다는 개발자가 수학적 사고와 친숙하고 컴퓨터의 구조를 잘알아야 한다는 거에 가까움
허용범위 내의 오차가 있지만 그대신 무지막지하게 연산이 줄어드는 기법들 보다보면 전 그냥 ㅂㅅ이구나 라는것만 느끼게 됬죠. 대학 과목중에 이게 있어서 3개월은 ㅂㅅ된 기분이었는데
와씨 와드
Q3 개발진이라고 뭉뜽그리기보다 카멕형이 만든거라고 봐야할거같다ㅋㅋ
이드 개발진 = 존카멕 공식은 레이지때까지 거의 유효했음.. 개발은 나 혼자 다 하면 된다던 사람이라..
그럿타. 둠3 엔진 만들때 C++로 처음 넘어간 양반일 정도로 효율을 되게 따진모양
이해했음 저 코드를 복사하면 된다는거지?
사실 API 이용하는 수준에서는 저런 수학 쓸 일도 적겠지만 저런 API를 만드는 입장에서는 대학원 석박사들이 모여서 저런 수학 이야기만 하겠지 무섭다
그럼 지금 기술은 저거보다 더한 게 많단 말이겠네.. 와..
요즘게임은 저걸 어떻게 극복했을까
V_solves_everything
압도적인 성능을 기반으로 처리능력이 딸리면 구린 컴퓨터 쓰는 유저탓을 함
요즘은 하드웨어가 좋아서 대부분 최적화 필요없음
V_solves_everything
요샌 그냥 컴파일러가 알아서 저런 코드로 바꿔줌. 저런 거 하느라 생산성 낭비하느니 그냥 다른 코드 한줄을 추상적으로 더 짜고 최적화는 대부분 컴파일러한테 떠넘기면 됨. 오히려 어줍잖게 최적화한다고 깝치면 컴파일러 최적화가 제대로 안 돌아서 더 느릴수도 있음
이게 맞말이지 이젠 그냥 루트쓰면됨 퀘이크3는 1999년대 게임이니까 그런거지
지금은 극한환경에서 동작할 임베디드 머신 만들게 아니라면 저런 방법을 쓸 이유가 없어졌어
프로그래밍할거라 수학 잘 몰라도 된다는 애들이 꼭 봐야할거네 ㅋㅋㅋㅋㅋㅋ
게임 개발 안할거면 수학 필요없는게 맞음
???
나도 개발로 밥벌어 먹고 산지 10년정도 됐는데 수학쪽이 약해서 어디가서 개발자라고 얘기 안함. 그냥 개잡부 입니다. 이렇게 얘기하지
아주 틀린 말은 아니지
이제 하드웨어 좋아져서 게임이나 임베디드 아니면 굳이 수학잘할 필요없는게 맞긴함
프로그래밍은 그런이야기 잘 안나오지. 처음 발 담글때부터 닥치고 수학이라 것보다 기획에서 많이나옴. 그림못그리고 프로그래밍 못하는데 게임개발 하고싶은애들이 많다
다른 프로그래밍은 수학 안쓸것 같지? 요새 유행하는 인공 지능만 해도 수식 덩어리이고, DB도 수학 기반이고.. 하나못해 반복문 돌리는것도 기초적인 산수 필요함
사실 고수준 알고리즘 필요한 프로그래밍에선 수학 없인 불가능하죠...
생각보다 게임 말고도 수학이 많이 들어가는 분야는 많아요.
게임 개발을 안 할 거면 수학이 필요없다라기보단, 게임 개발이 그만큼 프로그래밍 중에서도 가장 어려운 축에 속한다고 보면 정확함. '나도 게임 만들어보고 싶어' 라는 건 '나도 초정밀 뇌수술 한 번 해 보고 싶어' 같은 말과 비슷하다고 보면 될 듯?
1/sqrt 가 저렇게까지 해야하는거였나...
수학과가 괜히 컴공으로 발돌린다는게 아니긴 하지
뭔소리지
좋아 이해해써
뇌가 이진법으로 되어있으신가ㄷㄷ 미쳤다;;
진짜 존카멕은 전설이다
무슨소리야 시팔
수학자가 괜히 알고리즘 개발하는게 아니지
광원효과 코드 와드
이런거보면 내가 월급받고 개발하고있는게 너무 죄송스러워진다 흑흑
나도 왓더퍽 이라고 주석 달았겠다. 뭐야 왜되는데? 하면서 수학자 입장에서는 쉽게 이해?할것 같다만 프로그래머 입장에서 느낌이 방정식 쉽게 계산하는거 찾다가 혹은 우연히 코드 찾아서 넣었더니 너무 잘작동되서 기분은 좋은데 정확하게 이해못해서 말한기분 ㅋㅋㅋㅋ
와 아이디어 대단하다
광원효과 코드 와드
왓더퍽
근데 뉴턴 랩슨법이나 이런 계산 수치계산쪽도 자세히 알아야하겠네
고등학교때로 돌아가면 수학따위 아무쓸모없다고 생각한나에게 죽빵때리고싶다
당연히 실생활에서는 그다지 필요 없음. 프로그래머나 공학 직업 가진 사람에게 필요하지....ㅋㅎㅎㅎ
직업이 공학쪽이라서.....
ㅠㅠ 왜 공부 안했어
두렵다..
결국에 근사값 최대한 이용해서 식 간단화했다는 거네. 컴퓨터 성능이 이걸 그냥 시켜도 사실상 프레임에 영향이 없을 정도로 발전한 지금은 이럴 필요는 없겠지.
컴퓨터 구조에 관한 명확한 지식이 없으면 할 수 없는
와 비트연산 극한을 여기서 보네 이게 뭐시에요
???:아 난 게임만들거라서 수학공부는 안해도 된다고!
와드
그전에 오차를 교정하는 수식도 있다는게 넘모 놀랍다
자신감이 떨어졌어
슈팅게임에서 주인공 기체따라 날라오는 좌/우편향 총알이나 주인공 기체가 쏜 총알이 긋는 궤적같은것도 방정식이 한덩어리씩 들어가지. 난 이전기획자가 넘겨둔 문서 그대로 개발에 던졌다가 개발이랑 같이 자빠졌었다. 소수점포함 8자리 숫자 하나 구할라고 10^33까지 올라갔다가 00.000000까지 내려오는 계산식을 만들어뒀더만. 수식 바꾸느라 둘이서 한달동안 대가리터짐. 난 안그래도 수학도 잘 못하는데 씨부럴..
https://youtu.be/DEqXNfs_HhY 이런거 보면 수학하시는 분들 존경스러움
빠른 제곱근 코드 와드
쩌네요
비트연산을 저렇게 써먹는거구나...
한국인이면 한국말로 해르
정확한 계산은 수학자들 몫이지 우리 공학자들은 적당한 보정값만 구해서 최고 효율만 원한다고
간단하게 6을 구하시오 하면 1+1+1+1+1+1로 더하기로 하냐 2×3하냐 해서 컴퓨터가 리소스 덜 잡고 빠르게 값을 구할때 수학이 중요하다는거
https://ko.wikipedia.org/wiki/%EA%B3%A0%EC%86%8D_%EC%97%AD_%EC%A0%9C%EA%B3%B1%EA%B7%BC "이 알고리즘은 1990년대 초에 실리콘 그래픽스에서 개발한 것으로 추정되며, 1999년에 퀘이크 3 아레나의 소스 코드에 쓰인 것이 가장 유명하다." 카맥이 만든게 아님. "이 알고리즘은 뉴턴의 방법을 사용하여 비교적 정확한 결과를 만들어 내지만, 소수점의 손실 때문에 부정확하고 1999년부터 도입된 x86 SSE의 rsqrtss에 비해 훨씬 느리다." 요새는 FPU가 더 빠르고 정확해서 안 씀
카맥이 쓴건 저 왓더 뻑 이라는 주석이라는 소리 카멕도 다져다 복 붙했....
그래서 저 함수를 걍 컨트롤C 컨트롤 V 하면 된다는거지?
ㄴㄴ 라이브러리화 되어있으니 불러오기 하면 됨
요즘엔 그냥 루트쓰고 컴파일러님이 해결해주는거 구경하면 됨
컴파일러가 최적화 까지 다해준다니 개쩐다
무한반복문 돌릴때 for랑 while랑 속도 다르던 시절도 있었으니.
코어급 개발 아닌이상 어줍잖게 머리 안굴려도 라이브러리에 이미 최적화 된상태로 들어가고 컴파일러가 처리해주기도 하고 해서 날이 갈수록 신경 안써도 되는부분이 늘어남
먼말이야 슈바
저게 이해 안되면 이걸 생각하면 됨 1. pc에서 1부터 10000 까지 더한 결과를 내야 되는 경우가 있음. 2 단순한 프로그래머는 반복문을 이용해서 1+2+3.... 해서 10000 까지 더함. - 이러면 덧셈을 9999번 하는 거. 3. 그런데 옆에 지나가는 수학자가 (10000+1)x10000/2 라는 수식을 가르쳐줌. - 한번의 덧셈과 곱셈과 나눗셈으로 끝. 라이브러리 단계로 가면 이런게 꽤 있음
컴퓨터에게 수학을 노가다 시켜서 풀게 하냐 아니면 수식을 간단화해서 풀게 하냐의 차이같네
와,,, 개쩌네 본체의 연산능력을 이용해서 아예 프로그램이 해결하게 할거냐 아니면 식을 간소화 할거냐 캬 수학 좋아했었는데 역시 쩐다
비트연산이란 경우의 수를 생각하는 것부터 다르다.
광원 와드
전혀 모르겠다. //그래서 큰 업적 세우신 분들 보면 항상 수학자분들이랑 협업을 하지.. 막말로 나는 이론을 만들테니 너는 증명해라 ㅋㅋㅋㅋ
코드 읽다가 저 0x5f3759df에서 주석처럼 왓더뻑이란 생각이 듬 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 솔직히 용도는 몰라도 어떤 계산이 이루어지는구나 하는건 이해가 가는 간결한 코드임 저 32비트짜리 수 빼면 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
역시 수학은 대가리를 써서 풀어야돼 노가다로 풀면안돼고
요즘엔 하드웨어 성능뿐만 아니라 라이브러리랑 컴파일러 성능도 같이 좋아져서 예전엔 똑같은 기능도 다르게 쓰면 속도가 다른게 같은 속도로 처리되게 바뀌기도 하고...
어차피 곱셈 나눗셈은 코드로 접근하면 모두 가산기(+)를 통해 처리되어 비트 단위 덧셈과 비트 쉬프트, 오버로드 등으로 처리됨. 그 어셈블리 코드를 이해하면 적용 가능한 수준이긴 하지만.. 역시 WTF이군. 참고로 퀘이크의 존 카멕은 어쎔블러로 프로그램 하던 사람임. 어셈블러(기계어를 영문자로 치완한, 즉, 기계어와 1:1 메칭되는 언어) 물론 이후 세대부터는 컴파일 과정을 포함해서 1:1이라기는 좀 그렇게 되었지만, C나 basic, java처럼 보고 이해가기 쉽게 만들어진 언어는 아님. 간단한 C코드 Disassamble하면 장난아닌 길이의 코드가 나온다.(물론 컴파일러의 최적화와 관련 있긴하지만.)