THESISFORTHEDEGREEOFDOCTOROFPHILOSOPHY Real-Time Shading and Accurate Shadows Using GPGPU Techniques OlaOlsson DivisionofComputerEngineering DepartmentofComputerScienceandEngineering CHALMERSUNIVERSITYOFTECHNOLOGY Go¨teborg,Sweden2014 Real-TimeShadingandAccurateShadowsUsingGPGPUTechniques OLAOLSSON ISBN978-91-7385-964-6 c OLAOLSSON,2014 (cid:13) DoktorsavhandlingarvidChalmerstekniskaho¨gskola NyserieNr3645 ISSN0346-718X TechnicalReport104D DepartmentofComputerScienceandEngineering Researchgroup: ComputerGraphics DivisionofComputerEngineering ChalmersUniversityofTechnologyandGothenburgUniversity SE–41296 Go¨teborg,Sweden Phone: +46(0)31–7721000 Contactinformation: OlaOlsson DivisionofComputerEngineering DepartmentofComputerScienceandEngineering ChalmersUniversityofTechnology SE–41296 Go¨teborg,Sweden Phone: +46(0)31–7721678 Fax: +46(0)31–7723663 Email: [email protected] URL: http://www.cse.chalmers.se/˜olaolss PrintedinSweden ChalmersReproservice Go¨teborg,Sweden2014 Real-Time Shading and Accurate Shadows Using GPGPU Techniques OLAOLSSON DivisionofComputerEngineering,ChalmersUniversityofTechnology Abstract Overthelast10-15years,computergraphicshardwarehasevolvedatatremendous pace, with an exponential growth in the number of transistors. This evolution has transformedtheGraphicsProcessingUnit(GPU)fromanentirelyfixed-functionunit intoahighlyparallelgeneral-purposearchitecturethatcanbeprogrammedusinghigh- levelprogramminglanguages.Duringthistime,thecomputationalpoweroftheGPUhas continuallyoutpacedthatofCPUs,resultinginaconsiderableperformanceadvantage. AstheGPUarchitectureandcapabilitieshaveevolved,somustthealgorithmsthat targetthesedevices. Whereaspreviouslytheonlyroadtoreal-timeperformancelayin findingwaysofmappingproblemstothefixed-functionhardware, todaythebulkof computationalpowerisfoundinthegeneral-purposeportionsoftheGPU. Theapproachinthisthesisutilizesthisflexibilityandpowertoexplorenoveland moreefficientalgorithmsthatsolveimportantreal-timecomputergraphicsproblemsby targetingthegeneral-purposeGPU-cores. Thethesisfocusesontwoconcreteproblem areas:many-lightshadingandaccurateshadows.Forbothoftheseareas,newalgorithms arepresentedthatovercomesubstantialbottlenecksinpreviousalgorithms. Intheareaofmany-lightshading,thethesispresentsalgorithmsthatenableavery largenumberoflightstobeshaded,effectivelyeliminatingthenumberoflightsasa primarybottleneck. Anefficientmethodforusingvirtualshadowmapsforhundredsof lightsisalsointroduced,apreviouslyunsolvedproblem. Foraccurateshadows,analgorithmispresentedthattakesanovelapproachtoshadow volumesandshowsthatthisresultsinarobust,flexible,andhighlyefficientalgorithm. The new algorithm is shown to outperform previous work and provide much more predictableperformancewithchangingviews. Theunderlyingproblemthatissolvedinthedifferentalgorithmsinthisthesisisthat ofintersectingthevisiblesampleswithboundingvolumesrepresentinglightorshadow. Thesolutionspresentedinthisthesisdemonstratethatthiscanbeefficientlyachieved usinggroupingsofviewsamples,combinedwithahierarchicalaccelerationstructure. Thisproblemisofaquitegeneralnature,andthesolutionsderivedinthisthesisshould thereforebeapplicabletomanyrelatedreal-timerenderingproblems. Keywords:rendering,shading,shadows,shadowvolumes,transparency,virtualshadow- maps,realtime,GPU,GPGPU. i ii Acknowledgments MythanksandrespectarefirstandforemostduetoUlfAssarsson,forbeingagreat PhDadvisor,withtimelyfeedbackandadowntoearthapproach.IalsowishtothankUlf forallhishardworkinestablishingthecomputergraphicsresearchgroupatChalmers, andforprovidingmewiththeopportunityforthesemostrewardingsixyears. I’mvery gratefulforhavingbeenpartofthisprojectandallowedtoletmyideasrunwildonthe fieldsofCG(inamannerofspeaking). Thanks are also due to the rest of the computer graphics group, who are also co- authorsonmypapers,ErikSintorn,andMarkusBilleterandViktorKa¨mpe,forbeinga greatteamofpeopletoworkwith. TherearealsomanyotherpeopleatChalmerswho havemadethisagreatandstimulatingplacetoconductmyPhDstudies,thankyouall. I would also like to thank my Masters Thesis advisor, Angela Wallenburg, and examiner,ReinerHa¨hnle,forbeingverysupportiveinmyambitiontobecomeaPhD student,initiallybyprovidingaconfusedundergraduate(thatis,me)witharealresearch challengeformymastersthesisproject. Thiswasmyfirstexperiencewithresearch, andwithoutthisandtheirsubsequentencouragement,itisnotlikelythatIwouldhave starteddownthispath. BigthanksofcoursetomylovelywifeJaz,whohaspatientlyputupwiththeseyears ofmedeliveringweirdexplanationsofcomputergraphicsalgorithmsandconcepts(the lastofwhichinvolvedpeas,aneverincreasingnumberofarms,andakeyhole). During mytimeasaPhDstudentwealsohadourtwochildren,StellaandRuben,andSTELLA willbeabletoreadhernamerightthere! Thankyouallforjustbeingwonderful,andfor introducingahealthydoseofperspectiveintomylife. I also wish to express my gratitude to remaining family and friends, for always showinginterestandatleastpretendingtoconsidermyabsurdinterestsnormal.Itishard toimaginehavingtogothroughsuchanundertakingasthiswithoutthisacceptance. I also wish to thank enthusiastic people in the games industry, in particular Emil PerssonofAvalancheStudios. Emilhasbeenafantasticpromoterofclusteredshadingin theindustry,andithasbeenmygreatpleasuretodopresentationstogether. Thepeople intheGameTechnologyBrisbaneMeetupgrouphavealsobeeninspiringandinterested inmywork. Finally,IwishtothankPerStenstro¨m,myexaminer,whohasalwaysbeenreadyto giveconstructivefeedback. Notleastimportantlyduringthewritingprocessleadingto thisPhDthesis. iii iv ListofAppendedPapers Thisthesisisasummaryofthefollowingpapers. Referencestothepaperswillbemade usingtheRomannumbersassociatedwiththepapers. I OlaOlssonandUlfAssarsson,“TiledShading”,in Journalofgraphics,GPU, andgametools,Volume15,Issue4,Pages235–251,2011 II OlaOlsson,MarkusBilleter,andUlfAssarsson,“ClusteredDeferredandForward Shading”, in HPG ’12 Proceedings of the Conference on High Performance Graphics,pp87–96,June,2012 III OlaOlsson,ErikSintorn,ViktorKa¨mpe,MarkusBilleterandUlfAssarsson,“ EfficientVirtualShadowMapsforManyLights”,in I3D’14: Proceedingsofthe 2014symposiumonInteractive3Dgraphicsandgames,toappear,March,2014 IV ErikSintorn,OlaOlssonandUlfAssarsson,“AnEfficientAlias-freeShadowAlgo- rithmforOpaqueandTransparentObjectsusingper-triangleShadowVolumes”, in ACMTransactionsonGraphics(TOG)-ProceedingsofACMSIGGRAPH Asia2011,Volume30,Issue6,ArticleNo. 153,December2011 V ErikSintorn,ViktorKa¨mpe,OlaOlssonandUlfAssarsson,“Per-TriangleShadow VolumesUsingaView-SampleClusterHierarchy”,in I3D’14:Proceedingsofthe 2014symposiumonInteractive3Dgraphicsandgames,toappear,March,2014 Otherpapers,bythesameauthor,omittedinthethesis: OlaOlssonandUlfAssarsson,“ImprovedRayHierarchyAliasFreeShadows”, • in TechnicalReport2011:09,ChalmersUniversityofTechnology,April2011 MarkusBilleter,OlaOlssonandUlfAssarsson,“EfficientStreamCompaction • onWideSIMDMany-CoreArchitectures”,in ProceedingsoftheConferenceon HighPerformanceGraphics2009,August1-3,2009 v vi Contents 1 Real-TimeShadingandAccurateShadowsUsingGPGPUTechniques 1 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 OverallObjectiveandProblemStatements . . . . . . . . . . . 5 1.3 Maincontributions . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 ThesisStructure . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Real-TimeMany-LightShading . . . . . . . . . . . . . . . . . . . . . 8 2.1 PaperI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 PaperII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 PaperIII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3 Real-TimeAccurateShadows. . . . . . . . . . . . . . . . . . . . . . . 12 3.1 PaperIV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 PaperV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4 DiscussionandFutureWork . . . . . . . . . . . . . . . . . . . . . . . 15 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 PaperI: TiledShading 21 3 PaperII: ClusteredDeferredandForwardShading 41 4 PaperIII: EfficientVirtualShadowMapsforManyLights 53 5 PaperIV: AnEfficientAlias-freeShadowAlgorithmforOpaqueandTrans- parentObjectsusingper-triangleShadowVolumes 63 6 PaperV: Per-TriangleShadowVolumesUsingaView-SampleClusterHi- erarchy 75 vii viii