DOC PREVIEW
UVA CS 445 - The Z-buffer Visibility Culling

This preview shows page 1-2-15-16-17-32-33 out of 33 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 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 33 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 33 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 33 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 33 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 33 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 33 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1AdminDemoRecap: Painter’s AlgorithmSlide 5Recap: Analytic Visibility AlgorithmsRecap: Analytic Algorithms Worst CaseSlide 8Recap: BSP TreesRecap: BSP TreesRecap: BSP Tree Construction for PolygonsRecap: BSP Tree Traversal for PolygonsBSP DemoSummary: BSP TreesWarnock’s Algorithm (1969)Warnock’s AlgorithmSlide 17The Z-Buffer AlgorithmSlide 19Slide 20Slide 21Slide 22Interpolating ZSlide 24Z-Buffer ProsZ-Buffer ConsVisibility CullingMotivationThe GoalSlide 30View-Frustum CullingEfficient View-Frustum CullingSlide 33CS 445: Introduction to Computer GraphicsDavid LuebkeUniversity of VirginiaVisibility: The Z-bufferVisibility CullingAdminGrades for assignment 1 should be outClipping assignment: how’s it going?–Sample solution (partial) on webDemoVideosRecap: Painter’s AlgorithmSimple approach: render the polygons from back to front, “painting over” previous polygons:–Draw blue, then green, then pinkRecap: Painter’s AlgorithmIntersecting polygons present a problemEven non-intersecting polygons can form a cycle with no valid visibility order:Even without such a cycle, not obvious how to sort (ex: cube)Recap: Analytic Visibility AlgorithmsEarly visibility algorithms computed the set of visible polygon fragments directly, then rendered the fragments to a display:–Now known as analytic visibility algorithmsRecap: Analytic Algorithms Worst CaseMinimum worst-case cost of computing the fragments for a scene composed of n polygons: O(n2) visible fragmentsRecap: Analytic Visibility AlgorithmsSo, for about a decade (late 60s to late 70s) there was intense interest in finding efficient algorithms for hidden surface removalWe’ll talk about two: –Binary Space-Partition (BSP) Trees–Warnock’s AlgorithmRecap: BSP Trees Binary Space Partition tree: organize all of space (hence partition) into a binary tree–Preprocess: overlay a binary tree on objects in the scene–Runtime: correctly traversing this tree enumerates objects from back to front–Idea: divide space recursively into half-spaces by choosing splitting planesSplitting planes can be arbitrarily orientedNotice: nodes are always convexRecap: BSP Trees123456789135687 9 2 4Recap: BSP Tree Construction for PolygonsSplit along the plane containing any polygonClassify all polygons into positive or negative half-space of the plane–If a polygon intersects plane, split it into two Recurse down the negative half-spaceRecurse down the positive half-spaceRecap: BSP Tree Traversal for PolygonsQuery: given a viewpoint, produce an ordered list of (possibly split) polygons from back to front:BSPnode::Draw(Vec3 viewpt)Classify viewpt: in + or - half-space of node->plane?// Call that the “near” half-spacefarchild->draw(viewpt);render node->polygon; // always on node->planenearchild->draw(viewpt);Intuitively: at each partition, draw the stuff on the farther side, then the polygon on the partition, then the stuff on the nearer sideBSP DemoNice demo:–http://symbolcraft.com/graphics/bsp/index.html –Also has a link to the BSP Tree FAQSummary: BSP TreesPros:–Simple, elegant scheme–Only writes to framebuffer (i.e., painters algorithm)Thus once very popular for video games (but no longer, at least on PC platform)Still very useful for other reasons (more later)Cons:–Computationally intense preprocess stage restricts algorithm to static scenes–Worst-case time to construct tree: O(n3)–Splitting increases polygon count Again, O(n3) worst caseOuchWarnock’s Algorithm (1969)Elegant scheme based on a powerful general approach common in graphics: if the situation is too complex, subdivide–Start with a root viewport and a list of all primitives–Then recursively:Clip objects to viewportIf number of objects incident to viewport is zero or one, visibility is trivialOtherwise, subdivide into smaller viewports, distribute primitives among them, and recurseWarnock’s AlgorithmWhat is the terminating condition?How to determine the correct visible surface in this case?Warnock’s AlgorithmPros:–Very elegant scheme–Extends to any primitive typeCons:–Hard to embed hierarchical schemes in hardware–Complex scenes usually have small polygons and high depth complexityThus most screen regions come down to the single-pixel caseThe Z-Buffer AlgorithmBoth BSP trees and Warnock’s algorithm were proposed when memory was expensiveEd Catmull (mid-70s) proposed a radical new approach called the z-buffer–(He went on to help found a little company named Pixar)The big idea: resolve visibility independently at each pixelThe Z-Buffer AlgorithmWe know how to rasterize polygons into an image discretized into pixels:The Z-Buffer AlgorithmWhat happens if multiple primitives occupy the same pixel on the screen? Which is allowed to paint the pixel?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:01001110000100001minminminzzzMThe 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, depending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 spansInterpolating ZThe Z-Buffer Algorithm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 polygons traverse?–What does this imply for the front of the pipeline?–How does Z-buffer load scale with visible polygons? With framebuffer resolution?Z-Buffer ProsSimple!!!Easy to implement in hardwarePolygons can be processed in arbitrary orderEasily handles polygon interpenetrationEnables deferred shading –Rasterize shading


View Full Document

UVA CS 445 - The Z-buffer Visibility 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 The Z-buffer Visibility 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 The Z-buffer Visibility 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 The Z-buffer Visibility 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?