Effective Compression Techniques for Precomputed Visibility

for Precomputed Visibility

MichielvandePanne

A.JamesStewart

DepartmentofComputerScience,UniversityofToronto

fvan,jstewartg@dgp.utoronto.c a

Abstract. Inrenderinglargemodels,itisimportanttoidentifythesmallsubset

ofprimitivesthatisvisiblefromagivenviewpoint.Oneapproachistopartition

theviewpointspaceintoviewpointcells,andthenprecomputeavisibilitytable

whichexplicitlyrecordsforeachviewpointcellwhetherornoteachprimitiveis

potentiallyvisible. Weproposetwoalgorithms forcompressingsuchvisibility

tablesinordertoproducecompactandnaturaldescriptionsofpotentially–visible

sets. Alternatively, thealgorithmscanbethoughtofastechniques forcluster-

ingcellsandclusteringprimitivesaccordingtovisibilitycriteria.Thealgorithms

aretested onthreetypesofsceneswhichhaveverydifferentstructures: ater-

rainmodel, abuilding model,and aworldconsisting ofcurvedtunnels. The

resultsshowthatthenaturalstructureofeachtypeofscenecanautomaticallybe

exploitedtoachieveacompactrepresentationofpotentiallyvisiblesets.

1 Introduction

Thevisibilityproblemistodeterminewhichsceneelementsarevisiblefromaparticular

viewpoint.Algorithmsthatsolvethisproblemareveryexpensiveintime,inmemory,or

incomplexity.Forthesereasons,real–timeapplicationswilloftenprecomputevisibility

information,storeit,andlateruseittoacceleraterendering.

Storageoftheprecomputedvisibilityinformationcanrequireaverylargeamount

ofmemory. Thispaper describestwoeffectivetechniquestocompressprecomputed

visibilityinformation. Thesetechniquesareverygeneralandmaybeusedinapplica-

tionsasvariedasarchitecturalwalkthroughs,terrainyovers,andtunnelroaming.

Techniquesthatprecomputevisibilitytypicallydividespaceinto regionsandde-

terminewhatpartsofscenearevisiblefromeachregion. Thisisacommonstrategy:

TellerandSequin[17]divideabuildingintoroomsand,foreachroom,computethe

otherroomsvisiblefromit. YagelandRay[19]subdividespaceintoaregulargridof

cellsanduseadifferentmethodtocomputecell–to–cellvisibility.Gamesinmaze–like

environmentsoftenhaveroom–to–roomvisibilityexplicitlystoredinatable.

Thesetechniques canbethoughtofas usingavery coarseform ofclusteringto

reducememory requirements: By storingcell–to–cell visibility, ratherthancell–to–

polygonvisibility,groupsofpolygonsinthesamecellareclusteredanddonotneedto

beexhaustivelyenumerated.

Thiscoarseformofclusteringhasseveraldrawbacks:polygonclustersarerestricted

tocorrespondone–to–onetoviewpointregions;viewpointregionsthemselvesarenot

clusteredatall; apolygonclustermustbe entirelyrenderedifevenatinyfractionof

it is visible; and it is unclearhow tocreate optimal clustersin less well-structured

environments,suchasterrains.

putationstepdetermineswhichpolygonsarevisiblefromeachregion.Abooleanvis-

ibilitytableencodesthisinformation:entry(i;j)ofthetableisTR UEifpolygonj is

potentiallyvisiblefromsomepointinregioni.Giventhenesubdivisionofspaceand

thepossiblylargenumberofpolygons,thevisibilitytableispotentiallyhuge.

Thispaper'sprincipalcontributionconsistsoftwomethodstocompressthevisibil-

itytable:

The rstisalossycompressionmethodwhichmergesviewpointregionsand

mergespolygons. Thismethodmayconservativelydeemapolygontobevisi-

blewheninfact itisnot. Likeallconservativevisibility algorithms,thisdoes

notposeaproblemaslongashiddensurfaceelimination(e.g. Z–buffering)is

performedduringrendering.

Thesecondisalosslesscompressionmethodwhichcontructsagraphofview-

pointandpolygonclusters.Visiblepolygonscanbeenumeratedbyperforminga

verysimpletraversalofthisgraph.Thislosslessmethodnevermistakenlydeems

apolygontobevisiblewhenitisnot.

Thesecompressionmethodshaveseveraldesirablefeatures:

Acombinationofthetwocompressiontechniquesyieldsbettercompressionthan

eitheralone.

Thelevelofcompressionmaybechosentooptimizememory,occlusioninfor-

mation,orsomeratioofthetwo.

Thesetechniquespermitveryefcient“randomaccess”decompression:Forany

particularviewpointregion,allvisiblepolygonscanbequicklyenumerated.

Thepolygonandviewpointclustersareautomaticallyadaptedinanaturalway

to theenvironment,making thisa very general method. Forexample, in our

experiments(presentedinSection6)wediscovered:

– interrains,polygonsareclusteredinseparatevalleysandonpeaks;

– intunnels,viewpointsareclusteredincontiguoustunnelsections;and

