Fast and simple occlusion culling using hardware-based depth queries

DepthQueries

K.HilleslandB.SalomonA.LastraD.Manocha

UniversityofNorthCarolinaatChapelHill{khillesl,salomon,lastra,dm}@cs.unc.eduhttp://www.cs.unc.edu/∼walk/FSOC

Abstract:algorithmwerenderdecomposeforWelargepresentaconservativeocclusioncullingtheenvironments.sceneusingAspartofapreprocess,Ourtheprimitivesatruntimeainspatialsubdivisionandtoalgorithmuseshardwareacceleratedafront-to-backocclusionqueriesorder.progressivetestthevisibilityofmoredistantvolumesofspaceinimplementocclusionandmanner.TheresultingalgorithmissimpletoaWecardhaveimplementedqueriesmakesanduseitvertexofhardwarefeaturesincludingtheonashadersPCforfastperformance.ofable12.5andmillionareabletrianglestorenderwithanNVidiaGeForce3at10a−powerplantmodelcomposedratewithtoachievenolossainspeedupimagequality.

offrom20fourframestotenasecond.timesinWeframeare1Introduction

Ingraphicsspiteofmodelshardware,therapiditprogressintheperformancelevelsofplicationsatinteractiveisstillnotpossibletorenderverylargetionincludingCAD,rates.Thevirtualmodelsusedincommonap-time,andasthesimulationsbandwidtharetothegettinggraphicsmoreenvironments,cardscomplex.isnotAtvisualiza-thesameratesfastascomputationalpower.Therefore,toachieveincreasingpeakmodelsrequiresthatrenderingbedoneinretainedmode.Sincetherederedismustahardbelimitstoredononthethesizememoryofmodelsofthethatgraphicscard,modelsatthatisfullbandwidthrates.Givenlimited,thatourthefirstrenderingcanberen-priorityofisverylargeicscard.

weminimizethenumberofprimitivessenttothetoensuregraph-notInmassivemodelsmanyoftheitivescontributeintothreetocategories.

thefinalimage.Weunderlyingcanclassifyprimitivestheseprim-do1.Thoseoutsidetheviewfrustum.

2.Thoseandframearethatbuffer.notprojectrenderedtoduelesstothantheasampledpixelinnaturescreenofspacethe3.Thosebackfacingfullyprimitives).

