View-Dependent Refinement of Progressive Meshes

HuguesHoppe

MicrosoftResearch

ABSTRACT

Level-of-detail(LOD)representationsareanimportanttoolforreal-timerenderingofcomplexgeometricenvironments.Thepreviouslyintroducedprogressivemeshrepresentationdefinesforanarbitrarytrianglemeshasequenceofapproximatingmeshesoptimizedforview-independentLOD.Inthispaper,weintroduceaframeworkforselectivelyrefininganarbitraryprogressivemeshaccordingtochangingviewparameters.Wedefineefficientrefinementcriteriabasedontheviewfrustum,surfaceorientation,andscreen-spacegeometricerror,anddevelopareal-timealgorithmforincrementallyrefiningandcoarseningthemeshaccordingtothesecriteria.Thealgorithmexploitsviewcoherence,supportsframerateregulation,andisfoundtorequirelessthan15%oftotalframetimeonagraphicsworkstation.Moreover,forcontinuousmotionsthisworkcanbeamortizedoverconsecutiveframes.Inaddition,smoothvisualtransitions(geomorphs)canbeconstructedbetweenanytwoselectivelyrefinedmeshes.

Anumberofpreviousschemescreateview-dependentLODmeshesforheightfields(e.g.terrains)andparametricsurfaces(e.g.NURBS).Ourframeworkalsoperformswellforthesespecialcases.Notably,theabsenceofarigidsubdivisionstructureallowsmoreaccurateapproximationsthanwithexistingschemes.Weincluderesultsforthesecasesaswellasforgeneralmeshes.

CRCategories:I.3.3[ComputerGraphics]:Picture/ImageGeneration-Displayalgorithms;I.3.5[ComputerGraphics]:ComputationalGeometryandObjectModeling-surfacesandobjectrepresentations.

AdditionalKeywords:meshsimplification,level-of-detail,multiresolutionrepresentations,dynamictessellation,shapeinterpolation.

1INTRODUCTION

Renderingcomplexgeometricmodelsatinteractiveratesisachal-lengingproblemincomputergraphics.Whilerenderingperfor-manceiscontinuallyimproving,significantgainsareobtainedbyadaptingthecomplexityofamodeltoitscontributiontotheren-deredimage.Theidealsolutionwouldbetoefficientlydeterminethecoarsestmodelthatsatisfiessomeperceptualimagequalities.Onecommonheuristictechniqueistoauthorseveralversionsofamodelatvariouslevelsofdetail(LOD);adetailedtrianglemeshisusedwhentheobjectisclosetotheviewer,andcoarserapprox-imationsaresubstitutedastheobjectrecedes[4,8].SuchLODmeshescanbecomputedautomaticallyusingmeshsimplification

Itingshowseventhatthoughtrianglethemeshstripsconnectivitycanbegeneratedisirregularforefficientanddynamicrender-(Section6).

Finally,importantitspecialdemonstratescasesoftheheightframework’sfieldsandtessellatedeffectivenessparametriconthesurfaces,aswellasongeneralmeshes(Section8).

NotationWedenoteatrianglemeshMasatuple(VF),where

Visasetofverticesvjwithpositionsj3

,andFisasetoforderedvertextriplesvjfacesincounter-clockwiseorder.vkvlThespecifyingneighborhoodverticesofofavertextrianglev,denotedNv,referstothesetoffacesadjacenttov.

2RELATEDWORK

2.1View-dependentLODfordomainsinR2

Previousview-dependentrefinementmethodsfordomainsin2fallintotwocategories:heightfieldsandparametricsurfaces.

Althoughthereexistnumerousmethodsforsimplifyingheightfields,onlyasubsetsupportefficientview-dependentLOD.Thesearebasedonhierarchicalrepresentationssuchasgridquadtrees[14,23],quaternarytriangularsubdivisions[15],andmoregeneraltri-angulationhierarchies[3,6,20].(Thesubdivisionapproachof[15]generalizesto2-dimensionaldomainsofarbitrarytopologicaltype.)Becausequadtreesandquaternarysubdivisionsarebasedonareg-ularsubdivisionstructure,theview-dependentmeshescreatedbytheseschemeshaveconstrainedconnectivities,andthereforerequiremorepolygonsforagivenaccuracythanso-calledtriangulatedir-regularnetworks(TIN’s).Itwaspreviouslythoughtthatdynam-icallyadaptingaTINatinteractiverateswouldbeprohibitivelyexpensive[14].Inthispaperwedemonstratereal-timemodifica-tionofhighlyadaptableTIN’s.Moreover,ourframeworkextendstoarbitrarymeshes.

