**Anti-Aliasing**

Aliasing is the generation of a false (alias) frequency along with the correct one when doing frequency sampling. For instance, in graphics world, it produces a jagged edge or stair-step effect for images(src: whatis.techtarget.com). Sometimes this aliasing phenomenon is bad for rendering quality. It disturbs people do satisfied the visuals from the real-time rendering.

In computer science, some have developed a sort of Anti-Aliasing(AA) techniques such as SSAA(Super Sampling Anti-Aliasing), MSAA(Multi-Sampling Anti-Aliasing), FXAA(Fast Approximate Anti Aliasing), TXAA, RSAA, TAA, QAA, MLAA, etc to get rid of aliasing, to get cleaner and nicer realistic visual images. Thereby, AA have been many used in computer games for years.

But In this article, I'm not going to take cover those famous AA techniques but share you another practical case that I designed for a certain UI system.

*No AA(left), AA(right)*

Before get jumped in, let's review the basic graphics concept for a drawing model briefly. The traditional polygon is a shape filled with color. One polygon has multiple points(vertices) and lines which are connecting to each other. This polygon could be used for a shape(boundary) of the graphical components in the UI. Next figure helps you understand what I'm talking about.

*Mapping texture onto polygon*

While the rasterization, filling pixels into the polygon boundary, it may encounter the aliasing problem due to the screen display limitation. Normally, a display is consisted with lighting dots which are possibly 1:1 mapping to each pixel. As far as the color-tone contrast is high, we could see the aliasing issue more easily.

*Pixels mapping to display*

We could generate and add intermediate color pixels on the edges, it will reduce the stair-step effect smoothly by reducing high color contrast.

*Adding intermediate pixels*

**Polygon Edge Anti-Aliasing (****Hermetic AA Method)**

As some of AA techniques such as FXAA, MSAA, AA algorithm requires a step for finding edges for applying AA partially. Here polygon edge AA mechanism is same as them. It applies AA processing only to edge area. This speeds up AA, it's very cheap and fast method by avoiding unnecessary processing, of course, we need to know edge information as prerequisite.

In this article, we don't take cover the prerequisite. Also, we don't take cover mathematics for polygon and texture mapping techniques. More than them, I'd like to more focus on AA rendering step.

So, let's say, we satisfied those prerequisite having information for edges and the pixel colors which were filled with a polygon. Here we could construct a span which is somewhat simplified data for convenient. A span contains edge and pixel information for a horizontal line.

```
//A span structure for a horizontal line
struct Span {
int x, y; //Line start point
int length; //Line length
Pixel* pixels; //pixel data. Size is line length.
};
```

This span indicates pixel data which should be drawn onto a canvas(buffer). For instance, if span x is 3, span y is 3 and length is 6, this will be a horizontal line from (3, 3) to (9, 3) on a buffer. Of course, the pixels of the line come from the pixels in the span.

Likewise, we could construct a series of spans for a polygon.

Come to think of it, we don't need y field in Span because y position of spans are always incremental by 1 pixel. Consequently, we just need this.

```
//A span structure for a horizontal line
struct Span {
Pixel* pixels; //Pixel data. Size is line length.
int x; //Line start point x
int length; //Line length
};
//A polygon image structure for drawing
struct PolygonImage {
Span *spans; //Span data. Size is span length.
int y; //Span start point y
int length; //Span length
};
```

Now, we are ready to draw a polygon, it's time to consider how to generate intermediate pixels. The overall rule is very simple.

**
A. Divide a polygon by 2 sections, left and right.
B. Find edge lines.
C. Decide anti-aliasing coverage for an edge line.
D. Fine-tune for better quality.
E. Compute alpha channel.
**

Then let's go through it step by step.

**A. Divide a polygon by 2 sections, left and right**

Basically, this AA method scans outlines vertically. To do this, Scan vertical edges for two directions, left and right sides in the order. Even though left and right sides of a polygon are different, we could apply same AA algorithm for them because they are basically homogeneous. For instance, if there is a polygon (see next figure), we could scan the left and right outline in order.

Since we know pixel position and length for a line, we could scan the left and right edges easily.

