# Line and Circle Rasterization shen.94/681/Site/DDA_files/DDA.pdfLine and Circle Rasterization Algorithms ... Bresenham’s Line Drawing Algorithm Only incremental integer operations are used In the case of 0 m 1,

• Published on
18-Apr-2018

• View
215

3

Transcript

• Line and Circle Rasterization Algorithms

2D screen coordinate systems (0based)

(1) pixels as grid cells

(2) pixels as intersection points

0 1 2 3 4 5 6 7

543210

: (3,5)

: (3,5)

0 1 2 3 4 5 6 7

543210

We use convention (2)

• LineDrawing Algorithm

0 1 2 3 4 5 6 7 8 9 10 11 12 ....

876543210

rasterize_line_segment(x0, y0, x1, y1);

x0,y0

x1,y1

0 1 2 3 4 5 6 7 8 9 10 11 12 ....

876543210

• For a given pair of points (x0,y0) and (x1,y1), let dx = x1x0, and dy = y1y0

we can compute the slope as:

m = (y1y0)/(x1x0) = dy / dx

and

intercept b = y1 m*x1

(x0, y0)

(x1, y1)

Given the slope, we have:

dy = m . dx

also

dx = dy . (1/m)

We can use the above equation to computea sequence of discrete points along the linesegment:

SlopeIntercept Line Equation

y = m . x + b slope intercept

DDA LineDrawing Algorithm

• Starting from X = x0 Y = y0

If we choose the next points x value at:

X = X + X

Then we have:

Y = Y + ??

(x0, y0)

(x1, y1)

xy

(x,y)

Now consider the screen (discrete) space ...

our goal: finding the closest pixels (integer x and y) along the line path

0 1 2 3 4 5 6 7

543210

DDA LineDrawing Algorithm (contd)

To do this, we can set x = 1, and we will have:

X1 = x0 + 1 ... Xk = Xk1 + 1

Y1 = y0 + m ... Yk = Yk1 + m

plot (X1, int(Y1)) ... plot (Xk, int(Yk))

• What about a line looks like this ?

0 1 2 3 4 5 6 7

543210

Instead, we should increment Y by 1 in this case:

Can we still use X = 1 and compute y ?

No! Because if we do so, we will end up with .....

DDA LineDrawing Algorithm (contd)

Set y = 1, and we will have:

X1 = x0 + 1/m ... Xk = Xk1 + 1/m

Y1 = y0 + 1 ... Yk = Yk1 + 1

plot (int(X1), Y1) ... plot (int(Xk),Yk)

• So far in our discussions the slope m is greater

than 0, what to do if m is negative?

The above algorithm is called DDA

(Digital Differential Analyzer) algorithm because

it is based on X and Y

Read page 8788 in the textbook

DDA Algorithm has two problems:

1) Numerical errors (could be bad for long line segments)

2) Floating point operations Too slow

DDA LineDrawing Algorithm (contd)

• Bresenhams Line Drawing Algorithm

Only incremental integer operations are used

In the case of 0 < m < 1,

we sample the line at unit X intervals, what we

really need to decide is

Should we increment Y now?

: pixel has been drawn

: draw northeast pixel?

: draw east pixel?

NE

E

• Xk

Y +1

Y

d2

d1

Should we increment Y?

If d1 > d2

if d2 > d1

Use NE pixel (y = Y+1)

Use E pixel (y = Y)

Can we compute and compare d1 and d2 using pure integer operations ?

Bresenhams Line Drawing Algorithm (contd)

The key idea:

NE

E

• Assuming that the kth pixels (Xk, Yk) along the line has been drawn, and 0 d2)

Remember the line equation: Y = m*X + b

so we have Y = m (Xk + 1) + b

d1 = Y Yk = m (Xk + 1) + b Yk d2 = (Yk + 1) Y = Yk + 1 m ( Xk + 1) b

d1 d2 = 2 m (Xk + 1) 2 Yk + 2 b 1

Substitute m = dy / dx

d1 d2 = 2 (dy / dx ) (Xk + 1) 2 Yk + 2 b 1

d2

d1

NE

E(Xk, Yk)

Bresenhams Line Drawing Algorithm (contd)

dx (d1d2) = 2dy (Xk + 1) 2 dx Yk + dx (2b1)

let 2 dy + dx ( 2b1) = c We have:

dx (d1d2) = 2dy . Xk 2 dx . Yk + C

• dx (d1d2) = 2dy . Xk 2 dx . Yk + C

Remember C = 2 dy + dx ( 2b1) and

dy = y1 y0 (y distance of two end points) dx = x1 x0 (x distance of two end points)

Let Pk = dx (d1 d2)

If we only consider the dx > 0 (draw the line from left to right):

then Pk has the same sign as (d1 d2)

That is:

if Pk < 0 => d1 < d2 => Yk+1 = Yk (take the E Pixel)

else d1 > d2 => Yk+1 = Yk + 1 ( take the NE pixel)

Bresenhams Line Drawing Algorithm (contd)

d2

d1

NE

E(Xk, Yk)

• Consider

Pk = 2 dy . Xk 2 d x . Yk + C

We have:

Pk+1 = 2 dy . Xk+1 2 d x . Yk+1 + C where

(Xk+1, Yk+1) is the (k+1)th pixel

Pk+1 Pk = 2 dy (Xk+1 Xk) 2 dx (Yk+1 Yk)

= 2 dy 2 dx (Yk+1 Yk)

So,

Pk+1 = Pk + 2 dy 2 d x . (Yk+1 Yk)

The initial condition P0:

P0 = 2 dy. X0 2 dx . Y0 + 2 dy

+ dx ( 2 Y0 2 dy/dx . X0 1)

= 2dy d x

Given Pk, we can compute Pk+1 incrementally:

Bresenhams Line Drawing Algorithm (contd)

• Bresenhams Line Algorithm

Given end points (x0,y0) (x1,y1)

dx = x1 x0, dy = y1 y0

Starting with an end point (x0, y0):

1. Compute P0 = 2dy dx

2. For each K, starting with k = 0

if (Pk < 0)

the next point is (Xk + 1, Yk) // E pixel Pk+1 = Pk + 2 dy

else

the next point is (Xk + 1, Yk + 1) // NE pixel Pk+1 = Pk + 2(dy dx)

3 Repeat step 2 x1x0 times