# CSC 210 1.0 Computer Graphics - drawing algorithms DDA Midpoint (Bresenhams) Algorithm Circle drawing algorithms

• Published on
17-Apr-2018

• View
218

4

Transcript

• 7/21/2017

1

CSC 210 1.0

Computer Graphics

Kasun@dscs.sjp.ac.lk

Department of Computer Science

University of Sri Jayewardanepura

1

Lecture 02

Line drawing algorithms

DDA

Midpoint (Bresenhams) Algorithm

Circle drawing algorithms

Simple Circle Algorithm

Mid-Point Circle Algorithm

Ellipse drawing algorithms

Simple Ellipse Algorithm

Midpoint Ellipse Algorithm

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 2

A line segment in a scene is defined by the coordinate positions of the line end-points

x

y

(2, 2)

(7, 5)

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 4

But what happens when we try to draw this on a pixel based display?

How do we choose which pixels to turn on?7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 5

Considerations to keep in mind:

The line has to look good

Avoid jaggies

It has to be lightening fast!

Millions of lines need to be drawn in a typical scene.

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 6

• 7/21/2017

2

Lines must create visually satisfactory images.

Lines should appear straight

Lines should terminate accurately

Lines should have constant density

Line density should be independent of line length and angle.

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 7

Ideally, the following properties should be considered

Smooth

Continuous

Pass through specified points

Uniform brightness

Efficient

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 8

There are three possible choices.

Explicit: y = f(x)

y = m (x - x0) + y0 where m = dy/dx

Parametric: x = f(t), y = f(t)

x = x0 + t(x1 - x0), t in [0,1]

y = y0 + t(y1 - y0)

Implicit: f(x, y) = 0

F(x,y) = (x-x0)dy - (y-y0)dx

if F(x,y) = 0 then (x,y) is on line

F(x,y) > 0 then (x,y) is below line

F(x,y) < 0 then (x,y) is above line

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 9

