Simulating Soft Shadows with Graphics Hardware

rtandMichaelHerfJanuary15,1997CMU-CS-97-104SchoolofComputerScienceCarnegieMellonUniversityPittsburgh,PA15213email:ph@,herf+@ldWideWeb:/eviatedversionappearedin[rt,FastSoftShadows,VisualProceedings,SIGGRAPH96,Aug.1996,p.145].AbstractThispaperdescribesanalgorithmentgraphicsworkstations,thetechniquecancalculatethesoftshadowscastbymoving,tic,diffusescene,thesehighqualityshadowscanthenbedisplayedat30Hz,ffusescene,themethodprecomputesaradiancetexturetureforeachpolygoniscomputedbycreatingregisteredprojectionsofthesceneontothepolygonfrommultiplesamplepointsoneachlightsource,anhisprecomputation,softshadowsinastaticscenecanbedieloperationsemployedbythnwsandconclusionscontainedinthisdocumentarethoseoftheauthorsandshouldnotbeinterpretedasrepresentingtheofficialpolicies,eitherexpressedorimplied,ment.

Keywords:penumbra,texturemapping,graphicsworkstation,interaction,real-time,SGIRealityEngine.

1IntroductionShadowsarebothanimportantvisualcuefortheperceptiosdifferaccordingtothetypeoflightsourcecausingthem:pointlightsourcesyieldhardshadows,whilelinearandarea(alsoknownasextended)lightsourcesgenerallyyieldsoftshadowswithanumbra(fullyshadowedregion)andpenumbra(partiallyshad-owedregion).Therealworldcontainsmostlysoftshadowsduetothefinitesizeofskylight,thesun,andlightbulbs,yetmostcomputergraphicsrenderingsoftwaresimulatesonlyhardshadows,ivesharpnessotgraphicsworkstations,suchasSiliconGraphics(SGI)andHewlettPackard(HP)machines,providez-bufsareseldomsimulatedonsuchmachines,however,becauseexistingalgorithmsarenotgeneralenough,dowalgorithmsmostsuitableforinteractionongraphicsworkstatuchalgorithmsarepracticalforoneortwolightsources,theyareimpractenthereanorithmexploitsgraphicshardwareforfastprojective(perspective)transformation,clipping,scanconversion,texturemapping,visibilitytesting,dwareisusedbothtocomputetheshadingonthesurfacesandtodisplayit,fusescenes,theshadingiscomputedinapreprocessingstepwhosecostisproportionaltothenumberoflightsourcesamples,butwhilethesceneisstatic,hodisalsouoryrequirementsofthealgorithmarealsoindependentofthenumberoflightsourcesamples.1.1TheIdeaFordiffusescenes,ourmethodworksbyprecomputing,foreachpolygoninthescene,aradiancetexture[12,14]thatrecordsthecolor(outgoingradiance)fusescene,theradianceateachsurfacepointisviewindependent,diancetextureisaaradiosityalgorithm,however,ideaistousegraphicshardwaretodeterminevisibilityandcalculateshading,thatis,todeterminewhichportionsofasurfaceareoccludedwithrespecttoagivenextendedlightsource,rtosimulateextendedlightsources,weapproximatethemwithanumberoflightsamplepoints,anasmanyoperationsinhardwareaspossible,however,wedonotuseahemicube[7]d,tocomputetheshadowsforasinglepolygon,werenderthesceneintoascratchbuffer,withallpolygonsexcepttheonebeingshadedappropriatelyblackened,usingiewsareregiseresultinghardshadowimagesareaveraged,asoftshadowimageresults(figure1).Thisimageisthenusedturessemainderofthepaper,wesummarizepreviousshadowalgorithms,wepresentourmethodfordiffusescenesinmoredetail,wediscussgeneralizationstosceneswithspecularandgeneralre-flectance,wepresentourimplementationandresults,edanumberofshadowalgorithms[19].Herewealgorithmscanbedividedintothreecategories:thosethatcomputeeverythingonthefly,thosethatprecomputejustvisibility,raytracingcomputeseverythingontheflsarecomputedonapoint-by-pointbasisbytracingraysbetwadowscanbesimulatedbytracingraystoanumberofpointsdistributedacrossthelightsource[8].Theshadowvolumeapproachisanothermethodforcomputingshadowsontheflismethod,oneconstructsimaginarysurfacesthanandBadlerusedanextendedz-bufferalgorithmwithlinkedlistsateachpixeltosupportsoftshadowsusingthisapproach[4].TepixelprocessorsofthePixelPlanesmachinetosimulatehardshadowsinreal-time[10].HeidmannusedthestencilbufferinadvancedSGImachines[13].WithHeidmann’salgorithm,thescenemustberenderedthroughthestencilcreatedfromeachlightsource,sothecostperframe1991hardware,softshhodappearstobeoneofthealgoridprefer,however,e,bruteforceapproach,goodforcastingshadowsofobjectsontoaplane,istofindtheprojectivetransformationthatprojectsobjectsfromapointlightontoaplane,andtouseittodraweachsquashed,blackenedobjectontopoftheplane[3],[15,p.401].Thisalgorithmeffectivelymultipliesthenumberofobjectsinthescenebythenumberoflightsourcestimesthenumberofreceiverpolygonsontowhichshadowsarebeingcast,however,soitistypirproblemwiththismethodisthatoccludersbehindthereceiverwillcasterroneousshadows,dofcomputingvisibilityonthefly,-buffershadowalgorithmusestwo(ormore)passesofz-bufferrendering,firstfromthelightsources,andthenfromtheeye[18].Thez-buffersfromthelightviewsareusedinthefinal

