4 ms·

I don't think in Comanche they painted back to front, or at least I hope they didn't. It's best to render front to back, tracking the highest (in screen space)

by Jare 6y ago

I don't think in Comanche they painted back to front, or at least I hope they didn't. It's best to render front to back, tracking the highest (in screen space) pixel you have drawn, and as you move further back, only drawing lines from that height. That "max height" is a zbuffer of sorts for each ray. [edit: I just read further down and they mention this] Also, you want to render each ray/vertical screen line one at a time, rather than running each single step of the ray for all rays/vertical lines. Once you are rendering each ray at once, it's easy to do a circular rather than flat projection, which feels a lot more stable when you rotate and admits higher fields of view without distortion.

ironSkillet 6y ago
He mentions the front to back optimization, keeping track of the max height.
- jameshart 6y ago
  He misses the additional optimization of tracking one ray at a time - depth first rather than breadth first. You don’t need to hold a complete z-buffer, just know the last height/distance you drew, and keep scanning out along the line until you find another terrain point high enough to see.
  - s-macke 6y ago
    Author here. But then you have a division of each coordinate. And this was more expensive than a memory lookup. So you might end up with a table as well. You have to test and optimize both approaches to be really sure.
    - jameshart 6y ago
      I’m not sure why a division is necessary. When you send a ray out in a given direction through the screen, you can calculate its height in world space at distance z just by multiplication; and you can construct that ray entirely by multiplication and addition of values that are constant for the frame. So you can march a point out in increasing z along a ray pointing towards the bottom of the screen, then when it hits the ground, move it up the screen until it stops hitting the ground, then draw that line and start increasing z again. The perspective correction division just disappears completely. I don’t disagree that you need to benchmark approaches to see if they will work, but it’s got to be interesting to consider if it’s possible to avoid allocating a buffer to store the height reached per column, right?
jedimastert 6y ago
> I don't think in Comanche they painted back to front, or at least I hope they didn't. It's best to render front to back, tracking the highest (in screen space) pixel you have drawn, and as you move further back, only drawing lines from that height. That "max height" is a zbuffer of sorts for each ray. Discussed here <https://github.com/s-macke/VoxelSpace#more-performance https://github.com/s-macke/VoxelSpace#more-performance>
ant6n 6y ago
> Also, you want to render each ray/vertical screen line one at a time, rather than running each single step of the ray for all rays/vertical lines. This may require more performance. Remember, this algorithm was used for an early Nineties game. The advantage of drawing along a line of same-distance (i.e. constant z) is that per pixel, there are no divisions, only additions and one multiplication (which could perhaps be optimized away?). Drawing vertical screen lines, you get the z-division for each step. (Then again, perhaps the division could be removed with a look-up-table)
- Jare 6y ago
  I wrote the code for this in late 1993 https://www.youtube.com/watch?v=9KoUyFhddIs&t=102 https://www.youtube.com/watch?v=9KoUyFhddIs&t=102 . You can find the C + assembly source code in https://archive.scene.org/mirrors/hornet/code/effects/land/ign_land.zip https://archive.scene.org/mirrors/hornet/code/effects/land/i... Yep, we used a lookup table with built-in levels of detail. Since rays always sample the terrain at the same Z distances from the camera, the lookup was trivial. Rendering vertical lines had additional benefits back then, including faster use of paged VGA video modes and, as described, doing circular projection to avoid deformations on the sides of the screen.
  - ant6n 6y ago
    Interesting. It looks very nice! I could imagine mixing in "normal" polygons with this approach may not be trivial, though. I couldn`t find much information about this circular projection online, some napkin-math tells me that straight lines in world-space don't project into straight lines in screen-space. just drawing a triangle is not trivial.
scoot 6y ago
> It's best to render front to back, tracking the highest (in screen space) pixel you have drawn As mentioned in the README of the linked repo: 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.

by Jare 6y ago

ironSkillet 6y ago

He mentions the front to back optimization, keeping track of the max height.

jameshart 6y ago
He misses the additional optimization of tracking one ray at a time - depth first rather than breadth first. You don’t need to hold a complete z-buffer, just know the last height/distance you drew, and keep scanning out along the line until you find another terrain point high enough to see.
- s-macke 6y ago
  Author here. But then you have a division of each coordinate. And this was more expensive than a memory lookup. So you might end up with a table as well. You have to test and optimize both approaches to be really sure.
  - jameshart 6y ago
    I’m not sure why a division is necessary. When you send a ray out in a given direction through the screen, you can calculate its height in world space at distance z just by multiplication; and you can construct that ray entirely by multiplication and addition of values that are constant for the frame. So you can march a point out in increasing z along a ray pointing towards the bottom of the screen, then when it hits the ground, move it up the screen until it stops hitting the ground, then draw that line and start increasing z again. The perspective correction division just disappears completely. I don’t disagree that you need to benchmark approaches to see if they will work, but it’s got to be interesting to consider if it’s possible to avoid allocating a buffer to store the height reached per column, right?

jedimastert 6y ago

> I don't think in Comanche they painted back to front, or at least I hope they didn't. It's best to render front to back, tracking the highest (in screen space) pixel you have drawn, and as you move further back, only drawing lines from that height. That "max height" is a zbuffer of sorts for each ray. Discussed here <https://github.com/s-macke/VoxelSpace#more-performance https://github.com/s-macke/VoxelSpace#more-performance>

ant6n 6y ago

> Also, you want to render each ray/vertical screen line one at a time, rather than running each single step of the ray for all rays/vertical lines. This may require more performance. Remember, this algorithm was used for an early Nineties game. The advantage of drawing along a line of same-distance (i.e. constant z) is that per pixel, there are no divisions, only additions and one multiplication (which could perhaps be optimized away?). Drawing vertical screen lines, you get the z-division for each step. (Then again, perhaps the division could be removed with a look-up-table)

Jare 6y ago
I wrote the code for this in late 1993 https://www.youtube.com/watch?v=9KoUyFhddIs&t=102 https://www.youtube.com/watch?v=9KoUyFhddIs&t=102 . You can find the C + assembly source code in https://archive.scene.org/mirrors/hornet/code/effects/land/ign_land.zip https://archive.scene.org/mirrors/hornet/code/effects/land/i... Yep, we used a lookup table with built-in levels of detail. Since rays always sample the terrain at the same Z distances from the camera, the lookup was trivial. Rendering vertical lines had additional benefits back then, including faster use of paged VGA video modes and, as described, doing circular projection to avoid deformations on the sides of the screen.
- ant6n 6y ago
  Interesting. It looks very nice! I could imagine mixing in "normal" polygons with this approach may not be trivial, though. I couldn`t find much information about this circular projection online, some napkin-math tells me that straight lines in world-space don't project into straight lines in screen-space. just drawing a triangle is not trivial.

scoot 6y ago

> It's best to render front to back, tracking the highest (in screen space) pixel you have drawn As mentioned in the README of the linked repo: 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.