Companion Code for the Article on Ray Triangle Intersection

TriangleLineIntersection.js

//@author Joseph Catrambone
// See https://www.josephcatrambone.com/?p=967 for the original blog post and the derivation of all formulas.

class Point {
	constructor(x, y, z) {
		this.x = x;
		this.y = y;
		this.z = z;
	}
	dot(other) {
		return this.x*other.x + this.y*other.y + this.z*other.z;
	}
	cross(other) {
		return new Point(
			this.y*other.z - this.z*other.y,
			this.x*other.z - this.z*other.x,
			this.x*other.y - this.y*other.x
		);
	}
	add(v) {
		if(v instanceof Point) {
			return new Point(this.x+v.x, this.y+v.y, this.z+v.z);
		} else {
			return new Point(this.x+v, this.y+v, this.z+v);
		}
	}
	subtract(v) {
		if(v instanceof Point) {
			return new Point(this.x-v.x, this.y-v.y, this.z-v.z);
		} else {
			return new Point(this.x-v, this.y-v, this.z-v);
		}
	}
	multiply(v) {
		if(v instanceof Point) {
			return new Point(this.x*other.x, this.y*other.y, this.z*other.z);
		} else {
			return new Point(this.x*v, this.y*v, this.z*v);
		}
	}
}

class Triangle {
	constructor(a, b, c) {
		this.a = a;
		this.b = b;
		this.c = c;
	}
	getIntersection(p0, p1) {
		var r = this.b.subtract(this.a);
		var s = this.c.subtract(this.a);
		var normal = r.cross(s);
		var numerator = normal.dot(this.a.subtract(p0));
		var denominator = normal.dot(p1.subtract(p0));
		
		if(Math.abs(denominator) < 1e-6) {
			return null;
		}
		
		var t = numerator / denominator;
		if(t < 0.0 || t > 1.0) { // Outside of the line segment.
			return null;
		}
		
		// If the line segment hits the plane, it hits here.
		var p = p0.add((p1.subtract(p0)).multiply(t)); // p0 + (p1-p0)*t
		
		// Is the point P inside the triangle, though?
		var alpha = r.dot(r);
		var beta = r.dot(s);
		var gamma = r.dot(s);
		var delta = s.dot(s);
		
		var invDeterminant = (alpha*delta) - (gamma*beta);
		if(Math.abs(invDeterminant) < 1e-6) { // Can't invert the matrix.
			return null;
		}
		
		// Rescale alpha, beta, and gamma by the denominator.
		alpha /= invDeterminant;
		beta /= invDeterminant;
		gamma /= invDeterminant;
		delta /= invDeterminant;
		
		// We have that handy multiply operator, so we can compute the rows in one swoop.
		var mRow0 = r.multiply(delta).add(s.multiply(-beta)); // r*beta + s*-beta // Row 0 of matrix.
		var mRow1 = r.multiply(-gamma).add(s.multiply(alpha));
		
		var u = mRow0.dot(p.subtract(this.a));
		var v = mRow1.dot(p.subtract(this.a));
		
		if(u+v >= 0 && u >= 0 && u <= 1 && v >= 0 && v <= 1 && u+v <= 1) {
			return p;
		} else {
			return null;
		}
	}
}

// Everything below this is just demo code for rendering to a canvas.

// If you want to see the rendering from different angles, try uncommenting the different return statements.
function screenProject(pt) {
	return [pt.x, pt.y]; // Viewed from Z, we see X and Y.
	//return [pt.y, pt.z]; // Viewed from X, we see Y and Z.
	//return [pt.x, pt.z]; // Viewed from Z, we see X and Y.
}

function drawTriangle(ctx, tri) {
	ctx.beginPath();
	ctx.moveTo(...screenProject(tri.a)); // looking down on Z.
	ctx.lineTo(...screenProject(tri.b));
	ctx.lineTo(...screenProject(tri.c));
	ctx.lineTo(...screenProject(tri.a));
	ctx.stroke();
}

function drawRay(ctx, start, end) {
	ctx.beginPath();
	ctx.moveTo(...screenProject(start));
	ctx.lineTo(...screenProject(end));
	ctx.stroke();
}

function drawPoint(ctx, pt) {
	var [screenPtX, screenPtY] = screenProject(pt);
	ctx.fillRect(screenPtX-1, screenPtY-1, 3, 3);
}

var timeAccumulator = 0;
var previousTime = 0;

function draw() {
	var time = new Date();
	var ms = time.getMilliseconds();
	var dt = ms - previousTime;
	timeAccumulator += Math.max(0, dt);
	previousTime = ms;
	
	var rayStart = new Point(50, 50, 0);
	var rayEnd = new Point(50 + 50*Math.cos(timeAccumulator/1000), 50 + 50*Math.sin(timeAccumulator/1000), 100);
	
	var tri = new Triangle(
		new Point(1, 1, 44),
		new Point(100, -1, 53),
		new Point(50, 100, 50)
	);
	

	var canvas = document.getElementById("canvas");
	if(canvas == null) {
		console.log("Failed to acquire canvas.");
		return;
	}
	var ctx = canvas.getContext('2d');
	ctx.globalCompositeOperation = 'destination-over';
	ctx.clearRect(0, 0, 300, 300);
	
	ctx.save();
	ctx.restore();
	var intersection = tri.getIntersection(rayStart, rayEnd);
	if(intersection) {
		ctx.fillStyle = 'red';
		drawPoint(ctx, intersection);
	}
	drawTriangle(ctx, tri);
	drawRay(ctx, rayStart, rayEnd);
		
	window.requestAnimationFrame(draw);
}

window.requestAnimationFrame(draw);