### Mathematics VS Engineering

We like to think about a scene as mathematical primitives in a world-space. This scene is then rendered into the frame buffer. This allows a logical separation of the world from the view of that world.mathematically, points are infinitely small

mathematically, line segments are infinitely thin

these mathematical elements need to be converted into discrete pixels

as usual, there is an obvious easy way of doing these conversions, and then there is the way it is actually done (for efficiency.)

### Scan Conversion (rasterization) of a line ( Foley 3.2 )

take an analytic (continuous) function and convert (digitize) it so appropriate pixels can be illuminated in the frame bufferIn a language such as OpenGL a programmer can generate a 2D line segment in world-space with code like the following:

- glBegin(GL_LINE_STRIP);

- glVertex2f(1.5, 3.0);

glVertex2f(4.0, 4.0);

In a language such as OpenGL polygons are very restricted to improve speed:

- edges can not intersect (simple polygons)
- polygon must be convex, not concave

To generate the outline of a triangular 2D polygon in world-space using OpenGL a programmer can write code like the following:

- glBegin(GL_LINE_LOOP);

- glVertex2f(1.5, 3.0);

glVertex2f(4.0, 4.0);

glVertex2f(4.0, 1.0);

- glBegin(GL_POLYGON);

- glVertex2f(1.5, 3.0);

glVertex2f(4.0, 4.0);

glVertex2f(4.0, 1.0);

Note that large complex objects are often reduced down to a large number of triangles ( i.e. triangulated ), for a number of reasons:

- Triangles are guaranteed to be simple convex polygons.
- All points in a triangle are guaranteed to be co-planar.
- Most importantly, modern computer graphics hardware is often optimized to generate large numbers of triangles very quickly, so it is actually faster to break a complex shape down and then deal with a kazillion triangles than to deal with a smaller number of more complicated shapes.
- ( The degenerate case, of three co-linear points is usually not a major problem. )

How are line segments and polygons in world-space converted into illuminated pixels on the screen?

First these coordinates in world-space must be converted to coordinates in the viewport (ie pixel coordinates in the frame buffer.) This may involve the conversion from a 2D world to a 2D frame buffer (which we will study in a couple weeks), or the reduction from a 3D world to a 2D frame buffer (which we will study a couple weeks later.)

Then these coordinates in the viewport must be used to draw lines and polygons made up of individual pixels (rasterization.) This is the topic we will discuss now.

Most of the algorithms in Computer Graphics will follow the same pattern below. There is the simple (braindead) algorithm that works, but is too slow. Then that algorithm is repeatedly refined, making it more complicated to understand, but much faster for the computer to implement.

### Braindead Algorithm

given a line segment from leftmost (Xo,Yo) to rightmost (X1,Y1):- Y=mX+B

m = deltaY / deltaX = (Y1 - Yo) / ( X1 - Xo)

start = round(Xo)

stop = round(X1)

for (Xi = start; Xi <= stop; Xi++)

- illuminate Xi, round(m * Xi + B);

- comparison
- fractional multiplication
- 2 additions
- call to round()

Why is the slope (m) important?

if m=1 then each row and each column have a pixel filled in

if 0 <= m< 1 then each column has a pixel and each row has >= 1, so we increment X each iteration and compute Y.

if m > 1 then each row has a pixel and each column has >= 1, so we increment Y each iteration and compute X.

### Simple Incremental Algorithm ( Foley 3.2.1 )

The basic improvement of this algorithm over the purely braindead one is that instead of calculating Y for each X from the equation of a line ( one multiplication and one addition ), we will calculate it from the previous Y by just adding a fixed constant ( one addition only ). This works because the delta change in X from one column to the next is known to be exactly 1.given a line segment from leftmost (Xo,Yo) to rightmost (X1,Y1):

- Y=mX+B

m = deltaY / deltaX = (Y1 - Yo) / ( X1 - Xo)

if deltaX is 1 -> deltaY is m

so if Xi+1 = Xi + 1 -> Yi+1 = Yi + m

starting at the leftmost edge of the line:

- X = round(Xo)

Y = Yo

while (X <= X1) repeatedly

- illuminate X, round(Y)

add 1 to X (moving one pixel column to the right)

add m to Y

If |m| > 1 then we must reverse the roles of X and Y, incrementing Y by 1 and incrementing X by 1/m in each iteration.

Horizontal and vertical lines are subsets of the 2 cases given above.

need such a common, primitive function to be VERY fast.

features:

- + incremental
- - rounding is a time consuming operation(Y)
- - real variables have limited precision, can cause a cumulative error in long line segments (e.g. 1/3)
- - Y must be a floating point variables

### Midpoint Line Algorithm ( Foley 3.2.2 )

This algorithm follows from the previous one, and further takes advantage of the observation that for line slopes between 0 and 1, the change in Y from one column to the next will be either 0 or 1. This algorithm requires no rounding, no floating point numbers, and no multiplications.given a line segment from leftmost (Xo,Yo) to rightmost (X1,Y1):

- Y=mX+b

m = deltaY / deltaX = (Y1 - Yo) / ( X1 - Xo)

assuming Xo,X1,Yo,Y1 are integers

Y=mX+B

m = deltaY / deltaX = (Y1 - Yo) / ( X1 - Xo)

can rewrite the equation in the form: F(X,Y) = ax + by + c = 0

Y = (deltaY / deltaX) * X + B

0 = (deltaY / deltaX) * X - Y + B

