0x5f3759df

Из Википедије, слободне енциклопедије
Израчунавања осветљења и рефлексија (овде приказани у пуцачини из првог лица OpenArena) користе брзи инверз квадратног корена за налажење упадног угла.

Брзи инверз квадратног корена (познат и као Fast InvSqrt() или по хексадекадној константи 0x5f3759df) је метод за рачунање x−½, мултипликативног инверза квадратног корена броја записаног у 32-битној прецизности покретног зареза у IEEE 754 формату. Алгоритам је вероватно развијен у компанији Силикон графикс почетком 1990их, а његова имплементација се јавила 1999. у изворном коду игрице Quake III Arena, али сам метод се није појавио на јавним форумима као што је Usenet све до 2002 или 2003.[1] У то време, првенствена предност алгоритма се састојала у избегавању рачунски скупих аритметичких операција у покретном зарезу, уместо којих се користе целобројне операције. Инверзни квадратни корен се користи у рачунању упадних углова и рефлексије светлости и сенки у рачунарској графици.

Алгоритам узима 32-битни број у покретном зарезу као улаз, и складишти његову половину за каснију употребу. Затим се, посматрајући битове који представљају број у покретном зарезу као 32-битни цео број, спроводи операција логичког шифтовања удесно за један бит, а резултат те операције се одузима од „магичне“ константе 0x5f3759df. Ово је прва апроксимација инверзног квадратног корена улаза. Затим се битови поново посматрају као број у покретном зарезу и спроводи се једна итерација Њутновог метода како би се добила прецизнија апроксимација. Ово рачуна апроксимацију инверза квадратног корена броја у покретном зарезу отприлике четири пута брже него коришћењем дељења бројева у покретном зарезу.

Алгоритам је првобитно приписиван Џону Кармаку, али је истраживање показало да овај код има дубље корене у хардверској и софтверској страни рачунарске графике. Прилагођавања и измене су пролазиле кроз компаније Силикон графикс и 3dfx Interactive, а имплементација Гарија Таролија за SGI Indigo представља најранију познату употребу алгоритма. Није познато како је константа првобитно откривена, мада је истраживање навело на неке могуће методе.

Мотивација[уреди]

Површинске нормале имају честу примену у израчунавањима осветљавања и сенки, што захтева израчунавање норми вектора. На слици је приказано поље вектора нормалних на површину.

Инверз квадратног корена броја у покретном зарезу се користи у рачунању нормализованог вектора.[2] Како програми који раде са 3Д графиком користе ове нормализоване векторе за одређивање осветљења и рефлексија, неопходно је извршити милионе оваквих рачунања у секунди. Пре него што је развијен специјализовани хардвер који се бави трансформацијама и осветљењем, софтверско израчунавање је могло да буде врло споро. Конкретно, када је овај алгоритам развијен раних 1990их, већина процесора је била много спорија у рачунању операција са покретним зарезом него у рачунању целобројних операција.[1]

Како би се нормализовао вектор, одређује се дужина вектора рачунањем његове еуклидске норме: квадратни корен збира квадрата координата вектора. Када се свака координата вектора подели том дужином, вектор постаје јединични вектор са истим правцем.

\|\boldsymbol{v}\| = \sqrt{v_1^2+v_2^2+v_3^2} је еуклидска норма вектора, аналогна еуклидском растојању између две тачке у еуклидском простору.
\boldsymbol{\hat{v}} = \boldsymbol{v} / \|\boldsymbol{v}\| је нормализовани (јединични) вектор. Ако се са \boldsymbol{x} представи v_1^2+v_2^2+v_3^2, добије се
\boldsymbol{\hat{v}} = \boldsymbol{v} / \sqrt{x}, што повезује јединични вектор са инверзом квадратног корена компоненти раздаљине.

Quake III Arena је користила алгоритам за брзи инверз квадратног корена како би убрзала израчунавање у графичкој процесној јединици, али овај алгоритам је у међувремену имплементиран у специјалним хардверским вертекс шејдерима који користе FPGA.[3]

Преглед кода[уреди]

Следи изворни код имплементације алгоритма за брзи инверз квадратног корена коришћен у игрици Quake III Arena, са уклоњеним C препроцесорским директивама, али са очуваним неизмењеним оригиналним коментарима:[4]