– inbuildings,polygonsareclusteredaround“opencorridors”fromwhichall

ofthepolygonsoftheclusterarevisible.

Thebeautyofusingthevisibilitytableisthatviewpointclustersandpolygonclus-

tersmaybetreatedidentically:oneconsistsofaclusterofrows,whiletheotherconsists

ofaclusterofcolumns. Thisobservationyieldsverysimplealgorithmswhichdonot

needtoknowanythingabouttheunderlyingstructureoftheviewpointregionsorthe

scenepolygons.

2 RelatedWork

Inworkofsimilarspirittoours,YagelandRay[19]precomputevisibilityinformation

foratwo–dimensionalsceneusingaregularsubdivisionofspace.Theirprincipalcon-

tributionisanelegantalgorithmtocomputecell–to–cellvisibility,buttheyalsosuggest

clusteringcellsofsimilarvisibilityusingcriterialikethoseofourlossycompression

algorithm. Wangetal.[18] combineprecomputedpotentially-visiblesetswithdetail

simplicationinregionswherethesetsbecomeverylarge.

Mostmethodsthatprecomputevisibilitydividetheviewpointspaceintocellsand

computecell–to–cellvisibility. Thishastheimpliciteffectofclusteringpolygonsin

detailedvisibilityinformation.TellerandSequin[17]divideabuildingintoroomsand

computeroom–to–roomvisibility. CoorgandTeller[6]exploitthe presenceoflarge

occluderstoperformocclusioncullingforaviewpoint.Cohen-Oretal.[2]exploitlarge

convexoccluderstocomputecell-to-objectvisibility.Plantinga[13]usesasmallsetof

effectiveoccludersandcomputesvisualeventsamongtheoccludersinordertopartition

theviewpointspaceinto2Dcells.

CoorgandTeller[5],GigusandMalik[7],andCohen-OrandZadicari[4]allex-

ploitfeaturesofaspectgraphstoproduceincrementalupdatesofvisibility. Yageland

Ray[19]alsosuggestrecordingonlychangesinvisibilityinordertocompresstheir

cell–to–cellvisibilityinformation.

Anotherclassofvisibilitymethodscomputesvisibilityduringtherenderingprocess.

SomeexamplesincludethehierarchicalZ–bufferofMeagher[12]andofGreene,Kass,

andMiller [9], the hierarchical coveragemasks of Greene [8], and the hierarchical

occlusionmapsofZhanget al[20]. An advantage ofthese techniquesis thatthey

cancope withdynamicscenes. However, thesetechniqueswork bestwhenasetof

largeoccluderscanrapidlybeidentiedforthecurrentviewpoint,whichisnotalways

possible. Thesetechniquescanpotentiallybeusedinconjunctionwithacompressed

visibilitytable,usingatabletoachievethesameresultasalargeoccluder.

Therehasalsobeenasubstantialamountofworkinclusteringforglobalillumi-

nation. Hierarchicalradiosity[10],forexample,imposesahierarchicalstructureon

thescenesurfacesandcomputesenergytransferbetweendifferentnodesinthishier-

archy. Analternative“hierarchyofuniformgrids”isdescribedbyCazals,Drettakis,

andPuech[1]. However,theprincipalexpenseinglobalilluminationliesindetermin-

ingwhetheronesurfaceseesanother,andclusteringusuallyoccursbeforevisibilityis

computed,whichisoppositetowhatwedowhencompressingthevisibilitytable.

3 TheVisibilityTable

Visibilityisencodedinabooleantable,inwhicheachrowinitiallycorrespondstoone

viewpointcellandeachcolumninitiallycorrepondstoonepolygon. Thetableideally

encodesthepartialvisibility:theentryinrowi,columnjisTR UEifandonlyifpolygon

jisatleastpartiallyvisiblefromsomepointincelli.However,ourlossycompression

canallowsomeocclusionstobelost,inwhichcasethetablewillencodeaconservative

visibilityset[2],whichisasupersetoftheexactpartial-visibilityset.

Anydivisionofviewpointregionsmaybe used; ourexperimentsusedaregular

voxelsubdivisionofspace.Onecouldjustaswelluseanothersubdivision,suchasan

oct–tree,abinaryspacepartition,orak–dtree.Similarly,anydivisionofthescenemay

beused;ourexperimentsusedsinglepolygons. Onecouldalsopre–clusterpolygons

manually,givensomeknowledgeofthescene,oronecouldgointheoppositedirection,

subdividingverylargepolygons(e.g. imposters)ifitislikelythatonlyapartofthe

polygonwillbevisibleatanytime.

Givenavisibilitytable,renderingissimple: Locatetherowcorrespondingtothe

regioncontainingtheviewpointandrendereachpolygonwhosecorrespondingcolumn

containsthevalueTR UE.Inorderthattherenderingtimebeproportionaltothenumber

ofvisiblepolygons,eachrowofthe tablecanbestoredasalinkedlist oftheTR UE

entries,oralternatively,theFALSEentriesmustberun–lengthencoded.Wechoosethe

latter.Arowisrepresentedbyasequenceofintegers,whereeachintegeristhenumber

