DH2640 Grafik och Interaktionsprogrammering, 9 hp

Kursen inleds med en kort översikt över datorgrafikens och grafiska interaktionens historia. Anledningen är att dels är det viktigt att historien inte glöms bort, dels är det enklare att förstå varför datorgrafikområdet ser ut som det gör idag om man vet hur det har utvecklats.

Datorgrafikens rötter kan spåras tillbaka till 1920-talet då TVn uppfanns. Den teknik som gör att en TV fungerar låg till grund för utvecklingen av katodstrålemonitorn på sent 1950-tal, som först användes i militära sammanhang, bl.a. taktisk simulering. Ett av de mest välkända projekten hette Sage, och påbörjades redan 1954. Det var också i det militära sammanhanget som det första datorspelet byggdes. William Higinbotham presenterade ett tennis-spel som del av en öppet-hus-presentation 1958 vid Brookhaven National Laboratories (där bl.a. atombombsforskning bedrevs).

På 60-talet användes datorer för att generera kortfilmer (t.ex. i förtexterna till Hichcock's Vertigo), och 1963 presenterades det första datorbaserade ritprogrammet, Sketchpad, av Ivan Sutherland. Sedan dess har datorer och datorgrafik använts i stor utsträckning inom konstvärlden, inte enbart för bildbehandling och animation, utan också som ett kreativt verktyg.

En annan bransch som också tidigt anammade datorgrafiken var specialeffektsindustrin. George Lucas, som var en av pionjärerna, använde datorer för att skapa en 3D-visualisering i Star Wars så tidigt som 1977, och 1980 imponerade Tron med sina långa datorgenererade sekvenser. Tron var också den första långfilm där människor interagerade med datorgenererade virtuella miljöer. På mitten av 1980-talet var tekniken mogen för att skapa helt datorgenererade karaktärer (Max Headroom var ett av de tidigaste exemplen). Filmer som Terminator 2 (1991) och Jurassic Park (1993) banade väg för en helt ny industri genom att göra sig helt beroende av digitala karaktärer, och 1995 hade den första 100% datorgenererade långfilmen premiär, Toy Story.

Inom industrin är det mycket vanligt att man använder datorgrafik för visualisering och simulering. Den första flygsimulatorn byggd på datorgrafik blev klar 1967, och Pierre Bézier använde datorer för att visualisera bildelar för första gången runt 1970. På tidigt 80-tal grundlades också CAD/CAM-metodiken (Computer Aided Design / Computer Aided Manufacturing), bl.a. med stor hjälp av produkter som AutoCAD, som premiärvisades 1982. Användningen av särskild hårdvara för att effektivisera visualisering (som trackers, stereo-displayer och specialdesignade interaktionsverktyg) fick ett rejält uppsving kring mitten av 1980-talet, och den kommersiella marknaden för Virtual Reality hade en kulmen i mitten av 90-talet. Idag används datorgrafik till vardags av alla stora industrier som har nytta av simulering, t.ex. flygbolag, oljebolag, biltillverkare, brandsäkerhetsbolag, och meteorologiinstitut.

Datorgrafiken själv har också - naturligtvis - varit föremål för forskning, framför allt i USA. Efter de tidigaste militära tillämpningarna har datorgrafikforskningen kommit att bedrivas inom universitet- och högskolor. Algoritmer för linjeritning, kamerasimulering och perspektiv, borttagning av skymda ytor, bildbuffertar, skuggning, och globala belysningsmodeller har alla utvecklats av akademiker med anknytning till amerikanska universitet. 1986 kom det kanske största genombrottet inom datorgrafiken någonsin, då Jim Kajiya presenterade den s.k. renderingsekvationen, som kopplar samman en matematisk beskrivning av ljusenergi med en abstrakt modell för ytreflektion. Insikten att alla algoritmer för att generera (realistisk) datorgrafik faktiskt löser denna ekvation (eller approximationer av den), har lett till en stor mängd nya sätt att arbeta och massor av spännande algoritmer för syntes av bilder. Idag arbetar många av de mest framgångsrika datorgrafikforskarna för amerikanska storföretag som Microsoft, Pixar, nVidia, och Alias (Jim Kajiya är f.n. på Microsoft Research, t.ex.), men nya förmågor (och de viktigaste nya rönen) kommer oftast från den akademiska sektorn.

Utvecklingen av grafikhårdvara, däremot, har sedan 80-talet i första hand letts av industrin. Fram till mitten av 90-talet var kanske Silicon Graphics det främsta företaget, medan det idag finns en mängd aktörer på marknaden som ständigt pressar varandra till nya, och mer prisvärda lösningar. Man kan också säga att datorspelsindustrin har en nyckelroll, eftersom de flesta funktioner och algoritmer som utvecklas för grafikkorten är framtagna med tanke på datorspel.

Även om datorgrafik handlar mycket om 3D så ska man inte glömma att det mesta av det vi representerar på våra datorskärmar är tvådimensionellt. Dessutom är många algoritmer inom 2D-grafik direkt tillämpbara i 3D (eller kan byggas på så att de funkar där också).

I den här delen av kursen kommer vi att behandla koncept som fönster och dialogsystem, text och teckensnitt, enkla ritfunktioner och transformationer som rotation, skalning och translation. Vi kommer också att repetera en del linjär algebra. Vi kommer också att tala en del om hur datorn representerar datorgrafisk information och hur datorn bär sig åt för att flytta information mellan huvudminnet och grafikkortet. Koncept som sprites och färgpaletter kommer också att tas upp.

Det här avsnittet i kursen bygger direkt på 2D-grafikdelen.

Med bildbehandling menar man normalt processer där datorn genomför matematiska eller procedurella operationer på tvådimensionell bilddata. En bild i datorn är egentligen inget annat än en matris med värden för rött, grönt, och blått (eller analogt, tre lika stora matriser med skalärer: en för rött, en för grönt och en för blått). Det gör att det är mycket enkelt att manipulera bildinformationen. Kursen kommer att ta upp olika former av filter, som t.ex. blurring, sharpening, och edge detection, och exemplifiera hur de används i en kommersiell mjukvara, Adobe Photoshop. Kursen kommer också att ta upp olika mer avancerade tekniker för att manipulera bilder för film, reklam och konst.

Efter den inledande historieöversikten kommer kursen att ta upp vad all datorgrafik egentligen är i grund och botten: en diskretisering av kontinuerliga signaler, och ge en kort introduktion till digital signalbehandling.

Datorgrafiken handlar om att digitalt representera kontinuerliga data och att rekonstruera denna representation som en analog signal (t.ex. som ljusenergi från en datorskärm). När man ritar en linje på skärmen, t.ex., utgår man oftast från start- och slutpunktens tänkta positioner. Dessa positioner är normalt inte kopplade direkt till bildelementen på skärmen, utan lagras som flyttal. Rent matematiskt är linjen endimensionell och kan därför i praktiken inte representeras som diskreta bildelement. Således kommer inte bildelementen som tänds på skärmen att motsvara den riktiga linjen, utan en s.k. sampling (eller representation) av linjen.

Den kanske viktigaste satsen inom digital signalbehandling, Nyquists sats, säger att det krävs minst två gånger så hög upplösning i den digitala representationen som den högsta frekvensen i den signal man vill representera. I fallet med linjen så existerar ingen sådan övre gräns - det krävs en oändligt hög upplösning för att representera en endimensionell linje perfekt på en datorskärm. Det är en av anledningarna till att datorgrafiken är så känslig för aliasing, d.v.s., "trappstegseffekter" där en signal inte samplats med tillräckligt hög frekvens.

Det två vanligaste sätten att göra aliasingproblemet mindre är 1) att öka upplösningen, och 2) att försöka "byta" aliasing mot brus genom att använda filter av olika slag. Bilden till höger visar ett exempel på hur man kan reducera effekterna av aliasing i text genom att filtrera tecknen då de ritas ut.

