Good exercise to challenge yourself. How might you implement the other seven cases for line drawing? (Based on the direction/slope of the line.)

For 'shallow' lines pointing to the right with -1<s<0, if s is calculated as a signed float, no change is needed, since adding the negative slope will decrement the V axis as needed.

For 'shallow' lines pointing left instead of right, we need to change how we're incrementing u. If we change u++ in the for loop to u--, we would be going in the correct direction. If u1,v1 is our starting coordinates, we also need to change v += s to v -= s to account for a flipped slope.

For 'steep' lines, the issue now is that we are always incrementing u on every loop. If |s| > 1, we will be constantly be skipping squares and will cause a very fragmented line. The extreme case is a vertical (or near vertical line), where only the origin and the very top pixel of the line would be filled in. One easy way to do fix this is instead iterate a for loop based on v, which looks like: for (v=v1; v<=v2; v++) { u += s; draw;}.

All of the 'steep' lines pointing down or to the left have the same solutions but iterating over v instead of u and flipping whatever axis we were doing operations on (compared to our shallow sloped cases).

As a thought - to what extent does this approach extend to curves? Maybe as long as your curve can be described as an equation, you can define some interface where you traverse a certain amount t (equation parameterized as f(t) => (x, y)), then cleverly sample from this to do diamond checks. Curious as to whether in practice SVG renderers just try to hand-craft things for different types of lines and only support a subset of splines and not arbritrary equations (I guess we'll find out in HW1?)

One thing I didn't understand w.r.t. using the inscribed diamond - why does it matter that it's a diamond? If we're always working in the center of the pixel, the diamond extends the full height of the pixel so it doesn't change the results relative to using the full pixel square IIUC. I assume the answer is "we're not always working in the center of a pixel", but I don't see how this algorithm would boil down to checking against the inscribed diamond in that case.

@mershy I think it might be simpler to treat lines pointed to the left by switching the endpoints. That leaves us with only 4 cases to treat. If |dv| > |du|, just do a different for loop over v, just as you said.

seven other cases can be implemented based on the procedure in this slide. Therefore, depending on the slope of the line, the algorithm could keep an axis to increment 1, and increment by the slope for the other axis. It maybe necessary to swap endpoints or decrement by 1 on the axis for certain cases.

@jochuang I suppose if one zooms in close enough, a curve can be estimated as a line through which we can find the slope of, vis-a-vis small signal linearization. Given a small enough increment, one could dynamically keep finding the slope between u1,u2,v1,v2 values that update per increment.

@jchh, @jochuang a curve's local slope can not only be estimated, but analytically realized through a derivative of many function we wish to draw. Instead of numerically recalculating the slope, we could take the derivative and get the analytical result at whatever u_x point we're at (gets more complicated with functions that aren't 1:1).

@jochuang and @mershy mentioned 'cleverly' sampling and analytically deriving the instantaneous slope/curvature, and that got me thinking about how to handle really high/extreme curvature. I liken this problem to how gradient descent often requires tuning the step size. The sampling rate can be tuned but at the cost of speed. And perhaps there are extreme or degenerate cases where this algorithm's performance is simply not acceptable.

We could go by treating 3 cases only? First we check if v1 and v2 are equal(so it is a horizontal line) or if u1 and u2 are equal(so it is a vertical line) and draw the pixels accordingly by increasing u or v. Then for the sloped cases, we make sure u1 always would be smaller than u2 and use the above algorithm. If it is slanted downward, it would still work since s would be negative.

I was quite confused about the common optimization part in this slide: how do we rewrite this algorithm to only use integer arithmetic, given that s is a floating-point number?

@mershy I like your idea of iterating a for loop based on v for those steep lines. To be honest I didn't realize drawing a line could be such tricky when we rasterize it on the screen. One improvement I propose based on your solution and @movissup's is to combining both "steep" and "shallow" cases in a greedy fashion, such that:

1) compare the value (u1, v1) and (u2, v2) to find the starting and end point for the iteration, let's say src and dst. 2) Increment by 1 on both x and y direction from src towards dst, and find the dx and dy 3) If dx > dy, then our greedy iterator will increment its coordinates by 1 on y axis. If dx < dy, then go with the x direction. 4) Keep doing step2 to step3 until we reach dst.

This way we don't need to have different implementations based on slopes, and should generalize to curves without analytically calculating the derivatives like @jestinm mentioned, as long as it's a single-valued function.

Why do we increment v before draw? In the second time through the loop, wouldn't u = u1+1 and v = v1+2s, and v round to v1+1?

I am confused about se2's point, too. Seems like we should draw before incrementing?