Lecture Note
University
University of California San DiegoCourse
CSE167 | Computer GraphicsPages
11
Academic year
2023
Jake Tomson
Views
0
Page Date / Bresenham's Line Drawing Algorithm This is an accurate and efficient raster It scan converts line using incremental line generating algorithm integer calculation that can be adapted to display circles and other curve. In this algorithm we have to decide which pixel position is closest to the scan line. By using a decision parameter we can determine the losest one to the scan line yktz y K4T fig YK xk n x K+1 K+2 when dieda, then Pic of negative ykth OR d2>d1 d2 y fig.2 di YK nk n xk+1
Camlin Page Date The Figure 1 shows a positive slope that is less than 1. Here (xk yk is the starting position Next pixel positions are x and Yk+1 In Figure 2, y is the scan line ie y = mn+b di and d2 are the vertical pixel separation from the scan line y.From figure 2 , the equation of the slope will be y mex di =y-yk = di = m / n +1) +b'- Yk d2 = lyk +1) y d2 = yk+1 - [m (nk +1) + b] d2 = YK+ mv(x) +1) Tb di - d2 = m (n K +1) tb - Yk - ykt1-m(x+1)-b) m/xi 1)+b-y y, K - 1+m(xx+1) + b di- - dz = 2m (n K 1) - Qyk +2b-1 Substitute m = Dy Ax
= 2 Dy (n+1) K - 2yk 2b - Dn = An (2Dy (nk +1)] - 20 xyx - +2Dnb - An Dn = 20y (nk 11)- - 2Dnyk + 2Dnb - An = 2Dyx k + 2Dy -2Dxyk +2 Anb. - An = 2Dynk + 2 Dy -2D ny +(2b-1) An Pk 20yx K - 2Dxy 20y + (2b-1) Dn P Kfl = 2Dy n - 2Dny +2 Dy + (2b - 1) 02 k+1 K+1 An(di-d2) is called as the decision parameter PK. Here An will always be greater than o, because it is a positive slopey ie The sign will of Pk will depend on sign of (di-di ie . Pk always depend on sign (di-di Pk is negative when t d2 > di) of or (didds So di
Date When Pk is negative, we can plot the lower pixel, when PK is positive we can plot the upper pixel. we can obtain the values of successive decision parameter using incremented integer calculations. At step K+1 the decision parameter is evaluated as Pk+1. Pk+1= = 20yx k+1 - +2Dy + (2b-1)Dn Pk+1 = 20yn K+1 - -20nykt tc PK+1-P = 20yx K+1 - -2Dxykt1+c- 1 [20 ty n, k - 2Dx (yk+c) = 2Dyn K+1 - -20ny +1+C - 2Dyx, K +2Dnyk . C 12Dryr, K+1 - 12Dyxx -2Dxy +2Dxyk - 20y (n K+1 - xx) -20n Set x = Xk+1 K+ = 20ytn +1-XX) - 2.0n (YRT K+1 - yy) PRH - -Pk = 20y-20n - (YRT) -yk) - PK+1 = Pk + 2Dy -2.An (YRTI -yk)
1 where depending on the sign of Pk the term Ykti - Yk is parameter either o or plot the upper pixel of Ykti when Pk >0 + we ie. YK+1 yk+1 then PR71 PK + 2 Dy - 2D ly+1-yr) K Pkti Pk +2 Dy - when PK we plot the lower pixel Yk 40, then Pk+1 PK + 2Dy - 2An lyk -yk) Pk+1 Pk + 2Dy Initial Decision Parameter Po 2Dy - Ax Bresenham's Line drawing algorithm [Im/cl] I Input the 2 line endpoints and store the left endpoint in (no,yo) 2 plot the first point. Load (no, yo) into the frame buffer / ie, 3 Calculate An and obtain the t starting Dy 2Dy , 20y - 20x value for the
Camlin Page Date / / decision parameter as Po = 20y - on 4 At each n along the line starting perform the following test (a) If PK 20, the next point to plot is (XR+1) yk) and Pkti = Pk + 2Dy b) therwise, the next point is (xkti ) when PR 30 and PR+1 = Pk + 20y - 2 An 5 Repeat step 4 On times or till the reaching of last endpoint. Example eg:- Drawa line using Bresenham's algorithm given the starting and ending point as (20,10) and (30,18) The line has a slope of 0.8 (xo, yo) = (20590) slope = 0.8 M
K.O , po - PK pk = 6 Pk>o P1 = 2 Dy - 2 Dn 64-4 2 (P1,70) K Pk (nkth ykti "I 5 0 6 (21,11) 1 2 (22,12) 2 -2 (23, 12) 3 14 (24,13) 4 10 (25,14) 5 6 (26,15) 6 2 (27, 16) 7 -2 (28,16) 8 14 (29,17) 9 10 (30,18)
P2 Pk + 20y - Risix = 2+-A -2 C P2LO) P3 = Pk + 2Dy -2-4-16 p 14 (P370) - Pq Pk 20y- 25x 14+-4 610 (P470) Ps = PK +2 A y - 202 = 10 +16 20 = 10-4 - = 6 ( Ps 70) = P6 = Pk 4 2 A y - - 2An = 6+-4 2 (P6>0) = P7 = Pk+2Dy - 20x 22-4 = -2 ('P70) Pq = Pk+2Dy- 2 AXAS = 14 + - 4 = 10 ( Pa >0) - 2.
eg:- (9,18) (14, 22) no,yo) (9,18) An = N2-X1 Dy = y2-y1 = 14-9 22-18 =5 4 2Dy = 2x4= 8 2Dn= 2x5 =10 = a Po=20y -An 20x-2Ay = +8-10 = =2 = S-5 3 (Po20) ik Pk (nkm) Pr = Po + 2Dy-20 o 03 (9,18) 3 + 8 - 10 I 1 (10,19) 3 - 3 - 2 21 -1 (11,19) P121 (PI>O) 3 7 (12,20) 4 5 (13,21) P2 = Pit2Dy-2Dn 5 3 (14,22) =1+8-10 NAS - NAS + = 1t-2 P2 =-1 (P20) 1-5-+-2 = $ + 3 - P4 = 27+8-10 P5 70) =7-2 Cac or =.5 (P4>0)
Date Advantages of Bresenham 1 It is easy to implement 2 It is fast and incremental 3' It executes fast but less faster than DDA algorithm 4 The points generated by this algorithm are more accurate than DDA algorithm 5. It uses fixed points only. Disadvantages of Bresenham 1' The result line is not smooth 2. This algorithm is for the basic line drawing 3 It cannot handle diminishing jaggies. Circle Drawing Algorithm circle is defined as the set of points that are all at a given distance 'r' from a centre position ( N.C, yc) The general equation of a circle is:- n2 ty = r Yc r Xc X
from figure, the distance relationship is expressed as (x - x1)2 (+(y-yc) = 92 To calculate the position of points on a circle circumference by stepping along the x -axis - in unit steps from mc r to xctr and the corresponding Y values at each position as y = y t J 92 - (nc-x) Problem with this approach is that it involves considerable computation at each step. Also the spacing between plotted pixel position is not uniform To eliminate the unequal spacing, calculate polar coordinates r and O. points along the circular boundary using Expressing the circle equation in polar form x = xc + rcaso y= yc + r sin O by using equally spaced points along the By using with these equations, a circle is plotted depends circumference The step size chosen for o device on the application and display
Bresenham's Line Drawing Algorithm
Please or to post comments