Figure1:2:Left:scenewithsquarelightsource(foreground),triangularoccluder(center),andrectangularreceiver(background),:Approximatesoftshadowsresultingfrom22gridofsamplepoints;:Correctsoftshadowimage(generatedwith1616sampling).detnsformationofpointsfromonecoordinatesystemtoanothercanbeacceleratedusingtexturemappinghard-ware[17].Thislattermethod,bySegaletal.,achievesreal-timerates,adowscanbegeneratedonagraphicsworkstationbyrenderingthescenemultipletimes,usingdifferentpointsontheextendedlightsource,averagingtheresultingimagesusingaccumulationbufferhardware[11].Avariationoftheshadowvolumeapproachistointersectthesevolumeswithsurfacesinthescenetoprecomputetheumbraandpenumbraregionsoneachsurface[16].Duringthefinalrenderingpass,putationcanbetakenfur-ther,mostrelevanttodiffusescenes,thesemethodscomputevisibilitycontinuously,lresearchershaveexploredcontinuousvisiisapproach,surfacesaresubdividedintofullylit,penumbra,andandFeiner’ssoftshadowmethod,polygonsaresplitusingBSPtrees,andthesesub-polygonsarethenpre-shaded[6].kisandFiumeusedmoresophisticatedcomputationalgeometrytechniquestoprecomputetheirsubdivision,andreportedrenderingtimesofseveralseconds[9].Mostradiositymethodsdiscretizeeachsurfaceintoameshofelementsandthenuicubemethodcomputesvisibilityfromalightsourcepointtoanentirehemispherebypro-jectingthesceneontoahalf-cube[7].itymeshestypicallydonotresolveshadowswell,lartifactsareMadiositymethodsarenotfastenoughtosupportinteractivechangestothegeometry,’sincrementalradiositymethodisanexception[5].Ourownmethodcanbecategorizednexttohemicuberadiositymethods,h-niqueforcomputingvisibilityalsohasparallelstothemethodofflatteningobjectstoaplane.2.2GraphicsHardwareCurrentgraphicshardware,suchastheSiliconGraphicsRealityEngine[1],canprojective-transform,clip,shade,scanconvert,andtexturetensofthousandsofpolygonsinreal-time(in1/30sec.).lly,suchhardwaresupportsarbitrary44homogeneoustransformationsofplanarpolygons,clippingtoanytruncatedpyra-midalfrustum(rightoroblique),achines,Phongshading(onceperpixel)isnotpossible,butfacetedshading(onceperpolygon)andGouraudshading(oncepervertex)hading2

n,generalformforhardware-supportedilluminationisdif-fusereflectionfrommultiplepointspotlightsources,withatexturemappedreflectancefunctionandattenuation:light lrx'liθ'θreceiver

