Ray Tracing
by Ethan Alexander Shulman (June 23, 2023)

Ray tracing/casting is common across many areas of programming including game development, physics simulations and graphics rendering. But how does it really work? In this post I'm going to walk through different ray tracing methods, with interactive examples using common Javascript that anyone can run in their browser. While everything below is in 2D, you can extend most of these methods to 3D easily by repeating what was done for XY with Z.

"Lonely Tree" by Pablo Roman Andrioli (Kali), a fractal rendered in real-time using ray tracing.

Ray?
The core part of ray tracing is the ray, a line starting at a origin point and extending infinitely in a direction. Since we're working in 2D our ray will have 4 variables: rayOriginX, rayOriginY, rayDirectionX and rayDirectionY. Below is an interactive example of a ray, you can change the 4 variables to see how it changes the line.

Tracing?
Tracing is the procedure of taking a ray and finding if it intersects other geometry along the way. Imagine drawing a straight line on a piece of paper and stopping the line once it hits something. The way we define our tracing in programming is with different tracing functions, for example one function might check if a ray intersects a box and another function might check if a ray intersects a circle. Generally the function also returns data such as where the ray hit the object or the surface normal where the ray hit.

We're going to start with the most very basic ray tracing function, an axis aligned plane. In the example below you can see an X axis aligned plane at -2 on the Y axis and extending infinitely in both directions on the X axis. With the mouse you can aim a ray at the plane and see where it hits.

Our tracing function needs to check if a ray intersects the geometry as well as output where the intersection was. We also want the distance from the ray origin to the surface while travelling along the ray direction, you can see this distance visualized above as 'Ray Hit Distance'. What makes the axis aligned plane so easy is it's confined all to 1 axis, we only need to work with the Y component of our positions and directions. First we can calculate the distance from the origin to plane by subtracting one from the other planeY-rayOriginY, next we divide it by rayDirectionY which scales it based on the direction the ray is travelling. If this value is greater or equal to 0 there is a hit, finally if rayDirectionY is 0 we return no hit to prevent division by zero. Below you can see our first ray tracing function.
//Returns distance to hit. Distance >= 0 if hit found, or < 0 if no hit function TraceXAxisAlignedPlane(rayOriginY,rayDirectionY, planeY) { if (rayDirectionY === 0) return -1; return (planeY-rayOriginY)/rayDirectionY; }

Now we can extend this to any direction by using both axes and taking plane direction into account. First we get the distance to the plane using dot(planeOrigin-rayOrigin, planeDirection), then the direction scalar is dot(rayDirection,planeDirection), which gives us our ray trace plane function below.
//Returns distance to hit. Distance >= 0 if hit found, or < 0 if no hit function TracePlane(rayOriginX,rayOriginY,rayDirectionX,rayDirectionY, planeX,planeY,planeDirectionX,planeDirectionY) { var dx = planeX-rayOriginX, dy = planeY-rayOriginY, dstDot = dx*planeDirectionX+dy*planeDirectionY,//dot(planeOrigin-rayOrigin, planeDirection) dirDot = rayDirectionX*planeDirectionX+rayDirectionY*planeDirectionY;//dot(rayDirection,planeDirection) if (dirDot === 0) return -1; return dstDot/dirDot; }

Doing some of the math above by hand can help you understand why our axis aligned function works the way it does. When planeDirectionX = 0 the X axis can be completely removed from the equation because it will just be multiplied to 0 during the dot products.

Shapes
In 2D we can create all the shapes we could ever need using lines and we can make a ray trace line function using our trace plane function. By stepping the ray forward using the distance from TracePlane we can then check if the point on the plane lies on our line, if it does we have a hit. Another thing we must do is convert our line points to the plane direction which is perpendicular to the line direction. See the ray trace line function below.
//Returns distance to hit. Distance >= 0 if hit found, or < 0 if no hit function TraceLine(rayOriginX,rayOriginY,rayDirectionX,rayDirectionY, lineAX,lineAY,lineBX,lineBY) { var lineDirX = lineBX-lineAX, lineDirY = lineBY-lineAY, lineLen = lineDirX*lineDirX+lineDirY*lineDirY; if (lineLen !== 0) { lineLen = Math.sqrt(lineLen); lineDirX /= lineLen;//get line direction by normalizing difference between line points lineDirY /= lineLen; } var planeDirX = -lineDirY, planeDirY = lineDirX;//plane direction is tangent of line of direction //trace plane var dst = TracePlane(rayOriginX,rayOriginY,rayDirectionX,rayDirectionY, lineAX,lineAY,planeDirX,planeDirY); if (dst < 0) return -1; //check if hit lies on line var hitX = rayOriginX+rayDirectionX*dst-lineAX, hitY = rayOriginY+rayDirectionY*dst-lineAY, linePt = hitX*lineDirX+hitY*lineDirY;//0 = pointA, lineLen = pointB if (linePt < 0 || linePt > lineLen) {//check if point lies on line return -1; } return dst; }

