Ok, I've got a brand new algorithm that I'm going to try. This one so far is much much faster than the old one and allows some pretty insane viewing distances.
The problem with the old one was stepping through the map by cos and sin. This is sort of like trying to draw a line between two points on a screen using increments lower than 1. Deathly slow. Not to mention that sometimes you will have unecessary overdraw because your ray will hit the same cell, or in the case of the screen - the same pixel, many many times.
So my new algorithm still uses sin and cos to create the ray, but it creates a line between 2 points and draws a line between them in the map using Bresehnams algorithm. Since this algo is integer based it simply flies and it produces perfect ray-to-voxel intersections. Also I can increase the step size through the map which can produce some insance viewing distances with little or no performance loss.
To move this to 3D will be simple. I will just need a 3D Bresehnam's algo and it is quite possible that I can produce a 6 DOF voxel engine with very fast framerates. Also since I'm stepping through the map by integers...the shimmering that usually happens in voxels engines won't be there because the intersections will be pixel perfect - no floating point values to mess with, no nearest point sampling, etc. The only floats will be when I divide the world ray coords by the cellsize. I subtract that value from its integer counterpart to get the barycentric coords to use in the interpolation. So I've moved from all floats to 2 floats.
Here is some sample code:
Code:
//Starting point of ray
ray.x=player.x;
ray.z=player.z;
//Angle stepping
angle.x=CS[player.angle];
angle.z=SN[player.angle];
//Ending point of ray
ray.x2=player.x+(angle.x*cast_distance);
ray.z2=player.z+(angle.z*cast_distance);
//Differences
ray.diffx=ray.x2-ray.x;
ray.diffz=ray.z2-ray.z;
//Step size
//Very similar to old school DOS rendering
//stepy=320, stepx=1
//No need to step in y
int stepx=1;
int stepy=mapwidth;
//Compute mapoffset
//Map is 1024x1024
DWORD mapoffset=(ray.z<<10)+ray.x;
//Check for diffx<0 and diffz<0
if (ray.diffx<0)
{
ray.diffx=-ray.diffx;
stepx=-stepx;
}
if (ray.diffz<0)
{
ray.diffz=-ray.diffz;
stepz=-stepz;
}
//Now draw the line using the algo
...
...
There is no difference drawing a line in an array in memory (the map) as opposed to the screen. Both are arrays in memory as far as the computer is concerned. So any technique that is used to speed up rendering on the screen can also be used on arrays in memory since both are arrays in memory.
I will post the EXE very soon. I hope to get some very very good viewing distances with this new algo. Since my algo is very fast...the bilinear interpolation on color and height should have plenty of cycles to play with before the rendering gets too slow.
The Pentium 4 can do integer operations in one half clock tick...so this algo should scream.
Screen shots to follow.
