AXEL engine- modification of voxel terrain algorithm

Introdction

Voxel engine is simple and fast routine that allows to create 3D scenes even on relatively slow platforms such as Atari or Commodore. The method is somehat similar to raycasting since we cast "rays" for each column of pixels and check for the intersection ith the elements of array.
In this article one can get to know more information about said engine. I will try to summarize the knowledge about this method here.

 

 

In the above image one can see the basic principle of voxel terrain- we have a camera located somewhere aove the ground and the terrain below.  The terrain is represented as a two-dimensional array of bytes, which means the altitude of the land varies from 0(lowest) to 255(highest) .

 

First thing we need to do is casting the rays. Each ray can be represented as 2D vector, for X and Z coordinate values, for instance p(0.1,0.9). We can achieve that by calculating sine and cosine of the given angle. The 2D coordinate will be used in iterating through 2D array. we do it by adding fractional values of unit vector to camera origin "above" the 2D array of points.

 Next inportant thing to remember is the fact that we draw oour screen from bottom up, column by column.

When we iterate through the array we need to constantly check if a given value needs to be casted onto the screen. We can calculate it by performing following equation (excerption taken from mentioned link):

Ys = ( Yv - Ye ) * Yk / Z + Yc

Ys: coordinate projected onto the screen
Yv: altitude of the voxel column
Ye: coordinate of the eye
Z: distance from the eye to the considered point
Yk: constant to scale the projection, possibly negative
Yc: constant to centre the projection, usually half the screen resolution

As one can see we are taking Z value into account in order to caluclate actual altitude of given array velue- same value can look differently depending on distance to the camera.

Then, when we have positionn of the we can check if it's bigger than last drawn and calculated position of the closer element. In case it's bigger we can plot one or more pixels of the same colour vertically- depending on distance from the last drawn column. For instance if the previous pixel was drawn at position 34 and our new voxel should be placed at psoition 50, the we have to fill the gap all the way from 33 to 50 by a single clour indicated by our voxel coordinate (in case we use lookaup table for texture) or altitude (in case we draw higher voxels as brighter).

As one can see the algorithm is quite simple and fast and can be optimized in many way speed-wise. Unfortunatelly voxel terrain engine has some limitations.

Limitations of Voxel Engine

First downside of this method is the fact it requires a lot of memory for arrays. 256x256 byte array takes 64 Kb of RAM which is quite much when we are dealing with older computers. Unfortunately there's is no actual solution to this- we just have to accept the fact that this effect will take a lot of memory.

Another downside is the fact that voxels aren't really 3D, they are more ike 2,5D similarily to some early 3D games as Duke Nukem 3D or Doom. Actually we are always  casting rays in 2D field neglecting the Y axis- in other words we only iterate through 2D array without taking into account third dimension, that 's wy all voxel terrain engines alays "look" in one direction in frot of the camera.

AXEL terrain engine- introduction

The basic principle of this method is taking into account all 3 dimensions of the graphics. It turns out it's possible to use voxel-like method but also transforming it in a way that it ran now represent add 3 dimensions.

In order to do so we need to examine three possibilities, represented by following images:

On the first figure we can see that all elements of the array that are in scope need to be displayed on screen, simply because there is nothing that obscures them- they are all visible from the above.

Third image depicts situation that almost no perspective calculations need to be applied simply because the canera is facing zero degrees angle (or sideways in other words). During calculations we only need to check if next voxel is above previous one.

Finally second image shows a situation "something in the middle"- there are areas obscured by bumps of terrain and the angle of camera may vary.

Those are three general situations when coping with arbitrary camera movement.

Actual algorithm

 

 The whole idea is to iterate through the array representing the height of the terrain in a specific way- when the camera looks forward then we take into account the points that are higher than the previos ones that were drawn- just like in real voxel alogrithm. When the camera starts lbeing directed down then more points are being taken into account since less points cover the next points. While the camera looks directly from top to down then all points are being drawn.

 

