Rasterization: Bresenham’s Midpoint cs4600/lectures/Wk2_ 2015 CS4600 1 Rasterization: Bresenham’s Midpoint Algorithm CS4600 Computer Graphics adapted from Rich Riesenfeld’s slides Fall 2015

  • Published on
    18-Apr-2018

  • View
    215

  • Download
    3

Transcript

Fall 2015CS4600 1Rasterization: Bresenhams Midpoint AlgorithmCS4600 Computer Graphicsadapted from Rich Riesenfelds slidesFall 2015RasterizationGeneral method: Use equation for geometry Insert equation for primitive Derive rasterization methodFall 2015CS4600 2Line Characterizations Explicit: Implicit: Constant slope: Constant derivative: Bmxy 0),( cbyaxyxFkxykxf )(Line Characterizations - 2 Parametric: where, Intersection of 2 planes Shortest path between 2 points Convex hull of 2 discrete pointsPtPttP 10)()( 1 PPPP 10 )(;)0( 1 Fall 2015CS4600 3Two Line Equations Explicit: Implicit:Define: Hence, Bmxy 0),( cbyaxyxF0101xxdxyydyBxdxdyy From previousWe have,Hence, Bxdxdyy 0 ByxdxdyFall 2015CS4600 4Relating Explicit to Implicit EqsRecall, Multiply through by dx,where, 0 Byxdxdy0)()()( Bdxydxxdy0)()()(),( BdxydxxdyyxF)();();( dxBcdxbdya Discrete Lines Lines vs. Line Segments What is a discrete line segment? This is a computer graphics problem How to generate a discrete line?Fall 2015CS4600 5Good Discrete Line No gaps in adjacent pixels Pixels close to ideal line Consistent choices; same pixels in same situations Smooth looking Even brightness in all orientations Same line for as for Double pixels stacked up?PP 10 PP 01How to Draw a Line?Plug into the equation directly1. Compute slope2. Start at on point (xo, yo)3. Increment X and draw How to figure this out?Fall 2015CS4600 6Derive from Line EquationY = mX + bYi = mXi + bXi+1 = Xi + Yi+1 = mXi+1 + bYi+1 = (y / x)(Xi+1) + bFall 2015CS4600 7What about slope?Fall 2015CS4600 8Derive from Line EquationY = mX + bYi = mXi + bYi+1 = mXi+1 + bmXi+1 = Yi+1 - b Xi+1 = (Yi+1 - b) / mXi+1 = (Yi+1 - b) / (y/x)Xi+1 = (Yi+1 - b) * (x/y)Fall 2015CS4600 9What about slope?If |y1 y0| > |x1 x0|increment Yelseincrement X Line segment in first octant with0 < m < 1 After we derive this, well look at the other cases (other octants)Restricted FormFall 2015CS4600 10Incremental Function Eval Recall Characteristics Fast Cumulative Error Need to define )()()1( ixixfixf )( oxfInvestigate Sign of FVerify thatLook at extreme values of y 0 ),( yxFabove linebelow lineon lineFall 2015CS4600 11The Picturexy0 ),( yxFabove linebelow line0 ),( yxFKey to Bresenham AlgorithmReasonable assumptions have reduced the problem to making a binary choice at each pixel:(Previous)NE (next)E (next)Fall 2015CS4600 12Decision Variable d (logical)Define a logical decision variable d linear in form incrementally updated (with addition) tells us whether to go E or NEThe PicturemidpointENEpreviousQ1 pxxpxx pyy 1 pyyMFall 2015CS4600 13The Picture (again)ENEpreviousQ),( pp yx),(211 pp yx)1,1( pp yx),( 1 pp yx midpointMObserve the relationships Suppose Q is above M, as before. Then , M is below the line So, means line is above M, Need to move NE, increase y value0)( MF0)( MFFall 2015CS4600 14The Picture (again)midpointENEpreviousQ),( pp yx),(211 pp yx)1,1( pp yx),( 1 pp yx Observe the relationships Suppose Q is below M, as before. Then F(M) < 0 , implies M is above the line So, F(M) < 0 , means line is below M, Need to move to E; dont increase yFall 2015CS4600 15M = Midpoint = : ),(211 pp yx Want to evaluate at M Will use an incremental decision variable d Let,),(211 pp yxFdcybxad pp )(( 21)1How will d be used?Let,Therefore,cybxad pp )(( 21)1)(arbitrary 0line) ideal above(midpoint 0line) ideal below(midpoint 0EENEdFall 2015CS4600 16Case E: Suppose E is chosen Recall ...cybxad ppold )(( 21)1cybxayxFdppppnew)(((2121)2),21: ; , yE x x y ...addcybxacybxaddoldnewppppoldnew)(1()(2(2121))Case E: Suppose E is chosenFall 2015CS4600 17...addcybxacybxaddoldnewppppoldnew)(1()(2(2121))Case E: Suppose E is chosen...addcybxacybxaddoldnewppppoldnew)(1()(2(2121))Case E: Suppose E is chosenFall 2015CS4600 18...addcybxacybxaddoldnewppppoldnew)(1()(2(2121))Case E: Suppose E is chosenReview of Explicit to ImplicitRecall, Or,where, 0 Byxdxdy0)()()( Bdxydxxdy0)()()(),( BdxydxxdyyxF)();();( dxBcdxbdya Fall 2015CS4600 19Case E: .new oldd d a increment we add if is chosen. So, . But remember that (from line equations).Hence, ( ) is not evaluated explicitly.We simply add to update for EEEEaa dyF Ma d ECase NE: Suppose NE chosenRecall...121)( ( )old p pd a x b y c 32322, )2)(( ( )new p pp pd F x ya x b y c1 1and, : ; , yNE x x y Fall 2015CS4600 20Case NE: Suppose NE...baddcybxacybxaddoldnewppppoldnew)(1()(2(2123))Case NE: .badd oldnew increment that we add if is chosen. So, . But remember that , and (from line equations).Hence, ( ) is not evaluated explicitly.We simply add to update for NENENENEa ba dy b dxF Ma b d NEFall 2015CS4600 21.for update to i.e., , addsimply wemeans, and , where,NEddxdybadxbdyabaNENENECase NE: . badd oldnew Summary At each step of the procedure, we must choose between moving E or NE based on the sign of the decision variable d Then update according to dxdyddyddNENEEE where, or , where, Fall 2015CS4600 22What is initial value of d ? First point is First midpoint is What is initial midpoint value?),( 00 yx),(211 00 yx),(),(211211 0000 yxFyxd0 0 0 00 00 01 11 1)2 22(2( , ) ( ( ), )bbFF x y a x b y cax by c ax y aWhat is initial value of d ?Fall 2015CS4600 23What is initial value of d ?0 0 0 0Note, ( (, ) 0, since , ) is on line.F x y x y22211)(0),( 00dxbdyayxFHence,What Does Factor of 2 x Do ? Has the same 0-set Changes the slope of the plane Rotates plane about the 0-set line Gets rid of the denominator0)(2),(2 cbyaxyxFFall 2015CS4600 240 0112Note, we can clear denominator and not change line, 2 ( , ) 2( )F x y dy dx What is initial value of d ?2 ( , ) 2( ) 0So, first value of 2( ) ( )F x y ax by cd dy dxWhat is initial value of d ?Fall 2015CS4600 25More Summary Initial value Case E: Case NE: Note, all deltas are constants)()(2 dxdy )(2 where, dydd EE )}(){(2 where ,dxdyddNENEMore SummaryChooseotherwise 0 if NEdEFall 2015CS4600 26Example Line end points: Deltas: dx = 4; dy = 3)11,9(),;)8,5(), 1100 (( yxyxGraph1312 11 10 9 8 7 64 5 6 7 8 9 10 11Fall 2015CS4600 27Example (dx = 4; dy = 3) Initial value of (5 8) 2( ) ( )6 4 2 02d , dy dxd NEotherwise 0 if NEdE)()(2 dxdy d =Graph1312 11 10 9 8 7 64 5 6 7 8 9 10 11Fall 2015CS4600 28Example (dx=4; dy=3 ) Update value of d Last move was NE, so2( )2(3 4) 22 2 0N E dy - dxd Eotherwise 0 if NEdE)(2 where, dydd EE )}(){(2 where ,dxdyddNENEGraph1312 11 10 9 8 7 64 5 6 7 8 9 10 11Fall 2015CS4600 29Example (dx=4; dy=3 ) Previous move was E2( )2(3) 60 6 0E dyd NEotherwise 0 if NEdE)(2 where, dydd EE )}(){(2 where ,dxdyddNENE2Graph1312 11 10 9 8 7 64 5 6 7 8 9 10 11Fall 2015CS4600 30Example (dx=4; dy=3 ) Previous move was NE2( )2(3 4) 26 2 4N E dy - dxd N Eotherwise 0 if NEdE)(2 where, dydd EE )}(){(2 where ,dxdyddNENE8 6Graph1312 11 10 9 8 7 64 5 6 7 8 9 10 11Fall 2015CS4600 31Graph1312 11 10 9 8 7 64 5 6 7 8 9 10 11Meeting Bresenham Criteria0 1 flip about -axism x 1 flip about m x y 0; 1 trivial casesm m Case 0:Case 1:Case 2:Fall 2015CS4600 32Case 0: Trivial Situations Do not need Bresenhamline horizontal0 mxym line1Case 2: Flip about x-axis), 00( yxxy), 11( yx), 11( yx ), 00( yx Fall 2015CS4600 33Case 2: Flip about x-axisFlip about -axis ( ) :x y y 0 0 0 01 11 1, ) ( ,, ) , )( );( (x y x yx y x y 1Suppose, 0 ,m How do slopes relate?01 001 011; by definitiony yy ymx xmx x)01 0(1i iSince , y ymyyx x Fall 2015CS4600 34How do slopes relate?)01 01( y ymx xm m1010 mmi.e.,Case 3: Flip about line y=x), 11( yx ), 00( yx yxxy ), 11( yx), 00( yxFall 2015CS4600 35Case 3: Flip about line y=x, swap and prime them ,,y mx Bx yx my Bmy x BCase 3: m=? 1 ,1 and,1 0 1y x Bmmmm mFall 2015CS4600 36More Raster Line Issues Fat lines with multiple pixel width Symmetric lines How should end pt geometry look? Generating curves, e.g., circles, etc. Jaggies, staircase effect, aliasing...Pixel Space12111098764 5 6 7 8 9 10Fall 2015CS4600 37ExampleExampleFall 2015CS4600 38Bresenham CirclesThe End Bresenhams Algorithm

Recommended

View more >