ofFALSEentriesbeforethenextTR UEentry. Forexample,thesequence5,3,0,0,1

indicatesthatTR UEentriesoccurincolumns5,9,10,11,and13:

0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 ...

The run-length encodingscheme describedabovecan be usedas a simple low-

costmethodforstoringthe visibilitytableinaneasy-to-decodefashion,comparable

toconventionalsparse-matrixstorage techniques. Thejob ofourcompressionalgo-

rithmsistodomuchbetterthanthis,andthusourcompressionalgorithmsmakeuseof

thisrun-lengthencodingonlyasalaststep. Itisworthremarkingthat,unlikeconven-

tionalsparse-matrixstorage,itwouldalsobepossibletorun-lengthencodethenon-zero

(TRUE)elements,giventhatthereisonlyoneassignablenon-zerovalue.Thus,these-

quence5, 1, 3, 3,1, 1, 5, 1could indicatethatthereare5FALSE entries,followed

byoneTRUEentry,3FALSEentries,etc. Inmanysituations, however,thiswillbe

lesscompactthansimplyrun-lengthencodingtheFALSEentries,giventheexpected

sparsityofTRUEentriesindenselyoccludedenvironments.Aswell,ourcompression

techniqueswill rstproducevisibility tableswhichareevensparser (butencodethe

sameinformation),andthenusearun-lengthencodingstepasanalcompressionstep.

ExperimentshaveshownapreponderanceofshortrunsofFALSEentries.Inorder

toencodetheserunswithlittlememory,eachrunisrepresentedwitheitheronebyteor

threebytes: Arunof0to254FALSEentriesisencodedwithasinglebytecontaining

therunlength,whilearunof255to65535FALSEentriesisencodedwithasinglebyte

of255followedbytwobytescontainingtherunlength.

Givenasetofviewpointregionsandasetofpolygons,the initialvisibilitytable

maybeconstructedinanyoneofmanyways.Sincetheinitialtableconstructionisnota

contributionofthispaper,weuseafairlynaiveapproachthatsamplesvisibilityusingan

itembuffer:Fromseveralpointswithineachviewpointregionandfromsixdirections

aroundeachsuchpoint,thesceneisrenderedintoanitembufferinwhicheachpolygon

isassigned auniquecolour. Aquick traversal ofthe itembufferdetermineswhich

polygonsarevisible. Oneproblemwiththeitembuffermethodis,ofcourse,thatit

isnotconservative: Polygonscanbemissedduetothelimitedresolutionoftheitem

bufferandthediscreteviewpointsamplingdonewithintheviewpointregion.However,

artifactscausedbysuchmissingpolygonswill,bydenition,likelybesmall. Another

problemisthatitistimeconsuming,sincethescenemustberenderedmanytimesfrom

manydifferentviewpoints. FortheexperimentsdescribedinSection6,thevisibility

tablestookseveralhourstocomputeusingsoftwarerenderingon166MhzPC.Other

methodsmaybeusedtoconstructtheinitialvisibilitytableusinggeneralmethods[19,

15,2],ormethodsforspecicenvironments[16,3].

4 LossyCompressionAlgorithm

Thelossycompressionalgorithmcompressesthevisibilitytablebymergingrowsand

bymergingcolumns.

TworowsaremergediftheyhaveasimilarsetofTR UEentries.Themergedeletes

thetwooldrowsandinsertsanewrowthatisthelogicalORoftheoriginaltwo

rows. Thiscorrespondstomergingtwoviewpointregionsthathavesimilarsets

ofvisiblepolygons.Themergecreatesanewmeta–regionfromwhichisvisible

the union of the polygonsvisible from the two originalregions. The logical

ORmaintainsconservativevisibility: Ifapolygonwas visiblefromoneofthe

originalregions,itisvisiblefromthemergedregion.

TwocolumnsaremergediftheyhaveasimilarsetofTR UEentries. Themerge

theoriginaltwocolumns. Thiscorrespondstomergingtwopolygonsthathave

identicalvisibilitystatusinmostviewpointregions. Thatis,formostviewpoint

regionseitherbothpolygonsarevisibleorneitherisvisible. Themergecreates

anewmeta–polygonwhichisvisiblefromallregionsfromwhicheitheroneof

theoriginalpolygonswasvisible. Again,thelogicalORmaintainsconservative

visibility.