factor=200/25;

for(aa=0;aa<100;aa++){
x=sin((ang+aa/2)*f);
z=cos((ang+aa/2)*f);  
factor_z=factor;
decr_z=1-factor*0.001;
addition_y=-factor*90;
for(dd=0;dd<150;dd++){
col=0;
h=field[p[0]][p[2]];
p[0]+=x*factor;
p[2]+=z*factor;
curr_height=(h*factor_z)+addition_y;
addition_y+=3-factor;
factor_z*=decr_z;
if(curr_height>prev_height){
col=h;
delta=curr_height-prev_height;
prev_height=curr_height;
for(a=0;a<delta/2;a++){
put_pix(aa,100-hi-a,col);
}
hi+=delta/2;
}
}

}

The code may seem to be complicated but it is actually not. Let's go thorugh it step by step:

factor=200/25;

Factor variable holds information about angle of the camera, 0 means that camera is perpendicular to the ground whereas values above 1 mean that camera is approaching parallel direction.

x=sin((ang+aa/2)*f);
z=cos((ang+aa/2)*f);  

Here we set up vector that will be used for iterating through the array.

factor_z=factor;
decr_z=1-factor*0.001;
addition_y=-factor*90;

Next we set up initial values of three key variables:

factor_z- this is a number that will be used to scale voxel point from the array in order to decrease or increase differences between next voxel array elements. This variable is used along with "addition_y" number. 
decr_z- this number is used for perspective projection. It will help to change "factor_z" value along the way of each ray. It will be discussed in details further.
addition_y- this variable is used for correcting the offset of pixels on the screen (centering spixels) and also it's used for modifying voxel values in order to hide or unhide elements behind the bumps and hills. It will be described later in this tutorial.

for(dd=0;dd<150;dd++){
col=0;
h=field[p[0]][p[2]];
p[0]+=x*factor;
p[2]+=z*factor;

This is the inner loop resopnsible for drawing a single column. At the begining we set up default color value, then we read from the voxel array and ncrease te 2D vector used for iterating through that array.
Important part of this multiplicating the X and Z step by constant value so the iterating through the array of terrain is changed according to camera facing different angles.

curr_height=(h*factor_z)+addition_y;
addition_y+=3-factor;
factor_z*=decr_z;

This is the place where actual magic happens. Curr_height is a code that caluclates perspective projection of voxel array point. By multiplying h (voxel) wih factor_z we decrease the value of h for two reasons:
-to have points closer being lower than those situated far away (thanks to "factor_z*=decr_z" code, which modifies value each iteration of the loop).
-to decrease difference between close voxels for approaching perpendicular position of the camera.

As one can see factor_z and addition_y are two main forces that influence perspective of the voxel- if voxel values are shrunked by multiplying them by"factor_z" then adding extra value will result in drawing  given voxels on the scrreen - it's useful in situations when camera is approaching perpendicular position tho the ground and differences between next voxels are close to zero (thanks to "factor_z" being close to zero), then if we add extra number to the equation then next "if" condition will recognize two nearby voxels as different points that need to be plotted on screen.
"addition_y+=3-factor" is just modification of mentioned variable so it can reflect current slope of camera.

if(curr_height>prev_height){
col=h;
delta=curr_height-prev_height;
prev_height=curr_height;
for(a=0;a<delta/2;a++){
put_pix(aa,100-hi-a,col);
}
hi+=delta/2;
}

At last it's time for plotting the pixels. First we check if current voxel is above the previous one. If that is positive then we set up color of pixel to voxel high (but can be other value). Then we calculate distance between current and previous hieghts of voxels and save new value of voxel as previous value for next iteration.
At the end we invoke pixel drawing procedure that plots the pixels in reversed order ("100-h-a") because screen memory starts at upper paert not the lower one, and you can remember that we draw columns in reversed order.

That's prretty much all. Full source code (as Eval Draw file) can be found here.
Happy coding!