View-dependenttessellationofparametricsurfacessuchasNURBSrequiresfairlyinvolvedalgorithmstodealwithpa-rameterstepsizes,trimmingcurves,andstitchingofadjacentpatches[1,13,18].Mostreal-timeschemessamplearegulargridintheparametricdomainofeachpatchtoexploitfastforwarddiffer-encingandtosimplifythepatchstitchingprocess.Ourframeworkallowsreal-timeadaptivetessellationsthatadapttosurfacecurvatureandviewparameters.

2.2Reviewofprogressivemeshes

InthePMrepresentation[10],anarbitrarymeshMissimplifiedthroughasequenceofnedgecollapsetransformations(ecolinFigure1)toyieldamuchsimplerbasemeshM0(seeFigure11):

(M=Mnecoln1

ecol1

ecol0

0

)

M1

MBecauseeachecolhasaninverse,calledavertexsplittransforma-tion,theprocesscanbereversed:

M0

vsplit0

1

vsplit1

vsplitn1

M(Mn=M)

Thetuple(M0vsplit0vsplitn1ofM.Eachvertexsplit,parametrized)formsasvsplitaPM(vrepresentation

sthemeshbyintroducingonenewvertexvvlvrvtflnewfr),modifiestandtwofacesfl=vsvtvlandfr=vsvrvtresultingsequenceofmeshesM0

MasnshowninFigure1.The

=Miseffectiveforview-independentLODcontrol(Figure11).Inaddition,smoothvisualtransitions(geomorphs)canbeconstructedbetweenanytwomeshesinthissequence.

Tocreateview-dependentapproximations,ourearlierwork[10]describesaschemeforselectivelyrefiningthemeshbasedonauser-specifiedqueryfunctionqrefine(vs).Thebasicideaistotraversethe

vsplit󰀀v󰀀t󰀀v󰀀v󰀀l󰀀s󰀀v󰀀v󰀀f󰀀r󰀀l󰀀l󰀀f󰀀r󰀀v󰀀v󰀀r󰀀s󰀀ecol󰀀Figure1:Originaldefinitionsoftherefinement(vsplit)andcoars-ening(ecol)transformations.

vsplitirecordsinorder,buttoonlyperformvspliti(vsivlivri

)if

v(1)vsplitiisalegaltransformation,thatis,iftheverticessivlivrisatisfysomeconditionsinthemeshrefinedsofar,and(2)qrefine(vsi)evaluatestotrue.

Theschemeisdemonstratedwithaview-dependentqrefinefunctionwhosecriteriaincludetheviewfrustum,proximitytosilhouettes,andscreen-projectedfaceareas.

However,somemajorissuesareleftunaddressed.Theqrefinefunctionisnotdesignedforreal-timeperformance,andfailstomeasurescreen-spacegeometricerror.Moreimportantly,nofacilityisprovidedforefficientlyadaptingtheselectivelyrefinedmeshastheviewparameterschange.

2.3Vertexhierarchies

XiaandVarshney[24]useecol/vsplittransformationstocreateasimplificationhierarchythatallowsreal-timeselectiverefinement.TheirapproachistoprecomputeforagivenmeshMamergetreebottom-upasfollows.First,allverticesVareenteredasleavesatlevel0ofthetree.Then,foreachlevell0,asetofecoltransformationsisselectedtomergepairsofvertices,andthere-sultingpropersubsetofverticesispromotedtolevell+1.Theecoltransformationsineachlevelarechosenbasedonedgelengths,butwiththeconstraintthattheirneighborhoodsdonotoverlap.Thetopmostlevelofthetree(ormoreprecisely,forest)correspondstotheverticesofacoarsemeshM0.(Insomerespects,thisstructureissimilartothesubdivisionhierarchyof[11].)

Atruntime,selectiverefinementisachievedbymovingavertexfrontupanddownthroughthehierarchy.Forconsistencyofthere-finement,anecolorvsplittransformationatlevellisonlypermittedifitsneighborhoodintheselectivelyrefinedmeshisidenticaltothatintheprecomputedmeshatlevell;theseadditionaldependenciesarestoredinthemergetree.Asaconsequence,therepresentationsharescharacteristicsofquadtree-typehierarchies,inthatonlygrad-ualchangeispermittedfromregionsofhighrefinementtoregionsoflowrefinement[24].

WhereasXiaandVarshneyconstructthehierarchybasedonedgelengthsandconstrainthehierarchytoasetoflevelswithnon-overlappingtransformations,ourapproachistoletthehierarchybeformedbyanunconstrained,geometricallyoptimizedsequenceofvsplittransformations(fromanarbitraryPM),andtointroduceasfewdependenciesaspossiblebetweenthesetransformations,inordertominimizethecomplexityofapproximatingmeshes.

