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 CullingAdminGrades for assignment 1 should be outClipping assignment: how’s it going?–Sample solution (partial) on webDemoVideosRecap: Painter’s AlgorithmSimple approach: render the polygons from back to front, “painting over” previous polygons:–Draw blue, then green, then pinkRecap: Painter’s AlgorithmIntersecting polygons present a problemEven 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 AlgorithmsEarly 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 CaseMinimum worst-case cost of computing the fragments for a scene composed of n polygons: O(n2) visible fragmentsRecap: Analytic Visibility AlgorithmsSo, for about a decade (late 60s to late 70s) there was intense interest in finding efficient algorithms for hidden surface removalWe’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 planesSplitting planes can be arbitrarily orientedNotice: nodes are always convexRecap: BSP Trees123456789135687 9 2 4Recap: BSP Tree Construction for PolygonsSplit along the plane containing any polygonClassify 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-spaceRecurse down the positive half-spaceRecap: BSP Tree Traversal for PolygonsQuery: 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 DemoNice demo:–http://symbolcraft.com/graphics/bsp/index.html –Also has a link to the BSP Tree FAQSummary: BSP TreesPros:–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 viewportIf number of objects incident to viewport is zero or one, visibility is trivialOtherwise, subdivide into smaller viewports, distribute primitives among them, and recurseWarnock’s AlgorithmWhat is the terminating condition?How to determine the correct visible surface in this case?Warnock’s AlgorithmPros:–Very elegant scheme–Extends to any primitive typeCons:–Hard to embed hierarchical schemes in hardware–Complex scenes usually have small polygons and high depth complexityThus most screen regions come down to the single-pixel caseThe Z-Buffer AlgorithmBoth BSP trees and Warnock’s algorithm were proposed when memory was expensiveEd 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 AlgorithmWe know how to rasterize polygons into an image discretized into pixels:The Z-Buffer AlgorithmWhat happens if multiple primitives occupy the same pixel on the screen? Which is allowed to paint the pixel?The Z-Buffer AlgorithmIdea: 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 AlgorithmAugment 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, dependingEdge equations: Z is just another planar parameter:z = Ax + By + C–Look familiar?–Total cost:1 more parameter to increment in inner loop3x3 matrix multiply for setup–See interpolating color discussion from lecture 10Edge walking: can interpolate Z along edges and across spansInterpolating ZThe Z-Buffer AlgorithmHow 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 ProsSimple!!!Easy to implement in hardwarePolygons can be processed in arbitrary orderEasily handles polygon interpenetrationEnables deferred shading –Rasterize shading
View Full Document