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