<p>It's an interesting question, because the advice changes over time. Having said that:</p>
<ul>
<li>On a GPU, by far the most efficient way, as Nathan Reed said in the comment, is to use the rasterisation hardware because that is that it is designed for.</li>
<li>On a CPU, one of the most efficient ways is to more-or-less mimic what rasterisation hardware does.</li>
</ul>
<p>GPU vendors are understandably quiet about the specifics of their hardware design, but the basic idea hasn't changed for a few decades.</p>
<ol>
<li>Conceptually split the screen into tiles, e.g. of 8 by 8 pixels.</li>
<li>Traverse the tiles which overlap with a triangle using some variant on <a href="https://www.cs.drexel.edu/%7Edavid/Classes/Papers/comp175-06-pineda.pdf" rel="nofollow noreferrer">Pineda's method</a>.</li>
<li>For each tile, compute a bit mask to find the exact pixels (or samples, if you're subsampling) in the bucket which are inside the triangle, using half-plane calculations. In GPU speak, the samples in a tile which are inside the triangle are called a <em>fragment</em>.</li>
<li>Do whatever processing is needed on the fragment.</li>
</ol>
<p>On a modern CPU, fragment processing (including the half-space calculations) can be made extremely efficient by using vector instructions.</p>

CC BY-SA 4.0
2020-10-06T11:22:59.157Z
I've heard about using something called a Scanline algorithm. Would that work too?
Sarah
CC BY-SA 4.0
2020-10-06T22:50:33.107Z
This is a scanline algorithm.

Broadly speaking, there are two ways to rasterise geometry. You either start with the raster grid and find out what geometry it corresponds to, or you start with the geometry and find out what parts of the raster grid it corresponds to. We typically call anything in the first category "ray tracing" or "ray casting", and we typically call anything in the second category "scanline".
Pseudonym
CC BY-SA 4.0
2020-10-08T18:30:37.020Z
@Pseudonym I disagree with that - the algorithm you've described here is _not_ a scanline rasterizer. A scanline rasterizer operates by iterating over the rows of pixels and tracking where the triangle edges intersect each row.
Nathan Reed
CC BY-SA 4.0
2020-10-09T00:01:44.483Z
@NathanReed Fair point. Perhaps the method as a whole is not really "scanline", but Pineda's method is certainly a scanline method, since it operates on rows rather than polygons or pixels.
Pseudonym
CC BY-SA 4.0
2020-10-06T01:04:20.450Z
2020-10-06T23:11:06.037Z
2020-10-06T23:11:06.037Z
Pseudonym
<p>Assuming I wanted to rasterize a scene of triangles that are all connected that is similar to the image below, what would be an efficient way to do it on a GPU and a CPU? The triangles can be of any size. Names of any methods utilized or any advice is appreciated!</p>
<p><a href="https://i.sstatic.net/00UNC.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/00UNC.png" alt="enter image description here" /></a></p>
<p>Thanks!</p>

CC BY-SA 4.0
2020-10-04T17:02:55.237Z
Do you mean you want to draw lines along the edges of the triangles, like in this image, or do you want to also texture and shade the triangles, etc? Anyway, triangle rasterization is kind of the whole reason GPUs were created, so, load up OpenGL (or other API of choice) and have at it! 
Nathan Reed
CC BY-SA 4.0
2020-10-07T19:27:02.127Z
I am curious for what application was the above required?
lightxbulb
<rasterizer><triangulation>
Efficient methods to rasterize a scene of connected triangles
Sarah
# Efficient methods to rasterize a scene of connected triangles

(Asked by: username_0 on 2020-10-04)

Assuming I wanted to rasterize a scene of triangles that are all connected that is similar to the image below, what would be an efficient way to do it on a GPU and a CPU? The triangles can be of any size. Names of any methods utilized or any advice is appreciated!

[![enter image description here](https://i.sstatic.net/00UNC.png)](https://i.sstatic.net/00UNC.png)

Thanks!

**Tags:** rasterizer, triangulation

> **Comments:**
> **username_1**: Do you mean you want to draw lines along the edges of the triangles, like in this image, or do you want to also texture and shade the triangles, etc? Anyway, triangle rasterization is kind of the whole reason GPUs were created, so, load up OpenGL (or other API of choice) and have at it!   
> **username_2**: I am curious for what application was the above required?  

---

## 1 answers

### Answer by username_3 on 2020-10-06. Score: 5 | Accepted answer

It's an interesting question, because the advice changes over time. Having said that:

* On a GPU, by far the most efficient way, as username_1 username_1 said in the comment, is to use the rasterisation hardware because that is that it is designed for.
* On a CPU, one of the most efficient ways is to more-or-less mimic what rasterisation hardware does.

GPU vendors are understandably quiet about the specifics of their hardware design, but the basic idea hasn't changed for a few decades.

1. Conceptually split the screen into tiles, e.g. of 8 by 8 pixels.
2. Traverse the tiles which overlap with a triangle using some variant on [Pineda's method](https://www.cs.drexel.edu/%7Edavid/Classes/Papers/comp175-06-pineda.pdf).
3. For each tile, compute a bit mask to find the exact pixels (or samples, if you're subsampling) in the bucket which are inside the triangle, using half-plane calculations. In GPU speak, the samples in a tile which are inside the triangle are called a *fragment*.
4. Do whatever processing is needed on the fragment.

On a modern CPU, fragment processing (including the half-space calculations) can be made extremely efficient by using vector instructions.

> **Comments:**
> **username_0**: I've heard about using something called a Scanline algorithm. Would that work too?  
> **username_3**: This is a scanline algorithm.  Broadly speaking, there are two ways to rasterise geometry. You either start with the raster grid and find out what geometry it corresponds to, or you start with the geometry and find out what parts of the raster grid it corresponds to. We typically call anything in the first category "ray tracing" or "ray casting", and we typically call anything in the second category "scanline".  
> **username_1**: @username_3 I disagree with that - the algorithm you've described here is _not_ a scanline rasterizer. A scanline rasterizer operates by iterating over the rows of pixels and tracking where the triangle edges intersect each row.  
> **username_3**: @username_1 Fair point. Perhaps the method as a whole is not really "scanline", but Pineda's method is certainly a scanline method, since it operates on rows rather than polygons or pixels.  

---

