4
$\begingroup$

A very tricky problem in graphics rendering is drawing thin lines ($1px$ width) that do not look jaggy. The only implementation I have seen that is very good is that in Mathematica, but their algorithm is proprietary.

Is there a well known algorithm for anti-aliasing thin lines?

$\endgroup$
3
  • $\begingroup$ @EvilJS That only antialiases straight lines. $\endgroup$ Jun 3, 2016 at 3:47
  • $\begingroup$ @What is "they"? The Xiaolin algorithm takes four inputs x1/y1 x2/y2. That's a straight line. There is also a Xiaolin "circle" algorithm, but that is only good for circles. I need an algorithm for lines of arbitrary shape. $\endgroup$ Jun 3, 2016 at 8:24
  • $\begingroup$ @EvilJS By a "thin line" I mean a 1 pixel line on a display which is from 72 to 90 pixels per inch. $\endgroup$ Jun 3, 2016 at 15:13

2 Answers 2

4
$\begingroup$

You can use Xiaolin Wu algorithm, but the concept is not restricted to straight lines, it handles circles, ellipses, any kind of functions. Moreover this is concept of fast antialiasing, if you need some polyline you have to apply it for every segment. If you meant curves, these are locally flat segments, so this concept is still applicable.

The thin line might described $1px$ lines, but if you need thinner width (less than $1px$) the common algorithm that comes to mind is Gupta-Sproull, which is not that common due to computation time. The same is applicable here like in the Wu case, it is not limited to straight lines.

The idea of drawing lines (probably with Bresenham) and then blurring is more computationally expensive and weights are not normalised, which gives feeling of thicker lines.

The concepts described can easily be extended to thicker lines (using Bresenham and applying antialiasing to the outter layer) or even varying width lines (with Bresenham extension - the Murphy algorithm).

Techniques like MSAA or FXAA are too expensive, unless implemented on GPU with a lots of lines and no concern about perceptible width. After reading about Mathematica, it uses MLAA (Morphological Anti-Aliasing), graphics is rendered on GPU, also Mathematica's reference supports this statement merely by looking at de Moiré patterns.

$\endgroup$
2
$\begingroup$

Not really an answer, but I've had an ongoing similar problem with my gpl'ed program http://www.forkosh.com/mimetex.html and tried several solutions, all of them variations on low-pass filter antialiasing or supersampling. My code's buried in the 20K lines of mimetex.c, which you can see by clicking the "mimeTeX listing" link under "Related Pages" on the top left-hand side of the preceding link. In particular, line 16060 starts a switch() that currently selects case 3.

That case is loosely based on http://netpbm.sourceforge.net/doc/pnmalias.html which is netpbm's antialiasing algorithm. But I messed with it, more or less as follows. Any pixel of a jaggy pixelized line image is surrounded by nearest neighbor pixels: by eight immediately nearest neighbors (it's the center pixel of a 3x3 grid), and by 15 two-deep nearest neighbors (near center of a 4x4 grid). If those nearest neighbors are either black or white, then that's $2^8$ or $2^{15}$ possible cases. I'd have preferred the 4x4 case, but that was too many cases to enumerate.

However, you don't even need $2^8$ since rotations and reflections of the grid yield self-similar patterns that you want to treat all the same way. And for the 3x3 grid, that left me 51 unique nearest neighbor patterns. And I just carefully tested the various ways of treating the center pixel of each such pattern (separate treatment depending on whether the center pixel started out black or white), and ad hoc selected what looked best to my eyes.

Then long lines of any shape just work themselves out as you antialias the overall image pixel-by-pixel. Note that I started out with jaggy-looking thin lines that were originally black&white, and turned them into somewhat less jaggy grayscale lines. But they're still jaggier than I'd hoped for, despite some non-trivial (to me) amount of effort.

Anyway, please let me know if you come across anything really good. And I'll keep watching this thread for a better answer than mine.

$\endgroup$
1
  • $\begingroup$ That is very interesting. This kind of mirrors my efforts which have so far indicated that it is a difficult and unsolved problem, at least for implementing as a linear time or quadratic time algorithm. $\endgroup$ Jun 3, 2016 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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