Ray Casting… Again…

Previously I visited a really simple and terrible way to render voxel terrain.  It involved stepping along a ray at uniform intervals, and simply sampling the height map at whichever texel the current point along the ray falls into to.  Its crude, but it works.  I would have liked to use my previous ray casting code to step along each ray, but the algorithm prohibits this.  That is because the old algorithm steps along in the x-axis intervals until it hits something and saves it.  Then it steps along the y-axis intervals until it hits something.  Finally, it takes the real hit point as the closer of the two hit points found.  That is simple and efficient when we only want to know the first intersection point, but useless when we need to step in order through a height map.

To improve the voxel landscape renderer, I needed to write a better raycast algorithm.  A requirement for its intended purpose is that the algorithm will visit each tile of the map in the order in which they are hit.  Something like a straight line algorithm (Bresenham’s) would do this, sure, but I also need to know exactly where each intersection takes place, and extra information on top of that, so a better solution had to be found.

I also should point out that I took every opportunity to ensure that this ray-cast method wouldn’t be only applicable to voxel landscape rendering.  It can be used in exactly the same fashion as my previous ray-caster, only this one should be more robust, and has a few nice additional properties.

It can return the exact tile that was hit, the exact location of the intersection and a code representing the side of the tile that was hit.  Also I needed to ensure that a hit would not be registered from the tile that the origin lies in.  This requirement is for other uses, such as light mapping, and radiosity calculations.  A demo I badly want to make would be 2D a radiosity light mapper using a photon vomiting approach.  Therefore I needed to ensure that I can find a normal ray intersection point, and later compute a reflected ray around that point, to simulate light bounce.  An issue I worried about and previously had trouble with was when the origin of a ray lies essentially touching a blocking tile.  This is an issue I hope has been resolved now.


The above image was generated in a stress test for the new algorythm where all rays are traced from the origin radiating out evenly in a circle.  In this case the origin is obviously the blue circle.  Lines are then drawn from the origin to the intersection points, which gives the appearance of a light source when a sufficient number of rays are used.  The stress test shows that the algorithm appears stable at all angles of ray, and was fast even when spitting out > 500 rays.  The new algorithm can be found below, but please give me some credit if you use it for anything.



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s