Anti-Aliasing

 

Aliasing refers to the occurrence of a false (alias) frequency alongside the correct one when conducting frequency sampling. For instance, in the realm of graphics, it manifests as jagged edges or a stair-step effect in images (source: whatis.techtarget.com). At times, this aliasing phenomenon detrimentally impacts rendering quality, causing visual disturbances for those seeking satisfaction from real-time rendering.

In the field of computer science, various Anti-aliasing (AA) techniques have been developed to mitigate aliasing issues, including SSAA (Super Sampling Anti-Aliasing), MSAA (Multi-Sampling Anti-Aliasing), FXAA (Fast Approximate Anti-Aliasing), TXAA, RSAA, TAA, QAA, MLAA, and more. These techniques aim to eliminate aliasing, resulting in cleaner and more visually appealing realistic images. Consequently, AA has seen extensive use in computer games for many years.

However, this article will not delve into the well-known AA techniques mentioned above. Instead, it will present another practical case that I have designed for a specific UI system.

No AA(left), AA(right)

Before we dive in, let's take a brief look at the fundamental graphics concepts underlying a drawing model. A traditional polygon is a shape filled with color, comprised of multiple points (vertices) and interconnected lines. Such polygons can define the boundaries of graphical components in a UI. The following illustration will provide a clearer understanding of the concepts I'm discussing.

Mapping texture onto polygon


During rasterization, which involves filling pixels within the polygon boundary, an aliasing problem can arise due to screen display limitations. Typically, a display is composed of individual light dots, which could potentially have a 1:1 mapping to each pixel. When there is a significant contrast in color tones, aliasing issues become more noticeable.

Pixels mapping to display


By introducing and incorporating intermediate color pixels along the edges, we can achieve a smoother reduction of the stair-step effect, effectively diminishing the high color contrast.

Adding intermediate pixels

 

Fast Edge Anti-Aliasing (FEAA)

 

Some AA techniques, such as FXAA and MSAA, utilize algorithms that involve a step of identifying edges in order to apply anti-aliasing (AA) selectively. Similarly, the polygon edge AA mechanism operates on the same principle, where AA is applied exclusively to the edge areas. This approach accelerates the AA process, making it highly efficient and economical by minimizing unnecessary computations. Naturally, prerequisite knowledge of edge information is essential.

However, it's important to note that this article does not cover the details of these prerequisites. Mathematical aspects of polygon and texture mapping techniques will also not be discussed here. Instead, the primary focus will be on the AA rendering step.

Assuming we have met the prerequisites by obtaining edge information and pixel colors within a polygon, we can proceed. At this point, we can create 'spans,' which are simplified data structures designed for convenience. A span encapsulates both 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 serves as a representation of pixel data that needs to be rendered onto a canvas or buffer. To illustrate, consider a scenario where span 'x' is 3, span 'y' is 3, and the length is 6. This configuration would correspond to a horizontal line extending from coordinates (3, 3) to (9, 3) within the buffer. Naturally, the pixels comprising this line are derived from the pixels contained within the span itself.

 

 

Similarly, we can generate a sequence of spans to encompass an entire polygon.

 

 

Upon reflection, it becomes evident that the 'y' field in the Span is unnecessary, as the vertical position of spans increment consistently by one pixel. As a result, the 'x' position alone becomes sufficient.

//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  
};

 

With our preparations complete, we can now proceed to draw the polygon and explore the generation of intermediate pixels. The guiding principle behind this process is remarkably straightforward.

A. Partition the polygon into two sections: left and right
B. Identify the edges of these sections
C. Determine the extent of anti-aliasing coverage for each edge line
D. Make refinements to enhance the overall quality
E. Calculate the alpha channel values


Let's now walk through each step in detail.

 

A. Partition the polygon into two sections: left and right


In essence, this anti-aliasing method involves vertical scanning of the polygon outlines. This process entails scanning the vertical edges in two directions: left and right sides, sequentially. Despite the distinct nature of a polygon's left and right sides, we can employ the same anti-aliasing algorithm for both sides due to their inherent homogeneity. As an illustration, consider a polygon depicted in the following figure. The scanning of its left and right outlines would proceed in the following order.

 

The specific appearance of the polygon is inconsequential; this scanning approach is universally applicable. This concept remains consistent regardless of the polygon's visual characteristics. Refer to the subsequent figures for visual clarity.

 

Given that we possess the pixel position and length information for a line, scanning the left and right edges becomes a straightforward task.

 

//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[y].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. Identify the edges of these sections

 

 

During this step, we analyze the position of each pixel and categorize them as belonging to edge lines. To aid your comprehension, please refer to the following illustrations.

 

From the figures above, it's evident that the focus is on the left-side edge. The key aspect of 'detecting an edge line' pertains to the continuity of pixels. When there is a change in the direction of consecutive pixels, a new line classification is warranted. To facilitate this process, seven directions have been defined.

 

However, it's worth noting that perfectly vertical and horizontal lines (corresponding to directions 1, 4, and 7) do not necessitate anti-aliasing processing, as they don't require the generation of intermediate colored pixels. Therefore, we can disregard cases 1, 4, and 7. Our focus lies solely on directions 2, 3, 5, and 6. To provide further clarity, let's examine the real-world scenarios alongside this direction classification.

 

