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

  • Published on
    18-Apr-2018

  • View
    215

  • Download
    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)