Computer Graphics (CS4300) 2011S: Lecture 4
Today
- midpoint algorithm for rasterizing line segments
- line attributes
Midpoint Algorithm
- given a line segment, e.g. as start and end points
, how should we decide how to “turn on” pixels to display it? - this is an example of rasterization: converting a description of geometry (or model) into an image
- we need an algorithm that will return a resonable set of pixels; one common method is called the midpoint algorithm
- first, observe that it is sufficient to only consider the case of a line in quadrant I with more run than rise, i.e. all coordinates positive and
. Any other line can be handled by small tweaks to this case. - overall structure of the algorithm:
(start at bottom)- for
to 
do (iterate from left to right)- turn on pixel
(we are now “on” a line pixel) - if condition then
(need to move up)
- The interesting part is condition. Idea: compute the midpoint
between the centers of the pixels at 
and 
(i.e. the pixel immediately to the right and the one above it); if is below the ideal line connecting 
to 
, then the pixel at is closer to the line than , so move up.
- computing the midpoint coordinates is actually trivial:
- but how to determine if is above or below (or on) the line?
- we have already seen one method: make a temporary vector from
and take the cross product of it and the vector 
, both extended from 2D to 3D with 
- if
is positive, then 
is below the line(NOTE: there was a typo here, it is not strictly correct to check the magnitude of the cross product, as it will alwasy be either positive or zero. You need to check the sign of the z component of the cross product. The dot product with 
selects the z component of the result of the cross product. It is mathematically correct, and a short way to write the equation, but in code you should realize that since the arguments to the cross product both had , that the output will always have 
. Thus you only need to calculate the 
component of the cross product and check its sign.) - how many floating point operations (FLOPS) does this require per iteration?
- note that
can be pre-computed before the loop - two additions to get
- two subtractions to get
- two multiplications and one subtraction to get (recall that only the component will be non-zero for the cross product of two 2D vectors extended to 3D with )
- total: 7 FLOPS per iteration using cross product
- we can do better, and we want to, because we may have many lines to draw, and the midpoint algorithm is linear in the maximum difference in
or 
coordinates from to - idea 2: use the implicit form of the line
- can be shown (see text or L3) that
is an implicit form for the line through the points 
will be zero if is on the line, positive if above, and negative if below (to prove that the signs work out like this, consider 
)- FLOP count:
- two additions to get
- two multiplies and two additions to evaluate
- total: 6 FLOPS per iteration using implict line eqn directly
- this is not much better than using the cross product, but it sets the stage for an incremental approach
- idea 3: observe that if we know the value of
for a given point 
, we can use that value to accelerate the computation of nearby points: - so now if we initialize
before the loop, we can make condition simply check if 
- if so, we need to move up, and next time through we will need
- if not, we will not move up, and next time through we will need
- revised pseudocode:
- (start at bottom)
- for to do (iterate from left to right)
- turn on pixel (we are now “on” a line pixel)
- if then
- (need to move up)
- else (don’t move up)
- FLOP count:
- one addition, assuming we pre-compute
and 
- total: 1 FLOP per iteration using incremental approach
Line Attributes
- line width
- dash patterns
- end caps: butt, round, square
- joins: bevel, miter, round
Next Time
- sampling and antialiasing
- color perception and color spaces
- reading on website