Severaltypesofview-dependentcriteriaareoutlinedin[24],in-cludinglocalilluminationandscreen-spaceprojectededgelength.Inthispaperwedetailthreeview-dependentcriteria.Oneofthesemeasuresscreen-spacesurfaceapproximationerror,andthereforeyieldsmeshrefinementthatnaturallyadaptstobothsurfacecurva-tureandviewingdirection.

AnotherrelatedschemeisthatofLuebke[16],whichconstructsavertexhierarchyusingaclusteringoctree,andlocallyadaptsthecomplexityofthescenebyselectivelycoalescingtheclusternodes.

vsplit󰀀f󰀀f󰀀n1󰀀v󰀀f󰀀n3󰀀n1󰀀v󰀀u󰀀f󰀀n3󰀀s󰀀f󰀀f󰀀l󰀀f󰀀r󰀀n0󰀀f󰀀n2󰀀f󰀀n0󰀀v󰀀t󰀀f󰀀n2󰀀ecol󰀀Figure2:Newdefinitionsofvsplitandecol.

3SELECTIVEREFINEMENTFRAMEWORK

Inthissection,weshowthatareal-timeselectiverefinementframe-workcanbebuiltuponanarbitraryPM.

LetaselectivelyrefinedmeshMSbedefinedasthemeshobtainedbyapplyingtothebasemeshM0asubsequenceS0n1ofthePMvsplitsequence.AsnotedinSection2.2,anarbitrarysubsequenceSmaynotcorrespondtoawell-definedmesh,sinceavsplittransformationislegalonlyifthecurrentmeshsatisfiessomepreconditions.Thesepreconditionsareanalogoustothevertexorfacedependenciesfoundinmosthierarchicalrepresentations[6,14,24].Severaldefinitionsofvsplitlegalityhavebeenpresented(twoin[10]andonein[24]);oursisyetanother,whichwewillintroduceshortly.LetbethesetofallmeshesMSproducedfromM0byasubsequenceSoflegalvsplittransformations.

Tosupportincrementalrefinement,itisnecessarytoconsidernotjustvsplit’s,butalsoecol’s,andtoperformthesetransformationsinanorderpossiblydifferentfromthatinthePMsequence.Amajorconcernisthataselectivelyrefinedmeshshouldbeunique,regardlessofthesequenceof(legal)transformationsthatleadstoit,andinparticular,itshouldstillbeameshin.

Wefirstsoughttoextendtheselectiverefinementschemeof[10]withasetoflegalitypreconditionsforecoltransformations,butwereunabletoformaconsistentframeworkwithoutoverlyrestrict-ingit.Instead,webegananewwithmodifieddefinitionsofvsplitandecol,andfoundasetoflegalitypreconditionssufficientforcon-sistency,yetflexibleenoughtopermithighlyadaptablerefinement.Theremainderofthissectionpresentsthesenewdefinitionsandpreconditions.

NewtransformationdefinitionsThenewdefinitionsofvsplitandecolareillustratedinFigure2.Notethattheireffectsonthemesharestillthesame;theyaresimplyparametrizeddiffer-ently.Thetransformationvsplit(vstheparentvertexvtwochildrenvtvuflfrvfn0fn1fn2fn3),re-placessbytandvu.Twonewfacesflandfrarecreatedbetweenthetwopairsofneighboringfaces(fn0formationfn1)and(fn2ecol(vfn3)adjacenttovsvtvu

performstheinverseoperation.)hastheTosames.Thesupportparametersedgecollapsemeshesaswithvsplittrans-bound-andaries,faceneighborsfn0fn1fn2fn3mayhaveaspecialnilvalue,andvertexsplitswithfn2=fn3=nilcreateonlythesinglefacefl.LetdenotethesetofverticesinallmeshesofthePMsequence.

Notethat

isapproximatelytwicethenumberVoforiginalverticesbecauseofthevertexrenamingineachvsplit.Incontrast,thefacesofaselectivelyrefinedmeshMSarealwaysasubsetoftheoriginalfacesF.Wenumbertheverticesandfacesintheorderthattheyarecreated,sothatvsplitiintroducestheverticesti=V0+2i+1andui=V0intheselectively+2i+2.refinedWesaymeshthatMaSvertex.

orfaceisactiveifitexistsVertexhierarchyAsin[24],theparent-childrelationonthe

verticesestablishesavertexhierarchy(Figure3),andaselectivelyrefinedmeshcorrespondstoa“vertexfront”throughthishierarchy(e.g.M0andMinFigure3).Ourvertexhierarchydiffersintworespects.First,verticesarerenamedastheyaresplit,andthis

