CSC 210 1.0 Computer Graphics - drawing algorithms DDA Midpoint (Bresenham’s) Algorithm Circle drawing algorithms

  • Published on
    17-Apr-2018

  • View
    218

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

    academia. Bresenham

    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

    quadrants

    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

    heard about earlier.

    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

Recommended

View more >