How is the position of the sample point determined in Chen's line drawing algorithm?

Question

Referring to this paper, I don't understand how the sample point p is determined. I would like to implement this algorithm as I need the start and end points of my line to be off the integer grid. Since I can't find any ready-made code on the interwebs, I want to take a stab at it myself.

If I understand it correctly, the four points surrounding point p are on grid. The intensity of an on-grid point is determined proportional to the rectangle spanned by point p and the opposite point on grid.

In the introduction it says specifically: in this paper, we propose to simulate a sampled point (x, y) by the four pixels around (x, y) where x and y are not necessarily to be integers. Based on this method, we show that sampling infinite number of points along a line is possible since the closed-form solutions for the received intensities of pixels can be derived.

In the above paragraph I also struggle with what is meant by sampling infinite number of points. Can anyone shed some light on this? Thanks a bunch.

Answer 1

As far as I understand it, the idea behind Chen's algorithm is to define how the point p = (x, y) (x,y real) can be drawn in a "unit square" of four pixels. In section 3, it is then shown that a line can be drawn by sampling infinite points along the line and accumulating their contributions to adjacent pixels for each unit square along the line. In other words, integrate the contributions of points along the line.

While p has to lie on real coordinates for this idea to work, the issue here is that the endpoints of the line have been chosen to lie on integer coordinates anyway. I can only assume that this was done to simplify the case distinction in section 3 of the paper.

I suppose there is an easy way to extend Chen's algorithm to make it possible to draw lines with non-integer endpoints. Let's take a look at a simple case where a line starts somewhere in a unit square and leaves it on the right-hand edge. In this case, we could use Corollary 3 to recalculate the intensities given in Theorem 2. Specifically, we would need to recalculate I_(j, ⌈f(j)⌉+1), I_(j, ⌈f(j)⌉+1), and the contributions of the upper unit square in I_(j, ⌈f(j)⌉) and I_(j+1, ⌈f(j)⌉). In essence, I propose moving line segment l(q2, q3) in Fig. 3. upwards by some distance h and applying Corollary 3.

To cover cases where the line starts somewhere in the unit-square and leaves it on the top edge, we could rely on Corollary 3 again, but rotate the idea by 90°. Essentially, move line segment l(q1, q2) right by some distance w, and use the idea from Corollary 3 to recalculate the intensities of the adjacent vertices.

For a short line that never leaves the unit square, it may be possible to simply apply the two transformations described above in succession.

To back all this up with proof, I suggest finding similar closed form expressions as the ones shown in the paper. This may become a bit tedious with the more general cases, as was already hinted in the paper.