M󰀀0󰀀v󰀀1󰀀v󰀀2󰀀v󰀀3󰀀v󰀀10󰀀v󰀀11󰀀v󰀀4󰀀v󰀀5󰀀v󰀀8󰀀v󰀀9󰀀M󰀀^󰀀v󰀀14󰀀v󰀀15󰀀v󰀀6󰀀v󰀀7󰀀v󰀀12󰀀v󰀀13󰀀Figure3:Thevertexhierarchyonformsa“forest”,inwhichtherootnodesaretheverticesofthecoarsestmesh(basemeshM0)andtheleafnodesaretheverticesofthemostrefinedmesh(originalmeshM).

destroys/󰀀v󰀀v󰀀t󰀀v󰀀u󰀀f󰀀l󰀀f󰀀r󰀀creates󰀀s󰀀f󰀀n0󰀀f󰀀n1󰀀f󰀀n2󰀀f󰀀n3󰀀f󰀀n0󰀀f󰀀n1󰀀f󰀀n2󰀀f󰀀n3󰀀requires󰀀vsplit󰀀ecol󰀀v󰀀t󰀀v󰀀u󰀀f󰀀l󰀀f󰀀r󰀀v󰀀s󰀀Figure4:Preconditionsandeffectsofvsplitandecoltransforma-tions.

renamingcontributestotherefinementdependencies.Second,thehierarchyisconstructedtop-downafterloadingaPMusingasimpletraversalofthevsplitrecords.Althoughourhierarchiesmaybeunbalanced,theytypicallyhavefewerlevelsthanin[24](e.g.24insteadof65forthebunny)becausetheyareunconstrained.PreconditionsWedefineasetofpreconditionsforvsplitandecoltobelegal(refertoFigure4).

Avsplit(vsvtvu

)transformationislegalif(1)vsisanactivevertex,and

(2)thefacesfn0fn1fn2fn3areallactivefaces.

Anecol(vsvtvu

)transformationislegalif(1)vtandvuarebothactivevertices,and

(2)thefacesadjacenttoflandfrarefn0fn1urationofFigure2.

fn2fn3,intheconfig-PropertiesLetbethesetofmeshesobtainedby0transitiveclosureoflegalvsplitandecoltransformationsfromM(orequiv-alentlyfromMsincethePMsequenceM0Mislegal).Forany

meshM=(VF)

,weobservethefollowingproperties:1Ifvsplit(vsvtvu)islegal,thenfn0pairwiseadjacentandadjacenttovfn1andfn2fn3bemust

sasinFigure2.

Iftheactivevertexfrontliesbelowecol(vsvtvuF),thenf)(i.e.flfr

n0fn1fn2fn3mustallbeactive.

M

S

,i.e.M=MforsomesubsequenceS,i.e.

=

.

obtainedbyapplyingtoMM=MSisidenticaltothemeshthecomplementsubsequencen10Sofecoltransforma-tions,whicharelegal.

ImplementationTomaketheseideasmoreconcrete,Figure5liststheC++datastructuresusedinourimplementation.Aselec-tivelyrefinablemeshconsistsofanarrayofverticesandanarrayoffaces.Oftheseverticesandfaces,onlyasubsetareactive,asspecifiedbytwodoubly-linkedliststhatthreadthroughasubsetof

structListNode//NodepossiblyonalinkedlistListNode*next;//0ifthisnodeisnotonthelist;

ListNode*prev;structVertex

ListNodeactive;//liststringingactiveverticesVPointpoint;Vectornormal;Vertex*parent;//0ifthisvertexisinM0Vertex*vt;//0ifthisvertexisinM;(vu=vt+1)//Remainingfieldsencodevsplitinformation,definedifvt=0.Face*fl;//(fr=fl+1)Face*fn[4];//requiredneighborsfn0fn1fn2fn3RefineInforefine

vertices;//headoflistV

ListNodeactive

view

away(vs)returnfalse

//Refineonlyifscreen-projectederrorexceedstolerance.ifscreenerror(vs)returnfalsereturntrue

ViewfrustumThisfirstcriterionseekstocoarsenthemeshout-sidetheviewfrustuminordertoreducegraphicsload.Ourapproachistocomputeforeachvertexvtheradiusrvofaspherecen-teredatthatboundstheregionofMsupportedbyvandallitsdescendants.Weletqrefine(v)returnfalseifthisboundingsphereliescompletelyoutsidetheviewfrustum.

TheradiirvarecomputedafteraPMrepresentationisloadedintomemoryusingaboundingspherehierarchyasfollows.First,wecomputeforeachvV(theleafnodesofthevertexhierarchy)asphereSvthatboundsitsadjacentverticesinM.Next,weperformapostordertraversalofthevertexhierarchy(byscanningthevsplit

α󰀀v󰀀Gauss map󰀀n󰀀^󰀀v󰀀n󰀀^󰀀v󰀀S󰀀'󰀀v󰀀v󰀀backfacing󰀀region󰀀(a)Nv(b)regionofM

(c)S2Figure6:Illustrationof(a)theneighborhoodofv,(b)theregioninMaffectedbyv,and(c)thespaceofnormalsoverthatregionandtheconeofnormalsthatboundsit.

sequencebackwards)toassigneachparentvertexvsthesmallestsphereSvsincethesthatboundsthespheresSvresultingspheresStSvuofitstwochildren.Finally,varenotcenteredonthevertices,wecomputethatboundsateachSvertexvtheradiusrvofalargerspherecenteredatv.

Sincetheviewfrustumisa4-sidedsemi-infinitepyramid,asphereofradiusrvcenteredat=(vxvyvz)liesoutsidethefrustumif

aivx+bivy+civz+di

rvforanyi=1

4

whereeachlinearfunctionalaix+biy+ciz+dimeasuresthesignedEuclideandistancetoasideofthefrustum.SelectiverefinementbasedsolelyontheviewfrustumisdemonstratedinFigure12a.SurfaceorientationThepurposeofthesecondcriterionistocoarsenregionsofthemeshorientedawayfromtheviewer,againtoreducegraphicsload.Ourapproachisanalogoustotheviewfrustumcriterion,exceptthatwenowconsiderthespaceofnormalsoverthesurface(theGaussmap)insteadofthesurfaceitself.normalsisasubsetoftheunitsphereS2=

3Thespaceof

:=1;foratrianglemeshM,itconsistsofadiscretesetofpoints,eachcorrespondingtothenormalofatrianglefaceofM.

Foreachvertexv,weboundthespaceofnormalsassociatedwiththeregionofMsupportedbyvanditsdescendants,usingaconeofnormals[22]definedbyasemianglevaboutthevectorv=vnormal(Figure6).ThesemianglesvarecomputedafteraPMrepresentationisloadedintomemoryusinganormalspacehierarchy[12].Asbefore,wefirsthierarchicallycomputeateachvertexvasphereSvthatboundstheassociatedspaceofnormals.Next,wecomputeateachvertexvthesemianglevofaconevthatboundstheintersectionofSvandS2

about

.Weletv=

2)exists.

