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.
"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.
Download Example Source Code
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.
Download Example Source Code
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.
//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!
Download Example Source Code
Thanks for Reading!
If you have any questions feel free to reach out to me at xaloezcontact@gmail.com.
-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.