3Dc
3Dc (FourCC : ATI2), poznata kao i DXN, BC5, ili Block Compression 5 je algoritam kompresije sa gubitkom podataka za normalne mape napravljen i prvo implementiran od strane ATI[1]. Oslanja se na raniji DXT5 algoritam i to je otvoren standard.3Dc je sada implementiran od strane ATI[1] i Nvidia[2] je jedan od najvećih svetskih proizvođača grafičkih čipova za lične računare i Xbox.
Ciljna aplikacija
urediCiljna aplikacija, normalno mapiranje, je ekstenzija bamp mapiranja koja simulira osvetljenje geometriskih povrsina tako što čita površine normala sa provoliniskih mreža koji su analogni teksturnim mapama - dajući jednostavnim modelima impresiju povećane kompleksnosti. Ovaj dodatni kanal povećava učitavanje protoka grafičkim memoriskim sistemima. Pre postojanja algoritama sa gubitkom podataka implementiranim na korisničkom hardveru imali smo manjak preciznosti neophodnu za reprodukciju normalnih mapa bez prekomernih vidljivih artefakta, pravdajući razvoj 3Dc.
Algoritam
urediNormale površine su trodimenzionalni vektori, jedinične vrednosti. Zato sto je dužina konstantna samo dva elementa jedne normale moraju biti sortirana. I zbog toga je ulaz samo niz od samo dvodimenzionalnih elemenata.
Kompresija se izvodi na 4h4 blokovima. U svakom bloku, dve komponente svake vrednosti su kompresovane pojedinačno. Za svaki blok, svaka od dve komponente ima paletu od osam vrednosti. Palete su generisane od dve vrednosti koje predstavljaju početak i kraj prave, ostale šest vrednosti su generisane kao linearna kombinacija početka i kraja prave.
Kompresija je izvorno postignuta pronalaženjem najmanje i najveće vrednosti od 16 piksela, koje su kompresovane i sortirane u 8-bitnim količinama. Individualni elementi u 4h4 blokovima se čuvaju u 3-bita pojedinačno, predstavljajući njihovu poziciju na osmo stepenoj linearnj skali. Svaka 3-bitna vrednost piksela biće izabrana od minimalne distance od originalne vrednosti.
Ukupno čuvanje je 128-bita po 4h4 bloku, kad dva izvora budu faktorisana. U ne kompresovanoj šemi sa 8-bitnoj preciznošću, izvor podataka je 32 8-bitne vrednosti za istu oblast, zauzimaju ći 256 bita. Tada algoritam pravi kompresiju razmere 2:1.
Razmera kompresije na početku je 4:1 jer je uobičajno da se koristi 16-bitna preciznost za ulazne podatke nego 8-bitna.
3Dc+
uredi3Dc+ (FourCC: ATI1) (poznata kao BC4 ili Block Compression 4) može da kompresuje teksture tj. lake mape, mape senki, HDR teksture i svojstva materijala.3Dc+ omogućava 2:1 odnos kompresije sa jednom komponentom 8-bitne celobrojne teksture i 4:1 odnos kompresije sa normalnim mapama i sa teksturama koje se sastoje od dve 8-bitne celobrojne komponente.
Reference
urediLiteratura
uredi- Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, knjigu možete pogledati ovde Arhivirano na sajtu Wayback Machine (18. oktobar 2016)
- Algoritmi i strukture podataka - Milo Tomašević