Givenaviewpoint,itisunnecessarytosplitvifliesinthebackfacingregionofv,thatis,if

v

^󰀀n󰀀2cot

δ󰀀0.5󰀀0.25󰀀µ󰀀0󰀀-0.25󰀀-0.5󰀀-1󰀀-0.5󰀀0󰀀1󰀀0.5󰀀0󰀀-0.5󰀀0.5󰀀(a)(b)(c)1󰀀-1󰀀Figure7:Illustrationof(a)thedeviationspaceDnˆ(

),(b)itscross-section,and(c)theextentofitsscreen-spaceprojectionasafunctionofviewingangle(with=05and=1).

Todeterminewhetheravertexv

shouldbesplit,weseekameasureofthedeviationbetweenitscurrentneighborhoodNv(thesetoffacesadjacenttov)andthecorrespondingregionNvinM.OnequantitativemeasureistheHausdorffdistance(NvNv),definedasthesmallestscalarrsuchthatanypointonNviswithindistancerofapointonNv,andviceversa.Mathematically,(NvNv)isthesmallestrforwhichNvNvistheclosedballofradiusrandB(r)denotesandNvtheNvMinkowskiB(r)wheresumB2(r)the(N.IfvNv)=r,thescreen-spaceapproximationerrorisboundedbyscreen-spaceprojectionoftheballB(r).

IfNvandNvaresimilarandapproximatelyplanar,atighterdis-tanceboundcanbeobtainedbyreplacingtheballB(r)intheabovedefinitionbyamoregeneraldeviationspaceD.Forinstance,Lind-strometal.[14]recorddeviationofheightfields(graphsoffunctionsovertheplane)byassociatingtoeachvertexascalarresentingaverticaldeviationspaceDzˆ()=hThemainadvantageofusingD:valuehrep-.zˆ()isthatitsscreen-spaceprojec-tionvanishesasitsprincipalaxisdirection,unlikethecorrespondingbecomesB().

paralleltotheviewingTogeneralizetheseideastoarbitrarysurfaces,wedefineade-viationspaceDnˆ(

)showninFigure7a–b.Themotivationisthatmostofthedeviationisorthogonaltothesurfaceandiscap-turedmaybybearequireddirectionalwhencomponentN,butauniformuniformcomponentviscurved.Thecomponentalsoallowsaccurateapproximationofdiscontinuitycurves(suchassurfaceboundariesandmaterialboundaries)whosedeviationsare