Finally we can use our trace line function to trace polygons, we can form regular polygons(triangle, square, pentagon, etc) by stepping through angles from 0 to PI*2 and getting our line points from cos/sin of the angles. Tracing each of those individual lines and finding the closest(minimum) hit distance.
//Returns distance to hit. Distance >= 0 if hit found, or < 0 if no hit function TracePolygon(rayOriginX,rayOriginY,rayDirectionX,rayDirectionY, polygonX,polygonY,polygonSides,polygonRadius) { //loop through sides of polygon var closestHit = Number.MAX_VALUE, lastX = polygonX+Math.cos(0)*polygonRadius, lastY = polygonY+Math.sin(0)*polygonRadius, iToAngle = Math.PI*2/polygonSides; for (var i = 0; i < polygonSides; i++) { var angle = (i+1)*iToAngle, x = polygonX+Math.cos(angle)*polygonRadius,//calculate line points of polygon using points on a circle from cos/sin y = polygonY+Math.sin(angle)*polygonRadius, traceDst = TraceLine(rayOriginX,rayOriginY,rayDirectionX,rayDirectionY, lastX,lastY,x,y); if (traceDst >= 0 && traceDst < closestHit) { closestHit = traceDst;//find closest line hit } lastX = x; lastY = y; } if (closestHit === Number.MAX_VALUE) { return -1;//no hit found } return closestHit; }

Path Tracing
Now what are we going to do with our ray tracing functions? Let's do something unique that ray tracing allows us to do, path tracing. We will simulate light rays bouncing around a scene of 2D polygons, but let's begin by making a scene.

Our scene is going to be made up of polygons using the TracePolygon function and we want them to be colored and possibly emit light. We will create a Polygon class to hold these variables and use it to render our scene by looping through them all and finding the closest hit.
//Regular polygon class used to describe scene function Polygon(x,y,sides,size, r,g,b, light) { this.x = x; this.y = y; this.sides = sides; this.radius = size*0.5; this.r = r;//color this.g = g; this.b = b; this.light = light;//amount of light emitted this.distance = 0;//used as buffer to store ray hit distance } //Returns Polygon if hit, or null if no hit function TraceScene(rayOriginX,rayOriginY,rayDirectionX,rayDirectionY) { var closestHit = Number.MAX_VALUE, closestPolygon = null; //trace polygons in scene for (var i = 0; i < polygons.length; i++) { var pgon = polygons[i], pdst = TracePolygon(rayOriginX,rayOriginY,rayDirectionX,rayDirectionY, pgon.x,pgon.y,pgon.sides,pgon.radius); if (pdst >= 0 && pdst < closestHit) { closestHit = pdst; closestPolygon = pgon; } } if (closestPolygon) closestPolygon.distance = closestHit; return closestPolygon; }

And we create our scene by defining polygons.
//polygons making up scene var polygons = [ new Polygon(0.5,//x 0.5,//y 3,//number of polygon sides, LIGHT_SIZE,//polygon size, 1,1,1,//polygon r,g,b color 1//light emission amount ),//white triangle light in center new Polygon(0.3,0.4, 4,0.3, 0.95,0.05,0.05,0),//red square top left new Polygon(0.39,0.65, 3,0.2, 0.05,0.05,0.95,0),//blue triangle bottom left new Polygon(0.75,0.5, 5,0.3, 0.05,0.95,0.05,0)//green pentagon right ];

We're going to use a simple form of path tracing called montecarlo path tracing and keep it basic by bouncing rays uniformly in all directions. I'll describe the algorithm, the path has your usual ray variables position, direction but also has a color tinted by objects it bounces off and a light sum of all the color absorbed.
-We initialize our color to 1,1,1(r,g,b), light sum to 0 and ray direction to a random direction.
-Trace the ray, if no hit is found jump to last statement.
-If a hit is found multiply the color by the polygon color and add the color multiplied by polygon light emission to the light sum.
-Step the ray forward to the hit point using the hit distance, generate a new random ray direction to bounce the ray.
-Repeat from TraceRay above until maximum path bounces has been met.
-Repeat for each pixel, adding up and averaging the light samples.