Datorgrafik används i princip alltid i kommunikationen mellan dator och människa. Det vanligaste sättet brukar vara i form av grafiska användargränssnitt (graphical user interface eller GUI på engelska). Vi har väl alla använt oss av WIMP-gränssnitt (Windows, Icons, Menus, Pointing device) med fönster, menyer, scrollbars, knappar, pekare, etc. Men det finns massor av andra grafiska gränssnitt, och kursen kommer att ta upp några av dem, bl.a. hur man kan hantera interaktion i datorspel och virtual reality.

Efter att ha gått igenom hur grafiska gränsnitt kan se ut i allmänhet fokuserar kursen under en tid på hur man programmerar "vanliga" gränssnitt med fönster, menyer, scrollbars, etc. Vi koncentrerar oss på hur det fungerar i Java, och vi använder oss av ett paket som kallas Swing. De flesta fönstersystem fungerar så att man bygger gränssnittet hierarkiskt genom att skapa och konfigurera instanser av ett antal existerande komponentklasser, s.k. widgets. Varje widgetklass fyller en speciell funktion (t.ex. tryckknapp eller scrollbar) eller fungerar som en "låda" i vilken man kan samla andra widgetinstanser. För att få funktionalitet i gränssnittet kopplar man sedan händelselyssnare (event listeners) till sina widgets. Varje widgetinstans får ett meddelande (event) från operativsystemet då användaren aktiverat eller ändrat i instansen. Den programkod man skriver för sin lyssnare genomför sedan operationen som man tänkt ska vara kopplad till widgetinstansen.

