Last Time Clipping Liang Barksy Weiler Atherton Drawing points Intro to drawing lines Midterm Oct 28 10 21 04 University of Wisconsin CS559 Fall 2004 Today Drawing lines Filling polygons 10 21 04 University of Wisconsin CS559 Fall 2004 Bresenham 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 2004 Midpoint 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 yi 1 yi 1 yi yi xi xi 1 Choose xi 1 yi 10 21 04 xi xi 1 Choose xi 1 yi 1 University of Wisconsin CS559 Fall 2004 Midpoint Decision Variable Write the line in implicit form F x y ax by c y x x y x y1 y x1 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 10 21 04 University of Wisconsin CS559 Fall 2004 What Can We Decide d i 2 y xi 1 2 xyi x 2c 1 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 10 21 04 University of Wisconsin CS559 Fall 2004 Updating The Decision Variable dk 1 is the old value dk plus an increment d k 1 d k d k 1 d k If we chose yi 1 yi 1 If we chose yi 1 yi d k 1 d k 2 y 2 x d k 1 d k 2 y What is d1 assuming integer endpoints d1 2 y x Notice that we don t need c any more 10 21 04 University of Wisconsin CS559 Fall 2004 Bresenham 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 2 y 2 x If d 0 then y y draw x y d d 2 y Compute the constants 2 y 2 x and 2 y 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 required 10 21 04 University of Wisconsin CS559 Fall 2004 Example 2 2 to 7 6 x 5 y 4 x y 7 6 5 4 3 2 1 1 2 10 21 04 3 4 5 6 7 8 University of Wisconsin CS559 Fall 2004 d Filling 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 now 10 21 04 University of Wisconsin CS559 Fall 2004 What 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 inside 10 21 04 University of Wisconsin CS559 Fall 2004 Inside Outside Rules Polygon Non exterior Non zero Winding No 10 21 04 Parity University of Wisconsin CS559 Fall 2004 What is inside 2 Assume sampling with an array of spikes If spike is inside pixel is inside 10 21 04 University of Wisconsin CS559 Fall 2004 Ambiguous 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 offscreen point What if a pixel is on a vertex Do our rules still work 10 21 04 University of Wisconsin CS559 Fall 2004 Ambiguous 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 2004 Ambiguous Case 2 10 21 04 University of Wisconsin CS559 Fall 2004 Ambiguous Case 2 10 21 04 or University of Wisconsin CS559 Fall 2004 Really 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 1 6 2 5 4 10 21 04 University of Wisconsin CS559 Fall 2004 3 Exploiting 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 endpoints 10 21 04 University of Wisconsin CS559 Fall 2004 Sweep 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 vertex 10 21 04 University of Wisconsin CS559 Fall 2004
View Full Document
Unlocking...