Unformatted text preview:

Drawing LinesPlotting a line-segmentScan conversionThe various cases0 < slope < 1Integer endpointsWhich point is closer?The Decision VariableComputing di+1 from diHow does algorithm start?‘bresdemo.cpp’Filling a triangle or polygonTriangle IllustrationNon-Convex PolygonsBucket-SortHandling CornersIn-class exercisesDrawing LinesThe Bresenham Algorithm for drawing lines and filling polygonsPlotting a line-segment•Bresenham published algorithm in 1965•It was originally to be used with a plotter•It adapts well to raster “scan conversion”•It uses only integer arithmetic operations•It is an “iterative” algorithm: each step is based on results from the previous step•The sign of an “error term” governs the choice among two alternative actionsScan conversionThe actual line is comprised of points drawn from a continuum,but it must be “approximated” using pixels from a discrete grid.The various cases•Horizontal or vertical lines are easy cases•Lines that have slope 1 or -1 are easy, too •Symmetries leave us one remaining case:0 < slope < 1•As x-coodinate is incremented, there are just two possibilities for the y-coordinate:(1) y-coordinate is increased by one; or (2) y-coordinate remains unchanged0 < slope < 1y increases by 1 y does not changeX-axisY-axisInteger endpointsΔXΔYslope = ΔY/ΔX(X0,Y0)(X1,Y1)ΔY = Y1 – Y0ΔX = X1 – X00 < ΔY < ΔXWhich point is closer?ABxi -1xiy = mx + berror(A) = (yi -1 + 1) – y* error(B) = y* - (yi -1) ideal lineyi -1yi -1+1The Decision Variable•Choose B if and only if error(B)<error(A)•Or equivalently: error(B) – error(A) < 0•Formula: error(B) – error(A) =2m(xi – x0) + 2(y0 – yi -1) -1•Remember: m = Δy/Δx (slope of line)•Multiply through by Δx (to avoid fractions)•Let di = Δx( error(B) – error(A) )•Rule is: choose B if and only if di < 0Computing di+1 from didi+1 = 2(Δy)(xi+1 – x0) +2(Δx)(y0 – yi) – Δxdi = 2(Δy)(xi – x0) + 2(Δx)(y0 – yi-1) – ΔxThe difference can be expressed as:di+1 = di + 2(Δy)(xi+1 – xi) – 2(Δy)(yi – yi-1)Recognize that xi+1 – xi = 1 at every stepAnd also: yi – yi-1 will be either 0 or 1(depending on the sign of the previous d)How does algorithm start?•At the outset we start from point (x0,y0)•Thus, at step i =1, our formula for di is: d1 = 2(Δy) - Δx•And, at each step thereafter:if ( d i < 0 ) { di+1 = di + 2(Δy); yi+1 = yi; }else { di+1 = di + 2(Δy-Δx); yi+1 = yi + 1; }xi+1 = xi + 1;‘bresdemo.cpp’•The example-program is on class website: http://nexus.cs.usfca.edu/~cruse/cs686/•It draws line-segments with various slopes•The Michener algorithm (for a circle-fill) is also included, for comparative purposes•Extreme slopes (close to zero or infinity) are not displayed in this demo program•They can be added by you as an exerciseFilling a triangle or polygon•The Bresenham’s method can be adapted•But an efficient data-structure is needed•All the sides need to be handled together•We let the y-coordinate steadily increment•For sides which are “nearly horizontal” the x-coordinates can change by more than 1Triangle IllustrationNon-Convex PolygonsBucket-Sort0123456781011128 87 96 10111213141516579111315YXLO XHI1317 17Handling CornersIn-class exercises•For the ‘bresdemo.cpp’ program:–Supply a function that tests the capability of the Breshenham line-drawing algorithm to draw lines having the full range of slopes•For the ‘fillpoly.cpp’ program:–Modify the program code so that it will work with polygons having more than three


View Full Document

USF CS 686 - Drawing Lines

Documents in this Course
Load more
Download Drawing Lines
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 Drawing Lines 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 Drawing Lines 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?