Hacker News Reader

Comment by dahart | Hacker News Reader

@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?

View on HN

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

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.

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.

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!

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.

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!

A render routine with exchanged for loops looks like this.

https://www.pastiebin.com/5e10d48ac6595

Just exchange the Render() method in my VoxelSpace.html file with the pastie.

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.

I wonder if you could nearly as efficiently draw to fixed distance arcs instead of perpendicular to viewing area lines to avoid that effect?

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.

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.

Reply on news.ycombinator.com