Todeterminewhich`similar'setsofcolumnsorrowsshouldbemerged,thelossy

algorithmmustdeterminethebenetandthecostofapotentialmerge.

Thebenetofamergeisequaltothereductionintablesize.Sincethetableisrun–

lengthencoded,itssizeisproportionaltothenumberofTR UEentriesandthebenetof

amergeisequaltothenumberofTR UEentriesthatareeliminated.

Thecostofamergeisequaltothenumberofocclusionsthatare“lost.”Anocclu-

sionisrepresentedbyaFALSE entry,whichindicatesthatsomepolygonisoccluded

fromviewpointsinsomeregion.Anocclusionis“lost”wheneverthelogicalORisap-

pliedtotwoentriesofdifferentbooleanvalues,TR UEandFALSE:TheresultoftheOR

isTR UE,andtheoriginalFALSEvalue,representinganocclusion,islost. Notethatno

informationislostwhentwoentriesofequalvalueareORed.

Ifaroworcolumnistheresultofnpriormerges,eachFALSEentryinthatrowor

columnrepresentsnocclusions.IfsuchaFALSEentryislostinamerge,thecostisn

lostocclusions,ratherthanone.Thus,inorderthatcostsbecorrectlycalculated,each

rowandcolumnmustrecordthenumbermergesofwhichitistheresult.

Our slowgreedyalgorithmevaluatesallpairsofrowsandallpairs ofcolumns,

andmergesthepairwiththelargestratioofbenet–to–cost.Thisisrepeateduntilsome

user–determined criterionissatised. Thisalgorithmis slowbecauseeachiteration

takestimequadraticinthenumberofrowsandinthenumberofcolumns. Forlarge

sceneswithmorethanafewthousandinitialviewpointregionsorinitialpolygons,the

slowalgorithmisunusable. However,thegoodfeatureofthe slowalgorithmisthat

it performsprogressivecompression, therebyallowing controloverthe compromise

betweenlostocclusionsandtablesize.Ausermightexpresstheirdesiredcompromise

intermsofatargettablesizeoralimitonthepercentageoflostocclusions.Weusethe

latterinourexperiments,stoppingthelossycompressionwhen5%ofocclusionshave

beenlost.

Analternativefastgreedyalgorithmisusedinpractice,asfollows:Axedfrac-

tionoftherowsarechosenas“seedrows.” Eachremaining“non–seedrow”istested

againsteachseedrowandismergedwiththeseedrowofmaximumbenet–to–cost

ratio. Asimilarprocedureisthenperformedwiththeresultingcolumns. Inpractice,

wechoosetheseedrowsusingaregularsamplingpattern.Ifthelistofsceneprimitives

hassomestructure,aswemightexpect,thenthishelpstodistributetheseedrowsinan

equitablefashionaroundthescene.Thefastgreedyalgorithmproducesexcellentcom-

pressionandwasusedinallthelossycompressionexperimentsreportedinSection6.

5 LosslessCompressionAlgorithm

Analternativecompressionalgorithmcantakeadvantageoflocally-similarbutglobally-

dissimilarvisibilityrelationships. Forexample,viewpointslocatedinthehallwayofa

buildingallsharethevisibilityofaroomattheendofthehallway,buttheymaynot

sharethe visibilityofroomslocatedalong thehallway. Similarscenariosalsooccur

innon-architecturalscenes,aswillbeillustratedbytheexperimentalresults. Interms

numberofTR UE values,butthatarenotmergedbythelossyalgorithmbecausethey

alsodifferinalargenumberofotherentries(i.e. theirmergecostistoohigh). The

losslesscompressionalgorithm,identiesthesesituationsandmergesonlypartofthe

roworcolumn.

Thelosslesscompressionalgorithmoperatesasfollows(refertoFigure1):

1. Findaset,V, ofviewpointsregionsthathaveaset,P,ofvisiblepolygonsin

common.Pickthesettomaximizetheproductofthecardinalities:jVjjPj.

2. CreateasinglepolygonclusterconsistingofthepolygonsofPandallocatefor

itanewcolumninthevisibilitytable. Sincethepolygonclusterisvisiblefrom

eachoftheviewpointregionsinV,the newcolumnhasaTR UE valueineach

rowcorrespondingtoaregioninV.

3. Symmetrically,createasingleregionclusterconsistingoftheviewpointregions

ofV andallocateforitanewrowinthevisibilitytable.Sincetheregioncluster

sees allofthepolygons inP, the newrowhasa TR UE valueineachcolumn

correspondingtoapolygoninP.

4. SettoFALSEallentriesintheintersectionoftherowsandcolumnsofV andP.

(Theseentriesaremaderedundantwiththeadditionofthenewrowandcolumn.)

5. RepeatwithnewV andPuntilnoclustersremainabovesomeuser–denedsize.

Thereisnocosttothisoperation,sincenoocclusionsarelost. Thebenetisthat

thevisibilitytablebecomessparser.Foragivencluster,thebenetcanbecomputedas

thenumberofTR UEentrieswhichbecomeFALSE,minusthenumberofTR UEentries

createdinthenewrowandnewcolumn.IfjVjandjPjarethecardinalitiesofV and

P,respectively,thenthebenetisjV jjPj jV j jPj. Byincludingthenew

regionandpolygonclustersasanewrowandnewcolumnofthetable,theseclusters

canparticipateinsubsequentmerges,asshowninFigures1(b)and1(c).

Todeterminewhichpolygonsare visiblefromaparticularviewpointregion,the

correspondingrowofthevisibilitytableistraversed,justasitisdonewiththelossy–

compressedtable. However,if (on thatrow)a TR UE entry is encounteredin some

column,j, andif columnj correspondstoapolygonclusterratherthan toasingle

polygon,thenarecursivetraversalofrowjisperformed.(Itiseasytodistinguishthe

clustercolumns,sincetheyallappeartotherightoftherightmostpolygoncolumn.)

Itisinterestingtonotethatthesametraversalmaybeperformedwiththerolesofthe

rowsandcolumnsreversed(i.e.traverseeachcolumn). Inthiscase,weenumerateall

viewpointregionsthatseeaparticularpolygon. ThissymmetryisevidentinFigure1.

Forexample,polygoncisvisiblefromregions0,1,and3.

6 ExperimentalResults

Ourexperimentsappliedbothtypesofcompression,as wellas theircombination,to

threetypesofscenes.Thesesceneswerechosenfortheirdissimilarstructuresinorder

toillustratethegeneralityofourmethodandtoshowthatthecompressiontechniques

automaticallyexploitthenaturalstructureofeachsceneinordertoyieldcompactvis-

ibilitydescriptions. We rst motivate the choice ofeach datasetorscene and then

provideasummaryofthekeypropertiesofeachscene.

TheterraindatasetisshowninFigure2andwasprocedurallygeneratedusingan

iterativesubdivide-and-displaceapproximationofafractal terrain. Theexistenceof

occlusion-cullingtechniquesspecictoterrains[14]motivatedthe choiceofthisex-

ample,aswellasthelargenumberofsimulationandgamingapplicationsthatinvolve

0 1 1 1 1 0 1

1 1 1 1 1 1 1

2 1 1 0 1 0 1

3 0 1 1 1 0 1

!

Cluster

0 0 0 0 0 0 0 1

1 0 0 0 0 1 0 1

2 1 1 0 1 0 1 0

3 0 1 1 1 0 1 0

1 1 1 1 0 1 0

(a)

a b c d e f

0 0 0 0 0 0 0 1

1 0 0 0 0 1 0 1

2 1 1 0 1 0 1 0

3 0 1 1 1 0 1 0

1 1 1 1 0 1 0

!

Cluster

a b c d e f

0 0 0 0 0 0 0 1 0

1 0 0 0 0 1 0 1 0

2 1 0 0 0 0 0 0 1

3 0 0 1 0 0 0 0 1

1 0 1 0 0 0 0 1

0 1 0 1 0 1 0 0

(b)

(c)

Fig. 1. An example ofthe lossless clusteringalgorithm, where lettersdenotepolygons and

digitsdenoteviewpointregions. (a)Thevisibilitytableismodiedwhenacluster, ,iscre-

ated,consisting off0;1gfa;b;c;d;fg. (b)Asecond cluster, , iscreated, consistingof

f2;3;gfb;d;fg.Includedinaretheviewpointregionsofcluster,butnotthepolygons

ofcluster.(c)Analternativerepresentationofthevisibilitytable,wherealinedirectedupward

fromitojcorrespondstoTRUEentryinrowi,columnjofthevisibilitytable.Toenumeratethe

polygonsvisibleinaregion,i,allupwardpathsfromiarefollowed.Forclusteredtables,these

pathstraverseintermediateclusters,suchasandintherightmostgraph. Forexample,the

polygonsvisiblefromviewpointregion3areb,c,d,andf.Allpolygonsarevisiblefromregion

1.

Fig.2.Theterraindataset.(a)primitives(b)voxelgriddeningtheviewpointcells(c)planview

ofterrain(d)planviewofvisiblesetforaparticularviewpoint.

(a) (b) (c) (d)

Fig.3. Thetunnelsdataset. (a)exteriorview(b)voxelizationused fortheviewpointcells(c)

interiorviewwithdiffuselighting(d)exteriorviewofvisiblesetfortheviewpointusedin(c).

movingonoroverterrains.Inourexamplewedealspecicallywithvoxel–to–primitive

visibility,as onemightuseinaightsimulator. Otherapplicationswhichrestrictthe

viewpointtothesurface,suchasindrivingorwalkingsimulations,woulddobetterto

usea2Dsurfaceparameterizationoftheviewpointspaceinstead ofavolumetricpa-

rameterization.Theviewingspaceisdividedintoa10108setofvoxels,asshown

inFigure2(b).Viewpointsbelowtheterrainsurfacearetreatedashavingacompletely

occludedviewoftheworld.

Oursecondtestsceneconsists ofasetofwindingtunnels,asshowninFigure3.

Thisdatasetwasmotivatedbyapplicationssuchas colonoscopy[11]. The voxeliza-

tionisconstructedprocedurallyfromtheboundaryrepresentationofthetunnels. The

viewpointcellwhichcontainsagivenviewpointcanbequicklylocatedbycomputing

auniquevoxelIDbasedonthequantizedxyz coordinatesoftheviewpoint,andthen

usingahashtableindexedbythisID.Thisavoidsallocatingvoxelstorageforthelarge

volumeofspaceoutsideofthetunnelsystem,undertheassumptionthattheviewpoint

shouldalwaysremainwithinthetunnels. Viewpointsthatareoutsidethetunnelwalls

—eveniftheyareinsidecellsthatstraddlethewalls—areconsideredtoseenothing,

sotreatmentofstraddlingcellsrequiressomecare.

Lastly, we chooseabuildingoorplanas adataset, as shown in Figure4. The

oorplanexistsona1017unitgrid. Allwallsegmentsarebrokenintoprimitives,

eachnolongerthan1unitinlength. Theviewpointcellsconsistof11unitsquares

onthegrid.TheseareschematicallyillustratedinFigure4(b).Thesceneisconstructed

asa3Dmodel,althoughthe2Doorplaneffectivelycontainsalltheinformationabout

thestructureofthescene.Eachwallisdouble–sided.

Thekeypropertiesthatcharacterizeeachofthethreeexamplescenesaregivenin

Table1. Somedetailsofthistablebearfurtherexplanation. Themaximumocclusion

intheterrainandtunnelscenesis100%,assomeviewpointcellsarelocatedbelowthe

terrainsurfaceoroutsidethetunnelwall. Thedatasetsizeassumesanuncompressed

Fig.4. Theroomsdataset. (a)planview(b)planviewshowingvoxels(c)planviewshowing

primitives

sceneproperties terrain tunnels rooms

#viewpointcells 800 1275 170

#primitives 1217 4166 242

meanocclusion 84% 82% 90%

min,maxocclusion 48%,100% 70%,100% 80%,94%

datasetsize 15kB 50kB 10kB

uncompressedtablesize 122kB 664kB 5.3kB

tablesize,gzip 26kB 64kB 1.2kB

lossycompression

reductionapplied 2p,2v 10p,5v 200g

tablesize(compression) 22.1kB(5.5) 23kB(29) 0.2kB(27)

losslesscompression

#clusters 2000 2000 100

tablesize(compression) 28.5kB(4.3) 95kB(7.0) 1.3kB(4.1)

losslesscompression

tablesize(compression) 6.1kB(20) 4.4kB(151) 0.1kB(53)

%oforiginaltablesize(gzip) 5%(21%) 0.7%(10%) 2%(23%)

%ofdatasetsize(gzip) 41%(173%) 9%(128%) 1%(12%)

Table1.ExperimentalDataandResults

representationofan indexed–vertexrepresentation ofthe geometry. An xyz vertex

tripleisassumedtoberepresentedin12bytes,whileanindexisassumedtobestored

asa4–byteinteger.Therawtablesizeassumesabinaryrepresentationofthevisibility

table. Therun–lengthencodedversionsoftherawtablearecomparableinsizetothe

binary–encodedrawtablesforourexamples.

Weusegziptoprovideasimplepointofcomparisonforourcompressiontech-

niques. Inpractice,therequirementforrandomaccesstotherowsinordertoanswer

visibilityqueriesmeansthatindividualrowsshouldbecompressedinsteadoftheentire

table.Weusegzipasappliedtotheentiretableasanupperboundontheperformance

ofarow–basedcompressionalgorithm.Itshouldalsobenotedthatafurtheradvantage

ofourcompressionschemesisthattheyproduceenumeratedlistsofvisibleprimitives,

unlikebinarycompressionalgorithmswhichonlyreproducetheoriginalrowsofthe

visibilitytable. Lastly,we notethatgzipisonlya`fair'comparisonforthe lossless

