# Line drawing

Views:

Category: Entertainment

## Presentation Description

No description available.

## Presentation Transcript

### Points and Lines :

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 in use. With a CRT monitor, for example, the electron beam is turned on to illuminate the screen phosphor at the selected location.

### WHERE TO DRAW A LINE?? :

WHERE TO DRAW A LINE?? Line drawing is accomplished by calculating intermediate positions along the line path between specified end points. An output device is then directed to fill in these positions between the endpoints. Precise definition of line drawing Given two points P and Q in the plane, both with integer coordinates, determine which pixels on a raster screen should be on in order to make a picture of a unit-width line segment starting from P and ending at Q.

### Scan Converting 2D Line Segments :

Scan Converting 2D Line Segments Given: Segment endpoints (integers x1, y1; x2, y2) Identify: Set of pixels (x, y) to display for segment

### Line Rasterization Requirements :

Line Rasterization Requirements Transform continuous primitive into discrete samples Uniform thickness & brightness Continuous appearance No gaps Accuracy Speed

### Line Drawing :

Line Drawing Horizontal Line The horizontal line is obtained by keeping the value of y constant and repeatedly incrementing the x value by one unit. The following code draw a horizontal line from (xstart,y) to (xend,y), xstart <= xend. For (x=xstar; x<= xend ; x++)do Putpixel(x,y,8); If xstart>xend, in the for loop u must start from reseved order (high to low)

### Line Drawing :

Line Drawing The vertical line is obtained by keeping the value of x constant and repeatedly incrementing the y value by one unit. The following code draw a horizontal line from (x,ystart) to (x,yend), ystart <= yend. For (y=ystart ; y<=yend ;y++) do Putpixel(x,y,8); If ystart>yend, the for loop must be replaced by in reserve counter (high to low).

### Slide 7:

0 1 2 3 4 5 6 6 5 4 3 2 1 0 (3, 3)

### Scan Converting A Line :

Scan Converting A Line The Cartesian slope- intercept equation for a straight line is:

### Line drawing (cont) :

Line drawing (cont) The thinnest line is of one-pixel wide. We will concentrate on drawing a line of 1 pixel resolution. The Cartesian slope-intercept equation for a straight line is y= m. x + b m is the slope of the line and b is the y intercept. Given the endpoints of a line segment. m = y2-y1 / x2-x1 b= y1-m.x1

### Scan Converting A Line :

Scan Converting A Line These equation form the basic for determining deflection voltage in analog devices. |m|<1 |m|>1

### Line Drawing (cont) :

Line Drawing (cont) Also for any given x interval ∆x along a line, we can compute the corresponding y interval ∆y from ∆y= m. ∆x Similarly we can obtain the x interval ∆x corresponding to a specified ∆y as ∆x= ∆y / m These equations form the basis for determining deflection voltages in analog devices.

### Line Drawing (cont) :

Line Drawing (cont) 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. ∆y= m. ∆x. 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. ∆x= ∆y / m. For lines with m = 1, ∆ x = ∆ y and the horizontal and vertical deflections voltages are equal.

### Scan Converting A Line :

Scan Converting A Line On raster system, lines are plotted with pixels, and step size (horizontal & vertical direction) are constrained by pixel separation.

### Scan Converting A Line :

Scan Converting A Line We must sample a line at discrete positions and determine the nearest pixel to the line at each sampled position.

### Symmetry :

Symmetry If we could draw lines with positive slope (0<=slope<=1) we would be done. For a line with negative slope (0>=slope>=-1) We negate all Y values For a line with slope > 1 or slope <-1 we just swap x and y axes 450 (y,x) (x,y) (x,-y) (y,-x) (-y,x) (x,-y) (-x,-y) (-y,-x)

### Lines & Slopes :

Lines & Slopes The slope of a line (m) is defined by its start and end coordinates The diagram below shows some examples of lines and their slopes

### A Very Simple Solution :

A Very Simple Solution We could simply work out the corresponding y coordinate for each unit x coordinate Let’s consider the following example:

### A Very Simple Solution (cont…) :

A Very Simple Solution (cont…) 1 2 3 4 5 0 1 2 3 4 5 6 0 7

### A Very Simple Solution (cont…) :

A Very Simple Solution (cont…) First work out m and b: Now for each x value work out the y value:

### A Very Simple Solution (cont…) :

A Very Simple Solution (cont…) Now just round off the results and turn on these pixels to draw our line 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7

### A Very Simple Solution (cont…) :

A Very Simple Solution (cont…) However, this approach is just way too slow In particular look out for: The equation y = mx + b requires the multiplication of m by x Rounding off the resulting y coordinates We need a faster solution

### A Quick Note About Slopes :

A Quick Note About Slopes In the previous example we chose to solve the parametric line equation to give us the y coordinate for each unit x coordinate What if we had done it the other way around? So this gives us: where: and

### A Quick Note About Slopes (cont…) :

A Quick Note About Slopes (cont…) Leaving out the details this gives us: We can see easily that this line doesn’t lookvery good! We choose which way to work out the line pixels based on the slope of the line 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7

### A Quick Note About Slopes (cont…) :

A Quick Note About Slopes (cont…) If the slope of a line is between -1 and 1 then we work out the y coordinates for a line based on it’s unit x coordinates Otherwise we do the opposite – x coordinates are computed based on unit y coordinates

### Slide 25:

Digital Differential Analyzer (DDA Algorithm)

### DDA Algorithm :

DDA Algorithm Algorithm is an incremental scan conversion method. Based on calculating either ∆y or ∆x If |m|<1,

### DDA Algorithm :

DDA Algorithm If |m|>1, If For the above cases it is assumed that lines are to be processed from the left endpoint to the right endpoint. If the process is reverse, If

### DDA Pseudo-code :

DDA Pseudo-code // assume that slope is gentle DDA(float x0, float x1, float y0, float y1) { float x, y; float xinc, yinc; int numsteps; numsteps = Round(x1) – Round(x0); xinc = (x1 – x0) / numsteps; yinc = (y1 – y0) / numsteps; x = x0; y = y0; ColorPixel(Round(x),Round(y)); for (int i=0; i<numsteps; i++) { x += xinc; y += yinc; ColorPixel(Round(x),Round(y)); } } Q: For each step, how many floating point operations are there? A: 4 Q: For each step, how many integer operations are there? A: 2

### DDA Example :

DDA Example Suppose we want to draw a line starting at pixel (2,3) and ending at pixel (12,8). What are the values of the variables x and y at each timestep? What are the pixels colored, according to the DDA algorithm? numsteps = 12 – 2 = 10 xinc = 10/10 = 1.0 yinc = 5/10 = 0.5

### DDA ALGORITHM :

DDA ALGORITHM Major deficiency in the above approach : The rounding operations and floating-point arithmetic in DDA algo. are still time-consuming. We can improve the performance of the DDA algorithm by separating the increments m and l /m into integer and fractional parts so that all calculation are reduced to integer operations. Major advantages in the above approach : Faster method for calculating pixel positions than the direct use of Eq. y=mx+c It eliminates the multiplication by making use of raster characteristics, so that appropriate increments are applied in the x or y direction to step to pixel positions along the line path.

### Slide 31:

Bresenham’s Line Algorithm

### Bresenham’s Line Algorithm :

Bresenham’s 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.

### Slide 33:

Bresenham’s Line Algorithm

### Slide 34:

Bresenham’s Line Algorithm

### Slide 35:

Bresenham’s Line Algorithm

### Slide 36:

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 – yk d2 = (yk + 1) – y = yk + 1- m(xk + 1) – b d1-d2 = 2m(xk + 1) – 2 yk + 2b – 1 Bresenham’s Line Algorithm

### Slide 37:

Define pk = Δx ( d1-d2) = 2Δyxk-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 2Δy + Δ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. Bresenham’s Line Algorithm

### Slide 38:

