java3dgeometryjmonkeyengine

How to find the intersection of two lines in a 3D space using jmonkeyengine3 (or possibly another library)?


At first I tried something like this:

  Ray ray1 = new Ray();
  Vector3f originRay1 = new Vector3f(0, 0, 1);
  ray1.setOrigin(originRay1);
  Vector3f directionRay1 = new Vector3f(0, 0, -1);
  ray1.setDirection(directionRay1 );

  Ray ray2 = new Ray();
  Vector3f originRay2 = new Vector3f(1, 0, 0);
  Vector3f directionRay2 = new Vector3f(-1, 0, 0);
  ray2.setDirection(directionRay2 );
  ray2.setOrigin(originRay2);

  CollisionResults results= new CollisionResults();
  int collide = ray1.collideWith(ray2, results);

But that throws an UnsupportedCollisionException, so it's not something that can be calculated using two Ray objects.

To be honest I don't know what I expected when I tried this. There can't be any line collision algorithm without taking into account a delta / margin of error of some sort or a different kind of result altogether by, for example, returning the shortest vector between the two lines. Or at least such an algorithm wouldn't make much sense to me!

In any case I also looked into classes Line and LineSegment but they don't implement the Collidable interface. Then I looked for some candidate that does implement Collidable and resembles a line, but I don't see a clear candidate.

I'd rather do it using jme3 or the JDK libraries if possible, but I'm open to read other suggestions.

As mentioned before I would have to take into account the precision somehow. For example, there would be an intersection if the distance between the lines is below a 'delta' that I pass as parameter and then it returns the point on one of the lines if the shortest distance between the lines is less than that delta.


Solution

  • A safe way is to compute the shortest distance between the two lines.

    This is easily done by taking the cross product of the direction vectors of the two lines, which gives the direction of the common perpendicular, normalizing it then computing the scalar product of this vector with any vector from a point of the first line to a point of the second.

    Let the vector equations be

    A1 + t1 D1
    A2 + t2 D2
    

    Then the distance:

    d12 = |(A2 - A1).(D1 x D2)| / |D1 x D2|
    

    If the lines are given by points PQ and RS,

    d = |(P - R).((Q - P) x (S - R))| / |(Q - P) x (S - R)|