Vi tar en närmare titt på en integrerad utvecklingsmiljö, Eclipse, som specialdesignats för att underlätta programmering av applikationer med "standardgränssnitt".

Den här delen av kursen handlar om hur man tar steget från 2D till 3D.

Det första vi kommer ta upp är hur den "tredje dimensionen" i ens figurer kan "tas bort" så att bilden kan visas i ett tvådimensionellt fönster. Här har datorgrafiken hämtat mycket från teori kring bildprojektioner, särskilt centralperspektivet som uppfanns och utvecklades av arkitekten Filippo Brunelleschi i 1400-talets Italien. En annan viktig bildprojektion som bl.a. används för 2D-tillämpningar och CAD/CAM-programvara är ortogonalprojektionen. Kursen kommer också att ge en översikt över andra typer av projektioner som förekommer.

Vi kommer också att titta närmare på transformationer av tredimensionell data, och utöka de metoder vi kommit i kontakt med i 2D-delen. Det visar sig att det för de absolut flesta tillämpningar räcker med att använda sig av affina transformationer av sin data, d.v.s. transformationer som bevarar linjer. Det gör att det i realtidsgrafik räcker med att manipulera hörnen i sina figurer och sedan dra räta linjer mellan dem. Vi kommer också att ta upp hur man kan skriva projektioner som transformationsmatriser, vilket ger ett enhetligt och smidigt sätt att kombinera transformationer och projektioner.

Den här delen av kursen handlar om kurv- och ytrepresentation, d.v.s., hur man kan beskriva två- och tredimensionell form med hjälp av matematiska formler. Av olika skäl väljer man oftast att använda parametriska polynomkurvor/ytor av tredje graden, och vi kommer att gå igenom en rad olika varianter av sådana: interpolerande, Hermite, Beziér, splines, och NURBS. Men vi kommer också att titta närmare på polygoner och Catmull-Clarkytor (som ofta också kallas subdivision surfaces).

Att kunna manipulera bilder är en viktig förutsättning för att kunna skapa ytdetaljer på 3D-modeller, s.k. texturer, men det krävs förstås också kunskaper i hur man skapar form i datorn. Att direkt hantera den matematiska representationen av kurvor och ytor är normalt alltför komplicerat. Därför kommer vi att ägna en del tid åt hur man kan skapa form med olika typer av mjukvaruverktyg.

Eftersom datorn arbetar med diskreta enheter (som vi sett i den del av kursen som behandlar signalbehandling och aliasing) måste kurvor, ytor och polygoner i slutändan översättas till grupper av pixelpunkter, d.v.s., rastreras. Den här delen av kursen handlar om hur det går till. Man har huvudsakligen två alternativ: 1) att rita kurvan eller ytan pixel för pixel, eller 2) att approximera kurvor som ett antal räta linjer och ytor som ett antal plana polygoner. Alternativ två är givetvis det absolut vanligaste inom alla applikationer som ritar grafik i realtid.

Den här delen av kursen kommer också att behandla hur man åstadkommer borttagning av skymda ytor. I 3D-sammanhang vill man normalt att de ytor som ligger närmast kameran ska skymma de ytor som ligger längre bort, och det finns en mängd olika sätt att åstadkomma detta. Vi kommer att gå igenom ett antal olika algoritmer, bl.a. painter's algorithm och z-buffering. Vi kommer också att ta en titt på klippning, d.v.s. hur man kan undvika att rita delar av linjer och polygoner som ligger utanför skärmfönstret.