compressionalgorithm.

Thecompressiontestsweapplytothetestscenesare(1)lossycompression,(2)lossless

compression,and(3)lossycompressionfollowedbylosslesscompression. Werst

lookathowlossycompressionperformsonthedatasets.Theresultsaresummarizedin

Table1,wherethenotation10p, 5vmeansthatthenumberofprimitiveswasreduced

byafactorof10andthenumberofviewpointcellswasreducedbyafactorof5.Inall

cases,thelossyclusteringprocedurewascontinueduntil5%oftheocclusionspresent

intheoriginalvisibilitytablewerelost. Thefastgreedyalgorithmwasappliedinthe

caseoftheterrainandtunnelsdatasetsbecauseoftheirsize.Theslowgreedyalgorithm

couldbeappliedtotheroomscene(for200iterations)becauseofitssmallsize. Inall

cases,thelossycompressiontooklessthan20minutestocompleteascomputedona

166MHzPC.

Theresultsshowthatthelossycompressionschemecanreducethesizeofthepre-

computedvisibilitytablebyafactorof29forthewell–structuredtunnelscene.Italso

doesverywellonthe roomsscene(27compression),althoughnot as wellforthe

less–structuredterrainscene(5.5). Figure5(a)(seecolorplates)showstheclusters

whichareformedfortheterrainscene,resultingfromreducingthenumberofprimi-

