- Home
- Documents
- 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-2018View

215Download

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

Ask yourself ...

In the class, we assumed that 0 < m < 1 and dx > 0, where m is the slope of the line segment and dx = x1 x0

Describe how we should modify the algorithm

at the bottom of page 90 in the textbook for an arbitrary slope m and dx ?

(hint: read page 91, 92)