Eccentric DevelopmentsIn 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.
function createScene() {
return {
scene: [
{
center: [0.0, 0.0, 0.0],
radius: 5.0,
color: [0, 0, 1.0],
},
],
};
}
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.
function createAspectRatioFunction() {
return {
aspectRatio: (width, height) => {
let gcd = width;
let reminder = height;
while (reminder != 0) {
const temp = reminder;
reminder = gcd % reminder;
gcd = temp;
}
return [width / gcd, height / gcd];
},
};
}
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, leftTop, rightTop and leftBottom map to the points (0,0), (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 leftTop to rightTop having width steps.
function createCamera(args) {
const { width, height, aspectRatio } = args;
const [w, h] = aspectRatio(width, height);
return {
camera: {
leftTop: [-w, h, -50.0],
rightTop: [w, h, -50.0],
leftBottom: [-w, -h, -50.0],
eye: [0.0, 0.0, -75.0],
},
};
}
Since I am discussing the output image geometry, I'll add a function to create those as well.
function createImageGeometry({ width, height }) {
return {
imageGeometry: {
width,
height,
},
};
}
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.
function createVectorFunction() {
const zip = (A, B) => A.map((a, idx) => [a, B[idx]]);
const sub = (A, B) => zip(A, B).map(([a, b]) => a - b);
const add = (A, B) => zip(A, B).map(([a, b]) => a + b);
const mul = (A, B) => zip(A, B).map(([a, b]) => a * b);
const dot = (A, B) => mul(A, B).reduce((acc, v) => acc + v, 0.0);
const scale = (A, s) => A.map((a) => a * s);
const norm = (A) => Math.sqrt(dot(A, A));
const unit = (A) => scale(A, 1.0 / norm(A));
const getValue = (A) => A.value?.() ?? A;
const vector = (A) => ({
zip: (B) => vector(zip(A, getValue(B))),
sub: (B) => vector(sub(A, getValue(B))),
add: (B) => vector(add(A, getValue(B))),
dot: (B) => vector(dot(A, getValue(B))),
scale: (s) => vector(scale(A, getValue(s))),
unit: () => vector(scale(A, 1.0 / norm(A))),
value: () => A,
});
return {
vector,
};
}
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.
function calculatePrimaryRays(args) {
const {
camera: { rightTop, leftTop, leftBottom, eye },
imageGeometry: { width, height },
vector,
} = args;
const vdu = vector(rightTop)
.sub(leftTop)
.scale(1.0 / width);
const vdv = vector(leftBottom)
.sub(leftTop)
.scale(1.0 / height);
const primaryRays = [];
for (let y = 0; y < height; y++) {
for (let x = 0; x < width; x++) {
const pixel = y * width + x;
const origin = eye;
const direction = vdu
.scale(x)
.add(vdv.scale(y))
.add(leftTop)
.sub(origin)
.unit()
.value();
primaryRays.push({
pixel,
origin,
direction,
});
}
}
return {
primaryRays,
};
}
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.
function createIntersectionFunction(args) {
const { vector } = args;
const intersect = (ray, sphere) => {
const { center, radius } = sphere;
const oc = vector(ray.origin).sub(center);
const a = vector(ray.direction).dot(ray.direction).value();
const b = oc.dot(ray.direction).value();
const c = oc.dot(oc).value() - radius * radius;
const dis = b * b - a * c;
if (dis > 0) {
const e = Math.sqrt(dis);
let t = (-b - e) / a;
if (t > 0.007) {
const point = vector(ray.direction).scale(t).add(ray.origin).value();
return {
hit: true,
distance: t,
point,
};
}
t = (-t + e) / a;
if (t > 0.007) {
const point = vector(ray.direction).scale(t).add(ray.origin).value();
return {
hit: true,
distance: t,
point,
};
}
}
return {
hit: false,
};
};
return {
intersect,
};
}
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 false.
function createTraceFunction(args) {
const { scene, intersect } = args;
const trace = (ray) =>
scene
.map((sphere) => ({ ...intersect(ray, sphere), sphere }))
.filter(({ hit }) => hit)
.reduce(
(acc, intersection) =>
intersection.distance < acc.distance ? intersection : acc,
{ hit: false, distance: Number.MAX_VALUE }
);
return {
trace,
};
}
Next up is writing the function that will take each primary ray and run them through the intersection function.
function tracePrimaryRays(args) {
const { trace, primaryRays } = args;
const traceResults = primaryRays.map((ray) => ({
ray,
intersection: trace(ray),
}));
return {
traceResults,
};
}
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.
function generateBitmap(args) {
const {
traceResults,
imageGeometry: { width, height },
} = args;
const bitmap = new Uint32Array(width * height);
traceResults.forEach(({ intersection }, idx) => {
const { hit, sphere } = intersection;
let pixel = 0xff999999;
if (hit) {
const [r, g, b] = sphere.color;
pixel = (255 << 24) | (Math.floor(b * 255) << 16) | (Math.floor(g * 255) << 8) | Math.floor(r * 255);
}
bitmap[idx] = pixel;
});
return {
bitmap,
};
}
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.
function pipeline(fns) {
return (args) => {
let results = { ...args };
for (const fn of fns) {
results = { ...results, ...fn(results) };
}
return results;
};
}
Finally, I take it all together and generate a pipeline that returns a bitmap, which is then rendered in the canvas right after this.
const canvas = document.getElementById("canvas-1");
const ctx = canvas.getContext("2d")
const width = canvas.width;
const height = canvas.height;
const renderingPipeline = pipeline([
createAspectRatioFunction,
createScene,
createCamera,
createImageGeometry,
createVectorFunction,
calculatePrimaryRays,
createIntersectionFunction,
createTraceFunction,
tracePrimaryRays,
generateBitmap,
]);
const { bitmap } = renderingPipeline({ width, height });
const imageData = new ImageData(new Uint8ClampedArray(bitmap.buffer), width);
ctx.putImageData(imageData, 0, 0);
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