tivesbyafactorof30,showingaplanviewontheleft,andaninteriorviewontheright.

Clusterstypicallyconsistofconnectedpolygons,althoughthisadjacencyinformation

isnotexplicitlypresentintherawvisibilitytable. Aswell,clusterstendtobebased

onmountainfacesandvalleys. The clustersproducedforthetunnelscene,shownin

Figure5(b)showsimilarbehaviors,creatingapatchworkcoverageofthetunnelwalls.

Wedo notshowthe viewpointclustersfortheterrainandtunnelscenes,as theyare

difculttodepict,giventheir3Dnature.

Theviewpointclustersformedfortheroomscene,showninFigure5(c)aremainly

basedonindividualrooms,asonemightintuitivelyexpect. Theprimitiveclustersare

similarlyorganized. Thetwogureson theright illustrate examples ofthelost oc-

clusionsthatariseduringthelossycompression. Theviewpointisindicatedasablue

dot,whilethebluewallsegmentsindicatetheoriginalminimal–sizePVS.Theredwall

segmentsindicatetheadditionsmadetothePVSintheinterestofobtaininggoodcom-

pression.

6.2 LosslessCompressionResults

TheresultsforlosslesscompressionareshowninTable1andFigure6. Losslessclus-

teringbyitself producescompressionfactors ofbetween4and7. Theseresultsare

