Anti-aliasing algorithm in Java

Question

I’m using the method setRenderingHints from the awt library to do anti-aliasing. The method provides a significant improvement in the rounded 2D objects. How does the algorithm work? What are the similarities and differences between anti-aliasing used in letters and applied in objects? I wanted to implement an own with improvements.

Answer 1

Strategies for the anti-aliasing

The algorithm of anti-aliasing in general it is not very complex, but it becomes complex when you go into the sordid details and optimizations. For comparison purposes let’s start with a simple algorithm without anti-aliasing, which I shall call To:

To: For each pixel you analyze to decide what your color is, you check inside which geometric shape this pixel is and apply the corresponding color.

And now with anti-aliasing, let’s make an algorithm B:

B: For each pixel you analyze to decide what color is, you check which fraction of its area is in each of the geometric shapes and then get the corresponding color of each of the geometric shapes and apply the color corresponding to the average weighted by the areas.

That’s basically the algorithm. It is obvious that it becomes more complicated when you start applying gradients, textures, transparencies and translucencies, reflection, etc. One simple way to deal with this complexity is to use a technique called supersampling, then creating the algorithm C:

C: Subdivide each pixel into a sufficient number of subpixels and apply the algorithm To for each subpixel. At the end, the color of the resulting pixel will be the average of the colors of the subpixels.

The result of this algorithm C must be identical or almost identical to the algorithm B, but maintaining the simplicity of the algorithm To. The problem is that its performance is much worse due to the large number of subpixels, but there is plenty of space to perform optimizations and eliminate the need to compute subpixels with known identical colors, as well as many other possible optimizations.

In addition, to calculate sufficient number of subpixels of the algorithm C, usually the number of different shades that each color component (red, green or blue) can assume is an upper bound for such a number. That is, in most cases, where each component is represented with a byte ranging from 0 to 255, then dividing a pixel into 256 subpixels (16x16) is sufficient, but perhaps this number is exaggerated and you want to subdivide into a smaller number of subpixels.

Anti-aliasing on LCD monitors

I also have to say that the algorithm used in monitors and LCD screens is different from CRT. In CRT the algorithm is basically the B or the C. On the LCD, if you do anti-aliasing of a black diagonal line on a white background, or so of letters, and you give a screenshot on the resulting image (button prt scr) and zoom in on it, the anti-aliasing will present very different colors than would be expected without the anti-aliasing. Here’s a screenshot the text "LCD" black on white background zoom 500%, next to the original image to prove this:

This is because the LCD algorithm has a significant difference to the algorithm C previously outlined: he considers that subpixels are not equal to pixels that can assume any color. On the LCD, the subpixels are monochrome, at least in my case, the blue subpixels are on the rightmost part of the pixel, the red ones on the leftmost part and the green ones in the center. By knowing the layout of the colors of the subpixels, it is possible to perform this type of anti-aliasing.

Color composition

It is important to keep in mind that although white is the result of the sum of red, green and blue, it does not mean that each of these three colors represents a third of white. This is not true, and can be easily perceived empirically by noting that pure green is bright, while pure red is matte and pure blue is dark.

In fact, the exact proportion of white light composition depends on the disposition of the different receptor cells in the retina of the observer’s eye, health conditions, weariness, age and stress of the observer, lighting conditions, brightness and contrast of the screen, the angle and direction between the screen plane and the observer’s line of sight, the screen type (reflective or reflective Anti-reflective, CRT, LED, plasma, LCD, overhead projector, Kindle, etc.), among many other variables, may even vary from one eye to another in the same person with normal and healthy vision.

But disregarding these variables that are out of the programmer’s control and assuming that the user has a healthy view and is using a good quality screen in an environment with adequate lighting, there’s a formula I saw in a book once a few years ago that gave the following ratio:

It’s a shame I don’t remember the title, but the bfavaretto gave three references to it in the comments: 1, 2 and 3, although there are small variations in the exact factors.

Keeping these brightness composition factors in mind is important in case you want to make an algorithm for anti-aliasing considering that subpixels have different colors.

This same formula given above for the white color, can be used to measure the brightness of a certain color from its red, green and blue components. According to this page, the formula recommended by W3C (similar to the one above) is:

However, this same page says that this formula may still fail. For example, the color (240, 0, 30) is slightly brighter than (80, 80, 80), and by this formula of the W3C, the first would have a brightness of 75.18 while the second would have 80 (). The reason for this is that the brightness is actually the distance that a color has in relation to black, and not just the weighted sum of the values of its shades.

If we consider all colors arranged as different internal points in a parallelepiped where one of the vertices is black, the opposite vertex is white, the vertices adjacent to black are red, green and blue and the vertices opposite to these are cyan, magenta and yellow (in this order), one of the dimensions would correspond to the value of the red component, the other of the green component and the other of the blue component. If we define the size of each of the dimensions of this parallelepiped as the intensity of the corresponding color component, then we could use the Euclidean distance from the point occupied by any color within that parallelepiped to the vertex of the black color as a measure of brightness. Thus, to calculate the intensity of a color, just use the Pythagorean theorem. If we use the values of W3C, we would arrive at this formula:

In this formula, the brightness of the above colors would be 131,62 and 80.

Completion

There are quite significant differences between the algorithms of anti-aliasing for geometric shapes in general and for text, but I do not know the details. In the background, the algorithm for anti-aliasing text consists of converting the text into geometric shapes and then applying the algorithm to geometric shapes, but there are several things that can be optimized by knowing that the content of the image is a text to be rendered, which is important because the text consists of a large number of small geometric shapes. One of the main optimizations performed is that knowing the font size, keep the letters/characters of the text already pre-rendered in some memory bitmap with transparent background and only draw such bitmap on the target area.