# 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

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;

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

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