Comment trouver l'intersection de deux lignes dans un espace 3D en utilisant jmonkeyengine3 (ou éventuellement une autre bibliothèque)?

Question

Au début, j'essayé quelque chose comme ceci:

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); 

Mais qui jette un UnsupportedCollisionException, il est donc pas quelque chose qui peut être calculé à l'aide de deux Ray objets.

Pour être honnête, je ne sais pas à quoi je m'attendais quand j'ai essayé ça. Il ne peut pas y avoir d'algorithme de collision de ligne sans tenir compte d'une delta/marge d'erreur quelconque ou d'un type de résultat différent, par exemple en retournant le vecteur le plus court entre les deux lignes. Ou au moins un tel algorithme n'aurait pas beaucoup de sens pour moi!

Dans tous les cas j'ai également regardé dans les classes Line et LineSegment mais ils n'implémentent pas l'interface Collidable. Ensuite, j'ai cherché un candidat qui met en œuvre Collidable et ressemble à une ligne, mais je ne vois pas de candidat clair.

Je préfère le faire en utilisant jme3 ou les bibliothèques JDK si possible, mais je suis ouvert à lire d'autres suggestions.

Comme mentionné précédemment, je devrais prendre en compte la précision en quelque sorte. Par exemple, il y aurait une intersection si la distance entre les lignes est en dessous d'un «delta» que je passe en paramètre et ensuite elle renvoie le point sur l'une des lignes si la distance la plus courte entre les lignes est inférieure à ce delta.

Answer 1

Un moyen sûr est de calculer la distance la plus courte entre les deux lignes. Cela se fait facilement en prenant le produit croisé des vecteurs de direction des deux lignes, ce qui donne la direction de la perpendiculaire commune, en la normalisant puis en calculant le produit scalaire de ce vecteur avec tout vecteur à partir d'un point de la première ligne à un point de la seconde.

Laissez les équations vectorielles être

A1 + t1 D1 
A2 + t2 D2 

Puis la distance:

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

Si les lignes sont données par des points PQ et RS,

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

Answer 2

Je pense que cela pourrait être utile à quelqu'un d'autre si j'ai posté ici mon implémentation Java, qui n'est rien de plus que la traduction de this c implementation comme suggéré dans les commentaires ci-dessus et quelques tests unitaires. Je crois aussi que le résultat est plus lisible que l'original, il jette des exceptions quand les arguments sont invalides au lieu de retourner un type de résultat nul et la portée des variables est réduite.

quelques observations concernant le code:

1. Je compris les EPS epsilon dans la version originale de la distance minimale entre les coordonnées de deux points afin de définir une ligne. J'utilise déjà une telle constante avec le nom long et explicite NUMBERS_SHOULD_BE_DIFFERENT_DELTA qui est la distance minimale nécessaire entre deux points de sorte que la perte de précision dans les calculs n'a pas d'effet négatif sur le résultat. Je crois en général qu'un autre delta de ce type est nécessaire dans les applications avec des calculs de géométrie lorsqu'on compare si les points sont presque égaux. D'où le nom long pour les différencier.

2. LineSegment3D classe, non inclus ici, est juste une enveloppe mince pour en cas de jme3 LineSegment vous vous demandez pourquoi j'utilise jme3 et non jme3 de LineSegment.

Ne concerne pas la question, mais la raison est que je préfère faire la distinction entre la sémantique des vecteurs et des points (jme3 utilise uniquement des vecteurs partout).

import static com.google.common.base.Preconditions.checkNotNull; 
import static com.google.common.base.Preconditions.checkArgument; 
import static java.lang.Math.abs; 
import javax.vecmath.Point3d; 

