Kako je Džon Karmak redefinisao programiranje i pokrenuo revoluciju 3D grafike

Početkom devedesetih godina prošlog veka, personalni računari (PC) smatrani su mašinama za tabelarna proračunavanja, pisanje tekstova i ozbiljan kancelarijski rad. Ako ste želeli da se igrate, kupovali biste konzole poput Sega Mega Drive-a ili Nintendo Entertainment System-a (NES). PC je bio prespor, njegova grafika je bila rigidna, a hardverska arhitektura fragmentisana i neprijateljski nastrojena prema dinamičnim, brzim video-igrama.

A onda se pojavio Džon Karmak (John Carmack).

Kao suosnivač i tehnički mozak studija id Software, Karmak nije samo promenio način na koji se igre prave – on je promenio način na koji računari razmišljaju o trodimenzionalnom prostoru. Kroz seriju revolucionarnih softverskih inovacija, od glatkog skrolovanja u igri Commander Keen, preko pseudosvetova Wolfensteina 3D i Dooma, pa sve do potpunog 3D renderovanja u Quakeu, Karmak je naterao hardversku industriju da ga prati. Ovo je priča o čoveku koji je od programiranja napravio umetnost čistog inženjeringa i pokrenuo revoluciju koja i danas definiše modernu 3D grafiku.

---

Rušenje barijera na PC-ju: Od Commander Keena do Wolfensteina 3D

Pre nego što je 3D grafika uopšte bila teoretska mogućnost na kućnim računarima, najveći izazov bio je dvodimenzionalni skrolovanje (side-scrolling). Konzole poput NES-a imale su namenski hardver koji je omogućavao glatko pomeranje pozadine piksel po piksel. PC računari tog vremena, opremljeni EGA grafičkim karticama¹, morali su ponovo da iscrtavaju čitav ekran za svaki frejm, što je rezultiralo nepodnošljivim seckanjem.

Karmak je ovaj problem rešio tehnikom zvanom Adaptive Tile Refresh (prilagodljivo osvežavanje pločica). Umesto da ponovo iscrtava svih 320x200 piksela, njegov algoritam je pratio koje se "pločice" (tiles) na ekranu zapravo menjaju kako se igrač kreće, i osvežavao samo njih. Ostatak ekrana je jednostavno pomeran u memoriji grafičke kartice koristeći hardverske registre.

Kada su Karmak i Džon Romero (John Romero) kreirali savršenu repliku prvog nivoa legendarne igre Super Mario Bros. 3 na PC-ju, Nintendo je bio zapanjen, ali je odbio saradnju. To ih nije pokolebalo: iskoristili su ovu tehnologiju da stvore Commander Keen (1990), dokazavši svetu da PC može da se takmiči sa konzolama.

Rađanje pseudo-3D sveta: Wolfenstein 3D

Sledeći korak bio je prelazak u treću dimenziju, ali hardver iz 1992. godine (uglavnom procesori Intel 286 i rani 386) nije bio ni blizu dovoljno brz da procesira prave 3D poligone. Karmak je stoga primenio tehniku zvanu Raycasting (projekcija zraka).

U Wolfensteinu 3D, svet nije bio trodimenzionalan. Mapu je predstavljao jednostavan dvodimenzionalni raster (mreža). Za svaki vertikalni piksel na ekranu, motor igre je "ispaljivao" zrak iz ugla gledanja igrača dok ne udari u zid. Na osnovu udaljenosti do zida, algoritam je skalirao i iscrtavao vertikalnu kolonu teksture.

Ova matematika je bila toliko brza da je omogućila glatkih 30 frejmova u sekundi na prosečnom hardveru tog vremena. Ipak, igra je imala striktna ograničenja: svi zidovi su morali biti pod pravim uglom od 90 stepeni, a podovi i plafoni su bili jednobojni, bez tekstura.

---

Doom i revolucija BSP stabala

Dok je Wolfenstein 3D bio vizuelno impresivan, njegovi ortogonalni zidovi i ravan teren brzo su postali monotoni. Karmak je želeo svet sa promenljivim visinama, kosim zidovima, dinamičkim osvetljenjem i teksturisanim podovima. Rezultat je bio Doom (1993), igra koja je redefinisala pop-kulturu i tehnologiju.

Da bi postigao ovaj nivo kompleksnosti bez žrtvovanja performansi na procesorima klase Intel 486, Karmak je morao da reši problem sortiranja vidljivosti. U 3D prostoru, najteži zadatak za procesor je da odluči koje objekte treba iscrtati ispred, a koje iza drugih (kako se ne bi trošilo vreme na iscrtavanje nečega što je zaklonjeno zidom).

Rešenje je pronašao u akademskom radu o BSP stablima (Binary Space Partitioning)².

Kako funkcioniše BSP u Doomu?

BSP algoritam deli dvodimenzionalnu mapu na pola, pa te polovine ponovo na pola, kreirajući binarno stablo. Kada se igrač kreće kroz nivo, igra prolazi kroz ovo stablo kako bi odredila tačan redosled iscrtavanja zidova od najbližeg ka najudaljenijem.

1. Podela prostora: Mapa se preprocesira i deli na sektore.
2. Sortiranje: Tokom igranja, položaj igrača određuje koje grane stabla su ispred njega.
3. Sprečavanje prepisivanja (Overdraw): Zidovi se iscrtavaju od napred prema nazad. Jednom iscrtani pikseli se "zaključavaju" u horizontalnom nizu, tako da se udaljeniji zidovi koji su iza njih uopšte ne procesiraju.

Ova matematička elegancija omogućila je Doomu da renderuje kompleksne lavirinte sa stotinama neprijatelja, treperavim svetlima i visinskim razlikama u realnom vremenu, bez potrebe za namenskim grafičkim čipom.

