Last TimeTodayBresenham’s Algorithm OverviewMidpoint MethodsMidpoint Decision VariableWhat Can We Decide?Updating The Decision VariableBresenham’s AlgorithmExample: (2,2) to (7,6)Filling polygonsWhat is inside - 1?Inside/Outside RulesWhat is inside - 2?Ambiguous CaseAmbiguous Case 1Ambiguous Case 2Slide 17Really AmbiguousExploiting CoherenceSweep Fill Algorithms10/21/04 © University of Wisconsin, CS559 Fall 2004Last Time•Clipping–Liang-Barksy–Weiler-Atherton•Drawing points•Intro to drawing lines•Midterm Oct 2810/21/04 © University of Wisconsin, CS559 Fall 2004Today•Drawing lines•Filling polygons10/21/04 © University of Wisconsin, CS559 Fall 2004Bresenham’s Algorithm Overview•Input: Line with integer endpoints, slope 0<m<1•Aim: For each x, plot the pixel whose y-value is closest to the line•Given (xi,yi), must choose from either (xi+1,yi+1) or (xi+1,yi)•Idea: compute a decision variable–Value that will determine which pixel to draw–Easy to update from one pixel to the next•Bresenham’s algorithm is the midpoint algorithm for lines–Other midpoint algorithms for conic sections (circles, ellipses)10/21/04 © University of Wisconsin, CS559 Fall 2004yiyi+1xi+1Midpoint Methods•Consider the midpoint between (xi+1,yi+1) and (xi+1,yi)•If it’s above the line, we choose (xi+1,yi), otherwise we choose (xi+1,yi+1)xiChoose (xi+1,yi) yiyi+1xi+1xiChoose (xi+1,yi+1)10/21/04 © University of Wisconsin, CS559 Fall 2004Midpoint Decision Variable•Write the line in implicit form:•The value of F(x,y) tells us where points are with respect to the line–F(x,y)=0: the point is on the line–F(x,y)<0: The point is above the line–F(x,y)>0: The point is below the line•The decision variable is the value of di = 2F(xi+1,yi+0.5)–The factor of two makes the math easier 11, xyyxyxxycbyaxyxF 10/21/04 © University of Wisconsin, CS559 Fall 2004What Can We Decide?•di negative => next point at (xi+1,yi)•di positive => next point at (xi+1,yi+1)•At each point, we compute di and decide which pixel to draw•How do we update it? What is di+1?)12(2)1(2 cxxyxydiii10/21/04 © University of Wisconsin, CS559 Fall 2004Updating The Decision Variable•dk+1 is the old value, dk, plus an increment:•If we chose yi+1=yi+1: •If we chose yi+1=yi:•What is d1 (assuming integer endpoints)?•Notice that we don’t need c any more)(11 kkkkdddd xyddkk221yddkk21xyd 2110/21/04 © University of Wisconsin, CS559 Fall 2004Bresenham’s Algorithm•For integers, slope between 0 and 1:–x=x1, y=y1, d=2dy - dx, draw (x, y)–until x=x2•x=x+1•If d>0 then { y=y+1, draw (x, y), d=d+2y - 2x }•If d<0 then { y=y, draw (x, y), d=d+2y }•Compute the constants (2y-2x and 2y ) once at the start–Inner loop does only adds and comparisons•For floating point, initialization is harder, x and y will be floating point, but still no rounding required10/21/04 © University of Wisconsin, CS559 Fall 2004Example: (2,2) to (7,6)x=5, y=4x y d12 3 4 5 6 7 8123456710/21/04 © University of Wisconsin, CS559 Fall 2004Filling polygons•Sampling polygons:–When is a pixel inside a polygon? –Given a pixel, which polygon does it lie in? Point location•Polygon representation:–Polygon defined by a list of edges - each is a pair of vertices–All vertices are inside the view volume and map to valid pixels (clipping gave us this).–Assume integers in window coordinates to simplify things for now10/21/04 © University of Wisconsin, CS559 Fall 2004What is inside - 1?•Easy for simple polygons - no self intersections or holes–OpenGL requires these. Undefined for other cases–OpenGL also requires convex polygons – easy triangulation•For general polygons, three rules are possible:–Non-exterior rule: A point is inside if every ray to infinity intersects the polygon–Non-zero winding number rule: Draw a ray to infinity that does not hit a vertex, if the number of edges crossing in one direction is not equal to the number crossing the other way, the point is inside–Parity rule: Draw a ray to infinity and count the number or edges that cross it. If even, the point is outside, if odd, it’s inside10/21/04 © University of Wisconsin, CS559 Fall 2004PolygonParityNon-zero Winding No.Non-exteriorInside/Outside Rules10/21/04 © University of Wisconsin, CS559 Fall 2004What is inside - 2?•Assume sampling with an array of spikes•If spike is inside, pixel is inside10/21/04 © University of Wisconsin, CS559 Fall 2004Ambiguous Case•Ambiguous cases: What if a pixel lies on an edge?–Problem because if two polygons share a common edge, we don’t want pixels on the edge to belong to both–Ambiguity would lead to different results if the drawing order were different–Aim: A consistent rule that (almost) always results in one polygon “owning” the edge•One Rule: if (x+, y+) is in, (x,y) is in (for arbitrarily small )•Another: edge belongs to polygon on same side as some off-screen point•What if a pixel is on a vertex? Do our rules still work?10/21/04 © University of Wisconsin, CS559 Fall 2004Ambiguous Case 1•Rule 1:–On edge? If (x+, y+) is in, pixel is in–Which pixels are colored?•Rule 2:–If polygon is on same side as point (huge,huge)–Which pixels?–Corners?10/21/04 © University of Wisconsin, CS559 Fall 2004Ambiguous Case 210/21/04 © University of Wisconsin, CS559 Fall 2004Ambiguous Case 2????or10/21/04 © University of Wisconsin, CS559 Fall 2004Really Ambiguous•We will accept ambiguity in such cases–The center pixel may end up colored by one of two polygons in this case–Which two?12345610/21/04 © University of Wisconsin, CS559 Fall 2004Exploiting Coherence•When filling a polygon–Several contiguous pixels along a row tend to be in the polygon - a span of pixels•Scanline coherence–Consider whole spans, not individual pixels–The pixels required don’t vary much from one span to the next•Edge coherence–Incrementally update the span endpoints10/21/04 © University of Wisconsin, CS559 Fall 2004Sweep Fill Algorithms•Algorithmic issues:–Reduce to filling many spans–Which edges define the span of pixels to fill?–How do you update these edges when moving from span to span?–What happens when you cross a
View Full Document
Unlocking...