RxcoscosFigure3:ianceatpointonthereceiverisbeingcalculatedbysummingthecontributionsfromasetofpointlightsourcesatonlight.3.1ApproximatingExtendedLightSourcesAlthoughsuchintegralscanbesolvedinclosedformforplanar1),thecomplexityofthevisibilitysurfaceswithnoocclusion(omputeapproximationstotheintegral,however,byreplacingeachextendedlightsourcebyasetofpointlightsources:1whereisa3-DDiracdeltafunction,ource,andTypically,eachsampleonalightsourcehasequalarea:,isapproximation,theradianceofareflectivesurfacepointcanbecomputedbysummingthecontributionsoverallsamplepointsonalllightsources:acos+cos+12where,asshowninFigure3,isa3-Dpointonareflectivesurface,andisapointonalightsource,ispolarangle(anglefromnormal)at,istheangleat,isthedistancebetweenand,,,andarefunctionsofand,isoutgoingradianceatpointforcolorchannel,duetoeitheremissionorreflection,aisambientradiance,isreflectance,isaBooleanvisibilityfunctionthatequals1ifpointisvisiblefrompoint,else0,cos+maxcos0,forbackfacetesting,andtheintegralisoverallpointsonalllightsources,withrespect,whichisaninfinputstotheproblemarethegeometry,thereflectance,onalllightsources,theambientradi-andemittedradianceancea,andtheoutputisthereflectedradiancefunction.2(2)Eachtermintheinnersummationcanberegardedasahardshadowimageresultingfromapointlightsourceat,firstone,whichisanareatimesthereflectanceofthereceivingpolygon,ondfactoristhecosineoftheangleonthereceiver,timesthecosineoftheangleonthelight3

b+ex+eyzoyoy=wb+ex=0x=wy=0yab+exbxohasapexanditsparallelogrambasehasonevertexatandedgevectorsxandy(boldlowercasedenotesa3-Dpointorvector).Theparallelepipedliesinwhatwewillcallunitscreenspace,fromtheapex,theleftandrightsidesofthepyramidmaptotheparallelplanesu0andu1,thebottomandtopmaptou0andu1,andthebaseplaneand,figure4.A44homogeneousmhavetheform:Figure4:,timestheradianceofthelightsource,nbecomputedinhardwarebyrenderingthereceiverpolygonturnedon,usingaspinesthatdonotsupportPhongshading,wewillhavetofirdfactorilitycanbecomputedbyprojectingfulladvantageofthehardware,wecanprecomputetheshadingforeachpolygonusingtheformulaabove,andthendisplayviewsofthescenutesoftshadowtextures,ehardshadowimagesarenotregistered(theywouldnotbe,usinghemi-cubes),thenitwouldbenecessarytoresamplethemsothatcorresralternativeistochoosethetransformationforeachprojectnarreceiversurfaces,thisiseasilyaccofitaparallelogramaroundthereceiversurfaceofinterest,andthencon-structapyramidwiththisasitsbaseandthelightpointasitsapex,thereisa44homogeneoustransformationthatwillmapsuchapyramidintoanaxis-alignedbox,dshadowimageduetosamplepointonlightiscreatedbyloadiygonisilluminatedbytheambientlightplusasinglepointlightsourceat,ibilityfunctionisthencomputedbyrenderingtheremainderofthescenewithallsurfacesshadedasiftheywerethereceiverilluminatedbyambientlight:mostquicklydonewithz-bufferingoff,geachpolygonwithanunsortedpainter’salgorithmsufficesherebecauseallpolygonsarethesamecolor,andafterclipping,theonlypolygonfragmentsremainingwillliebetweenthelightsourceandthereceiver,utetheweightedaverageofthehardshadowimagessocreated,weusetheaccumulationbuffer.3.3ProjectiveTransformationofaPyramidtoaBoxWewantaprojective(perspective)transformationthatamidliesinobjectspace,=0w=141333andthehomogeneoustransformationandhomogeneousdivisiontotransformobjectspacetounitscreenspaceare:o1o1oanduuu1Thethirdrowofmatrixtogeneousscreencoordinates,,andareeachaffinefunctionsofo,o,ando(thatis,linearplustranslation).Theconstraintsabovespecifythevalueofeachofthethreecoordinatesatfourpointsinspace–rdinate,forexample,hasvalue1atthepoints,x,andy,ore,thevectorw,thusfixingthefirstisnormaltoanyplaneofconstantyxthreeelementsofthelastrowofthematrixwithinascalefactor:gandw1ww,first33wwcanbederivedsimilarly(seefigure4).Theresulttworowsofis:xyxxyxwxxyxyyyxyxzyzxyxy0001wwwywwzwwwherexywwxyyxwandxyw111xyxywwBlinn[3]usesarelatedprojectivetransformationforthegenera-tionofshadowsonaplane,buthisisaprojection(itcollapses3-Dto2-D),hethirddimensionforclipping.3.4UsingtheTransformationTousethistransformationinourshadowalgorithm,wefirstfieceiverisarectangleorotherparallelogram,thefitisexact;ifthereceiverisatriangle,thenwefitthetriangleintothelowerlefttriangleoftheparallelogram;andformoregeneralpolygonswithfourormoresides,ssibletogofurtherwithprojectivetransformations,mappingarbitraryplanarquadrilateralsintosquares(usingtheho-mogeneoustexturetransformationmatrixofOpenGL,forexample).Weassumeforsimplicity,however,thatthetransformationbetweentexturespace(thescreenspaceintheselightsourceprojections)andobjectspaceisaffine,andsowerestrictourselvestoparallelograms.

3.5SoftShadowAlgorithmforDiffuseScenesToprecomputesoftshadowradiancetextures:turnoffz-bufferingforeachreceiverpolygonchooseresolutionforreceiver’stexture(xypixels)clearaccumulatorimageofxypixelstoblackcreatetemporaryimageofxypixelsforeachlightsourcefirstbackfacetest:ifisentirelybehindorisentirelybehind,thenskiptonextforeachsamplepointonlightsourcesecondbackfacetest:ifxliisbehindthenskiptonextcomputetransformationmatrixM,whereaxli,andthebaseparallelogramfitstightlyaroundsetcurrenttransformationmatrixtoscalexy1Msetclippingplanestounear1andufarbigdrawwithilluminationfromxlionly,asdescribedinequation(2),intotempimageforeachotherobjectinscenedrawobjectwithambientcolorintotempimageaddtempimageintoaccumulatorimagewithweightsaveaccumulatorimageastextureforpolygonsteps,sticsampling[8]withthesamenumberofsamplesyieldssmootherpenumbrathanauniformgrid,jitfixednumberofsamplesoneachlightsourceisineffi-mplingofalightsourceismostimportantwhenthelightsourcesubtendsalargesolidanglefromthepointofviewofthereceiver,sincethatpproachistochoosethelightsourcesampleresolutionsuchthatthesolidanglesubtendedbythelightsourceareaassociatedwitheachsampleisbelowauser-specifiorithmcaneasilyhandlediffuse(non-directional)lightsourceswhoseoutgoingradiancevarieswithposition,hlightsources,importancesam-plingmightbepreferable:concenreaveragedtogethertocomputeasoftshadowimage,atobjectscastingshadowsneednotbepolygonal;layastaticscenefrommovingviewpoints,simply:3.8TextureResolutionTheresolutionoftheshadowtextureshouldberoughlyequaltotheresolutionatwhichitwillbeviewed(onetexturepixelmappingtoonescreenpixel);lowerresolutionresultsinvisibleartifactssuchasblockyshadows,bsenceofinformationaboutprobableviews,areasonabletechniqueistosetthenumberofpixelsonapolygon’stexture,ineachdimension,proportionaltoitssizeinworldspaceus-inga“desiredpixelsize”isscheme,therequiredtexturememory,inpixels,willbethetotalworldspacesurfaceareememoryfortrianglescanbefurtheroptimizedbyearetoomanypolygonsinthescene,orthedesiredpixelsizeistoosmall,thetexturememorycouldbeexceeded,cetexturescanbeantialiasedbysupersampling:gener-atingthehardandinitialsoftshadowimagesatseveraltimesthedesiredresolution,andthenfiedsurfacesshouldberenderedwithgoodtexturefilygonswillcontainpenumbralregionswithrespecttoalightsource,andwillrequirehightextureresolution,butotherswillbeeithertotallyshadowed(umbral)ortotallyilluminatedbyeachlightsource,mesthesefunctionswillbesosmooththtimizationsavessignifieacanbecarriedfurther,replacingthplexshadowpatternsandradiancefunctions,however,texturesmayrenderfasterthanthecorrespondingGouraudapproximation,dependingontherelativespeedoftexturemappingandGouraud-shadedtriangledrawing,z-bufferingforeachobjectinsceneifobjectreceivesshadows,drawittexturedbutwithoutilluminationelsedrawobjectwithillumination3.6BackfaceTesting0canbeoptimizedusingbackfaceThecaseswherecos+cos+ifpolygonisbehindpolygon,computethesigneddistancesfromtheplaneofpolygontoeachoftheverticesof(signedpositiveonthefrontofandnegativeontheback).Iftheyareallpositive,thenisentirelyinfrontof,iftheyareallnonpositive,isentirelyinback,otherwise,iftheapexofthepyramidisbehindthereceiverthatdefinesthebaseplane,simplytestifww0.0ateverypointontheTheabovecheckswillensurethatcosreceiver,butthereisstillthepossibilitythatcos0onportionsofthereceiver(ereceiverisonlypartiallyilluminatedbythelightsource).Thisfinalcaseshouldbehandledatthepohading,oragoodapproximationtoit,isneededhere.3.7SamplingExtendedLightSourcesThesetofsamplesusedoneachlightsourcegreatlyinflsamples,orapoorlychosensampledistribution,resultinpenumbrasthatappearstepped,anysamplesareused,however,formgridofsamplepointsisused,mple,ifauniformgridofsamplesisusedonaparallelogramlightsource,anoccluderbigedgecoplanarwithoneofthelightsourceedgeswillcause3.9ComplexityWenowanalyzetheexpectedcomplexityofouralgorithm(worstcasecostsarenotlikelytobeobservedinpractice,sowedonotdiscussthemhere).Althoughmoresophisticatedschemesarepos-sible,wewillassumeforthepurposesofanalysisthatthesameset5

3.10ComparisontoOtherAlgorithmslight

本文标签： 学好 语言 心得 作者