Wavelets in 3D-graphics

Terminologie

Voor de doeleinden van dit artikel bestaat een textuur uit een 32-bit afbeelding, $2^n$ texels breed en $2^n$ texels hoog. Een "texel" is een industrieterm voor een pixel van de textuur voordat deze op het scherm wordt geprojecteerd. Voor elke afbeelding worden ook mipmaps opgeslagen. Elke mipmap is een macht van twee kleiner dan de vorige en wordt gegenereerd door anti-aliasing van de voorgaande afbeelding. De mipmap-set voor een textuur van $128\times128$ zou dus bestaan uit $64\times64$, $32\times32$, $16\times16$, $8\times8$, $4\times4$, $2\times2$ en $1\times1$.

Doorgaans zijn de onderste 3 of 4 mipmap-niveaus meer moeite om te onderhouden dan ze waard zijn en worden ze vaak weggelaten; voor een game kan men de scène vaak zo inrichten dat polygonen die zo ver weg zijn niet zichtbaar zijn. Als ze wel zichtbaar zijn, heb je waarschijnlijk grotere problemen met het enorme aantal kleine polygonen dat geprojecteerd en weergegeven moet worden dan met een klein aliasing-probleem in de verte. Het opslaan van mipmaps verhoogt de opslagvereisten voor texturen met 1/3.

Het Probleem

Een typische textuurgrootte is $256\times256$. Bij 4 bytes per texel verbruikt deze enkele afbeelding 256 KB RAM per textuur. In een praktische scène zijn ongeveer een dozijn texturen tegelijk zichtbaar, en tot honderd verspreid over de kaart op plaatsen waar ze niet direct zichtbaar zijn. Om alles constant geladen te houden, zou ongeveer 200 MB aan geheugen nodig zijn, enkel voor de textuur- en mipmapdata, nog afgezien van game-logica, lightmapping of geometrie. Uiteraard is het onredelijk om zoveel geheugen te verwachten van de computer van een typische eindgebruiker in deze tijd.

Mogelijke Oplossingen

Een oplossing is om de afbeeldingen te reduceren tot 8-bits gepalettiseerde weergaven. Dit brengt de geheugenvereisten terug naar ongeveer 50 MB, wat redelijk kan worden gewisseld tussen schijf en geheugen als men gebruik kan maken van coherentie in de manier waarop texturen over de kaart zijn verdeeld. Echter, als men geen gebruik kan maken van ruimtelijke coherentie of caching, ontstaat er een "stutter" (hapering) door de plotselinge vertraging bij het opvragen van de textuur om het renderen voort te kunnen zetten.

Deze hapering heeft een zeer negatief psychologisch effect; als speler word je er plotseling aan herinnerd dat je een game speelt en het gevoel van immersie verdwijnt. Consistentie in de framerate is over het algemeen belangrijker dan de best-case prestaties, dus is er een factor nodig die de prestaties egaliseert. De hapering wordt verergerd door het feit dat de engine voor het wisselen van texturen naar de schijf moet kijken, wat verschillende ordes van grootte langzamer is dan directe toegang tot het geheugen. Daarnaast vereist een gepalettiseerde weergave van texturen een kleiner subset van de kleurenruimte, waardoor er veel kwaliteit verloren gaat bij de conversie. Zelfs na reconstructie, bij gebruik van een standaard palet met zes-bits kleurcomponenten, is de gereconstrueerde texel in het beste geval 18 bits. Er doen zich andere complicaties voor wanneer men een alpha-kanaal (translucentie) wil opslaan in een gepalettiseerde weergave.

Een andere optie is om een gecomprimeerde weergave van de textuur in het geheugen op te slaan en de mipmaps daaruit af te leiden. Het probleem met deze benadering is dat je de volledige textuur moet decompresseren en vervolgens alle mipmap-niveaus moet extraheren, zelfs als je alleen de $32\times32$ mipmap nodig had van een $256\times256$ textuur. Meestal heb je de lagere mipmaps nodig voordat de grotere mipmaps nodig zijn voor een bepaalde textuur. Dit is intuïtief, want terwijl je door een scène loopt, komen oppervlakken in de verte in beeld en komen ze dichterbij. Naarmate ze naderen, hebben ze geleidelijk meer detail nodig (hogere mipmap-niveaus). Bij deze benadering moet je de volledige klap in één keer opvangen, wat wederom haperingen introduceert.