Coordinate changes along the line occur in unit steps in either the x or y directions. Therefore, we can obtain the values of successive decision parameters using incremental integer calculations. At step k + 1, the decision parameter can be evaluated as, pk+1 = 2Δy.xk+1 - 2Δx.yk+1 + c Taking the difference of pk+ 1 and pk we get the following. pk+1 – pk = 2Δy.(xk+1- xk)-2Δx.(yk+1 – yk) But, xk+1 = xk +1, so that pk+1 = pk + 2Δy - 2 Δx(yk+1 – yk) Where the term yk+1-yk is either 0 or 1, depending on the sign of parameter pk Bresenham’s Line Algorithm

### Slide 39:

The first parameter p0 is directly computed p0 = 2 Δyx0 - 2 Δxy0 + c = 2 Δyx0 – 2 Δxy0 +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 = 2Δy – Δx The constants 2Δy and 2Δy-2Δx are calculated once for each time to be scan converted Bresenham’s Line Algorithm

### Slide 40:

So, the arithmetic involves only integer addition and subtraction of 2 constants 1. Input the two end points and store the left end point in (x0,y0) 2. Load (x0,y0) into the frame buffer (plot the first point) 3. Calculate the constants Δx, Δy, 2Δy and 2Δy-2Δx and obtain the starting value for the decision parameter as p0 = 2Δy- Δx Bresenham’s Line Algorithm

### Slide 41:

4. 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 + 2Δy 5. Repeat step 4 (above step) Δx times Otherwise Point to plot is (xk+1, yk+1) pk+1 = pk + 2Δy - 2Δx Bresenham’s Line Algorithm

### Slide 42:

#include "device.h" 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 > xb) { x = xb; y = yb; xEnd = xa; } else { x = xa; y = ya; xEnd = xb; } setPixel (x, y); while (x < xEnd) { x++; if (p < 0) p += twoDy; else { y++; p += twoDyDx; } setPixel (x, y); } } Bresenham’s Line Algorithm

### Slide 44:

Suppose we want to draw a line starting at pixel (2,3) and ending at pixel (12,8). What are the values of p0, dx and dy? What are the values of the variable p at each timestep? What are the pixels colored, according to Bresenham’s algorithm? dx = 12 – 2 = 10 dy = 8 – 3 = 5 p0 = 2dy – dx = 15 2dy = 10 2dy – 2dx = -10 Bresenham’s Line Algorithm

### Where do we draw a circle??? :

Where do we draw a circle??? Properties of a circle: A circle is defined as a set of points that are all the given distance (xc,yc). This distance relationship is expressed by the pythagorean theorem in Cartesian coordinates as (x – xc)2 + (y – yc) 2 = r2 We could use this equation to calculate the points on the circle circumference by stepping along x-axis in unit steps from xc-r to xc+r and calculate the corresponding y values at each position as y = yc +(- ) (r2 – (xc –x )2)1/2 This is not the best method: Considerable amount of computation Spacing between plotted pixels is not uniform

### Polar co-ordinates for a circle :

Polar co-ordinates for a circle We could use polar coordinates r and θ, x = xc + r cosθ y = yc + r sinθ A fixed angular step size can be used to plot equally spaced points along the circumference A step size of 1/r can be used to set pixel positions to approximately 1 unit apart for a continuous boundary But, note that circle sections in adjacent octants within one quadrant are symmetric with respect to the 45 deg line dividing the two octants Thus we can generate all pixel positions around a circle by calculating just the points within the sector from x=0 to x=y This method is still computationally expensive

### Bresenham to Midpoint :

Bresenham to Midpoint Bresenham's 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. Bresenham's circle algorithm avoids square-root calculations by comparing the squares of the pixel separation distances.

### Midpoint Circle Algorithm :

Midpoint Circle Algorithm We will first calculate pixel positions for a circle centered around the origin (0,0). Then, each calculated position (x,y) is moved to its proper screen position by adding xc to x and yc to y Note that along the circle section from x=0 to x=y in the first octant, the slope of the curve varies from 0 to -1 Therefore, we can take unit steps in the positive x direction over this octant and use a decision parameter to determine which of the two possible y positions is closer to the circle path at each step. Positions in the other seven octants are then obtained by symmetry. Circle function around the origin is given by fcircle(x,y) = x2 + y2 – r2 Any point (x,y) on the boundary of the circle satisfies the equation fcircle(x,y) =0