float Q_rsqrt( float number )
{
	long i;
	float x2, y;
	const float threehalfs = 1.5F;
 
	x2 = number * 0.5F;
	y = number;
	i = * ( long * ) &y; // evil floating point bit level hacking
	i = 0x5f3759df - ( i >> 1 ); // what the fuck?
	y = * ( float * ) &i;
	y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
 
	return y;
}

Како би се одредио инверз квадратног корена, полази се од апроксимације за x^{-1/2}, коју одређује софтвер, а затим се примењује нека нумеричка метода да би се апроксимација поправљала све док не дође у опсег прихватљивог одступања од тачног решења. Уобичајени софтверски методи са почетка 1990их су прву апроксимацију извлачили из предефинисаних таблица.[5] Горенаведени код се у пракси показао бржим од таблица, и отприлике четири пута бржи него кад би се користило уобичајено дељење у покретном зарезу.[6] Долазило је до извесног губитка у прецизности, али је он надомешћен значајним напретком у перформансама.[7] Алгоритам је развијен за IEEE 754-1985 32-битне бројеве у покретном зарезу, али испитивање Криса Ломонта и касније Чарлса МакЕнирија је показало да би могао да буде имплементиран и у другим форматима бројева у покретном зарезу.

Предности у брзини које пружа овај алгоритам се између осталог заснивају на „досетки“ да се 32-битни број у покретном зарезу[note 1] третира као цео број и одузме од специфичне константе, 0x5f3759df. Сврха константе није одмах јасна некоме ко прегледа код, па се стога, као и друге сличне константе које се користе у програмирању, често назива „магичним бројем“.[1][8][9][10] Ово целобројно одузимање и битовско шифтовање даје 32-битну вредност која се затим поново посматра као број у покретном зарезу, и представља грубу апроксимацију инверза квадратног корена почетног броја. Примењује се једна итерација Њутновог метода како би се добило на прецизности, и ту се код завршава. Алгоритам генерише разумно прецизне резултате користећи јединствену прву апроксимацију за Њутнов метод. Међутим, ово је знатно спорије и мање прецизно него коришћење SSE инструкције rsqrtss на x86 процесорима, која је такође објављена 1999.[11]

Напомене[уреди]

  1. ^ Коришћење типа long умањује портабилност овог кода на модерним системима. Како би се код извршавао исправно, sizeof(long) мора да буде 4 бајта, у супротном може да дође до негативних вредности у резултату. На многим модерним 64-битним системима, sizeof(long) је 8 бајтова.

Референце[уреди]

  1. ^ а б в Sommefeldt, Rys (November 29, 2006). „Origin of Quake3's Fast InvSqrt()“. Beyond3D Приступљено 12. 2. 2009.. 
  2. ^ Blinn (2003), стр. 130.
  3. ^ Middendorf, Lars; Mühlbauer, Felix; Umlauf, George; Bodba, Christophe (1. 6. 2007.). „Embedded Vertex Shader in FPGA“. In Rettberg, Achin. Embedded System Design: Topics, Techniques and Trends. IFIP TC10 Working Conference:International Embedded Systems Symposium (IESS), et al.. Irvine, California: Springer. pp. 155-164. ISBN 978-0-387-72257-3. 
  4. ^ „quake3-1.32b/code/game/q_math.c“. Quake III Arena. id Software Приступљено 15. 11. 2010.. 
  5. ^ Eberly (2001), стр. 504.
  6. ^ Lomont, Chris (February, 2003). „Fast Inverse Square Root“. p. 1 Приступљено 13. 2. 2009.. 
  7. ^ McEniry, Charles (August, 2007). „The Mathematics Behind the Fast Inverse Square Root Function Code“. p. 1 Приступљено 13. 2. 2009.. 
  8. ^ Lomont (2003), стр. 3.
  9. ^ McEniry (2007), стр. 2, 16.
  10. ^ Eberly, David (2002). Fast Inverse Square Root. Geometric Tools. pp. 2- Приступљено 22. 3. 2009. 
  11. ^ Ruskin, Elan (16. 10. 2009.). „Timing square root“. Some Assembly Required Приступљено 13. 9. 2010.. 

Литература[уреди]

Спољашње везе[уреди]