For the implementation, begin by defining the requisite variables.

 

 

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 evident from the code snippet above, we introduce the 'tx' variable for computational convenience. Given that this AA algorithm applies to both the left and right directions, we must treat the 'x' direction uniformly. However, it's important to note that the direction is entirely reversed, resulting in an inverted increase in size. Refer to the subsequent figure to aid your understanding.

 

When considering the left direction, the difference between the current 'x' and the previous 'x' is -3. Conversely, for the right direction, this difference is 3. The outcome is inherently inverted. To address this inconsistency, the 'tx' variable was introduced. This allows us to achieve consistent results of -3 for both cases. It's important to note that the macro 'PUSH_EDGE_POINT()' is used to update the '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. Determine the extent of anti-aliasing coverage for each edge line

 

 

In the preceding step, we analyzed edge turning points to derive various edge lines: Horizontal Outside (DirOutHor), Vertical Outside (DirOutVer), Horizontal Inside (DirInHor), and Vertical Inside (DirInHor). Each of these edge lines begins from the previous point (p_edge) and extends to the current point (x, yidx). Leveraging this point information, we can ascertain the length of each line, which directly corresponds to the pixel count.

To facilitate the calculation of anti-aliasing (AA) coverage for a line, we define an AA spectrum ranging from 0 to 255. This allows us to compute the AA coverage for individual pixels along the line. Refer to the subsequent figures for a visual representation.

 

Meanwhile, the approach for handling vertical lines is not significantly different.

 

Remember, we must also consider the cases of vertical inside and horizontal inside edges. The key distinction lies in the reversed order of opacity increments.

 

An obvious but important point is that we can skip the opacity 255 case to avoid unnecessary computation.

Before delving into the implementation details, let's review additional fields required for this process.

//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, proceed to update the AA length and coverage for each scenario.

 

//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;
  }
  ...
}

 

Up to this point, we have introduced two functions: `calc_horiz_coverage()` and `calc_vert_coverage()`. Let's take a closer look at their implementations.

 

//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 visual representation illustrating the 'Tip' comment within the `calc_horiz_coverage()` function to aid your understanding.

 

 

D. Make refinements to enhance the overall quality


In essence, we have implemented the majority of the anti-aliasing process. However, there are still a few remaining cases that need to be addressed.

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

While the basic algorithm outlined above naturally addresses 1-pixel stair-step diagonal lines, it's important to approach these cases in a special manner. Allow me to illustrate the rationale behind this.

 

In the scenario depicted in the figure above, we're considering an idealized case where we can anticipate the presence of continuous 1-pixel stair-step lines. In such cases, our algorithm will naturally handle AA coverage, resembling the illustration in the figure. The outcome seems problem-free. However, the situation changes when the diagonal lines exhibit a different pattern, as illustrated below.

 

Our algorithm generates AA pixels that manifest as shown below.


While this representation is an improvement over the non-AA case, it's not optimal due to the irregularity of the stair-step pattern. The following image illustrates one such scenario. Take a closer look at the diagonal edge.

 


Now the issue becomes more apparent. So, how can we enhance this situation? One potential solution is known as 'shaving'.

 

Implementing edge shaving proves to be highly effective. It mitigates the jagged appearance by gradually transitioning the transparency of the stair-step pixels. The following figure demonstrates an actual result achieved through the application of 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);     
  }
}

 

The code implementation for edge shaving is not overly complex. Initially, it counts the number of pixels in 1-pixel stair-step cases. Following that, it handles AA for four directional lines. The function `calc_irregular_coverage()` is similar to `calc_vert_coverage()`, but it rewinds pixels vertically to calculate AA coverage for target spans. The key difference in `calc_irregular_coverage()` is that it passes an `edge_dist` argument to start the rewind from a specific point. This is necessary because `calc_irregular_coverage()` is triggered one step after the end of the 1-pixel stair-step diagonal.

 

b. Addressing the turning point.

This fine-tuning process is not overly intricate, but it focuses on addressing turning points where there is a sharp change in the incremental direction. These turning points are relevant only in the following scenarios: DirOutVer <-> DirOutHor, DirOutHor -> DirInHor, DirOutHor -> DirInVer. The determination of these cases was made through experimentation to achieve better overall quality. Refer to the subsequent figure for visualization.

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. Handling leftovers.


Finally, let's address the last aspect of the process. Given that this AA algorithm operates by analyzing two linked points (current point and previous point), it involves rewinding spans along the y-axis to apply coverage. If the scanning process abruptly concludes, there's a risk of missing the opportunity for AA coverage on the last edge. Therefore, we need to consider handling the leftover cases as well. The following code presents the complete main source code, including the handling of 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. Calculate the alpha channel values


Up to this point, we have successfully implemented the core anti-aliasing algorithm. The following code snippet provides a function that returns the alpha channel value using the coverage values we calculated earlier.

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 straightforward operation; we assume it simply multiplies a pixel with an alpha value.

Congratulations, we've completed the implementation! The next video demonstrates the rendering process using Span Edge Anti-Aliasing. Please watch it in full-screen mode at 1080p resolution for the best viewing experience.