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