```
//eidx (edge index) 0: left edge, 1: right edge
void calc_aa_coverage(PolygonImage *polygon, int eidx)
{
//Scan edge vertically
for (int yidx = 0; yidx < polygon->length; yidx++)
{
//Decide left or right
int xidx = 0;
if (eidx == 1) xidx = polygon->spans[yidx].length - 1;
```

//x, y: position of current edge
int x = polygon->spans[yy].x;
if (eidx == 1) x += polygon->spans[yidx].length;
int y = polygon->y + yidx;
//Access the pixel on the edge?
Pixel *p = &polygon->spans[yidx].pixels[xidx];
}
}
//Somewhere calls this function to apply AA... on rendering?
void apply_aa(PolygonImage *polygon)
{
//One function enough to scan 2 edges.
//Scan left edge
calc_aa_coverage(polygon, 0);
//Scan right edge
calc_aa_coverage(polygon, 1);
}

**B. Find edge lines**

In this step, we read each pixel's position and classify edge lines. For your understanding, see next figures.

As you can see above figures, Spotlights on left side edge. The point of 'finding an edge line' is how pixel continues. If the continual pixel direction is changed, we should classify a new line. For doing this, we define 7 directions.

However, perfect vertical and horizontal lines (above 1, 4, 7 directions) actually don't require AA processing, they don't need to generate any intermediate color pixels. So here we don't care 1, 4, 7 cases. Only matter is to 2, 3, 5, 6 directions. Let's see actual scenario along with this direction classification.

For implementing, define necessary variables first.

And code.

```
//Define edge direction
#define DirOutHor 0x0011 //Horizontal Outside
#define DirOutVer 0x0001 //Vertical Outside
#define DirInHor 0x0010 //Horizontal Inside
#define DirInVer 0x0000 //Vertical Inside
#define DirNone 0x1000 //Non specific direction
//eidx (edge index) 0: left edge, 1: right edge
void calc_aa_coverage(PolygonImage *polygon, int eidx)
{
Point p_edge = {-1, -1}; //previous edge point
Point edge_diff = {0, 0}; //temporary use for point's distance (between previous and current)
int tx[2] = {0, 0}; //This is just for computation convenience.
int ptx[2]; //Back up previous tx here.
int prev_dir = DirNone; //previous line direction
int cur_dir = DirNone; //current line direction
//Scan edge vertically
for (int yidx = 0; yidx < polygon->length; yidx++)
{
//x, y: position of current edge
int x = polygon->spans[yidx].x;
if (eidx == 1) x += polygon->spans[yidx].length;
int y = polygon->y + yidx;
//Ready tx. Since left and right edge' faces are inverted, previous and current x should be inverted as well.
if (eidx == 0)
{
tx[0] = p_edge.x;
tx[1] = x;
}
else
{
tx[0] = x;
tx[1] = p_edge.x;
}
//Compute distance between previous and current edge
edge_diff.x = (tx[0] - tx[1]);
edge_diff.y = (yidx - p_edge.y);
//Evaluate Edge direction
if (edge_diff.x > 0)
{
if (edge_diff.y == 1) cur_dir = DirOutHor;
else cur_dir = DirOutVer;
}
else if (edge_diff.x < 0)
{
if (edge_diff.y == 1) cur_dir = DirInHor;
else cur_dir = DirInVer;
}
else cur_dir = DirNone;
switch (cur_dir)
{
case DirOutHor:
{
//TODO:
PUSH_EDGE_POINT();
}
break;
case DirOutVer:
{
//TODO:
PUSH_EDGE_POINT();
}
break;
case DirInHor:
{
//TODO:
PUSH_EDGE_POINT();
}
break;
case DirInVer:
{
//TODO:
PUSH_EDGE_POINT();
}
break;
}
if (cur_dir != DirNone) prev_dir = cur_dir;
}
}
```

As you can see the above code, we declare 'tx' variable for computation convenient. Since this AA algorithm is used for left, right both directions, we need to handle x direction in the same way. However, direction is totally inverted, the size increase is inverted as well. See next figure for your understanding.

In case of left, current x - previous x is -3. On the other hand in case of right, it's value is 3. The result is solely inverted. To fix this, tx came out. We could get both results same -3. In the meanwhile, PUSH_EDGE_POINT() is a macro to update p_edge and ptx values.

```
#define PUSH_EDGE_POINT() \
{ \
p_edge.x = x; \
p_edge.y = yidx; \
ptx[0] = tx[0]; \
pty[1] = ty[1]; \
}
```

