Aliasing & Anti-Aliasing in CGI

Aliasing Artifacts

In CGI, television and movies, Aliasing is also referred to as: Jaggies, Face Popping, Edge Crawling, Narrow Faces Breakup, Moiré Patterns and Distracting Artifacts. Anti-aliasing (AA) techniques can be used to minimize these distracting artifacts.

Single Point Sample (No Anti-Aliasing)

When using single point sample per pixel, there are distracting artifacts in CGI images, referred to as aliasing or jaggies.

Jaggies and Edge Crawling

When images are computed using a single sample per pixel, they show aliasing artifacts such as stairsteps on feature edges (jaggies). Refer to Figure 2.

In dynamic scenes, aliasing artifacts are amplified, resulting in edge crawling, line breaking and small features popping in-and out.

Narrow Face Breakup

When the width of narrow faces is near or smaller than the pixel size, the rendering results in Narrow Face Breakup. Refer to Figure 3

Face popping

Face popping is a temporal artifact. It shows with objects going in-and-out of scenes when some dimensions of displayed polygon faces are smaller than the pixel size.

In Figure 4 there are examples of face popping. These tiny faces are displayed only when the pixel sample point is inside of the faces. In a moving scene, this results into faces popping in-and-out of the scene.

Z-Buffer (or Depth-Buffer)

In 3D space, objects are made of many triangular faces. When these triangles are projected onto a 2D image, points in 3D space with coordinate V=(x, y, z) end up with 2D image coordinates V=i(xi, yi), where:

xi=x/z; yi=y/z

3D Distance Coordinate z and Depth in Image Coordinate zi:

