3 ms·
Wait, what? They rasterize a triangle by checking for each pixel if it intersects with the triangle? Where are the days when you learned Bresenham [1] or fixe
by smokel 2y ago
Wait, what? They rasterize a triangle by checking for each pixel if it intersects with the triangle? Where are the days when you learned Bresenham [1] or fixed-point arithmetic [2] to determine the extents of a scan line, and then fill it with an ordinary for-loop?
[1] https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
[2] https://en.wikipedia.org/wiki/Fixed-point_arithmetic https://en.wikipedia.org/wiki/Fixed-point_arithmetic
- vardump 2y agoChecking every pixel is generally faster on modern hardware due to SIMD! Of course you’ll need to clip properly. There are some pathological cases, like a thin long almost diagonal triangles. But those (rare) cases can be handled too by some subdivision clipping.
- randomNumber7 2y agoI get that a GPU is doing it like that, but are you really sure this is the better algorithm for cpu?
- vardump 2y agoYes, because you can handle 8 or 16 pixels in parallel with SIMD. You have also less branches which helps a lot.
- cv5005 2y agoThe thing is that modern computer architecture strikes again - like the old linked list vs array thing. Doing a candidate loop over a bounding box with edge equations can be much faster than ye old scanline algorithm because it lends itself more easily to simd and parallel approches - you can divide things up into tiles and process multiple pixels at a time with wide instructions and schedule tiles on multiple threads.
- smokel 2y agoFor those not in the know, things only get faster with this approach when you apply some optimization. The article that we are discussing won't get there until part 12. For the time being one may consult Ryg's amazing blog series: https://fgiesen.wordpress.com/2013/02/10/optimizing-the-basic-rasterizer/ https://fgiesen.wordpress.com/2013/02/10/optimizing-the-basi...
- ehaliewicz2 2y agoThose were the 90s. Modern rasterizers* all use barycentric coordinate based algorithms for a few reasons. Easier to implement with proper fill conventions and multisampling, and much easier to parallelize in hardware and software. * Hardware even back in the 90s used this type of approach :)
- thechao 2y agoWe use barycentric (both in high performance software rasterizers and in hardware) because attribute interpolation is significantly more costly than in-bounds checking (both due to the total number of interpolates, and the precision). The in-bounds check is going to be just a few instructions (a few fmas and some sign checking) for two dimensions (x, y); whereas attribute interpolation could be needed for 30–128 'dimensions'. It's easier to push the interpolation to the use-site in the fragment shader, and let the compiler do its magic.
- deleted 2y ago[deleted]
- Lerc 2y agoThere used to be a series of articles similar to this one that did things that way as well. As I recall, the author was making swiftshader, which I think was acquired by RAD Game Tools, then the articles got bitrot and eventually disappeared.
- amelius 2y agoThey probably do that because shading uses the same general approach (a float computation per pixel, with some shared terms).
- deleted 2y ago[deleted]
- randomNumber7 2y agoSomeone in the comments here posted a version of that and was downvoted. Probably the author doesn't like competition.