**C. Decide anti-aliasing coverage for an edge line.**

In the previous step, we examined edge turning points, obtained all edge lines, Horizontal Outside(DirOutHor), Vertical Outside(DirOutVer), Horizontal Inside(DirInHor), Vertical Inside(DirInHor). Each edge lines start from previous point(p_edge) to current point(x, yidx). Using these point's information, we can examine length of the line, exactly pixel count. If we define AA spectrum from 0 to 255 for a line, we could calculate each pixels AA coverage for a line. See next figures.

In the meanwhile, vertical line is not too different.

Keep in mind, we should examine vertical inside and horizontal inside as well. The only different is incremental order of opacity is reversed.

Trivial but obviously, we can skip for opacity 255 case for avoiding meaningless computation.

Before see implementation bodies, check additional fields for this.

```
//A span structure for a horizontal line
struct Span {
Pixel* pixels; //Pixel data. Size is line length.
int x; //Line start point x
int length; //Line length
int aa_length[2]: //Opacity(less than 255) pixels count. [0]: left edge, [1]: right edge
int aa_coverage[2]; //Coverage unit. [0]: left edge, [1]: right edge
};
```

Now, update AA length and coverage for each case.

```
//eidx (edge index) 0: left edge, 1: right edge
void calc_aa_coverage(PolygonImage *polygon, int eidx)
{
...
switch (cur_dir)
{
case DirOutHor:
{
```**calc_horiz_coverage(polygon, eidx, yidx, tx[0], tx[1]);**
PUSH_EDGE_POINT();
}
break;
case DirOutVer:
{
**calc_vert_coverage(polygon, eidx, yidx, edge_diff.y, true);**
PUSH_EDGE_POINT();
}
break;
case DirInHor:
{
//Here inner case is one step faster than outer, so pass y - 1 than y.
**calc_horiz_coverage(polygon, eidx, (yidx - 1), tx[0], tx[1]);**
PUSH_EDGE_POINT();
}
break;
case DirInVer:
{
**calc_vert_coverage(polygon, eidx, yidx, edge_diff.y, false);**
PUSH_EDGE_POINT();
}
break;
}
...
}

So far, two functions were introduced - calc_horiz_coverage() and calc_vert_coverage(). Let's see them.

```
//y: current edge y position, rewind: vertical length, reverse: decides the direction whether opacity increase or decrease on y axis
void calc_vert_coverage(PolygonImage *polygon, int eidx, int y, int rewind, bool reverse)
{
if (eidx == 1) reverse = !reverse;
int coverage = (255 / (rewind + 1));
int tmp;
for (int ry = 1; ry < (rewind + 1); ry++)
{
tmp = y - ry;
if (tmp < 0) return; //just in case.
polygon->spans[tmp].aa_length[eidx] = 1; //vertical lines AA pixel is only one.
if (reverse) polygon->spans[tmp].aa_coverage[eidx] = (255 - (coverage * ry));
else polygon->spans[tmp].aa_coverage[eidx] = (coverage * ry);
}
}
//y: current edge y position, x: current edge x position, y: previous edge x position
void calc_horiz_coverage(PolygonImage *polygon, int eidx, int y, int x, int x2)
{
//Tip: edge point pixels could be targeted AA twice in horizontal and vertical ways. In this case, we apply horizontal first. See next figure for your understand.
if (polygon->spans[y].aa_length[eidx] < abs(x - x2))
{
polygon->spans[y].aa_length[eidx] = abs(x - x2);
polygon->spans[y].aa_coverage[eidx] = (255 / (polygon->spans[y].aa_length[eidx] + 1));
}
}
```

Here is a figure about Tip comment in calc_horiz_coverage() to understand you.

**D. Fine-tune for better quality.**

Actually, we implemented most parts of AA. However, it still remains a few cases to deal with yet.

**a. 1 pixel stair-step diagonal lines**

Even though above basic algorithm naturally take deal 1 pixel stair-step diagonal lines, we need to take deal it in a special way. Let me show you the reason.

In the above figure, it's a bit ideal case if we can expect continuous 1 pixel stair-step lines. If it does, actually we don't need to take care of it anymore, our algorithm will take deal AA coverage like the illustration in the figure. It looks no problems in the result. However, what if the diagonal lines look like this?

