Segment-Segment Distance in 3D

One of my favorite functions projects points onto line segments.

function constrainToSegment(position, a, b) {
    ba = b - a; t = Dot(position - a, ba) / Dot(ba, ba);
    return Lerp(a, b, Clamp01(t));
}

It’s just so simple, fast, and useful! It works using the dot product to do vector projection.

But did you know that you can extend this trick to find the closest point between two line segments?

Line Segments

The key is to recognize that you can turn the pair of line segments INTO a point and a line segment by squishing all four points onto the plane defined by the first line segment!

inPlaneA = segA.projectToPlane(segC, segD-segC);
inPlaneB = segB.projectToPlane(segC, segD-segC);
inPlaneBA = inPlaneB-inPlaneA;
t = Dot(segC-inPlaneA, inPlaneBA)/Dot(inPlaneBA, inPlaneBA);
t = (inPlaneA != inPlaneB) ? t : 0f; // Zero's t if parallel
segABtoLineCD = Lerp(segA, segB, Clamp01(t));

segCDtoSegAB = constrainToSegment(segABtoLineCD, segC, segD);
segABtoSegCD = constrainToSegment(segCDtoSegAB, segA, segB);

Solving for the closest point in this reduced sub space gives you an answer that is valid in the full space!

Optimization

You can also do this function entirely without square roots in its slightly more optimized form:

segDC = segD-segC; float lineDirSqrMag = Dot(segDC, segDC);
inPlaneA = segA-((Dot(segA-segC, segDC)/lineDirSqrMag)*segDC);
inPlaneB = segB-((Dot(segB-segC, segDC)/lineDirSqrMag)*segDC);
inPlaneBA = inPlaneB-inPlaneA;
t = Dot(segC-inPlaneA, inPlaneBA)/Dot(inPlaneBA, inPlaneBA);
t = (inPlaneA != inPlaneB) ? t : 0f; // Zero's t if parallel
segABtoLineCD = Lerp(segA, segB, Clamp01(t));

segCDtoSegAB = constrainToSegment(segABtoLineCD, segC, segD);
segABtoSegCD = constrainToSegment(segCDtoSegAB, segA, segB);

(The only branch checks if the lines are completely parallel (which is unlikely in real-world data)).

Comments

The wonderful thing about vector math is that it (should) work in any number of dimensions!

Word Vector Geometry, anyone?

Leave a Comment

Loading...