Compressie in JPEG-stijl kan effectief worden ingezet en biedt doorgaans een hogere compressieratio dan de onderstaande methode. Helaas maakt het "alles-of-niets"-karakter het ongeschikt voor mijn behoeften. Bovendien gaat betere compressie ten koste van het uitvoeren van de inverse DCT op elk $8\times8$ blok van de afbeelding. Dit proces vereist 54 vermenigvuldigingen, 462 optellingen en 6 shifts per kanaal via de methode van Feig, wat momenteel de meest efficiënte gepubliceerde methode is voor Intel-processoren. Ter vergelijking: hetzelfde $8\times8$ blok decomprimeert met 256 optellingen per kanaal met behulp van Haar.

Een overzicht van de Haar-basis

Dit is bedoeld om een intuïtief begrip te geven van hoe de Haar-basis werkt. Het is niet bedoeld als een strikt wiskundig bewijs of onderzoek.

Gegeven $2^n$ samples, zoals: { 11, 1, 1, 7 }

1. Koppel samples en bereken het gemiddelde: { (11+1)/2, (1+7)/2 } = { 6, 4 }
2. Herhaal dit tot je één waarde overhoudt: { (6+4)/2 } = { 5 }

De waarde aan de top van deze boom is je schalingswaarde.

Vervolgens recurseer je terug naar beneden via de hiërarchie die je hebt gekoppeld. Op elk niveau trek je de waarde in het rechterkind van de huidige node af van de waarde in de huidige node. Recurseer niet in de bladeren van de boom.

Er zijn $2^n$ waarden op een bepaald niveau van de boom. Deze waarden zijn je wavelet-coëfficiënten. Met deze waarden kun je de oorspronkelijke sample-set reconstrueren, aangezien deze operatie omkeerbaar is.

Er zijn $2^m$ coëfficiënten op het $m$-de niveau van de hiërarchie. Door de schalingswaarde aan deze set toe te voegen, krijg je hetzelfde aantal waarden als in de oorspronkelijke dataset. Echter, wanneer dit is omgezet naar Haar-vorm, geven de getallen nu de veranderingen ten opzichte van het kleinere niveau aan.

Reconstructie is eenvoudig. Begin met de schalingswaarde en de coëfficiënt voor niveau 0. Tel de coëfficiënt op bij de schalingswaarde om het linkerkind te genereren, en trek deze af van de schalingswaarde om het rechterkind te genereren. Neem deze nodes en herhaal dit naar beneden in de boom:

• Links: Optellen
• Rechts: Aftrekken

Vervolgens weeg je de coëfficiënten op basis van hun niveau in de boom. Dit wordt gedaan om de coëfficiënten te normaliseren. Er zijn verschillende populaire wegingsmechanismen, elk geldig voor verschillende toepassingen. Ik geef de voorkeur aan normalisatie door elke waarde te vermenigvuldigen met $1/\sqrt{2^j}$, waarbij $j$ het niveau van de coëfficiënt in de boom is.

Je data bestaat nu uit:

• De schalingswaarde: { 6 }
• De wavelet-coëfficiënten: { 1, 5, -3 }
• De gewogen wavelet-coëfficiënten: { 1, 5/sqrt(2), -3/sqrt(2) }

Tot nu toe heeft dit proces niet geleid tot compressie. De volledige transformatie heeft simpelweg vier waarden omgezet in vier andere waarden en enkele gewogen waarden die daaruit zijn afgeleid.

Haar Toepassen

De volgende stap is bepalen hoe dit kan worden toegepast op beeldcompressie. Een afbeelding is een tweedimensionaal raster van samples, niet een eendimensionale set.

Er zijn twee gangbare benaderingen:

1. Standaard decompositie: Hierbij wordt de Haar-transformatie op elke rij uitgevoerd, waarna kolom voor kolom elke kolom op zijn beurt wordt getransformeerd. Dit is helaas niet erg nuttig voor het reconstrueren van mipmaps. Om een $2\times2$ mipmap te extraheren, zou ik de volledige afbeelding moeten reconstrueren en vervolgens via anti-aliasing terug naar $2\times2$ moeten gaan. In dat geval zou er geen voordeel zijn bij het reconstrueren van de lagere mipmaps.

