LODESTAR:AnOctree-BasedLevelOfDetailGeneratorForVRMLDieterSchmalstiegViennaUniversityofTechnology,Austriadieter~cg.tuwien.ac.at-http:liwww.cg.tuwien.ac.ati-dieterlAbstractapplicationsthatcreategeometrycannowexportmodelsinLevelofdetailgenerationisimportantformanagingVRMLformat,andsomeofthemsupportlevelofdetailgeometriccomplexityofthree-dimensionalobjectsandcontrol.However,sinceVRMLismostoftenusedwithvirtualworlds.However,mostalgorithmsthatcomputeInternet-basedapplications,inpracticeoneisoftenlevelsofdetaildonotdealwiththespecialrequirementsofconfrontedwiththeproblemthattheapplicationthatinputdatainVRMLformat.Wereportanalgorithmcalledgeneratedthemodelisnomoreavailable.Informationontheinternalstructureofthemodelislost,andsothetaskofLODmTAR,basedonoctreequantizationthatrobustlycomputessimplificationsforobjectsinVRML.generatinglevelsofdetailforinputdatathatcomesinVRMLformatisallbuttrivial.ThissituationisoftenCRCategoriesandSubjectDescriptors:1.3.5[ComputerdeterioratedbyexportfiltersortranslatorsthatproduceGraphics]:ComputationalGeometryandObjectModeling-non-standardVRMLfilesorintroducedegeneracies(forsurfacesandobjectrepresentations‘example,non-planarorotherwisedistortedpolygonsareAdditionalKeywords:VRML,polygonalobjectcommonlyfound).simplification,levelsofdetail,octreequantization2.RELATEDWORK1.INTRODUCTIONANDMOTIVATIONTheterm,,geometricprimitive”inthecontextofinteractiveLevelsofdetail(LODS)areapproximationsofanobjectrenderingusuallymeanspolygonsortriangles,butotherwithfewergeometricprimitives,thatareselectedatrungeometricentitiescartbeusedaswell(e.g.,aboundingboxtimetosustaininteractiveframerates[1].Reducingofanobjectcansufficeasa“cheap”coarseLOD).geometriccomplexityofgeometricmodelsisparticularlyHowever,thealgorithmsthathavebeenreportedononlyimportantforVRMLworldsforatleasttwogoodreasons:dealwithpolygonalobjects.Forasurvey,see[5].wWhile3-Drenderingsystemsarenotoriouslytooslow,thisisparticularlypainfulforlowcostdevicessuchas2.1SurfacealgorithmspersonalcomputersthataremostfrequentlyusedforVRMLapplications.Themethodsthatproducethehighestqualityworkonthesurfaceofpolygonalobjects,e.g.[9,11,2].ForthemomentqAsinglelevelofdetailforagivenobjectcanbeconsideredaformoflossycompression.Effectively,theletusassumethatweareonlydealingwithtriangles.Withsizeoftheoriginalmodelisreducedattheexpenseofinformationonwhichtrianglesareneighbors,localquality,allowingforfasttransmissionandmoreoperationscanbeappliedtoremovetrianglesandfilltheeffectivedistributedapplications.holescreatedbythatprocess.SuchalgorithmscantakeintoaccountlocalcurvatureandcangeneratesimplificationsManyalgorithmshavebeenpublishedonhowtosimplifywithguaranteederrorbounds.However,theyaregeometricmodels,buttheygenerallyplaceassumptionsonconstrainedtoobjectswithwell-connectedsurfaces.thedatathathampertheirapplicationtoVRMLfiles.ManyUnfortunately,thisconstraintisoftennotfulfilledbyCADmodels.ManyofthesealgorithmsarealsoconstrainedtoPa-mission10makedigilahlsardcopiesofallorpmlofthismaterialforpreservethegenusoftheobject,andcanthereforenotpersonalorclassroomuseisgrankdwithoutfeeprovidedthat[hecopiessimplifytheobjectsbeyondamodel-dependentlevel.arenotmadeordistributedforprotitorcommercialadvanlage.thecopy-rightnotice,thetitleoflhepuhlicntionanditsdateappear,andnoticeisgiventhatcopy-ighlisbypermissionofIIMACM,Inc.Tocopyothetwise,torepublid),topostonserversor10redistributetolist~,requiresspecific2.2Clusteringalgorithmspermissionand/orfeeVRML97,MontereyCAUSAReal-worldapplicationsalmostalwaysinvolveill-behavedCopyrighl1997ACM0-8979I-8t16-x/97/02..$3.50data,andforverylargescenesandslowconnections,it125shouldbepossibletoproduceverycoarseapproximationsaswellasmoderatelycoarseones.MoreapttothistaskareLODgenerationmethodsthatignorethetopologyofobjectsandforceareductionofthedataset.Thekeyideahereistoclustermultipleverticesofthepolygonalobjectthatarecloseinobjectspaceintoone,andremovealltrianglesthatdegenerateorcollapseintheprocess,Theproblemhereisthatexactcontroloverlocaldetailisnotsoeasilypossible,butsuchanalgorithmcanrobustlydealwithanytypeofinputdata,andproducearbitrarilyhighcompression.Vertexclusteringcaneitherbedonewithasimpleuniformquantization[6]orabinarytree[7].3.OCTREEQUANTIZATIONFORLODSWehaveinvestigatedalevelofdetailgenerationalgorithmcalledLODNTAR.Itusesoctreequantization[3]forvertexclustering.Octreequantizationissuperiorinqualitytouniformquantizationandinspeedtobinarytrees.Thethree-dimensionalspatialstructurerepresentedbyanoctreeallowssimpleclusteringoperationsonthree-dimensionalsamplesinlineartime.Themethodworkswellforcolors(thethreedimensionsbeingtheR,G,andBcomponent),andhasbeenadaptedfor(x,y,z)vertexcoordinatetuplesinthiswork.Inthefollowing,weoutlinethequantizationmethod.Westartbyexplaininghowtocreatetheoctreedatastructure,andproceedwithdetailsonhowtoidentifyclusters,andhowtoselecttherepresentativeforeachidentifiedcluster.Finally,wedescribehowtoobtainthesimplifiedmodelfromtheoriginalmodelusingtheoctreeasanauxiliarydatastructure.3.1BuildingtheoctreeOctreequantizationwasoriginallydevelopedtoselecttheentriesforacolorlookuptablethatoptimallyrepresentagivenimage.Insteadofcolorpixels,weentertheverticesofthemodelintoanoctree.Intermediatenodesoftheoctreerepresentsubdivisionsoftheobjectspacealongthe~,y,andzdirection.Thegoalistoplaceexactlyonevertexineachsubvohune.Theoctreeissuccessivelyrefinedbyfurthersubdivisionofleafnodeswhenenteringnewverticesuntilthiscriterionissatisfied.Theoretically,thiscangeneratearbitrarilydeepoctrees,butinpracticeacertainoctreedepthisneverexceededastheinputdatacomesinfiniteprecisionfloatingpointnumbers.Whenenteringanewvertex,theoctreeisrecursivelytraversedbycomparingthecoordinatesofthenewvertexagainstthecoordinatesstoredintheoctreenode,andtraversingthelinktotheappropriatechildnodeuntilaleaforanilpointerisencountered.Threecasesmustbedistinguished:126Case1:Theselectedlinkisanilpointer,sothecorrespondingsubvolumeisempty,andwecansimplycreateanewleafnodeandstorethevertexinthatnode(Figure1).[0-4)foundaplaceh0,6,0[4-8]toin=rt\\[y)...........-..--’,....;...[0-2)[24)‘---------i1,1,1~[[0-2)0-2)&[04)[o-t)[0-4)3,1,2[02)[24)h2,3,3[2-4)[2+[24)Figure1:InsertingavertexintoanemptysubvolumeCase2:Thelinkpointstoaleafnode,andthenewvertexisequaltothevertexstoredintheler&Nonewnodeiscreated,butthevertexcounteroftheexistingnodeissimplyincremented.Notethatthisautomaticallysortsoutdoubletsinthevertices,whichareamajordefectofmanyVRMLmodelsfoundtoday,becauseonlyonecopyofeachvertexisfinallyoutput(Figure2).‘“2X!!!!!!!d[0-4)[0-4)0,6,0[4-8][04)[0-4)+\\[0-4)notinserted,avertexwithequalcoordinates--+3,3,2[tp2)alreadyexistsb:h[’”)2,3,3[24)[24)Figure2:InsertinganalreadyexistingvertexCase3:Thelinkpointstoaleafnode,butthenewvertexisnotequaltothevertexstoredintheled.Theleafvertexandthenewvertexfallintothesamesubvolume,sotheoctreemustbesubdividedinthatlocation.Anewintermediatenodeiscreated,andtheoldleafnodeandanewnodecontainingthenewvertexareinsertedaschildrenofthenewintermediatenode(Figure3).me[0-6][0-6][0-6][04)[0-4)0,6,0[4-6][0-4)[0-4)\\~[O+noda3,1,2iara@acadbyanewintenndate,....+[24)p+nods3,2,1andnewnode3,1,1%node~\\-,..-.j[0-2)2,3,3[2-4)areinawtedintothenew.,.,’$...-[24)[24)intermediatenode:-------.:+’-’”””[3-4)‘“[34)!31............1!~11~a3,1,2[1-2)p-3)Figure3:Insertingavertexintoanoccupiedsubvolume3.2VertexclusteringThenumberofverticesisreducedbycombiningmultiplecloseverticesintoonecluster.Forsuchacluster,arepresentativeischosenfromthesetofverticesrepresentedbythatcluster.Thishastheadvantagethatnonewvertexmustbesynthesized,andtheoriginalsetofverticescanbekeptunchanged.Vertexclusteringisdonebyreplacingleafnodesthatshareanintermediatenodeascommonparentwiththatparent,settingthevertexcountoftheparenttothesumofTheerrorareaisdefinedasthedifferenceinthesummedareaoftheinvolvedpolygonsbeforeandaftertheclustering.Thevertexthatproducesthesmallesterrorareaischosen.Errorvolumeisanattempttomeasuretheobject’schangeinvolume:Foreveryinvolvedtriangle,weconstructthetetrahedronfromthethreeoriginalverticesandthepotentialrepresentative.Thevolumeofsuchatetrahedronthevertexcountsofitschildren.Inselectingthecluster,thefollowingcriteriaarerelevant:qFromallclusters,selecttheonewhosenodeshavethelargestdepthwithintheoctree,fortheyrepresentiszeroifoneoftheverticesiselectedtherepresentative.Thesummedvolumeofallsuchtetrahedronsistakenastheerrorvolume,andthevertexwiththesmallesterrorvolumeiselected.Onedisadvantageofthisapproachisthatallvolumesarezeroiftheverticeslieinaplane,soitisonlyusefulincombinationwithanotherheuristic.verticesthatlieclosesttogether.s‘tRIfthereismorethanonesuchcluster,additionalcriteriacanbeusedfortheselectionaccordingtotheuser’spreferences:Selectingtheclusterthatrepresentsthefewestverticeswillkeeptheemorsumsmall.Selectingtheclusterthatrepresentsthemostverticeswilltendtogeneratecoarserrepresentationsoffinelytessellatedareaswithfewervertices,butpreservesmalldistinctivefeaturesinstead.Experimentsshowthatthislatterstrategyusuallyproducesbetterresults.F@reWAcB3.3SelectingtheclusterrepresentativeTheremainingproblemiswhichstrategytousetoselecttherepresentativevertexfromtheverticesinthecluster.Todoso,weusethreedifferentheuristicswithuserdefinedweight.Lettheinvolvedtrianglesbethosetrianglesthat5:Theerrorvolumeiscomputedfromthete~ahedronwiththeoriginaltriangleABC-asabaseandthechosenrepresentativeRasthetopWeightedmeanisanattempttofindthevertexthat“best”representstheothervertices:Anaveragevertexissynthesizedfi-omtheclusterasaweightedmean,wheretheweightsarethevertexcountsofthenodesinthecluster(rememberthatleafnodesrepresentasinglevertex,intermediatenodesrepresentallleavesintheirsubtree).thatisclosesttothemeanischosen.ThevertexUnfortunately,thisdoesnottakeintoaccountanysurfaceproperties,andourexperimentsshowthatresultsusingthishaveatleastonevertexinthecluster.Errorareaisanattempttomeasurethechangeintheextentoftheobject’ssurface:Ifaclusterofverticesisreplacedbyarepresentative,theareasofmostinvolvedtriangleschange.&&@&Bcheuristicarevisuallynotasappealingastheothertwoheuristics.Weightedmeanwaskeptforthesolepurposeofhandlingindexedlinesets(seebelow).3.4ComputingthereducedtrianglesetS.4Bctc%tf-’(y’-’Figure4:DifferentchoicesoftherepresentativeinfluencetheareaoftheresultingtrianglemeshAfterthenumberofverticeshasbeenreducedbythedesiredamount,thesetoftrianglesassociatedwiththereducedvertexsetmustbereconstructed.Foreverytriangle,itsverticesarereplacedbytherepresentativechosenforthatvertex.Thisprocessmayproducedoublets(triangleswithidenticalvertices)forwhichonlyoneinstanceiskept.Trianglesmayalsocollapseintolines,mostofwhichareidenticaltotheedgeofanothertriangleandcanbediscarded.Theremaininglinesareusuallyimportantfortheappearanceofthemodelandarethus127saved.Sometimestrianglescollapseintopoints,whichareremovedfromthemodel.4.DEALINGWITHVRMLSPECIFICSUptonowwehavesilentlyassumedthatthegeometricmodelconsistsofanunstructuredsetoftriangles,andwehaveneglectedinthediscussionavarietyofpropertiesspecifictoVRMLmodels.filerequiresthatadditionalnodes(suchasbindings)areoutput,thewholestructureiswrappedinanadditionalSeparator.ThechildrenoftheLODnodearetheIndexedFaceSetscontainingthecomputedlevelsofdetail.Ifanytrianglescollapsedtolinesareproducedasaresultoftheclusteringprocess,anadditionalIndexedLineSetisgeneratedtocomplementtheIndexedFaceSet,andtheresultingstructureiswrappedinaSeparator.4.3Triangulation4.1Non-polygonalnodesVRMLmodelsdonotonlyconsistoftrianglesorpolygons,butalsoofotherprimitiveslikespheresortext,andofcontext-definingnodessuchastransformations.However,theessentialstructureofVRMLscenesistheIndexedFaceSetanditshelpernodesCoordinate,Normal,TextureCoordinate2,andMaterial.LargeamountsofgeometricprimitivesarealmostexclusivelyspecifiedusingIndexedFaceSets,andthereforeitisreasonabletoconcentrateonthisnodeforlevelofdetailgeneration.LevelofdetailgenerationdealingwithVRMLgeometryotherthanIndexedFaceSetsmaybecomeaninterestingareaforfutureresearch,butthisisbeyondthescopeofthispaper.4.2ScenegraphstructureandoutputformatVRMLmodelsandscenesarenot“flat”,butareratherarrangedinahierarchicalscenegraph,soanalgorithmdealingwithasinglesetofpolygonsisnotsuftlcient.ThesimpleyeteffectivesolutionthatwasusedinLODmTARistotraversetheVRMLmodelandapplytheLODgenerationtoeveryIndexedFaceSetindividually,producingforeachanewLODnode(detailsonhowtodealwithmultipleIndexedFaceSetsaregiveninsection5).!i&“”Figure6:AsingleindexedfacesetisconvertedintoasubtreewithasingleLODnodeLODESTARreplaceseveryIndexedFaceSetintheoriginalfilewithasubtreecontainingthecomputedLODS.ThissubtreecontainsasingleLODnode.Ifthestructureofthe128Asalreadymentioned,mostlevelofdetailalgorithmsincludingLODELSTARcanonlydealwithtrianglesasaninput.Thetriangulationisnecessarybecauseafteravertexclusteringoperation,anyn-sidedtriangle(with03)almostcertainlybecomesnon-planar.Thereforealln-sidedpolygonsaretriangulatedfirstbyusingthealgorithmfrom[4].Asasideeffect,allconcavepolyg?nsareremovedfromthemodel,whichallowstheuseofalgorithmsthataresimpler,morerobustandfaster.Theexceptionarequadrilaterals,forwhichtheerrorisoftensmallandhencetolerable(i.e.non-visible).Itisnecessary,though,tocheckanyquadrilateralsforvalidityafteramodificationofitsvertices.Concavequadrilateralsorquadrilateralswhicharedistortedinspacemorethanauser-specifiedthreshold(measuredasthemaximumanglebetweenthenormalsatthevertices)aresplitintotwotriangles(Figure7).tnonconvexquadrilaterald*OlteCtquadrilateralFtgure7:DegeneratedquadrilateralsmustbesplitTriangulationincreasesthenumberofpolygonsandcaninvolveaperformancepenalty.However,most3-Drenderingenginestriangulateallgeometryinternally[10],sowiththeuseoftrianglestrips,aperformancepenaltycanbeavoided.Thisconsiderationofcourseassumesthattherendererdetectsandusestrianglestrips,whichunfortunatelycannotbeinfluencedfromwithinaVRMLfile.4.4LinesIndexedLineSetscanbetreatedalmostlikeIndexedFaceSets:Verticesareclusteredwithoctreequantization,andanewIndexedLineSetisconstructedfromthereducedvertexsetforeverylevelofdetail.TheoutputdepthbetheleveloftheoctreecorrespondingtolevelofisequivalenttothestructuredepictedinFigure6,exceptdetailbeingcomputed:thatIndexedFaceSetsarereplacedbyIndexedLineSets.However,forIndexedLineSetstheonlyapplicableheuristics=rootsize.43I2@’lfl.1forrepresentativeselectionisweightedmean.Theheightofthescreenhiscomputedfromthecameraheightanglealphaandthefocallengtifi4.5Bindingsh=2tan(cuZ)fNon-indexedbindingsimposeaone-to-onerelationshipGiventhedesirederrorrange(inpercent),wecancomputebetweenentriesintheIndexedFaceSetfieldsandthethemaximumprojecteddeferralpsas:correspondinghelpernodes.Theycannotbemaintainedifmultiplelevelsofdetailaretosharethesamematerials,ps=errorrange1100.hnormalsetc.Thereforenon-indexedbindingsareFinally,fromtherelation&s=l/ps,wecancomputethetransformedintothecorrespondingindexedbindings,andrangedasanindexwillbesynthesized.Inthiscase,anadditionalMaterialBindingorNormalBindingisgenerated,d=sl(errorrange1100~2.tan(d))Totakeintoaccounttheextentofthecluster,fortheactual4.6Rangevaluesrangeonehastoaddtheradiusoftheboundingsphereoftheclustertod.TheselectionofaLODinVRMLisperformedbycomparingranges.AviewerswitchestothenextLODifthedistanceoftheobjecttotheviewpointisgreaterthanor5.JOININGNODESequaltoaspecifiedvalue.Forsatisfactoryperformance,theLODgeneratorhastocomputereasonablerangevalues.OftenVRMLfilesareproducedwithprimitiveconvertersthatgeneratemanyIndexedFaceSetsinsequence,eachscreencontainingveryfewpolygons,ComputinglevelsofdetailsforeveryIndexedFaceSetofsuchamodelhasatendencyofrippingapartthemodelandwddktaneeproducesuselessLODS(seeFigure9),aproblemalsoreportedby[5],sSizeFortunately,mostofthesedegeneraciescanbecuredwithapsprojectedsizeverysimplealgorithmthatjoinssequentialIndexedFaceSetshscreenheightintooneifpossible.ThisalgorithmdoesnotevenrequireaviewingangleknowledgeoftheinvolvedgeometrybutcanoperateinpurelysyntacticalwayontheVRMLfile.ItdoesnotworkFigure8:AheuristicisusedtocomputetherangevaluesrequiredfortheLODnodeineverycase(thiswouldrequireadeepanalysisofbothmodelstructureandgeometry),butitcuresmostoftheThenextlevelofdetailiscomputedbymovingverticesdegeneraciesthatwe‘haveencounteredsofar.andevenfromaclustertoaselectedrepresentative.Themaximummoreimportantly,itworksveryfast.visibleerrorintroducedbythisoperationisequaltothemaximumdistanceavertexcanmoveinscreenspacedue5.1Basicjoiningalgorithmtoaclusteringoperation(deviation).ThegoalistocomputeLODswitchingrangesinsuchawaythatthismaximumForthecomponentsofaboundaryrepresentationvisibleerrordoesnotexceedauserdefinedthreshold,that(IndexedFaceSet,IndexedLineSetMaterial,Normal,isspecifiedasapercentageofthescreenheight.TextureCoordinate2,Coordinate)andSeparators,GroupsandBindings,subsequentnodesofthesametypearejoinedTheviewermustswitchLODSifthemaximumdeviationunlessthesecondistaggedwithDEF.sprojectedontothescreenisgreaterthanerrorrangespecifiedasafractionoftheheightofthescreen.LetIncaseofmultipleSeparatororGroupnodes,thesub-rootsizebetheextentofthecubeassociatedwiththeoetreegroupscanbejoined.Inthisprocess,thecomponentsofaroot(notethattheactualsizeiscomputedfromthelocalboundaryrepresentationthatspanmultiplesub-groupsarecoordinatesintheoctreemodifiedbythecurrentscalejoinedintoonenodeofthattype,soasinglefactorfromprecedingScaleorTransformnodes!)andIndexedFaceSetcanbesynthesized.129NotethatitisnecessarytoinsertanewMaterialBindingsothatthesynthesizedMaterialnodeisputincorrectrelationtothesynthesizedIndexedFaceSet.Example2Separator{Coordinate{point[101112,131415,IndexedFaceSet161718]}{coordIndex[0,1,2,-11?SeparatorCoordinateIndexedFaceSet){){point[202122,232425,2627281{coordIndex[0,1,2,-11}}Figure9:ThehulloftheshipmodelwasrepresentedbymanysmallIndexedFaceSets(oneshowninupperimag).WhencomputingLODS,thehullpartsaremodifiedindividually,andundesirableholesappeary.Thiscanbesuppressedbyjoiningnodes.Example1Separator{0.41}becomesSeparator{Coordinate{point[101112,131415,161718,202122,232425,262728]}IndexedFaceSet}JoiningtwoCoordinateSeparatornodeswithpossiblydifferent{coordIndex[0,1,2,-1,3,4,5,-1]}Material{diffuse0.50.6IndexedFaceSet{coordIndex[1,2,3,-11?Separator{Material{diffuse0.30.3IndexedFaceSet(coordIndex[4,5,6,-1]subnodesandpossiblydifferentIndexedFaceSetsubnodes:ThealgorithmalsoworkswithCoordinate,NormalandTextureCoordinate2nodes:0.3)}5.2TrailingSeparatorsThejoiningalgorithmsworksbytraversingthescenegraphbottom-upfromtheleaves,sothatjoinabilitycanbepropagatedupwards.Toimprovechancesofjoinability,trailingSeparatorsareremoved(aSeparatornodeontheendofalistisnotnecessary).SeparatorSeparator}}}becomesSeparator{IndexedFaceSet{{IndexedFaceSet{coordIndex[0,1,2,-11)becomesSeparator{[0.50.30.60.30.4,0.3]Material{diffuseColox}MaterialBindingIndexedFaceSetcoordIndexxnaterialIndex})(valuePER_FACE_INDEXED{[1,2,3,-1,4,5,6,-11[0,11{coordIndex[0,1,2,-1]}JoiningtwoSeparatornodeswithdifferentMaterialsubnodesandpossiblydifferentIndexedFaceSetsubnodes.130Limitations.Thejoiningalgorithmisaheuristicthatwasdevelopedafterstudyingthekindofdegeneraciesthatarecommonlyfound.ItonlyworksforrelativelysimplecasesinvolvingdirectrelationsbetweenthecomponentsofanIndexedFaceSet.CaremustbetakenthatnoothernodesuchasaTransformispresentthatforbidsthejoining.References[1]J.Clark:HierarchicalGeometricModelsforVisibleSurfaceAlgorithms.CommunicationsoftheACM,Vol.19,No.10,pp.547-554(1976)[2]M.Eck,T.DeRose,T.Duchamp,H.Hoppe,M.Lounsbery,W.Stuetzle:MultiresolutionAnalysisofArbitraryMeshes.ProceedingsofSIGGRAPH’95,pp.173-182(1995)[3]M.Gervautz,W.Purgathofer:Asimplemethodforcolorquantization:octreequantization.NewTrendsinComputerGraphics,ProceedingsofComputerGraphicsInternational’88,p.219-231,Springer,Geneva.Reprintedin:GraphicsGemsI,pp.287-293(1990)[4]A.Narkhede,D.Manocha:FastPolygonTriangulationBasedOnSeidel’sAlgorithm.GraphicsGemsV,AcademicPress,pp.394-397(1995)[5]J.-L.Pajon,Y.Collenot,X.Lhomme,N.Tsingos,F.Sillion,P.Guiloteau,P.Vuyslteker,G.Grillon,D.David:BuildingandExploitingLevelsofDetail:AnOverviewandSomeVRMLExperiments.6.IMPLEMENTATIONThealgorithmdescribedinthispaperhasbeenimplementedunderC++andportedtoavarietyofplatforms,includingmultipleflavorsofUnix,0S/2,andDOS.Becauseofthedesigndecisionsoutlinedearlier,itrunsveryfast.ItworksreasonablyrobustoninputfilesthatdonotexactlycomplytotheVRMLspecification(suchassomeInventorfiles).Furthermore,thesoftwarecanbeusedasa,,cleanup”filterforVRMLfiles:Asexplainedinsection3.1,theprocessremoveddoubletsinthevertices,colorsetc.,soinvokingtheprogramwiththe,,nolevelsofdetail”optioncleansupredundantmodels.Seetheappendixforsomesampleresults,ProceedingsofVRML’95,SanDiegoCA,pp.117-122(1995)[6]JarekRossignac,PaulBorrel:Multi-Resolution3DApproximationforRenderingComplexScenes.IFIPTC5.WG5.10IIConferenceComputerGraphics(1993)onGeometricModelingin7.CONCLUSIONSANDFUTUREWORKWehavepresentedanalgorithmthatproduceslevelsofdetailforpolygonalobjects.ThisalgorithmsreadsandwritesVRMLfilesandtakescareoftheparticularneedsofthehierarchicalstructureandotheradvancedfeaturesofthisformat.OurcurrentimplementationwasdesignedtoworkwiththeVRML1.0specification.Naturally,weintendtomodifytheimplementationtotoworkwithVRML2.0files,whichwillmainlyinvolveadaptingtheparser.softwareisapartialresultofalargerresearchprojectaimedatdevelopingbettermethodstocontrolthebandwidthrequirementsoflargedistributedvirtualenvironments.Itisusedtocreatethelevelsofdetailgeometrytransmissionrequiredbythedemand-drivenprotocol[8]forclient-serverbasedvirtualenvironments.Tofurtherincreasenetworkperformanceandavoidwasteofbandwidth,wehavealsodevelopedacustomcompressionmethodforVRML.TheLOD~TAR[7]G.Schaufler,W.Sturzlinger:GeneratingMultipleLevelsofDetailfromPolygonalGeometryModels.VirtualEnvironments’95,Springer(1995)[8]D.Schmalstieg,M.Gervautz:Demand-DrivenTransmissionforDistributedVirtualGeometryEnvironments.ComputerGraphicsForum(Proc.EUROGRAPHICS‘96),Vol.15,No.3,pp.421-433(1996)[9]W.Schroeder,J.Zarge,W.Lorensen:DecimationofTriangleMeshes.ProceedingsofSIGGRAPH’92,pp.65-70(1992)[10]SGI:OpenGLProgrammingGuide,Addison-Wesley(1993)[11]G.TurkRe-TilingPolygonSurfaces.ProceedingsSIGGRAPH’92,pp.55-64(1992)ofAppendix:ResultsTheLODESTARcodewastestedwh.halargenumberofAcknowledgments.ManythankstoRainhardSainitzerandHerbertBucheggerwhoworkedontheimplementationofthisalgorithm.Resources.MoredetailedresultsofLODESTARandbinariesformostpopularplatformsmodelsdownloadedresultsofviatheInternet.andimagestheimplementation.HerewepresentTheafewofthequantitativeperformancetogiveanimpressioncanbeobtainedfreeofcharge,,Enterprise”fornon-profituseathttp:lhvw.cg.tuwien.ac.at/researcWvrllodestarlmodel(10LODS)wascomputedin5.4secondsandthe,,Galleon”model(8LODS)wascomputedin7.8secondsonanSGIIndyR4400/150workstation.131Table1:,,Ente~rise”modelstatisticsTable2:,,Galleon”modelstatisticsLODTri’sLineRangeLODTri’sLineRangeI42I6I553]355213999152I7167I679313182172I8I511325!11219116126151150201o469800091962266440706882456714781478108248840125051250546122909321234142368629811411960Figure10:ThreeLODSoftheenterprisemode(LOD#0,4,8).Ifdisplayedinasizecorrespondingtothecomputedranges,thequalitydegradationisnolongervisibleFigure11:ThreeLODSfromthegalleonmodel(LOD#O,4,5)132