oftentangenttothesurface.TheparticulardefinitionofDnˆ(

)correspondstotheshapewhoseprojectedradiusalongadirectionhasthesimpleformulamax(thegraphofthisradiusasafunctionofview).AsdirectionshownhasinFiguretheshape7c,ofasphereofradiusunionedwitha“bialy”[14]ofradius.DuringtheconstructionofaPMrepresentation,weprecompute

vvfordeviationspaceDnˆeachecol(vv(vv)ateachvertexv

asfollows.AftersthedeviationbetweenvtvuN)transformationisapplied,weestimatevvectorsE=sandNvsbyexaminingtheresidualerrorilocallyprojectontofromNadensesetofpointsXsampledonMthatvs,asexplainedinmoredetailin[10].WeusemaxethesmallestiE(iv)maxeDiEivtofixtheratiovv,andfindnˆv(vv)withthatratiothatboundsE.Alternatively,othersimplificationschemessuchas[2,5,9]couldbeadaptedtoobtaindeviationspaceswithguaranteedbounds.

Notethatthecomputationofvvdoesnotmeasureparametricdistortion.Thisisappropriatefortexture-mappedsurfacesifthetextureisgeometricallyprojectedor“wrapped”.Ifinstead,verticesweretocontainexplicittexturecoordinates,theresidualcomputa-tioncouldbealteredtomeasuredeviationparametrically.

Givenviewpoint,screen-spacetolerance(asafractionofviewportsize),andfield-of-viewangle,qrefine(v)returnstrueif

2

)22iscomputedonceperframe.Notethatthe

testreducestothatof[14]whenv=0andv=afewmorefloatingpointoperationsinthegeneral,andcase.requiresAsseenonlyinFigures13band16b,ourtestnaturallyresultsinmorerefinementnearthemodelsilhouettewheresurfacedeviationisorthogonaltotheviewdirection.

Ourtestprovidesonlyanapproximateboundonthescreen-spaceprojectederror,foranumberofreasons.First,thetestslightlyunderestimateserrorawayfromtheviewportcenter,aspointedoutin[14].Second,aparallelprojectionassumptionismadewhenprojectingDnˆonthescreen,asin[14].Third,theneighborhoodaboutvwhenevaluatingqrefine(v)maybedifferentfromthatinthePMsequencesinceMisselectivelyrefined;thusthedeviationspacesDnˆprovidestrictboundsonlyattheverticesthemselves.Nonetheless,thecriterionworkswellinpractice,asdemonstratedinFigures12–16.

ImplementationWestoreineachVertex.RefineInforecordthe

fourscalarvaluesrvmenttestsshareseveralcommonsin2v22

subexpressions,vv.Becauseevaluationthethreerefine-ofthe

completeqrefinefunctionrequiresremarkablyfewCPUcyclesonaverage(230cyclespercallasshowninTable2).

5INCREMENTALSELECTIVEREFINEMENT

ALGORITHM

WenowpresentanalgorithmforincrementallyadaptingameshwithintheselectiverefinementframeworkofSection3,usingtheqrefinefunctionofSection4.ThebasicideaistotraversethelistofactiveverticesVbeforerenderingeachframe,andforeachvertexvV,eitherleaveitasis,splitit,orcollapseit.Thecoreofthetraversalalgorithmissummarizedbelow.procedureadapt

vsplit(v)

elseifvparentandecol

vsplit(v)

stackvwhilevstack.top()ifvvtandvflFstack.pop()//vwassplitearlierintheloopelseifvV

stack.push(vparent)elseifvsplit

3Implementation

detail:thevertexthatshouldbesplittocreateanin-activefacefisfoundinfvertices[0]parentbecausewealwayssetbothflvertices[0]=vtandfratingtheneedforaFace.verticesparent[0]field.

=vtwhencreatingfaces,therebyobvi-WeiteratethroughthedoublylinkedlistofactiveverticesV.ForanyactivevertexvM,ifqrefine(v)evaluatestotrue,thevertexshouldbesplit.Ifvsplit(v)isnotlegal(i.e.ifanyofthefacesvfn[03]arenotactive),achainofothervertexsplitsareperformedinorderforvsplit(v)tobecomelegal(procedureforce

transformingMAintoMB,isO(VAB

refinement,

AM0MB+V)intheworstcasesinceMcouldpossiblyrequireO(VA)ecol’sandO(VBvsplitB’s,eachtakingconstanttime.Forcontinuousviewchanges,)VisusuallysimilartoVA,andthesimpletraversaloftheactivevertexlististhebottleneckoftheincrementalrefinementalgo-rithm,asshowninTable2.NotethatthenumberVofactiveverticesistypicallymuchsmallerthanthenumberVoforiginalvertices.Therenderingprocess,whichhasthesametimecom-plexity(F2V),infacthasalargertimeconstant.Indeed,

adapt

refinementattime

framet,wesett=t1(Ft1activefacesinthepreviouslydrawnm)frame.whereAsFt1shownistheinnumberFigure10,ofthissimplefeedbackcontrolsystemexhibitsgoodstabilityforourterrainflythrough.Moresophisticatedcontrolstrategiesmaybenecessaryforheterogeneous,irregularmodels.Directregulationofframeratecouldbeattempted,butsinceframerateismoresensitivetooperatingsystem“hiccups”,itmaybebestachievedindirectlyusingasecondary,slowercontrolleradjustingm.

AmortizationSincethemainloopofadapt

vsplittoadvancethevertexfronttowardsthatoftheother

mesh.ThemeshMGhasthepropertythatitsfacesFGareasuperset

ofbothFAandAFB,andthatanyvertexvjvandauniqueancestorvVGhasauniqueancestorGA(j)VGB(j)VB.ThegeomorphMG()isthemesh(FGVG())with

Gj(

)=(1

)

G

A)