1. Niet-standaard decompositie: Hierbij wordt één niveau naar beneden getransformeerd voor elke rij, en vervolgens één niveau naar beneden voor elke kolom. Dit wordt herhaald tot alleen de schalingsfunctie overblijft. Intuïtief gezien kun je zo een $2\times2$ mipmap extraheren uit de $1\times1$ mipmap (de schalingscoëfficiënt) en de set coëfficiënten voor niveau 0 (één rij-coëfficiënt en twee kolom-coëfficiënten). Vervolgens kun je de $4\times4$ mipmap extraheren uit de $2\times2$ met behulp van de mipmap en de coëfficiënten voor niveau 1 (2 rij-coëfficiënten, 4 kolom-coëfficiënten), enzovoort.

Dit stelt je in staat om de afbeelding incrementeel te reconstrueren naarmate je in de game dichter bij het oppervlak komt. Omdat je plotselinge enorme hoeveelheden data vermijdt, kun je haperingen voorkomen. Als je gedwongen wordt te wachten op een hogere mipmap in één frame van de animatie omdat er onvoldoende processortijd was om deze te decompresseren, kun je het lagere mipmap-niveau tijdelijk als vervanger gebruiken. In de praktijk heb ik gemerkt dat het beter is om een constante refresh rate van 25 frames per seconde aan te houden, dan om af en toe te zakken naar 5 omdat er geen textuur klaarstond.

Ik heb gekozen voor de niet-standaard decompositie. Tot nu toe hebben we echter alleen één set getallen voor een andere geruild; er is geen compressie opgetreden, tenzij je meetelt dat we geen extra geheugen voor de mipmap-niveaus hoeven op te slaan, aangezien deze kunnen worden afgeleid tijdens de reconstructie.

De volgende stap is het comprimeren van de coëfficiëntenset. Een voordeel van wavelets is dat een kleine wijziging in de coëfficiëntenset een vergelijkbaar kleine wijziging in de herstelde sampleset veroorzaakt, en dat deze fout netjes over de afbeelding wordt verdeeld, waardoor zichtbare discontinuïteiten als gevolg van deze fout worden vermeden.

Zodra ze correct gewogen zijn op basis van hun niveau in de boom, kun je termen elimineren die niet veel bijdragen aan het totale beeld door herhaaldelijk de kleinste gewogen coëfficiënt weg te gooien (te vervangen door 0), totdat een vooraf bepaald aantal coëfficiënten is verwijderd of een maximale weging is bereikt. Deze heuristiek is zeer nuttig gebleken, aangezien sommige afbeeldingen inherent vergevingsgezinder zijn voor compressie dan andere. Hierdoor ben ik (met tegenzin) de compressiefase gaan inrichten als een interactief proces, maar als gevolg daarvan biedt het ook meer artistieke controle.

Het vervangen van coëfficiënten door 0 is een goede systematische manier om een begrensde maximale fout te bieden. Helaas bleek dit niet te resulteren in een zeer goed comprimeerbare dataset. Kwantisering van de resterende coëfficiënten was noodzakelijk. Na de stap van 0-vervanging haal ik de set coëfficiënten door een neuraal netwerk dat de resterende coëfficiënten kwantiseert met behulp van hun gewogen vorm. Let op: in plaats van elke coëfficiënt gelijk te tellen, weeg ik mijn selectie op basis van het gewicht van de wavelet-coëfficiënt. Bij het opslaan op schijf gebruik ik echter de ongewogen vorm. In de praktijk heb ik een hogere redundantie gevonden in waarde dan in exact gewicht, en in mijn geval bood het opslaan van de gekwantiseerde waarde ongewogen een betere compressieratio.

Het gebruik van een neuraal netwerk voor kwantisering naar een 'palet' van coëfficiënten lijkt misschien overbodig, maar ik had de routines om naar een gepalettiseerde textuur te converteren al geschreven. Daarna stuur ik de kleinere set gekwantiseerde coëfficiënten en frequentietellers door een Huffman-boom generator, waarna ik de data door een Huffman-compressor haal. Aangezien dit alles een pre-process is, is de procestijd nagenoeg irrelevant, behalve dat het wijzigingen aan de game-engine tediouser maakt. Ik kon iets betere compressie bereiken door de kwantiseringsfase over te slaan en de coëfficiënten direct in een QM-arithmetische coder te voeren, maar de decompressiesnelheid leed hieronder enorm. In mijn ogen was het niet de moeite waard om zes keer langer te decompresseren en te maken met patenten van IBM voor een verbetering van 3% in compressie.

