Cg Programming/Rasterization

Rasterization is the stage of the graphics pipeline that determines the pixels covered by a primitive (e.g. a triangle) and interpolates the output parameters of the vertex shader (in particular depth) for each covered pixel. The interpolated output parameters are then given to the fragment shader. (In a wider sense, the term “rasterization” also includes the execution of the fragment shader and the per-fragment operations.)

Usually, it is not necessary for Cg programmers to know more about the rasterization stage than described in the previous paragraph. However, it is useful to know some details in order to understand features such as perspectively correct interpolation and the role of the fourth component of the vertex position that is computed by the vertex shader. For some advanced algorithms in computer graphics it is also necessary to know some details of the rasterization process.

The main two parts of the rasterization are:

Determining the pixels that are covered by a primitive (e.g. a triangle)
Linear interpolation of output parameters of the vertex shader and depth for all covered pixels

Determining Covered Pixels

In OpenGL (ES), a pixel of the framebuffer is defined as being covered by a primitive if the center of the pixel is covered by the primitive as illustrated in the diagram to the right.

There are certain rules for cases when the center of a pixel is exactly on the boundary of a primitive. These rules make sure that two adjacent triangles (i.e. triangles that share an edge) never share any pixels (unless they actually overlap) and never miss any pixels along the edge; i.e. each pixel along the edge between two adjacent triangles is covered by either triangle but not by both. This is important to avoid holes and (in case of semitransparent triangles) multiple rasterizations of the same pixel. The rules are, however, specific to implementations of GPUs. Moreover, other APIs than OpenGL may specify different rules. Thus, they won't be discussed here.

Linear Interpolation of Parameters

Once all the covered pixels are determined, the output parameters of the vertex shader are interpolated for each pixel. For simplicity, we will only discuss the case of a triangle. (A line works like a triangle with two vertices at the same position.)

For each triangle, the vertex shader computes the positions of the three vertices. In the diagram to the right, these positions are labeled as $V_{1}$ , $V_{2}$ , and $V_{3}$ . The vertex shader also computes values of output parameters at each vertex. We denote one of them as $f_{1}$ , $f_{2}$ , and $f_{3}$ . Note that these values refer to the same output parameter computed at different vertices. The position of the center of the pixel for which we want to interpolate the output parameter is labeled by $P$ in the diagram.

We want to compute a new interpolated value $f_{P}$ at the pixel center $P$ from the values $f_{1}$ , $f_{2}$ , and $f_{3}$ at the three vertices. There are several methods to do this. One is using barycentric coordinates $\alpha _{1}$ , $\alpha _{2}$ , and $\alpha _{3}$ , which are computed this way:

${\begin{array}{lcl}\alpha _{1}&=&{\frac {A_{1}}{A_{\text{total}}}}={\frac {{\text{area of triangle }}PV_{2}V_{3}}{{\text{area of triangle }}V_{1}V_{2}V_{3}}}\\\alpha _{2}&=&{\frac {A_{2}}{A_{\text{total}}}}={\frac {{\text{area of triangle }}V_{1}PV_{3}}{{\text{area of triangle }}V_{1}V_{2}V_{3}}}\\\alpha _{3}&=&{\frac {A_{3}}{A_{\text{total}}}}={\frac {{\text{area of triangle }}V_{1}V_{2}P}{{\text{area of triangle }}V_{1}V_{2}V_{3}}}\\\end{array}}$

The triangle areas $A_{1}$ , $A_{2}$ , $A_{3}$ , and $A_{\text{total}}$ are also shown in the diagram. In three dimensions (or two dimensions with an additional third dimension) the area of a triangle between three points $Q$ , $R$ , $S$ , can be computed as one half of the length of a cross product:

${\begin{array}{lcl}{\text{area of triangle }}QRS&=&{\frac {1}{2}}|{\overrightarrow {QR}}\times {\overrightarrow {QS}}|\end{array}}$

With the barycentric coordinates $\alpha _{1}$ , $\alpha _{2}$ , and $\alpha _{3}$ , the interpolation of $f_{P}$ at $P$ from the values $f_{1}$ , $f_{2}$ , and $f_{3}$ at the three vertices is easy:

${\begin{array}{lcl}f_{P}&=&\alpha _{1}f_{1}+\alpha _{2}f_{2}+\alpha _{3}f_{3}\end{array}}$

This way, all output parameters can be linearly interpolated for all covered pixels.

Perspectively Correct Interpolation of Parameters

The interpolation described in the previous section can result in certain distortions if applied to scenes that use perspective projection. For the perspectively correct interpolation the distance to the view point is placed in the fourth component of the three vertex positions ( $w_{1}$ , $w_{2}$ , and $w_{3}$ ) and the following equation is used for the interpolation:

${\begin{array}{lcl}f_{P}&=&{\frac {\alpha _{1}f_{1}/w_{1}+\alpha _{2}f_{2}/w_{2}+\alpha _{3}f_{3}/w_{3}}{\alpha _{1}/w_{1}+\alpha _{2}/w_{2}+\alpha _{3}/w_{3}}}\end{array}}$

Thus, the fourth component of the position of the vertices is important for perspectively correct interpolation of output parameters. Therefore, it is also important that the perspective division (which sets this fourth component to 1) is not performed in the vertex shader, otherwise the interpolation will be incorrect in the case of perspective projections. (Moreover, clipping fails in some cases.)

It should be noted that actual implementations of graphics pipelines are unlikely to implement exactly the same procedure because there are more efficient techniques. However, all perspectively correct linear interpolation methods result in the same interpolated values.

Determining Covered Pixels

Linear Interpolation of Parameters

Perspectively Correct Interpolation of Parameters

Further reading