Fast and High-Quality Visibility Determination
(2015)- Abstract
- Computer generated imagery is vital to the entertainment industry in the production of games and films, for example. It is also increasingly important for visualization in design, architecture, engineering, and medicine, to name a few. Improvements to rendering techniques come from a combination of improved algorithms and more powerful hardware. Typically, hardware developments introduce new challenges and opportunities for algorithms that better fit the platform. Recently, these developments involve a widening gap between memory bandwidth and compute capabilities, wide SIMD units, and shared memory between CPU and GPU.
The focus of this thesis is on improved algorithms for visibility queries that are used in graphics,... (More) - Computer generated imagery is vital to the entertainment industry in the production of games and films, for example. It is also increasingly important for visualization in design, architecture, engineering, and medicine, to name a few. Improvements to rendering techniques come from a combination of improved algorithms and more powerful hardware. Typically, hardware developments introduce new challenges and opportunities for algorithms that better fit the platform. Recently, these developments involve a widening gap between memory bandwidth and compute capabilities, wide SIMD units, and shared memory between CPU and GPU.
The focus of this thesis is on improved algorithms for visibility queries that are used in graphics, motivated by challenges introduced by recent hardware developments. Geometry sampling lies at the core of rendering techniques, both for real-time and offline rendering, and generating images of higher quality generally involves taking more samples. Performance and quality improvements for visibility samples can thus enable higher quality rendering within a smaller time budget.
This thesis presents five published papers with new solutions for visibility queries in the two major rendering paradigms in use today: rasterization and ray tracing. Two-dimensional rasterization is common in real-time graphics because of its computational efficiency. Multiple point samples are usually taken for each pixel to get high-quality images without aliasing artifacts. When rendering thin curves, many samples will typically be required to achieve acceptable quality. In this context, we propose that thin curves can be rasterized in high quality on a graphics processor using spatial line samples and curve-specific intersection tests. Further, we propose that the recent advent of shared memory between CPU and GPU can allow for MSAA computations to be offloaded to idle CPU cores. In three-dimensional rasterization, specifically rasterization with motion blur, we introduce a way to render practically noise- and alias-free images with competitive performance using semi-analytical line-based visibility queries on a multi-core CPU.
Ray tracing, common in offline rendering, is a flexible rendering technique that can model how light propagates in a scene. Challenges in ray tracing include how a ray can be efficiently tested against a scene. Tests are accelerated by building a spatial hierarchy over the scene and our work in ray tracing specifically targets the process of traversing rays against a bounding volume hierarchy (BVH). The first contribution involves a flexible BVH traversal algorithm that executes without storing the traversal state in a stack, which may be beneficial in cases where storing a stack is expensive. The second contribution is an efficient algorithm for traversing large streams of rays against a BVH while making use of wide SIMD. (Less) - Abstract (Swedish)
- 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... (More) - 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/5471133
- author
- Barringer, Rasmus LU
- supervisor
- opponent
-
- Professor Eisemann, Elmar, TU Delft Faculty of Electrical Engineering, Mathematics and Computer Science, The Netherlands
- organization
- alternative title
- Snabba Synlighetsberäkningar med Hög Kvalité
- publishing date
- 2015
- type
- Thesis
- publication status
- published
- subject
- keywords
- computer graphics, visibility, anti-aliasing, line sampling, ray tracing, rendering
- pages
- 151 pages
- defense location
- E:1406
- defense date
- 2015-09-04 13:00:00
- ISBN
- 9789176233757
- language
- English
- LU publication?
- yes
- id
- f8007cbd-79fa-4ca1-97e2-bdcb4236079e (old id 5471133)
- date added to LUP
- 2016-04-04 09:22:12
- date last changed
- 2021-05-06 20:42:27
@phdthesis{f8007cbd-79fa-4ca1-97e2-bdcb4236079e,
abstract = {{Computer generated imagery is vital to the entertainment industry in the production of games and films, for example. It is also increasingly important for visualization in design, architecture, engineering, and medicine, to name a few. Improvements to rendering techniques come from a combination of improved algorithms and more powerful hardware. Typically, hardware developments introduce new challenges and opportunities for algorithms that better fit the platform. Recently, these developments involve a widening gap between memory bandwidth and compute capabilities, wide SIMD units, and shared memory between CPU and GPU.<br/><br>
<br/><br>
The focus of this thesis is on improved algorithms for visibility queries that are used in graphics, motivated by challenges introduced by recent hardware developments. Geometry sampling lies at the core of rendering techniques, both for real-time and offline rendering, and generating images of higher quality generally involves taking more samples. Performance and quality improvements for visibility samples can thus enable higher quality rendering within a smaller time budget.<br/><br>
<br/><br>
This thesis presents five published papers with new solutions for visibility queries in the two major rendering paradigms in use today: rasterization and ray tracing. Two-dimensional rasterization is common in real-time graphics because of its computational efficiency. Multiple point samples are usually taken for each pixel to get high-quality images without aliasing artifacts. When rendering thin curves, many samples will typically be required to achieve acceptable quality. In this context, we propose that thin curves can be rasterized in high quality on a graphics processor using spatial line samples and curve-specific intersection tests. Further, we propose that the recent advent of shared memory between CPU and GPU can allow for MSAA computations to be offloaded to idle CPU cores. In three-dimensional rasterization, specifically rasterization with motion blur, we introduce a way to render practically noise- and alias-free images with competitive performance using semi-analytical line-based visibility queries on a multi-core CPU.<br/><br>
<br/><br>
Ray tracing, common in offline rendering, is a flexible rendering technique that can model how light propagates in a scene. Challenges in ray tracing include how a ray can be efficiently tested against a scene. Tests are accelerated by building a spatial hierarchy over the scene and our work in ray tracing specifically targets the process of traversing rays against a bounding volume hierarchy (BVH). The first contribution involves a flexible BVH traversal algorithm that executes without storing the traversal state in a stack, which may be beneficial in cases where storing a stack is expensive. The second contribution is an efficient algorithm for traversing large streams of rays against a BVH while making use of wide SIMD.}},
author = {{Barringer, Rasmus}},
isbn = {{9789176233757}},
keywords = {{computer graphics; visibility; anti-aliasing; line sampling; ray tracing; rendering}},
language = {{eng}},
school = {{Lund University}},
title = {{Fast and High-Quality Visibility Determination}},
url = {{https://lup.lub.lu.se/search/files/5305786/5471161.pdf}},
year = {{2015}},
}