### Midpoint Circle Algorithm :

Midpoint Circle Algorithm For a point in the interior of the circle, the circle function is negative and for a point outside the circle, the function is positive Thus, fcircle(x,y) < 0 if (x,y) is inside the circle boundary fcircle(x,y) = 0 if (x,y) is on the circle boundary fcircle(x,y) > 0 if (x,y) is outside the circle boundary yk yk-1 xk xk+1 xk+3 Midpoint x2+y2-r2=0 Midpoint between candidate pixels at sampling position xk+1 along a circular path

### Midpoint Circle Algorithm :

Midpoint Circle Algorithm Assuming we have just plotted the pixel at (xk,yk) , we next need to determine whether the pixel at position (xk + 1, yk-1) is closer 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 – r2 If pk < 0 , this midpoint is inside the circle and the pixel on the scan line yk is closer to the circle boundary. Otherwise, the mid position is outside or on the circle boundary, and we select the pixel on the scan line yk-1

### Midpoint Circle Algorithm :

Midpoint Circle Algorithm Successive decision parameters are obtained using incremental calculations pk+1 = fcircle(xk+1+1, yk+1-1/2) = [(xk+1)+1]2 + (yk+1 -1/2)2 –r2 OR pk+1 = pk+2(xK+1) + (yK+12 – yk2) – (yk+1- yk)+1 Where yk+1 is either yk or yk-1, depending on the sign of pk Increments for obtaining pk+1: 2xk+1+1 if pk is negative 2xk+1+1-2yk+1 otherwise

### Midpoint circle algorithm :

Midpoint circle algorithm Note that following can also be done incrementally: 2xk+1 = 2xk +2 2 yk+1 = 2yk – 2 At the start position (0,r) , these two terms have the values 2 and 2r-2 respectively 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-r2 OR P0 = 5/4 -r If radius r is specified as an integer, we can round p0 to p0 = 1-r

### The actual algorithm :

The actual 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 < 0 , the next point along the circle centered on (0,0) is (xk+1, yk) and pk+1 = pk + 2xk+1 + 1

### The algorithm :

The algorithm Otherwise the next point along the circle is (xk+1, yk-1) and pk+1 = pk + 2xk+1 +1 -2yk+1 Where 2xk+1 = 2xk+2 and 2yk+1 = 2yk-2 4: Determine symmetry points in the other seven octants 5: Move each calculated pixel position (x,y) onto the circular path centered on (xc ,yc) and plot the coordinate values x = x+ xc , y= y+ yc 6: Repeat steps 3 through 5 until x >= y

### Midpoint Circle Algorithm :

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 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); } /* EXAMPLE ENDS HERE */

### Midpoint Ellipse :

Midpoint Ellipse Derivation

### Midpoint Ellipse Algorithm :

Midpoint Ellipse Algorithm Input and ellipse center and obtain the first point on an ellipse centered on the origin as Calculate the initial value of the decision parameter in region 1 as

### Midpoint Ellipse.. :

Midpoint Ellipse.. At each position in region 1, starting at k = 0, perform the following test. if , the next point along the ellipse centered on (0,0) is and Otherwise, the next point along the ellipse is and with and continue until

### Midpoint Ellipse Contd. :

Midpoint Ellipse Contd. Calculate the initial value of the decision parameter in region 2 as where is the last position calculated in region 1 At each position in region 2, starting at k=0, perform the following test. if , the next point along the ellipse centered on (0,0) is and Otherwise, the next point along the ellipse is and Using the same incremental calculations for x and y as in region 1. Continue until y=0

### Midpoint Ellipse :

Midpoint Ellipse For both regions, determine symmetry points in the other three quadrants Move each calculated pixel position (x, y) onto the elliptical path that is centered on and plot the coordinate values 