Voxel landscapes - flying around...
By Mikael Kalms (Scout / C-Lous)

This text assumes that a normal coordinate system has the X axis going to the right, the Y axis going up, and the Z axis going into the screen. It also assumes that the screen used is a LORES 320x256 one with 2x2 C2P conversion, yielding an effective resolution of 160x128.

The basic idea of a voxel landscape is having a world built up of a lot of vertical bars, where each bar begins very far down and has its height stored in a table. Each bar also has its own, unique colour (preferably stored in a colour-table). You have the bars ordered along a quadratic grid. Another way of thinking of this is that you have laid a grid over a perfect, super-resolution original world and read one 'sample' from every square in the grid and stored them in the y-array and the c-array.

Now you have the height and colour of every vertical bar. If you want to display the voxel landscape on an SGI, you 3d-rotate, perspective project and draw all the bars.

Unfortunately 99% of the readers of this mag do not have enough cash for the SGI, so it is time to develop simplified, approximative, maybe more restricted models of the 3d voxelspace that even run smoothly on our beloved Amigas...

One of the favourite approaches is called 'raycasting'. It is used in most Wolfenstein clones as well. The idea behind raycasting is to determine the contents of the screen by casting rays and checking what they hit, thus calculating "which bar(s) will I see on these pixels?" for all pixels (or groups of pixels), as opposed to rotating/projecting/drawing all bars, thus calculating "which pixel(s) will this bar cover?" for all bars.

Y-rotating landscape We begin with a rotating voxelspace where you can rotate around the Y axis but you always look horizontally.

When drawing the voxelspace, you will consider the screen a set of vertical stripes. Every stripe is a screen-high and extremely narrow "window" into the world. You shoot one ray (horizontally) through every stripe and draw the bars they hit.

In what direction(s) shall you shoot the ray(s)? You have an FOV (Field of Vision) of approx. 180 degrees. That means you can see things in an 180 degree field in front of you (From -90 to +90 degrees relative to your current facing angle). The screen acts like a 'window' into the world and it therefore looks good with an FOV of about 60 degrees in the voxelspace. Therefore you should fire the rays, evenly distributed, in the field -30 to +30 degrees relative to your current facing angle.

When you fire a ray, start from your current position and set the value of a "last Y-coord"-variable to the Y-coord at the bottom of the screen. Then repeat this process "Z-depth of landscape" number of times: Move 1 unit in the direction of the ray, read the Y and C of the bar you are currently on and perspective project the Y-coord (remember that Z increases 1 per step along the ray). Check if this Y-coord is less than "last Y-coord". If it is not, the current bar is not visible, so skip to the beginning of the loop. If it is, draw a vertical line from Y-coord to "last Y-coord" using colour C, set "last Y-coord" to the value of Y-coord and skip to the beginning of the loop.

If we name the XY axes in the voxeltables 'UV' to avoid confusion with screen XY coordinates, pseudocode for the voxelrout could look like this:

;eyeU, eyeV and eyedir are variables containing current UV and direction
;persp is perspective-constant. 30 or so may look good
raydir = eyedir + 30
raydirinc = -60 / scrwidth
for X = 0 to scrwidth do
{
lastY = scrheight
;lastY = bottom of screen
U = eyeU;
;Start at eye position
V = eyeV;
Uinc = cos(raydir)
;Stepsize along U
Vinc = -sin(raydir)
;Stepsize along V
For Z = 1 to zdepth do

{
U = U + Uinc
;Step 1 unit along U
V = V + Vinc
;Step 1 unit along V
Y = voxelYtab[U][V]
;Get Y coord
Y = persp*Y/Z + (scrheight/2)
;Persp project
if y < 0
{
y = 0
;Clip to top of screen
}
if y < lasty
{
C = voxelCtab[U][V]
;Get colour of bar
line from X,Y to X,lastY with colour C
lastY = Y
;New Y of last drawn bar
}
if lastY = 0
{
End this ray
;Reached top of screen
}
}
raydir = raydir + raydirinc
}

raydirinc is negative since the screen is gone through left-to-right. Vinc is set to -sin to change the V axis orientation (up to down). This routine MAY draw a mirrored landscape since I (the author of the article) made the pseudcode from scratch. The UV stepping should be done using 8:8 fixed point math. (I will not describe fixed point math here.)

It is easy to apply depth-shading to this since we always have the Z value at hand when drawing a bar. Precalculate another 2d table, that: given a colour C at depth Z, gives us a new colour C. (Use 24-bit truecolour when precalculating the new C values, and then, in order to get back to 256 colours, find the best matching colours in the palette. Save the 2d-table with 256-colour entries.) Then add one more line after "C = ..." in the voxelrout: C = VoxelZshade[Z][C]. That will give your voxel landscape good-looking Z-shading.

