- Ray Casting
- Fast Canvas Drawing
- Back to basics - Binary search
- Back to basics - Bubble sort
- Remote machine development
- WebAssembly In The Browser
- WebAssembly Brief Intro
- The Programming Metagame
- Raspberry Pi Zero Cluster
In the previous entry, I experimented with some simple ways to draw pixels in a canvas, using that as a starting point, I want to implement a very simple Ray Caster.
The ray casting algorithm is very simple, given a 3D scene descriptor and a camera, it outputs a 2D representation (raster) of it. I'll be implementing several functions to generate the ray caster elements and a pipeline to make it easier to extend.
First thing is to create a function that returns a very simple 3D scene representation. Right now, only spheres are supported, and that is what the following code returns in an array.
The aspect ratio function below is mostly used to make it easier to change the output image geometry and keep the scene elements looking as intended, i.e. the spheres should not look stretched. This function uses Euclid's algorithm to find the Greatest Common Divisor to convert a width/height pair, i.e.
640/480 into the corresponding
4:3 aspect ratio.
Next up, I'll create another function to return the camera configuration, this is used to generate the primary rays.
The given points represent the geometry of the camera, this are used to calculate 3D space points that correspond to the desired output image geometry. In other words,
leftBottom map to the points
(width - 1, 0) and
(0, height - 1) in the final image.
Which also means that, for the first row of the final image (and all rows afterwards), and interpolation will be calculated from
Since I am discussing the output image geometry, I'll add a function to create those as well.
Now it is a good time to introduce some helper functions for vectors that will be required later. This functions are coded so they present a fluent interface, this is not required but it makes for some interesting code later on.
This brings me to the next code, the function that generates the primary rays. These are the rays that have the
eye of the camera as the origin and a direction that represents a mapped pixel from the
imageGeometry to the
camera plane. They are called
primary as they are the starting point for calculating each pixel of the final image.
Having the primary rays ready, the next step is to detect the intersections between each of them and the scene. But first I need the intersection detection function, as mentioned previously, this only supports finding intersections with spheres.
Now I proceed to create the tracing function, this will take one ray and test is against all the objects in the scene. The output will be the closest hit point and the sphere that was found, unless there was no intersection in which case the result is only an
Object with the
hit property set to
Next up is writing the function that will take each primary ray and run them through the intersection function.
With the results of the primary ray intersections, the following code determines if there was a hit, if so, it will take the sphere that was found and take its color, if no hit, then it will simply return
0xff999999. Each pixel is a 32bit ABGR value.
Up to this point I have written a bunch of standalone functions, next is the implementation of a pipeline that will take an array of functions, that are executed one after the other, each getting an accumulated
Object that contains all the results from previous functions calls.
Finally, I take it all together and generate a pipeline that returns a bitmap, which is then rendered in the canvas right after this.
To see the results, click on the Run button, you can go back and modify any of the previous code to change how this ray caster behaves.
The Ray Casting algorithm was used in early 3D games like Wolfenstein 3D because it is simple and fast, it is also the starting point for more involved rendering algorithms like Ray Tracing