Advanced

Algorithmic Improvements for Stochastic Rasterization & Depth Buffering

Andersson, Magnus LU (2015)
Abstract (Swedish)
Popular Abstract in Swedish

Inom området datorgrafik undersöker man hur virtuella scener kan omvandlas till verklighetstrogna bilder. För interaktiva miljöer, som exempelvis datorspel, måste en ny bild vara genererad och klar att visas på skärmen mellan 30-60 gånger i sekunden för att upplevelsen ska kännas responsiv och för att rörelser ska flyta på ett naturligt sätt. För att datorn ska hinna med att beräkna nya bilder krävs en kombination av smarta algoritmer och hög beräkningskapacitet för de typer av beräkningar som behöver utföras.

I dagens datorer, mobiltelefoner och pekplattor finns en hårdvaruenhet tillägnad att hantera grafikproblem, en så kallad grafikprocessor (Eng. graphics processing unit eller GPU).... (More)
Popular Abstract in Swedish

Inom området datorgrafik undersöker man hur virtuella scener kan omvandlas till verklighetstrogna bilder. För interaktiva miljöer, som exempelvis datorspel, måste en ny bild vara genererad och klar att visas på skärmen mellan 30-60 gånger i sekunden för att upplevelsen ska kännas responsiv och för att rörelser ska flyta på ett naturligt sätt. För att datorn ska hinna med att beräkna nya bilder krävs en kombination av smarta algoritmer och hög beräkningskapacitet för de typer av beräkningar som behöver utföras.

I dagens datorer, mobiltelefoner och pekplattor finns en hårdvaruenhet tillägnad att hantera grafikproblem, en så kallad grafikprocessor (Eng. graphics processing unit eller GPU). En av GPUns huvuduppgifter är att avgöra vilka ytor i scenen som är synliga för varje pixel i bilden genom en process som kallas rasterering. Viktigt att tänka på är att ogenomskinliga ytor ju faktiskt fullständigt kan täcka varandra och endast ytorna närmast kameran som kommer därför synas i den färdiga bilden. Rastereringshårdvaran i moderna GPUer ritar en yta åt gången, vilket medför att det inte går att veta vilken yta som slutgiltigt kommer vara närmast kameran under rastereringens gång. För att lösa detta problem används så kallad djupbuffring, där GPUn håller reda på vilken yta som är närmast i varje pixel, efterhand som bilden successivt byggs upp. Bufferten som innehåller djupvärdena för

varje pixel ligger i minnet på GPUn, och att läsa och uppdatera medför en hel del datatrafik. I avhandlingen presenteras en serie hårdvaruförbättringar som kan användas för att minska datatrafiken som uppkommer p.g.a. djupbuffring, vilket leder till bättre prestanda och lägre strömförbrukning.

För att den genererade bilden ska se mer verklighetstrogen ut så är det viktigt att omvandlingen från virtuell scen till bild även tar med begränsningar i kamerautrustning som vi människor är vana att se i fotografier och på film. Två av de viktigaste fenomenen är förmodligen skärpedjup och rörelseoskärpa. Det är bara möjligt att fokusera och få en skarp bild inom ett begränsat avstånd från kameran, inom det så kallade skärpedjupet. Föremål i förgrunden och bakgrunden blir således mer och mer oskarpa ju längre ifrån skärpedjupet de befinner sig. Rörelseoskärpa uppkommer då motivet flyttar sig under exponeringstiden, vilket gör att rörelsemönstret "fångas" i bilden.

Att modellera ett kamerasystem som tar exponeringstid och linssystem i beaktning är en beräkningsmässigt tung uppgift, vilket gör det svårt att simulera allt för komplicerade kameramodeller i interaktiva applikationer. En algoritm som fått dragkraft inom forskningsvärlden under de senaste åren för att simulera rörelseoskärpa och skärpedjup är så kallad stokastisk rasterering. Genom att betrakta scenen från slumpvis utvalda ögonblick och vägar genom linssystemet kan en bild som innehåller både rörelseoskärpa och skärpedjup byggas upp. Dessvärre medför metoden fler läsningar och skrivningar till djupbufferten.

En stor del av vår forskning är riktad åt att förbättra djupbufferprestandan, både för konventionell och för stokastisk rasterering. De tekniker som undersökts är förbättrad minnesanvändning genom s.k. minnescachning, datakompression och utgallring av täckta ytor. Cache:ar används för att förkorta tiden det tar att hämta och skriva data till och från RAM-minnet, där djupbufferten finns. Genom att använda komprimering så kan djupdatan representeras mer kompakt, vilket ytterligare minskar datatrafiken till minnet. Utgallring av täckta ytor är en teknik som går ut på att minimera mängden bortkastat arbete genom att i ett tidigt skede avgöra vilka ytor som är täckta och därför inte kommer bidra till den slutgiltiga bilden. Dessa tekniker kan tillsammans användas för kraftigt förbättra prestandan för djupbuffersystemet.