occludedbyotherprimitives(includingSubmittedtoJournalofGraphicsToolsTheitivesgoalofviewfrustumcullingistoquicklyrejectprim-basedinnumberimpostorcategorytechniquesone.Level-of-detailarecommonly(LOD)usedandimage-tooftypetwoprimitives,whileocclusiontocullingreduceaimstheiseliminateLODsusedroutinely,primitivesandofthetypethree.Viewfrustumcullingnoculling.simpleorimpostorsisbecominguseofmoreautomatically-generatedcommon.However,mainCurrentandgeneralocclusionsolutionscullingarealgorithmsknownforfallocclusionels,categories.Somearespecifictocertaintypesintoofmod-twoapplicablesuchasproachestoarchitecturalgeneralenvironments.orurbanenvironmentsTheandnotpre-processingeithergraphicsableoccluderspipelines,ofrequirevisibility,veryspecializedhardware,moregeneralextensiveap-intheorscene.

thepresencemultipleofpasseslarge,usingeasilymultipleidentifi-MainthatResults:Wepresentanovelocclusionture.ismodel.Itsimple,conservative,general,andprogressivecullingmethodinna-approximateBasedbeginsonbytheprecomputingsubdivision,awespatialrendersubdivisiontheprimitivesoftheinwevisibilityusehardware-basedfront-to-backorder.Asrenderingprogresses,andtialzbufferofmorewrites,distantocclusionscanvolumesordepthqueriestotesttheconverttheofspace.boundariesWedisablecolorwouldcells,behaveandbeenqueryrendered.thehardwareIfthetoprimitivesseewhetherofthespa-inacellanywouldpixelsWeoccluded,tialenginesubdivisions.presentresultsweavoidsendingthemtothegraphicscard.forefficientWefromtraversalalsobothuseuniformofthetheuser-programmableandhierarchicalspa-subdivisions.

vertexfiedTheocclusion-queryhardwarescanconvertselsity.wouldprimitivesThefirstbeaffected.todeterminewhetheranyframe-bufferthespeci-pix-oneswidelyTheseavailable,queriessuchvaryasinthefunctional-OpenGLcullingqueryextensionfromHewlettPackard1,performedonepipelineatsionstheofcullingstallatime.whileUnfortunately,thistestcouldresultinatests,waitingincludingforaresults.newerMorerecentver-testsstallbypipeliningqueriesonmultipleoneprimitives.fromHP,Theseavoidprimitivesalsoseparatepipelinefromthetheprocedurecallstorenderthequeryrendering.canWebekeptareusingfullcallwithtoobtaintheresults.ThusthetheeitherNVIDIAotherOpenGLqueriesorextensionnormalGLqueryNVhardwareocclusionavailablequery2,onwhichtheGeForce3exploitstheandocclusion-GeForce4

1http://oss.sgi.com/projects/ogl-sample/registry/HP/occlusiontest.txt2

http://oss.sgi.com/projects/ogl-sample/registry/NV/occlusionquery.txtPage1

cards.

triangles.WetestedoverWetheobtain,algorithmonaverage,onamodelafactorcontainingoffour13speedupmilliondifferenceview-frustumrateoncullingalone.However,theperformancethespeedupdifficultofoverframestentimes.ismoreThis,dramatic,withaframe-depthoverheadcomplexity.queries.associatedNotewiththecullingofalgorithmcourse,includesandthethesystem.WeIftherethathavenotisnoperformanceseenocclusion,thisonathewillcomplexqueriesvarywithmodel.willdepthslowTheseOurinclude:

occlusioncullingapproachhasseveraladvantages.•Itveryrequiresdifficultnoproblemexplicit[ZMHH97,occluderselection,KS01].whichisa•UnlikeHyper-Zpurelyduceorhardware-basedmethodslikeATI’sducesdemandsNVIDIA’sthebandwidthonfill,totheZ-Cull,themethodwhichgraphicswearecard.presentmeantalsotore-re-•Ourmakesapproachinvolvesverylittletivityornoanyassumptionexplicitinformationrelatedtomodelpreprocessinglikebigformat,occluders.connec-and•Itperformsconservativeocclusionculling.

•ItwellcanbeeasilycombinedofveryaslargeLOD-andbasedcomplexalgorithmswithview-frustumenvironments.forinteractivecullingdisplayasOrganization:lowingTherestofthepaperisorganizedinthefol-work.manner.spatialThealgorithmsSectionbased2providesonuniformanoverviewandofrelatedformancesubdivisionandproposedresultsfutureinareSectionpresentedinSection3,andhierarchicaltheper-workinSection4.Weclose5.

withconclusions2RelatedWork

Inocclusionthissection,largedatasets.

cullingweandgiverelatedabrieftechniquesoverviewofforpreviousfasterdisplayworkonof2.1OcclusionCulling

Theacomputergivenproblemviewpointofcomputingisoneportionsofthefundamentalofthesceneproblemsvisiblefromthreegivendecadesgraphics.ofocclusionin[COCS01].andaItrecenthasbeenwellstudiedformorethanincullingInalgorithms.

thissurveysection,ofwedifferentgiveabriefalgorithmsoverviewiscializedManycullingalgorithmshavebeendesignedforspe-oncomposedcellsenvironments,andportals[ARB90,includingTel92]architecturalandurbanmodelsdatasetsbasedWWS00,tainWWS01].oflargeoccludersHowever,[CT97,theymayHMC+notbe97,SDDS00,numbersignificantofsmallcullingoccluders.

onlargeenvironmentscomposedabletoofob-asifiedAlgorithmsmate,basedonforwhethergeneraltheyenvironmentsarecanbebroadlyclas-archieswhetheraortheyuseobjectspaceconservativeorimageorspaceapproxi-hier-tiallyregion.Thewhetherconservativetheycomputealgorithmsvisibilitycomputefromtheapointortives,[CT97,plusvisibleasmallset(PVS)thatincludesallthevisiblepoten-primi-hand,theGKM93,approximateHMCnumber+algorithms97,ofKS01,potentiallyincludeZMHH97].occludedmostofOnprimitivesthethevisible

otherSubmittedtoJournalofGraphicsToolsobjects[BMH99,butKS00,mayalsoZMHH97].

cullawaysomeofthevisibleobjectsorformboundingObjectspacevolumealgorithmshierarchies;makehowever,useofspatialitishardpartitioningtoper-erscludingwith“occluderobjectfusion”spacemethods.onscenesImagecomposedspaceofsmallocclud-hierarchicalthehierarchicalallyocclusionmapsZ-buffer(HOM)(HZB)[ZMHH97][GKM93,algorithmsin-areGre01]orapproachmoreingpresentscapableaofprogressivecapturingoccluderschemethatfusion.Thegener-HZBitetneedstheZ-pyramidspecialhardwareafterrasterizingtosupporteachprimitive.involvesHowever,updat-whereal.ware)passandit[GKM93]rendersusesitthehasalsopresentedthatatwo-passcapability.approach,Greenetoculloccluders,thegeometry.buildsaTheHZB(e.g.insoft-tionapproximatehardwareapproachforthatocclusionmakesuseculling.oftexture-mappedHOMItisalsoabletorasteriza-isatwo-performparameterscullingbasedonvaryingtheopacitythresholdsitsalleffectivenessusedtheforegrounddependsinocclusionoccluders.

onbeingmapsable[ZMHH97].toefficientlyHowever,selectcanItronmentscomputeiswidelythebelievedPVSatthatinteractivenoneofratesthecurrentforcomplexalgorithmsenvi-threetheirperformance.

differentoncurrentapproachesgraphicshavesystemsbeenproposed[ESSS01].toRecently,improveRegion-basedvisibility[DDTP00,foravisibilityalgorithms:Thesepre-computescenesSDDS00,regionofWWS00].spacetoreduceMostofthethemruntimeworkoverheadwellisaatradeoffwithlargebetweenorconvexthequalityoccluders.oftheNevertheless,thereforberegioncullingextremelyandtheonscenesconservativememoryoverhead.PVSestimationforcomposedorThesealgorithmsmayofnotsmallableoccluders.

toobtainsignificantHardwarevisibilityvisibilityqueries:Atheirtions.graphicsqueriessystemshavebeentoaccelerateaddednumberbymanufacturersofimage-spacetosions,[BMH99,itemThesebufferincludetechniques,theHPATI’socclusionvisibilitycomputa-HyperZcullingexten-varies[KS01]basedKS01,ontheGre01,modelMBH+and02].Theirextensionseffectivenessetc.GLcationHPhasocclusionpresentedtestatwo-passtheapproachunderlyingthatutilizeshardware.thethesetoimprovetheperformanceand[Gre01]ofhasHZB.proposedAscomparedamodifi-tosivefeaturesocclusionapproaches,cullingwepresentalgorithmasimplethatmakesandeffectiveuseofprogres-vertexprograms.

ofgraphicscards,includingdepthqueryteststhenewandSeparateics[WWS01].systemvisibilityasavisibilityserver:Theserverusehasofanbeenadditionalproposedgraph-byparallelurbanwithItthecomputesmainrenderingthePVSforaregionatruntimeinalgorithmenvironments.which[WWS00]However,pipelineandworkswellfortoitusestheoccludershrinkingmetricworkswellonlycomputeiftheoccluderstheregion-basedarelargeandvisibility,volu-thehaveuser’sinnature.motion.TheMoremethodrecently,alsomakesBaxterassumptionsetal.aboutforusesinteractiveusedatwo-pipelinewalkthroughbasedofcomplexocclusion3Dculling[BSGM02]environments.algorithmwithahierarchiesvariationofoftwo-passlevels-of-detail.

HZBalgorithmandcombinesItitPage2

2.2InteractiveDisplayofLargeDatasets

Otherbasedapproachestofasterdisplayrelyontheuseoftechniques.representationsgeometryImage-basedortheimpostorsuseofcanmultipleimage-beusedaccelerationtoreplacetheocclusionframedistantrate.Impostorsfromthecanviewpointbecombinedandtherebyspeedupmodelto[ACWculling+99].usingHowever,acellbaseddecompositionwithLODsofandthepling.

poppingordis-occlusionartifactstheusebecauseofimpostorsofpoorcansam-leadbeenAframeworkgreepresentedinto[ASVNB00].integrateocclusionIttriescullingtoestimateandLODshaslectofvisibilityofeachobjectinthePVSandusesitthetode-se-algorithmsanappropriateLOD.However,nogeneralandefficientofareknownforaccuratelyestimatingthedegreeothervisibilityinscenescomposedofsmalloccluders.An-tionintegratedapproachusestheprioritized-layeredprojec-renderingvisibilityformstheapproximate[ESSS01].approximationvisibility,Theresultingalgorithmwithview-dependentasopposedrenderingalgorithmper-high.

runtimeoverheadforlargecomplexenvironmentstoconservative,canandbe[FKST96]TheUCBerkeleycomputationscombinedhierarchicalArchitecturealgorithmsWalkthroughwithsystemThe[Tel92]andLODsforarchitecturalvisibilitymodels.chicalBRUSHmodels.representationsystemfor[SBM+large94]mechanicalusedLODsandarchitecturalwithhierar-datacullingstructureTheQSplatthatcombinessystem[RL00]viewfrustumelegantlyculling,usesbackfaceasinglesivefastdisplayandLODoflargeselectionmesheswithatpointinteractiverenderingrates.forprogres-ray-tracing.approachcomputationIttoalsorenderprovideslargeamodelssolutionisbasedoninteractiveAnotherdistributeddescribedray-tracingortheocclusiontothevisiblesurfaceofproblem.Afastalgorithmforatcluster4−5in[WSB01].IthighlycanrendercomplexthePowerplantmodelshasmodelbeenofframessevenadualsecondprocessorat0PCs.

×480pixelresolutionona3Algorithm

WespatialbeginbysortingthemodelgeometryintobinsbasedonavisionEachcellsubdivision.todetermineWecanifitstestcontentsthevisibilityofeachsubdi-drawncelltheinthecancurrentonlybeshouldberendered.frame.testedagainstgeometrypreviouslythespatialTherefore,wewouldliketotesteye.

subdivisioncellsinafront-to-backorderingfromometryAnocclusiontion.tothegraphicsquerycardisaccomplishedfortransformationbysendingandqueryge-callgeometrythatTocompletereturnspassedwhethertheocclusionthedepthorquery,wemakearasteriza-functiontest.

notanyfragmentofthequeryformWefirstdescribeasimpleimplementationchicalgrid.approachesspatialWethenproceedtodescribehowtousinguseahierar-auni-thenecessarywesubdivisionocclusiontaketoreduce(nestedqueries.

thegrid).amortizedSectioncost3.4ofdescribesmakingsimplicityThechoicenestedorcomplexityofspatialofsubdivisiontraversal.typedeterminesthebeenthemade,grid.suchOtherchoicesforspatialsubdivisionWeuseauniformcouldhaveordent,bestassubdivisionasaisevidencedschemeBSPtree,byexperienceisnon-trivial,orasimpleintheandoctree.raytacingmodelChoosingdepen-litera-

SubmittedtoJournalofGraphicsToolsFigure1:deemedAlgorithmOverview.Thefirstcellistestedanddered.SomeAllvisible(green),soallintersectinggeometryisren-notvisibleofthethe(gray).cellscellsininthethesecondfirst”slab””slab”arearedeemeddisoveredvisible.tobeture.onamortizingOurchoicetheofsetupauniformcostinourgridandnestedgridisbasedever,Wemayalsohaveusedaboundingiterativeboxtraversalscheme.termsboundingboxhierarchiesraisefurtherhierarchy.complicationsHow-inmore,oftiveforthetraversaltheoriginalorderandintelligentconstruction.Further-purposeobjectofvisibilitydefinitionstesting.

areoftenquiteineffec-3.1UniformGridDecomposition

Modelangleassignedthattrianglesintersectsarefirstmoresortedthanintoauniformgrid.ATri-ofsharedtotriangleseachcellatthatitintersects.onegridWeelement,returntoorthecell,issueisorderAtvisibility.withrenderrespecttime,tothethethegridendofeye-point.istraversedthissection.

Eachinafront-to-backintersectAnocclusiontheIfthecellcellarequeryrendered.

isfoundtobevisible,cellalltrianglesistestedthatforforauniformgridcellisasfollows:1.Turnoffzandcolorwrites

2.Renderthecell(acube)asquerygeometry

3.Obtaingeometrythepassedresulttheastoz-test.whetheranypartofthequeryfragmentsTheresultwouldpassedofthetheocclusionz-test.Ifquerytheisresultintermsiszero,ofhowthemanyble,mechanismnonenotofbeitsvisible.contentsSincearethevisible.boundingThiscubeocclusionisnotcubevisi-GLframeIfNVisprovidedbytheNVIDIAOpenGLextensionqueryatriangleocclusionintersectsquery.morethanonegridelement,beeningrenderedcounterinischeckedthecurrenttoframe.seeiftheThistriangleistoavoidhasalreadyare-renderingitmultipleanytimes.trianglesWefoundsharedthatbetweenthisisfasterrender-twocells.

thansimplyPage3

Figure2:Thisviewshowsascreenshotfromtherunningsystemwiththegridcellsrenderedinwireframe.Athirdperson

viewfromthesideshowstheviewfrustumwiththevisiblecellsrenderedagaininwireframe.Thegeometryextendsoutsidethecellsbecausealltrianglesthatintersectthevisiblecellsarerendered(trianglesarenotclippedtocells.)Thethirdimageshowsthesamethirdperson’sviewusingonlyviewfrustumculling.

3.2NestedGridDecomposition

Theeffectivenessofauniformgridishighlydependentontriangledistribution.Cellsthatcontainmanyprimitivestendtoalsocontainmanyoccludedprimitivesthatarenotculled.Inordertoalleviatethisproblem,weextendthealgorithmpresentedabovetoincludeahierarchyofgrids.Cellsfoundtohaveanassociatedsetoftrianglesabovesomethresholdaresubdividedfurther,recursinguntilamaximumdepthisreached,ornocell(leaf)hasmorethanthethresholdnumberoftrianglesassociatedwithit.

Thenestedgridistraversedinthesamefront-to-backmannerastheuniformgrid,testingforvisibilityofeachcell.Inthiscase,however,ifacellisdeterminedtobevisible,andcontainsasubgrid,werecursetotraverseitscontainedgrid.

Thealgorithmtokeepthepipelinefullisasfollows:

Foreachslab,whereaslabisacollectionofcellsasdescribedinSection3.3:

1.Getthenextncellswithintheslab,

wherenisthemaximumnumberofocclu-sionqueriesthatmaybeinthepipelineatonetime2.Fori=1ton

•RenderCiquerygeometry(zandcolorwritesoff)

3.Fori=1ton

•GetresultofqueryforCiquerygeometry•IfCiisvisible:

–Renderthemodelgeometryasso-ciatedwithcellCi

3.3Traversal

Efficienttraversalinafront-to-backmannerisimportant.Weneedtoquicklydeterminethenextcell.Choosingcellssuchthatgeometryinlatercellsdoesnotoccludegeometryinearliercellsisimportanttothesuccessofaprogressiveapproach.Ourtraversalisavariantoftheaxisalignedslabsusedinvolumerendering.Weuseslabsthatareequivalenttorasterizedplanesapproximatelyorthogonaltotheviewvec-tor.

3.4EfficientQuerying

Theperformanceoftheoverallalgorithmisdeterminedbythenumberofdepthqueriesthatwecanperforminthegiventimeframe.Themoreocclusionquerieswecanper-form,themoremodelgeometrywecanpotentiallycull.Wehavethereforemadeanefforttoreducethecostofocclusionqueries.Thissectionhighlightsourapproachtominimizeboththetimetorenderthequerygeometry,andthepipelinestallscausedbywaitingonqueryresults.

Theresultofanocclusionqueryonaparticularsetofquerygeometryisnotavailableuntilthegeometryhasfin-ishedrasterization.Thiscreatesapotentialforpipelinestalls.Wethereforetrytokeepthepipelinebusybysubmit-tinganumberofquerygeometrysetsatonce.Thisis,infact,anexplicitdesignintentionoftheGLNVocclusionqueryextension.

Betweenthetimeaqueryissubmitted,andthetimeweneedtheresults,anumberofotherqueriesandmodelgeom-etryhasbeensubmitted.Thiswillreducepipelinestalls.Wewantallvisiblegeometryintersectingslabitoberen-deredbeforebeginningthevisibilitydeterminationofslabi+1.Otherwise,westandtoloosesomeamountofcullingduetoocclusionofpartsofslabi+1bygeometryinslabi.Theregularityofourocclusionrepresentationallowsustoexploitaprogrammablevertexshadertomoreefficientlyrenderthecubesofthesubdivision.Wereducethenecessaryhosttographicsdatatransfersize,andprovideformoreef-ficienttransformationofthesubdivisioncubevertices.Foreachsubdivisiongrid,wetransferworldspaceoriginofthegrid,anditsscale.Foreachcube,wesendthecubeindicesforacanonicalcube,andtheindicesdefiningwhichgridele-mentthecubewillrepresent.Thevertexprogramcomputesthepositionsofalleightverticesofthecube.

3.5Levels-of-detail

Thealgorithmwehavesofardescribedhelpstoreducethenumberofprimitivessenttothegraphicscardthatareoc-cludedorfalloutsidetheviewfrustum.Insomecircum-stances,theremainingtrianglesmaybetoomanytorender

SubmittedtoJournalofGraphicsToolsPage4

Average Frame Time and Average Number

of Queries vs. Cell Size

0.251600014000

0.212000sei)ce10000res0.15u( e8000Q rmeiT0.16000bmu4000N0.052000000

20

406080100

120

Number of Cells in Largest DimensionUniform Grid Frame TimeNested Grid Frame TimeUniform Grid Query CountNested Grid Query CountFigureThe3:AvgFrameRatementationsaverageframerateandandqueryAvgcountQueriesofthevstwoCell-Size:

olution.toTheareuniformgraphedhereasafunctionofthegridimple-res-cansmallercellsizeswhilegridimplementationthenestedgridisimplementationmoresensitivetheidenticalquerycompensateandplots.theHowever,throughsubdivision.plotsconvergetheframeThiscanbeseenbyascelltimesizemiminadecreases.

arenearlyatbeinteractiveusedtoalleviaterates.thisTheproblem.

useoflevels-of-detail(LODs)canTrianglesOursystemOcclusioncoulddoesthecullingstillnotofbeprecludetheuseofLODtechniques.primitivessortedintowouldcellsstillasalreadybedetermineddescribed.onwouldbasisobjectbeofAtandstoredthespatialwhichsuchrepresentationthatsubdivision.theyareHowever,theprimitivesofidentifiedtheobjectwiththeythebelongoriginalanruntime,whenthecontentsofacellaretoberendered,to.theLODpossiblecellthatselectionbelongistomade,andonlythosetriangleswithinstilltomaintainthethatintegrityLODareoftherendered.Thismakesitsion.

allowingforocclusioncullingwithoriginalthespatialLODs,subdivi-while4ImplementationandPerformance

Initsthisitsperformancesection,wemoreperformanceondescribeourimplementationandhighlightonaacomplexmodelofmodel.acoal-firedInparticular,wetestedofthan13milliontriangles.Muchofthepowerupperplantportionwithocclusionthemodelfrominthisconsistssectionofaarisescomplexnetworkofpiping.MostWeanaggregationoftheocclusionnotfromprovidedindividualbypipes,thebutmostfoundoutsidechallengethatthisportionofthemodelprovidedonepipes.oftheviewsofscenariothewholeformodel.

ourocclusionsystemasidefromthatOurshownbeginsresultsonanareuppergeneratedfloor,fromapaththroughthemodelinginthevideo).Thepathalongentersananexposedenclosurewalkway(asthroughthousandsthisarea.

ofpipesthroughasmallwindow,andcontain-wanderstiumTheofover,RAM.4machinetestrunsNotethatwithwereouraperformedonadualprocessorPen-applicationNVIDIAGeForceissingle4cardand2GBrequirethemoreconfigurationsthan1GBofusedRAMforoptimalforthepowerperformancethreaded.More-plantmodel.

donotSubmittedtoJournalofGraphicsToolsFrame Time

1.41.21)ces0.8( emiT0.60.40.20

Uniform GridNested GridView Frustum Culling OnlyFigure4:ourFrameTime:Thisfigurecomparesframetimeuniformbestimplementation.gridconfigurationimplementation,forthenestedgridimplementation,of

cullingtimesvastlyoutperformItisclearandviewfrustumcullingonlyviewthatfrustumbothsystemscullingwithocclusioncomparable.

fornestedgridanduniformgridimplementationsonly.FrameareTriangle Count

10000000

1000000)elac100000s gol( 10000tnuoC1000 elgnai100rT101

Uniform GridNested GridView Frustum Culling OnlyItem BufferFigure5:trianglesiblerenderedTriangleperCount:frameThisgraphshowsthenumberof

givenasonlyfordeterminedthenestedbygrid,anitemversustheactualnumbervis-uniformbuffer.Trianglecountsaresameimplementations.screenresolution(The800xitem800)buffergrid,asourrenderingandviewothertests.

usedfrustumthe4.1TimingResults

Therewithcantheareperformanceanumberofofuserourspecifiedmethod.ForparametersassociatednumbervaryIfofthetrianglesresolutioninaofthegrid,andtheauniformthresholdgrid,onwetheparticularthetimequery,celltorendercellthatwarrantanocclusiontest.islessthemodelgeometryassociatedwithathevaluesocclusionthenwetest.couldthanthetimetoperformanocclusionInsimplypractice,renderthecellcontentswithouttrianglesofquirements,whichthesetimes.Acellmayitishardintersecttopredictafewtheverypreciselargeascomparedwhenrenderedtothemaycellitself.

havehigherfill-ratere-differencesTimingcomparisonsForamongthresholdindicatednegligibleperformance1.

theresultspresentedhere,valuesweusedrangingathresholdfrom1valueto50of.withFigurevarying4showsgridresolution.theaverageWeframehavetimefoundofourthattestforpaththe

Page5

Visible Cell Percentage

45.00%40.00%35.00%el30.00%bisiV25.00% tnec20.00%reP15.00%10.00%5.00%0.00%

Unifrom GridNested GridFigure6:werelutiondeterminedThisgraphtionofthenestedtobegridvisible.showswhatsystemGivenpercentageiscomparablethatthetopofthecells

tothelevelresolu-reso-tohierarchy.

identifyoftheuniformgeometrygrid,tobeweculledseethatbeyonditismuchthetopmoreleveldifficultofthepowermaximumplantmodel,aimplementationdimensiongivesresolutionthebestbetweenresults.35Theandnested50intheassion.adeepertreeismakesmuchlesssensitivetothegridresolution,gridofItisclearfromFigureupfor4thatacoarsetoplevelsubdivi-tumouralgorithmismuchbetterthantheusingoverallonlyperformanceviewfrus-cullingculling.gridMoreover,approacheswas0The.36weresecondsaverageframetimefortheviewfrustum0.087whileand0for.ouruniformandnestedingcullingonlylargespikesintheframe088timeseconds,obtainedrespectively.withus-algorithm.

viewfrustumcullingarereducedbytheocclusionrameters:Forthenestedgridscheme,anglebranchingfactor,andsplittingweusedthreshold.twoadditionalIfthepa-tri-thehavecellcountissubdividedofagridcellisgreaterthanthethresholdvalue,orbestatotalfoundresults.

ofthatcells,abranchingaccordingandathresholdfactortotheofbranchingof410infactor.We,000eachproduceddimension,the4.2EfficiencyinOcclusionCulling

Weiblecompareactsetcomputedthenumberperframeoftrianglesbyourmethodinthepotentiallyagainstthevis-ex-thevisibleentitemtocolor.buffersetdeterminedbyanitembufferinFigure5.InByreadingtesteachbacktrianglethecolorisrenderedusingadiffer-updeterminethenumberofprimitivesvisiblebuffer,inweeachwereframe,ableourtoalsoalgorithmthescreentoexactlyspaceresolution.computethisIdeally,wewouldlikebuffer.governedbythediscretesamplingvisiblenatureset,ofthewhichframeisticalapproachvalueBysettingwithregardsoursplittingtoperformance),thresholdto150(animprac-terminedwithinafactorof10ofthenumberweofweretrianglesabletoculling13timesalonevisiblehigherproducesbythethanthetriangleitembufferde-fastestconfigurationcountsmethod.thatonViewfrustumforaveragenestedgridareapproximationgrid.

and7timeshigherthanthatfortheuniformisAmeasureoftheoverheadtivestheusedchangeonlyinfortriangleocclusion.throughput,incurredWehavenottofoundcountingattainthesethethroughput

theresultsprimi-SubmittedtoJournalofGraphicsToolsFigure7:view.ItconsistsPowerplantofmoreModel:than13Thismillionimagetriangles.

showstheoutside

forlionthebytrianglessystemperwithsecondviewfrustum(MTPS).cullingThisonlyisprimarilytobe5.23limitedmil-icsAGP3.79cardbandwidth,MTPSfastandenough.as2.17MTPSTheweareforsystemnotabletheuniformpresentedtofeedgridherethegraph-andobtainsnestedgrid,torenderrespectively.modelgeometry.

WeusedstandardOpenGLvertexarraysclusionOuralgorithmsionqueries.Therendersadditionalthegridboundariestoperformoc-put.stallsThequeryingremainingaccountsthroughputforpartgeometryreductionofthedecreaserenderedforocclu-isattributedinthrough-tothatoccurwhenwaitingformodelgeometrytothedropfinish,queriesinbeforerenderingadditionalquerygeometry.renderingThisresultcullinusingthroughputisthecostofperformingtheocclusionimprovedouralgorithm.performance,Ingeneral,ouralgorithmwillthanathehigherpercentagepercentagereductionoftheifocclusiondetectioncanintrianglestriangleinthroughput.theviewfrustumpowerWealgorithmplant,haveshownthepotentiallythatforavisiblecomplexsetmodeldeterminedsuchbyasthefrustumgridforonaaverageuniformisgrid18%methodofthegeometryourandintheviewthroughputmethod.inanoverallutilizationThesemeasuresperformanceof72increase.

%andare41far%,less9andthan%fortherefore,theatrianglenestedresult5Conclusion

Weacceleratehaveshownhowtoeffectivelyuseaity.ourThepresentedtherenderingdataofalsomodelsillustrateswithhighhardwarez-querytotheeffectivenessdepthcomplex-ofvisibleschemeintermsofachievingthegoalofrenderingcoststriangles,keepingthepipelinefull,andtheoverheadonlyapproach,associatedaflatgridwithwillourbemethod.suitableWeforbelievemostscenarios.

thatusingourPage6

Figure8:PowerplantModel:InternalViewfromourpath

6FutureWork

Thereexploitaremanyavenuesforfuturework.Wewouldliketoclusionframe-to-frameWequerycanculling,furthertheandreduceintegratecoherence,pipelinedifferentperformstallsapproachesapproximateoc-causedbyforwaitsLODs.forresults,andwishtopursuemoreeffectivetechniquesforaddresskeepingincorporatelargetheLODsamountspipelinefull.Ourcurrentalgorithmdoesnotasdiscussedofvisibleingeometry.Section3.5.

WewouldliketoocclusionCurrently,allcellsintheviewfrustumarecheckedforthearenestedcorrespondingterminateinthetopgrid,wechecktoalluniformthecellsspatialintheviewsubdivision.frustumthatFortheyarefilled.

thetraversalleveloftheofthehierarchy.gridinregionsItshouldofbethepossiblescreen,toassionAnotheractuallyisthefeatureoftheGLNVocclusionqueryexten-proximatepassabilitythetoreturnthenumberoffragmentsthatitythewouldbeocclusiondepthinfluencedcullingtest.Thiscouldbeusedinanap-bytheschemenumberwhereofrenderingprior-asz-test.ItcanbeusedtoselectanfragmentspassingWesuggestedinthecurrentOpenGLappropriateextensionspecification.staticLOD,toincrementaldynamicwouldalsoenvironments,liketoextendourocclusioncullingalgorithmruntime.

updateofthewhichspatialwouldsubdivisionbasicallyhierarchiesinvolveanatReferences

[ACW+99]

D.Aliaga,J.Cohen,A.Wilson,H.Zhang,C.Erikson,K.Hoff,T.Hudson,W.Stuerzlinger,E.Baker,R.Bastos,M.Whitton,F.Brooks,andD.Manocha.Mmr:Aninte-gratedmassivemodelrenderingsystemusinggeometricandimage-basedacceleration.InProc.ofACMSymposiumonInteractive3DGraphics,1999.

[ARB90]

J.Airey,J.Rohlf,andF.Brooks.Towardsimagerealismwithinteractiveupdateratesincomplexvirtualbuildingen-vironments.InSymposiumonInteractive3DGraphics,pages41–50,1990.

[ASVNB00]C.Andujar,C.Saona-Vazquez,I.Navazo,andP.Brunet.

Integratingocclusioncullingandlevelsofdetailthroughhardly-visiblysets.InProceedingsofEurographics,2000.[BMH99]

D.Bartz,M.Meibner,andT.Huttner.Openglassistedoc-clusioncullingforlargepolygonalmodels.ComputerandGraphics,23(3):667–679,1999.

SubmittedtoJournalofGraphicsTools[BSGM02]

B.Baxter,A.Sud,N.Govindraju,andD.Manocha.Gi-gawalk:Interactivewalkthroughofcomplex3denviron-ments.TechnicalReportTR02-013,DepartmentofComputerScience,UniversityofNorthCarolina,2002.

[COCS01]

D.Cohen-Or,Y.Chrysanthou,andC.Silva.Asurveyofvisibilityforwalkthroughapplications.SIGGRAPHCourseNotes#30,2001.

[CT97]

S.CoorgandS.Teller.Real-timeocclusioncullingformod-elswithlargeoccluders.InProc.ofACMSymposiumonInteractive3DGraphics,1997.

[DDTP00]

F.Durand,G.Drettakis,J.Thollot,andC.Puech.Con-servativevisibilitypreprocessingusingextendedprojections.Proc.ofACMSIGGRAPH,pages239–248,2000.

[ESSS01]

J.El-Sana,N.Sokolovsky,andC.Silva.Integratingocclu-sioncullingwithview-dependentrendering.Proc.ofIEEEVisualization,2001.

[FKST96]

T.A.Funkhouser,D.Khorramabadi,C.H.Sequin,andS.Teller.Theucbsystemforinteractivevisualizationoflargearchitecturalmodels.Presence,5(1):13–44,1996.

[GKM93]N.Greene,M.Kass,andG.Miller.Hierarchicalz-buffervis-ibility.InProc.ofACMSIGGRAPH,pages231–238,1993.[Gre01]

N.Greene.Occlusioncullingwithoptimizedhierarchicalz-buffering.InACMSIGGRAPHCOURSENOTESONVISI-BILITY,#30,2001.

[HMC+97]

T.Hudson,D.Manocha,J.Cohen,M.Lin,K.Hoff,andH.Zhang.Acceleratedocclusioncullingusingshadowfrusta.InProc.ofACMSymposiumonComputationalGeometry,pages1–10,1997.

[KCCO00]

V.Koltun,Y.Chrysanthou,andD.Cohen-Or.Virtualocclud-ers:Anefficientintermediatepvsrepresentation.RenderingTechniques2000:11thEurographicsWorkshoponRender-ing,pages59–70,2000.

[KS00]

J.KlowoskiandC.Silva.Theprioritized-layeredprojectionalgorithmforvisiblesetestimation.IEEETrans.onVisual-izationandComputerGraphics,6(2):108–123,2000.[KS01]

J.KlowoskiandC.Silva.Efficientconservativevisib-litycullingusingtheprioritized-layeredprojectionalgo-rithm.IEEETrans.onVisualizationandComputerGraphics,7(4):365–379,2001.

[MBH+02]

M.Meissner,D.Bartz,T.Huttner,G.Muller,andJ.Einighammer.Generationofsubdivisionhierarchiesforefficientocclusioncullingoflargepolygonalmodels.Com-puterandGraphics,2002.Toappear.

[RL00]

S.RusinkiewiczandM.Levoy.Qsplat:Amultiresolutionpointrenderingsystemforlargemeshes.Proc.ofACMSIG-GRAPH,2000.

[SBM+94]

B.Schneider,P.Borrel,J.Menon,J.Mittleman,andJ.Rossignac.Brushasawalkthroughsystemforarchitec-turalmodels.InFifthEurographicsWorkshoponRendering,pages3–399,July1994.

[SDDS00]

G.Schaufler,J.Dorsey,X.Decoret,andF.Sillion.Con-servativevisibilitypreprocessingusingextendedprojections.Proc.ofACMSIGGRAPH,pages229–238,2000.

[Tel92]

S.J.Teller.VisibilityComputationsinDenselyOccludedPolyheralEnvironments.PhDthesis,CSDivision,UCBerke-ley,1992.

[WSB01]

I.Wald,P.Slusallek,andC.Benthin.Interactivedistributedray-tracingofhighlycomplexmodels.InRenderingTech-niques,pages274–285,2001.

[WWS00]

P.Wonka,M.Wimmer,andD.Schmalstieg.Visibilitypre-processingwithoccluderfusionforurbanwalkthroughs.InRenderingTechniques,pages71–82,2000.

Page7

[WWS01]P.Wonka,M.Wimmer,andF.Sillion.Instantvisibility.InProc.ofEurographics,2001.

[ZMHH97]

H.Zhang,D.Manocha,T.Hudson,andK.Hoff.Visibil-itycullingusinghierarchicalocclusionmaps.Proc.ofACMSIGGRAPH,1997.

SubmittedtoJournalofGraphicsToolsPage8