Datorgrafik har i princip alltid använts för att skapa rörliga bilder. Datoranimation finns överallt; från konst, film/TV och undervisning till tillverkningsindustri och militära sammanhang. Den här delen av kursen kommer att ge en översikt över animationstekniker som scripting, inverse kinematics, morphing, fysikbaserad animation och motion capture och beskriva hur de används, framför allt med fokus på film, specialeffekter och datorspel. Vi kommer också att fördjupa oss en del i scripting genom att använda enkla animationsverktyg i Autodesk Maya.

Efter introduktionen till gränssnittsprogrammering är det dags att titta på hur man programmerar 3D-grafik för realtidsapplikationer. Det finns idag egentligen bara två alternativ för att programmera 3D-grafik "nära hårdvaran": Microsoft Direct 3D, som fungerar på PC/Windows, och OpenGL, som fungerar på i princip alla plattformar. Båda systemen är i princip ekvivalenta i funktionalitet och prestanda, men OpenGL är f.n. enklare att lära sig.

Vi kommer också att arbeta med s.k. shaders, som är små program som beskriver vad grafikkortets interna processor ska göra med hörn och pixelpunkter i bilden. Med hjälp av shaders kan man implementera en rad spännande specialeffekter och reflektionsmodeller, och shaders är den vanligaste tekniken för att skapa specifika material inom både spel- och specialeffektsindustrin. Det shaderprogramspråk vi använder är nVidia Cg.

Den här delen av kursen förutsätter det som gåtts igenom m.a.p. signalbehandling, 2D-grafik, kamerasystem och transformationer, kurvor och ytor, modellering, rastrering och animation.

Ett mycket viktigt användningsområde för datorgrafik är Visualisering av olika slag. Med visualisering menar man (oftast) att man presenterar en datamängd visuellt på ett sådant sätt att den blir enkel att förstå, eller så att intressanta fenomen som finns inneboende i data blir synliga. Det krävs förstås inte datorgrafik för att åstadkomma visualisering, men en stor fördel med att använda datorn är att visualiseringen kan göras interaktiv så att den kan manipuleras i realtid på olika sätt. Man kan också enkelt skapa nya visualiseringar och enkelt presentera sin data på många olika sätt och jämföra presentationerna.

Vi kommer att gå igenom olika grundprinciper för visualisering, och titta lite på några olika visualiseringsverktyg. Vi kommer också att prata lite om olika typer av hårdvara som utvecklats speciellt för visualisering.

Att skapa realistiska bilder av virtuella miljöer har alltid varit viktigt inom datorgrafiken. I bildsyntes är målet att skapa fotorealistiska bilder, d.v.s. man försöker beskriva ljusets interaktion med material så pass noggrant att resultatet inte går att skilja från ett riktigt fotografi.

Alla former av bildsyntes löser renderingsekvationen:

Den säger att den ljusenergi som lämnar punkten x i en viss riktning r_o är summan av mängden energi som genereras i x i den riktningen (för ljuskällor), och mängden energi som reflekteras i r_o från alla inkommande riktningar r_i.

Ekvationen är komplicerad att lösa, och vi kommer att ta en översiktlig titt på ett antal olika metoder som används idag, bl.a. ray tracing, radiosity, och photon mapping. Vi kommer också att ta en kort titt på verktyg för bildsyntes, som t.ex. Mental Ray (som finns inbygd i Maya).

De sista två delarna av kursen knyter ihop stoffet. Först kommer vi tala om vad som kännetecknar modern grafikhårdvara. Idag handlar realtidsgrafik om mycket mer än att rita polygoner på skärmen. Vi kommer bl.a. att spåna lite kring framtiden för shaders och titta närmare på ett par avancerade shaderalgoritmer. Vi kommer också att diskutera den senaste tidens utveckling av Direct 3D, som har visat sig vara särskilt intressant för spel- och realtidsgrafikindustrin.

Vi avslutar kursen med att diskutera datorspelsgrafik.

Att utveckla ett datorspel kräver en mängd olika kompetenser, inte minst inom datorgrafik. En duktig datorspelsgrafiker har en grundling kännedom om alla moment som tagits upp i kursen, men är dessutom specialiserad på ett eller ett par av dem. Vi kommer att prata om vilka komponenter som ingår i moderna datorspelsmotorer och vi kommer att titta närmare på olika grafiska lösningar i ett olika moderna spel.