Implementing a Tiny CPU Rasterizer
lisyarus.github.io
Implementing a Tiny CPU Rasterizer
1–10 of 50 posts
Re: Implementing a Tiny CPU Rasterizer
#2I love looking at stuff like this, working in the GPU space has only ever renewed my ambitions to work on similar projects. The hardest thing I always ran into with the more optimized fill algorithms was working around the single pixel holes that appear when doing everything with integers.
Small nitpick though, there seems to be an issue with the source code views, the file names and the first line of the code are on the same line with no spacing. looks like it might be a static site generation issue since there aren't any nodes to separate the name and the code in the raw html.
Edit: turns out the issue I'm seeing is somehow due to Firefox, seems to work correctly in edge.
Re: Implementing a Tiny CPU Rasterizer
#3Wait, 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
Re: Implementing a Tiny CPU Rasterizer
#4Wait, 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 [2] https://en.wikipedia.org/wiki/Fixed-point_arithmetic
Checking 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.
Re: Implementing a Tiny CPU Rasterizer
#5Wait, 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 [2] https://en.wikipedia.org/wiki/Fixed-point_arithmetic
The 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.
Re: Implementing a Tiny CPU Rasterizer
#6Wait, 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 [2] https://en.wikipedia.org/wiki/Fixed-point_arithmetic
Those 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 :)
Re: Implementing a Tiny CPU Rasterizer
#7Wait, 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 [2] https://en.wikipedia.org/wiki/Fixed-point_arithmetic
Those 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 :)
We 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.
Re: Implementing a Tiny CPU Rasterizer
#8Wait, 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 [2] https://en.wikipedia.org/wiki/Fixed-point_arithmetic
The 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 thread…
For 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-basi...
Re: Implementing a Tiny CPU Rasterizer
#9Nostalgia flashback. Anyone else implemented a renderer based on fatmap2.txt[1]?
I came up with my own approach using bresenham and storing spans, but it was slow and sucked.
Then my buddy found fatmap2.txt on a BBS and gave it to me, as I didn't have a modem at the time. It was a revelation.
Programming in Turbo Pascal I was hampered by it being 16bit, but discovered I could prepend the assembly opcodes with 66h to turn them into 32bit instructions.
Later I tried converting the code to C, being only 300 lines and at that point well understood I figured it was a good task to get started with C. I was self-taught at programming but had read enough C to feel confident enough to try.
Converted it all line by line to C before compiling... and got literally over 3000 errors and warnings, and none of them made any sense.
Discouraged I left it, but a week later I was determined to get it working. After a few hours staring and bashing my head against the wall, I saw that the constant for the texture width which I had converted to a #define in C, had a semi-colon at the end...
So I removed it, and voila it complied flawlessly...
Only later did I realize my C compiler, djgpp, was actually a C++ compiler and that's probably why I got so many seemingly weird errors.
Anyway, good times...
[1]: https://github.com/rcoscali/ftke/blob/master/ogles/doc/fatma...
Re: Implementing a Tiny CPU Rasterizer
#10I love looking at stuff like this, working in the GPU space has only ever renewed my ambitions to work on similar projects. The hardest thing I always ran into with the more optimized fill algorithms was working around the single pixel holes that appear when doing everything with integers. Small nitpick though, there seems to be an issue with the source code views, the file names and the first line of the code are on…
It looks like for some reason Firefox isn't being served the same source as Safari or Chrome. In those browsers, the filename is wrapped in , , and elements, and followed by
.
.
But in the version of the HTML that Firefox receives, all that is missing and the filename is just some text that ends up immediately in front of the first line of code.