//... 

    /** 
    * Calculate the line segment that is the shortest route between the two lines 
    * determined by the segments. 
    * 
    * Even though we are passing segments as arguments the result is the intersection of the lines in which 
    * the segments are contained, not the intersection of the segments themselves. 
    * 
    */ 
    public static LineSegment3D lineToLineIntersection(LineSegment3D segmentA, LineSegment3D segmentB) { 
     checkNotNull(segmentA, "Segment cannot be null."); 
     checkNotNull(segmentB, "Segment cannot be null."); 

     Point3d p1 = segmentA.getPoints().getValue0(); 
     Point3d p2 = segmentA.getPoints().getValue1(); 
     Point3d p3 = segmentB.getPoints().getValue0(); 
     Point3d p4 = segmentB.getPoints().getValue1(); 

     Point3d p43 = new Point3d(p4.x - p3.x, p4.y - p3.y, p4.z - p3.z);  
     checkArgument(!(abs(p43.x) < NUMBERS_SHOULD_BE_DIFFERENT_DELTA && 
         abs(p43.y) < NUMBERS_SHOULD_BE_DIFFERENT_DELTA && 
         abs(p43.z) < NUMBERS_SHOULD_BE_DIFFERENT_DELTA), MSG_INVALID_POINTS_FOR_INTERSECTION_CALCULATION); 
     Point3d p21 = new Point3d(p2.x - p1.x, p2.y - p1.y, p2.z - p1.z); 
     checkArgument(!(abs(p21.x) < NUMBERS_SHOULD_BE_DIFFERENT_DELTA && 
         abs(p21.y) < NUMBERS_SHOULD_BE_DIFFERENT_DELTA && 
         abs(p21.z) < NUMBERS_SHOULD_BE_DIFFERENT_DELTA), MSG_INVALID_POINTS_FOR_INTERSECTION_CALCULATION); 
     Point3d p13 = new Point3d(p1.x - p3.x, p1.y - p3.y, p1.z - p3.z); 
     double d1343 = p13.x * p43.x + p13.y * p43.y + p13.z * p43.z; 
     double d4321 = p43.x * p21.x + p43.y * p21.y + p43.z * p21.z; 
     double d4343 = p43.x * p43.x + p43.y * p43.y + p43.z * p43.z; 
     double d2121 = p21.x * p21.x + p21.y * p21.y + p21.z * p21.z; 
     double denom = d2121 * d4343 - d4321 * d4321; 
     checkArgument(abs(denom) >= NUMBERS_SHOULD_BE_DIFFERENT_DELTA, MSG_INVALID_POINTS_FOR_INTERSECTION_CALCULATION); 
     double d1321 = p13.x * p21.x + p13.y * p21.y + p13.z * p21.z; 
     double numer = d1343 * d4321 - d1321 * d4343; 

     double mua = numer/denom; 
     double mub = (d1343 + d4321 * mua)/d4343; 

     return new LineSegment3D(
      new Point3d(p1.x+mua*p21.x, p1.y+mua*p21.y, p1.z+mua*p21.z), 
      new Point3d(p3.x+mub*p43.x, p3.y+mub*p43.y, p3.z+mub*p43.z)); 
    } 

Un couple de cas de test JUnit 4.Notez que j'utilise aussi une méthode personnalisée pour tester si deux points sont suffisamment similaires pour être considéré comme le même:

@Test 
    public void testLineToLineIntersection_LineAlongZAxis_LineAlongXAxis() { 
     LineSegment3D segmentA = new LineSegment3D(new Point3d(1, 0, 0), new Point3d(3, 0, 0)); 
     LineSegment3D segmentB = new LineSegment3D(new Point3d(0, 0, -1), new Point3d(0, 0, 5)); 
     LineSegment3D segment = GeometryUtil.lineToLineIntersection(segmentA, segmentB); 

     Point3d expected = new Point3d(0, 0, 0); 
     Pair<Point3d, Point3d> segmentPoints = segment.getPoints(); 

     Assert.assertTrue(GeometryUtil.almostEqual(segmentPoints.getValue0(), expected)); 
     Assert.assertTrue(GeometryUtil.almostEqual(segmentPoints.getValue1(), expected)); 
    } 

    @Test 
    public void testLineToLineIntersection_LineAlongZAxis_LineParallelXAxis_DoNotCross() { 
     LineSegment3D segmentA = new LineSegment3D(new Point3d(1, 0, 0), new Point3d(3, 0, 0)); 
     LineSegment3D segmentB = new LineSegment3D(new Point3d(0, 1, -1), new Point3d(0, 1, 5)); 
     LineSegment3D segment = GeometryUtil.lineToLineIntersection(segmentA, segmentB); 

     Pair<Point3d, Point3d> segmentPoints = segment.getPoints(); 

     Point3d expectedFrom = new Point3d(0, 0, 0); 
     Point3d expectedTo = new Point3d(0, 1, 0); 

     Assert.assertTrue(GeometryUtil.almostEqual(segmentPoints.getValue0(), expectedFrom)); 
     Assert.assertTrue(GeometryUtil.almostEqual(segmentPoints.getValue1(), expectedTo)); 
    } 

    //I created this test by using 
    //https://technology.cpm.org/general/3dgraph/ 
    //it's pretty easy to create four points and play around until one can ensure that the lines approximately intersect 
    //The calculations for creating intersecting examples are quite easy too, this just saved a little more time and it's good enough for me 
    @Test 
    public void testLineToLineIntersection_RandomLinesAlmostIntersect() { 
     LineSegment3D segmentA = new LineSegment3D(new Point3d(-3, -2, 4), new Point3d(1, 3, 2)); 
     LineSegment3D segmentB = new LineSegment3D(new Point3d(-1, -2, 1), new Point3d(-1, 4, 6)); 
     LineSegment3D segment = GeometryUtil.lineToLineIntersection(segmentA, segmentB); 

     Pair<Point3d, Point3d> segmentPoints = segment.getPoints(); 

     double distance = segmentPoints.getValue0().distance(segmentPoints.getValue1()); 

     Assert.assertTrue(distance < 0.1); 
    }