<p>The scan-line algorithm (as described on <a href="https://en.wikipedia.org/wiki/Scanline_rendering" rel="noreferrer">Wikipedia</a> for instance) is concerned with generating the pixels in order, left-to-right and top-to-bottom, with each pixel needing to be touched only once. It was developed in the late 1960s, for devices with no framebuffer memory—so it has to generate each pixel just-in-time as it scans out to the display.</p>

<p>The constraint to generate the pixels exactly in order is a strong one. Now, it's possible to imagine a very simple and naive algorithm that doesn't need tables, buckets, or sorting to accomplish this. For example, for each pixel, you might just iterate over all the triangles, test whether the current pixel falls inside it, and keep track of the closest triangle that passes that test. (That's effectively ray tracing without any acceleration structure.)</p>

<p>It's pretty clear that this is inefficient as soon as you have more than a handful of triangles. The complicated data structures and stuff that show up in the classic scan-line algorithm are there to optimize this process. For instance, pre-bucketing the edges by Y-coordinate and maintaining an "active edge table" lets you quickly and incrementally identify the edges that affect each scanline as you move down the image. Keeping the edge intersections sorted by X-coordinate allows you to quickly generate the pixels left-to-right within each scanline, and keeping a Z-sorted list of active triangles as you scan left-to-right enables you to do hidden surface removal at the same time.</p>

<hr>

<p>Incidentally, this algorithm is of mainly historical interest. It is very far from how modern GPU rasterizers or even software rasterizers work. Nowadays we pretty much always have a framebuffer and use double buffering, so we don't need to generate the pixels precisely in order anymore; consequently, we usually iterate over the triangles first, then find which pixels each triangle covers, rather than the other way around.</p>

<p>Moreover, the scanline algorithm is pretty inherently serial and doesn't make good use of today's highly parallel hardware. Modern approaches rely on multicore processing and SIMD to test many pixels against many triangles at once, rather than incrementally updating sorted lists of edges and suchlike.</p>

<p>For more on modernized software rasterization, see Fabian Giesen's articles <a href="https://fgiesen.wordpress.com/2013/02/08/triangle-rasterization-in-practice/" rel="noreferrer">Triangle rasterization in practice</a> and <a href="https://fgiesen.wordpress.com/2013/02/10/optimizing-the-basic-rasterizer/" rel="noreferrer">Optimizing the basic rasterizer</a>.</p>

CC BY-SA 3.0
2017-05-24T21:45:10.007Z
2017-05-24T23:06:11.927Z
2017-05-24T23:06:11.927Z
Nathan Reed
<p>It makes use of tables, buckets, and sorting, which all seem unnecessary.</p>

<p>I don't understand why I can't just fill between pairs of scan line intersections, ignoring vertices and edges with gradient 0.</p>

<p>My lecturer didn't provide the best notes on this algorithm, and all I can find online are even more complicated versions of it.</p>

<p>An ideal answer would be an explanation of the algorithm, and a reason why simply filling between pairs of intersections won't work.</p>

CC BY-SA 3.0
2017-05-22T05:37:29.730Z
Some things to consider, while you wait for the answer. How would you get a unsorted dataset in order if not by sorting? So nearly every algorithm stars by organising data to suit their need. Where would you store that data? Suddenly you have tables and sorting on everything you do.
joojaa
CC BY-SA 4.0
2023-09-27T17:59:45.460Z
I agree, explanations seems to be rather confusing... I have found zero that seemed clear. I needed this algorithm for a project so I went searching for implementations. I ended up doing it myself from scratch and what I found was this: these extraneous pieces which are almost always roped in (as you say: tables, buckets, sorting)... only exist to reduce computation aka speed it up. In its essence, all you're doing is scanning across a plane line by line, and if you cross a polygon edge then you toggle between filling/not-filling.
DAG
<rasterizer><scanline>
Why is the scan line filling algorithm so seemingly over complicated?
toastedDeli
# Why is the scan line filling algorithm so seemingly over complicated?

(Asked by: username_0 on 2017-05-21)

It makes use of tables, buckets, and sorting, which all seem unnecessary.

I don't understand why I can't just fill between pairs of scan line intersections, ignoring vertices and edges with gradient 0.

My lecturer didn't provide the best notes on this algorithm, and all I can find online are even more complicated versions of it.

An ideal answer would be an explanation of the algorithm, and a reason why simply filling between pairs of intersections won't work.

**Tags:** rasterizer, scanline

> **Comments:**
> **username_1**: Some things to consider, while you wait for the answer. How would you get a unsorted dataset in order if not by sorting? So nearly every algorithm stars by organising data to suit their need. Where would you store that data? Suddenly you have tables and sorting on everything you do.  
> **username_2**: I agree, explanations seems to be rather confusing... I have found zero that seemed clear. I needed this algorithm for a project so I went searching for implementations. I ended up doing it myself from scratch and what I found was this: these extraneous pieces which are almost always roped in (as you say: tables, buckets, sorting)... only exist to reduce computation aka speed it up. In its essence, all you're doing is scanning across a plane line by line, and if you cross a polygon edge then you toggle between filling/not-filling.  

---

## 1 answers

### Answer by username_3 on 2017-05-24. Score: 8 | Accepted answer

The scan-line algorithm (as described on [Wikipedia](https://en.wikipedia.org/wiki/Scanline_rendering) for instance) is concerned with generating the pixels in order, left-to-right and top-to-bottom, with each pixel needing to be touched only once. It was developed in the late 1960s, for devices with no framebuffer memory—so it has to generate each pixel just-in-time as it scans out to the display.

The constraint to generate the pixels exactly in order is a strong one. Now, it's possible to imagine a very simple and naive algorithm that doesn't need tables, buckets, or sorting to accomplish this. For example, for each pixel, you might just iterate over all the triangles, test whether the current pixel falls inside it, and keep track of the closest triangle that passes that test. (That's effectively ray tracing without any acceleration structure.)

It's pretty clear that this is inefficient as soon as you have more than a handful of triangles. The complicated data structures and stuff that show up in the classic scan-line algorithm are there to optimize this process. For instance, pre-bucketing the edges by Y-coordinate and maintaining an "active edge table" lets you quickly and incrementally identify the edges that affect each scanline as you move down the image. Keeping the edge intersections sorted by X-coordinate allows you to quickly generate the pixels left-to-right within each scanline, and keeping a Z-sorted list of active triangles as you scan left-to-right enables you to do hidden surface removal at the same time.

---

Incidentally, this algorithm is of mainly historical interest. It is very far from how modern GPU rasterizers or even software rasterizers work. Nowadays we pretty much always have a framebuffer and use double buffering, so we don't need to generate the pixels precisely in order anymore; consequently, we usually iterate over the triangles first, then find which pixels each triangle covers, rather than the other way around.

Moreover, the scanline algorithm is pretty inherently serial and doesn't make good use of today's highly parallel hardware. Modern approaches rely on multicore processing and SIMD to test many pixels against many triangles at once, rather than incrementally updating sorted lists of edges and suchlike.

For more on modernized software rasterization, see Fabian Giesen's articles [Triangle rasterization in practice](https://fgiesen.wordpress.com/2013/02/08/triangle-rasterization-in-practice/) and [Optimizing the basic rasterizer](https://fgiesen.wordpress.com/2013/02/10/optimizing-the-basic-rasterizer/).


---

