Computer Graphic - Lines, Circles and Ellipse

Computer Graphic - Lines, Circles and Ellipse

1. Computer Graphics CH02 – lines, Circles and ellipse

2. Bresenham’s line drawing algorithm For |m|<1 Input 2 line end points and store the left end point in (x ,y ). Load (x ,y ) into the frame buffer to plot the first end point. Calculate constants ∆ x, ∆y, and 2∆y - 2 ∆x and 2∆y and obtain the storing value for the decision parameter as : P = 2∆y - ∆ x. At each x k along the line, starting at k = 0, do the following test: if p k < 0, the next point to plot is (x k+1 , y k ) and p k+1 = p k + 2∆y else, the next point to plot is ( x k+1 , y k+1 ) and p k+1 = p k + 2∆y - 2∆ x Repeat step 4 ∆ x times.

3. Example 1 part 1 Suppose we have the line with the 2 following end points (20,10) and (30,18) use line drawing algorithm to draw this line. m= ∆y / ∆x = 8/10 < 1. Initial point : (20,10) ∆ x = 10 ∆y = 8 2 ∆y - 2∆ x = -4 2 ∆y = 16 Initial decision parameter P = 2∆y - ∆ x =16 – 10 = 6 (30,18) (20,10)

4. Example 1 part 2 k p k (x k+1 ,y k+1 ) 6 (21,11) 1 6-4 = 2 (22,12) 2 18-20 = -2 (23,12) 3 -2+16 = 14 (24,13) 4 14-4 = 10 (25,14) 5 6 (26,15) 6 2 (27,16) 7 -2 (28,16) 8 14 (29,17) 9 10 (30,18)