G

B(j)

+((j)

InthecasethatMBistheresultofcallingadapt

passM

A

G

refinement,wemaketwopasses:arefinement

passMG

MMBwhereonlyvsplitareconsidered,andacoarseningwhereonlyecolareconsidered.Ineachpass,werecordthesequenceoftransformationsperformed,allowingustobacktrackthroughtheinverseoftheecolsequencetorecovertheintermediatemeshMG,andtoconstructthedesiredancestryfunctionsGAandGB.Suchageomorphisdemonstratedontheaccompanyingvideo.Becauseofviewcoherence,thenumberofverticesthatrequireinterpolationisgenerallysmallerthanthenumberofactivevertices.Moreresearchisneededtodeterminethefeasibilityandusefulnessofgeneratinggeomorphsatruntime.

6RENDERING

Manygraphicssystemsrequiretrianglestriprepresentationsforoptimalrenderingperformance[7].Becausethemeshconnectivityinourincrementalrefinementschemeisdynamic,itisnotpossibletoprecomputetrianglestrips.Weuseagreedyalgorithmtogeneratetrianglestripsateveryframe,asshowninFigure12e.Surprisingly,thealgorithmproducesstripsofadequatelength(onaverage,10–15facesper“generalized”trianglestripunderIRISGL,andabout4.2facesper“sequential”trianglestripunderOpenGL),anddoessoefficiently(Table2).

ThealgorithmtraversesthelistofactivefacesF,andatanyfacenotyetrendered,beginsanewtrianglestrip.Then,iteratively,itrenderstheface,checksifanyofitsneighbor(s)hasnotyetbeenrendered,andifsocontinuesthestripthere.Onlyneighborswiththesamematerialareconsidered,soastoreducegraphicsstatechanges.Toreducefragmentation,wealwaysfavorcontinuinggeneralizedtrianglestripsinaclockwisespiral(Figure12e).Whenthestripreachesadeadend,traversalofthelistFresumes.OnebitoftheFace.matidfieldisusedasabooleanflagtorecordrenderedfaces;thesebitsareclearedusingaquicksecondpassthroughF.

Recently,graphicslibrarieshavebeguntosupportinterfacesforimmediate-moderenderingof(VF)meshrepresentations(e.g.Direct3DDrawIndexedPrimitiveandOpenGLglArrayElementAr-rayEXT).Althoughnotusedinourcurrentprototype,suchinter-facesmaybeidealforrenderingselectivelyrefinedmeshes.

7OPTIMIZINGPMCONSTRUCTIONFOR

SELECTIVEREFINEMENT

ThePMconstructionalgorithmof[10]findsasequenceofvsplitrefinementtransformationsoptimizedforaccuracy,withoutregardtotheshapeoftheresultingvertexhierarchy.Wehaveexperi-mentedwithintroducingasmallpenaltyfunctiontothecostmetricof[10]tofavorbalancedhierarchiesinordertominimizeunneces-sarydependencies.Thepenaltyforecol(vtvu)isc(nvnt+nvu)wherevisthenumberofdescendantsofv(includingitself)andcisauser-specifiedparameter.Wefindthatasmallvalueofcimprovesresultsslightlyforsomeexamples(i.e.reducesthenumberoffacesforagivenerrortolerance),butthatascincreases,thehierarchiesbecomequadtree-likeandtheresultsworsenmarkedly(Figure17).Ourconclusionisthatitisbeneficialtointroduceasmallbiastofavorbalancedhierarchiesintheabsenceofgeometricpreferences.

8RESULTS

TimingresultsWeconstructedaPMrepresentationofaGrandCanyonterrainmeshof6002vertices(717,602faces),andtrun-catedthisPMrepresentationto400,000faces.Thispreprocessingrequiresseveralhoursbutisdoneoff-line(Table1).LoadingthisPMfromdiskandconstructingtheSRMeshrequireslessthanaminute(mostofitspentcomputingrvandv).Figures9and10showmeasurementsfroma3-minutereal-timeflythroughoftheterrainwithoutandwithregulation,onanSGIIndigo2Extreme(150MHzR4400with128MBofmemory).Themeasurementsshowthatthetimespentinadapt

info)inaseparatearrayof“Vsplit”records

