DOC PREVIEW
UVA CS 445 - RasterizatioN- Polygons Visibility

This preview shows page 1-2-3-4-25-26-27-52-53-54-55 out of 55 pages.

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

Unformatted text preview:

Rasterization Polygons Visibility CS 445 Introduction to Computer Graphics David Luebke University of Virginia Admin Call roll New room starting next week MEC 216 Clipping assignment Show Spring 2003 assignment Needs to be adapted for this semester If this happens tonight due in two weeks March 1 Otherwise due March 3 Demo Videos General Polygon Rasterization Now that we can rasterize triangles what about general polygons We ll not take an edge equations approach why General Polygon Rasterization Consider the following polygon D B C A E F How do we know whether a given pixel on the scanline is inside or outside the polygon General Polygon Rasterization Does it still work D B H C A G I E F General Polygon Rasterization Basic idea use a parity test for each scanline edgeCnt 0 for each pixel on scanline l to r if oldpixel newpixel crosses edge edgeCnt draw the pixel if edgeCnt odd if edgeCnt 2 setPixel pixel Why does this work What assumptions are we making Faster Polygon Rasterization How can we optimize the code for each scanline edgeCnt 0 for each pixel on scanline l to r if oldpixel newpixel crosses edge edgeCnt draw the pixel if edgeCnt odd if edgeCnt 2 setPixel pixel Big cost testing pixels against each edge Solution active edge table AET Active Edge Table Idea Edges intersecting a given scanline are likely to intersect the next scanline Within a scanline the order of edge intersections doesn t change much from scanline to scanline Active Edge Table Algorithm Sort all edges by their minimum y coord Starting at bottom add edges with Ymin 0 to AET For each scanline Sort edges in AET by x intersection Walk from left to right setting pixels by parity rule Increment scanline Retire edges with Ymax Y Add edges with Ymin Y Recalculate edge intersections and resort how Stop when Y Ymax for last edges Recap 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 determination Invisible Primitives Why might a polygon be invisible Invisible 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 occluded View 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 polygons to pass through portions intersecting view frustum What is the cost of clipping n polygons Can we do better Back 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 formed CAD part Back 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 Back Face Culling On the surface of a closed manifold polygons whose normals point away from the camera are always occluded Back Face Culling On the surface of a closed manifold polygons whose normals point away from the camera are always occluded Back Face Culling On the surface of a closed manifold polygons whose normals point away from the camera are always occluded Note backface culling alone doesn t solve the hidden surface problem Back Face Culling By not rendering backfacing polygons we improve performance By how much When in the pipeline should we perform backface culling Occlusion For most interesting scenes some polygons will overlap To render the correct image we need to determine which polygons occlude which Painter 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 Painter s Algorithm Problems Intersecting polygons present a problem Even non intersecting polygons can form a cycle with no valid visibility order 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 algorithms Analytic Visibility Algorithms What is the minimum worst case cost of computing the fragments for a scene composed of n polygons Analytic Visibility Algorithms What is the minimum worst case cost of computing the fragments for a scene composed of n polygons Answer O n2 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 Algorithm Binary 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 convex BSP Trees Objects 9 6 7 5 1 8 4 2 3 BSP Trees Objects 9 6 7 5 1 8 5 4 2 3 6 7 8 9 1 2 3 4 BSP Trees Objects 9 6 7 5 1 8 7 4 2 3 8 9 5 6 2 3 4 1 BSP Trees Objects 9 6 7 5 1 8 1 4 2 3 8 7 9 6 5 3 2 4 BSP Trees Objects 9 6 7 5 1 8 1 4 2 3 8 6 7 9 5 3 2 4 Rendering BSP Trees renderBSP 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 Trees 9 6 7 5 1 8 1 4 2 3 8 6 7 9 5 3 2 4 Rendering BSP Trees 9 6 7 5 1 8 1 4 2 3 8 6 7 9 5 3 2 4 Polygons 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 space Polygons BSP Tree Traversal 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


View Full Document

UVA CS 445 - RasterizatioN- Polygons Visibility

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 RasterizatioN- Polygons Visibility
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 RasterizatioN- Polygons Visibility 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 RasterizatioN- Polygons Visibility 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?