VisibilityOverviewOcclusionPainter’s AlgorithmPainter’s Algorithm: ProblemsAnalytic Visibility AlgorithmsSlide 7Slide 8Slide 9Binary Space Partition Trees (1979)Binary Space Partition TreesBSP Trees: ObjectsSlide 13Slide 14Slide 15Slide 16Rendering BSP TreesSlide 18Slide 19Polygons: BSP Tree ConstructionPolygons: BSP Tree TraversalDiscussion: BSP Tree ConsBSP TreesBSP DemoSummary: BSP TreesSlide 26Slide 27Warnock’s Algorithm (1969)Warnock’s AlgorithmSlide 30Slide 31The Z-Buffer AlgorithmSlide 33Slide 34Slide 35Slide 36Interpolating ZSlide 38Z-Buffer ProsZ-Buffer ConsSlide 41Visibility CullingThe GoalSlide 44View-Frustum CullingEfficient View-Frustum CullingSlide 47Slide 48Cells & PortalsSlide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Cells and PortalsSlide 62Cells and Portals: HistorySlide 64Slide 65General Occlusion CullingSlide 67Loose Front-To-Back SortingImage-Space Occlusion CullingSlide 70Hierarchical Z-BufferSlide 72Slide 73Slide 74Slide 75Hierarchical Z-Buffer: DiscussionSlide 77Modern Occlusion CullingSlide 79111 uses for Occlusion QueriesSlide 81Fog filters – what’s wrong with it?Haze and the Z-bufferFog and the Z-bufferWater and the Z-bufferSlide 86VisibilityAaron BloomfieldCS 445: Introduction to GraphicsFall 2006(Slide set originally by David Luebke)2OverviewAnalytic Visibility AlgorithmsBSPsWarnock's AlgorithmZ-Buffer AlgorithmVisibility CullingCells and PortalsOcclusion CullingHierarchical Z-BufferModern Occlusion CullingFog3OcclusionFor most interesting scenes, some polygons will overlap:To render the correct image, we need to determine which polygons occlude which4Painter’s AlgorithmSimple approach: render the polygons from back to front, “painting over” previous polygons:Draw blue, then green, then pinkWill this work in general?5Painter’s Algorithm: ProblemsIntersecting polygons present a problemEven non-intersecting polygons can form a cycle with no valid visibility order:6Analytic Visibility AlgorithmsEarly visibility algorithms computed the set of visible polygon fragments directly, then rendered the fragments to a display:Now known as analytic visibility algorithms7Analytic Visibility AlgorithmsWhat is the minimum worst-case cost of computing the fragments for a scene composed of n polygons?Answer: O(n2)8Analytic 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 analytic visibility algorithms: Binary Space-Partition (BSP) TreesWarnock’s Algorithm9OverviewAnalytic Visibility AlgorithmsBSPsWarnock's AlgorithmZ-Buffer AlgorithmVisibility CullingCells and PortalsOcclusion CullingHierarchical Z-BufferModern Occlusion CullingFog10Binary Space Partition Trees (1979)Basic algorithmFor each triangle (or polygon) t in the sceneFind the plane that t implicitly formsLet the eyepoint be on one side of tThen t can be drawn before all triangles on the other side of tSo we draw the “far” stuff first, then t, then the “near” stuffRestrictionsOnly works on a scene where no polygons crosses a plane defined by another polygonThis also means you can’t have a cycleThis restriction is relaxed by a preprocessing stepSplit up such triangles into multiple triangles11Binary Space Partition TreesBSP tree: organize all of space (hence partition) into a binary treePreprocess: overlay a binary tree on objects in the sceneThis includes the step of splitting a primitive that crosses a plane into multiple primitivesRuntime: correctly traversing this tree enumerates objects from back to frontIdea: divide space recursively into half-spaces by choosing splitting planesSplitting planes can be arbitrarily orientedNotice: nodes are always convex12BSP Trees: Objects12345678913BSP Trees: Objects12345678956 78 9 1 2 3414BSP Trees: Objects1234567895 67 8 9234 115BSP Trees: Objects12345678913245697816BSP Trees: Objects123456789135687 9 2 417Rendering BSP TreesrenderBSP(BSPtree *T)BSPtree *near, far;if (eye on left side of T->plane)near = T->left; far = T->right;else near = T->right; far = T->left;renderBSP(far);if (T is a leaf node)renderObject(T) renderBSP(near);18Rendering BSP Trees123456789135687 9 2 419Rendering BSP Trees123456789135687 9 2 420Polygons: BSP Tree ConstructionSplit along the plane containing any polygonClassify all polygons into positive or negative half-space of the planeIf a polygon intersects plane, split it into two The aforementioned preprocessing stepRecurse down the negative half-spaceRecurse down the positive half-space21Polygons: BSP Tree TraversalQuery: 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 side22Discussion: BSP Tree ConsNo bunnies were harmed in my exampleBut what if a splitting plane passes through an object?Split the object; give half to each node:Worst case: can create up to O(n3) objects!Ouch23BSP TreesA BSP Tree increases storage requirements by splitting polygonsWhat is the worst-case storage cost of a BSP tree on n polygons? But rendering a BSP tree is fairly efficientWhat is the expected cost of a single query, for a given viewpoint, on a BSP tree with m nodes?24BSP DemoNice demo:http://symbolcraft.com/graphics/bsp/index.html Also has a link to the BSP Tree FAQ25Summary: BSP TreesPros:Simple, elegant schemeOnly 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)26Summary: BSP TreesCons:Computationally intense preprocess stage restricts algorithm to static scenesWorst-case time to construct tree: O(n3)Splitting increases polygon count Again, O(n3) worst case27OverviewAnalytic Visibility
View Full Document