DOC PREVIEW
UVA CS 445 - Visibility Calculations and Occlusion Culling

This preview shows page 1-2-3-20-21-40-41-42 out of 42 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 CullingAdminGrades for assignment 1 should be outClipping assignment: how’s it going?–Sample solution (partial) on webDemoVideosRecap: Visibility CullingThe 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 cullingThe obvious question: why bother?–Off-screen geometry: solved by clipping–Occluded geometry: solved by Z-bufferThe (obvious) answer: efficiency–Clipping and Z-buffering take time linear to the number of primitives–Would like rendering to scale sublinearlyThe GoalOur 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 visibleZ-buffer and clip this for the exact solution–This conservative estimate is the potentially visible set or PVSRecap: View-Frustum CullingAn old idea (Clark 76):–Organize primitives into clumps–Before rendering the primitives in a clump, test a bounding volume against the view frustumIf the clump is entirely outside the view frustum, don’t render any of the primitivesIf the clump intersects the view frustum, add to PVS and render normallyCommon bounding volumes: spheres, axis-aligned bounding boxesOther 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 testingIf a clump is entirely outside or entirely inside view frustum, no need to test its childrenCells & PortalsGoal: 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 & PortalsAn example:Cells & PortalsIdea: –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 portalsSo 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 & PortalsView-independent solution: find all cells a particular cell could possibly see:C can only see A, D, E, and HADHFCBEGADHECells & PortalsView-independent solution: find all cells a particular cell could possibly see:H will never see FADHFCBEGADCBEGCells and PortalsQuestions:–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 PortalsAirey (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: HistoryTeller (1993): view-independent + view-dependent–Portal-portal visibility calculated by line stabbing usinglinear programCell-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: HistoryLuebke & 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 AlgorithmDepth-first adjacency graph traversal–Render cell containing viewer–Treat portals as special polygonsIf portal is visible, render adjacent cellBut 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 AlgorithmRecursively rendering cells while clipping to portal boundaries not new–Visible-surface algorithm (Jones 1971): general polygon-polygon clippingElegant, expensive, complicated–Conservative overestimate (pfPortals): use portal’s cull boxCull box = x-y screenspace bounding boxCheap to compute, very cheap to intersectpfPortals AlgorithmHow badly does the cull box approximation overestimate PVS?A: Not much for most architectural scenesNote: Can implement mirrors as portals with an extra transformation!–Some clipping & Z-buffering issues –Must limit recursionCells and Portals: DetailsUsually 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 timeTeller: 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 memoryUse Teller stab trees to load in only cells that might be visibleCreating Cells and PortalsGiven a model, how might you extract the cells and portals?–Airey: k-D tree (axis-aligned


View Full Document

UVA CS 445 - Visibility Calculations and Occlusion Culling

Documents in this Course
Lighting

Lighting

49 pages

Color

Color

20 pages

Clipping

Clipping

10 pages

Shadows

Shadows

95 pages

Color

Color

37 pages

Radiosity

Radiosity

49 pages

Clipping

Clipping

59 pages

Assign 3

Assign 3

28 pages

Splines

Splines

17 pages

Color

Color

17 pages

Load more
Download Visibility Calculations and Occlusion Culling
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Visibility Calculations and Occlusion Culling and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Visibility Calculations and Occlusion Culling 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?