THREE.Ray.prototype.closestPointToRay

gistfile1.txt

THREE.Ray.prototype.closestPointToRay = function (that, details) {
  // that: THREE.Ray() 
  // details: (optional) object
  // { pointOnThisRay: <THREE.Vector3>
  // , pointOnThatRay: <THREE.Vector3>
  // , midPoint: <THREE.Vector3>
  // , distanceBetweenClosestPoints: <float>
  // }
  // For an explanation of the vector mathematics, see: 
  // http://morroworks.com/Content/Docs/Rays%20closest%20point.pdf
  
  // @return undefined if rays are invalid or parallel
  //         or THREE.Vector3() point on this ray which is closest
  //         to that ray.
  
  if (!(that instanceof THREE.Ray)) {
    return
  }
  
  var thisDirection = this.direction
  var thatDirection = that.direction

  if (!thisDirection.clone().cross(thatDirection).length()) {
    // Rays are parallel
    return 
  }

  if ( !thisDirection.dot(thisDirection)
    || !thatDirection.dot(thatDirection)) {
    // At least one of the rays is just a point with no direction
    return
  }

  var closestPoint = new THREE.Vector3()
  var thisOrigin = this.origin
  var thatOrigin = that.origin
  var sameOrigin = thisOrigin.equals(thatOrigin)

  if (sameOrigin) {
    // Simple case
    closestPoint.copy(thisOrigin)
  } else {
    var a = thisDirection.clone().normalize()
    var b = thatDirection.clone().normalize()
    var c = thatOrigin.clone().sub(thisOrigin)

    var p = a.dot(b)
    var q = a.dot(c)
    var r = b.dot(c)
    var s = a.dot(a) // already known to be non-zero
    var t = b.dot(b) // already known to be non-zero

    var divisor = (s * t - p * p)

    if (!divisor) {
      // The two rays are colinear. They are "closest" at all points
      // This case should already have been excluded by the .cross()
      // check made at the start.
      return
    }

    var d = (q * t - p * r) / divisor
    closestPoint.copy(thisOrigin).add(a.multiplyScalar(d))
  }

  if ( typeof details === "object" ) {
    details.pointOnThisRay = closestPoint
    
    if (sameOrigin) {
      // Should all points be the same object or clones?
      details.pointOnThatRay = closestPoint
      details.midPoint = closestPoint
      details.distanceBetweenClosestPoints = 0
    } else {
      // TODO: Add other details
      d = (p * q - r * s) / divisor
      var thatPoint = new THREE.Vector3().copy(thatOrigin).add(b.multiplyScalar(d))
      details.pointOnThatRay = thatPoint
      details.midPoint = closestPoint.clone()
                                     .add(thatPoint)
                                     .divideScalar(2)
      details.distanceBetweenClosestPoints = closestPoint.distanceTo(thatPoint)
    }
  }

  return closestPoint
}

I would not special case the sameOrigin, it is a very rare case and it should be handled by the general case code well. Not having it special case will speed up the majority cases.

You check for parallel rays twice, first here:

if (!thisDirection.clone().cross(thatDirection).length()) {
    // Rays are parallel
    return 
  }

then you check again here (collinear means parallel):

if (!divisor) {
      // The two rays are colinear. They are "closest" at all points
      // This case should already have been excluded by the .cross()
      // check made at the start.
      return
    }

I am not sure that a and b need to be normalized in the following code, the reason is because there is a.dot(a), and b.dot(b), which should be necessary if a and b where normalized:

    var a = thisDirection.clone().normalize()
    var b = thatDirection.clone().normalize()
    var c = thatOrigin.clone().sub(thisOrigin)

    var p = a.dot(b)
    var q = a.dot(c)
    var r = b.dot(c)
    var s = a.dot(a) // already known to be non-zero
    var t = b.dot(b) // already known to be non-zero

Not creating new a and b vectors would be very efficient because JavaScript memory allocations are costly.

If a and b are not normalized, it may be more efficient to replace this line of code:

closestPoint.copy(thisOrigin).add(a.multiplyScalar(d))

With something like this, because d would be in the parameter space of the current ray:

this.at( d, closestPoint );

This check is not needed:

if ( !thisDirection.dot(thisDirection)
    || !thatDirection.dot(thatDirection)) {
    // At least one of the rays is just a point with no direction
    return
  }

Because it is already covered by the check that divisor is 0 later on.

For speed purposes, it may just be easier to return the 'd' parameterization rather than computing all these derived values:

 if ( typeof details === "object" ) {
    details.pointOnThisRay = closestPoint

    if (sameOrigin) {
      // Should all points be the same object or clones?
      details.pointOnThatRay = closestPoint
      details.midPoint = closestPoint
      details.distanceBetweenClosestPoints = 0
    } else {
      // TODO: Add other details
      d = (p * q - r * s) / divisor
      var thatPoint = new THREE.Vector3().copy(thatOrigin).add(b.multiplyScalar(d))
      details.pointOnThatRay = thatPoint
      details.midPoint = closestPoint.clone()
                                     .add(thatPoint)
                                     .divideScalar(2)
      details.distanceBetweenClosestPoints = closestPoint.distanceTo(thatPoint)
    }
  }

The 'd' parameter can be used as I described above to get the point on the plane, thus it is a sufficient result --- although I am not sure how to represent the failure case in an efficient fashion -- I guess one could return null for the failure case (parallel lines) and a value number otherwise:

this.at( d, closestPoint );

I would write it something like this - I haven't checked this for simple mistakes, but it should be relatively close:

THREE.Ray.prototype.closestPointToRay = function ( that ) {

    var p = this.direction.dot(that.direction);
    var s = this.direction.lengthSq();
    var t = that.direction.lengthSq();

    var divisor = (s * t - p * p)

    if ( Math.abs( divisor ) < THREE.Epsilon ) {
      // The two rays are colinear. They are "closest" at all points
      // This case should already have been excluded by the .cross()
      // check made at the start.
      return null;
    }

    // only calculate these if we need to...
    var c = that.origin.clone().sub(this.origin);
    var q = this.direction.dot(c);
    var r = that.direction.dot(c);

    return (q * t - p * r) / divisor;
}