Slide 1AdminDemoRecap: Visibility CullingThe GoalRecap: View-Frustum CullingCells & PortalsSlide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Cells and PortalsSlide 20Cells and Portals: HistorySlide 22pfPortals AlgorithmSlide 24Slide 25Cells and Portals: DetailsWhy View-Independent?Creating Cells and PortalsCells and Portals: DiscussionGeneral Occlusion CullingSlide 31Loose Front-To-Back SortingImage-Space Occlusion CullingHierarchical Z-BufferSlide 35Slide 36Slide 37Slide 38Hierarchical Z-Buffer: DiscussionModern Occlusion CullingSlide 41111 uses for Occlusion QueriesCS 445: Introduction to Computer GraphicsDavid LuebkeUniversity of VirginiaVisibility Calculationsand Occlusion CullingAdminGrades for assignment 1 should be outClipping assignment: how’s it going?–Sample solution (partial) on webDemoVideosRecap: Visibility CullingThe basic idea: don’t render what can’t be seen–Off-screen: view-frustum culling–Occluded by other objects: occlusion culling–Generically: visibility calculation or visibility cullingThe obvious question: why bother?–Off-screen geometry: solved by clipping–Occluded geometry: solved by Z-bufferThe (obvious) answer: efficiency–Clipping and Z-buffering take time linear to the number of primitives–Would like rendering to scale sublinearlyThe GoalOur goal: quickly eliminate large portions of the scene which will not be visible in the final image–Don’t want the exact visibility solution!–Want quick-and-dirty conservative estimate of which primitives might be visibleZ-buffer and clip this for the exact solution–This conservative estimate is the potentially visible set or PVSRecap: View-Frustum CullingAn old idea (Clark 76):–Organize primitives into clumps–Before rendering the primitives in a clump, test a bounding volume against the view frustumIf the clump is entirely outside the view frustum, don’t render any of the primitivesIf the clump intersects the view frustum, add to PVS and render normallyCommon bounding volumes: spheres, axis-aligned bounding boxesOther bounding volumes: oriented bounding boxes, ellipsoids, caplets, etc.How big should the clumps be?–Choose minimum size so:cost testing bounding volume << cost clipping primitives–Organize clumps into a hierarchy of bounding volumes for more efficient testingIf a clump is entirely outside or entirely inside view frustum, no need to test its childrenCells & PortalsGoal: walk through architectural models (buildings, cities, catacombs)These divide naturally into cells–Rooms, alcoves, corridors… Transparent portals connect cells–Doorways, entrances, windows… Notice: cells only see other cells through portalsCells & PortalsAn example:Cells & PortalsIdea: –Cells form the basic unit of PVS–Create an adjacency graph of cells–Starting with cell containing eyepoint, traverse graph, rendering visible cells –A cell is only visible if it can be seen through a sequence of portalsSo cell visibility reduces to testing portal sequences for a line of sight…Cells & PortalsADHFCBEGHB C D F GEACells & PortalsADHFCBEGHB C D F GEACells & PortalsADHFCBEGHB C D F GEACells & PortalsADHFCBEGHB C D F GEACells & PortalsADHFCBEGHB C D F GEACells & PortalsADHFCBEGHB C D F GEA??Cells & PortalsADHFCBEGHB C D F GEAXXCells & PortalsView-independent solution: find all cells a particular cell could possibly see:C can only see A, D, E, and HADHFCBEGADHECells & PortalsView-independent solution: find all cells a particular cell could possibly see:H will never see FADHFCBEGADCBEGCells and PortalsQuestions:–How can we detect whether a given cell is visible from a given viewpoint?–How can we detect view-independent visibility between cells?The key insight: –These problems reduce to eye-portal and portal-portal visibilityCells and PortalsAirey (1990): view-independent only–Portal-portal visibility determined by ray-casting Non-conservative portal-portal test resulted in occasional errors in PVS–Slow preprocess–Order-of-magnitude speedupsCells and Portals: HistoryTeller (1993): view-independent + view-dependent–Portal-portal visibility calculated by line stabbing usinglinear programCell-cell visibility stored in stab trees View-dependent eye-portal visibility stage further refines PVS at run time–Slow (?) preprocess–Elegant, exact schemeCells and Portals: HistoryLuebke & Georges (1995): view-dependent only–Eye-portal visibility determined by intersecting portalcull boxes–No preprocess (integrate w/ modeling)–Quick, simple hack–Now-archaic public-domain library: pfPortalspfPortals AlgorithmDepth-first adjacency graph traversal–Render cell containing viewer–Treat portals as special polygonsIf portal is visible, render adjacent cellBut clip to boundaries of portal!Recursively check portals in that cell against new clip boundaries (and render) –Each visible portal sequence amounts to a series of nested portal boundaries Kept implicitly on recursion stackpfPortals AlgorithmRecursively rendering cells while clipping to portal boundaries not new–Visible-surface algorithm (Jones 1971): general polygon-polygon clippingElegant, expensive, complicated–Conservative overestimate (pfPortals): use portal’s cull boxCull box = x-y screenspace bounding boxCheap to compute, very cheap to intersectpfPortals AlgorithmHow badly does the cull box approximation overestimate PVS?A: Not much for most architectural scenesNote: Can implement mirrors as portals with an extra transformation!–Some clipping & Z-buffering issues –Must limit recursionCells and Portals: DetailsUsually separate model into occluders and detail objects–Occluders: walls, floors–Detail objects: desks, chairs, pencils–Cell creation process only accounts for occluders (Why?)pfPortals: find detail object visibility through portal sequences at run timeTeller: also precompute into PVSWhy View-Independent?If view-dependent techniques can often calculate a reasonable PVS fast enough, why bother finding view-independent PVS?One good answer: smart prefetching–Soda Hall walkthrough (Funkhouser)Whole model doesn’t fit in memoryUse Teller stab trees to load in only cells that might be visibleCreating Cells and PortalsGiven a model, how might you extract the cells and portals?–Airey: k-D tree (axis-aligned
View Full Document