5 ms·

@s-macke very cool article, it brings me back. :) Thanks for the write up. Regarding speeding it up & drawing front-to-back, didn’t some games do a back-to-fro

by dahart 7y ago

@s-macke very cool article, it brings me back. :) Thanks for the write up. Regarding speeding it up & drawing front-to-back, didn’t some games do a back-to-front with some kind of bounds on how far down they draw? That way you get speed up without needing the y-buffer memory. I remember that in some games you could sometimes see cracks in the terrain, and I’m guessing from my faded memory that it was bounding the vertical draw. Not entirely sure if I’m remembering seeing cracks in sprite-drawn terrain though. I was also wondering about the “Rotation” animated gif example, some extra mountains show up on the right side in the 360 spin for a couple of frames while the camera is passing the far end of the river, just before the pyramid comes into view. Is that just a bug, or is it something about the algorithm that’s tricky to fix?

pcwalton 7y ago
> That way you get speed up without needing the y-buffer memory. I mean, the "Y-buffer" memory is just one integer per column, pretty trivial even for a software rasterizer on an early 90s machine with a limited cache hierarchy. Pretty much any algorithm that has overdraw will lose to that. That's why this technique was so popular in the nineties—what Doom did was just a generalization of this idea to allow multiple sparse pixel spans per column instead of just one. (For comparison, Z-buffer bandwidth is expensive because it's an extra 16/24/32 bits per pixel, which can double your fill rate requirements.)
- dahart 7y ago
  Oh yeah, you’re totally right, please chalk that up to pre-coffee brain fart, I wasn’t thinking about the size and stupidly assumed it was on the same order as z-buffer.
pjtr 7y ago
Even drawing front-to-back you don't need the y-buffer, if you switch the loops: for x ... for y ... Another trick I now remember was to interpolate the color values on such a y-segment, to reduce the pixelated look.
- dahart 7y ago
  Such good points and so obvious (now that you said them) that first I really want to retract my comment and second now I feel like coding up a terrain generator today. Duh, Doom did (famously) switch the loops for similar reasons!
- s-macke 7y ago
  Indeed, switching the loops is valid and might or might not give you an additional speedup. I had hoped, that someone figures this out :-). However I think in order to understand the basic algorithm the way in the readme is the better one.
  - gliese1337 7y ago
    Do you know of referenceable pseudocode (or real code) for that somewhere? I've tried modifying your code to switch the loops, but it always comes out garbled; clearly I'm messing up somewhere in the refactoring process, but I don't have enough experience with this algorithm to figure out where!
    - s-macke 7y ago
      A render routine with exchanged for loops looks like this. https://www.pastiebin.com/5e10d48ac6595 https://www.pastiebin.com/5e10d48ac6595 Just exchange the Render() method in my VoxelSpace.html file with the pastie.
s-macke 7y ago
The rotation artifacts you see are a result of the very simple algorithm and the property of the viewing triangle. It renders objects that are farther away when they are near the border of the viewing screen.
- esrauch 7y ago
  I wonder if you could nearly as efficiently draw to fixed distance arcs instead of perpendicular to viewing area lines to avoid that effect?
  - s-macke 7y ago
    In the pseudo code in the readme just calculate the (square) distance between pleft and p and don't draw the line if the distance is larger than a given threshold. But this is not very efficient. When you switch the loops this will be easier because this check can be done in the outer loop. But I would suggest to experiment with some fog effect first.
    - gliese1337 7y ago
      Turns out it can be made quite efficient with a little effort put into arithmetic power reduction. In the outer loop, it is possible to calculate a `dr` value from the existing `dx` and `dy`. Then you just increment the radius traveled at the same time as `px` and `py`, and replace the inner loop condition that puts a bound on `z` with a new condition that puts a bound on the radius. That fixes the rotation artifacts, and then makes it really easy to add a distance-based fog effect to hide the cut-off where new terrain comes into view as well.

by dahart 7y ago

pcwalton 7y ago

> That way you get speed up without needing the y-buffer memory. I mean, the "Y-buffer" memory is just one integer per column, pretty trivial even for a software rasterizer on an early 90s machine with a limited cache hierarchy. Pretty much any algorithm that has overdraw will lose to that. That's why this technique was so popular in the nineties—what Doom did was just a generalization of this idea to allow multiple sparse pixel spans per column instead of just one. (For comparison, Z-buffer bandwidth is expensive because it's an extra 16/24/32 bits per pixel, which can double your fill rate requirements.)

dahart 7y ago
Oh yeah, you’re totally right, please chalk that up to pre-coffee brain fart, I wasn’t thinking about the size and stupidly assumed it was on the same order as z-buffer.

pjtr 7y ago

Even drawing front-to-back you don't need the y-buffer, if you switch the loops: for x ... for y ... Another trick I now remember was to interpolate the color values on such a y-segment, to reduce the pixelated look.

dahart 7y ago
Such good points and so obvious (now that you said them) that first I really want to retract my comment and second now I feel like coding up a terrain generator today. Duh, Doom did (famously) switch the loops for similar reasons!
s-macke 7y ago
Indeed, switching the loops is valid and might or might not give you an additional speedup. I had hoped, that someone figures this out :-). However I think in order to understand the basic algorithm the way in the readme is the better one.
- gliese1337 7y ago
  Do you know of referenceable pseudocode (or real code) for that somewhere? I've tried modifying your code to switch the loops, but it always comes out garbled; clearly I'm messing up somewhere in the refactoring process, but I don't have enough experience with this algorithm to figure out where!
  - s-macke 7y ago
    A render routine with exchanged for loops looks like this. https://www.pastiebin.com/5e10d48ac6595 https://www.pastiebin.com/5e10d48ac6595 Just exchange the Render() method in my VoxelSpace.html file with the pastie.

s-macke 7y ago

The rotation artifacts you see are a result of the very simple algorithm and the property of the viewing triangle. It renders objects that are farther away when they are near the border of the viewing screen.

esrauch 7y ago
I wonder if you could nearly as efficiently draw to fixed distance arcs instead of perpendicular to viewing area lines to avoid that effect?
- s-macke 7y ago
  In the pseudo code in the readme just calculate the (square) distance between pleft and p and don't draw the line if the distance is larger than a given threshold. But this is not very efficient. When you switch the loops this will be easier because this check can be done in the outer loop. But I would suggest to experiment with some fog effect first.
  - gliese1337 7y ago
    Turns out it can be made quite efficient with a little effort put into arithmetic power reduction. In the outer loop, it is possible to calculate a `dr` value from the existing `dx` and `dy`. Then you just increment the radius traveled at the same time as `px` and `py`, and replace the inner loop condition that puts a bound on `z` with a new condition that puts a bound on the radius. That fixes the rotation artifacts, and then makes it really easy to add a distance-based fog effect to hide the cut-off where new terrain comes into view as well.