I am currently a beginner when it comes to anti-aliasing. I have read some notes online that how anti-aliasing works is that you first draw the line using an algorithm such as Bresenham's algorithm. Then you modify it to include anti-aliasing.

Now, I understand that one method of anti-aliasing is to simply imagine there being a rectangle that encompasses the line and any pixel that touches that will be turned on or filled with an RGB value.

Now if I know that area of the segment of the pixel that is cut off by the rectangle (let's assume the pixel is a circle) how would I use that area of the segment to compute the density of the colour which is from 0-1 (where 0 is very light and 1 is the darkest)?

  • There are plenty of articles out there on the web on initialising of lines for example http.developer.nvidia.com/GPUGems2/gpugems2_chapter22.html. This was a very popular topic in the 80's so you might find good articles in books like Graphics Gem. It's more a matter of Google, searching and reading yourself. But that's a VERY well document topic. – user18490 Jan 22 '17 at 9:36
  • 1
    @user18490 its a very well documented topic, only many of those documents contain systematic flaws and assuptions. So it has a lot of documentation but lot of it is simply misleading. – joojaa Jan 22 '17 at 13:27
  • @jooja, I respect your opinion but if there is a topic on which there is a lot of information it is on the topic of line anti-aliasing. It is one of the first topics that was ever researched in CG and you will find algorithms for doing this specially that were developed in the 70s/80s. I pointed the OP to Graphics Gems books in which he/she will find information. On such basic questions you have to encourage OPs to search on Google before asking such questions on here (and show they researched the topic before coming here). Maybe you can also write an answer) – user18490 Jan 22 '17 at 19:04
  • 2
    @user18490 point is that lot treatises of computer graphics neglect to define scope and limits of their assumptions. So for example many coverage based calculations forget to mention 1. That you can not assume box filter being the best possible filter. 2. Algorithm is only right is you draw one line/curve but they do not stack up correctly (leading to the conflation issue many vector engines exhibit, even tough we have known of the cause since 1980's), 3. Your output frame buffer is not linear. etc etc. – joojaa Jan 22 '17 at 19:21
up vote 1 down vote accepted

You have a background color and the color of your line, an antialiased line has additional lines drawn on either side of the first that are simply part way between the color and brightness of your origonal line and the background.

If the line you are drawing is horizontal or vertical the additional antialiasing lines (however many, depending upon the intended resulting line thickness) should be closer in color and brightness to the intended color - there is absolutely minimal antialiasing on such lines, that there is a tiny amount is due to offset subpixel rendering on some but not all matrixes.

This shows the difficulty:

Subpixels Matrix

When the lines are not horizontal or vertical it gets more complicated ...

If the additional lines drawn on each side of your line are drawn:

  • with color and brightness more closely matching the background's color then your line remains sharper and the background color near your line is fuzzier.

    or

  • with color and brightness more closely matching your line's color then your line becomes fuzzier (wider) and the background color near your line remains sharper.

  1. That means that if you intend to draw a thin line, a single pixel wide line, you would use the first option. (Make the result skinny).

  2. If you want a two pixel wide line you would choose the second option but weigh the color of the background more towards the background's color and brightness. (Make the result not as skinny as a single line, with each of the two additional lines forming almost ~50% of the total width).

  3. If you want a three pixel wide line you still use the second option but would instead weigh the color of the background more towards the line's color and brightness. (Make the result clearly much fatter than a single line).

  4. For a four pixel wide line go back to the first method where you draw two lines of the intended color and brightness surrounded by two lines using the second method, making the two lines wider. (Sort of a blending of the first and second methods)

  5. For five pixel wide lines the center is exactly your intended color, the two nearest surrounding line are very close to the color and brightness of the center line, with the outer two fairly close to the color of the center line (but less than the ones immediately next to the center line)

  6. For a six pixel wide line there are two central lines of the intended drawing color and brightness, surrounded by two very similar lines, surrounded by another two less similar to the central two's color and brightness; but still very different from (lighter or darker) than the background color.

  7. A seven pixel line or greater follows number 5 or 6 above.

The weighing of the additional lines more towards the intended color gives a sharper line, if you thought of it from a sideview analogy it would be top hat shaped. If you weighed additional lines more towards the background color the (impossible) sideview analogy is that the profile of the 2D line would be rounded or triangular. If you are drawing 2D shapes it is in your interest to weigh towards the intended color. If you are rendering a 3D shape on a 2D screen then favoring the background color blends towards subsequent lines of a different Z depth.

A simplistic but effective algorithm with good speed is the Xiaolin Wu improvement to Bresenham's line drawing algorithm to implement antialiasing.

// Pascal
function plot(x, y, c) is
    plot the pixel at (x, y) with brightness c (where 0 ≤ c ≤ 1)

// integer part of x
function ipart(x) is
    return floor(x)

function round(x) is
    return ipart(x + 0.5)

// fractional part of x
function fpart(x) is
    return x - floor(x)

function rfpart(x) is
    return 1 - fpart(x)

function drawLine(x0,y0,x1,y1) is
    boolean steep := abs(y1 - y0) > abs(x1 - x0)

    if steep then
        swap(x0, y0)
        swap(x1, y1)
    end if
    if x0 > x1 then
        swap(x0, x1)
        swap(y0, y1)
    end if

    dx := x1 - x0
    dy := y1 - y0
    gradient := dy / dx
    if dx == 0.0 then
        gradient := 1.0
    end if

    // handle first endpoint
    xend := round(x0)
    yend := y0 + gradient * (xend - x0)
    xgap := rfpart(x0 + 0.5)
    xpxl1 := xend // this will be used in the main loop
    ypxl1 := ipart(yend)
    if steep then
        plot(ypxl1,   xpxl1, rfpart(yend) * xgap)
        plot(ypxl1+1, xpxl1,  fpart(yend) * xgap)
    else
        plot(xpxl1, ypxl1  , rfpart(yend) * xgap)
        plot(xpxl1, ypxl1+1,  fpart(yend) * xgap)
    end if
    intery := yend + gradient // first y-intersection for the main loop

    // handle second endpoint
    xend := round(x1)
    yend := y1 + gradient * (xend - x1)
    xgap := fpart(x1 + 0.5)
    xpxl2 := xend //this will be used in the main loop
    ypxl2 := ipart(yend)
    if steep then
        plot(ypxl2  , xpxl2, rfpart(yend) * xgap)
        plot(ypxl2+1, xpxl2,  fpart(yend) * xgap)
    else
        plot(xpxl2, ypxl2,  rfpart(yend) * xgap)
        plot(xpxl2, ypxl2+1, fpart(yend) * xgap)
    end if

    // main loop
    if steep then
        for x from xpxl1 + 1 to xpxl2 - 1 do
           begin
                plot(ipart(intery)  , x, rfpart(intery))
                plot(ipart(intery)+1, x,  fpart(intery))
                intery := intery + gradient
           end
    else
        for x from xpxl1 + 1 to xpxl2 - 1 do
           begin
                plot(x, ipart(intery),  rfpart(intery))
                plot(x, ipart(intery)+1, fpart(intery))
                intery := intery + gradient
           end
    end if
end function

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.