indexedbyvt.Ifspaceisalwaysallocatedfor2facespervsplit,theVertex.flfieldcanbedeletedandinsteadcomputedfromvt.ScalarvaluesintheRefineInforecordcanbequantizedto8bitswithanexponentialmapasin[14].Coordinatesofpointsandnormalscanbequantizedto16bits.Materialidentifiersareunnecessaryifthemeshhasonlyonematerial.Overall,thesechangeswouldreducememoryrequirementsdowntoabout140Vbytes.

Forthecaseofheightfields,thememoryrequirementpervertexfarexceedsthatofregulargridschemes[14].However,thefullydetailedmeshMmayhavearbitraryconnectivity,andmaythereforebeobtainedbypre-simplifyingagivengridrepresentation,possibly

Table1:Statisticsforthevariousdatasets.

Constr.

V

(MB)height

79,202

1.3

47

canyon400160,000

1.1

35.832

717,602

11.0

627

”trunc.200,600

1.5

44.935

19,800

0.3

11

teapottrunc.5,090

0.0

1.120

42,712

0.8

30

bunny

34,835

0.2

7.8

24

Table2:CPUutilization(ona150MHzMIPSR4400).

cycles/call

User

refinement14%(vsplit)(0%)(ecol)(1%)(qrefine)

(4%)render(tstrip/face)26%GLlibrary

19%

System

--

refinementtimesinseconds.

10|F|,thousands1pixel tolerance0.1frame time0.01AR time0.0010200400600800Frames1000120014001600Figure10:SamebutwithregulationtomaintainF9000.(is

neverallowedbelow0.5pixels.)

byanorderofmagnitudeormore,withoutsignificantlossofaccu-racy.Thispre-simplificationmaybeachievedbysimplytruncatingthePMrepresentation,eitheratcreationtimeoratloadtime.

Applicationsthatuseheightfieldsoftenrequireefficientgeomet-ricqueries,suchaspointsearch.BecausethevertexhierarchiesinourframeworkhaveO(logn)heightintheaveragecase(thiscanbeenforcedusingtheapproachinSection7),suchqueriescanbeper-formedinO(logn)timebyiterativelycallingforce

(a)BasemeshM0(1face)(b)M514(1,000faces)(c)M5066(10,000faces)(d)M=Mn(79,202faces)

Mn=M.Figure11:ThePMrepresentationofameshMcapturesacontinuoussequenceofview-independentLODmeshesM0

(a)Topview(=00;33,119faces)

(b)Topandregularviews(=033;10,013faces)

(c)TexturemappedM(79,202faces)(d)Texturemapped(10,013faces)(e)764generalizedtrianglestrips

Figure12:View-dependentrefinementofthesamePM,usingtheviewfrustum(highlightedinorange)andascreen-spacegeometricerrortoleranceof(a)0%and(b,d,e)0.33%ofwindowsize(i.e.2pixelsfora600600image).

(a)OriginalM(19,800faces)(b)Frontviewand(c)Topview(=0075;1,422faces)Figure13:View-dependentrefinementofatessellatedsphere,demonstrating(b)thedirectionalityofthedeviationspaceDnˆ(morerefinementnearsilhouettes)and(c)thesurfaceorientationcriterion(coarseningofbackfacingregions).

Figure14:View-dependentrefinement(=015;1,782faces)ofatruncatedPMrepresentation(10,000facesinM)createdfromatessellatedparametricsurface(25,440faces).Interactiveframeratenearthisviewpointis14.7frames/sec,versus6.8frames/secusingM.

(a)OriginalM(42,712faces)(b)View1(3,157faces)(c)View2(2,559faces)Figure15:Twoview-dependentrefinementsofageneralmeshMusingviewfrustumshighlightedinorangeandwith

setto0.6%.

(a)OriginalM(69,473faces)(b)Frontviewand(c)Topview(=01;10,528faces)

Figure16:View-dependentrefinement.Interactiveframeratenearthisviewpointis6.7frames/sec,versus1.9frames/secusingM.

Vertex hierarchy height4030201001e-071e-050.0010.1Bias parameter c10Number of mesh faces130001200011000100001e-07Figure17:Heightofvertexhierarchy,

andnumberoffacesinmeshofFigure16b,asfunctionsofthebiasparametercusedinPMconstructionofbunny.

1e-050.0010.1Bias parameter c10