---

Quake, pravi 3D i rođenje modernog hardverskog ubrzanja

Godine 1996. svetlo dana ugledao je Quake. Ako je Doom bio pseudo-3D (gde su neprijatelji i predmeti i dalje bili dvodimenzionalni crteži – sprajtovi), Quake je bio apsolutni, beskompromisni 3D. Sve u igri – od arhitekture nivoa do samih neprijatelja i njihovog oružja – bilo je sastavljeno od poligona.

Ovo je bio ogroman tehnički rizik. Procesiranje pravih 3D koordinata u realnom vremenu zahtevalo je toliko matematičkih proračuna u pokretnom zarezu (floating-point math) da je igra praktično zahtevala Intel Pentium procesor sa integrisanim matematičkim koprocesorom (FPU).

Tabela: Tehnološki skok kroz ključne mašine id Software-a

Lightmaps i spasavanje CPU-a

Pored prelaska na poligone, Quake je doneo i revolucionarni sistem osvetljenja. Računanje realističnih senki i svetlosti u realnom vremenu bilo je nemoguće za tadašnje procesore. Karmak je osmislio tehniku zvanu Lightmaps (mape svetlosti).

Svetlosni efekti su računati unapred (tokom kreiranja mape) i čuvani kao male, crno-bele teksture niske rezolucije koje su se preklapale preko originalnih tekstura zidova tokom renderovanja. Rezultat je bio neverovatno atmosferski svet sa mekim senkama, koji je radio glatko jer procesor nije morao da računa fiziku svetlosti u svakom frejmu.

glQuake i revolucija 3D kartica

U vreme izlaska Quake-a, na tržištu su počeli da se pojavljuju prvi "3D akceleratori" – preteče današnjih grafičkih kartica. Najpoznatiji među njima bio je 3dfx Voodoo.

Karmak je prepoznao potencijal ovog hardvera i napisao glQuake, verziju igre koja je koristila industrijski standard OpenGL za komunikaciju sa grafičkim čipom. Kada su igrači videli glQuake – sa savršeno filtriranim teksturama, fluidnim frejmrejtom i svetlosnim efektima u boji – industrija se promenila preko noći. Kupovina 3D kartice postala je obavezna za svakog gejmera. Džon Karmak je, praktično samostalno, naterao industriju hardvera da ubrza razvoj GPU-ova.

"U istoriji računarstva postoji samo nekoliko ljudi čiji je rad direktno uticao na živote miliona korisnika i kreirao čitave industrije. Džon Karmak je jedan od njih. Njegov kod je bio zakon gravitacije za trodimenzionalni prostor na PC-ju."
— Michael Abrash, legendarni programer i Karmakov bliski saradnik na Quake engine-u

---

Koderska elegancija: Brzi inverzni kvadratni koren

Jedan od najfascinantnijih detalja vezanih za Karmakovo ime (iako istorijski netačno pripisan isključivo njemu, on ga je popularizovao i optimizovao u kodu za Quake III Arena) jeste algoritam za brzi inverzni kvadratni koren (Fast Inverse Square Root).

U 3D grafici, proračuni vektora (poput refleksije svetlosti ili fizike kretanja) zahtevaju normalizaciju vektora, što podrazumeva deljenje sa kvadratnim korenom. Tradicionalna operacija deljenja i korenovanja na tadašnjim procesorima bila je izuzetno skupa i spora.

Algoritam koristi neverovatnu matematičku prečicu u načinu na koji računari čuvaju brojeve sa pokretnim zarezom (IEEE 754 standard).

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // Zli bit-level hak
    i  = 0x5f3759df - ( i >> 1 );               // Šta se dođavola ovde dešava?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // Prva iteracija Njutnove metode
    // y  = y * ( threehalfs - ( x2 * y * y ) ); // Druga iteracija, može se izostaviti

    return y;
}

Ovaj kod koristi "magični broj" `0x5f3759df` da bi direktno procenio inverzni kvadratni koren sa zapanjujućom preciznošću, a zatim koristi jednu iteraciju Njutn-Rafsonove metode da dodatno poboljša rezultat. Ova prečica radila je i do četiri puta brže od standardne funkcije, omogućavajući kompleksnu fiziku i osvetljenje u Quake III Arena bez opterećenja procesora.

---

Filozofija otvorenog koda i zaveštanje

Džon Karmak nije bio samo tehnički genije; on je bio i strastveni zagovornik otvorenog koda (open-source). Redovno je, nakon nekoliko godina od izlaska igara, objavljivao kompletan izvorni kod svojih endžina (engine) pod GPL licencom.

Ovaj potez omogućio je generacijama mladih programera širom sveta da uče od najboljeg. Mnogi današnji lideri u industriji video-igara i softverskog inženjeringa započeli su karijeru analizirajući i modifikujući kod Dooma i Quakea.

Njegov uticaj prevazilazi same video-igre. Tehnologije koje je on razvio ili popularizovao – od progresivnog učitavanja tekstura (MegaTexture) do optimizacije latencije – postavile su temelje za modernu virtuelnu realnost (VR), gde je Karmak godinama radio kao CTO kompanije Oculus (kasnije Meta).

Danas, kada igramo najmodernije naslove sa fotorealističnom grafikom i ray-tracing efektima na moćnim konzolama i PC mašinama, često zaboravljamo da ispod haube kuca srce tehnologije koju je pre više od tri decenije, u maloj kancelariji u Teksasu, osmislio čovek koji je jednostavno želeo da natera računar da crta brže. Džon Karmak nije samo redefinisao programiranje – on nam je pokazao kako izgleda kada se čista logika pretvori u magiju.

---