3
$\begingroup$

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

Thanks!

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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! 😉 $\endgroup$
    – Nathan Reed
    Commented Oct 4, 2020 at 17:02
  • $\begingroup$ I am curious for what application was the above required? $\endgroup$
    – lightxbulb
    Commented Oct 7, 2020 at 19:27

1 Answer 1

Reset to default
5
$\begingroup$

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

  • 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.
  • 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.
  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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I've heard about using something called a Scanline algorithm. Would that work too? $\endgroup$
    – Sarah
    Commented Oct 6, 2020 at 11:22
  • $\begingroup$ 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". $\endgroup$
    – Pseudonym
    Commented Oct 6, 2020 at 22:50
  • $\begingroup$ @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. $\endgroup$
    – Nathan Reed
    Commented Oct 8, 2020 at 18:30
  • $\begingroup$ @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. $\endgroup$
    – Pseudonym
    Commented Oct 9, 2020 at 0:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.