UNIT I - 2D PRIMITIVES Line, Circle and Ellipse drawing ... –Computer Graphics Unit - I 1 UNIT I - 2D PRIMITIVES Output primitives – Line, Circle and Ellipse drawing algorithms ... Output primitives ...

  • Published on
    11-Mar-2018

  • View
    215

  • Download
    2

Transcript

  • CS2401 Computer Graphics Unit - I

    1

    UNIT I - 2D PRIMITIVES

    Output primitives Line, Circle and Ellipse drawing algorithms - Attributes of

    output primitives Two dimensional Geometric transformation - Two dimensional

    viewing Line, Polygon, Curve and Text clipping algorithms

    Introduction

    A picture is completely specified by the set of intensities for the pixel positions in the

    display. Shapes and colors of the objects can be described internally with pixel arrays

    into the frame buffer or with the set of the basic geometric structure such as straight

    line segments and polygon color areas. To describe structure of basic object is referred to

    as output primitives.

    Each output primitive is specified with input co-ordinate data and other information about

    the way that objects is to be displayed. Additional output primitives that can be used to

    constant a picture include circles and other conic sections, quadric surfaces, Spline curves

    and surfaces, polygon floor areas and character string.

    Points and Lines

    Point plotting is accomplished by converting a single coordinate position furnished by

    an application program into appropriate operations for the output device. With a CRT

    monitor, for example, the electron beam is turned on to illuminate the screen phosphor at

    the selected location

    Line drawing is accomplished by calculating intermediate positions along the line path

    between two specified end points positions. An output device is then directed to fill in

    these positions between the end points

    Digital devices display a straight line segment by plotting discrete points between the two

    end points. Discrete coordinate positions along the line path are calculated from the

    equation of the line. For a raster video display, the line color (intensity) is then loaded

    into the frame buffer at the corresponding pixel coordinates. Reading from the frame

    buffer, the video controller then plots the screen pixels.

    Pixel positions are referenced according to scan-line number and column number (pixel

    position across a scan line). Scan lines are numbered consecutively from 0, starting at the

    bottom of the screen; and pixel columns are numbered from 0, left to right across each

    scan line

  • CS2401 Computer Graphics Unit - I

    2

    Figure : Pixel Postions reference by scan line number and column number

    To load an intensity value into the frame buffer at a position corresponding to column x

    along scan line y,

    setpixel (x, y)

    To retrieve the current frame buffer intensity setting for a specified location we use a low

    level function

    getpixel (x, y)

    Line Drawing Algorithms

    Digital Differential Analyzer (DDA) Algorithm

    Bresenhams Line Algorithm

    Parallel Line Algorithm

    The Cartesian slope-intercept equation for a straight line is

    y = m . x + b (1)

    Where m as slope of the line and b as the y intercept

    Given that the two endpoints of a line segment are specified at positions (x1,y1) and

    (x2,y2) as in figure we can determine the values for the slope m and y intercept b with the

    following calculations

  • CS2401 Computer Graphics Unit - I

    3

    Figure : Line Path between endpoint positions (x1,y1) and (x2,y2)

    m = y / x = y2-y1 / x2 - x1 (2)

    b= y1 - m . x1 (3)

    For any given x interval x along a line, we can compute the corresponding y interval

    y

    y= m x (4)

    We can obtain the x interval x corresponding to a specified y as

    x = y/m (5)

    For lines with slope magnitudes |m| < 1, x can be set proportional to a small

    horizontal deflection voltage and the corresponding vertical deflection is then set

    proportional to y as calculated from Eq (4).

    For lines whose slopes have magnitudes |m | >1 , y can be set proportional to a small

    vertical deflection voltage with the corresponding horizontal deflection voltage set

    proportional to x, calculated from Eq (5)

    For lines with m = 1, x = y and the horizontal and vertical deflections voltage

    are equal.

    Figure : Straight line Segment with five sampling positions along the x axis between x1 and x2

  • CS2401 Computer Graphics Unit - I

    4

    Digital Differential Analyzer (DDA) Algortihm

    The digital differential analyzer (DDA) is a scan-conversion line algorithm based on

    calculation either y or x

    The line at unit intervals in one coordinate and determine corresponding integer values

    nearest the line path for the other coordinate.

    A line with positive slop, if the slope is less than or equal to 1, at unit x intervals (x=1)

    and compute each successive y values as

    yk+1 = yk + m (6)

    Subscript k takes integer values starting from 1 for the first point and increases by 1 until

    the final endpoint is reached. m can be any real number between 0 and 1 and, the

    calculated y values must be rounded to the nearest integer

    For lines with a positive slope greater than 1 we reverse the roles of x and y, (y=1) and

    calculate each succeeding x value as

    xk+1 = xk + (1/m) (7)

    Equation (6) and (7) are based on the assumption that lines are to be processed from the

    left endpoint to the right endpoint.

    If this processing is reversed, x=-1 that the starting endpoint is at the right

    yk+1 = yk m (8)

    When the slope is greater than 1 and y = -1 with

    xk+1 = xk-1(1/m) (9)

    If the absolute value of the slope is less than 1 and the start endpoint is at the left, we set

    x = 1 and calculate y values with Eq. (6)

    When the start endpoint is at the right (for the same slope), we set x = -1 and obtain y

    positions from Eq. (8). Similarly, when the absolute value of a negative slope is greater

    than 1, we use y = -1 and Eq. (9) or we use y = 1 and Eq. (7).

  • CS2401 Computer Graphics Unit - I

    5

    Algorithm

    #define ROUND(a) ((int)(a+0.5))

    void lineDDA (int xa, int ya, int xb, int yb)

    {

    int dx = xb - xa, dy = yb - ya, steps, k;

    float xIncrement, yIncrement, x = xa, y = ya;

    if (abs (dx) > abs (dy) steps = abs (dx) ;

    else steps = abs dy);

    xIncrement = dx / (float) steps;

    yIncrement = dy / (float) steps

    setpixel (ROUND(x), ROUND(y) ) :

    for (k=0; k 6 (false) so, steps=6 5. Calculate xIncrement = dx/steps = 4 / 6 = 0.66 and yIncrement = dy/steps =6/6=1 6. Setpixel(x,y) = Setpixel(0,0) (Starting Pixel Position)

  • CS2401 Computer Graphics Unit - I

    6

    7. Iterate the calculation for xIncrement and yIncrement for steps(6) number of times 8. Tabulation of the each iteration

    Result :

    Advantages of DDA Algorithm

    1. It is the simplest algorithm 2. It is a is a faster method for calculating pixel positions

    Disadvantages of DDA Algorithm

    1. Floating point arithmetic in DDA algorithm is still time-consuming 2. End point accuracy is poor

    Bresenhams Line Algorithm

    An accurate and efficient raster line generating algorithm developed by Bresenham, that

    uses only incremental integer calculations.

    k x Y Plotting points

    (Rounded to Integer)

    0 0+0.66=0.66 0+1=1 (1,1)

    1 0.66+0.66=1.32 1+1=2 (1,2)

    2 1.32+0.66=1.98 2+1=3 (2,3)

    3 1.98+0.66=2.64 3+1=4 (3,4)

    4 2.64+0.66=3.3 4+1=5 (3,5)

    5 3.3+0.66=3.96 5+1=6 (4,6)

  • CS2401 Computer Graphics Unit - I

    7

    In addition, Bresenhams line algorithm can be adapted to display circles and other

    curves.

    To illustrate Bresenham's approach, we- first consider the scan-conversion process for

    lines with positive slope less than 1.

    Pixel positions along a line path are then determined by sampling at unit x intervals.

    Starting from the left endpoint (x0,y0) of a given line, we step to each successive column

    (x position) and plot the pixel whose scan-line y value is closest to the line path.

    To determine the pixel (xk,yk) is to be displayed, next to decide which pixel to plot the

    column xk+1=xk+1.(xk+1,yk) and .(xk+1,yk+1). At sampling position xk+1, we label vertical

    pixel separations from the mathematical line path as d1 and d2. The y coordinate on the

    mathematical line at pixel column position xk+1 is calculated as

    y =m(xk+1)+b (1)

    Then

    d1 = y-yk

    = m(xk+1)+b-yk d2 = (yk+1)-y

    = yk+1-m(xk+1)-b

    To determine which of the two pixel is closest to the line path, efficient test that is based

    on the difference between the two pixel separations

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

    A decision parameter Pk for the kth

    step in the line algorithm can be obtained by

    rearranging equation (2). By substituting m=y/x where x and y are the vertical and

    horizontal separations of the endpoint positions and defining the decision parameter as

    pk = x (d1- d2)

    = 2y xk.-2x. yk + c (3)

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

    Parameter C is constant and has the value 2y + x(2b-1) which is independent of the

    pixel position and will be eliminated in the recursive calculations for Pk.

    If the pixel at yk is closer to the line path than the pixel at yk+1 (d1< d2) than decision

    parameter Pk is negative. In this case, plot the lower pixel, otherwise plot the upper pixel.

    Coordinate changes along the line occur in unit steps in either the x or y directions.

  • CS2401 Computer Graphics Unit - I

    8

    To obtain the values of successive decision parameters using incremental integer

    calculations. At steps k+1, the decision parameter is evaluated from equation (3) as

    Pk+1 = 2y xk+1-2x. yk+1 +c

    Subtracting the equation (3) from the preceding equation

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

    But xk+1= xk+1 so that

    Pk+1 = Pk+ 2y-2x(yk+1 - yk) (4)

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

    This recursive calculation of decision parameter is performed at each integer x position,

    starting at the left coordinate endpoint of the line.

    The first parameter P0 is evaluated from equation at the starting pixel position

    (x0,y0) and with m evaluated as y/x

    P0 = 2y-x (5)

    Bresenhams line drawing for a line with a positive slope less than 1 in the following

    outline of the algorithm.

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

    converted.

    Bresenhams line Drawing Algorithm for |m| < 1

    1. Input the two line endpoints and store the left end point in (x0,y0) 2. load (x0,y0) into frame buffer, ie. Plot the first point. 3. Calculate the constants x, y, 2y and obtain the starting value for the decision

    parameter as P0 = 2y-x

    4. At each xk along the line, starting at k=0 perform the following test If Pk < 0, the next point to plot is(xk+1,yk) and

    Pk+1 = Pk + 2y

    otherwise, the next point to plot is (xk+1,yk+1) and

    Pk+1 = Pk + 2y - 2x

    5. Perform step4 x times.

  • CS2401 Computer Graphics Unit - I

    9

    Implementation of Bresenham Line drawing Algorithm

    void lineBres (int xa,int ya,int xb, int yb)

    {

    int dx = abs( xa xb) , dy = abs (ya - yb);

    int p = 2 * dy dx;

    int twoDy = 2 * dy, twoDyDx = 2 *(dy - dx);

    int x , y, xEnd;

    /* Determine which point to use as start, which as end * /

    if (xa > x b )

    {

    x = xb;

    y = yb;

    xEnd = xa;

    }

    else

    {

    x = xa;

    y = ya;

    xEnd = xb;

    }

    setPixel(x,y);

    while(x

  • CS2401 Computer Graphics Unit - I

    10

    x = 10 y=8

    The initial decision parameter has the value

    p0 = 2y- x = 6

    and the increments for calculating successive decision parameters are

    2y=16 2y-2 x= -4

    We plot the initial point (x0,y0) = (20,10) and determine successive pixel positions along

    the line path from the decision parameter as

    Tabulation

    k pk (xk+1, yK+1)

    0 6 (21,11)

    1 2 (22,12)

    2 -2 (23,12)

    3 14 (24,13)

    4 10 (25,14)

    5 6 (26,15)

    6 2 (27,16)

    7 -2 (28,16)

    8 14 (29,17)

    9 10 (30,18)

    Result

  • CS2401 Computer Graphics Unit - I

    11

    Advantages

    Algorithm is Fast

    Uses only integer calculations

    Disadvantages

    It is meant only for basic line drawing.

    Line Function

    The two dimension line function is Polyline(n,wcPoints) where n is assigned an integer

    value equal to the number of coordinate positions to be input and wcPoints is the array of

    input world-coordinate values for line segment endpoints.

    polyline function is used to define a set of n 1 connected straight line segments

    To display a single straight-line segment we have to set n=2 and list the x and y values of

    the two endpoint coordinates in wcPoints.

    Example : following statements generate 2 connected line segments with endpoints at

    (50, 100), (150, 250), and (250, 100)

    typedef struct myPt{int x, y;};

    myPt wcPoints[3];

    wcPoints[0] .x = 50; wcPoints[0] .y = 100;

    wcPoints[1] .x = 150; wcPoints[1].y = 50;

    wcPoints[2].x = 250; wcPoints[2] .y = 100;

    polyline ( 3 , wcpoints);

    Circle-Generating Algorithms

    General function is available in a graphics library for displaying various kinds of curves,

    including circles and ellipses.

    Properties of a circle

    A circle is defined as a set of points that are all the given distance (xc,yc).

  • CS2401 Computer Graphics Unit - I

    12

    This distance relationship is expressed by the pythagorean theorem in Cartesian

    coordinates as

    (x xc)2 + (y yc)

    2 = r

    2 (1)

    Use above equation to calculate the position of points on a circle circumference by

    stepping along the x axis in unit steps from xc-r to xc+r and calculating the corresponding

    y values at each position as

    y = yc +(- ) (r2 (xc x )

    2)1/2

    (2)

    This is not the best method for generating a circle for the following reason

    Considerable amount of computation

    Spacing between plotted pixels is not uniform

    To eliminate the unequal spacing is to calculate points along the circle boundary using

    polar coordinates r and . Expressing the circle equation in parametric polar from yields

    the pair of equations

    x = xc + rcos y = yc + rsin

    When a display is generated with these equations using a fixed angular step size, a circle

    is plotted with equally spaced points along the circumference. To reduce calculations use

    a large angular separation between points along the circumference and connect the points

    with straight line segments to approximate the circular path.

    Set the angular step size at 1/r. This plots pixel positions that are approximately

    one unit apart. The shape of the circle is similar in each quadrant. To determine the curve

    positions in the first quadrant, to generate he circle section in the second quadrant of the

    xy plane by nothing that the two circle sections are symmetric with respect to the y axis

  • CS2401 Computer Graphics Unit - I

    13

    and circle section in the third and fourth quadrants can be obtained from sections in the

    first and second quadrants by considering symmetry between octants.

    Circle sections in adjacent octants within one quadrant are symmetric with respect to the

    450 line dividing the two octants. Where a point at position (x, y) on a one-eight circle

    sector is mapped into the seven circle points in the other octants of the xy plane.

    To generate all pixel positions around a circle by calculating only the points within the

    sector from x=0 to y=0. the slope of the curve in this octant has an magnitude less than of

    equal to 1.0. at x=0, the circle slope is 0 and at x=y, the slope is -1.0.

    Bresenhams line algorithm for raster displays is adapted to circle generation by setting

    up decision parameters for finding the closest pixel to the circumference at each sampling

    step. Square root evaluations would be required to computer pixel siatances from a

    circular path.

    Bresenhams circle algorithm avoids these square root calculations by comparing

    the squares of the pixel separation distances. It is possible to perform a direct distance

    comparison without a squaring operation.

    In this approach is to test the halfway position between two pixels to determine if

    this midpoint is inside or outside the circle boundary. This method is more easily applied

    to other conics and for an integer circle radius the midpoint approach generates the same

    pixel positions as the Bresenham circle algorithm.

    For a straight line segment the midpoint method is equivalent to the bresenham line

    algorithm. The error involved in locating pixel positions along any conic section using

    the midpoint test is limited to one half the pixel separations.

  • CS2401 Computer Graphics Unit - I

    14

    Midpoint circle Algorithm:

    In the raster line algorithm at unit intervals and determine the closest pixel

    position to the specified circle path at each step for a given radius r and screen center

    position (xc,yc) set up our algorithm to calculate pixel positions around a circle path

    centered at the coordinate position by adding xc to x and yc to y.

    To apply the midpoint method we define a circle function as

    fcircle(x,y) = x2+y

    2-r

    2

    Any point (x,y) on the boundary of the circle with radius r satisfies the equation fcircle

    (x,y)=0. If the point is in the interior of the circle, the circle function is negative. And if

    the point is outside the circle the, circle function is positive

    fcircle (x,y) 0, if (x,y) is outside the circle boundary

    The tests in the above eqn are performed for the midposition sbteween pixels near the

    circle path at each sampling step. The circle function is the decision parameter in the

    midpoint algorithm.

    Midpoint between candidate pixels at sampling position xk+1 along a circular path.

    Fig -1 shows the midpoint between the two candidate pixels at sampling position xk+1. To

    plot the pixel at (xk,yk) next need to determine whether the pixel at position (xk+1,yk) or

    the one at position (xk+1,yk-1) is circular to the circle.

    Our decision parameter is the circle function evaluated at the midpoint between

    these two pixels

    Pk= fcircle (xk+1,yk-1/2)

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

    2-r

    2

    If Pk

  • CS2401 Computer Graphics Unit - I

    15

    Increments for obtaining Pk+1 are either 2xk+1+1 (if Pk is negative) or

    2xk+1+1-2 yk+1.

    Evaluation of the terms 2xk+1 and 2 yk+1 can also be done incrementally as

    2xk+1=2xk+2

    2 yk+1=2 yk-2

    At the Start position (0,r) these two terms have the values 0 and 2r respectively. Each

    successive value for the 2xk+1 term is obtained by adding 2 to the previous value and each

    successive value for the 2yk+1 term is obtained by subtracting 2 from the previous value.

    The initial decision parameter is obtained by evaluating the circle function at the

    start position (x0,y0)=(0,r)

    P0= fcircle (1,r-1/2)

    =1+(r-1/2)2-r

    2

    or

    P0=(5/4)-r

    If the radius r is specified as an integer

    P0=1-r(for r an integer)

    Midpoint circle Algorithm

    1. Input radius r and circle center (xc,yc) and obtain the first point on the circumference

    of the circle centered on the origin as

    (x0,y0) = (0,r)

    2. Calculate the initial value of the decision parameter as P0=(5/4)-r

    3. At each xk position, starting at k=0, perform the following test. If Pk =y.

  • CS2401 Computer Graphics Unit - I

    16

    Example : Midpoint Circle Drawing

    Given a circle radius r=10

    The circle octant in the first quadrant from x=0 to x=y. The initial value of the decision

    parameter is P0=1-r = - 9

    For the circle centered on the coordinate origin, the initial point is (x0,y0)=(0,10) and

    initial increment terms for calculating the decision parameters are

    2x0=0 , 2y0=20

    Successive midpoint decision parameter values and the corresponding coordinate

    positions along the circle path are listed in the following table.

    k pk (xk+1, yk-1) 2xk+1 2yk+1

    0 -9 (1,10) 2 20

    1 -6 (2,10) 4 20

    2 -1 (3,10) 6 20

    3 6 (4,9) 8 18

    4 -3 (5,9) 10 18

    5 8 (6,8) 12 16

    6 5 (7,7) 14 14

  • CS2401 Computer Graphics Unit - I

    17

    Implementation of Midpoint Circle Algorithm

    void circleMidpoint (int xCenter, int yCenter, int radius)

    {

    int x = 0;

    int y = radius;

    int p = 1 - radius;

    void circlePlotPoints (int, int, int, int);

    /* Plot first set of points */

    circlePlotPoints (xCenter, yCenter, x, y);

    while (x < y)

    {

    x++ ;

    if (p < 0)

    p +=2*x +1;

    else

    {

    y--;

    p +=2* (x - Y) + 1;

    }

    circlePlotPoints(xCenter, yCenter, x, y)

    }

    }

    void circlePlotPolnts (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 t y , yCenter - x);

    setpixel (xCenter - y , yCenter - x);

    }

    Ellipse-Generating Algorithms

    An ellipse is an elongated circle. Therefore, elliptical curves can be generated by

    modifying circle-drawing procedures to take into account the different dimensions of an

    ellipse along the major and minor axes.

  • CS2401 Computer Graphics Unit - I

    18

    Properties of ellipses

    An ellipse can be given in terms of the distances from any point on the ellipse to two

    fixed positions called the foci of the ellipse. The sum of these two distances is the same

    values for all points on the ellipse.

    If the distances to the two focus positions from any point p=(x,y) on the ellipse are

    labeled d1 and d2, then the general equation of an ellipse can be stated as

    d1+d2=constant

    Expressing distances d1 and d2 in terms of the focal coordinates F1=(x1,y2) and

    F2=(x2,y2)

    sqrt((x-x1)2+(y-y1)

    2)+sqrt((x-x2)

    2+(y-y2)

    2)=constant

    By squaring this equation isolating the remaining radical and squaring again. The

    general ellipse equation in the form

    Ax2+By

    2+Cxy+Dx+Ey+F=0

    The coefficients A,B,C,D,E, and F are evaluated in terms of the focal coordinates and the

    dimensions of the major and minor axes of the ellipse.

    The major axis is the straight line segment extending from one side of the ellipse

    to the other through the foci. The minor axis spans the shorter dimension of the ellipse,

    perpendicularly bisecting the major axis at the halfway position (ellipse center) between

    the two foci.

    An interactive method for specifying an ellipse in an arbitrary orientation is to

    input the two foci and a point on the ellipse boundary.

    Ellipse equations are simplified if the major and minor axes are oriented to align

    with the coordinate axes. The major and minor axes oriented parallel to the x and y axes

    parameter rx for this example labels the semi major axis and parameter ry labels the semi

    minor axis

  • CS2401 Computer Graphics Unit - I

    19

    ((x-xc)/rx)2+((y-yc)/ry)

    2=1

    Using polar coordinates r and , to describe the ellipse in Standard position with

    the parametric equations

    x=xc+rxcos

    y=yc+rxsin

    Angle called the eccentric angle of the ellipse is measured around the perimeter of a

    bounding circle.

    We must calculate pixel positions along the elliptical arc throughout one quadrant, and

    then we obtain positions in the remaining three quadrants by symmetry

    Midpoint ellipse Algorithm

    The midpoint ellipse method is applied throughout the first quadrant in two parts.

    The below figure show the division of the first quadrant according to the slope of an

    ellipse with rx

  • CS2401 Computer Graphics Unit - I

    20

    In the x direction where the slope of the curve has a magnitude less than 1 and unit steps

    in the y direction where the slope has a magnitude greater than 1.

    Region 1 and 2 can be processed in various ways

    1. Start at position (0,ry) and step clockwise along the elliptical path in the first

    quadrant shifting from unit steps in x to unit steps in y when the slope becomes less than

    -1

    2. Start at (rx,0) and select points in a counter clockwise order.

    2.1 Shifting from unit steps in y to unit steps in x when the slope becomes

    greater than -1.0

    2.2 Using parallel processors calculate pixel positions in the two regions

    simultaneously

    3. Start at (0,ry)

    step along the ellipse path in clockwise order throughout the first quadrant

    ellipse function (xc,yc)=(0,0)

    fellipse (x,y)=ry2x

    2+rx

    2y

    2 rx

    2 ry

    2

    which has the following properties:

    fellipse (x,y) 0, if(x,y) is outside the ellipse boundary

    Thus, the ellipse function fellipse (x,y) serves as the decision parameter in the

    midpoint algorithm.

    Starting at (0,ry):

    Unit steps in the x direction until to reach the boundary between region 1 and

    region 2. Then switch to unit steps in the y direction over the remainder of the curve in

    the first quadrant.

  • CS2401 Computer Graphics Unit - I

    21

    At each step to test the value of the slope of the curve. The ellipse slope is

    calculated

    dy/dx= -(2ry2x/2rx

    2y)

    At the boundary between region 1 and region 2

    dy/dx = -1.0 and 2ry2x=2rx

    2y

    to more out of region 1 whenever

    2ry2x>=2rx

    2y

    The following figure shows the midpoint between two candidate pixels at sampling

    position xk+1 in the first region.

    To determine the next position along the ellipse path by evaluating the decision

    parameter at this mid point

    P1k = fellipse (xk+1,yk-1/2)

    = ry2 (xk+1)

    2 + rx

    2 (yk-1/2)

    2 rx

    2 ry

    2

    if P1k

  • CS2401 Computer Graphics Unit - I

    22

    p1k+1 = fellipse(xk+1 +1,yk+1 - )

    =ry2[(xk +1) + 1]

    2 + rx

    2 (yk+1 -)

    2 - rx

    2 ry

    2

    Or

    p1k+1 = p1k +2 ry2(xk +1) + ry

    2 + rx

    2 [(yk+1 -)

    2 - (yk -)

    2]

    Where yk+1 is yk or yk-1 depending on the sign of P1k.

    Decision parameters are incremented by the following amounts

    increment = { 2 ry2(xk +1) + ry

    2 if p1k

  • CS2401 Computer Graphics Unit - I

    23

    Or

    p10 = ry2 - rx

    2 ry

    + rx

    2

    over region 2, we sample at unit steps in the negative y direction and the midpoint is now

    taken between horizontal pixels at each step. For this region, the decision parameter is

    evaluated as

    p2k = fellipse(xk + ,yk - 1)

    = ry2

    (xk + )2 + rx

    2 (yk - 1)

    2 - rx

    2 ry

    2

    1. If P2k >0, the mid point position is outside the ellipse boundary, and select the

    pixel at xk.

    2. If P2k

  • CS2401 Computer Graphics Unit - I

    24

    (x0,y0) = (0,ry)

    2. Calculate the initial value of the decision parameter in region 1 as P10=ry

    2-rx

    2ry +(1/4)rx

    2

    3. At each xk position in region1 starting at k=0 perform the following test. If P1k=2rx

    2 y

    4. Calculate the initial value of the decision parameter in region 2 using the last point (x0,y0) is the last position calculated in region 1.

    p20 = ry2(x0+1/2)

    2+rx

    2(yo-1)

    2 rx

    2ry

    2

    5. At each position yk in region 2, starting at k=0 perform the following test, If p2k>0 the next point along the ellipse centered on (0,0) is (xk,yk-1) and

    p2k+1 = p2k 2rx2yk+1+rx

    2

    Otherwise the next point along the ellipse is (xk+1,yk-1) and

    p2k+1 = p2k + 2ry2xk+1 2rxx

    2yk+1 + rx

    2

    Using the same incremental calculations for x any y as in region 1.

    6. Determine symmetry points in the other three quadrants. 7. Move each calculate pixel position (x,y) onto the elliptical path centered on

    (xc,yc) and plot the coordinate values

    x=x+xc, y=y+yc

    8. Repeat the steps for region1 unit 2ry2x>=2rx

    2y

  • CS2401 Computer Graphics Unit - I

    25

    Example : Mid point ellipse drawing

    Input ellipse parameters rx=8 and ry=6 the mid point ellipse algorithm by

    determining raster position along the ellipse path is the first quadrant. Initial

    values and increments for the decision parameter calculations are

    2ry2 x=0 (with increment 2ry

    2=72 )

    2rx2 y=2rx

    2 ry (with increment -2rx

    2= -128 )

    For region 1 the initial point for the ellipse centered on the origin is (x0,y0) =

    (0,6) and the initial decision parameter value is

    p10=ry2-rx

    2ry

    2+1/4rx

    2=-332

    Successive midpoint decision parameter values and the pixel positions along the

    ellipse are listed in the following table.

    k p1k xk+1,yk+1 2ry2xk+1 2rx

    2yk+1

    0 -332 (1,6) 72 768

    1 -224 (2,6) 144 768

    2 -44 (3,6) 216 768

    3 208 (4,5) 288 640

    4 -108 (5,5) 360 640

    5 288 (6,4) 432 512

    6 244 (7,3) 504 384

    Move out of region 1, 2ry2x >2rx2y .

    For a region 2 the initial point is (x0,y0)=(7,3) and the initial decision parameter

    is

    p20 = fellipse(7+1/2,2) = -151

    The remaining positions along the ellipse path in the first quadrant are then

    calculated as

    k P2k xk+1,yk+1 2ry2xk+1 2rx

    2yk+1

    0 -151 (8,2) 576 256

    1 233 (8,1) 576 128

    2 745 (8,0) - -

  • CS2401 Computer Graphics Unit - I

    26

    Implementation of Midpoint Ellipse drawing

    #define Round(a) ((int)(a+0.5))

    void ellipseMidpoint (int xCenter, int yCenter, int Rx, int Ry)

    {

    int Rx2=Rx*Rx;

    int Ry2=Ry*Ry;

    int twoRx2 = 2*Rx2;

    int twoRy2 = 2*Ry2;

    int p;

    int x = 0;

    int y = Ry;

    int px = 0;

    int py = twoRx2* y;

    void ellipsePlotPoints ( int , int , int , int ) ;

    /* Plot the first set of points */

    ellipsePlotPoints (xcenter, yCenter, x,y ) ;

    / * Region 1 */

    p = ROUND(Ry2 - (Rx2* Ry) + (0.25*Rx2));

    while (px < py)

    {

    x++;

    px += twoRy2;

    i f (p < 0)

    p += Ry2 + px;

    else

    {

    y - - ;

    py -= twoRx2;

    p += Ry2 + px - py;

    }

    ellipsePlotPoints(xCenter, yCenter,x,y);

    }

    /* Region 2 */

    p = ROUND (Ry2*(x+0.5)*' (x+0.5)+ Rx2*(y- l )* (y- l ) - Rx2*Ry2);

    while (y > 0 )

    {

    y--;

    py -= twoRx2;

    i f (p > 0)

    p += Rx2 - py;

    else

  • CS2401 Computer Graphics Unit - I

    27

    {

    x++;

    px+=twoRy2;

    p+=Rx2-py+px;

    }

    ellipsePlotPoints(xCenter, yCenter,x,y);

    }

    }

    void ellipsePlotPoints(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);

    }

    Attributes of output primitives

    Any parameter that affects the way a primitive is to be displayed is referred to as an

    attribute parameter. Example attribute parameters are color, size etc. A line drawing

    function for example could contain parameter to set color, width and other properties.

    1. Line Attributes 2. Curve Attributes 3. Color and Grayscale Levels 4. Area Fill Attributes 5. Character Attributes 6. Bundled Attributes

  • CS2401 Computer Graphics Unit - I

    28

    Line Attributes

    Basic attributes of a straight line segment are its type, its width, and its color. In some

    graphics packages, lines can also be displayed using selected pen or brush options

    Line Type

    Line Width

    Pen and Brush Options

    Line Color

    Line type

    Possible selection of line type attribute includes solid lines, dashed lines and dotted lines.

    To set line type attributes in a PHIGS application program, a user invokes the function

    setLinetype (lt)

    Where parameter lt is assigned a positive integer value of 1, 2, 3 or 4 to generate lines

    that are solid, dashed, dash dotted respectively. Other values for line type parameter it

    could be used to display variations in dot-dash patterns.

    Line width

    Implementation of line width option depends on the capabilities of the output device to

    set the line width attributes.

    setLinewidthScaleFactor(lw)

    Line width parameter lw is assigned a positive number to indicate the relative width of

    line to be displayed. A value of 1 specifies a standard width line. A user could set lw to a

    value of 0.5 to plot a line whose width is half that of the standard line. Values greater

    than 1 produce lines thicker than the standard.

    Line Cap

    We can adjust the shape of the line ends to give them a better appearance by adding line

    caps.

    There are three types of line cap. They are

    Butt cap

    Round cap

    Projecting square cap

  • CS2401 Computer Graphics Unit - I

    29

    Butt cap obtained by adjusting the end positions of the component parallel lines so that

    the thick line is displayed with square ends that are perpendicular to the line path.

    Round cap obtained by adding a filled semicircle to each butt cap. The circular arcs are

    centered on the line endpoints and have a diameter equal to the line thickness

    Projecting square cap extend the line and add butt caps that are positioned one-half of

    the line width beyond the specified endpoints.

    Three possible methods for smoothly joining two line segments

    Mitter Join

    Round Join

    Bevel Join

    1. A miter join accomplished by extending the outer boundaries of each of the two lines

    until they meet.

    2. A round join is produced by capping the connection between the two segments with a

    circular boundary whose diameter is equal to the width.

    3. A bevel join is generated by displaying the line segment with but caps and filling in tri

    angular gap where the segments meet

  • CS2401 Computer Graphics Unit - I

    30

    Pen and Brush Options

    With some packages, lines can be displayed with pen or brush selections. Options in this

    category include shape, size, and pattern. Some possible pen or brush shapes are given in

    Figure

    Line color

    A poly line routine displays a line in the current color by setting this color value in the

    frame buffer at pixel locations along the line path using the set pixel procedure.

    We set the line color value in PHlGS with the function

    setPolylineColourIndex (lc)

    Nonnegative integer values, corresponding to allowed color choices, are assigned to the

    line color parameter lc

    Example : Various line attribute commands in an applications program is given by the

    following sequence of statements

  • CS2401 Computer Graphics Unit - I

    31

    setLinetype(2);

    setLinewidthScaleFactor(2);

    setPolylineColourIndex (5);

    polyline(n1,wc points1);

    setPolylineColorIindex(6);

    poly line (n2, wc points2);

    This program segment would display two figures, drawn with double-wide dashed lines.

    The first is displayed in a color corresponding to code 5, and the second in color 6.

    Curve attributes

    Parameters for curve attribute are same as those for line segments. Curves displayed with

    varying colors, widths, dot dash patterns and available pen or brush options

    Color and Grayscale Levels

    Various color and intensity-level options can be made available to a user, depending on

    the capabilities and design objectives of a particular system

    In a color raster system, the number of color choices available depends on the amount of

    storage provided per pixel in the frame buffer

    Color-information can be stored in the frame buffer in two ways:

    We can store color codes directly in the frame buffer

    We can put the color codes in a separate table and use pixel values as an index into this table

    With the direct storage scheme, whenever a particular color code is specified in an

    application program, the corresponding binary value is placed in the frame buffer for

    each-component pixel in the output primitives to be displayed in that color.

    A minimum number of colors can be provided in this scheme with 3 bits of storage per

    pixel, as shown in Table

  • CS2401 Computer Graphics Unit - I

    32

    Color tables(Color Lookup Tables) are an alternate means for providing extended color

    capabilities to a user without requiring large frame buffers

    3 bits - 8 choice of color

    6 bits 64 choice of color

    8 bits 256 choice of color

    A user can set color-table entries in a PHIGS applications program with the function

    setColourRepresentation (ws, ci, colorptr)

  • CS2401 Computer Graphics Unit - I

    33

    Parameter ws identifies the workstation output device; parameter ci specifies the color

    index, which is the color-table position number (0 to 255) and parameter colorptr points

    to a trio of RGB color values (r, g, b) each specified in the range from 0 to 1

    Grayscale

    With monitors that have no color capability, color functions can be used in an application

    program to set the shades of gray, or grayscale, for displayed primitives. Numeric values

    over the range from 0 to 1 can be used to specify grayscale levels, which are then

    converted to appropriate binary codes for storage in the raster.

    Intensity = 0.5[min(r,g,b)+max(r,g,b)]

    Area fill Attributes

    Options for filling a defined region include a choice between a solid color or a

    pattern fill and choices for particular colors and patterns

    Fill Styles

    Areas are displayed with three basic fill styles: hollow with a color border, filled with a

    solid color, or filled with a specified pattern or design. A basic fill style is selected in a

    PHIGS program with the function

    setInteriorStyle(fs)

    Values for the fill-style parameter fs include hollow, solid, and pattern. Another value for

    fill style is hatch, which is used to fill an area with selected hatching patterns-parallel

    lines or crossed lines

  • CS2401 Computer Graphics Unit - I

    34

    The color for a solid interior or for a hollow area outline is chosen with where fill color

    parameter fc is set to the desired color code

    setInteriorColourIndex(fc)

    Pattern Fill

    We select fill patterns with setInteriorStyleIndex (pi) where pattern index parameter pi

    specifies a table position

    For example, the following set of statements would fill the area defined in the fillArea

    command with the second pattern type stored in the pattern table:

    SetInteriorStyle( pattern)

    SetInteriorStyleIndex(2);

    Fill area (n, points)

  • CS2401 Computer Graphics Unit - I

    35

    Character Attributes

    The appearance of displayed character is controlled by attributes such as font, size, color

    and orientation. Attributes can be set both for entire character strings (text) and for

    individual characters defined as marker symbols

    Text Attributes

    The choice of font or type face is set of characters with a particular design style as

    courier, Helvetica, times roman, and various symbol groups.

    The characters in a selected font also be displayed with styles. (solid, dotted,

    double) in bold face in italics, and in or sshhaaddooww styles.

    A particular font and associated stvle is selected in a PHIGS program by setting an

    integer code for the text font parameter tf in the function

    setTextFont(tf)

    Control of text color (or intensity) is managed from an application program with

    setTextColourIndex(tc)

    where text color parameter tc specifies an allowable color code.

    Text size can be adjusted without changing the width to height ratio of characters with

    SetCharacterHeight (ch)

    Parameter ch is assigned a real value greater than 0 to set the coordinate height of capital

    letters

    The width only of text can be set with function.

    SetCharacterExpansionFactor(cw)

  • CS2401 Computer Graphics Unit - I

    36

    Where the character width parameter cw is set to a positive real value that scales the body

    width of character

    Spacing between characters is controlled separately with

    setCharacterSpacing(cs)

    where the character-spacing parameter cs can he assigned any real value

    The orientation for a displayed character string is set according to the direction of the

    character up vector

    setCharacterUpVector(upvect)

    Parameter upvect in this function is assigned two values that specify the x and y vector

    components. For example, with upvect = (1, 1), the direction of the up vector is 45o and

    text would be displayed as shown in Figure.

    To arrange character strings vertically or horizontally

    setTextPath (tp)

  • CS2401 Computer Graphics Unit - I

    37

    Where the text path parameter tp can be assigned the value: right, left, up, or down

    Another handy attribute for character strings is alignment. This attribute specifies how

    text is to be positioned with respect to the $tart coordinates. Alignment attributes are set

    with

    setTextAlignment (h,v)

    where parameters h and v control horizontal and vertical alignment. Horizontal alignment

    is set by assigning h a value of left, center, or right. Vertical alignment is set by

    assigning v a value of top, cap, half, base or bottom.

    A precision specification for text display is given with

    setTextPrecision (tpr)

    tpr is assigned one of values string, char or stroke.

    Marker Attributes

    A marker symbol is a single character that can he displayed in different colors and in

    different sizes. Marker attributes are implemented by procedures that load the chosen

    character into the raster at the defined positions with the specified color and size. We

    select a particular character to be the marker symbol with

    setMarkerType(mt)

    where marker type parameter mt is set to an integer code. Typical codes for marker type

    are the integers 1 through 5, specifying, respectively, a dot (.) a vertical cross (+), an

    asterisk (*), a circle (o), and a diagonal cross (X).

  • CS2401 Computer Graphics Unit - I

    38

    We set the marker size with

    setMarkerSizeScaleFactor(ms)

    with parameter marker size ms assigned a positive number. This scaling parameter is

    applied to the nominal size for the particular marker symbol chosen. Values greater than

    1 produce character enlargement; values less than 1 reduce the marker size.

    Marker color is specified with

    setPolymarkerColourIndex(mc)

    A selected color code parameter mc is stored in the current attribute list and used to

    display subsequently specified marker primitives

    Bundled Attributes

    The procedures considered so far each function reference a single attribute that specifies

    exactly how a primitive is to be displayed these specifications are called individual

    attributes.

    A particular set of attributes values for a primitive on each output device is chosen by

    specifying appropriate table index. Attributes specified in this manner are called bundled

    attributes. The choice between a bundled or an unbundled specification is made by setting

    a switch called the aspect source flag for each of these attributes

    setIndividualASF( attributeptr, flagptr)

    where parameter attributer ptr points to a list of attributes and parameter flagptr points to

    the corresponding list of aspect source flags. Each aspect source flag can be assigned a

    value of individual or bundled.

    Bundled line attributes

    Entries in the bundle table for line attributes on a specified workstation are set with the

    function

    setPolylineRepresentation (ws, li, lt, lw, lc)

    Parameter ws is the workstation identifier and line index parameter li defines the bundle

    table position. Parameter lt, lw, tc are then bundled and assigned values to set the line

    type, line width, and line color specifications for designated table index.

  • CS2401 Computer Graphics Unit - I

    39

    Example

    setPolylineRepresentation(1,3,2,0.5,1)

    setPolylineRepresentation (4,3,1,1,7)

    A poly line that is assigned a table index value of 3 would be displayed using

    dashed lines at half thickness in a blue color on work station 1; while on workstation 4,

    this same index generates solid, standard-sized white lines

    Bundle area fill Attributes

    Table entries for bundled area-fill attributes are set with

    setInteriorRepresentation (ws, fi, fs, pi, fc)

    Which defines the attributes list corresponding to fill index fi on workstation ws.

    Parameter fs, pi and fc are assigned values for the fill style pattern index and fill color.

    Bundled Text Attributes

    setTextRepresentation (ws, ti, tf, tp, te, ts, tc)

    bundles values for text font, precision expansion factor size an color in a table position

    for work station ws that is specified by value assigned to text index parameter ti.

    Bundled marker Attributes

    setPolymarkerRepresentation (ws, mi, mt, ms, mc)

    That defines marker type marker scale factor marker color for index mi on

    workstation ws.

    Inquiry functions

    Current settings for attributes and other parameters as workstations types and status in the

    system lists can be retrieved with inquiry functions.

    inquirePolylineIndex ( lastli) and

    inquireInteriorcColourIndex (lastfc)

    Copy the current values for line index and fill color into parameter lastli and lastfc.

  • CS2401 Computer Graphics Unit - I

    40

    Two Dimensional Geometric Transformations

    Changes in orientations, size and shape are accomplished with geometric transformations

    that alter the coordinate description of objects.

    Basic transformation

    Translation T(tx, ty) Translation distances

    Scale S(sx,sy) Scale factors

    Rotation

    R( ) Rotation angle

    Translation

    A translation is applied to an object by representing it along a straight line path

    from one coordinate location to another adding translation distances, tx, ty to original

    coordinate position (x,y) to move the point to a new position (x,y) to

    x = x + tx, y = y + ty

  • CS2401 Computer Graphics Unit - I

    41

    The translation distance point (tx,ty) is called translation vector or shift vector.

    Translation equation can be expressed as single matrix equation by using column vectors

    to represent the coordinate position and the translation vector as

    Moving a polygon from one position to another position with the translation

    vector (-5.5, 3.75)

    Rotations:

    A two-dimensional rotation is applied to an object by repositioning it along a

    circular path on xy plane. To generate a rotation, specify a rotation angle and the

    position (xr,yr) of the rotation point (pivot point) about which the object is to be rotated.

    Positive values for the rotation angle define counter clock wise rotation about

    pivot point. Negative value of angle rotate objects in clock wise direction. The

    transformation can also be described as a rotation about a rotation axis perpendicular to

    xy plane and passes through pivot point

    TPP

    t

    t

    y

    x

    y

    x

    tyy

    txx

    ttT

    yxP

    y

    x

    y

    x

    yx

    '

    '

    '

    '

    '

    ),(

    ),(

  • CS2401 Computer Graphics Unit - I

    42

    Rotation of a point from position (x,y) to position (x,y) through angle relative to

    coordinate origin

    The transformation equations for rotation of a point position P when the pivot point is at

    coordinate origin. In figure r is constant distance of the point positions is the original

    angular of the point from horizontal and is the rotation angle.

    The transformed coordinates in terms of angle and

    x = rcos(+) = rcos cos rsinsin

    y = rsin(+) = rsin cos + rcossin

    The original coordinates of the point in polar coordinates

    x = rcos, y = rsin

    the transformation equation for rotating a point at position (x,y) through an angle about

    origin

    x = xcos ysin

    y = xsin + ycos

    Rotation equation

    P= R . P

    Rotation Matrix

    R = cossin

    sincos

  • CS2401 Computer Graphics Unit - I

    43

    Note : Positive values for the rotation angle define counterclockwise rotations about the

    rotation point and negative values rotate objects in the clockwise.

    Scaling

    A scaling transformation alters the size of an object. This operation can be carried out for

    polygons by multiplying the coordinate values (x,y) to each vertex by scaling factor Sx &

    Sy to produce the transformed coordinates (x,y)

    x= x.Sx y = y.Sy

    scaling factor Sx scales object in x direction while Sy scales in y direction.

    The transformation equation in matrix form

    y

    x

    s

    s

    y

    x

    y

    x

    0

    0

    '

    '

    or

    P = S. P

    Where S is 2 by 2 scaling matrix

    Turning a square (a) Into a rectangle (b) with scaling factors sx = 2 and sy= 1.

    Any positive numeric values are valid for scaling factors sx and sy. Values less than 1

    reduce the size of the objects and values greater than 1 produce an enlarged object.

    y

    x

    y

    x

    cossin

    sincos

    '

    '

  • CS2401 Computer Graphics Unit - I

    44

    There are two types of Scaling. They are

    Uniform scaling

    Non Uniform Scaling

    To get uniform scaling it is necessary to assign same value for sx and sy. Unequal values

    for sx and sy result in a non uniform scaling.

    Matrix Representation and homogeneous Coordinates

    Many graphics applications involve sequences of geometric transformations. An

    animation, for example, might require an object to be translated and rotated at each

    increment of the motion. In order to combine sequence of transformations we have to

    eliminate the matrix addition. To achieve this we have represent matrix as 3 X 3 instead

    of 2 X 2 introducing an additional dummy coordinate h. Here points are specified by

    three numbers instead of two. This coordinate system is called as Homogeneous

    coordinate system and it allows to express transformation equation as matrix

    multiplication

    Cartesian coordinate position (x,y) is represented as homogeneous coordinate

    triple(x,y,h)

    Represent coordinates as (x,y,h) Actual coordinates drawn will be (x/h,y/h)

    For Translation

    PttTP

    y

    x

    t

    t

    y

    x

    yx

    y

    x

    ,'

    1100

    10

    01

    1

    '

    '

    For Scaling

    PssSP

    y

    x

    s

    s

    y

    x

    yx

    y

    x

    ,'

    1100

    00

    00

    1

    '

    '

  • CS2401 Computer Graphics Unit - I

    45

    For rotation

    PRP

    y

    x

    y

    x

    '

    1100

    0cossin

    0sincos

    1

    '

    '

    Composite Transformations

    A composite transformation is a sequence of transformations; one followed by the other.

    we can set up a matrix for any sequence of transformations as a composite

    transformation matrix by calculating the matrix product of the individual

    transformations

    Translation

    If two successive translation vectors (tx1,ty1) and (tx2,ty2) are applied to a coordinate

    position P, the final transformed location P is calculated as

    P=T(tx2,ty2).{T(tx1,ty1).P}

    ={T(tx2,ty2).T(tx1,ty1)}.P

    Where P and P are represented as homogeneous-coordinate column vectors.

    100

    2110

    2101

    100

    110

    101

    .

    100

    210

    201

    tyty

    txtx

    ty

    tx

    ty

    tx

    Or

    T(tx2,ty2).T(tx1,ty1) = T(tx1+tx2,ty1+ty2)

    Which demonstrated the two successive translations are additive.

    Rotations

    Two successive rotations applied to point P produce the transformed position

    P=R(2).{R(1).P}={R(2).R(1)}.P

  • CS2401 Computer Graphics Unit - I

    46

    By multiplying the two rotation matrices, we can verify that two successive rotation are

    additive

    R(2).R(1) = R(1+ 2)

    So that the final rotated coordinates can be calculated with the composite rotation matrix

    as

    P = R(1+ 2).P

    100

    0)12cos()12sin(

    0)12sin()12cos(

    100

    01cos1sin

    01sin1cos

    .

    100

    02cos2sin

    02sin2cos

    Scaling

    Concatenating transformation matrices for two successive scaling operations produces

    the following composite scaling matrix

    100

    01.20

    001.2

    100

    010

    001

    .

    100

    020

    002

    sysy

    sxsx

    sy

    sx

    sy

    sx

    General Pivot-point Rotation

    1. Translate the object so that pivot-position is moved to the coordinate origin

    2. Rotate the object about the coordinate origin

    Translate the object so that the pivot point is returned to its original position

  • CS2401 Computer Graphics Unit - I

    47

    The composite transformation matrix for this sequence is obtain with the concatenation

    Which can also be expressed as T(xr,yr).R().T(-xr,-yr) = R(xr,yr,)

    General fixed point scaling

    Translate object so that the fixed point coincides with the coordinate origin

    Scale the object with respect to the coordinate origin

    Use the inverse translation of step 1 to return the object to its original position

  • CS2401 Computer Graphics Unit - I

    48

    Concatenating the matrices for these three operations produces the required scaling matix

    Can also be expressed as T(xf,yf).S(sx,sy).T(-xf,-yf) = S(xf, yf, sx, sy)

    Note : Transformations can be combined by matrix multiplication

    Implementation of composite transformations

    #include

    #include

    typedef float Matrix3x3 [3][3];

    Matrix3x3 thematrix;

    void matrix3x3SetIdentity (Matrix3x3 m)

    {

    int i,j;

    for (i=0; i

  • CS2401 Computer Graphics Unit - I

    49

    / * Multiplies matrix a times b, putting result in b */

    void matrix3x3PreMultiply (Matrix3x3 a. Matrix3x3 b)

    {

    int r,c:

    Matrix3x3 tmp:

    for (r = 0; r < 3: r++)

    for (c = 0; c < 3; c++)

    tmp[r][c] =a[r][0]*b[0][c]+ a[r][1]*b[l][c] + a[r][2]*b[2][c]:

    for (r = 0: r < 3: r++)

    for Ic = 0; c < 3: c++)

    b[r][c]=- tmp[r][c]:

    }

    void translate2 (int tx, int ty)

    {

    Matrix3x3 m:

    rnatrix3x3SetIdentity (m) :

    m[0][2] = tx;

    m[1][2] = ty:

    matrix3x3PreMultiply (m, theMatrix);

    }

    vold scale2 (float sx. float sy, wcPt2 refpt)

    (

    Matrix3x3 m.

    matrix3x3SetIdentity (m);

    m[0] [0] = sx;

    m[0][2] = (1 - sx)* refpt.x;

    m[l][l] = sy;

    m[10][2] = (1 - sy)* refpt.y;

    matrix3x3PreMultiply (m, theMatrix);

    }

    void rotate2 (float a, wcPt2 refPt)

    {

    Matrix3x3 m;

    matrix3x3SetIdentity (m):

    a = pToRadians (a);

    m[0][0]= cosf (a);

    m[0][1] = -sinf (a) ;

    m[0] [2] = refPt.x * (1 - cosf (a)) + refPt.y sinf (a);

    m[1] [0] = sinf (a);

    m[l][l] = cosf (a];

  • CS2401 Computer Graphics Unit - I

    50

    m[l] [2] = refPt.y * (1 - cosf (a) - refPt.x * sinf ( a ) ;

    matrix3x3PreMultiply (m, theMatrix);

    }

    void transformPoints2 (int npts, wcPt2 *pts)

    {

    int k:

    float tmp ;

    for (k = 0; k< npts: k++)

    {

    tmp = theMatrix[0][0]* pts[k] .x * theMatrix[0][1] * pts[k].y+ theMatrix[0][2];

    pts[k].y = theMatrix[1][0]* pts[k] .x * theMatrix[1][1] * pts[k].y+ theMatrix[1][2];

    pts[k].x =tmp;

    }

    }

    void main (int argc, char **argv)

    {

    wcPt2 pts[3]= { 50.0, 50.0, 150.0, 50.0, 100.0, 150.0};

    wcPt2 refPt ={100.0. 100.0};

    long windowID = openGraphics (*argv,200, 350);

    setbackground (WHITE) ;

    setcolor (BLUE);

    pFillArea(3, pts):

    matrix3x3SetIdentity(theMatrix);

    scale2 (0.5, 0.5, refPt):

    rotate2 (90.0, refPt);

    translate2 (0, 150);

    transformpoints2 ( 3 , pts)

    pFillArea(3.pts);

    sleep (10);

    closeGraphics (windowID);

    }

    Other Transformations

    1. Reflection

    2. Shear

    Reflection

    A reflection is a transformation that produces a mirror image of an object. The mirror

    image for a two-dimensional reflection is generated relative to an axis of reflection by

  • CS2401 Computer Graphics Unit - I

    51

    rotating the object 180o about the reflection axis. We can choose an axis of reflection in

    the xy plane or perpendicular to the xy plane or coordinate origin

    Reflection of an object about the x axis

    Reflection the x axis is accomplished with the transformation matrix

    100

    010

    001

    Reflection of an object about the y axis

    Reflection the y axis is accomplished with the transformation matrix

    100

    010

    001

    Reflection of an object about the coordinate origin

  • CS2401 Computer Graphics Unit - I

    52

    Reflection about origin is accomplished with the transformation matrix

    100

    010

    001

    Reflection axis as the diagonal line y = x

    To obtain transformation matrix for reflection about diagonal y=x the transformation

    sequence is

    1. Clock wise rotation by 450 2. Reflection about x axis 3. counter clock wise by 450

  • CS2401 Computer Graphics Unit - I

    53

    Reflection about the diagonal line y=x is accomplished with the transformation

    matrix

    100

    001

    010

    Reflection axis as the diagonal line y = -x

    To obtain transformation matrix for reflection about diagonal y=-x the transformation

    sequence is

    1. Clock wise rotation by 450 2. Reflection about y axis 3. counter clock wise by 450

    Reflection about the diagonal line y=-x is accomplished with the transformation

    matrix

    100

    001

    010

    Shear

    A Transformation that slants the shape of an object is called the shear transformation.

    Two common shearing transformations are used. One shifts x coordinate values and other

    shift y coordinate values. However in both the cases only one coordinate (x or y)

    changes its coordinates and other preserves its values.

  • CS2401 Computer Graphics Unit - I

    54

    X- Shear

    The x shear preserves the y coordinates, but changes the x values which cause vertical

    lines to tilt right or left as shown in figure

    The Transformations matrix for x-shear is

    100

    010

    01 xsh

    which transforms the coordinates as

    x =x+ xsh .y

    y = y

    Y Shear

    The y shear preserves the x coordinates, but changes the y values which cause horizontal

    lines which slope up or down

    The Transformations matrix for y-shear is

    100

    01

    001

    ysh

    which transforms the coordinates as

    x =x

    y = y+ ysh .x

  • CS2401 Computer Graphics Unit - I

    55

    XY-Shear

    The transformation matrix for xy-shear

    which transforms the coordinates as

    x =x+ xsh .y

    y = y+ ysh .x

    Shearing Relative to other reference line

    We can apply x shear and y shear transformations relative to other reference lines. In x

    shear transformations we can use y reference line and in y shear we can use x reference

    line.

    X shear with y reference line

    We can generate x-direction shears relative to other reference lines with the

    transformation matrix

    100

    010

    .1 refxx yshsh

    which transforms the coordinates as

    x =x+ xsh (y- refy )

    y = y

    Example

    Shx = and yref=-1

    1100

    01

    01

    1

    '

    '

    y

    x

    sh

    sh

    y

    x

    y

    x

  • CS2401 Computer Graphics Unit - I

    56

    Y shear with x reference line

    We can generate y-direction shears relative to other reference lines with the

    transformation matrix

    100

    010

    .1 refxx yshsh

    which transforms the coordinates as

    x =x

    y = shy (x- xref) + y

    Example

    Shy = and xref=-1

  • CS2401 Computer Graphics Unit - I

    57

    Two dimensional viewing

    The viewing pipeline

    A world coordinate area selected for display is called a window. An area on a display

    device to which a window is mapped is called a view port. The window defines what is to

    be viewed the view port defines where it is to be displayed.

    The mapping of a part of a world coordinate scene to device coordinate is referred to as

    viewing transformation. The two dimensional viewing transformation is referred to as

    window to view port transformation of windowing transformation.

    A viewing transformation using standard rectangles for the window and viewport

    The two dimensional viewing transformation pipeline

    The viewing transformation in several steps, as indicated in Fig. First, we

    construct the scene in world coordinates using the output primitives. Next to obtain a

    particular orientation for the window, we can set up a two-dimensional viewing-

    coordinate system in the world coordinate plane, and define a window in the viewing-

    coordinate system.

    The viewing- coordinate reference frame is used to provide a method for setting up

    arbitrary orientations for rectangular windows. Once the viewing reference frame is

    established, we can transform descriptions in world coordinates to viewing coordinates.

    We then define a viewport in normalized coordinates (in the range from 0 to 1) and map

    the viewing-coordinate description of the scene to normalized coordinates.

    At the final step all parts of the picture that lie outside the viewport are clipped, and the

    contents of the viewport are transferred to device coordinates. By changing the position

  • CS2401 Computer Graphics Unit - I

    58

    of the viewport, we can view objects at different positions on the display area of an

    output device.

    Window to view port coordinate transformation:

    A point at position (xw,yw) in a designated window is mapped to viewport coordinates

    (xv,yv) so that relative positions in the two areas are the same. The figure illustrates the

    window to view port mapping.

    A point at position (xw,yw) in the window is mapped into position (xv,yv) in the associated

    view port. To maintain the same relative placement in view port as in window

  • CS2401 Computer Graphics Unit - I

    59

    solving these expressions for view port position (xv,yv)

    where scaling factors are

    sx = xvmax xvmin sy = yvmax - yvmin

    xwmax xwmin ywmax - ywmin

    The conversion is performed with the following sequence of transformations.

    1. Perform a scaling transformation using point position of (xw min, yw min) that

    scales the window area to the size of view port.

    2. Translate the scaled window area to the position of view port. Relative

    proportions of objects are maintained if scaling factor are the same(Sx=Sy).

    Otherwise world objects will be stretched or contracted in either the x or y direction when

    displayed on output device. For normalized coordinates, object descriptions are mapped

    to various display devices.

    Any number of output devices can be open in particular application and another

    window view port transformation can be performed for each open output device. This

    mapping called the work station transformation is accomplished by selecting a window

    area in normalized apace and a view port are in coordinates of display device.

    Mapping selected parts of a scene in normalized coordinate to different video

    monitors with work station transformation.

    minmax

    min

    minmax

    min

    minmax

    min

    minmax

    min

    ywyw

    ywyw=

    yvyv

    yvyv

    xwxw

    xwxw=

    xvxv

    xvxv

    minmax

    minmaxminmin

    minmax

    minmaxminmin

    ywyw

    yvyvywyw+yv=yv

    xwxw

    xvxvxwxw+xv=xv

  • CS2401 Computer Graphics Unit - I

    60

    Two Dimensional viewing functions

    Viewing reference system in a PHIGS application program has following function.

    evaluateViewOrientationMatrix(x0,y0,xv,yv,error, viewMatrix)

    where x0,y0 are coordinate of viewing origin and parameter xv, yv are the world

    coordinate positions for view up vector.An integer error code is generated if the input

    parameters are in error otherwise the view matrix for world-to-viewing transformation is

    calculated. Any number of viewing transformation matrices can be defined in an

    application.

    To set up elements of window to view port mapping

    evaluateViewMappingMatrix (xwmin, xwmax, ywmin, ywmax, xvmin, xvmax, yvmin,

    yvmax, error, viewMappingMatrix)

    Here window limits in viewing coordinates are chosen with parameters xwmin, xwmax,

    ywmin, ywmax and the viewport limits are set with normalized coordinate positions

    xvmin, xvmax, yvmin, yvmax.

  • CS2401 Computer Graphics Unit - I

    61

    The combinations of viewing and window view port mapping for various workstations in

    a viewing table with

    setViewRepresentation(ws,viewIndex,viewMatrix,viewMappingMatrix,

    xclipmin, xclipmax, yclipmin, yclipmax, clipxy)

    Where parameter ws designates the output device and parameter view index sets an

    integer identifier for this window-view port point. The matrices viewMatrix and

    viewMappingMatrix can be concatenated and referenced by viewIndex.

    setViewIndex(viewIndex)

    selects a particular set of options from the viewing table.

    At the final stage we apply a workstation transformation by selecting a work station

    window viewport pair.

    setWorkstationWindow (ws, xwsWindmin, xwsWindmax,

    ywsWindmin, ywsWindmax)

    setWorkstationViewport (ws, xwsVPortmin, xwsVPortmax,

    ywsVPortmin, ywsVPortmax)

    where was gives the workstation number. Window-coordinate extents are specified in the

    range from 0 to 1 and viewport limits are in integer device coordinates.

    Clipping operation

    Any procedure that identifies those portions of a picture that are inside or outside of a

    specified region of space is referred to as clipping algorithm or clipping. The region

    against which an object is to be clipped is called clip window.

    Algorithm for clipping primitive types:

    Point clipping

    Line clipping (Straight-line segment)

    Area clipping

    Curve clipping

    Text clipping

    Line and polygon clipping routines are standard components of graphics packages.

  • CS2401 Computer Graphics Unit - I

    62

    Point Clipping

    Clip window is a rectangle in standard position. A point P=(x,y) for display, if following

    inequalities are satisfied:

    xwmin

  • CS2401 Computer Graphics Unit - I

    63

    All other lines cross one or more clipping boundaries. For a line segment with end points

    (x1,y1) and (x2,y2) one or both end points outside clipping rectangle, the parametric

    representation

    could be used to determine values of u for an intersection with the clipping boundary

    coordinates. If the value of u for an intersection with a rectangle boundary edge is outside

    the range of 0 to 1, the line does not enter the interior of the window at that boundary. If

    the value of u is within the range from 0 to 1, the line segment does indeed cross into the

    clipping area. This method can be applied to each clipping boundary edge in to

    determined whether any part of line segment is to displayed.

    Cohen-Sutherland Line Clipping

    This is one of the oldest and most popular line-clipping procedures. The method

    speeds up the processing of line segments by performing initial tests that reduce the

    number of intersections that must be calculated.

    Every line endpoint in a picture is assigned a four digit binary code called a region

    code that identifies the location of the point relative to the boundaries of the clipping

    rectangle.

    Binary region codes assigned to line end points according to relative position with

    respect to the clipping rectangle.

    10121

    121

    u,yyu+y=y

    ,xxu+x=x

  • CS2401 Computer Graphics Unit - I

    64

    Regions are set up in reference to the boundaries. Each bit position in region code is used

    to indicate one of four relative coordinate positions of points with respect to clip window:

    to the left, right, top or bottom. By numbering the bit positions in the region code as 1

    through 4 from right to left, the coordinate regions are corrected with bit positions as

    bit 1: left

    bit 2: right

    bit 3: below

    bit4: above

    A value of 1 in any bit position indicates that the point is in that relative position.

    Otherwise the bit position is set to 0. If a point is within the clipping rectangle the region

    code is 0000. A point that is below and to the left of the rectangle has a region code of

    0101.

    Bit values in the region code are determined by comparing endpoint coordinate

    values (x,y) to clip boundaries. Bit1 is set to 1 if x

  • CS2401 Computer Graphics Unit - I

    65

    these lines. Any lines that have a 1 in the same bit position in the region codes for each

    endpoint are completely outside the clipping rectangle, and we reject these lines.

    We would discard the line that has a region code of 1001 for one endpoint and a

    code of 0101 for the other endpoint. Both endpoints of this line are left of the clipping

    rectangle, as indicated by the 1 in the first bit position of each region code.

    A method that can be used to test lines for total clipping is to perform the logical

    and operation with both region codes. If the result is not 0000,the line is completely

    outside the clipping region.

    Lines that cannot be identified as completely inside or completely outside a clip

    window by these tests are checked for intersection with window boundaries.

    Line extending from one coordinates region to another may pass through the clip

    window, or they may intersect clipping boundaries without entering window.

    Cohen-Sutherland line clipping starting with bottom endpoint left, right , bottom

    and top boundaries in turn and find that this point is below the clipping rectangle.

    Starting with the bottom endpoint of the line from P1 to P2, we check P1 against

    the left, right, and bottom boundaries in turn and find that this point is below the clipping

    rectangle. We then find the intersection point P1 with the bottom boundary and discard

    the line section from P1 to P1.

    The line now has been reduced to the section from P1 to P2,Since P2, is outside the

    clip window, we check this endpoint against the boundaries and find that it is to the left

  • CS2401 Computer Graphics Unit - I

    66

    of the window. Intersection point P2 is calculated, but this point is above the window. So

    the final intersection calculation yields P2, and the line from P1 to P2is saved. This

    completes processing for this line, so we save this part and go on to the next line.

    Point P3 in the next line is to the left of the clipping rectangle, so we determine the

    intersection P3, and eliminate the line section from P3 to P3'. By checking region codes

    for the line section from P3'to P4 we find that the remainder of the line is below the clip

    window and can be discarded also.

    Intersection points with a clipping boundary can be calculated using the slope-

    intercept form of the line equation. For a line with endpoint coordinates (x1,y1) and (x2,y2)

    and the y coordinate of the intersection point with a vertical boundary can be obtained

    with the calculation.

    y =y1 +m (x-x1)

    where x value is set either to xwmin or to xwmax and slope of line is calculated as

    m = (y2- y1) / (x2- x1)

    the intersection with a horizontal boundary the x coordinate can be calculated as

    x= x1 +( y- y1) / m

    with y set to either to ywmin or to ywmax.

    Implementation of Cohen-sutherland Line Clipping

    #define Round(a) ((int)(a+0.5))

    #define LEFT_EDGE 0x1

    #define RIGHT_EDGE 0x2

    #define BOTTOM_EDGE 0x4

    #define TOP_EDGE 0x8

    #define TRUE 1

    #define FALSE 0

    #define INSIDE(a) (!a)

    #define REJECT(a,b) (a&b)

    #define ACCEPT(a,b) (!(a|b))

    unsigned char encode(wcPt2 pt, dcPt winmin, dcPt winmax)

    {

  • CS2401 Computer Graphics Unit - I

    67

    unsigned char code=0x00;

    if(pt.xwinmax.x)

    code=code|RIGHT_EDGE;

    if(pt.ywinmax.y)

    code=code|TOP_EDGE;

    return(code);

    }

    void swappts(wcPt2 *p1,wcPt2 *p2)

    {

    wcPt2 temp;

    tmp=*p1;

    *p1=*p2;

    *p2=tmp;

    }

    void swapcodes(unsigned char *c1,unsigned char *c2)

    {

    unsigned char tmp;

    tmp=*c1;

    *c1=*c2;

    *c2=tmp;

    }

    void clipline(dcPt winmin, dcPt winmax, wcPt2 p1,ecPt2 point p2)

    {

    unsigned char code1,code2;

    int done=FALSE, draw=FALSE;

    float m;

    while(!done)

    {

    code1=encode(p1,winmin,winmax);

    code2=encode(p2,winmin,winmax);

    if(ACCEPT(code1,code2))

    {

    done=TRUE;

    draw=TRUE;

    }

    else if(REJECT(code1,code2))

    done=TRUE;

    else

    {

  • CS2401 Computer Graphics Unit - I

    68

    if(INSIDE(code1))

    {

    swappts(&p1,&p2);

    swapcodes(&code1,&code2);

    }

    if(p2.x!=p1.x)

    m=(p2.y-p1.y)/(p2.x-p1.x);

    if(code1 &LEFT_EDGE)

    {

    p1.y+=(winmin.x-p1.x)*m;

    p1.x=winmin.x;

    }

    else if(code1 &RIGHT_EDGE)

    {

    p1.y+=(winmax.x-p1.x)*m;

    p1.x=winmax.x;

    }

    else if(code1 &BOTTOM_EDGE)

    {

    if(p2.x!=p1.x)

    p1.x+=(winmin.y-p1.y)/m;

    p1.y=winmin.y;

    }

    else if(code1 &TOP_EDGE)

    {

    if(p2.x!=p1.x)

    p1.x+=(winmax.y-p1.y)/m;

    p1.y=winmax.y;

    }

    }

    }

    if(draw)

    lineDDA(ROUND(p1.x),ROUND(p1.y),ROUND(p2.x),ROUND(p2.y));

    }

    Liang Barsky line Clipping:

    Based on analysis of parametric equation of a line segment, faster line clippers

    have been developed, which can be written in the form :

    x = x1 + u x

    y = y1 + u y 0

  • CS2401 Computer Graphics Unit - I

    69

    where x = (x2 - x1) and y = (y2 - y1)

    In the Liang-Barsky approach we first the point clipping condition in parametric

    form :

    xwmin

  • CS2401 Computer Graphics Unit - I

    70

    The value of u1 is taken as largest of set consisting of 0 and various values of r. The

    value of u2 is determined by examining the boundaries for which lines proceeds from

    inside to outside (P>0).

    A value of rkis calculated for each of these boundaries and value of u2 is the

    minimum of the set consisting of 1 and the calculated r values.

    If u1>u2, the line is completely outside the clip window and it can be rejected.

    Line intersection parameters are initialized to values u1=0 and u2=1. for each

    clipping boundary, the appropriate values for P and q are calculated and used by function

    Cliptest to determine whether the line can be rejected or whether the intersection

    parameter can be adjusted.

    When p0, the parameter r is used to update u2.

    If updating u1 or u2 results in u1>u2 reject the line, when p=0 and q

  • CS2401 Computer Graphics Unit - I

    71

    r=q/p

    if (r>*u2)

    retVal=FALSE;

    else

    if (r>*u1)

    *u1=r;

    }

    else

    if (p>0.0)

    {

    r=q/p

    if (r

  • CS2401 Computer Graphics Unit - I

    72

    }

    }

    }

    Nicholl-Lee-Nicholl Line clipping

    By creating more regions around the clip window, the Nicholl-Lee-Nicholl (or NLN)

    algorithm avoids multiple clipping of an individual line segment. In the Cohen-

    Sutherland method, multiple intersections may be calculated.These extra intersection

    calculations are eliminated in the NLN algorithm by carrying out more region testing

    before intersection positions are calculated.

    Compared to both the Cohen-Sutherland and the Liang-Barsky algorithms, the

    Nicholl-Lee-Nicholl algorithm performs fewer comparisons and divisions. The trade-off

    is that the NLN algorithm can only be applied to two-dimensional dipping, whereas both

    the Liang-Barsky and the Cohen-Sutherland methods are easily extended to three-

    dimensional scenes.

    For a line with endpoints P1 and P2 we first determine the position of point P1,

    for the nine possible regions relative to the clipping rectangle. Only the three regions

    shown in Fig. need to be considered. If P1 lies in any one of the other six regions, we can

    move it to one of the three regions in Fig. using a symmetry transformation. For

    example, the region directly above the clip window can be transformed to the region left

    of the clip window using a reflection about the line y = -x, or we could use a 90 degree

    counterclockwise rotation.

    Three possible positions for a line endpoint p1(a) in the NLN algorithm

  • CS2401 Computer Graphics Unit - I

    73

    Case 1: p1 inside region

    Case 2: p1 across edge

    Case 3: p1 across corner

    Next, we determine the position of P2 relative to P1. To do this, we create some new

    regions in the plane, depending on the location of P1. Boundaries of the new regions are

    half-infinite line segments that start at the position of P1 and pass through the window

    corners. If P1 is inside the clip window and P2 is outside, we set up the four regions

    shown in Fig

    The four clipping regions used in NLN alg when p1 is inside and p2 outside the clip

    window

    The intersection with the appropriate window boundary is then carried out,

    depending on which one of the four regions (L, T, R, or B) contains P2. If both P1 and P2

    are inside the clipping rectangle, we simply save the entire line.

    If P1 is in the region to the left of the window, we set up the four regions, L, LT, LR, and

    LB, shown in Fig.

  • CS2401 Computer Graphics Unit - I

    74

    These four regions determine a unique boundary for the line segment. For instance, if P2

    is in region L, we clip the line at the left boundary and save the line segment from this

    intersection point to P2. But if P2 is in region LT, we save the line segment from the left

    window boundary to the top boundary. If P2 is not in any of the four regions, L, LT, LR,

    or LB, the entire line is clipped.

    For the third case, when P1 is to the left and above the clip window, we usethe clipping

    regions in Fig.

    Fig : The two possible sets of clipping regions used in NLN algorithm when P1 is

    above and to the left of the clip window

    In this case, we have the two possibilities shown, depending on the position of P1,

    relative to the top left corner of the window. If P2, is in one of the regions T, L, TR, TB,

    LR, or LB, this determines a unique clip window edge for the intersection calculations.

    Otherwise, the entire line is rejected.

    To determine the region in which P2 is located, we compare the slope of the

  • CS2401 Computer Graphics Unit - I

    75

    line to the slopes of the boundaries of the clip regions. For example, if P1 is left of

    the clipping rectangle (Fig. a), then P2, is in region LT if

    slopeP1PTR

  • CS2401 Computer Graphics Unit - I

    76

    Display of a polygon processed by a line clipping algorithm

    For polygon clipping, we require an algorithm that will generate one or more closed areas

    that are then scan converted for the appropriate area fill. The output of a polygon clipper

    should be a sequence of vertices that defines the clipped polygon boundaries.

    Sutherland Hodgeman polygon clipping:

    A polygon can be clipped by processing the polygon boundary as a whole against

    each window edge. This could be accomplished by processing all polygon vertices

    against each clip rectangle boundary.

    There are four possible cases when processing vertices in sequence around the

    perimeter of a polygon. As each point of adjacent polygon vertices is passed to a window

    boundary clipper, make the following tests:

    1. If the first vertex is outside the window boundary and second vertex is inside,

    both the intersection point of the polygon edge with window boundary and

    second vertex are added to output vertex list.

    2. If both input vertices are inside the window boundary, only the second vertex

    is added to the output vertex list.

  • CS2401 Computer Graphics Unit - I

    77

    3. If first vertex is inside the window boundary and second vertex is outside only

    the edge intersection with window boundary is added to output vertex list.

    4. If both input vertices are outside the window boundary nothing is added to the

    output list.

    Clipping a polygon against successive window boundaries.

    Successive processing of pairs of polygon vertices against the left window boundary

    Clipping a polygon against the left boundary of a window, starting with vertex 1.

    Primed numbers are used to label the points in the output vertex list for this window

    boundary.

  • CS2401 Computer Graphics Unit - I

    78

    vertices 1 and 2 are found to be on outside of boundary. Moving along vertex 3 which is

    inside, calculate the intersection and save both the intersection point and vertex 3. Vertex

    4 and 5 are determined to be inside and are saved. Vertex 6 is outside so we find and save

    the intersection point. Using the five saved points we repeat the process for next window

    boundary.

    Implementing the algorithm as described requires setting up storage for an output list of

    vertices as a polygon clipped against each window boundary. We eliminate the

    intermediate output vertex lists by simply by clipping individual vertices at each step and

    passing the clipped vertices on to the next boundary clipper.

    A point is added to the output vertex list only after it has been determined to be inside or

    on a window boundary by all boundary clippers. Otherwise the point does not continue in

    the pipeline.

    A polygon overlapping a rectangular clip window

    Processing the vertices of the polygon in the above fig. through a boundary clipping

    pipeline. After all vertices are processed through the pipeline, the vertex list is {

    v2, v2, v3,v3}

  • CS2401 Computer Graphics Unit - I

    79

    Implementation of Sutherland-Hodgeman Polygon Clipping

    typedef enum { Left,Right,Bottom,Top } Edge;

    #define N_EDGE 4

    #define TRUE 1

    #define FALSE 0

    int inside(wcPt2 p, Edge b,dcPt wmin,dcPt wmax)

    {

    switch(b)

    {

    case Left: if(p.xwmax.x) return (FALSE); break;

    case bottom:if(p.ywmax.y) return (FALSE); break;

    }

    return (TRUE);

    }

    int cross(wcPt2 p1, wcPt2 p2,Edge b,dcPt wmin,dcPt wmax)

    {

    if(inside(p1,b,wmin,wmax)==inside(p2,b,wmin,wmax))

    return (FALSE);

    else

    return (TRUE);

    }

    wcPt2 (wcPt2 p1, wcPt2 p2,int b,dcPt wmin,dcPt wmax )

    {

    wcPt2 iPt;

    float m;

    if(p1.x!=p2.x)

    m=(p1.y-p2.y)/(p1.x-p2.x);

    switch(b)

    {

    case Left:

    ipt.x=wmin.x;

  • CS2401 Computer Graphics Unit - I

    80

    ipt.y=p2.y+(wmin.x-p2.x)*m;

    break;

    case Right:

    ipt.x=wmax.x;

    ipt.y=p2.y+(wmax.x-p2.x)*m;

    break;

    case Bottom:

    ipt.y=wmin.y;

    if(p1.x!=p2.x)

    ipt.x=p2.x+(wmin.y-p2.y)/m;

    else

    ipt.x=p2.x;

    break;

    case Top:

    ipt.y=wmax.y;

    if(p1.x!=p2.x)

    ipt.x=p2.x+(wmax.y-p2.y)/m;

    else

    ipt.x=p2.x;

    break;

    }

    return(ipt);

    }

    void clippoint(wcPt2 p,Edge b,dcPt wmin,dcPt wmax, wcPt2 *pout,int *cnt, wcPt2

    *first[],struct point *s)

    {

    wcPt2 iPt;

    if(!first[b])

    first[b]=&p;

    else

    if(cross(p,s[b],b,wmin,wmax))

    {

    ipt=intersect(p,s[b],b,wmin,wmax);

    if(b

  • CS2401 Computer Graphics Unit - I

    81

    if(b

  • CS2401 Computer Graphics Unit - I

    82

    The basic idea in this algorithm is that instead of always proceeding around the

    polygon edges as vertices are processed, we sometimes want to follow the window

    boundaries. Which path we follow depends on the polygon-processing direction

    (clockwise or counterclockwise) and whether the pair of polygon vertices currently being

    processed represents an outside-to-inside pair or an inside- to-outside pair. For clockwise

    processing of polygon vertices, we use the following rules:

    For an outside-to-inside pair of vertices, follow the polygon boundary.

    For an inside-to-outside pair of vertices,. follow the window boundary in a clockwise direction.

    In the below Fig. the processing direction in the Weiler-Atherton algorithm and the

    resulting clipped polygon is shown for a rectangular clipping window.

    An improvement on the Weiler-Atherton algorithm is the Weiler algorithm,

    which applies constructive solid geometry ideas to clip an arbitrary polygon

    against any polygon clipping region.

    Curve Clipping

    Curve-clipping procedures will involve nonlinear equations, and this requires

    more processing than for objects with linear boundaries. The bounding rectangle for a

    circle or other curved object can be used first to test for overlap with a rectangular clip

    window.

    If the bounding rectangle for the object is completely inside the window, we save

    the object. If the rectangle is determined to be completely outside the window, we discard

    the object. In either case, there is no further computation necessary.

    But if the bounding rectangle test fails, we can look for other computation-saving

    approaches. For a circle, we can use the coordinate extents of individual quadrants and

    then octants for preliminary testing before calculating curve-window intersections.

    The below figure illustrates circle clipping against a rectangular window. On the

    first pass, we can clip the bounding rectangle of the object against the bounding rectangle

  • CS2401 Computer Graphics Unit - I

    83

    of the clip region. If the two regions overlap, we will need to solve the simultaneous line-

    curve equations to obtain the clipping intersection points.

    Clipping a filled circle

    Text clipping

    There are several techniques that can be used to provide text clipping in a graphics

    package. The clipping technique used will depend on the methods used to

    generate characters and the requirements of a particular application.

    The simplest method for processing character strings relative to a window

    boundary is to use the all-or-none string-clipping strategy shown in Fig. . If all of the

    string is inside a clip window, we keep it. Otherwise, the string is discarded. This

    procedure is implemented by considering a bounding rectangle around the text pattern.

    The boundary positions of the rectangle are then compared to the window boundaries,

    and the string is rejected if there is any overlap. This method produces the fastest text

    clipping.

    Text clipping using a bounding rectangle about the entire string

    An alternative to rejecting an entire character string that overlaps a window

    boundary is to use the all-or-none character-clipping strategy. Here we discard only

    those characters that are not completely inside the window .In this case, the boundary

    limits of individual characters are compared to the window. Any character that either

    overlaps or is outside a window boundary is clipped.

  • CS2401 Computer Graphics Unit - I

    84

    Text clipping using a bounding rectangle about individual characters.

    A final method for handling text clipping is to clip the components of individual

    characters. We now treat characters in much the same way that we treated lines. If an

    individual character overlaps a clip window boundary, we clip off the parts of the

    character that are outside the window.

    Text Clipping performed on the components of individual characters

    Exterior clipping:

    Procedure for clipping a picture to the interior of a region by eliminating

    everything outside the clipping region. By these procedures the inside region of the

    picture is saved. To clip a picture to the exterior of a specified region. The picture parts to

    be saved are those that are outside the region. This is called as exterior clipping.

    Objects within a window are clipped to interior of window when other higher

    priority window overlap these objects. The objects are also clipped to the exterior of

    overlapping windows.

Recommended

View more >