On 20/08/2011 01:40 PM, Warp wrote:

>    However, since pixels are squares, not circles, and if you want a very
> accurate antialiasing, you would have to calculate how much of the square
> is covered by the line. I'm not aware of a very trivial way of doing that.
> (I'm not saying it's *complicated*. I'm saying it's *not trivial*, like
> eg. a simple one-liner.)

Suppose, for argument's sake, that your line is nearly horizontal. 
Assume also that pixels are square, and the line is exactly 1 pixel thick.

Now for every pixel that the line intersects, the edge of the line cuts 
the pixel into two regions: an "inside" and an "outside" region. In the 
simplest case, we want the darkness of the pixel to be proportional to 
the area that is "inside".

(In more advanced applications, people sometimes use more complicated 
methods that take into account the actual real-world fuzziness of the 
pixels and so forth. That obviously complicates things drastically.)

Bresenham's algorithm would draw a horizontal line by iterating over all 
the X-coordinates and tracking, for each one, the fractional Y 
coordinate of the center of the line. (But represented in integral 
form.) In the standard Bresenham's algorithm, this fractional-Y is 
simply rounded to the nearest integral-Y, and that is what is plotted.

Let us assume that integral coordinates correspond to the centers of 
pixels (rather than one of their corners or something). In that case, 
the fractional-Y is the Y value of the line at the center of a column of 
pixels.

The slanted area cut by the line actually has the same area as a 
rectangle with the same center hieght. (This is why the trapezoidal rule 
for numerical integration works.)

Hence, for every X-value, we colour floor(Y) according to floor(Y) - Y, 
and ceiling(Y) according to ceiling(Y) - Y (which, you'll notice, is 
equal to 1 - floor(Y) - Y). This trivial piece of math gives us 
antialisaing almost "for free".

>> On the other hand, if you want lines that begin and end at fractional
>> coordinates, or have rounded ends or whatever, the problem becames far
>> more complicated.
>
>    The ends of the line, especially if the line is wider than one pixel
> (and especially if you use antialiasing) become a quite ambiguous problem.
> Should the line be essentially a rectangle? Or two circles joined by a
> rectangle? What if you draw two consecutive lines, what should the joint
> point look like?

Most real drawing systems let you select the kind of end-caps and join 
styles you want, and so forth. Implementing this properly is highly 
non-trivial, I would expect.

A more "interesting" problem is what happens when multiple 
different-coloured lines overlap...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message