The projected image is on a plane at distance z==1 from the viewpoint. So, each point in 3D space can be considered to be on a 4-components coordinate system V=((x, y, z,1).

After projection, the vector V is projected onto a 2D vector Vi in the projection plane (image):

Vi = V/z = (x/z, y/z, z/z, 1/z) = (xi, yi, 1, zi), where zi = 1/z

The projected vector has a 2D coordinate (xi, yi) on the image plane and is also associated with a depth coordinate represented by zi=1/z. Or:

Vi=(xi, yi, zi)

Since the coordinate V=(x, y, z) is linear in the 3D space, Vi=(xi, yi, zi) is also linear in the 2D space. As a consequence:

The depth coordinate zi linear in the 2D space (image), while the distance z (from 3D space) is non-linear in the 2D space. On the other hand, the distance z cannot be linearly interpolated in the projected space…

Depth Coordinate zi:

The depth coordinate zi is linear in image coordinates and can be interpolated.

The image depth coordinate, zi, is used to determine which triangle is in front of another. During the image computation, the image is stored into 2 types of image buffers:

 Color-Buffer and Z-Buffer.

The color components (R, G, B) of the closest face (with max zi) are stored in the Color-Buffer and the depth coordinate zi is stored in the Z-Buffer. For the Color, there is a double buffer: one to build the image and one to display the previously computed image.

When 2 triangles are too close in depth, aliasing might result, when there is not enough depth accuracy to determine which one is the closest.

Definitions from Wikipedia

 Refer to definitions for Aliasing, Jaggies, Moiré Pattern from Wikipedia and Internet
    Aliasing:       https://en.wikipedia.org/wiki/Aliasing
    Jaggies:         https://en.wikipedia.org/wiki/Jaggies
    Moiré Pattern: https://en.wikipedia.org/wiki/Moir%C3%A9_pattern
    Z-Buffer or Depth-Buffer    https://www.geeksforgeeks.org/z-buffer-depth-buffer-method/

Early 3D Graphics CGI Systems

CGI was pioneered in the late 1960s by David C. Evans and Ivan Sutherland (E&S) at the University of Utah. Many of the early CGI contributors also came from the University of Utah. Among them were Jim Clark (founder of Silicon Graphics and co-founder of Netscape), Ed Catmull (co-founder of Pixar), John Warnock of Adobe, Scott P. Hunter of Oracle, Franklin C. Crow and Jim Blinn. In 1968, Dave Evans and Ivan Sutherland founded the first computer graphics HW company, Evans & Sutherland (E&S).

Point Sampling and Area Sampling

In the 1970s, many algorithms were developed for 3D graphics, using a Z-Buffer (or Depth Buffer) approach and single point sampling. At the same time, there was a need for fast real-time solutions used in flight simulators for the US military and NASA. One of the main requirements of these RT CGI systems was Speed and Anti-Aliasing. Aliasing Artifacts were not tolerated and were considered as negative training. Michel A Rohner, from Link Flight Simulation in Sunnyvale CA, was one of the main designers of the Link DIG RT CGI system that was used in the Shuttle Mission Simulator (SMS). Four Link DIGs were delivered to NASA in Houston to train In the 1970s, many algorithms were developed for 3D graphics, using a Z-Buffer (or Depth Buffer) approach and single point sampling. At the same time, there was a need for fast real-time solutions used in flight simulators for the US military and NASA. One of the main requirements of these RT CGI systems was Speed and Anti-Aliasing. Aliasing Artifacts were not tolerated and were considered as negative training. Michel A Rohner, from Link Flight Simulation in Sunnyvale CA, was one of the main designers of the Link DIG RT CGI system that was used in the Shuttle Mission Simulator (SMS). Four Link DIGs were delivered to NASA in Houston to train

At that time, the 3D CGI industry used the fastest computers, like the Cray-1 supercomputer, to compute beautiful 3D images for TV ads and movies, using single point or multi point sampling. On the other hand, there was only 3 companies (E&S, GE and Link) that could design the fastest RT CGI systems with AA. These systems were used in flight simulators for training US military pilots and NASA astronauts.

Later on in 1990s, video graphics adapters with 3D appeared for the IBM PC market. Oak Technology was the 1^st company that produced a video graphics adapter (Warp5) with AA as the default mode. M A Rohner was one of the Warp5 contributors. Although the Warp5 had good reviews and received some awards, most PC users preferred the fastest adapters for business applications and were not ready for AA. At around 2000, video game users became aware of the distracting aliasing artifacts caused using only 1 sample point per pixel. The immediate approach was to use higher image resolution or Super Sampling, resulting in increased system cost.

Anti-Aliasing in CGI

Most Aliasing Artifacts result from using only one sample point per pixel when computing 2D images. These distracting artifacts can be minimized by applying AA techniques. Several AA approaches are presented here. Refer to Figure 5.

One approach is to perform post processing after single point sampling. Another approach is to use subpixel processing (several samples per pixel).

For real-time applications (RT CGI) such as video games or flight simulators, images with AA have  to be generated at least at the rate of 60 frames per second. In complex state of the art games, images can require processing of millions of polygons.

References:

Anti-Aliasing: https://vr.arvilab.com/blog/anti-aliasing

What is anti-aliasing? TAA, FXAA, DLAA, and more explained:
     https://www.digitaltrends.com/computing/what-is-anti-aliasing/

What is Anti-Aliasing? Ultimate Guide:
    https://www.selecthub.com/resources/what-is-anti-aliasing/

Post-Process Anti-Aliasing

One approach to AA is to render images using one sample per pixel, followed by blurring pixels with post processing. Several AA methods use this post-process approach to reduce aliasing artifacts, while limiting the speed penalty. Some use GPUs to detect edges of a polygon by comparing color contrasts between two adjacent pixels. When both pixels are similar, it is assumed that they’re from the same polygon. Page 3 Sampling Functions

One advantage of this approach is that it can be faster than subpixel processing. A significant disadvantage of these techniques is that they make the image blurrier. This can negatively affect games with detailed features.

Fast Approximate Anti-Aliasing (FXAA)

Fast approximate anti-aliasing (FXAA) is a screen-space anti-aliasing algorithm created by Timothy Lottes at Nvidia. It is a single-pass, screen-space anti-aliasing technique designed for producing high-quality images with low performance impact. FXAA uses only 1 sample point per pixel. It achieves AA using a post process to clean to up jagged edges. This requires much less processing than MSAA and SSAA, though at the cost of image quality.

Temporal Anti-Aliasing (TAA)

Temporal Anti-Aliasing (TAA) uses a post process similar to FXAA. However, it samples a different location within each frame. It uses past frames to blend the samples together.

Morphological Anti-Aliasing (MLAA)

Morphological Antialiasing (MLAA) is a post process filtering similar to FXAA. It detects borders in the resulting image and also looks for specific patterns. Then it blends pixels in these borders, according to the pattern they belong to and their position within the pattern. It should be slower than FSAA.

SSAA and MSAA: Subpixel Point Samples

Two commonly used AA methods rely on subpixel point-sampling: Super-Sampling AA (SSAA) and Multiple-Sample AA (MSAA). These techniques are more time consuming since they require processing of several images, followed by image averaging.

Super Sampling AA (SSAA)

The SSAA approach has been used in non-real-time applications. In this approach, a 512×512 image is first computed at higher resolution, such as 2048×2048, for example. It is then reduced   through averaging or filtering to produce a 512×512 image. It is computation intensive and cannot be used for RT CGI applications. Since there are no time constraints, large images can be computed offline using high-speed general-purpose computers.

Multi Sample AA (MSAA)

For RT CGI applications, algorithms are limited to methods that can produce new images at rate of at least 60 frames per second. MSAA is the most commonly used approach to subpixel processing in RT. It relies on multiple sample points (or subpixels) inside of pixels. With MSAA, several images are computed for 4 or 8 sample points, followed by images averaging. The MSAA method can be computation intensive and costly.

8-Queens Puzzle

The position of the subpixel sample points can be derived from solutions to the “8 Queens-Puzzle”. The solutions to the 8-queens puzzle provide good results for near horizontal and vertical edges and edges at 45 degrees. But the AA effectiveness is considerably degraded for edges with angles in-between. On the other hand, the ABAA solution (see below) works consistently for all angles. 

Enhanced Subpixel Morphological Anti-Aliasing (SMAA)

Subpixel Morphological Anti-Aliasing (SMAA), is also similar to FXAA. It uses edge detection and blurs pixels around harsh edges. The main difference is that SMAA relies on taking multiple samples along those edges. Developed by Jorge Jimenez, a student from the Universidad de Zaragoza, SMAA combines post-process and spatial anti-aliasing to create an image. The images it creates are of higher quality than those produced by FXAA and MLAA.

Deep Learning Super Sampling (DLSS)

Deep learning super sampling (DLSS) is a family of real-time deep learning image enhancement and upscaling technologies developed by Nvidia that are available in a number of video games. The goal of these technologies is to allow the majority of the graphics pipeline to run at a lower resolution for increased performance, and then infer a higher resolution image from this that approximates the same level of detail as if the image had been rendered at this higher resolution. This allows for higher graphical settings and/or frame rates for a given output resolution, depending on user preference. (from Wikipedia)

Definitions from Wikipedia and Internet

Refer to definitions for SSAA, Spatial Anti-Aliasing, TAA, MSAA, MLAA, SMAA and 8-Queens Puzzle from Wikipedia

• FXAA:   https://blog.codinghorror.com/fast-approximate-anti-aliasing-fxaa
• TAA:             https://en.wikipedia.org/wiki/Temporal_anti-aliasing
• SSAA:            https://en.wikipedia.org/wiki/Supersampling
• Spatial AA:   https://en.wikipedia.org/wiki/Spatial_anti-aliasing
• MSAA:           https://en.wikipedia.org/wiki/Multisample_anti-aliasing
• MLAA:          https://en.wikipedia.org/wiki/Morphological_antialiasing
• SMAA:          https://github.com/iryoku/smaa
• DLSS          https://en.wikipedia.org/wiki/Deep_learning_super_sampling
• 8-Queens Puzzle:    https://en.wikipedia.org/wiki/Eight_queens_puzzle
• Moving Average       https://en.wikipedia.org/wiki/Moving_average

Area-based AA (ABAA): Subpixel Area Sampling

During the years working on RT CGI systems, Michel A Rohner experimented with different approaches for AA. Lately, he came up with the ultimate Area-Based AA (ABAA) solution.

ABAA solves the AA problem by producing high image quality without speed penalty. It relies on “area sampling” to determine the mixed color of the pixels. Most of the other AA solutions rely on “point sampling” followed with post processing.  They are a compromise between speed and image quality.

For example, the MSAA solution has been around for around 40 years. While it is slow, it is considered as the best current approach for image quality using point sampling.

 In order to solve the speed problem, some approaches use single point sampling, followed by post processing that blurs adjacent pixels that have high color contrast. They are a compromise between speed and image quality.

Although many approaches have been proposed, they did not solve 3 main problems:

• How to efficiently and accurately detect the covered subpixels.
• How to implement AA without speed (and cost) penalty.
• How to have equal steps as triangle edges move across pixels, for all edge orientations.

The new ABAA approach, solves these problems. It is a great improvement over MSAA. ABAA relies on subpixel areas samples instead of subpixel point samples to determine the mixed color of the pixels. This method produces more consistent results than SSAA or MSAA, at lower cost and lower power. Using the same number of subpixels, it produces better image quality than MSAA.

Currently, there is no readily available product using ABAA. But simulations have shown that ABAA is the fastest AA solution that also produces the best AA images, without postprocessing. ABAA is area-based instead of point sampling. During rendering, edges efficiently traverse the image from pixel to pixel. Intersected pixels are easily identified. The partially covered area of pixels, that is used for color mix, is readily available in 1 measurement (no lengthy computations). ABAA can be implemented directly using pixel covered area, or the area can be mapped into 4, 8, 16 or 32 subpixel areas.

The ABAA method is described in more details in a set of books from Michel A Rohner. There are 3 versions of the book, from introduction to extended versions:

• “Introduction to Area-Based Anti-Aliasing for CGI”, Michel A. Rohner, Gotham Books Inc 2024-05-15, 194 pages (short version).
  “Anti-Aliasing with ABAA vs MSAA”, Michel A. Rohner, Gotham Books Inc 2024-03-15, 272 pages (compact version).
• “Anti-Aliasing with ABAA vs MSAA”, Michel A. Rohner, Gotham Books Inc 2024-03-15, 272 pages (compact version).
• “New Area-Based Anti-Aliasing for CGI”, Michel A. Rohner, Gotham Books Inc 2024-03-15, 351 pages (extended version).

Detect Intersected Pixels with ABAA

Most approaches use sample points to decide when a portion of the triangle covers the pixel. Instead, ABAA computes the area inside of a pixel that is delimited by a triangle edge. This area is easily derived from the intersection of the triangle edge with a midline inside of that pixel.

In Figure 6, there is an example with 4 and 8 subpixel areas. ABAA evaluates the area inside of a pixel that is partially covered by a triangle in a few steps. For this process, ABAA uses 2 types of edges, according to their slopes: Vertical (VE) and Horizontal (HE) edges. The operation can be performed with fixed-points, since the magnitude of these slopes cannot be greater than 1.0. Another advantage is that true horizontal edges have a slope of 0.0, instead of infinity.

First, ABAA detects how the triangle edge intersects the pixel. The edge divides the pixels into 2 trapezoids. Since the height of the trapezoid is 1.0, the areas of these trapezoids are equal to the average of their top width and bottom width. That area can be measured on the midline. The areas of the trapezoids are determined by the intersection of the triangle edge with a midline inside of the pixel: horizontal midline for VE and vertical midline for HE.

With ABAA, a pixel is considered intersected only when the edge intersects the midline inside of that pixel. It does not matter if the trapezoid extends partially into an adjacent pixel. It does not matter if the edge intersects a pixel near a corner without intersecting a midline.

Note that even when the trapezoid extends outside the pixel boundary, the measured area is still correct. As edges move across pixels, the covered area transition from non-covered to fully-covered in equal steps, from 0.0 to 1.0. This method is very accurate. With 4 fractional bis, there can be 16 equal steps. The pixel color of intersected pixels is a weighted mix according to the 2 areas.

There can be 2 approaches when implementing ABAA:
– Use the computed area to mix the color of the 2 partial areas in the pixel. This approach works when there are only 2 fragments in a pixel. When there are mor fragments, this approach produces acceptable results.
– Assign the area covered by edges to subpixel areas (4, 6, 16 or 32). This approach is better when there are more than 2 fragments in a pixel.

Update Pixels with Partially Covered Area

In the simplest implementation, when an intersected pixel is encountered, the old pixel is retrieved from the Color buffer. If the depth of the new triangle is closer (with larger zi), the color of the retrieved pixel is updated according to the area partially covered by the new edge. The zi is also updated. There are different cases for beginning edges (BE) ending edges (!BE) and internal edges (IE).

There can be many ways to implement this solution. There can be several cases when there are more than one edges in a pixel. When there is another edge in the pixel, the new covered area is blended with the previous color mix. The new partial color is always mixed with the previous mix. The color error is negligeable, because it is attenuated by the new edge. This is comparable to a “moving average”.

This approach should produce more accurate and sharper images when compared with post processing methods that blend adjacent pixels with a 50/50 blurred intensity.

Assign Subpixel Areas to 4 or 8 Subpixels

A better approach is to map the partially covered area into 4 or 8 subpixel areas according to the edge flags and a decoding table.

Refer to the ABAA example with 4 and 8 subpixels in Figure 6 above. The advantage of this approach is that the color mix is more accurate, Also, the subpixel areas can have different depth values to help resolve cases of triangle penetration.

This approach is described in more details in the books. The simulations of ABAA vs MSAA below use this approach.

ABAA is Simpler and Faster

These new ABAA implementations are as fast as single point sampling, and produces the best AA images using 4 or 8 subpixel areas. ABAA can also be implemented in non-RT software used for movies and TV commercials. It can be a cost saving solution. Since this ABAA solution is new, as of this writing, there is no RT CGI system implemented with ABAA, yet. But, because of its speed and image quality, ABAA should soon become the preferred approach for 3D image generation.

ABAA Uses a New Math Approach

In 2019, M A Rohner published a book about a new math approach to 3D graphics: “New Fixed-Point Math for Logic Design”. This new math approach solves many nagging problems in 3D graphics and is at the root of the new ABAA solution. Some of the features of this new math approach are:
– Use “averaging” instead of “rounding” to convert fractional numbers into fixed-point numbers.
– For color and texture sampling, use the sample point at the center instead of the top-left corner of pixels.
– Redefine the way edges intersect pixels, using horizontal (HE) and vertical {VE} edges with slope magnitude <= 1.0.
– Improve speed of computations using fixed-point instead of floating-point in hardware (ASIC) implementations.
– Eliminate corner cases.

Conclusion

Since ABAA4 and ABAA8 require only one frame processing and no post processing, they are as fast a 1 sample per pixel. ABAA is the fastest approach and is ideal for RT CGI. Because of its efficiency, simplicity and lower cost, the ABAA solution should be widely accepted for new product development.