A visibility algorithm for hybrid geometry- and im

AVisibilityAlgorithmforHybridGeometry-andImage-BasedModelingandRenderingThomasA.FunkhouserPrincetonUniversityAbstractHybridgeometry-andimage-basedmodelingandrenderingsystemsusephotographstakenofareal-worldenvironmentandmappedontothesurfacesofa3Dmodeltoachievephotoreal-ismandvisualcomplexityinsyntheticimagesrenderedfromarbitraryviewpoints.Aprimarychallengeinthesesystemsistodevelopalgorithmsthatmapthepixelsofeachphotographefficientlyontotheappropriatesurfacesofa3Dmodel,aclassicalvisiblesurfacedetermina-tionproblem.Thispaperdescribesanobject-spacealgorithmforcomputingavisibilitymapforasetofpolygonsforagivencameraviewpoint.Thealgorithmtracespyramidalbeamsfromeachcameraviewpointthroughaspatialdatastructurerepresentingapolyhedralconvexdecompositionofspacecontainingcell,face,edge,andvertexadjacencies.Beamintersectionsarecomputedonlyforthepolygonalfacesontheboundaryofeachtraversedcell,andthusthealgorithmisoutput-sensitive.Thealgorithmalsosupportsefficientdeterminationofsilhouetteedges,whichallowsanimage-basedmodelingandrenderingsystemtoavoidmappingpixelsalongedgeswhosecolorsaretheresultofaveragingoverseveraldisjointsurfaces.Resultsreportedforseveral3Dmodelsindicatethemethodiswell-suitedforlarge,densely-occludedvirtualenvironments,suchasbuildinginteriors.1IntroductionHybridgeometry-andimage-basedrendering(GIBR)methodsareusefulforsynthesizingphoto-realisticimagesofreal-lifeenvironments(e.g.,buildingsandcities).Ratherthanmodelinggeo-metricdetailsandsimulatingglobalilluminationeffects,asintraditionalcomputergraphics,onlyacoarselydetailed3Dmodelisconstructed,andphotographsaretakenfromadiscretesetofviewpointswithintheenvironment.Thecalibratedphotographicimagesaremappedontothesur-facesofthe3Dmodeltoconstructarepresentationofthevisualappearanceofgeometricdetailsandcomplexilluminationeffectsoneachsurface.Then,novelimagescanberenderedforarbi-traryviewpointsduringaninteractivevisualizationsessionbyreconstructionfromthesehybrid1geometry-andimage-basedrepresentations.Thismethodallowsphotorealisticimagestobegen-eratedofvisuallyrichandlargeenvironmentsoverawiderangeofviewpoints,whileavoidingthedifficultiesofmodelingdetailedgeometryandsimulatingcomplexilluminationeffects.ApplicationsforGIBRsystemsincludeeducation,commerce,training,telepresence,anden-tertainment.Forexample,grammarschoolstudentscanusesuchasystemto“visit”historicalbuildings,temples,andmuseums.Realestateagentscanshowapotentialbuyertheinteriorofahomeforsaleinteractivelyviatheinternet[20].Distributedinteractivesimulationsystemscantrainteamsofsoldiers,firefighters,andotherpeoplewhosemissionsaretoodangerousortooexpensivetore-createintherealworld[3,26].Entertainmentapplicationscansynthesizephoto-realisticimageryofrealworldenvironmentstogenerateimmersivewalkthroughexperiencesforvirtualtravelandmulti-player3Dgames[21].TheresearchchallengesinimplementinganeffectiveGIBRsystemaretoconstruct,store,andre-samplea4Drepresentationfortheradianceemanatingfromeachsurfaceofthe3Dmodel.Previousrelatedmethodsdatebacktothemovie-mapsystembyLippman[25].Greene[18]pro-posedasystembasedonenvironmentmaps[2]inwhichimagescapturedfromadiscretesetofviewpointsareprojectedontothefacesofacube.ChenandWilliams[6]describedamethodinwhichreferenceimagesareusedwithpixelcorrespondenceinformationtointerpolateviewsofascene.Debevecetal.[9,10]developedasysteminwhichphotographswereusedtoconstructa3Dmodelmadefromparameterizedbuildingblocksandtoconstructa“view-dependenttexturemap”foreachsurface.Gortleretal.[17]usedapproximate3Dgeometrytofacilitateimagereconstruc-tionfromtheir4DLumigraphrepresentation.Coorg[7]constructedverticalfacadesfrommultiplephotographsandmappeddiffuseimageryontothesurfacesforinteractivevisualization.Severalwalkthroughapplicationsandvideogamesapply2Dview-independentphotographictexturestocoarse3Dgeometry[22].Otherrelatedimage-basedrepresentationsaresurveyedin[8],includingcylindricalpanorama[5,28],LightFields[24],andlayereddepthimages[33].AnimportantstepinconstructingaGIBRrepresentationistomappixelsamplesfromeveryphotographontothesurfacesofa3Dmodel.Thechallengeistodevelopalgorithmsthatdetermine2whichpartsofwhich3Dsurfacesarevisiblefromthecameraviewpointofeveryphotograph.Thisisaclassichiddensurfaceremoval(HSR)problem,butwithauniquecombinationofrequirementsmotivatedbyGIBRsystems.First,unlikealgorithmscommonlyusedincomputergraphics,theHSRalgorithmmustresolvevisiblesurfaceswithobject-spaceprecision.Image-spacealgorithmsmaycausesmallsurfacestobemissedorradiancesamplestobemisalignedonasurface,causingartifactsandblurringinreconstructedimages.Second,thealgorithmshouldcomputeacompletevisibilitymapforeachphotograph,encodingnotonlythevisiblesurfacesbutalsothevisibleedgesandverticeswiththeirconnectivitiesontheviewplane.Fromthevisibilitymap,aGIBRsystemcandetectpixelscoveringmultipledisjointsurfaces(e.g.,alongsilhouetteedges)andavoidmappingthemontoanysinglesurface,whichcausesnoticeableartifactsinresampledimages.Asanexample,considerthesituationshowninFigure1.Theimageontheleftshowsa“photograph”takenwithasyntheticcamera