Let's initialize the variables we need, config defining resolution, max bounces, etc, a Float32Array to store our light sum samples, the current path pixel, pixel index, a canvas element and 2D context.
//constants for configuration var LIGHT_RESOLUTION = 128,//resolution of path tracing PATHS_PER_FRAME = 2000,//pixel paths computed each animation frame LIGHT_STRENGTH = 1,//strength of light LIGHT_SIZE = 0.2,//size of light BOUNCES = 4,//max light path bounces DITHER = 0.00001,//amount that light ray can step into objects //path tracer canvas and lighting buffer lightCanvas, lightC2d, lightPx, light = new Float32Array(LIGHT_RESOLUTION*LIGHT_RESOLUTION*3), lightSamples = 1, pathX = 0, pathY = 0, pathIndex = 0, pxIndex = 0; //Page loaded event callback document.addEventListener("DOMContentLoaded",function() { //create light path tracing canvas lightCanvas = document.createElement("canvas"); lightCanvas.width = lightCanvas.height = LIGHT_RESOLUTION; lightC2d = lightCanvas.getContext("2d"); lightPx = lightC2d.getImageData(0,0,LIGHT_RESOLUTION,LIGHT_RESOLUTION); //show path tracing result on html page document.body.appendChild(lightCanvas); //start our path tracer Render(); });

Now to implement the path tracing process. We will loop through PATHS_PER_FRAME and for each iteration tracing a path, adding a light sample for each pixel, incrementing pathX/pathY/pathIndex/pxIndex along the image until we cover the image. At that point we write the averaged light samples to the canvas using putImageData and start over resetting pathY/pathIndex/pxIndex to 0. Limiting paths traced per frame to 2000 with PATHS_PER_FRAME will ensure we don't lag the browser as this is running on a single thread in Javascript. Below you can find our finished path tracer rendering loop.
//Render loop. function Render() { var pxData = lightPx.data; for (var p = 0; p < PATHS_PER_FRAME; p++) { var rand = Math.random()*Math.PI*2,//generate random ray direction by feeding random angle into cos sin dirX = Math.cos(rand), dirY = Math.sin(rand), rayX = pathX/LIGHT_RESOLUTION+dirX*DITHER, rayY = pathY/LIGHT_RESOLUTION+dirY*DITHER;//ray position //path trace var rayR = 1, rayG = 1, rayB = 1,//ray color tint lightR = 0, lightG = 0, lightB = 0;//ray light sum for (var b = 0; b < BOUNCES; b++) { var rayHit = TraceScene(rayX,rayY,dirX,dirY); if (rayHit) { //hit rayR *= rayHit.r;//apply polygon color tint to ray rayG *= rayHit.g; rayB *= rayHit.b; lightR += rayR*rayHit.light;//add polygon light emission to light sum lightG += rayG*rayHit.light; lightB += rayB*rayHit.light; //step ray forward to hit var hdst = rayHit.distance-1e-5; rayX += dirX*hdst; rayY += dirY*hdst; //bounce ray in random direction rand = Math.random()*Math.PI*2; dirX = Math.cos(rand); dirY = Math.sin(rand); //step ray forward a tiny bit allowing light to blend into geometry rayX += dirX*DITHER; rayY += dirY*DITHER; } else { //no hit break; } } //add light accumulation to light samples lightR += light[pathIndex]; lightG += light[pathIndex+1]; lightB += light[pathIndex+2]; light[pathIndex++] = lightR; light[pathIndex++] = lightG; light[pathIndex++] = lightB; var pxR = Math.min(255,Math.floor(lightR*255.999/lightSamples)),//average light sum and convert to ubyte pixel format pxG = Math.min(255,Math.floor(lightG*255.999/lightSamples)), pxB = Math.min(255,Math.floor(lightB*255.999/lightSamples)); pxData[pxIndex++] = pxR;//copy ubyte light values into light pixel data pxData[pxIndex++] = pxG; pxData[pxIndex++] = pxB; pxData[pxIndex++] = 255; pathX++;//next pixel path if (pathX >= LIGHT_RESOLUTION) { pathX = 0; pathY++; if (pathY >= LIGHT_RESOLUTION) { pathY = 0;//done whole frame pathIndex = 0; pxIndex = 0; lightSamples++; //copy pixel data into light canvas lightC2d.putImageData(lightPx,0,0); } } } requestAnimationFrame(Render); }

And we have ourselves a 2 dimensional path tracer, you can see global illumination where the light is tinted from bouncing off the shapes. The catch with montecarlo path tracing is the noise, as you increase the number of light samples the average converges and your image gets clearer. Ray tracing has a huge number of uses beyond path tracing, I hope you found this write up useful!