Jeffrey Cross
Jeffrey Cross

Quake'i kiire pöördvõrdeline ruutjuur

Pöördnurga funktsiooni (1 / sqrt (x)) kasutatakse mängumootori tõmbesilmus, et normaliseerida vektorid “ühik” vektoriteks, mille pikkus on 1. Normaliseeritud vektorid on olulised, sest kui te võtate kahe toote punkttoote neid (Ax * Bx + Ay * By + Az * Bz), on tulemuseks kahe vektori vahelise nurga kosinus.

Nii et kujutage ette, et teil on vektor, mis kirjeldab, kuidas pind on silmitsi (selle pinna normaalne) ja teine ​​vektor, mis kirjeldab päikesevalguse suunda. Kui päikesevalgusvektor on paralleelne sinu pinnaga, see tähendab, et pind on päikese poole, on kahe normaliseeritud vektori punkttoode 0, mis on 1. Kui pind on päikesest 90 kraadi, dot-toode on 90-i kosinus, mis on 0. Mis tahes vahel ja sa saad väärtuse vahemikus 0 kuni 1, mis sisuliselt võimaldab teil kirjeldada, kuidas heledalt peaksite seda pinda valgustama.

Nüüd käivitate selle arvutuse iga 3D-mängus nähtava kolmnurga kohta ja teete kõik, mis on 30 või enam korda sekundis, ja teil on punkt-allika valguse põhiefekt! Tuletame siiski meelde, et vajate seda pöördvõrdelise ruutjuure funktsiooni, et arvutada iga kolmnurga ühikvektoreid. Ruutjuure operatsioon on aeglane. Kas see on tuhandeid kordi tõmbesilmus ja sul on aeglane mäng.

Aga kui te ei pahanda, et visata marginaalset täpsust, on kiirem viis.

Seal on pöördvõrdeline ruutjuure funktsioon, mida paljud mängumootorid kasutavad Nvidia programmeerija Gary Tarolli poolt Quake III-st pärineva kuulsusega. See näeb välja selline:

float InvSqrt (float x) {float xhalf = 0.5f * x; int i = * (int *) & x; // saada bitti ujuva väärtuse i = 0x5f3759df - (i >> 1) jaoks; // annab esialgse arvutuse y0 x = * (float *) & i; // teisendada bitid tagasi ujumiseks x = x * (1.5f-xhalf * x * x); // Newtoni samm, kordamine suurendab täpsust tagasi x; }

Hoia, mis see oli?!?!

Nii et tagasi, kui Newton tulid välja nutika viisiga pöördvõrdelise ruutjuure ühtlustamiseks. Esiteks jagate algse arvu x kahega. Võimaldab seda nimetada "xhalf". Seejärel teete suhteliselt lähedase oletuse pööratud ruutjuurele. Kutsume seda g. Seejärel võtate need kaks muutujat ja teete seda arvutust (mida tunned InvSqrti funktsiooni viimase sammuna):

g = g * (1,5 - xhalf * g * g)

Kui teete seda ikka ja jälle, asendab iga iteratsiooni värskendatud g-ga g kiiresti x pöördvõrdelise ruutjuure! Tegelikult, kui valite korraliku g, et alustada, annab üks või kaks iteratsiooni õige väärtuse lähedale.

Küsimus on selles, kuidas sa leiad, et esimene g? Mängumootori kooderid kasutavad trikke sellega, kuidas ujuva punkti numbrid on esindatud binaarsel kujul, kusjuures eksponent ja mantissa purunevad sarnaselt teaduslikule märgistusele. 32-bitises ujukis on vasakpoolne bitt märkbitt ja positiivsete numbrite puhul 0. Sellele järgneb 8 bitti eksponenti (negatiivne ja positiivne eksponent esindab 127) ja viimased 23 bitti esindavad mantissat.

Pöördnurga juurte tegemiseks peate põhimõtteliselt eksponenti korrutama -1/2-ga. Kui liigutate neid bitte paremale (väga kiire toiming), on mõju eksponendile selle jagamine 2-ga. Peate siiski märkima 0-st, et muuta selle märgi muutmiseks, ja mida sa teed mantissat, mida mõjutas ka bittide vahetamise operatsioon?

See on koht, kus saabub maagiline 0x5f3759df number. See on absoluutselt naljakas, kuid lahutades bitti nihke tulemuse 0x5f3759df-st, lähtestatakse mantissa algsele olekule ja eksponent lahutatakse 0-st (võttes arvesse selle kalduvust 127) .

Tulemuseks on pöördvõrdeline ruutjuur. Piisav, et ühe Newtoni võrrandi läbisõit lõppeks praktilise otstarbega piisavalt täpse väärtusega.

Quake'i kiire inverteeritud ruudu juure kiire inverteeritud ruudujuur - üksikasjad ja matemaatika maagilise numbri taga (PDF)

Osa

Jätnud Kommentaari