Our algorithm generates AA pixels looking like this.

This is still better than Non-AA case but it doesn't very good because the stair-step pattern is irregular. Next picture is a one of the cases. Please look at the diagonal edge seriously.

Now the problem looks more clear. If so, how we can improve it? One solution is shaving.

Shaving edge works quite well. It removes jiggling points by transparenting stair-step pixels gradually. Next figure shows you an actual result adopting this method.

And code.

```
void calc_aa_coverage(PolygonImage *polygon, int eidx)
{
...
//Scan edge vertically
for (int yidx = 0; yidx < polygon->length; yidx++)
{
...
//Evaluate Edge direction
if (edge_diff.x > 0)
{
if (edge_diff.y == 1) cur_dir = DirOutHor;
else cur_dir = DirOutVer;
}
else if (edge_diff.x < 0)
{
if (edge_diff.y == 1) cur_dir = DirInHor;
else cur_dir = DirInVer;
}
else cur_dir = DirNone;
```**//1 pixel stair-step diagonal increase
if (cur_dir == prev_dir)
{
if ((abs(edge_diff.x) == 1) && (edge_diff.y == 1))
{
//Don't do anything, just keep tracking next point...
++diagonal;
PUSH_EDGE_POINT();
continue;
}
}**
switch (cur_dir)
{
case DirOutHor:
{
calc_horiz_coverage(polygon, eidx, yidx, tx[0], tx[1]);
if (diagonal > 0)
{
**calc_irregular_coverage(polygon, eidx, yidx, diagonal, 0, true);**
diagonal = 0;
}
PUSH_EDGE_POINT();
}
break;
case DirOutVer:
{
calc_vert_coverage(polygon, eidx, yidx, edge_diff.y, true);
if (diagonal > 0)
{
**calc_irregular_coverage(polygon, eidx, yidx, diagonal, edge_diff.y, false);**
diagonal = 0;
}
PUSH_EDGE_POINT();
}
break;
case DirInHor:
{
//Here inner case is one step faster than outer, so pass y - 1 than y.
calc_horiz_coverage(polygon, eidx, (yidx - 1), tx[0], tx[1]);
if (diagonal > 0)
{
**calc_irregular_coverage(polygon, eidx, yidx, diagonal, 0, false);**
diagonal = 0;
}
PUSH_EDGE_POINT();
}
break;
case DirInVer:
{
calc_vert_coverage(polygon, eidx, yidx, edge_diff.y, false);
if (diagonal > 0)
{
**calc_irregular_coverage(polygon, eidx, yidx, diagonal, edge_diff.y, true);**
diagonal = 0;
}
PUSH_EDGE_POINT();
}
break;
}
...
}
//y: current edge y position, diagonal: vertical length to rewinding, edge_dist: distance to the previous edge y position, reverse: decides the direction whether opacity increase or decrease on y axis
void calc_irregular_coverage(PolygonImage *polygon, int eidx, int y, int diagonal, int edge_dist, bool reverse)
{
if (eidx == 1) reverse = !reverse;
int coverage = (255 / (diagonal + 1));
int tmp;
for (int ry = 0; ry < (diagonal + 1); ry++)
{
tmp = y - ry - edge_dist;
if (tmp < 0) return; //just in case.
polygon->spans[tmp].aa_length[eidx] = 1; //vertical lines AA pixel is only one.
if (reverse) polygon->spans[tmp].aa_coverage[eidx] = 255 - (coverage * ry);
else polygon->spans[tmp].aa_coverage[eidx] = (coverage * ry);
}
}

Code is not too complex. Firstly, it just counts pixels number for 1 pixel stair-step case. After that, it deals with AA for four directional lines. calc_irregular_coverage() is almost same with calc_vert_coverage(). It just rewinds pixels vertically in order to compute AA coverage for target spans. The only different of calc_irregular_coverage() is, it passes edge_dist argument to jump to a start point to rewind. The reason is calc_irregular_coverage() will be triggered one step after of the end of the 1 pixel stair-step diagonal.

**b. The turning point**

This fine-tune is not serious but this turning point indicates that when the incremental direction is sharply changed. The incremental directions are only under this scenario. DirOutVer <-> DirOutHor, DirOutHor -> DirInHor, DirOutHor -> DirInVer. I decided those cases experimentally for better quality. See next figure.

