Fast and High-Quality Visibility Determination

Sammanfattning: Popular Abstract in Swedish Datorgenererade bilder är en viktig del av underhållningsindustrin, som bland annat innefattar spel- och filmindustrin. För att kunna skapa avancerade specialeffekter i filmer samt stora och detaljerade spelvärldar krävs datorprogram som utnyttjar beräkningskraften i dagens datorer på ett effektivt sätt. Bättre och snabbare datorprogram leder ofta till nya användarupplevelser som tidigare inte var möjliga. Även industrier utanför underhållningsbranschen använder sig av avancerad visualisering. Inom medicin kan röntgenbilder presenteras tredimensionellt för effektiv diagnostisering av sjukdomar och arkitekter kan låta sina klienter gå en virtuell tur i byggnader som ännu inte är färdigbyggda. För att generera en bild från en tredimensionell scen krävs en modell att utföra beräkningar på. Vanligtvis består modellen av geometriska former (exempelvis trianglar), ljuskällor och en kamera. Dessa är i regel utplacerade i ett modelleringsverktyg som fungerar som ett ritprogram med en extra dimension. De geometriska formerna har en beskrivning av sin yta som bestämmer hur ljus interagerar med den. En diffus yta sprider ljus jämnt åt alla håll vid en träff och en spegel reflekterar alla strålar till en viss vinkel baserat på vinkeln mellan ljuset och ytan, för att nämna några exempel. För att skapa en bild från kamerans synfält behöver en simulering genomföras där virtuellt ljus propagerar från ljuskällorna i modellen, träffa geometrin i ett eller flera studs och slutligen hamnar på kamerans sensor. För att göra processen snabbare kan strålar istället skickas från kameran. Strålarna håller då reda på var på sensorn de utgick ifrån och varje studs kan påverka sensorn på den ursprungliga platsen. Alternativt kan geometrin direkt projiceras till kamerans bildplan, vilket är vanligt i realtidsapplikationer som spel. Dessa tekniker har olika för- och nackdelar i form av prestanda och vilka ljuseffekter de kan fånga. En av de mest fundamentala operationerna när en bild ska genereras är att bestämma vad som är framför en bildpunkt på kamerasensorn eller vad som är framför en virtuell ljusstråle. Vi kallar dessa operationer för synlighetsberäkningar. Mycket forskning fokuserar på detta område men utvecklingen som har lett fram till dagens moderna datorer har samtidigt skapat nya utmaningar. Beräkningskraften har ökat mycket medan tiden det tar att läsa och skriva data från arbetsminnet inte har minskat lika snabbt. Vidare kan beräkningskraften inte utnyttjas till fullo om algoritmer inte anpassas för parallellt arbete på flera processorkärnor samt för vektoroperationer på instruktionsnivå. Ofta finns det även flera olika typer av beräkningsenheter på samma chip som måste samarbeta för att uppnå högsta möjliga prestanda. Mitt arbete innefattar algoritmer för att snabbt genomföra synlighetsberäkningar i olika situationer. Linjer över kamerasensorn har använts för att bestämma synlighet med hög kvalité för trianglar under rörelse samt tunna kurvor som exempelvis hår. De kombinerade resurserna av både centralprocessor och integrerad grafikprocessor på samma chip har använts för att snabbare rita bilder med kantutjämning. Vidare har två algoritmer för att testa strålar mot geometri som ligger i specifika datastrukturer tagits fram. Den första algoritmen innebär att testning mot ett binärt träd kan ske rekursivt utan att använda minne för att lagra en stack. Den andra algoritmen testar många strålar samtidigt mot ett träd så att vektoroperationer kan användas på ett effektivt sätt.