All points crossed by a line

Question

I need to find all points that are on a line. I tried Bresenham's algorithm but it doesn't work on the following case:

 (0, 0)
.-----------+-----------+-----------.
|...........|           |           |
|...........|           |           |
|.....XXXX..|           |           |
|........XXXX           |           |
|...........XXXXX       |           |
+-----------+---XXXX----+-----------+
|           |......XXXXX|...........|
|           |..........XXXX.........|
|           |...........|.XXXXX.....|
|           |...........|...........|
|           |...........|...........|
`-----------+-----------+-----------´
                              (2, 1)

X is the actual line, . is what Bresenham's algorithm returns, notice the line crosses (1, 0) but it is not marked.
How can I find all the pixels a line goes through efficiently? I don't need this anti-aliased so I think Wu's algorithm is an overkill. The line endpoints are in middle of the pixels.

To reference the algorithm I have is:

int dx = System.Math.Abs(x0 - x1);
int dy = System.Math.Abs(y0 - y1);

int sx = x0 < x1 ? 1 : -1;
int sy = y0 < y1 ? 1 : -1;

int err = dx - dy;

int lx = x0;
int ly = y0;

for(int i = 0; true; i++)
{
    Mark(x0, y0);

    if(x0 == x1 && y0 == y1)
        break;

    int e2 = err * 2;
    if(e2 > -dy)
    {
        err -= dy;
        x0 += sx;
    }
    if(e2 < dx)
    {
        err += dx;
        y0 += sy;
    }
}

Lugger

Answer 1

Well, just implement the obvious straightforward algorithm: start from one end of the line, find which side of the starting square it crosses, jump to the corresponding adjacent square... and so on. Walk until you reach the finish square.

The simplest way to implement it in integers would be to switch to superpixel precision: just multiply everything by a constant factor. The difficult part begins when you discover that you don't have enough integer range to multiply it sufficiently... I don't know whether this is the case in your case.

Mernamero

Using the starting point, the slope of the line and the size of each 'cell', you can find which side the line will cross first. – Contort