3 ms·
I suspect this could be done in reverse, for a profitable speedup. So that is to say, by following the painter's algorithm (far to close), we draw a lot of pix
by kazinator 6y ago
I suspect this could be done in reverse, for a profitable speedup.
So that is to say, by following the painter's algorithm (far to close), we draw a lot of pixels over and over again. If the closer terrain is rendered first (reverse painter's algorithm), fewer pixels have to be filled for the farther terrain. In some cases, none at all.
The basic premise is this: an element of the color/height map which is farther from the viewer will never occlude an element which is closer, regardless of its relative height, and regardless of the perspective projection. The elements of the map are colored, vertical columns. A column farther from the viewer cannot occlude a closer column.
Suppose our task is to render exactly two arbitrary elements into an empty frame buffer. We can confidently render the closer one first, and then render the farther one, painting the "pillar" from top to bottom, until we are about to hit a pixel which has already been colored. All those early breaks out of the column-painting loops can be expected show a marked speedup.
I'd be surprised if the 1992 game didn't do it that way; they were squeezing every cycle they could get out of 386 and 486 boxes.
- ChrisClark 6y agoYeah, that's how the optimization is done in the link I think.
- cma 6y agoFrom the article: >More performance >There are of course a lot of tricks to achieve higher performance. >Instead of drawing from back to the front we can draw from front to back. The advantage is, the we don't have to draw lines to the bottom of the screen every time because of occlusion. However, to guarantee occlusion we need an additional y-buffer. For every column, the highest y position is stored. Because we are drawing from the front to back, the visible part of the next line can only be larger then the highest line previously drawn. Level of Detail. Render more details in front but less details far away.
- kazinator 6y ago> However, to guarantee occlusion we need an additional y-buffer Not necessarily. If there is a uniformly colored background, and the pixels being drawn are of a different color, you can test the existing pixel value to determine whether it's a foreground object, or background. In the rare case that an object pixel value happens to be the same as the background, you can make an alteration in the least signficant bit of the least sensitive color to make it different. If there is a complex background, chances are you have a full copy of it, and can refer to it to see if any pixel in the image has changed. And in any case, a Y buffer is just the size of one scan line. E.g. using a 1024x768 screen as an example (3 byte RGB pairs), you need 1024x2 bytes for the Y buffer. That's .08% of the size of the frame buffer. You could use a scan line in the frame buffer for this storage. If you are not actually using the entire screen (because, say, the game shows the inside of a cockpit with instrumentation) there is no sacrifice at all; after being done using that temporary memory, you will draw over it anyway.
- n3k5 6y agoYup. A.k.a. depth testing†. TFA illustrates it under ‘More performance’: https://github.com/s-macke/VoxelSpace#more-performance https://github.com/s-macke/VoxelSpace#more-performance Edit: Originally, I had said: “Though in a highly constrained scenario such as this, with the right approach you could get away with a 1-bit depth buffer.” That would be true if you had one depth value per pixel, which is of course so common nowadays that no one even needs to think about it. Except in this case I should have thought about it, because this algorithm requires only one depth (or, alternatively, as TFA and parent comment explain, Y) value per column of pixels. † https://en.wikipedia.org/wiki/Z-buffering https://en.wikipedia.org/wiki/Z-buffering