CS 445 / 645: Introductory Computer GraphicsRecap: Rendering PipelineInvisible PrimitivesView Frustum ClippingSlide 5Slide 6Review Rendering PipelinePerspective Viewing Transf.Canonical Perspective VolumeClippingSlide 11Back-Face CullingManifoldSlide 14Slide 15Slide 16OcclusionPainter’s AlgorithmPainter’s Algorithm: ProblemsAnalytic Visibility AlgorithmsSlide 21Slide 22Binary Space Partition Trees (1979)BSP Trees: ObjectsSlide 25Slide 26Slide 27Slide 28Rendering BSP TreesSlide 30Slide 31Polygons: BSP Tree ConstructionPolygons: BSP Tree TraversalDiscussion: BSP Tree ConsBSP DemoSummary: BSP TreesWarnock’s Algorithm (1969)Warnock’s AlgorithmSlide 39The Z-Buffer AlgorithmSlide 41Slide 42Slide 43Slide 44Interpolating ZSlide 46Z-Buffer ProsZ-Buffer ConsCS 445 / 645: Introductory Computer GraphicsVisible Surface DeterminationRecap: Rendering PipelineAlmost finished with the rendering pipeline:–Modeling transformations–Viewing transformations–Projection transformations–Clipping–Scan conversionWe now know everything about how to draw a polygon on the screen, except visible surface determinationInvisible PrimitivesWhy might a polygon be invisible?–Polygon outside the field of view–Polygon is backfacing–Polygon is occluded by object(s) nearer the viewpointFor efficiency reasons, we want to avoid spending work on polygons outside field of view or backfacingFor efficiency and correctness reasons, we need to know when polygons are occludedView Frustum ClippingRemove polygons entirely outside frustum–Note that this includes polygons “behind” eye (actually behind near plane)Pass through polygons entirely inside frustumModify remaining polygonsto pass through portions intersecting view frustumView Frustum ClippingCanonical View Volumes–Remember how we defined camerasEye point, lookat point, v-upOrthographic | Perspective–Remember how we define viewportWidth, height (or field of view, aspect ratio)–These two things define rendered volume of space–Standardize the height, length, and width of view volumesView Frustum ClippingCanonical View VolumesReview Rendering PipelineClipping equations are simplifiedPerspective and Orthogonal (Parallel) projections have consistent representationsPerspective Viewing Transf.Remember the viewing transformation for perspective projection–Translate eye point to origin–Rotate such that projection vector matches –z–Rotate such that up vector matches yAdd to this a final step where we scale the volumeCanonical Perspective VolumeScalingClippingCanonical Perspective Volume can be converted into Canonical Orthogonal Volume–And vice versaUse homogeneous coordinates to accomplish the mapping–Don’t memorize this matrix for test01001110000100001minminminzzzClippingBecause both camera types are represented by same viewing volume–Clipping is simplified even furtherBack-Face CullingMost objects in scene are typically “solid”More rigorously: closed, orientable manifolds–Local neighborhood of all points isomorphic to disc–Boundary partitions space into interior & exteriorManifoldExamples of manifold objects: –Sphere–Torus–Well-formedCAD partBack-Face CullingExamples 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:Back-Face CullingOn 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!Back-Face CullingNot rendering backfacing polygons improves performance–By how much?Reduces by about half the number of polygons to be considered for each pixelOcclusionFor most interesting scenes, some polygons will overlap:To render the correct image, we need to determine which polygons occlude whichPainter’s AlgorithmSimple approach: render the polygons from back to front, “painting over” previous polygons:–Draw blue, then green, then orangeWill this work in the general case?Painter’s Algorithm: ProblemsIntersecting polygons present a problemEven non-intersecting polygons can form a cycle with no valid visibility order: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 algorithmsAnalytic Visibility AlgorithmsWhat is the minimum worst-case cost of computing the fragments for a scene composed of n polygons?Answer: O(n2)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 AlgorithmBinary 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 planesSplitting planes can be arbitrarily orientedNotice: nodes are always convexBSP Trees: ObjectsBSP Trees: ObjectsBSP Trees: ObjectsBSP Trees: ObjectsBSP Trees: ObjectsRendering 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);Rendering BSP TreesRendering BSP TreesPolygons: BSP Tree ConstructionSplit 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-spacePolygons: 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-space */farchild->draw(viewpt);render node->polygon; /* always on node->plane */nearchild->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 sideNo
View Full Document
Unlocking...