Computer Graphics - Line Drawing Line drawing is fundamental to computer graphics. We must have fast and efficient line drawing functions. Rasterization Problem: Given only the two end points, how to compute the intermediate pixels ...

  • Published on
    18-Apr-2018

  • View
    215

  • Download
    3

Transcript

  • Computer Graphics

    Line, Circle, Ellipse Drawing

    And

    Fill Area Algorithms

  • 2

    Line Drawing Line drawing is fundamental to computer graphics. We must have fast and efficient line drawing functions.

    Rasterization Problem: Given only the two end points, how to compute the intermediate pixels, so that the set of pixels

    closely approximate the ideal line.

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 3

    Line Drawing - Analytical Method

    y y

    x x

    y x

    b am

    b a

    c a ma

    y

    x

    y=mx+c

    ax bx

    A(ax,ay)

    B(bx,by)

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 4

    Directly based on the analytical equation of a line. Involves floating point multiplication and addition Requires round-off function.

    //Given (ax, ay) and (bx, by)

    double m = (double)(by-ay)/(bx-ax);

    double c = ay - m*ax;

    double y;

    int iy;

    for (int x=ax; x

  • Compute one point based on the previous point:

    (x0, y0)...(xk, yk) (xk+1, yk+1) .

    I have got a pixel on the line (Current Pixel).How do I get the next pixel on the line?

    Next pixel on next column(when slope is small)

    Next pixel on next row(when slope is large)

    Incremental Algorithms

    1/21/2011 5Gaurav Raj, Lovely professional University,

    Punjab

  • 6

    To find (xk+1, yk+!):

    xk+1 = xk+1

    yk+1 = ?

    Current

    Pixel

    (xk, yk) (5,2)

    (6,1)

    (6,2)

    (6,3)

    Assumes that the next pixel to be set is on the next column of pixels (Incrementing the value of x !)

    Not valid if slope of the line is large

    Incrementing along x

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 7

    Digital Differential Analyzer Algorithm is an incremental

    algorithm.

    Assumption: Slope is less than 1 (Increment along x).Current Pixel = (xk, yk).

    (xk, yk) lies on the given line. yk = m.xk + c

    Next pixel is on next column. xk+1 = xk+1Next point (xk+1, yk+1) on the line yk+1 = m.xk+1 + c

    = m (xk+1) +c= yk + m

    Given a point (xk, yk) on a line, the next point is given byxk+1 = xk+1yk+1 = yk + m

    Line Drawing - DDA

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 8

    Does not involve any floating point multiplication Involves floating point addition. Requires round-off function

    Line Drawing - DDA

    double m = (double) (by-ay)/(bx-ax);

    double y = ay;

    int iy;

    for (int x=ax; x

  • 9

    xk+1 = xk+1

    yk+1 = Either yk or yk+1

    Midpoint algorithm is an incremental algorithm

    Midpoint Algorithm

    Assumption:Slope < 1

    CurrentPixel

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 10

    Candidate Pixels

    Current Pixel(xk, yk)

    Midpoint

    Line

    Coordinates of Midpoint = (xk+1, yk+)

    (xk+1, yk)

    (xk+1, yk+1)

    Midpoint Algorithm -Notations

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 11

    Midpoint Below Line Midpoint Above Line

    Midpoint Algorithm:Choice of the next pixel

    If the midpoint is below the line, then the next pixel is (xk+1, yk+1)

    If the midpoint is above the line, then the next pixel is (xk+1, yk)

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 12

    A(ax, ay)

    B(bx, by)

    Equation of a line revisited

    Let w = bx ax, and h = by ay

    Then, h (x ax) w (y ay) = 0

    (h, w , ax , ay are all integers)

    In other words, every point (x, y) on the line satisfies the equation F(x, y) =0, where

    F(x, y) = h (x ax) w (y ay)

    Equation of the line:y x

    y y x x

    y a x a

    b a b a

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 13

    Midpoint Algorithm:Regions below and above the line

    F (x,y) > 0(for any point below line)

    F(x,y) < 0(for any point above line)

    F(x,y) = 0

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 14

    F(MP) > 0

    0),( yxf

    Midpoint below line

    F(MP) < 0

    Midpoint above line

    Midpoint Algorithm:Decision Criteria

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 15

    Midpoint AlgorithmDecision Criteria

    F(MP) = F(xk+1, yk+ ) = Fk (Notation)

    If Fk < 0 : The midpoint is above the line. So the next pixel is (xk+1, yk)

    If Fk 0 : The midpoint is below or on the line. So the next pixel is (xk+1, yk+1)

    Decision Parameter

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 16

    Midpoint Algorithm Story so far

    Midpoint Below Line

    Next pixel = (xk+1, yk+1)

    Fk > 0

    yk+1 = yk+1

    Midpoint Above Line

    Next pixel = (xk+1, yk)

    Fk < 0

    yk+1 = yk

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 17

    Midpoint Algorithm:Update Equation

    Fk = F(xk+1, yk+ ) = h (xk+1 ax) w (yk+ ay)

    Thus, given Fk< 0, yk+1 = yk then Fk+1 = Fk + h

    given Fk 0, yk+1 = yk+1 then Fk+1 = Fk + h w

    F0 = h (ax +1 ax) w (ay + ay) = h w/2

    Fk+1 = F(xk+1+1, yk+1+ ) = h (xk+1+1 ax) w (yk+1+ ay)

    Fk+1 - Fk = h (xk+1 xk) w (yk+1 yk)

    Fk+1 - Fk = h (xk +1 xk) w (yk+1 yk)

    Fk+1 = Fk + h w (yk+1 yk)

    1

    2

    2 1

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 18

    Midpoint Algorithm:Update Equation

    Summary:

    Fk+1 = Fk + h w (yk+1 yk)

    given Fk< 0, yk+1 = yk then Fk+1 = Fk + h

    given Fk 0, yk+1 = yk+1 then Fk+1 = Fk + h w

    F0 = h w/2

    Update Equation

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 19

    Midpoint Algorithm

    int h = by-ay;

    int w = bx-ax;

    float F = h-w/2;

    int y = ay;

    for (int x=ax; x

  • 20

    Bresenhams Algorithm(Improved Midpoint Algorithm)

    int h = by-ay;

    int w = bx-ax;

    int F = 2*h-w;

    int y = ay;

    for (int x=ax; x

  • Bresenhams Line Algorithm

    An accurate, efficient raster line drawing algorithm developed by Bresenham, scan converts lines using only incremental integer calculations that can be adapted to display circles and other curves.

    Keeping in mind the symmetry property of lines, lets derive a more efficient way of drawing a line.

    Starting from the left end point (x0,y0) of a given line , we step to each successive column (x position) and plot the pixel whose scan-line y value closest to the line path

    Assuming we have determined that the pixel at (xk,yk) is to be displayed, we next need to decide which pixel to plot in column xk+1.

    1/21/2011 21Gaurav Raj, Lovely professional University,

    Punjab

  • 1/21/2011 22Gaurav Raj, Lovely professional University,

    Punjab

  • Bresenham Line Algorithm (cont)

    The difference between these 2 separations is

    A decision parameter pk for the kth step in the line

    algorithm can be obtained by rearranging above equation so that it involves only integer calculations

    Choices are(xk +1, yk) and (xk+1, yK+1)

    d1 = y yk = m(xk + 1) + b ykd2 = (yk + 1) y = yk + 1- m(xk + 1) b

    d1-d2 = 2m(xk + 1) 2 yk + 2b 1

    1/21/2011 23Gaurav Raj, Lovely professional University,

    Punjab

  • Bresenhams Line Algorithm

    Define

    Pk = x ( d1-d2) = 2yxk-2 xyk + c

    The sign of Pk is the same as the sign of d1-d2, since x > 0.

    Parameter c is a constant and has the value 2y + x(2b-1)

    (independent of pixel position)

    If pixel at yk is closer to line-path than pixel at yk +1

    (i.e, if d1 < d2) then pk is negative. We plot lower pixel in such a case. Otherwise , upper pixel will be plotted.

    1/21/2011 24Gaurav Raj, Lovely professional University,

    Punjab

  • Bresenhams algorithm (cont)

    At step k + 1, the decision parameter can be evaluated as,

    pk+1 = 2yxk+1 - 2xyk+1 + c

    Taking the difference of pk+ 1 and pk we get the following.

    pk+1 pk = 2y(xk+1- xk)-2x(yk+1 yk)

    But, xk+1 = xk +1, so that

    pk+1 = pk + 2y - 2 x(yk+1 yk)

    Where the term yk+1-yk is either 0 or 1, depending on the sign of parameter pk

    1/21/2011 25Gaurav Raj, Lovely professional University,

    Punjab

  • Bresenhams Line Algorithm

    The first parameter p0 is directly computed

    p0 = 2 yxk - 2 xyk + c = 2 yxk 2 y + x (2b-1)

    Since (x0,y0) satisfies the line equation , we also have

    y0 = y/ x * x0 + b

    Combining the above 2 equations , we will have

    p0 = 2y x

    The constants 2y and 2y-2x are calculated once for each time to be scan converted

    1/21/2011 26Gaurav Raj, Lovely professional University,

    Punjab

  • Bresenhams Line Algorithm

    So, the arithmetic involves only integer addition and subtraction of 2 constants

    Input the two end points and store the left end point in (x0,y0)

    Load (x0,y0) into the frame buffer (plot the first point)

    Calculate the constants x, y, 2y and 2y-2x and obtain the

    starting value for the decision parameter as

    p0 = 2y- x

    1/21/2011 27Gaurav Raj, Lovely professional University,

    Punjab

  • Bresenhams Line Algorithm

    At each xk along the line, starting at k=0, perform the following test:

    If pk < 0 , the next point is (xk+1, yk) and

    pk+1 = pk + 2y

    Repeat step 4 (above step) x times

    Otherwise

    Point to plot is (xk+1, yk+1)

    pk+1 = pk + 2y - 2x

    1/21/2011 28Gaurav Raj, Lovely professional University,

    Punjab

  • 29

    To determine the closest pixel position to the specified circle path at each step.

    For given radius r and screen center position (xc, yc), calculate pixel positions around a circle path centered at the coodinate origin (0,0).

    Then, move each calculated position (x, y) to its proper screen position by adding xc to x and ycto y.

    Along the circle section from x=0 to x=y in the first quadrant, the gradient varies from 0 to -1.

    Midpoint Circle Drawing Algorithm

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 30

    Midpoint Circle Drawing Algorithm 8 segments of octants for a circle:

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 31

    Midpoint Circle Drawing Algorithm

    Circle function: fcircle (x,y) = x2 + y2 r2

    > 0, (x,y) outside the circle

    < 0, (x,y) inside the circle

    = 0, (x,y) is on the circle boundary{fcircle (x,y) =

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 32

    Midpoint Circle Drawing Algorithm

    yk

    yk-1

    midpoint

    Next pixel = (xk+1, yk)

    Fk < 0

    yk+1 = yk

    yk

    yk-1

    midpoint

    Next pixel = (xk+1, yk-1)

    Fk >= 0

    yk+1 = yk - 1

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 33

    Midpoint Circle Drawing AlgorithmWe know xk+1 = xk+1,

    Fk = F(xk+1, yk- )

    Fk = (xk +1)2 + (yk - )

    2 - r2 -------- (1)

    Fk+1 = F(xk+1+1, yk+1 - )

    Fk+1 = (xk +2)2 + (yk+1 - )

    2 - r2 -------- (2)

    (2) (1)

    Fk+1 = Fk + 2(xk+1) + (y2k+1 y

    2k) - (yk+1 yk) + 1

    If Fk < 0, Fk+1 = Fk + 2xk+1+1

    If Fk >= 0, Fk+1 = Fk + 2xk+1+1 2yk+1

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 34

    Midpoint Circle Drawing Algorithm

    For the initial point, (x0 , y0) = (0, r)

    f0 = fcircle (1, r- )

    = 1 + (r- )2 r2

    = 5 r4

    1 r

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 35

    Midpoint Circle Drawing AlgorithmExample:

    Given a circle radius = 10, determine the circle octant in the first octant from x=0 to x=y.

    Solution:

    f0 = 5 r4

    = 5 104

    = -8.75

    9

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 36

    Midpoint Circle Drawing Algorithm

    Initial (x0, y0) = (1,10)Decision parameters are: 2x0 = 2, 2y0 = 20

    k Fk x y 2xk+1 2yk+1

    0 -9 1 10 2 20

    1 -9+2+1=-6 2 10 4 20

    2 -6+4+1=-1 3 10 6 20

    3 -1+6+1=6 4 9 8 18

    4 6+8+1-18=-3 5 9 10 18

    5 -3+10+1=8 6 8 12 16

    6 8+12+1-16=5 7 7 14 14

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 37

    Midpoint Circle Drawing Algorithmvoid circleMidpoint(int xCenter, int yCenter, int radius)

    {

    int x = 0;

    Int y = radius;

    int f = 1 radius;

    circlePlotPoints(xCenter, yCenter, x, y);

    while (x < y) {

    x++;

    if (f < 0)

    f += 2*x + 1;

    else {

    y--;

    f += 2*(x-y)+1;

    }

    circlePlotPoints(xCenter, yCenter, x, y);

    }

    }1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 38

    Midpoint Circle Drawing Algorithm

    void circlePlotPoints( int xCenter, int yCenter,

    int x, int y)

    {

    setPixel (xCenter + x, yCenter + y);

    setPixel (xCenter x, yCenter + y);

    setPixel (xCenter + x, yCenter y);

    setPixel (xCenter x, yCenter y);

    setPixel (xCenter + y, yCenter + x);

    setPixel (xCenter y, yCenter + x);

    setPixel (xCenter + y, yCenter x);

    setPixel (xCenter y, yCenter x);

    }

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • Ellipse Drawing

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab39

    Y

    Xa-a

    -b

    b

    Equation of ellipse :

    F(X,Y) = b2X2 +a2Y2 a2b2 = 0

    Length of major axis: 2a and 2b

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab40

    Slpoe = -1R1

    R2

    We need to obtain points on the contour where the slope of the curve

    is -1.

    This help to demarcate region R1 and R2.

    Choice of pixels in Region R1 is between E and SE, Where in R2 , it

    is S and SE.

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab41

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab42

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab43

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab44

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab45

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab46

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab47

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab48

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab49

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab50

    x0 and y0 will be the accumulative results from region I at the boundary.

    It is not necessary to calculate them from values of a and b.

    where PkI is the accumulative result from region I at the boundary.

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab51

    The algorithm described above shows how to obtain the pixel coordinates in

    the first quarter only.

    The ellipse centre is assumed to be at the origin.

    In actual implementation, the pixel coordinates in other quarters can be

    simply obtained by use of the symmetric characteristics of an ellipse.

    For a pixel (x, y) in the first quarter, the corresponding pixels in other three

    quarters are (x, y), (x, y) and (x, y) respectively.

    If the centre is at (xC, yC), all calculated coordinate (x, y) should be adjusted

    by adding the offset (xC, yC). For easy implementation, a function

    PlotEllipse() is defined as follows:

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab52

    The function to draw an ellipse is described in the

    following pseudo-codes:

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab53

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab54

  • Conic Sections

    In general, we can describe a conic section (or conic) with the second-degree equation:

    where values for parameters A, B, C, D, E, and F determine the kind of curve we are to display. Give11 this set of coefficients, we can determine the particular conic that will be generated by evaluating the discriminant B2 - 4AC:

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab55

  • 1/21/2011Gaurav Raj, Lovely professional University,

    Punjab56

    we get the circle equation when

    A = B = 1, C = 0, D = -2xc, E = -2yc,

    and F = xc2 + yc

    2 - r2.

  • 57

    Anti-aliasing

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

    Polynomials and Spline Curves

    A polynomial function of nth degree in x is defined as

    where n is a nonnegative integer and the a, are constants, with an 0. We

    get a quadratic

    when n = 2; a cubic polynomial

    when n = 3; a quartic

    when n = 4; and so forth.

    And we have a straight line when n = 1.

    Polynomials are useful in a number of graphics applications, including the

    design of object shapes, the specification of animation paths, and the

    graphing of data trends in a discrete set of data points.

  • 58

    Anti-aliasingAnti-aliasing is a technique used to diminish the jagged edges of an image or a line, so that the line appears to be smoother; by changing the pixels around the edges to intermediate colors or gray scales.

    E.g. Anti-aliasing disabled:

    E.g. Anti-aliasing enabled:

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 59

    Anti-aliasing (OpenGL)

    Anti-aliasing disabled Anti-aliasing enabled

    Setting anti-aliasing option for lines:glEnable (GL_LINE_SMOOTH);

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 60

    Fill Area Algorithms

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 61

    Fill Area Algorithms Fill-Area algorithms are used to fill the

    interior of a polygonal shape.

    Many algorithms perform fill operations by first identifying the interior points, given the polygon boundary.

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 62

    The basic filling algorithm is commonly used in interactive graphics packages, where the user specifies an interior point of the region to be filled.

    Basic Filling Algorithm

    4-connected pixels

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 63

    [1] Set the user specified point.

    [2] Store the four neighboring pixels in a stack.

    [3] Remove a pixel from the stack.

    [4] If the pixel is not set,

    - Set the pixel

    - Push its four neighboring pixels into the stack

    [5] Go to step 3

    [6] Repeat till the stack is empty.

    Basic Filling Algorithm

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 64

    void fill(int x, int y) {

    if(getPixel(x,y)==0){

    setPixel(x,y);

    fill(x+1,y);

    fill(x-1,y);

    fill(x,y+1);

    fill(x,y-1);

    }

    }

    Basic Filling Algorithm (Code)

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 65

    Requires an interior point.

    Involves considerable amount of stack operations.

    The boundary has to be closed.

    Not suitable for self-intersectingpolygons

    Basic Filling Algorithm: Conditions

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 66

    Boundary Fill Algorithm

    For filling a region with a singleboundary color.

    Condition for setting pixels: Color is not the same as border color Color is not the same as fill color

    Flood Fill Algorithm

    For filling a region with multipleboundary colors.

    Condition for setting pixels: Color is same as the old interior color

    Types of Basic Filling Algorithms

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 67

    void boundaryFill(int x, int y,

    int fillColor, int borderColor)

    {

    getPixel(x, y, color);

    if ((color != borderColor)

    && (color != fillColor)) {

    setPixel(x,y);

    boundaryFill(x+1,y,fillColor,borderColor);

    boundaryFill(x-1,y,fillColor,borderColor);

    boundaryFill(x,y+1,fillColor,borderColor);

    boundaryFill(x,y-1,fillColor,borderColor);

    }

    }

    Boundary Fill Algorithm (Code)

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

  • 68

    void floodFill(int x, int y,

    int fillColor, int oldColor)

    {

    getPixel(x, y, color);

    if (color == oldColor)

    {

    setPixel(x,y);

    floodFill(x+1, y, fillColor, oldColor);

    floodFill(x-1, y, fillColor, oldColor);

    floodFill(x, y+1, fillColor, oldColor);

    floodFill(x, y-1, fillColor, oldColor);

    }

    }

    Flood Fill Algorithm (Code)

    1/21/2011Gaurav Raj, Lovely professional University,

    Punjab

Recommended

View more >