I have had no luck finding ready-to-use code, or converting other people's code, or even understanding the problem.
I've got so far as trying to make it on first principles. Here's what I've got:
function triangle_sphere_sweep(a,b,c,start,stop,radius,twoSided) { //clockwise winding, I think
/* RETURNS a tuple of the fraction of the line (start->stop) that the the
sphere moves, and the normal to point of impact with the triangle,
or null if no hit
*/
// get the normal of the triangle
var u = vec3_sub(b,a),
v = vec3_sub(c,a),
n = vec3_cross(u,v);
if(n[0]==0 && n[1]==0 && n[2]==0) // triangle is degenerate
return null;
var dir = vec3_sub(stop,start),
j = vec3_dot(n,dir);
var colinear = float_zero(j); // parallel, disjoint or on plane
// which side of triangle is line?
var start_height = vec3_dot(n,vec3_sub(start,a));
if(start_height < 0) // line is beneath triangle
return null;
var stop_height = vec3_dot(n,vec3_sub(stop,a));
if(stop_height > start_height) // going away from triangle
return null;
// is parallel?
colinear = colinear || (float_equ(start_height,stop_height) && float_equ(start_height,radius));
if(!colinear && (start_height > radius)) { // far enough above to hit the triangle itself?
// get intersect point of ray with triangle plane that is radius above it
var normal = vec3_normalise(n),
start_plane = vec3_add(a,vec3_scale(normal,radius)),
i = -vec3_dot(n,vec3_sub(start,start_plane)),
k = i / j;
if(k < 0) // line goes away from triangle
return null;
if(k > 1) // to far on line
return null;
// do we hit the triangle radius above?
var hit = vec3_add(start,vec3_scale(dir,k)), // intersect point of ray and plane at radius above it
uu = vec3_dot(u,u),
uv = vec3_dot(u,v),
vv = vec3_dot(v,v),
w = vec3_sub(hit,start_plane),
wu = vec3_dot(w,u),
wv = vec3_dot(w,v),
D = uv * uv - uu * vv,
s = (uv * wv - vv * wu) / D;
if(s>=0 && s<=1) {
var t = (uv * wu - uu * wv) / D;
if(t>=0 && (s+t)<=1) // hit in triangle
return [k,normal];
}
}
// we are on right side of the triangle, but we're not hitting exactly; maybe we hit an edge then?
var best_pt = null, best_ofs,
line = [start,stop],
line_scale,
radius2 = radius*radius,
sides = [[a,b],[b,c],[c,a]];
for(var side in sides) {
side = sides[side];
var nearest_ofs = line_line_closest_point_ofs(line,side), //[ofs_on_line,ofs_on_side]
nearest_pt = [vec3_lerp(start,stop,nearest_ofs[0]),
vec3_lerp(side[0],side[1],nearest_ofs[1])],
nearest_dist2 = vec3_distance_sqrd(nearest_pt[0],nearest_pt[1]);
if(nearest_dist2 <= radius2) {
// we want to move our hit centre-point so its radius distance from the intersection point on triangle edge
line_scale = line_scale || 1/vec3_length(vec3_sub(stop,start)); // lazy compute
var ofs = nearest_ofs[0] - (Math.sqrt(radius2-nearest_dist2) * line_scale);
// is the first, or the best, hit?
if((ofs > 0) && (best_pt == null || ofs < best_ofs)) {
best_pt = nearest_pt[1]; // just keeping this for test
best_ofs = ofs;
}
}
}
if(best_pt != null) { // hit edge
// lets do a little test; this is often FAILING
var hit = vec3_lerp(start,stop,best_ofs),
hit_dist2 = vec3_distance_sqrd(hit,best_pt);
assert(float_equ(hit_dist2,radius2),"wrong distance! "+hit_dist2+" != "+radius2+" ("+(hit_dist2-radius2)+")");
return [best_ofs,vec3_normalise(vec3_sub(hit,best_pt))];
}
// no hit
return null;
}
function line_line_closest_point_ofs(line1,line2) {
var v1 = vec3_sub(line1[1],line1[0]), // should be normalised?
v2 = vec3_sub(line2[1],line2[0]), // should be normalised?
v1dotv2 = vec3_dot(v1,v2),
denom = v1dotv2 * v1dotv2 - 1;
if(float_zero(denom)) {
assert(false,"lines are parallel");
// todo: how far
} else {
var c = 1/denom,
dot1 = vec3_dot(vec3_sub(line2[0],line1[0]),v1),
dot2 = vec3_dot(vec3_sub(line2[0],line1[0]),v2),
t1 = c * (-1 * dot1 + v1dotv2 * dot2),
t2 = c * (-v1dotv2 * dot1 + 1 * dot2);
t1 = Math.min(Math.max(0,t1),1); // if v1 is normalised, what
// would I do to map it to the real magnitude of line1?
t2 = Math.min(Math.max(0,t2),1);
}
return [t1,t2];
}
Now when intersecting with the edge of a triangle, it often puts the sphere centre too close or too far from the edge
Here's a screenie:
The blue sphere is the start of the sphere's path (the green line segment). The green sphere (drawn inverted so you can see in the middle) is where the intersection is computed; but its clearly too close to the triangle
The triangle has normals arrows drawn from each corner just so I know which side is up on it.
