Previous | Next --- Slide 44 of 65
Back to Lecture Thumbnails
kayvonf

Question: As part of your first programming assignment you'll implement a general line drawing algorithm that works in all cases, but here could someone at least suggest a solution for extending the basic algorithm for the case where s > 1?

kapalani

I guess the idea behind why this wouldn't work well when the slope was greater than 1 was because the line would be rising faster vertically than running horizontally. So if we moved along the x direction plotting the y values, a move to the right by just one pixel could mean we shoot up a lot, so there would be a lot of the line that wouldn't be shaded. To adapt this same algorithm to the case when slope>1, we could just walk along the line in the y direction and add 1/s each time (essentially reverse u and v in the above algorithm and therefore invert s). Now since the slope>1, 1/slope will be less than 1, so we've sort of reduced it to the case above, where we can be sure we won't have any holes in the line, because we're now walking along the direction that's changing more.

dsaksena

I agree with @kapalani and would suggest having an if-else case, hoping s = 1 works for if case

if(s <= 1){

v = v1;
for( u = u1; u<=u2; u++){

v += s;
draw(u, round(v));
}


}

else{

u = u1;
for( v = v1; v<=v2; v++){

u += 1/s;
draw(round(u), v);
}


}

dsaksena

A follow up question, if line is a 90 degree vertical line, s tends to infinity, would we just use INTMAX here and hope the discrepancy would hide with lack of resolution and user distance?

kmcrane

@dsaksena Hmm... sounds like a hack! :-) Can you think of a different way to do it, so that the algorithm clearly produces the right output in the vertical case? (Hint: try adding the calculation of s to your routine.)

dsaksena

yeah, i would calculate s = (v2 - v1)/ (u2 - u1)

since this a floating point, s can be inf and thus 1/s = 0 and finally using this in my above code, only necessary vertical pixels will be colored.

I believe my mistake was forgetting we are working with a floating point data s.

I hope this is correct.

doodooloo

if (abs(v2-v1) > abs(u2-u1))
draw pixels along the v direction (find u while v +/- 1);
else
draw pixels along the u direction (find v while u +/- 1);

I wonder if this works.

kmcrane

@dsaksena Ok, if you adopt a particular encoding for numbers (namely IEEE floating point), then you will indeed get a special symbolic value ("INF") for s, and subsequently 1/s will be zero. In other words, you're using the extended real numbers. While there are certainly some good arguments for thinking about numbers this way, there are two important practical issues to consider in the context of numerical computation, namely

1. not all programming languages/paradigms support a notion of infinity, and
2. (more importantly) IEEE floating point arithmetic can become hundreds of times slower when INFs get involved.

Here's a decent overview of the numerical issues involved with division by zero, though beware that division by zero can sink ships!

A simple (and less controversial) solution for the line rasterization algorithm would simply be to check: is |u2-u1| bigger than |v2-v1|? If so, compute s as |u2-u1|/|v2-v1|; otherwise, compute it as |v2-v1|/|u2-u1|. No great reason to invoke the strange and mysterious creature called infinity! :-)

(Of course, one should also be careful to handle the case where both u1=u2 and v1-v2...)

dsaksena

Thanks professor, @kmcrane, that is an elegant solution.