Last active
November 23, 2017 20:37
-
-
Save JosephCatrambone/578c22f6e507dc52420752013a45b92b to your computer and use it in GitHub Desktop.
Companion Code for the Article on Ray Triangle Intersection
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//@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