I want to implement anti-aliasing in BRE, but first, I want to explore what it is, how it is caused, and what are the techniques to mitigate this effect. That is why we will talk about Rasterization in depth in this post. Next post, will be about aliasing and anti-aliasing.
Raster Images and Raster Displays
Commonly, computer graphics images are presented to the user on some kind of display device based on a rectangular grid of light-emitting elements, or pixels (picture elements), each of whose colors and intensities is individually adjustable in every frame. For historical reasons relating to the way that picture tube-based televisions work, these displays are called raster displays.
Example of raster display
Raster Images are 2D arrays that store the pixel value for each pixel. A pixel can be defined by a scalar or a vector of values, depending on the image. In a grayscale image, each pixel is a scalar value representing the brightness of the image in that position. In a color image, each element is represented by a vector of multiple scalar components (typically three: an RGB color) that identifies the color of that image’s location. The length of the vector used to define a pixel defines the number of image channels of the image.
The size in pixels of an image is the number of pixels along its width and height. Usually, it is used interchangeably with its pixel resolution or just resolution, but there is an important difference between them. Resolution deals with how small are the details an image can represent and it is quantified to how close two lines can be on the image without appearing as a single line. The unit of measure of resolution is pixels per inch.
You could display a raster image stored in memory by using each pixel in the image to control the color of one pixel of the raster display. In the following picture, you can see an example of a raster image.
One problem with the previous way to display the raster image is that it does not necessarily match the raster display properties. For example, in televisions, the display could not have the same number of pixels as the image being displayed. Given this, you should think of a raster image as a device-independent description of the image to be displayed, and the display device as a way of approximating the ideal image.
Also, the same image may have different resolutions depending on which media is used to reproduce it. For example, if the size in pixels of both your mobile phone and your TV is 1280 x 800, it does not mean they have the same resolution because the mobile has the same number of pixels in a much smaller space. However, sometimes the size in pixels is used to indicate the resolution. This is because media are made to be observed at a certain distance. The mobile phone is made to be seen from 20 cm away, while the TV screen is seen at a couple of meters. They occupy a similar portion of our field of view and this is the reason why it makes sense just to use the number of pixels to indicate the resolution.
Example of display optimal distance vs size and resolution.
The quality of a raster image depends heavily on its resolution. A high resolution is required to draw smooth curves well. If the resolution is insufficient, the pixels become visible (pixelation).
What are some examples of Raster Devices?
As we are interested in computer graphics, we are going to talk about output display raster devices only.
Most of this kind of displays are based on fixed arrays of pixels. They can be separated into emissive displays, which use pixels that directly emit controllable amounts of light, and transmissive displays, in which the pixels themselves do not emit light but instead vary the amount of light that they allow to pass through them.
Transmissive displays require a light source to illuminate them (in a direct-viewed display, this is a backlight behind the array). An emissive display is its own light source.
Light-emitting diode (LED) displays are an example of the emissive type, while liquid crystal displays (LCD) are an example of the transmissive type.
Example of LCD display modes
Any type of display with a fixed pixel grid has a fixed resolution determined by the size of the grid. As we mentioned, for displays and images, resolution means the dimensions of the pixel grid (for example, a desktop monitor with a resolution of 1920 x 1080 pixels). An image of a different resolution must be converted into a 1920 x 1080 image to fill the screen.
How are the raster images and the pixels related?
When we measure or reproduce images, they take the form of two-dimensional distributions of light energy (for example, the light emitted from the monitor as a function of position on the face of the display). In the physical world, images are functions defined over two-dimensional areas (almost always rectangles). So we can abstract an image as a function I(x, y) : R -> V where R belongs to R^2 and is a rectangular area and V is the set of possible pixel values.
Now, we will see how this notion of a continuous image is related with a raster image: A display pixel (with its RGB subpixels) is designed so that the average color of the image over the face of the pixel is controlled by the corresponding pixel value in the raster image. In both cases, the pixel value is a local average of the color of the image, and it is called point sample of the image (when we find the value x in a pixel, it means “the value of the image in the vicinity of this grid point is x”).
Example of point sampling
Another important concept is where the pixels are located in 2D space. You can find a complete explanation about this in How Can I Find The Pixel Space Coordinates of a 3D Point – Part 1. Basically, we can use 2D real screen coordinate to specify pixel positions.
Rasterization and the Graphics Pipeline
We cannot talk about rasterization without describing the graphics pipeline first. The rasterization-based rendering pipeline implementation changes among different hardware, developers, and over time. In the following picture, you can see the sequence of operations that turn the specification of a set of geometric primitives into an image on the screen.
The input is a series of geometric primitives (points, lines, triangles, and polygons). All the geometric primitives are defined by vertices (1 for point, 2 for segments, 3 for triangles, etc). When we specify a vertex, we provide several attributes like position, normal vector, uv coordinates, etc. The first stage of the pipeline, per-vertex transformations and attributes setup, processes all the vertices and transforms its attributes (Refer to How Can I Find The Pixel Space Coordinates of a 3D Point – Part 1, Part 2, and Part 3 to understand the different space transformations).
The next stage is the primitive processing, which takes the transformed vertices and the primitive specified by the user and outputs points, lines, and triangles to the next stage. This stage may create or destroy primitives from the given input (geometry shader or tessellation stages).
The rasterization stage converts points, lines, and triangles to their raster representation and interpolates the vertex attribute values of the primitive being rasterized. The rasterization stage marks the passage from a world made of points, lines, and polygons in 3D space to a 2D world made of pixels.
While a pixel is defined by its coordinates in the image or screen and its color, the fragments produced by the rasterization may also contain a number of interpolated values other than the color. These fragments and are the input to the next stage, the per-fragment computation. Each fragment is processed by the per-fragment computation stage that calculates the final values of the fragment’s attributes.
The last stage of the pipeline determines how each fragment is combined with the current value stored in the frame buffer, that is, the data buffer that stores the image during its formation, to determine the color of the corresponding pixel.
What is done in the Rasterization step?
When a scene is made of many primitives it may happen that not all of them are entirely visible at the same time. This may happen for three reasons:
- because a primitive is partially or entirely covered by another with respect to the viewer, and then we need a hidden surface removal algorithm to avoid rasterizing it.
- because the primitive is partially outside the view volume, in which case we have to clip it, which means to determine which part of the primitive is inside the view volume.
- because the primitive is entirely outside the view volume, in which case we should simply avoid rasterizing it.
We are not going to talk about these steps (clipping, culling, etc), but we can see in the following picture why they are necessary.
After clipping and culling steps (which are done in NDC space, for performance reasons) we move to the window/screen/pixel coordinate space.
For each primitive that comes in, the rasterizer has two jobs: it enumerates the pixels that are covered by the primitive and it interpolates vertex attribute values, across the primitive. The output of the rasterizer is a set of fragments, one for each pixel covered by the primitive. Each fragment lives at a particular pixel and carries its own set of attribute values.
How can we know the pixels covered by a primitive?
We have a triangle in screen-space like in the following picture
First, we need to define a bounding rectangle that encloses the pixel area range where a polygon is to be drawn. That way the only pixels processed are the ones that can fall within the area of the primitive.
Rasterizing a polygon is referred to as polygon filling. Triangles are convex and any triangle intersects a horizontal row of pixels (also called scan line, for historical reasons having to do with CRT-based television displays) in at most one contiguous segment.
For any scan line that intersects a triangle, we can represent the intersection with only a minimum x value and a maximum x value, called a span. The representation of a triangle during rasterization consists of a set of spans, one per scan line, that the triangle intersects.
The convexity of triangles implies that the set of scan lines intersected by a triangle is contiguous in y; there are a minimum and a maximum y for a given triangle, which contains all of the non-empty spans. In the following picture, you can see an example of the set of spans for a triangle.
Second, we need to determine triangle fragments. At the rasterization level, fragments are the result of breaking down screen-space triangles to more directly match pixels in the framebuffer. These can be visualized as a triangle diced into pieces by cutting along pixel boundaries.
Many of these fragments (the interior of a triangle) will be square, the full size of the pixel square. We call these pixel-sized fragments complete fragments.
Along the edges of a triangle, these may be multi sided polygons that fit inside of the pixel square and are smaller than a pixel. We call these smaller fragments partial fragments.
The basic idea is that fragments represent the pieces of a triangle that impinge upon a given pixel. We can think of a pixel as being destinations into which we place all of the fragments that cover the area of a pixel. This is not a one-to-one mapping. A pixel may contain multiple fragments from different (or even the same) objects, or a pixel may not contain any fragments in the current view of the scene.
Example of multiple fragments falling inside the area of a single pixel
Complete fragments always continue on to the next stage of the rasterization process. For partial fragments, we need to decide if they continue or they are discarded. A common method for solving this is to keep partial fragments if and only if they contain the pixel’s center point. This is sometimes called center point sampling of geometry because an entire fragment is generated or not based on a single-point sample within each pixel at its center.
There is an important situation to address, that is when a triangle vertex or edge falls exactly on a pixel center. The behavior of the graphics system is determined by a system-dependent fill convention. This convention ensures that if two triangles share a vertex or an edge, only one triangle will contribute a fragment to the pixel. Without this convention, there may be holes (pixels where both triangles partial fragments are dropped) or double drawn pixels (where the partial fragments of both triangles are promoted to complete fragments) on the shared edges between triangles. Holes along a shared triangle edge allow the background color to show through what would otherwise be continuous, opaque surface, making the surface appear to have cracks running through it. Double-drawn pixels along a shared edge result in more subtle artifacts, normally seen only when transparency or other forms of blending are used.
How is vertex attributes interpolation done?
As we already mentioned, to each vertex we may assign attributes other than its position. For example, we can assign a color attribute to each vertex. Now, we need to know which color should be assigned to the pixels rasterized by the primitive. If we have a line segment going from v0 to v1 and we assign the red color to v0 and the blue color to v1, then the color should fade from red to blue as we follow the rasterization of the segment from v0 to v1. We can get this result using the following linear combination of two colors: c(i, j) = Red λ0(i, j) + Blue λ1(i, j) where we indicate with c(i, j) the color of pixel (i, j) and with λ0(i, j) and λ1(i, j) the coefficients of the linear combination. Suppose the position of the pixel (i’, j’) is in a middle way between v0 and v1, then both coefficients should be 1/2. This concept can be extended to a generic point on the segment by means of barycentric coordinates.
We can describe a triangle in 2D with 2D points p0 = (x0, y0), p1 = (x1, y1), and p2 = (x2,y2) in screen coordinates. If the vertices have colors c0, c1, and c2, the color at a point in the triangle with barycentric coordinates (α, β, γ) is c = α * c0 + β * c1 + γ * c2.
This type of interpolation of color is known in graphics as Gouraud interpolation after its inventor.
Example of barycentric interpolation
We reached the end of the article. In the next post, we are going to talk about aliasing and anti-aliasing.
References
Fundamentals of Computer Graphics, 4th Edition
Essential Mathematics for Games and Interactive Applications, 3rd Edition
Introduction to Computer Graphics: A Practical Learning Approach, 1st Edition
Nicolás Bertoa 