(This article is part of a series. You can jump to the previous section or the next section if you would like to.)
Our rasterizer contains two fundamental operations: Scan converting edges and drawing horizontal lines.
Drawing horizontal lines is not too complicated, but the scan conversion has some more complexity to it. In this section we will improve correctness and performance.
The current scan converter uses floating point values. It calculates the edge slope as dx/dy, and increments the current x coordinate with this value as it traverses the edge along the y coordinate.
This has two downsides: Performance and precision. Divisions can be slow, so if possible, we would like to avoid them. Admittedly, slow divisions used to be more of an issue before, on older computers. However, precision still remains a potential problem for us. Adding long sequences of floating-point numbers will lead to errors - as the numerical precision of the initial division, and then of each addition, is limited. This will lead to visual artifacts - gaps or overlaps between two triangles that share an edge. See this section in the previous article series for more details.
We will now change the scan converter to be exact. It will operate on integers only so we eliminate numerical errors. How can we do that? Ie, how can we calculate the edge slope without performing a (non-exact) division? The trick here is to keep track of the slope value as a fraction, and to never perform the divide. We instead store the slope as a pair of numbers (a numerator and denominator), and just use the normal rules for additions of fractions when we do the math.
You may have already heard of an integer-based algorithm for line drawing (Bresenham’s), and we could have used that one here as well. However, some of the refinements we will do later in this series are easier to implement when we follow this approach.
Let’s see how the integer-based scan converter looks like. In this example, we assume that the edge runs downwards and to the right, and that the major axis (the largest dimension) for the edge is along the y axis. This means we have to iterate along the y axis from start to end (top to bottom), and find an x coordinate for each integer y.
We start off by calculating the dx and dy values for the edge - ie the difference in x and y. The edge slope can be expressed as dx/dy, but this time we choose to not calculate this value by dividing. We also read out the pixel coordinates of the start point of the edge.
scan(start, end, buffer) {
const dx = end[0] - start[0];
const dy = end[1] - start[1];
let x = start[0];
let y = start[1];
We then set up our fraction by introducing a numerator variable. The denominator we will use will be the dy variable (as y is the major axis in this case). We then add the slope (still expressed as a fraction, and not a real-value number) to the x coordinate as we iterate over the y axis of the edge, from top to bottom.
let numerator = 0;
while (y <= end[1]) {
numerator += dx;
if (numerator > dy) {
x++;
numerator -= dy;
}
buffer[y] = x;
y++;
}
For each iteration, we add dx to the numerator, and then check whether the fraction overflows - ie, whether the numerator becomes larger than the denominator. If so, we move one pixel coordinate to the right by increasing the x variable, and then we subtract the denominator value from the numerator. This way we keep the fraction a true fraction (the value stays less than 1).
That is all there is to it! Handling the remaining cases, where an edge run downwards to the left, or when the major axis (the largest dimension) is along the x axis, is not too hard. See the source code for details - the changes are mostly swapping dx with dy and changing signs.
There is one thing more we need to do now. We need to adjust when and how we draw the horizontal lines. If you have read the previous article series on rasterizing, you may remember the “top left rule”. (See section 4 if you want.) Right now the pixels that lie on edges that are shared between two triangles will be drawn twice. We would like to avoid that, as it is unnecessary work and also creates visual artifacts.
A quick way to avoid drawing pixels twice, is to avoid drawing the initial horizontal line, and to skip the leftmost pixel of each horizontal line. This is not too hard to implement:
// we start at ymin+1 due to "top left" rasterization rule
let y = ymin + 1;
while (y <= ymax) {
// we start at xmin+1 due to "top left" rasterization rule
let x = this.startBuffer[y] + 1;
let endx = this.endBuffer[y];
let i = imageDataOffset + (x << 2);
while (x <= endx) {
(...)
}
y++;
// point to x=0 on the next line
imageDataOffset += this.imageData.width << 2;
}
And with that, we now have our first exact scanline rasterizer up and running! In the next section we will look at how we can draw the horizontal lines a bit more efficiently. In the meantime, have a look at the demo app for this section! Please note that our rasterizer still draws triangles based on vertex coordinates that are integers. This means that the animation is not smooth - the triangles seem to jump around a bit while they rotate. We will improve on that in a later section.