comparabletogzip,keepinginmindthatgzipisnotamenabletotherandom–access

andfastenumerationrequirementsofvisibilityapplications.

Theclustersformedbythelosslesscompressionalgorithmhaveadifferentstructure

thanthoseofthelossycompression,asshowninFigure6(seecolorplates). Clusters

formedearlyonappearhighintheclusterhierarchyandresult inthe largeststorage

reductions. WeillustratesomeoftheseclustersinFigure6forthethreetestscenes.

InFigure6(a),thesameclusterisshowntwice;rstinaplanviewandtheninaside

view. Althoughtheclusterlookstobeanunlikelyagglomerationofprimitivesinthe

planview,thesideviewrevealsthatitisreallyagroupofprimitivesfacingapartic-

ulardirection, andhenceconsistentlyvisibleas agroupfromaparticular(large)set

ofviewpoints. Theimportantclustersforthetunnelscene,showninFigure6(b),tend

tobecoherentcylindricalregionsofthetunnels,althoughtheclustersdonotprovide

completelycontinuouscoverage,asevidentfromthe“holes.”Theappearanceofthese

holesisunintuitivetous. Theroomsdatasetprovidesresultshavinganintuitiveinter-

togethertheprimitivesinaroom.Theremainingtwoclustersillustratedistributedclus-

terswhicheffectivelycaptureparticular`visibilitycorridors'withinthescene.

6.3 CombiningLossyandLosslessCompression

Aninteresting characteristicofthelossyandlosslesscompressiontechniquesisthat

theyappeartooperateinorthogonalfashions.Theresultsoffollowinglossycompres-

sionwithlosslesscompressionaregiveninTable1. Theocclusionswhichare`lost'

whenusingthecombinationoftechniquesarethesameasthosewhicharelostusing

thelossytechniquealone. Thecompressionratiosachievedfortheterrainandtunnels

scenesareapproximatelytheproductofthecompressionratiosachievablebyeachtech-

niquealone. Forallthreedatasets,thecombinedcompressionperforms4to10times

betterthangzip.Moreinterestingly,thenalcompressedvisibilitytable,onlyamounts

toasmallpercentageofthestoragespacerequiredfortheuncompresseddatasetgeom-

etry.

ThereareseveralcaveatstobestatedaboutTable1. Theroomsexamplehas3D

geometrybuta2Dvisibilityproblem,andthereforethestoragecostfortheprecom-

putedvisibilityissmallwhencomparedtothestoragecostforthedatasetgeometry.

Thetunnelsdatasetisperhapsthemostconvincingresult, storing95%oftheocclu-

sionrelationshipswithamemorycostof9%oftheuncompresseddatasetgeometry.

However,thiskindofresultsisprobablyrestrictedtosceneswhichhavewellstructured

visibilitycoherence. Alastcaveatisthatanyimplementationthatmustdecodetheta-

blemustalsobuildassociatedindexingdatastructuressuchasthehashtablerequired

forthe tunnelscene inordertoefciently locatethe viewpointcell,givenaparticu-

larviewpoint. Theseadditionaldatastructurescould potentiallydoubleortriplethe

storagecostsgiveninTable1,althoughwehavenotyetevaluatedtheiraveragecosts.

Nevertheless,theresultsshowthatremarkablylittlestoragespaceisneededtoencode

precomputedvisibilityinformation.

7 SummaryandDiscussion

Precomputedvisibilityinformationcanbeusedtoanswerthequestion“Whatisvisible

fromthisviewpoint?”Thealgorithmspresentedinthispaperaddressanewproblem(to

thebestofourknowledge):Howcanprecomputedvisibilityinformationbeefciently

compressed?Experimentalresultsshowthattheproposedalgorithmsareeffectivefor

threeverydifferenttypesofdatasets:aterrain,aseriesofwindingtunnels,andabuild-

inginterior. Theresultisanear–optimalmethodofocclusioncullingwhichhaslow

storagecostandwhichpermitsfast,random–accessenumerationofvisibleprimitives.

Weproposeavarietyoffutureworkwhichwouldextendthesetechniquestonew

applicationdomainsaswellasaddressingsomecaveatsintheiruse.

Scalabilityisanimportantissue. Largesceneslikelyneedtobetackledwitha