Ett annat problem som försvåras av stokastisk rasterering är hur man beräknar färgen för ytor som är i rörelse eller är ur fokus. Färgen av en yta beror bland annat på dess materialegenskaper, på ljussättningen och på var kameran befinner sig. Vi har utvecklat två algoritmer med ändamålen att snabbt och effektivt beräkna ytfärgen. Den första metoden delar upp färgberäkningen och den stokastiska rastereringen i två separata pass. Uppdelningen gör att vi enkelt kan återanvända den beräknade färgen under rastereringspasset och på så vis uppnå mycket goda prestandaresultat. Den andra metoden används för att avgöra om en yta är i skugga eller ej då objekt och/eller kameran är i rörelse. Att beräkna skuggan under sådana omständigheter är ett svårt problem, inte minst för interaktiva miljöer då beräkningstiden är begränsad. Vi presenterar en algoritm som ger trovärdiga skuggor med hög kvalité. Båda algoritmerna är implementerade och testade på existerande GPUer och är alltså användbara redan idag. (Less)
Abstract
The field of computer graphics refers to the use of computers to generate realistic-looking images from virtual scenes. Graphics processing units use an algorithm known as rasterization to compute images of scenes viewed from a virtual camera. The commonly used pinhole camera model does not account for the imperfections that stem from the physical limitations in real-world cameras. This includes, for example, motion and defocus blur. These two phenomena can be captured using stochastic rasterization, which is an algorithm that extends upon conventional rasterization by being able to handle moving and out-of-focus objects. Using this approach, the virtual scene is sampled at different instances in time and using different paths through the... (More)
The field of computer graphics refers to the use of computers to generate realistic-looking images from virtual scenes. Graphics processing units use an algorithm known as rasterization to compute images of scenes viewed from a virtual camera. The commonly used pinhole camera model does not account for the imperfections that stem from the physical limitations in real-world cameras. This includes, for example, motion and defocus blur. These two phenomena can be captured using stochastic rasterization, which is an algorithm that extends upon conventional rasterization by being able to handle moving and out-of-focus objects. Using this approach, the virtual scene is sampled at different instances in time and using different paths through the camera lens system. Alas, the extended functionality comes at a higher computational cost and consumes much more memory bandwidth. Much of the increased bandwidth usage is due to the increase in traffic to the depth buffer. The focus of the six papers included in this thesis is threefold. First, we have explored ways to reduce the high memory bandwidth consumption inherent in depth buffering, targeting both conventional and stochastic rasterization. We have evaluated a number of hardware changes, including novel compression schemes and cache improvements, which efficiently reduce memory bandwidth usage. We also propose a hardware friendly algorithm which reduces the pressure on the depth buffering system by culling unnecessary work early in the pipeline. Second, we propose an algorithm to reduce shading computations for stochastic rasterization. In our approach, we decouple shading and visibility determination into two separate passes. The surface color is sparsely evaluated in the first pass and can be efficiently used in the second pass, when rendering from the camera. The two-pass approach allows us to adaptively adjust the shading rate based on the amount of blur resulting from motion and defocus effects, which greatly reduces rendering times. Third, we propose a real-time algorithm for rendering shadows cast by objects in motion. Due to the complicated interplay between moving objects, moving light sources, and a moving camera, rendering motion blurred shadows is an especially difficult problem. Using our algorithm, high quality, smooth shadows can be achieved on conventional graphics processors. Collectively, I believe that our research is a significant step forward for rendering scenes with motion and/or defocus blur, both in terms of quality and performance. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Poulin, Pierre, Université de Montréal, Département d'informatique et de recherche opérationnelle
organization
publishing date
type
Thesis
publication status
published
subject
defense location
Lecture hall E:1406, building E, Ole Römers väg 3, Lund University, Faculty of Engineering (LTH), Lund
defense date
2015-10-16 13:00
language
English
LU publication?
yes
id
3a3dec14-811b-41ad-a424-242a8ab5dd46 (old id 7936207)
alternative location
http://fileadmin.cs.lth.se/graphics/research/papers/2015/ThesisMagnus/Thesis.pdf
date added to LUP
2015-09-23 08:47:56
date last changed
2016-09-19 08:45:19
@misc{3a3dec14-811b-41ad-a424-242a8ab5dd46,
  abstract     = {The field of computer graphics refers to the use of computers to generate realistic-looking images from virtual scenes. Graphics processing units use an algorithm known as rasterization to compute images of scenes viewed from a virtual camera. The commonly used pinhole camera model does not account for the imperfections that stem from the physical limitations in real-world cameras. This includes, for example, motion and defocus blur. These two phenomena can be captured using stochastic rasterization, which is an algorithm that extends upon conventional rasterization by being able to handle moving and out-of-focus objects. Using this approach, the virtual scene is sampled at different instances in time and using different paths through the camera lens system. Alas, the extended functionality comes at a higher computational cost and consumes much more memory bandwidth. Much of the increased bandwidth usage is due to the increase in traffic to the depth buffer. The focus of the six papers included in this thesis is threefold. First, we have explored ways to reduce the high memory bandwidth consumption inherent in depth buffering, targeting both conventional and stochastic rasterization. We have evaluated a number of hardware changes, including novel compression schemes and cache improvements, which efficiently reduce memory bandwidth usage. We also propose a hardware friendly algorithm which reduces the pressure on the depth buffering system by culling unnecessary work early in the pipeline. Second, we propose an algorithm to reduce shading computations for stochastic rasterization. In our approach, we decouple shading and visibility determination into two separate passes. The surface color is sparsely evaluated in the first pass and can be efficiently used in the second pass, when rendering from the camera. The two-pass approach allows us to adaptively adjust the shading rate based on the amount of blur resulting from motion and defocus effects, which greatly reduces rendering times. Third, we propose a real-time algorithm for rendering shadows cast by objects in motion. Due to the complicated interplay between moving objects, moving light sources, and a moving camera, rendering motion blurred shadows is an especially difficult problem. Using our algorithm, high quality, smooth shadows can be achieved on conventional graphics processors. Collectively, I believe that our research is a significant step forward for rendering scenes with motion and/or defocus blur, both in terms of quality and performance.},
  author       = {Andersson, Magnus},
  language     = {eng},
  title        = {Algorithmic Improvements for Stochastic Rasterization & Depth Buffering},
  year         = {2015},
}