Technically this is not related to voxels ("volumetric pixels", so to say), which split the 3D space equally along all three axes. This is just a height map, a set of prisms, not entirely unlike a Doom map. Every prism has a regular fixed-size square base.
For 1992, this was mind-boggling though.
DonHopkins 3 minutes ago [-]
Louse Castle developed a "voxel plus" software render for Westwood Studios' 1997 Blade Runner. It used "voxels" (with scare quotes) for character animation, not just terrain.
madmoose on May 28, 2018 | parent | context | favorite | on: How Voxels Became ‘The Next Big Thing’
Blade Runner didn't actually use voxels, they used a rather unique technique that they called "slice animations".
The 3D models were sliced from bottom to top into a couple of hundred slices (depending on desired quality) by intersecting the model with a horizontal plane and storing the resulting polygons.
The engine can only rotate the models around the vertical axis.
I made a hacky javascript version of the renderer a long time ago:
No? Each pixel on a height map corresponds to a column of voxels of the specified height. You could represent the same height data with a fully general octree and it would look exactly the same.
bastawhiz 31 minutes ago [-]
It's kind of weird to call them "columns of voxels" when the columns can't have gaps and the "voxels" below the topmost are ignored completely. Which is to say, they're just columns...which is (definitionally) just a height map.
In fact, an octree for this approach would be _meaningfully worse_ because finding "the topmost voxel" in each column is O(logn)—or maybe worse?—versus O(1) for a height map. With no benefits, because you never look at any other voxels.
binarymax 15 minutes ago [-]
Is this the same algo used for Magic Carpet (1994)? The style looks very familiar, and I always wondered how they pulled it off.
Was this also how the flight sim that used to be hidden in EXEL.EXE had been built, I wonder.
mondainx 25 minutes ago [-]
Reading Voxel always takes me back, way back.. I played Comanche for hours and read up on Voxel tech in various magazines of the day; so clever and easy to implement. Nice demo and thanks for the trip down memory lane.
karmakaze 28 minutes ago [-]
First thing that comes to my mind is the procedural generation in Rescue on Fractalus! (Behind Jaggi Lines) 1984 by LucasFilm Games which blew my mind on Atari 6502.
a1o 2 hours ago [-]
When this was first posted I made a game with a port of this approach to AGS Engine. Nowadays AGS is much faster since we have improved a lot of things, but this wasn’t the case at the time, so I had to make a few little tricks to make the rendering work well with the engine at the time.
I remember figuring all this out as a self-taught teenager (pre-internet) with some books, a whole lot of time, and only a high-school level understanding of trigonometry. I built different versions - first in Pascal, then C, then Assembly.
Figuring out the algorithm was hard, but one of the optimizations I was most proud of was inventing (or so I thought) lookup tables to get around the slow floating point multiplication of my 16MHz 80286 CPU. I also remember "inventing" (ha!) the old bit shift + add technique.
There was something immensely satisfying about squeezing every last drop of performance out of a machine.
Nothing ever came of it. It was more or less a demo, but man did it make me feel like I accomplished something magical. I'd give anything to have a look at that source code today, but this post is the next best thing. So thanks for sharing. This made my day.
Jare 2 hours ago [-]
[Edit] ah ok they clarify later as a performance enhancement. I think it was pretty integral to the algorithm, but ok.
Wait why do they say painter's algorithm. Comanche and other such voxel terrain engines went front to back and never had overdraw.
s-macke 2 hours ago [-]
Author here. Yes, it is integral. I chose this approach to first show how to draw it from back to front, because the code is easier to understand this way.
swiftcoder 2 hours ago [-]
Reverse painters algorithm is still painters algorithm. You trade off the cost of a full screen clear before the frame, in return for eliminating overdraw
knome 2 hours ago [-]
You could avoid a full screen clear by using the y-buffer to draw in sky segments after rendering terrain.
swiftcoder 2 hours ago [-]
You still need to have some sort of mask to tell you which pixels have not yet been written this frame
knome 2 hours ago [-]
that's what the y-buffer is that the article mentions in the front-to-back rendering section.
it tracks how tall each columns write is so you can use it to only write the diff between it and the voxel behind it, skipping writing anything at all if the voxel behind is shorter than the current height.
So once you're done rendering front-to-back, you've got a y-buffer of highest-writes you can slap your blue sky across from highest-to-screentop on each line, avoiding the need to clear by write the sky to the full screen before starting the render.
swiftcoder 48 minutes ago [-]
yes, I guess you can get away with only clearing the y buffer, rather than the whole screen
esafak 2 hours ago [-]
I remember how groundbreaking Comanche was. Now I learned that it was a result of the programmer's experience in the medical industry (CT/MRI scanning): https://en.wikipedia.org/wiki/Voxel_Space
If you render columns instead of rows you can render near-to-far without a Y-buffer and with zero overdraw. :)
nkrisc 1 hours ago [-]
You just store the last highest Y value as you iterate near to far?
mthoms 35 minutes ago [-]
This is true.
I vaguely remember there was something about the VGA architecture of the day that made this approach much slower, but I might be misremembering. My recollection of it is fuzzy. I'm hoping someone will chime in to remind me what I might be thinking of.
It might also just have been that this approach didn't work well with my lookup table optimization (see my other post).
TheChaplain 3 hours ago [-]
I really love this kind of articles, so much to learn.
haruharuha 38 minutes ago [-]
[dead]
swordlucky666 3 hours ago [-]
[dead]
Rendered at 17:36:34 GMT+0000 (Coordinated Universal Time) with Vercel.
For 1992, this was mind-boggling though.
https://en.wikipedia.org/wiki/Blade_Runner_(1997_video_game)
https://news.ycombinator.com/item?id=17171287
madmoose on May 28, 2018 | parent | context | favorite | on: How Voxels Became ‘The Next Big Thing’
Blade Runner didn't actually use voxels, they used a rather unique technique that they called "slice animations".
The 3D models were sliced from bottom to top into a couple of hundred slices (depending on desired quality) by intersecting the model with a horizontal plane and storing the resulting polygons.
The engine can only rotate the models around the vertical axis.
I made a hacky javascript version of the renderer a long time ago:
http://thomas.fach-pedersen.net/bladerunner/mccoy_anim_13_fr...
EDIT: Let me also plug our WIP Blade Runner engine for ScummVM:
https://github.com/scummvm/scummvm/tree/master/engines/blade...
In fact, an octree for this approach would be _meaningfully worse_ because finding "the topmost voxel" in each column is O(logn)—or maybe worse?—versus O(1) for a height map. With no benefits, because you never look at any other voxels.
https://en.wikipedia.org/wiki/Magic_Carpet_(video_game)
https://github.com/ericoporto/i_rented_a_boat
I remember figuring all this out as a self-taught teenager (pre-internet) with some books, a whole lot of time, and only a high-school level understanding of trigonometry. I built different versions - first in Pascal, then C, then Assembly.
Figuring out the algorithm was hard, but one of the optimizations I was most proud of was inventing (or so I thought) lookup tables to get around the slow floating point multiplication of my 16MHz 80286 CPU. I also remember "inventing" (ha!) the old bit shift + add technique.
There was something immensely satisfying about squeezing every last drop of performance out of a machine.
Nothing ever came of it. It was more or less a demo, but man did it make me feel like I accomplished something magical. I'd give anything to have a look at that source code today, but this post is the next best thing. So thanks for sharing. This made my day.
Wait why do they say painter's algorithm. Comanche and other such voxel terrain engines went front to back and never had overdraw.
it tracks how tall each columns write is so you can use it to only write the diff between it and the voxel behind it, skipping writing anything at all if the voxel behind is shorter than the current height.
So once you're done rendering front-to-back, you've got a y-buffer of highest-writes you can slap your blue sky across from highest-to-screentop on each line, avoiding the need to clear by write the sky to the full screen before starting the render.
I vaguely remember there was something about the VGA architecture of the day that made this approach much slower, but I might be misremembering. My recollection of it is fuzzy. I'm hoping someone will chime in to remind me what I might be thinking of.
It might also just have been that this approach didn't work well with my lookup table optimization (see my other post).