Z-rotation
Three alternatives here.
You can 'shear' the landscape. This looks good when you rotate max 30 degrees around the Z axis. It does not work well if you rotate more than 45 degrees. It is done by adding "shearXfactor*(x-(scrwidth/2))" to the Y-coord after perspective projection, where shearXfactor = sin(Zangle). If you want to be able to do full 360 degree rotations around the Z axis, you must either draw non-vertical lines or split the process into two parts, where the first part draws the landscape without Z-rotation, and the second part is a zoomrotator that rotates the newly generated picture around the Z axis.

X-rotation
This is the hardest effect of all. When you rotate around the X axis, the vertical stripes on screen should not remain vertical anymore. (Draw some vertical lines on a piece of paper and check what happens when you rotate the paper around the X axis, then you will see what I mean.) They should not even remain lines! (Perspective effects make them wider at the end that's closer to the eye... argh :)) The only sensible approximation I know of is 'shearing' the landscape in Z direction. It is done by adding "shearZfactor*Z" to the Y-coord before perspective projection, where shearZfactor = sin(Xangle).

If you want examples on some of these methods, Artwork's "The Gate" (first place at Symposium'96) uses the 'shear' method for both X- and Z-rotation, while C-Lous' "Kolor" (Icing'96) and "Kolor remix" (Remedy'96) uses 'shear' for X- and 2-pass for Z-rotation. Artwork's voxelroutine has some more features though:

Y-coord interpolation
In order to get rid of the "jaggedness" of the landscape (the individual bars are clearly visible if you don't have gazillions of them), you can interpolate the y-coordinates. It is done by interpolating between the four UV values closest to your current UV position. The interpolation shall be performed every time you read a Y-value out of voxelYtab, and in a fashion like this:

;UV are floating point values, Ufraction & Vfraction are fractional parts of them
slope1 = voxelYtab[U+1][V] - voxelYtab[U][V]
slope2 = voxelYtab[U+1][V+1] - voxelYtab[U][V+1]
Y1 = slope1 * Ufraction + voxelYtab[U][V];
Y2 = slope2 * Ufraction + voxelYtab[U][V+1];
slope3 = Y2 - Y1;
Y = slope3 * Vfraction + Y1;

//Then Y is the interpolated Y coordinate

Observe that if your landscape has voxelYtab as bytes, slope1 is -255 .. +255, and if UV are 8:8 fixed point vals, Ufraction and Vfraction is 0 .. +255, so you can relpace the multiplications with table lookups: Have a mul-table that is 512*256 bytes large and index it via: multab[slope1][Ufraction].

This sceme can be simplified even more if necessary. (For example only interpolating along U or V axis, depending on which has the largest step length.)

C-value interpolation This is just vertical Gouraud-shading. If Y-coords are interpolated, interpolate C-values the same way. Have a 'last C-value' variable. Then have your linedrawer draw Gouraud shaded vertical lines:
//Vertical Gouraud shader
Cinc = (C2 - C1) / (Y2 - Y1)
for pixelY = Y1 to Y2
{
putpixel(X,Y,C)
C = C + Cinc
}

Tables can be used here as well. Since C2-C1 is -255 .. 0 .. +255 and Y2-Y1 is 0 .. +scrheight, have a Cinctab that is scrheight*512 words large. (words since Cinc is 0 .. +255.255 with 8:8 fixed point)

Correcting some errors The Ustep and Vstep expression has an error. It would be correct if we had 3d hologram-styled screens, but as we use 2d screens we distort the contents to make it look good. One of the rules we use is that distance to a point on screen is measured along the eye direction, which makes that changing x or y doesn't change the distance to the point. Z = distance of the point. However, this error makes the steps at the edges of the screen 'shorter' in terms of change in Z. We can correct this error by dividing Ustep and Vstep with cos(eyedir - raydir) (= -30 .. 0 .. +30). That will make Z change correctly, and the shading correct. It also looks better performing rotations about the Y axis. This tweak makes the rays at the edges longer than 1, so you may want to make steps with a Z-length of cos(30) instead of 1 (= cos(0)).

Full 3d Despite the 3d look of all the prevoiusly described algorithms, they are technically still just 2d algorithms with perspective projection. How about a full 3d one...? Instead of raycasting every vertical stripe you raycast EVERY PIXEL. The rays are stepped in UVW direction. A hit is when voxelYtab[U][V] < W. (This means that the ray has collided with a bar.) When a bar is hit, a pixel is drawn with the colour of the bar, and that ray is finished.

There are many ways of calculating the directions of the rays. One is placing a grid in front of you in 3d space and calculating the direction from the eye to every intersection in the grid. One advantage of this method is that the rays' steplength in Z direction is automatically corrected for the 3d->2d distortion.

Another method is measuring the screen in degrees. It has alreay been done along the X-axis (-30 .. 0 .. +30), but if you have degrees along the Y-axis as well you have some very interesting calculations ahead... The calculation of UVWstep sure don't look easy, but maybe it can be performed using spherical coordinates or something like that? Then the UVWstep should be divided by (cos(Xdeg)*cos(Ydeg)) to correct Z-step length.

An example of one version of the full 3d technique can be found in TBL's demo "MindProbe" (TP95). That routine uses a 3d cube with pixels instead of a 2d voxeltable, but it is almost the same technique.