```
void calc_aa_coverage(PolygonImage *polygon, int eidx)
{
...
switch (cur_dir)
{
case DirOutHor:
{
calc_horiz_coverage(polygon, eidx, yidx, tx[0], tx[1]);
if (diagonal > 0)
{
calc_irregular_coverage(polygon, eidx, yidx, diagonal, 0, true);
diagonal = 0;
}
/* Increment direction is changed: Outside Vertical -> Outside Horizontal */
```**if (prev_dir == DirOutVer) calc_horiz_coverage(polygon, eidx, p_edge.y, ptx[0], ptx[1]);**
PUSH_EDGE_POINT();
}
break;
case DirOutVer:
{
calc_vert_coverage(polygon, eidx, yidx, edge_diff.y, true);
if (diagonal > 0)
{
calc_irregular_coverage(polygon, eidx, yidx, diagonal, edge_diff.y, false);
diagonal = 0;
}
/* Increment direction is changed: Outside Horizontal -> Outside Vertical */
**if (prev_dir == DirOutHor) calc_horiz_coverage(polygon, eidx, p_edge.y, ptx[0], ptx[1]);**
PUSH_EDGE_POINT();
}
break;
case DirInHor:
{
//Here inner case is one step faster than outer, so pass y - 1 than y.
calc_horiz_coverage(polygon, eidx, (yidx - 1), tx[0], tx[1]);
if (diagonal > 0)
{
calc_irregular_coverage(polygon, eidx, yidx, diagonal, 0, false);
diagonal = 0;
}
/* Increment direction is changed: Outside Horizontal -> Inside Horizontal */
**if (prev_dir == DirOutHor) calc_horiz_coverage(polygon, eidx, p_edge.y, ptx[0], ptx[1]);**
PUSH_EDGE_POINT();
}
break;
case DirInVer:
{
calc_vert_coverage(polygon, eidx, yidx, edge_diff.y, false);
if (diagonal > 0)
{
calc_irregular_coverage(polygon, eidx, yidx, diagonal, edge_diff.y, true);
diagonal = 0;
}
/* Increment direction is changed: Outside Horizontal -> Inside Vertical */
**if (prev_dir == DirOutHor) calc_horiz_coverage(polygon, eidx, p_edge.y, ptx[0], ptx[1]);**
PUSH_EDGE_POINT();
}
break;
}
...
}

**c. Leftovers **

This is the last part we are going to look at. Since this AA algorithm looks for and examines two points(current point, previous point) which are linking together, it rewinds the spans along the y-axis and apply coverage. If the scanning reaches to the end all of sudden, it misses AA chance for the last edge. So we need to take care the leftovers additionally. Next code is full main source code including the leftovers.