5. Bresenham’s line drawing algorithm For |m|>=1 Interchange the values of x and y (y is always increasing in the table and the decision parameter become : P = 2 ∆x - ∆y and p k+1 = p k + 2 ∆x - 2 ∆ y or p k + 2∆x .

6. Example 2 part 1 Suppose we have the line with the 2 following end points (1,3) and (7,12) use line drawing algorithm to draw this line. m= ∆y / ∆x = 9/6 > 1. Initial point : (1,3) ∆ x = 6 ∆y = 9 2∆x - 2 ∆y = -6 2∆x = 12 Initial decision parameter P = 2 ∆x - ∆y = 3 (7,2) (1,3)

7. Example 2 part 2 k p k (x k+1 ,y k+1 ) 3 (2,4) 1 (3+12-18) = -3 (2,5) 2 9 (3,6) 3 3 (4,7) 4 -3 (4,8) 5 9 (5,9) 6 3 (6,10) 7 -3 (6,11) 8 9 (7,12)

8. Example 3 part 1 Suppose we have the line with the 2 following end points (5,7) and (9,19) use line drawing algorithm to draw this line. m= ∆y / ∆x = 12/4 > 1. Initial point : (5,7) ∆ x = 4 ∆y = 12 2∆x - 2 ∆y = -16 2∆x = 8 Initial decision parameter P = 2 ∆x - ∆y = -4 (9,19) (5,7)

9. Example 3 part 2 k p k (x k+1 ,y k+1 ) -4 (5,8) 1 4 (6,9) 2 -12 (6,10) 3 -4 (6,11) 4 4 (7,12) 5 -12 (7,13) 6 -4 (7,14) 7 4 (8,15) 8 -12 (8,16) 9 -4 (8,17) 10 4 (9,18) 11 -12 (9,19)

10. Example 4 part 1 Suppose we have the line with the 2 following end points (2,6) and (8,7) use line drawing algorithm to draw this line. m= ∆y / ∆x = 1/6 < 1 . Initial point : (2,6) ∆ x = 6 ∆y = 1 2 ∆y - 2∆ x = -10 2 ∆y = 2 Initial decision parameter P = 2 ∆y - ∆x = -4 (8,7) (2,6)

11. Example 4 part 2 k p k (x k+1 ,y k+1 ) -4 (3,6) 1 -2 (4,6) 2 (5,7) 3 -10 (6,7) 4 -8 (7,7) 5 -6 (8,7)

12. Midpoint circle algorithm Input radius r and circle center (x i ,y i ) and obtain the first point on the circumference of the circle centered on the origin as (0,r). Calculate the initial value of decision parameter as p = 5/4 – r (if its integer 1-r). At each x k position starting at k=0 , perform the following test : If p k < 0 then the next point on circle centered on (0,0) is (x k+1 ,y k ) and p k+1 = p k +2x k+1 +1 else the next point along the circle centered on (0,0) is ( x k+1 ,y k-1 ) and p k+1 = p k +2x k+1 +1-2y k+1 Repeat step 3 until x>=y.

13. Example 1 Given r=10 use midpoint circle algorithm to draw circle. Initial point : (0,10) Initial decision parameter P = 1-r = -9 k p k (x k+1 ,y k+1 ) 2x k+1 2y k+1 -9 (1,10) 2 20 1 -6 (2,10) 4 20 2 -1 (3,10) 6 20 3 6 (4,9) 8 18 4 -3 (5,9) 10 18 5 8 (6,8) 12 16 6 5 (7,7) Stop 14 14

14. Example 2 Given r=14 use midpoint circle algorithm to draw circle. Initial point : (0,14) P = 1-r = -13 k p k (x k+1 ,y k+1 ) 2x k+1 2y k+1 -13 (1,14) 2 28 1 -10 (2,14) 4 28 2 -5 (3,14) 6 28 3 2 (4,13) 8 26 4 -15 (5,13) 10 26 5 -4 (6,13) 12 26 6 9 (7,12) 14 24 7 (8,11) 16 22 8 -5 (9,11) 18 22 9 14 (10,10)

15. Midpoint Ellipse drawing Input r x , r y and ellipse center (x c ,y c ) and obtain the first point on an ellipse centered (0,0) on the origins as (x ,y ) = (0,r y ). Calculate the initial value of decision parameter in region 1 as p1 = r y 2 - r x 2 r y + ¼ r x 2 . At each x k position in region 1 starting at k=0 , perform the following test : If p1 k < 0 then the next point along the ellipse centered on (0,0) is (x k+1 ,y k ) and p1 k+1 = p1 k +2r y 2 x k+1 +r y 2 else the next point along the ellipse centered on (0,0) is ( x k+1 ,y k-1 ) and p1 k+1 = p1 k +2r y 2 x k+1 +r y 2 -2r x 2 y k+1. Repeat the steps for region 1 until 2r y 2 x k+1 >= 2r x 2 y k+1

16. Midpoint Ellipse drawing Calculate the initial value of decision parameter in region 2 using the last point (x ,y ) calculated in region 1 as p2 = r y 2 (x +½) 2 +r x 2 (y -1) 2 -r x 2 r y 2 At each y k position in region 2 starting at k=0, perform the following test: If p2 k >= 0 then the next point along the ellipse centered on (0,0) is ( x k ,y k-1 ) and p2 k+1 = p2 k -2r x 2 y k+1 +r x 2 else the next point along the ellipse centered on (0,0) is ( x k+1 ,y k+1 ) and p2 k+1 = p2 k +2r y 2 x k+1 -2r x 2 y k+1 +r x 2 . (Note: Use the same increment value for x and y in region 1.) Repeat the steps for region 2 until y k+1 =0.

17. Example 1 part 1 Given ellipse parameter with r x =8 and r y =6 use midpoint ellipse drawing to draw an ellipse. Initial point for region 1 (0,r y )=(0,6). 2r y 2 x= 0 (with increment value 2r y 2 = 2(6) 2 =72) 2r x 2 y= 2r x 2 r y = 2(8) 2 (6) (with increment value –r x 2 =-2(8) 2 =-128) The initial decision parameter for region 1 p1 = r y 2 - r x 2 r y + ¼ r x 2 =(6) 2 - (8) 2 (6) + ¼(8) 2 =-332

18. Example 1 part 2 k p k (x k+1 ,y k+1 ) 2r y 2 x k+1 2r x 2 y k+1 -332 (1,6) 72 768 1 -224 (2,6) 144 768 2 -44 (3,6) 216 768 3 208 (4,5) 288 640 4 -108 (5,5) 360 640 5 288 (6,4) 432 512 6 244 (7,3) 504 384 Stop since 2r y 2 x k+1 > 2r x 2 y k+1

19. Example 1 part 3 We now move to region 2 Initial point for region 2 (x ,y )=(7,3). The initial decision parameter for region 2 p2 = r y 2 (x +½) 2 +r x 2 (y -1) 2 -r x 2 r y 2 =36(7.5) 2 +64(2) 2 -64*36= -151 k p k (x k+1 ,y k+1 ) 2r y 2 x k+1 2r x 2 y k+1 -151 (8,2) 576 256 1 233 (8,1) 576 128 2 745 (8,0) 576

20. Example 2 part 1 Given ellipse parameter with r x =8 and r y =10 use midpoint ellipse drawing to draw an ellipse. Initial point for region 1 (0,r y )=(0,10). 2r y 2 x= 0 (with increment value 2r y 2 = 2(10) 2 =200) 2r x 2 y= 2r x 2 r y = 2(8) 2 (10) (with increment value –r x 2 =-2(8) 2 =-128) The initial decision parameter for region 1 p1 = r y 2 - r x 2 r y + ¼ r x 2 =(10) 2 - (8) 2 (10) + ¼(8) 2 =-524

21. Example 2 part 2 k p k (x k+1 ,y k+1 ) 2r y 2 x k+1 2r x 2 y k+1 -524 (1,10) 200 1280 1 -224 (2,10) 400 1280 2 276 (3,9) 600 1152 3 -176 (4,9) 800 1152 4 724 (5,8) 1000 1024 5 800 (6,7) 1200 896

22. Example 2 part 3 We now move to region 2 Initial point for region 2 (x ,y )=(6,7). The initial decision parameter for region 2 p2 = r y 2 (x +½) 2 +r x 2 (y -1) 2 -r x 2 r y 2 =100(6.5) 2 +64(6) 2 -64*100= 129 k p k (x k+1 ,y k+1 ) 2r y 2 x k+1 2r x 2 y k+1 129 (6,6) 1200 768 1 -703 (7,5) 1400 640 ( ,0) Stop