Aan de negatieve kant hebben gecomprimeerde texturen de complexiteit van mijn surface caching-algoritme drastisch verhoogd, wat grootschalige wijzigingen aan de game-engine aanzienlijk moeilijker maakt. Ook heb ik veel meer tijd besteed aan de compressie-pipeline dan ik had gewild. Achteraf had ik waarschijnlijk beter af geweest door zlib of een andere uitgebreid geteste bibliotheek te gebruiken voor de uiteindelijke compressiefase.

Het enige echte probleem doet zich voor bij texturen met een hoog contrast. Gelukkig worden deze in polygonale engines meestal strikt vermeden, omdat dezelfde algemene compressie-artefacten die optreden bij wavelets ook zichtbaar zijn bij het mipmappen van de textuur. Deze artefacten kunnen worden vermeden door anisotrope texture-sampling en andere technieken, maar op het moment van schrijven zijn deze niet snel genoeg voor realtime graphics en dus niet relevant. Compressie resulteert ook in een merkbare toename van de "blokvorming" van de textuur, proportioneel aan hoe hoog je de foutdrempel instelt. Deze blokvorming zou kunnen worden verzacht door een bilineaire filterstap toe te voegen, maar dit zou de problemen met texturen met hoog contrast vergroten. Bilineair filteren is bovendien niet echt nodig wanneer de textuur wordt doorgegeven aan een high-end 3D-acceleratorkaart die dit automatisch kan doen.

Als vuistregel vertoonden texturen geen artefacten tot een compressie van 8:1 en werden ze onbruikbaar naarmate ik de 35:1 naderde. De bruikbaarheid van de niveaus daartussen hing grotendeels af van het contrast over het grootste deel van de textuur. De compressor ging goed om met texturen die een mix van hoge en lage contrastgebieden hadden. De gebieden met hoog contrast behielden voldoende definitie omdat harde kleurveranderingen relatief hoge gewichten kregen, terwijl de gebieden met laag contrast simpelweg verder werden gedempt. Het effect hiervan is dat borden aan de muur, technische gadgets, etc., opvallen tegen een achtergrond met een lagere frequentie van verandering.

Er wordt veel onderzoek gedaan naar wavelets. De Haar-basis is eigenlijk helemaal geen goede wavelet-basis. Hij is "lelijk" vanwege de discontinuïteit (het is effectief een hiërarchie van pulsen), maar zijn belangrijkste voordelen zijn dat hij het snelst te extraheren is uit een afbeelding, het snelst is om een afbeelding uit te genereren en dat hij vrij intuïtief is, in tegenstelling tot veel geavanceerdere wavelets.

Tijdens mijn werk aan de game-engine heb ik verschillende andere manieren onderzocht om wavelets voor mij te laten werken. Er bestaan diverse basisfuncties voor het comprimeren van oppervlakken met een zeer hoog polygoonaantal. In de praktijk weegt de tijd die nodig is om door de hiërarchie te lopen en een redelijk niveau van surface data caching te beheren echter zwaarder dan de opslagvereisten van het vooraf berekenen van de beste tessellatie voor een bepaalde afstand. Uiteindelijk zal iets in die richting vereist zijn, maar op dit moment is er meer geheugen beschikbaar dan rekenkracht. Op dat vlak bleken wavelets een beetje een teleurstelling.

Referenties

• E. Stollnitz, T. Derose, D. Salesin. "Wavelets for Computer Graphics", ISBN 1-55860-375-1 Morgan Kaufmann Publishers Inc. San Francisco, CA 1996
• W. Pennebaker, J. Mitchell. "JPEG: Still Image Data Compression Standard", ISBN 0-442-01272-1 Van Nostrand Reinhold Inc. New York, NY 1993
• D. Morgan. "Numerical Methods for DSP in C", ISBN 0-471-12232-2 Jon Wiley & Sons Inc. Canada 1997
• B. Hubbard. "The World According to Wavelets", ISBN 1-56881-047-4 AK Peters Ltd. Welleskey, MA 1996
• Foley, van Dam, Feiner, Hughes, "Computer Graphics: Principles and Practice, 2nd Ed. in C" ISBN 0-201-84840-6 Addison-Wesley Publishing Co. Reading, MA 1996