VisibilityRecap: The Z-Buffer AlgorithmSlide 3Slide 4Slide 5Slide 6Recap: Interpolating ZThe Z-Buffer AlgorithmZ-Buffer ProsZ-Buffer ConsVisibility CullingMotivationThe GoalSlide 14View-Frustum CullingEfficient View-Frustum CullingSlide 17Cells & PortalsSlide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Cells and PortalsSlide 31David Luebke 1 01/14/19VisibilityCS 445/645Introduction to Computer GraphicsDavid Luebke, Spring 2003David Luebke 2 01/14/19Recap:The Z-Buffer Algorithm●Both BSP trees and Warnock’s algorithm were proposed when memory was expensive■Example: first 512x512 framebuffer > $50,000!●Ed Catmull (mid-70s) proposed a radical new approach called z-buffering■(He went on to help found a little company named Pixar)●The big idea: resolve visibility independently at each pixelDavid Luebke 3 01/14/19Recap:The Z-Buffer Algorithm●We know how to rasterize polygons into an image discretized into pixels:David Luebke 4 01/14/19Recap:The Z-Buffer Algorithm●What happens if multiple primitives occupy the same pixel on the screen? Which is allowed to paint the pixel?David Luebke 5 01/14/19Recap:The Z-Buffer Algorithm●Idea: retain depth (Z in eye coordinates) through projection transform■Recall canonical viewing volumes■Can transform canonical perspective volume into canonical parallel volume with:01001110000100001minminminzzzMDavid Luebke 6 01/14/19Recap:The Z-Buffer Algorithm●Augment framebuffer with Z-buffer or depth buffer which stores Z value at each pixel■At frame beginning initialize all pixel depths to ■When rasterizing, interpolate depth (Z) across polygon and store in pixel of Z-buffer■Suppress writing to a pixel if its Z value is more distant than the Z value already stored there○“More distant”: greater than or less than, dependingDavid Luebke 7 01/14/19●Edge equations: Z is just another planar parameter:z = Ax + By + C■Look familiar?■Total cost:○1 more parameter to increment in inner loop○3x3 matrix multiply for setup■See interpolating color discussion from lecture 10●Edge walking: can interpolate Z along edges and across spansRecap:Interpolating ZDavid Luebke 8 01/14/19The Z-Buffer Algorithm●To think about:■How much memory does the Z-buffer use?■Does the image rendered depend on the drawing order?■Does the time to render the image depend on the drawing order?■How much of the pipeline do occluded polgyons traverse?○What does this imply for the front of the pipeline?○How does Z-buffer load scale with visible polygons? With framebuffer resolution?David Luebke 9 01/14/19Z-Buffer Pros●Simple!!!●Easy to implement in hardware●Polygons can be processed in arbitrary order●Easily handles polygon interpenetration●Enables deferred shading ■Rasterize shading parameters (e.g., surface normal) and only shade final visible fragments■When does this help?David Luebke 10 01/14/19Z-Buffer Cons●Lots of memory (e.g. 1280x1024x32 bits)●Read-Modify-Write in inner loop requires fast memory●Hard to do analytic antialiasing●Hard to simulate translucent polygons●Precision issues (scintillating, worse with perspective projection)David Luebke 11 01/14/19Visibility Culling●The basic idea: don’t render what can’t be seen■Off-screen: view-frustum culling■Occluded by other objects: occlusion cullingDavid Luebke 12 01/14/19Motivation●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 primitivesDavid Luebke 13 01/14/19The Goal●Our goal: quickly eliminate large portions of the scene which will not be visible in the final image■Not the exact visibility solution, but a quick-and-dirty conservative estimate of which primitives might be visible○Z-buffer& clip this for the exact solution■This conservative estimate is called the potentially visible set or PVSDavid Luebke 14 01/14/19Visibility Culling●The remainder of this talk will cover:■View-frustum culling (briefly)■Occlusion culling in architectural environments ■General occlusion cullingDavid Luebke 15 01/14/19View-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 normallyDavid Luebke 16 01/14/19Efficient View-Frustum Culling●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 childrenDavid Luebke 17 01/14/19Efficient View-Frustum Culling●What shape should the bounding volumes be?■Spheres and axis-aligned bounding boxes: simple to calculate, cheap to test■Oriented bounding boxes converge asymptotically faster in theory■Lots of other volumes have been proposed, but most people still use spheres or AABBs.David Luebke 18 01/14/19Cells & 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 portalsDavid Luebke 19 01/14/19Cells & Portals●An example:David Luebke 20 01/14/19Cells & 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…David Luebke 21 01/14/19Cells & PortalsADHFCBEGHB C D F GEADavid Luebke 22 01/14/19Cells & PortalsADHFCBEGHB C D F GEADavid Luebke 23 01/14/19Cells & PortalsADHFCBEGHB C D F GEADavid Luebke 24 01/14/19Cells &
View Full Document
Unlocking...