DrawLine(int x1, int y1, int x2, int y2, int color){

float y;int x;

for (x=x1; x

• 7/21/2017

3

Lets quickly review the equations involved in drawing lines

x

y

y0

yend

xendx0

Slope-intercept line

equation:

cxmy

where:

0

0

xx

yym

end

end

00 xmyc 7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 13

The slope of a line (m) is defined by its start and end coordinates

The diagram below shows some examples of lines and their slopes

m = 0

m = -1/3

m = -1/2

m = -1

m = -2m = -4

m =

m = 1/3

m = 1/2

m = 1

m = 2m = 4

m = 0

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 14

We could simply work out the corresponding

y coordinate for each unit x coordinate Lets consider the following example:

x

y

(2, 2)

(7, 5)

2 7

2

5

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 15

1

2

3

4

5

0

1 2 3 4 5 60 7

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 16

x

y

(2, 2)

(7, 5)

2 3 4 5 6 7

2

5

5

3

27

25

m

5

42

5

32 c

First work out m and b:

Now for each x value work out the y value:

5

32

5

43

5

3)3( y

5

13

5

44

5

3)4( y

5

43

5

45

5

3)5( y

5

24

5

46

5

3)6( y

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 17

Now just round off the results and turn on these pixels to draw our line

35

32)3( y

35

13)4( y

45

43)5( y

45

24)6( y

0 1 2 3 4 5 6 7 8

0

1

2

3

4

5

6

7

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 18

• 7/21/2017

4

However, this approach is just way too slow In particular look out for:

The equation y = mx + c requires the

multiplication of m by x

Rounding off the resulting y coordinates

We need a faster solution

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 19

In the previous example we chose to solve the parametric line equation to give us the ycoordinate for each unit x coordinate

What if we had done it the other way around?

Where: andm

cyx

0

0

xx

yym

end

end

00 xmyc

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 20

Leaving out the details this gives us:

We can see easily that this line doesnt lookvery good!

We choose which way to work out the line pixels based on the slope of the line

0 1 2 3 4 5 6 7 8

0

1

2

3

4

5

6

7

43

23)3( x 5

3

15)4( x

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 21

If the slope of a line is between -1 and 1 then we work out the y coordinates for a line based on its unit x coordinates

Otherwise we do the opposite x coordinates are computed based on unit y coordinates

m = 0

m = -1/3

m = -1/2

m = -1

m = -2m = -4

m =

m = 1/3

m = 1/2

m = 1

m = 2m = 4

m = 0

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 22

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 23

Given points P1 = (x1, y1) and P2 = (x2, y2)x = x1 + t(x2-x1)y = y1 + t(y2-y1)

t is called the parameter. Whent = 0 we get (x1,y1)t = 1 we get (x2,y2)

As 0 < t < 1 we get all the other points on the line segment between (x1,y1) and (x2,y2).

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 24

• 7/21/2017

5

The digital differential analyzer (DDA) algorithm takes an incremental approach in order to speed up scan conversion

Simply calculate yk+1based on yk

The original differential analyzerw a s a p h y s i c a l m a c h i n edeveloped by Vannevar Bush atMIT in the 1930s in order tosolve ordina ry differen tia le q u a t i o n s .

M o r e i n f o r m a t i o n h e r e .

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 26

Digital differential analyser

Y=mx+cFor m1x=y/m

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 27

Procedure DDA(X1,Y1,X2,Y2 :Integer);

Var Length, I :Integer;

X,Y,Xinc,Yinc :Real;

Begin

Length := ABS(X2 - X1);

If ABS(Y2 -Y1) > Length Then

Length := ABS(Y2-Y1);

Xinc := (X2 - X1)/Length;

Yinc := (Y2 -Y1)/Length;

X := X1;

Y := Y1;

For I := 0 To Length

Do

Begin

Plot(Round(X),

Round(Y));

X := X + Xinc;

Y := Y + Yinc

End {For}

End; {DDA}

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 28

Compute which pixels should be turned on to represent the line from (6,9) to (11,12).

Length := Max of (ABS(11-6), ABS(12-9)) = 5Xinc := 1Yinc := 0.6

Values computed are:(6,9), (7,9.6), (8,10.2), (9,10.8),(10,11.4), (11,12)

6 7 8 9 10 11 12 13

9

10

11

12

13

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 29

Consider the list of points that we determined for the line in our previous example: (2, 2), (3, 23/5), (4, 3

1/5), (5, 34/5), (6, 4

2/5), (7, 5)

Notice that as the x coordinates go up by one, the y coordinates simply go up by the slope of the line

This is the key insight in the DDA algorithm

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 30

http://scoter2.union.edu/~hemmendd/Encyc/Articles/Difanal/difanal.html

• 7/21/2017

6

When the slope of the line is between -1 and 1 begin at the first point in the line and, by incrementing the x coordinate by 1, calculate the corresponding y coordinates as follows:

When the slope is outside these limits, increment the y coordinate by 1 and calculate the corresponding x coordinates as follows:

myy kk 1

mxx kk

11

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 31

Again the values calculated by the equations used by the DDA algorithm must be rounded to match pixel values

(xk, yk) (xk+1, yk+m)

(xk, round(yk))

(xk+1, round(yk+m))

(xk, yk)(xk+

1/m, yk+1)

(round(xk), yk)

(round(xk+ 1/m), yk+1)

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 32

Lets try out the following examples:

x

y

(2, 2)

(7, 5)

2 7

2

5

x

y (2, 7)

(3, 2)

2 3

2

7

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 33

It is much faster than our previous attempt.

No any multiplications involved.

However, there are still two big issues:

Accumulation of round-off errors can make the pixelated line drift away from what was intended

The rounding operations and floating point arithmetic involved are time consuming

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 34

It is another incremental scan conversion algorithm.

The big advantage of this algorithm is that it uses only integer calculations

J a c k B r e s e n h a m

worked for 27 years at

IBM before entering

developed his famous

algorithms at IBM in

t h e e a r l y 1 9 6 0 s

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 36

• 7/21/2017

7

The midpoint algorithm is even better than the above

algorithm in that it uses only integer calculations. It treats line drawing as a sequence of decisions. For each pixel that is drawn the next pixel will be either N

or NE, as shown below.

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 37

It uses the implicit definition of the line, F(x,y) =0.

The N/NE decisions are made as follows.

d = F(xp + 1, yp + 0.5)

if d < 0 line below midpoint choose E

if d > 0 line above midpoint choose NE

if E is chosen

dnew = F(xp + 2, yp + 0.5)

dnew- dold = F(xp + 2, yp + 0.5) -F(xp + 1, yp + 0.5)

Delta = d new -d old = dy

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 38

If NE is chosen

dnew = F(xp+2, yp+1.5)

Delta = dy-dx

Initialization

dstart = F(x0+1, y0+0.5)= (x0+1-x0)dy - (y0+0.5-y0)dx= dy-dx/2

Integer only algorithm

F(x,y) = 2 F(x,y) ; d = 2d

dstart = 2dy - dx

Delta = 2Delta

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 39

DrawLine(int x1, int y1, int x2, int y2, int color)

{

int dx, dy, d, incE, incNE, x, y;

dx = x2 - x1;

dy = y2 - y1;

d = 2*dy - dx;

incE = 2*dy;

incNE = 2*(dy - dx);

y = y1;

for (x=x1; x0) {

d = d + incNE;

y = y + 1;

} else {

d = d + incE;

}

}

}

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 40

x := 0;

y := 0;

d := b - a/2;

For i := 0 to a do

Plot(x,y);

If d >= 0 Then

x := x + 1;

y := y + 1;

d := d + b a

Else

x := x + 1;

d := d + b

End

End

Note:

The only non-integer value is a/2. If we then

multiply by 2 to get d' = 2d, we can do all

integer arithmetic using only the operations +, -,

and left-shift. The algorithm still works since

we only care about the sign, not the value of d.

The initial value for the decision variable, d0, may be calculated directly from the formula at point (0,0).

d0 = f(0 + 1, 0 + 1/2) = b(1) - a(1/2) = b - a/2

Therefore, the algorithm for a line from (0,0) to (a,b) in the first octant is:

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 41

To generalize lines with arbitrary slopes Consider symmetry between various octants and

For m > 1, interchange roles of x and y, that is step in y direction, and decide whether the x value is above or below the line.

If m > 1, and right endpoint is the first point, both x and y decrease. To ensure uniqueness, independent of direction, always choose upper (or lower) point if the line go through the mid-point.

Handle special cases without invoking the algorithm: horizontal, vertical and diagonal lines

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 42

• 7/21/2017

8

Generalize the algorithm to work for lines beginning at points other than (0,0) by giving x and y the proper initial values.

Begin {Bresenham for lines with slope between 0 and 1}a := ABS(xend - xstart);b := ABS(yend - ystart);d := 2*b - a;Incr1 := 2*(b-a);Incr2 := 2*b;If xstart > xend Then

x := xend;y := yend

Else x := xstart;y := ystart

End For I := 0 to a Do

Plot(x,y);x := x + 1;If d >= 0 Then

y := y + 1;d := d + incr1

Else d := d + incr2

EndEnd {For Loop}

End {Bresenham}

Note: This algorithm only works for lines with slopes between 0 and 1

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 43

Move across the x axis in unit intervals and at each step choose between two different y coordinates

For example, from

position (2, 3) we have

to choose between (3,

3) and (3, 4)

We would like the point

that is closer to the

original line2 3 4 5

2

4

3

5

(xk, yk)

(xk+1, yk)

(xk+1, yk+1)

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 44

The y coordinate on the mathematical line at

xk+1 is:

At sample position xk+1the vertical separations from the mathematical

line are labelled dupperand dlower

bxmy k )1(

y

yk

yk+1

xk+1

dlower

dupper

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 45

So, dupper and dlower are given as follows:

and:

We can use these to make a simple decision about which pixel is closer to the mathematical line

klower yyd

kk ybxm )1(

yyd kupper )1(

bxmy kk )1(1

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 46

Explicit: y = f(x)

Parametric:

Implicit: f(x) = x2+y2-R2

2 2y R x

cos

sin

x R

y R

If f(x,y) = 0 then it is on the circle.f(x,y) > 0 then it is outside the circle.f(x,y) < 0 then it is inside the circle.

Usually, we draw a quarter circle by incrementing x from 0 to R in unit steps and solving for +y for each step.

- by stepping the angle from 0 to 90- avoids large gaps but still insufficient.

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 48

• 7/21/2017

9

The first thing we can notice to make our circle drawing algorithm more efficient is that circles centred at (0, 0) have eight-way symmetry

(x, y)

(y, x)

(y, -x)

(x, -y)(-x, -y)

(-y, -x)

(-y, x)

(-x, y)

2

R

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 49 7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 50

The equation for a circle is:

where r is the radius of the circleSo, we can write a simple circle drawing

algorithm by solving the equation for y at unit xintervals using:

222 ryx

22 xry

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 51

20020 220 y

20120 221 y

20220 222 y

61920 2219 y

02020 2220 y

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 52

This is not a brilliant solution!

It has large gaps where the slope approaches the vertical.

The calculations are not very efficient The square (multiply) operations The square root operation try really hard to

avoid these!

We need a more efficient, more accurate solution

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 53

X=r*cos+xcY=r*sin+yc

0360Or

0 6.28(2*)

Problem:

Deciding the increment in

Cos, sin calculations

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 54

• 7/21/2017

10

Similarly to the case with lines, there is an incremental algorithm for drawing circles the mid-point circle algorithmIn the mid-point circle algorithm we use eight-way symmetry so only ever calculate the points for the top right eighth of a circle, and then use symmetry to get the rest of the points

The mid-point circle

a l g o r i t h m w a s

developed by Jack

Bresenham, who we

Bresenhams patent

for the algorithm can

b e v i e w e d h e r e .7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 56

dold = F(xp+1, yp+0.5) If dold < 0, E is chosen

dnew = F(xp+2, yp-0.5)

= dold+(2xp+3)

DeltaE = 2xp+3

If dold >= 0, SE is chosen

dnew = F(xp+2, yp-1.5)= dold+(2xp-2yp+5)

DeltaSE = 2xp-2yp+5

Initialization

dinit = 5/4 R= 1 - R

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 57 7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 58

6

2 3 41

5

4

3

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 59

M

6

2 3 41

5

4

3

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 60

http://patft.uspto.gov/netacgi/nph-Parser?u=/netahtml/srchnum.htm&Sect1=PTO1&Sect2=HITOFF&p=1&r=1&l=50&f=G&d=PALL&s1=4371933.PN.&OS=PN/4371933&RS=PN/4371933

• 7/21/2017

11

M

6

2 3 41

5

4

3

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 61

(xk+1, yk)

(xk+1, yk-1)

(xk, yk)

Assume that we have

just plotted point (xk, yk)The next point is a

choice between (xk+1, yk)

and (xk+1, yk-1)We would like to choose the point that is nearest to the actual circleSo how do we make this choice?

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 62

Lets re-jig the equation of the circle slightly to give us:

The equation evaluates as follows:

By evaluating this function at the midpoint between the candidate pixels we can make our decision

222),( ryxyxfcirc

,0

,0

,0

),( yxfcirc

boundary circle theinside is ),( if yx

boundary circle on the is ),( if yx

boundary circle theoutside is ),( if yx

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 63

Assuming we have just plotted the pixel at (xk,yk) so we need to choose between (xk+1,yk) and (xk+1,yk-1)Our decision variable can be defined as:

If pk < 0 the midpoint is inside the circle and andthe pixel at yk is closer to the circleOtherwise the midpoint is outside and yk-1 is closer

222 )2

1()1(

)2

1,1(

ryx

yxfp

kk

kkcirck

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 64

To ensure things are as efficient as possible we can do all of our calculations incrementallyFirst consider:

or:

where yk+1 is either yk or yk-1 depending on the sign of pk

2212111

21]1)1[(

21,1

ryx

yxfp

kk

kkcirck

1)()()1(2 122

11 kkkkkkk yyyyxpp

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 65

The first decision variable is given as:

Then if pk < 0 then the next decision variable is given as:

If pk > 0 then the decision variable is:

r

rr

rfp circ

45

)2

1(1

)2

1,1(

22

0

12 11 kkk xpp

1212 11 kkkk yxpp

7/21/2017 Kasun@dscs.sjp.ac.lk - Faculty of Applied Sciences of USJP 66