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.)
take an analytic (continuous) function and convert (digitize) it so appropriate pixels can be illuminated in the frame buffer
In 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);
glEnd();
Polygons are single closed loops of line segments, usually
drawn with their interiors filled.
In a language such as OpenGL polygons are very restricted to improve
speed:
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);
glEnd();
To generate a filled triangular 2D polygon in world-space using
OpenGL a programmer can write code like the following:
glBegin(GL_POLYGON);
glVertex2f(1.5, 3.0);
glVertex2f(4.0, 4.0);
glVertex2f(4.0, 1.0);
glEnd();
We will not limit ourselves to these 'easier' polygons.
Note that large complex objects are often reduced down to a large number of triangles ( i.e. triangulated ), for a number of reasons:
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.
given a line segment from leftmost (Xo,Yo) to rightmost (X1,Y1):
Y=mX+B
m = deltaY / deltaX = (Y1 - Yo) / ( X1 - Xo)
Assuming |m| <= 1 we start at the leftmost edge of the line, and move right one pixel-column at a time illuminating the appropriate pixel in that column.
start = round(Xo)
stop = round(X1)
for (Xi = start; Xi <= stop; Xi++)
illuminate Xi, round(m * Xi + B);
Why is this bad? Each iteration has:
Addition is OK, fractional multiplication is bad, and a function call is very bad as this is done A LOT. So we need more complex algorithms which use simpler operations to decrease the speed.
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.
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
Assuming |m| <= 1 we start at the leftmost edge of the line, and move right one pixel-column at a time illuminating the pixel either in the current row or an adjacent row.
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
This guarantees there is one pixel illuminated in each column for the line
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:
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
Assuming 0 <= m <= 1 we start at the leftmost edge of the line, and move right one pixel-column at a time illuminating the pixel either in the current row (the pixel to the EAST) or the next higher row (the pixel to the NORTHEAST.)
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
Given that we have illuminated the pixel at (Xp,Yp) we will next either illuminate
the pixel to the EAST (Xp+ 1,Yp)
or the pixel to the NORTHEAST (Xp+ 1,Yp+ 1)
To decide we look at the Midpoint between the EAST and NORTHEAST pixel and see which side of the midpoint the line falls on.
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 create a decision variable called d
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
That tells us which pixel to illuminate next. Now we need to compute what Midpoint is for the next iteration.
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
if we pick the NORTHEAST pixel
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
since (Xo,Yo) is on the line -> F(Xo,Yo) = 0
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
else
add deltaNE to d
add 1 to X
add 1 to Y
illuminate X, Y
The full algorithm is given (in C) in the red book as program
3.2 on p.75.
The full algorithm is given (in C) in the white book as figure
3.8 on p. 78.
features:
Exercise:
Calculate which pixels will be highlighted using the
midpoint algorithm to draw a line from ( 5,8 ) to ( 9, 11 ).
AFTER you have determined your answer, compare it to the results
shown in Figure 3.9 of Foley.