0 = deltaY * X - deltaX * Y + deltaX * B

F(X,Y) = deltaY * X - deltaX * Y + deltaX * B

so for any point (Xi,Yi) we can plug Xi,Yi into the above equation and

- F(Xi,Yi) = 0 -> (Xi,Yi) is on the line

F(Xi,Yi) > 0 -> (Xi,Yi) is below the line

F(Xi,Yi) < 0 -> (Xi,Yi) is above the line

- the pixel to the EAST (Xp+ 1,Yp)

or the pixel to the NORTHEAST (Xp+ 1,Yp+ 1)

- line above the midpoint -> illuminate the NORTHEAST pixel

line below the midpoint -> illuminate the EAST pixel

line exactly on the midpoint -> CHOOSE TO illuminate the EAST pixel

We plug the Midpoint into the above F() for the line and see where the midpoint falls in relation to the line.

d = F(Xp+1,Yp+0.5)

- d > 0 -> pick NORTHEAST pixel

d < 0 -> pick EAST pixel

d = 0 -> ***CHOOSE*** to pick EAST pixel

if we pick the EAST pixel

- Midpoint is incremented by 1 in X and 0 in Y

We want to compute the new d without recomputing d from the new Midpoint

We want to compute the new d only using current d

dcurrent= F(Xp + 1,Yp + 0.5)

using the function F(X,Y) = deltaY * X - deltaX * Y + deltaX * B we can expand this out ...

dcurrent= deltaY * (Xp + 1) - deltaX * (Yp + 0.5) + deltaX * B

dnew = F(Xp + 2, Yp + 0.5)

dnew = deltaY * (Xp + 2) - deltaX * (Yp + 0.5) + deltaX * B

when you simplify it you end up with: dnew = dcurrent + deltaY

so we create a new variable called deltaE where deltaE = deltaY

- Midpoint is incremented by 1 in X and 1 in Y

We want to compute the new d without recomputing d from the new Midpoint, only using current d

We want to compute the new d only using current d

dcurrent= F(Xp + 1,Yp + 0.5)

using the function F(X,Y) = deltaY * X - deltaX * Y + deltaX * B we can expand this out ...

dcurrent= deltaY * (Xp + 1) - deltaX * (Yp + 0.5) + deltaX * B

dnew = F(Xp + 2, Yp + 1.5)

dnew = deltaY * (Xp + 2) - deltaX * (Yp + 1.5) + deltaX * B

when you simplify it you end up with: dnew = dcurrent + deltaY - deltaX

so we create a new variable called deltaNE where deltaNE = deltaY - deltaX

initial point (Xo,Yo) is known

so initial M is at (Xo + 1, Yo + 0.5)

so initial d = F(Xo + 1,Yo + 0.5)

using the function F(X,Y) = deltaY * X - deltaX * Y + deltaX * B we can expand this out ...

- = deltaY * (Xo + 1) - deltaX * (Yo + 0.5) + deltaX * B

= (deltaY * Xo - deltaX * Yo + deltaX * B) + deltaY - 0.5 * deltaX

= F(Xo,Yo) + deltaY - 0.5 * deltaX

so initial d = deltaY - deltaX / 2

the divion by 2 is still annoying, but we can remove it by being clever

we can avoid the division by 2 by multiplying F() by 2

this also multiplies d, deltaE, deltaNE by 2

but since d is only concerned with =0,< 0, or > 0 multiplication does not affect it

So now we can finally show the Midpoint Line algorithm

Assuming integral endpoints for the line segment (if not then make them integral)

starting at the leftmost edge of the line:

- deltaX = X1 - Xo

deltaY = Y1 - Yo

d = deltaY * 2 - deltaX

deltaE = deltaY * 2

deltaNE = (deltaY - deltaX) * 2

X = Xo

Y = Yo

illuminate X, Y

while (X < X1) repeatedly

- if ( d <= 0)

- add deltaE to d

add 1 to X

- add deltaNE to d

add 1 to X

add 1 to Y

The full algorithm is given (in C) in the white book as figure 3.8 on p. 78.

features:

- + incremental
- + only addition done in each iteration
- + all integer variables

**Calculate which pixels will be highlighted using the midpoint algorithm to draw a line from ( 5,8 ) to ( 9, 11 ).**

__Exercise:__AFTER you have determined your answer, compare it to the results shown in Figure 3.9 of Foley.

### Complications

- What if the line segment starts on the right and proceeds
to the left?
- with plain lines you could reverse the endpoints and draw the line from left to right as described above. If the line has a pattern this simplification will not work.

- What about lines with slope < 0 or slope > 1?
- some modifications needed

- What about clipped lines?
- Determination of the starting and ending points and the deltas within the clipped region must be done carefully, so that the exact same pixels are drawn as if the original unclipped line were being drawn.

- Varying intensity of pixels with slope.
- A line drawn at an angle will have fewer pixels per inch than one drawn at a horizontal, even though each has one pixel per column, because the angled line covers a greater distance. ( To give a specific example, a 45 degree line has 70% of the pixel density of a horizontal line. As a result, the angled line will appear thinner than the horizontal one. One solution to this problem is to increase the intensity of the pixels on the angled line to account for the lower pixel density.

- Intersections of drawn lines.
- When drawing two or more lines that intersect, ( such as the outline edges of a polygon ), it may be important not to draw the common pixels twice, depending on the hardware and graphics techniques being used.