VisibilityRecap: Rendering PipelineInvisible PrimitivesSlide 4View Frustum ClippingBack-Face CullingSlide 7Slide 8Slide 9Slide 10Slide 11OcclusionPainter’s AlgorithmPainter’s Algorithm: ProblemsAnalytic Visibility AlgorithmsSlide 16Slide 17Slide 18Binary Space Partition Trees (1979)BSP Trees: ObjectsSlide 21Slide 22Slide 23Slide 24Rendering BSP TreesSlide 26Slide 27Polygons: BSP Tree ConstructionPolygons: BSP Tree TraversalDiscussion: BSP Tree ConsBSP TreesBSP DemoSummary: BSP TreesSlide 34Warnock’s Algorithm (1969)Warnock’s AlgorithmSlide 37The Z-Buffer AlgorithmSlide 39Slide 40Slide 41Slide 42Interpolating ZSlide 44Z-Buffer ProsZ-Buffer ConsDavid Luebke 1 01/14/19VisibilityCS 445/645Introduction to Computer GraphicsDavid Luebke, Spring 2003David Luebke 2 01/14/19Recap: Rendering Pipeline●Almost finished with the rendering pipeline:■Modeling transformations■Viewing transformations■Projection transformations■Clipping■Scan conversion●We now know everything about how to draw a polygon on the screen, except visible surface determinationDavid Luebke 3 01/14/19Invisible Primitives●Why might a polygon be invisible?David Luebke 4 01/14/19Invisible Primitives●Why might a polygon be invisible?■Polygon outside the field of view■Polygon is backfacing■Polygon is occluded by object(s) nearer the viewpoint■Other reasons:○Too small to be seen○Obscured by fog or haze●For efficiency reasons, we want to avoid spending work on polygons outside field of view or backfacing●For efficiency and correctness reasons, we need to know when polygons are occludedDavid Luebke 5 01/14/19View Frustum Clipping●Remove polygons entirely outside frustum■Note that this includes polygons “behind” eye (actually behind near plane)●Pass through polygons entirely inside frustum●Modify remaining polygonsto pass through portions intersecting view frustum■What is the cost of clipping n polygons? ■Can we do better?David Luebke 6 01/14/19Back-Face Culling●Most objects in scene are typically “solid”●More rigorously: closed, orientable manifolds■Local neighborhood of all points isomorphic to disc■Boundary partitions space into interior & exterior●Examples of manifold objects: ■Sphere■Torus■Well-formedCAD partDavid Luebke 7 01/14/19Back-Face Culling●Examples of non-manifold objects:■A single polygon■A terrain or height field■polyhedron w/ missing face■Anything with cracks or holes in boundary■one-polygon thick lampshade:David Luebke 8 01/14/19Back-Face Culling●On the surface of a closed manifold, polygons whose normals point away from the camera are always occluded:David Luebke 9 01/14/19Back-Face Culling●On the surface of a closed manifold, polygons whose normals point away from the camera are always occluded:David Luebke 10 01/14/19Back-Face Culling●On the surface of a closed manifold, polygons whose normals point away from the camera are always occluded:Note: backface cullingalone doesn’t solve thehidden-surface problem!David Luebke 11 01/14/19Back-Face Culling●By not rendering backfacing polygons, we improve performance■By how much?■When in the pipeline should we perform backface culling?David Luebke 12 01/14/19Occlusion●For most interesting scenes, some polygons will overlap:●To render the correct image, we need to determine which polygons occlude whichDavid Luebke 13 01/14/19Painter’s Algorithm●Simple approach: render the polygons from back to front, “painting over” previous polygons:■Draw blue, then green, then pink●Will this work in general?David Luebke 14 01/14/19Painter’s Algorithm: Problems●Intersecting polygons present a problem●Even non-intersecting polygons can form a cycle with no valid visibility order:David Luebke 15 01/14/19Analytic 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 algorithmsDavid Luebke 16 01/14/19Analytic Visibility Algorithms●What is the minimum worst-case cost of computing the fragments for a scene composed of n polygons?David Luebke 17 01/14/19Analytic Visibility Algorithms●What is the minimum worst-case cost of computing the fragments for a scene composed of n polygons?●Answer: O(n2)David Luebke 18 01/14/19Analytic 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 AlgorithmDavid Luebke 19 01/14/19Binary Space Partition Trees (1979)●BSP 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 convexDavid Luebke 20 01/14/19BSP Trees: Objects123456789David Luebke 21 01/14/19BSP Trees: Objects12345678956 78 9 1 2 34David Luebke 22 01/14/19BSP Trees: Objects1234567895 67 8 9234 1David Luebke 23 01/14/19BSP Trees: Objects123456789132456978David Luebke 24 01/14/19BSP Trees: Objects123456789135687 9 2 4David Luebke 25 01/14/19Rendering 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);David Luebke 26 01/14/19Rendering BSP Trees123456789135687 9 2 4David Luebke 27 01/14/19Rendering BSP Trees123456789135687 9 2 4David Luebke 28 01/14/19Polygons: BSP Tree Construction●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-spaceDavid Luebke 29 01/14/19Polygons: BSP Tree Traversal●Query: given a viewpoint, produce an ordered list of (possibly split) polygons from back to
View Full Document
Unlocking...