top–downdivide–and–conquerapproach,inadditiontothebottom–upapproach

proposedthusfar.

Thecompromisebetweenstoragecostandlostocclusionsneedstobeexplored

intermsofatrade-offbetweenrenderingtimeandstoragecost.

The viewpointspacecouldbe expandedtoincludetheviewingdirection. The

techniquecouldalsobeappliedtoefcientlystorevoxel–to–voxelvisibility.

Modelsoftherenderingcostcouldbeincorporatedintotheclusteringcriteria.

1. Fr´ed´ericCazals,GeorgeDrettakis,andClaudePuech. Filtering,clusteringandhierarchy

construction: anewsolutionforray-tracingcomplexscenes. ComputerGraphicsForum,

14(3):371–382,August1995.ProceedingsofEurographics'95.ISSN1067-7055.

2. D.Cohen-Or,G.Fibich,D.Halperin,andE.Zadicario. Conservativevisibilityandstrong

occlusionforviewspacepartitioningofdenselyoccludedscenes.1998.

3. D.Cohen-OrandA.Shaked. Visibilityanddead-zonesindigitalterrainmaps. Computer

GraphicsForum,14(3):C/171–C/180,September1995.

4. D.Cohen-Orand E.Zadicario. Visibilitystreamingfornetwork-basedwalkthroughs. In

ProceedingsofGraphicsInterface'98,1998.

5. SatyanCoorgandSethTeller.Temporallycoherentconservativevisibility.InProceedingsof

theTwelfthAnnualSymposiumOnComputationalGeometry(ISG'96),pages78–87,New

York,May1996.ACMPress.

6. SatyanCoorgandSethTeller.Real-timeocclusioncullingformodelswithlargeoccluders.

InProceedingsofthe1997Symposiumon3DInteractiveGraphics,1997.

7. Z.GigusandJ.Malik. Computingthe aspectgraph fortheline drawingsofpolyhedral

objects.IEEETrans.PatternAnalysisandMachineIntelligence,12(2),February1990.

8. N.Greene. Hierarchicalpolygontilingwithcoveragemasks. ComputerGraphics,30(An-

nualConferenceSeries):65–74,1996.

9. N.Greene,M.Kass,andG.Miller. HierarchicalZ-buffervisibility. InComputerGraphics

(SIGGRAPH'93Proceedings),1993.

10. PatHanrahan,DavidSalzman,andLarryAupperle.Arapidhierarchicalradiosityalgorithm.

ComputerGraphics(SIGGRAPH'91Proceedings),25(4):197–206,July1991.

11. LichanHong,ShigeruMuraki,ArieKaufman,DirkBartz,andTaosongHe.Virtualvoyage:

Interactivenavigationinthehumancolon. InTurnerWhitted,editor,SIGGRAPH97Con-

ferenceProceedings,AnnualConferenceSeries,pages27–34.ACMSIGGRAPH,Addison

Wesley,August1997.

12. DonaldJ.Meagher. Efcientsyntheticimagegenerationofarbitrary3–Dobjects. InPro-

ceedingsoftheIEEEConferenceonPatternRecognitionandImageProcessing,pages473–

478,June1982.

13. H.Plantinga. Conservativevisibilitypreprocessingforefcientwalkthroughsof3dscenes.

InProceedingsofGraphicsInterface'93,pages166–173,1993.

14. A.JamesStewart. Fasthorizoncomputationatallpointsofaterrainwithvisibilityand

shadingapplications.IEEETransactionsonVisualizationandComputerGraphics,4(1):82–

93,March1998.

15. SethTellerandPatHanrahan.Globalvisibilityalgorithmsforilluminationcomputations.In

ComputerGraphicsProceedings,AnnualConferenceSeries,1993,pages239–246,1993.

16. SethJ.Teller. Computingtheantipenumbraofanarealightsource. InComputerGraphics

(SIGGRAPH'92Proceedings),volume26,pages139–148,July1992.

17. SethJ.TellerandCarloH.S´equin. Visibilitypreprocessingforinteractivewalkthroughs.

InThomasW.Sederberg,editor, ComputerGraphics(SIGGRAPH'91Proceedings),vol-

ume25,pages61–69,July1991.

18. Y.Wang,H.Bao,andQ.Peng. Acceleratedwalkthroughsofvirtualenvironmentsbased

onvisibilitypreprocessingandsimplication.ComputerGraphicsForum(Eurographics98

issue),17(3):187–194,1998.

19. R.YagelandW.Ray. Visibilitycomputationforefcientwalkthroughofcomplexenviron-

ments.Presence,5(1):45–60,1995.

20. H.Zhang,D.Manocha,T.Hudson,andKennethE.HoffIII.Visibilitycullingusinghierar-

chicalocclusionmaps.InSIGGRAPH97ConferenceProceedings.

(b)

(c)

Fig.5. Clusteringresultingfromlossycompression. (a)terraindataset(b)tunnelsdataset(c)

roomsdataset

(a)

(b)

(c)

Fig.6. Clusteringresultingfromlosslesscompression.(a)terraindataset(b)tunnelsdataset(c)

roomsdataset