Bresenham’s line algorithm is used to draw a line from the starting point (x0 , y0 ) (20,10) to the end point
(xend , yend ) (30,18). Given the current pixel (xk , yk )
that has been intensified, the next pixel (xk1, yk1) to be
intensified is determined by the decision parameter pk x(dlower dupper), where xxend x0, dlower and
dupper are vertical pixel separations from the mathematical line as shown in Figure P1. Calculate the
decision parameter pk and the next pixel’s coordinates (xk1,yk1) for k0,1,2,3 according to Bresenham’s
line algorithm.
Bresenham’s line algorithm is used to draw a line from the starting point (x0,y0)(5,4) totheendpoint (xend,yend)(20,10). Giventhecurrentpixel (xk,yk)
that has been intensified, the next pixel (xk1, yk1) to be intensified is determined by the decision parameter pk x(dlower dupper), where x xend x0, dlower and dupper
are vertical pixel separations from the mathematical line as shown in Figure P1. Calculate the decision parameter pk and the next pixel’s coordinates (xk1, yk1) for
k 0, 1, 2, 3, 4 according to Bresenham’s line algorithm.
Bresenham’s line algorithm is used to draw a line from the starting point (x0,y0)(10,4) totheendpoint (xend,yend)(25,12). Giventhecurrentpixel (xk,yk)
that has been intensified, the next pixel (xk1, yk1) to be intensified is determined by
the decision parameter pk x(dlower dupper), where x xend x0, dlower and dupper
are vertical pixel separations from the mathematical line as shown in Figure P1. One of the pixels to be intensified is located at ( x p , y p ) where the x-coordinate is x p 13.
Calculate the y-coordinate, y p , of this pixel according to Bresenham’s line algorithm.
300029 Engineering Visualization: Tutorial 4
Examples in lecture: Examples in tutorial: Homework:
*Problem 1
Problems with two asterisks (**) Problems with one asterisk (*) All problems for this tutorial
Tutorial 4 Scan Converting Lines and Circles
Dr. J.J. Zou, WSU School of Engineering Page 1
Bresenham’s line algorithm is used to draw a line from the starting point (x0,y0)(5,6) totheendpoint (xend,yend)(15,18). Giventhecurrentpixel (xk,yk)
that has been intensified, the next pixel (xk1, yk1) to be intensified is determined by the decision parameter pk x(dlower dupper), where x xend x0, dlower and dupper
are vertical pixel separations from the mathematical line as shown in Figure P1. One of the pixels to be intensified is located at ( x p , y p ) where the x-coordinate is x p 1.
Calculate the y-coordinate, y p , of this pixel according to Bresenham’s line algorithm.
*Problem 5
The mid-point circle algorithm is used to draw the 2nd octant of a circle with radius r 10, centred at the
origin. Given the current pixel (xk , yk ) that has been
intensified, the next pixel (xk1, yk1) to be intensified is
determined by the decision parameter p x2 y2 r2 k
at the mid-point (x, y) (xk 1, yk 0.5) as shown in Figure P5. Calculate the decision parameter pk and the next pixel’s coordinates (xk1,yk1) for k0,1,2,3 according to the mid-point circle algorithm.
The mid-point circle algorithm is used to draw the 2nd octant of a circle with radius r 15, centred at the origin. Given the current pixel (xk , yk ) that has been intensified,
k 0, 1, 2, 3, 4 according to the mid-point circle algorithm.
The mid-point circle algorithm is used to draw the 2nd octant of a circle with radius r 8, centred at the origin. Given the current pixel (xk , yk ) that has been intensified,
the next pixel (xk1, yk1) to be intensified is determined by the decision parameter p x2 y2 r2 atthemid-point (x,y)(x 1,y 0.5) asshowninFigureP5.One
of the pixels to be intensified is located at ( x p , y p ) where the x-coordinate is x p 3.
Calculate the y-coordinate, yp, of this pixel according to the mid-point circle algorithm.
300029 Engineering Visualization: Tutorial 4
the next pixel (xk1, yk1) to be intensified is determined by the decision parameter p x2 y2 r2 at the mid-point (x,y)(x 1,y 0.5) as shown in Figure P5.
Calculate the decision parameter pk and the next pixel’s coordinates (xk1, yk1) for
Dr. J.J. Zou, WSU School of Engineering Page 2
of the pixels to be intensified is located at ( x p , y p ) where the x-coordinate is x p 5.
Calculate the y-coordinate, yp, of this pixel according to the mid-point circle algorithm.
300029 Engineering Visualization: Tutorial 4
The mid-point circle algorithm is used to draw the 2nd octant of a circle with radius r 9, centred at the origin. Given the current pixel (xk , yk ) that has been intensified,
the next pixel (xk1, yk1) to be intensified is determined by the decision parameter p x2 y2 r2 atthemid-point (x,y)(x 1,y 0.5) asshowninFigureP5.One
Dr. J.J. Zou, WSU School of Engineering Page 3
*Problem 1
Solutions to Problems in Tutorial 4
Bresenham’s line algorithm is used to draw a line from the starting point (x0 , y0 ) (20,10) to the end point
(xend , yend ) (30,18). Given the current pixel (xk , yk )
that has been intensified, the next pixel (xk1, yk1) to be
intensified is determined by the decision parameter pk x(dlower dupper), where x xend x0, dlower and
dupper are vertical pixel separations from the mathematical line as shown in Figure P1. Calculate the
decision parameter pk and the next pixel’s coordinates (xk1, yk1) for k 0,1,2,3 according to Bresenham’s
line algorithm.
According to Bresenham’s line algorithm : *p0 2yx;
*If pk 0,thennextpixellowerpixel,and
pk1 pk 2y;
*If pk 0,thennextpixelupperpixel,and
300029 Engineering Visualization: Tutorial 4
pk 1 pk 2y 2x. p0 2yx2(1810)(3020)6;
For k 0 :
p0 0 Nextpixelupperpixel: x1 x0 121, y1 y0 111.
p0 0 p1 p0 2y2x62(1810)2(3020)2; p10Nextpixelupperpixel:x2 x1122,y2 y1112.
For k 2 :
p1 0 p2 p1 2y2x22(1810)2(3020)2; p2 0 Nextpixellower pixel: x3 x2 123, y3 y2 12.
p2 0 p3 p2 2y22(1810)14; p30Nextpixelupperpixel:x4 x3124,y4 y3113.
Dr. J.J. Zou, WSU School of Engineering
For k 0 :
p0 0 Next pixel lower pixel : x1 x0 1 6, y1 y0 4.
p0 0 p1 p0 2y 3 2(10 4) 9; p10Nextpixelupperpixel:x2 x117,y2 y115.
For k 2 :
p1 0 p2 p1 2y2x92(104)2(205)9; p2 0 Next pixel lower pixel : x3 x2 1 8, y3 y2 5.
For k 3 :
p2 0 p3 p2 2y 9 2(10 4) 3;
p3 0 Next pixel upper pixel : x4 x3 1 9, y4 y3 1 6.
For k 4 :
p3 0 p4 p3 2y2x32(104)2(205)15; p4 0 Next pixel lower pixel : x5 x4 1 10, y5 y4 6.
300029 Engineering Visualization: Tutorial 4
Bresenham’s line algorithm is used to draw a line from the starting point (x0,y0)(5,4) totheendpoint (xend,yend)(20,10). Giventhecurrentpixel (xk,yk)
that has been intensified, the next pixel (xk1, yk1) to be intensified is determined by the decision parameter pk x(dlower dupper), where x xend x0, dlower and dupper
are vertical pixel separations from the mathematical line as shown in Figure P1. Calculate the decision parameter pk and the next pixel’s coordinates (xk1, yk1) for
k 0, 1, 2, 3, 4 according to Bresenham’s line algorithm. Solution:
According to Bresenham’s line algorithm : *p0 2yx;
*If pk 0,thennextpixellowerpixel,and
pk1 pk 2y;
*If pk 0,thennextpixelupperpixel,and
pk1 pk 2y2x. p0 2yx2(104)(205)3;
Dr. J.J. Zou, WSU School of Engineering
For k 0 :
p0 0 Next pixel upper pixel : x1 x0 1 11, y1 y0 1 5.
p0 0 p1 p02y2x12(124)2(2510)13; p10Nextpixellowerpixel:x2 x1112,y2 y15.
For k 2 :
p1 0 p2 p12y132(124)3;
p2 0 Next pixel upper pixel : x3 x2 1 13, y3 y2 1 6.
yp y3 6.
300029 Engineering Visualization: Tutorial 4
Bresenham’s line algorithm is used to draw a line from the starting point (x0,y0)(10,4) totheendpoint (xend,yend)(25,12). Giventhecurrentpixel (xk,yk)
that has been intensified, the next pixel (xk1, yk1) to be intensified is determined by the decision parameter pk x(dlower dupper), where x xend x0, dlower and dupper
are vertical pixel separations from the mathematical line as shown in Figure P1. One of the pixels to be intensified is located at ( x p , y p ) where the x-coordinate is x p 13.
Calculate the y-coordinate, y p , of this pixel according to Bresenham’s line algorithm. Solution:
According to Bresenham’s line algorithm : *p0 2yx;
*If pk 0,thennextpixellowerpixel,and
pk1 pk 2y;
*If pk 0,thennextpixelupperpixel,and
pk1 pk 2y2x. p0 2yx2(124)(2510)1;
Dr. J.J. Zou, WSU School of Engineering
For k 0 :
p0 0 Next pixel upper pixel : x1 x0 1 4, y1 y0 1 7.
p0 0 p1 p0 2y2x42(186)2(15(5))12; p1 0 Next pixel lower pixel : x2 x1 1 3, y2 y1 7.
For k 2 :
p1 0 p2 p1 2y 12 2(18 6) 12;
p2 0 Next pixel upper pixel : x3 x2 1 2, y3 y2 1 8.
For k 3 :
p2 0 p3 p2 2y2x122(186)2(15(5))4; p3 0 Next pixel lower pixel : x4 x3 1 1, y4 y3 8.
yp y4 8.
300029 Engineering Visualization: Tutorial 4
Bresenham’s line algorithm is used to draw a line from the starting point (x0,y0)(5,6) totheendpoint (xend,yend)(15,18). Giventhecurrentpixel (xk,yk)
that has been intensified, the next pixel (xk1, yk1) to be intensified is determined by the decision parameter pk x(dlower dupper), where x xend x0, dlower and dupper
are vertical pixel separations from the mathematical line as shown in Figure P1. One of the pixels to be intensified is located at ( x p , y p ) where the x-coordinate is x p 1.
Calculate the y-coordinate, y p , of this pixel according to Bresenham’s line algorithm. Solution:
According to Bresenham’s line algorithm : *p0 2yx;
*If pk 0,thennextpixellowerpixel,and
pk1 pk 2y;
*If pk 0,thennextpixelupperpixel,and
pk1 pk 2y2x. p0 2yx2(186)(15(5))4;
Dr. J.J. Zou, WSU School of Engineering
pk1 pk 2(xk 1)2(yk 1)1. p0 1r1109;
For k 0 :
p0 0 Nextpixelupperpixel: x1 x0 11, y1 y0 10.
p0 0 p1 p0 2(x0 1)192(01)16; p10Nextpixelupperpixel:x2 x112,y2 y110.
For k 2 :
p1 0 p2 p1 2(x1 1)162(11)11;
p2 0 Nextpixelupperpixel: x3 x2 13, y3 y2 10.
p2 0 p3 p2 2(x2 1)112(21)16;
p3 0 Nextpixellower pixel: x4 x3 14, y4 y3 19.
300029 Engineering Visualization: Tutorial 4
*Problem 5
The mid-point circle algorithm is used to draw the 2nd octant of a circle with radius r 10, centred at the
origin. Given the current pixel (xk , yk ) that has been
intensified, the next pixel (xk1, yk1) to be intensified is
determined by the decision parameter p x2 y2 r2 k
at the mid-point (x, y) (xk 1, yk 0.5) as shown in Figure P5. Calculate the decision parameter pk and the next pixel’s coordinates (xk1,yk1) for k0,1,2,3 according to the mid-point circle algorithm.
According to the mid – point circle algorithm : * ( x0 , y0 ) (0, r) (0, 10);
*If pk 0,thennextpixelupperpixel,and
pk1pk2(xk1)1;
*If pk 0,then nextpixellowerpixel,and
Dr. J.J. Zou, WSU School of Engineering
The mid-point circle algorithm is used to draw the 2nd octant of a circle with radius r 15, centred at the origin. Given the current pixel (xk , yk ) that has been intensified,
the next pixel (xk1, yk1) to be intensified is determined by the decision parameter p x2 y2 r2 at the mid-point (x,y)(x 1,y 0.5) as shown in Figure P5.
Calculate the decision parameter pk and the next pixel’s coordinates (xk1, yk1) for
k 0, 1, 2, 3, 4 according to the mid-point circle algorithm. Solution:
According to the mid – point circle algorithm : *(x0, y0 ) (0, r) (0,15);
*If pk 0,thennextpixelupperpixel,and
pk1pk2(xk1)1;
*If pk 0,then nextpixellowerpixel,and
pk1 pk 2(xk 1)2(yk 1)1. p0 1r11514;
For k 0 :
p0 0 Nextpixelupperpixel: x1 x0 11, y1 y0 15.
p0 0 p1 p0 2(x0 1)1142(01)111; p10Nextpixelupperpixel:x2 x112,y2 y115.
For k 2 :
p10 p2 p12(x11)1112(11)16;
p2 0 Nextpixelupperpixel: x3 x2 13, y3 y2 15.
p2 0 p3 p2 2(x2 1)162(21)11; p30Nextpixellowerpixel:x4 x314,y4 y3114.
For k 4 :
p3 0 p4 p3 2(x3 1)2(y3 1)112(31)2(151)118; p4 0 Nextpixelupperpixel: x5 x4 15, y5 y4 14.
300029 Engineering Visualization: Tutorial 4
Dr. J.J. Zou, WSU School of Engineering
The mid-point circle algorithm is used to draw the 2nd octant of a circle with radius r 8, centred at the origin. Given the current pixel (xk , yk ) that has been intensified,
the next pixel (xk1, yk1) to be intensified is determined by the decision parameter p x2 y2 r2 atthemid-point (x,y)(x 1,y 0.5) asshowninFigureP5.One
of the pixels to be intensified is located at ( x p , y p ) where the x-coordinate is x p 3.
Calculate the y-coordinate, yp, of this pixel according to the mid-point circle algorithm.
According to the mid – point circle algorithm : * ( x0 , y0 ) (0, r) (0, 8);
*If pk 0,thennextpixelupperpixel,and
pk1pk2(xk1)1;
*If pk 0,then nextpixellowerpixel,and
pk1 pk 2(xk 1)2(yk 1)1. p0 1r187;
For k 0 :
p0 0 Nextpixelupperpixel: x1 x0 11, y1 y0 8.
p0 0 p1 p0 2(x0 1)172(01)14; p10Nextpixelupperpixel:x2 x112,y2 y18.
For k 2 :
p1 0 p2 p1 2(x1 1)142(11)11;
p2 0 Nextpixellower pixel: x3 x2 13, y3 y2 17.
yp y3 7.
300029 Engineering Visualization: Tutorial 4
Dr. J.J. Zou, WSU School of Engineering
The mid-point circle algorithm is used to draw the 2nd octant of a circle with radius r 9, centred at the origin. Given the current pixel (xk , yk ) that has been intensified,
the next pixel (xk1, yk1) to be intensified is determined by the decision parameter p x2 y2 r2 atthemid-point (x,y)(x 1,y 0.5) asshowninFigureP5.One
of the pixels to be intensified is located at ( x p , y p ) where the x-coordinate is x p 5.
Calculate the y-coordinate, yp, of this pixel according to the mid-point circle algorithm.
According to the mid – point circle algorithm : * ( x0 , y0 ) (0, r) (0, 9);
*If pk 0,thennextpixelupperpixel,and
pk1pk2(xk1)1;
*If pk 0,then nextpixellowerpixel,and
pk1 pk 2(xk 1)2(yk 1)1. p0 1r198;
For k 0 :
p0 0 Nextpixelupperpixel: x1 x0 11, y1 y0 9.
p0 0 p1 p0 2(x0 1)182(01)15; p10Nextpixelupperpixel:x2 x112,y2 y19.
For k 2 :
p10 p2 p12(x11)152(11)10;
p2 0 Nextpixellower pixel: x3 x2 13, y3 y2 18.
p2 0 p3 p2 2(x2 1)2(y2 1)102(21)2(91)19; p3 0 Nextpixelupperpixel: x4 x3 14, y4 y3 8.
For k 4 :
p3 0 p4 p3 2(x3 1)192(31)10;
p4 0 Nextpixellower pixel: x5 x4 15, y5 y4 17.
yp y5 7.
Dr. J.J. Zou, WSU School of Engineering
300029 Engineering Visualization: Tutorial 4