3 ms·

Rasterization in One Weekend

54 points by corysama 8y ago

ggambetta 8y ago
An alternative approach that is probably faster and simpler (no matrices or dot products), although slightly "less correct": http://www.gabrielgambetta.com/computer-graphics-from-scratch/filled-triangles.html http://www.gabrielgambetta.com/computer-graphics-from-scratc...
- NotCamelCase 8y ago
  That's cool! Although I'll take linear code with bunch of matrix-vector products over bunch of branches any day :-) As you may know, where this algorithm of 2D homogeneous rasterization really shines is in how it simplifies the triangle setup by deferring the perspective-divide until later rasterizer stagee. It's tricky for cases where (w <= 0.0f) so explicit clipping/generating new vertices and handling all the additional vertex attributes is not needed. In reality, there is no mat3::inverse() or even per-vertex attribute bary calculation so it fits rather easily and elegantly to the rest of tri. setup. The original paper I link there explains greatly how for HW the gains can be even bigger.
  - ggambetta 8y ago
    Super interesting, thanks :) My rasteriser is admittedly optimised for requiring the most basic math possible, as it's mostly an educational resource.
    - NotCamelCase 8y ago
      No problem! You've got some great resources there too! :) I had problems running some demos though.
      - ggambetta 8y ago
        Hmm, mind telling me which ones, which browser, etc? My contact info is in my profile if you rather do this privately.
  - vardump 8y ago
    > That's cool! Although I'll take linear code with bunch of matrix-vector products over bunch of branches any day :-) Any day? Even on those days when you need to use say, 80486 or 68000? Or some low-end microcontroller?
jholman 8y ago
It continues to frustrate me that no one seems to have a better name for this process than "rasterization". It frustrates me because that word very clearly seems to say "turning non-raster data into rasters". This process does this, but so does ray-tracing. For that matter, various algorithms for turning 2d vector data into 2d raster data would also seem to be covered by "rasterization", like filling triangles with scanlines, or the like. Just another lost battle, I suppose.
thechao 8y ago
It’s been 5+ years since I worked in it, but the well-tuned version of openswr.com was competitive with discrete HW, ca., 2012. This isn’t “rasterization in a day”; it’s more like “a team of professionals over 18 months” who had done two prior rasterizers on Larrrabee, including working directly with Mike Abrash & co.
- NotCamelCase 8y ago
  That's impressive. In some synthetic scenes or actual applications? I think careful and elaborate design and scalability can get you a long way, but the thing is, without relaxing some API rules (e.g. rasterization order) which makes a rasterizer robust, you're gonna have difficulty keeping up with HW eventually.
  - thechao 8y ago
    We started with Quake III, Minecraft, etc. and were able to maintain "game play FPS" (800+), but nothing like a high end discrete card. Where SWR really shined was on high end HPC visualization software, where discrete cards (if they didn't crash/hang) could only maintain 1-2 FPS. SWR could get 12-17 FPS. Such applications are strongly bandwidth limited.
- corysama 8y ago
  You mean http://openswr.org http://openswr.org

54 points by corysama 8y ago

An alternative approach that is probably faster and simpler (no matrices or dot products), although slightly "less correct": http://www.gabrielgambetta.com/computer-graphics-from-scratch/filled-triangles.html http://www.gabrielgambetta.com/computer-graphics-from-scratc...

NotCamelCase 8y ago
That's cool! Although I'll take linear code with bunch of matrix-vector products over bunch of branches any day :-) As you may know, where this algorithm of 2D homogeneous rasterization really shines is in how it simplifies the triangle setup by deferring the perspective-divide until later rasterizer stagee. It's tricky for cases where (w <= 0.0f) so explicit clipping/generating new vertices and handling all the additional vertex attributes is not needed. In reality, there is no mat3::inverse() or even per-vertex attribute bary calculation so it fits rather easily and elegantly to the rest of tri. setup. The original paper I link there explains greatly how for HW the gains can be even bigger.
- ggambetta 8y ago
  Super interesting, thanks :) My rasteriser is admittedly optimised for requiring the most basic math possible, as it's mostly an educational resource.
  - NotCamelCase 8y ago
    No problem! You've got some great resources there too! :) I had problems running some demos though.
    - ggambetta 8y ago
      Hmm, mind telling me which ones, which browser, etc? My contact info is in my profile if you rather do this privately.
- vardump 8y ago
  > That's cool! Although I'll take linear code with bunch of matrix-vector products over bunch of branches any day :-) Any day? Even on those days when you need to use say, 80486 or 68000? Or some low-end microcontroller?

jholman 8y ago

It continues to frustrate me that no one seems to have a better name for this process than "rasterization". It frustrates me because that word very clearly seems to say "turning non-raster data into rasters". This process does this, but so does ray-tracing. For that matter, various algorithms for turning 2d vector data into 2d raster data would also seem to be covered by "rasterization", like filling triangles with scanlines, or the like. Just another lost battle, I suppose.

thechao 8y ago

It’s been 5+ years since I worked in it, but the well-tuned version of openswr.com was competitive with discrete HW, ca., 2012. This isn’t “rasterization in a day”; it’s more like “a team of professionals over 18 months” who had done two prior rasterizers on Larrrabee, including working directly with Mike Abrash & co.

NotCamelCase 8y ago
That's impressive. In some synthetic scenes or actual applications? I think careful and elaborate design and scalability can get you a long way, but the thing is, without relaxing some API rules (e.g. rasterization order) which makes a rasterizer robust, you're gonna have difficulty keeping up with HW eventually.
- thechao 8y ago
  We started with Quake III, Minecraft, etc. and were able to maintain "game play FPS" (800+), but nothing like a high end discrete card. Where SWR really shined was on high end HPC visualization software, where discrete cards (if they didn't crash/hang) could only maintain 1-2 FPS. SWR could get 12-17 FPS. Such applications are strongly bandwidth limited.
corysama 8y ago
You mean http://openswr.org http://openswr.org