What is scanline fill algorithm?

The scanline fill algorithm is designed to determine the interior parts of a polygon in a rendered image. The algorithm scans the image from top to bottom by avoiding the need to perform complex and time-consuming point-in polygon tests. It has significant applications in rendering engines, games, and 3D modeling tools.

How scanline works

• The scanline fill algorithm works with lines (one at a time).

• It intersects each line with all polygon edges and determines which intersections are entry or exit points.

• The spans between entry and exit points are filled in.

• It then processes the polygon line by line, from the defined minimum to maximum y-values.

• The edge tableThe table that contain the coordinates of two endpoints. (ET) is sorted by the lowest y value (or highest, if you render from top to bottom) and contains all the edges of a polygon.

• Each entry in the edge table contains the data such as the lowest $y$ coordinate of an edge ($y_\text{min}$), the highest y coordinate ($y_\text{max}$), the $x$ coordinate corresponding to the $y = y_\text{min}$ ($x\text \;{of}\; y_\text{min}$), and the inverse of the slope (1/m).

• The active edge tableA data structure that consists of all the intersection points of the edges with the current scanline. (AET) initially contains no edges.

• As we move from one line to the next, we add edges from the ET to the AET when we reach their $y = y_\text{min}$ and remove edges from the AET when we reach the $y = y_\text{max}$.

• The edges in the AET are then sorted by their current $x$ value which can be found by using the formula given below.

Scanline algorithm: Main loop

• Repeat until the ET and AET are empty.

  • Move any edges from the ET to the AET where, $y = y_\text{min}.$

  • Sort the AET on $x$.

  • Fill the desired pixels on the scanline y using pairs of x coordinates from the AET.

  • Increment $y$ by 1.

  • Remove edges from AET where $y = y_\text{max}.$

  • Update each edge's $x$ value in the AET for the next scanline.

  • Repeat the process.

Handling special cases

Case 1:

Intersection is the point where the two edges of the lines meet.

• In this diagram, $p_1$ is the intersection point of both the edges $e_1$ and $e_2$. So, we can fill the shape pairwise ($p_o$, $p_1$) and ($p_1$, $p_2$).

• If we compute the intersection of the scanline with the edge $e_1$ and $e_2$ separately, we get the intersection point $p_1$ twice.

• In order to correctly fill in the shape, we need to count the intersection point twice. Keep both of the points $p_1$ in the AET.

Case 2:

• If we count $p_1$ twice here, we will end up filling between $p_1$ and $p_2$.

• In order to fill it up correctly, do not count $p_1$ twice ($p_o$, $p_1$, $p_1$, $p_2$, $p_3$).

Note: A simple solution to handle the cases mentioned above, is to check if the intersection is the $y_\text{min}$or $y_\text{max}$ of both the edge's endpoint. If it is, we count it twice, otherwise, we count it only once.

Demonstration

Continue reading

• What is super-sampling anti-aliasing?

• How 3D engines use triangles to draw object surfaces