Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Companion Code for the Article on Ray Triangle Intersection
//@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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.