```
void calc_aa_coverage(PolygonImage *polygon, int eidx)
{
Point p_edge = {-1, -1}; //previous edge point
Point edge_diff = {0, 0}; //temporary use for point's distance (between previous and current)
int tx[2] = {0, 0}; //This is just for computation convenience.
int ptx[2]; //Back up previous tx here.
int prev_dir = DirNone; //previous line direction
int cur_dir = DirNone; //current line direction
//Scan edge vertically
for (int yidx = 0; yidx < polygon->length; yidx++)
{
//x, y: position of current edge
int x = polygon->spans[yidx].x;
if (eidx == 1) x += polygon->spans[yidx].length;
int y = polygon->y + yidx;
//Ready tx. Since left and right edge' faces are inverted, previous and current x should be inverted as well.
if (eidx == 0)
{
tx[0] = p_edge.x;
tx[1] = x;
}
else
{
tx[0] = x;
tx[1] = p_edge.x;
}
//Compute distance between previous and current edge
edge_diff.x = (tx[0] - tx[1]);
edge_diff.y = (yidx - p_edge.y);
//Evaluate Edge direction
if (edge_diff.x > 0)
{
if (edge_diff.y == 1) cur_dir = DirOutHor;
else cur_dir = DirOutVer;
}
else if (edge_diff.x < 0)
{
if (edge_diff.y == 1) cur_dir = DirInHor;
else cur_dir = DirInVer;
}
else cur_dir = DirNone;
//Evaluate Edge direction
if (edge_diff.x > 0)
{
if (edge_diff.y == 1) cur_dir = DirOutHor;
else cur_dir = DirOutVer;
}
else if (edge_diff.x < 0)
{
if (edge_diff.y == 1) cur_dir = DirInHor;
else cur_dir = DirInVer;
}
else cur_dir = DirNone;
//1 pixel stair-step diagonal increase
if (cur_dir == prev_dir)
{
if ((abs(edge_diff.x) == 1) && (edge_diff.y == 1))
{
//Don't do anything, just keep tracking next point...
++diagonal;
PUSH_EDGE_POINT();
continue;
}
}
switch (cur_dir)
{
case DirOutHor:
{
calc_horiz_coverage(polygon, eidx, yidx, tx[0], tx[1]);
if (diagonal > 0)
{
calc_irregular_coverage(polygon, eidx, yidx, diagonal, 0, true);
diagonal = 0;
}
/* Increment direction is changed: Outside Vertical -> Outside Horizontal */
if (prev_dir == DirOutVer) calc_horiz_coverage(polygon, eidx, p_edge.y, ptx[0], ptx[1]);
PUSH_EDGE_POINT();
}
break;
case DirOutVer:
{
calc_vert_coverage(polygon, eidx, yidx, edge_diff.y, true);
if (diagonal > 0)
{
calc_irregular_coverage(polygon, eidx, yidx, diagonal, edge_diff.y, false);
diagonal = 0;
}
/* Increment direction is changed: Outside Horizontal -> Outside Vertical */
if (prev_dir == DirOutHor) calc_horiz_coverage(polygon, eidx, p_edge.y, ptx[0], ptx[1]);
PUSH_EDGE_POINT();
}
break;
case DirInHor:
{
//Here inner case is one step faster than outer, so pass y - 1 than y.
calc_horiz_coverage(polygon, eidx, (yidx - 1), tx[0], tx[1]);
if (diagonal > 0)
{
calc_irregular_coverage(polygon, eidx, yidx, diagonal, 0, false);
diagonal = 0;
}
/* Increment direction is changed: Outside Horizontal -> Inside Horizontal */
if (prev_dir == DirOutHor) calc_horiz_coverage(polygon, eidx, p_edge.y, ptx[0], ptx[1]);
PUSH_EDGE_POINT();
}
break;
case DirInVer:
{
calc_vert_coverage(polygon, eidx, yidx, edge_diff.y, false);
if (diagonal > 0)
{
calc_irregular_coverage(polygon, eidx, yidx, diagonal, edge_diff.y, true);
diagonal = 0;
}
/* Increment direction is changed: Outside Horizontal -> Inside Vertical */
if (prev_dir == DirOutHor) calc_horiz_coverage(polygon, eidx, p_edge.y, ptx[0], ptx[1]);
PUSH_EDGE_POINT();
}
break;
}
if (cur_dir != DirNone) prev_dir = cur_dir;
}
```**//leftovers...?
if ((edge_diff.y == 1) && (edge_diff.x != 0))
{
//Finished during horizontal increment.
calc_horiz_coverage(polygon, eidx, yidx, tx[0], tx[1]);
}
else
{
//Finished during vertical increment
calc_vert_coverage(polygon, eidx, yidx, edge_diff.y, (prev_dir & 0x00000001));
}**
}

**E. Compute alpha channel.**

So far, we implemented the core algorithm of AA. Next code is just for a code snippet that returns Alpha channel value using coverage that we computed before.

```
void _aa_coverage_apply(Span *span)
{
for (int i = 0; i < span->length; i++)
{
//Left Edge Anti Anliasing
if (span->aa_length[0] <= i)
{
Pixel val = MUL256(span->pixels[i], (i + 1) * span->aa_coverage[0]);
}
//Right Edge Anti Aliasing
if (i >= span->length - span->aa_length[1])
{
Pixel val = MUL256(span->pixels[i], (span->aa_length[1] - (i - (span->length - span->aa_length[1]))) * span->aa_coverage[1]);
}
}
}
```

MUL256() is a trivial, we suppose that it just multiply a pixel with alpha value.

It's done! Next video demonstrates the this Polygon Edge Anti-Aliasing rendering. Please see with 1080p full screen.