JavaFX 8 3D Szenen Schnittpunkt

Question

Ist es möglich in einer JavaFX 8 3D Szene Punkte entlang eines Strahls (zB PickRay) zu finden, beginnend an einem beliebigen Punkt im 3D Raum mit einem 3D Richtungsvektor, wo der Strahl die Dreiecke schneidet ein Mesh (TriangleMesh in einem MeshView)?

Ich weiß, dass dies im Camera/MouseHandler zum Mauspicken gemacht wird, aber ich sehe keine Möglichkeit, dies für beliebige Strahlen zu tun.

Answer 1

Wie @ jdub1581 vermuten lässt, ist ein Strahl nur ein geometrischer Vektor. Um also eine Liste von Dreiecken zu finden, die von diesem Vektor geschnitten werden, müssen wir Probleme der Art "Schnittlinie" und "Schnittlinie" lösen Dreiecksgrenzen ".

Nehmen wir an, wir haben eine TriangleMesh, und wir haben eine Liste von Vertices und eine Liste von Gesichtern. Jeder Eckpunkt mit 3 Koordinaten, jede Fläche mit 3 Eckpunkten (ohne Berücksichtigung von Textur, Normalen, ...). Der Einfachheit halber verwenden wir zwei Listen von Point3D, um sie zu speichern.

In diesem link gibt es mehrere 3D-Formen bereit zu verwenden. Lassen Sie uns eine CuboidMesh greifen.

CuboidMesh cuboid = new CuboidMesh(10f,12f,4f,4); 

Dies wird uns diese 3D-Form:

Wenn wir nun einen Blick auf das Netz haben wir zwei Listen mit den Eckpunkten schaffen könnte und Gesichter:

List<Point3D> vertices=Arrays.asList(new Point3D(5.0, 6.0, 2.0), 
     new Point3D(5.0, 6.0, 2.0), new Point3D(5.0, -6.0, 2.0), ..., 
     new Point3D(-1.875, -2.25, -2.0), new Point3D(-1.875, -1.5, -2.0)); 

List<Point3D> faces=Arrays.asList(new Point3D(0, 386, 388), 
     new Point3D(98, 387, 386.0), new Point3D(100, 388, 387), ..., 
     new Point3D(383, 1535, 1537), new Point3D(1536, 1537, 1535)); 

Lassen Sie uns einige 3D-Punkte in unserer Szene, einen Ursprung und ein Ziel, beide in globalen Koordinaten, und definieren Sie die Richtung des Vektors, normalisiert:

wir werden eine visuelle Darstellung unserer ray haben

r(t) = (4,-7,-4)+t*(-0.154,0.771,0.617) 

Wenn wir einen schlanken Zylinder zwischen diesen zwei Punkten hinzufügen:

Point3D gloOrigin=new Point3D(4,-7,-4); 
Point3D gloTarget=new Point3D(2,3,2); 
Point3D direction=gloTarget.subtract(gloOrigin).normalize(); // -0.154,0.771,0.617 

Der Strahl Gleichung wird dann diese

Bounding Box Kreuzung

Im ersten Schritt wird geprüft, ob der Strahl die Begrenzungsbox unserer Form schneidet. In lokalen Koordinaten der Form haben wir 6 Gesichter durch ihre Normalen gegeben, mit ihren sechs Zentren:

Bounds locBounds = cuboid.getBoundsInLocal(); 
List<Point3D> normals=Arrays.asList(new Point3D(-1,0,0),new Point3D(1,0,0), 
    new Point3D(0,-1,0), new Point3D(0,1,0), new Point3D(0,0,-1), new Point3D(0,0,1)); 
List<Point3D> positions=Arrays.asList(new Point3D(locBounds.getMinX(),0,0), 
    new Point3D(locBounds.getMaxX(),0,0), new Point3D(0,locBounds.getMinY(),0), 
    new Point3D(0,locBounds.getMaxY(),0), new Point3D(0,0,locBounds.getMinZ()), 
    new Point3D(0,0,locBounds.getMaxZ())); 

Da wir auf dem lokalen System arbeiten werden, müssen wir unseren Ursprungspunkt in diesen Koordinaten:

Point3D gloOriginInLoc = cuboid.sceneToLocal(gloOrigin); // 4,-7,-4 since the box is centered in 0,0,0 

Nun erhalten wir für jede der sechs Flächen den Abstand t zu der Ebene, die dieser link folgt. Dann können wir prüfen, ob der Punkt zur Box gehört oder nicht.

AtomicInteger counter = new AtomicInteger(); 
IntStream.range(0, 6).forEach(i->{ 
    double d=-normals.get(i).dotProduct(positions.get(i)); 
    double t=-(gloOriginInLoc.dotProduct(normals.get(i))+d)/ 
       (gloDirection.dotProduct(normals.get(i))); 

    Point3D locInter=gloOriginInLoc.add(gloDirection.multiply(t)); 
    if(locBounds.contains(locInter)){ 
     counter.getAndIncrement(); 
    } 
}); 

Wenn counter.get()>0 dann haben wir einige Überschneidungen zwischen dem Strahl und der Form, und wir können mit den Dreiecken gehen. In diesem Beispiel sind dies die Schnittpunkte: (3,5, -4,5, -2) und (2,5,0,5,2).

Triangles Kreuzung

Es gibt mehrere Algorithmen für die Aufgabe des Findens, wenn der Strahl jedes Dreieck des Netzes schneidet, also müssen wir das Rad nicht neu zu erfinden.

Die, die ich verwendet habe, ist von Tomas Möller & Ben Trumbore. Es liefert den Abstand t vom Ursprung zum Flugzeug und die Koordinaten u,v innerhalb des Dreiecks für einen gegebenen Schnittpunkt.

Sobald wir den Ursprung der lokalen Koordinaten der Form haben, und wir kennen die Richtung des Strahls, die Umsetzung dieses Algorithmus ist dies:

private final float EPS = 0.000001f; 

public List<Point3D> getIntersections(Point3D origin, Point3D direction, 
             List<Point3D> points, List<Point3D> faces){ 

    return faces.parallelStream().filter(f->{ 
     // vertices indices 
     int p0=(int)f.getX(); 
     int p1=(int)f.getY(); 
     int p2=(int)f.getZ(); 

     // vertices 3D coordinates 
     Point3D a = points.get(p0); 
     Point3D b = points.get(p1); 
     Point3D c = points.get(p2); 

     Point3D edge1 = b.substract(a); 
     Point3D edge2 = c.substract(a); 
     Point3D pvec=direction.crossProduct(edge2); 
     float det=edge1.dotProduct(pvec); 

     if(det<=-EPS || det>=EPS){ 
      float inv_det=1f/det; 
      Point3D tvec=origin.substract(a); 
      float u = tvec.dotProduct(pvec)*inv_det; 
      if(u>=0f && u<=1f){ 
       Point3D qvec=tvec.crossProduct(edge1); 
       float v = direction.dotProduct(qvec)*inv_det; 
       if(v>=0 && u+v<=1f){ 
        float t = c.dotProduct(qvec)*inv_det; 
        System.out.println("t: "+t+", u: "+u+", v: "+v); 
        return true; 
       } 
      } 
     } 
     return false; 
    }).collect(Collectors.toList()); 
} 

In diesem Beispiel finden wir drei Gesichter, gegeben durch diese Eckpunkte: (85, 1245, 1274), (85, 1274, 1266) und (351, 1476, 1479).

Wenn wir diese Gesichter zeichnen die Kreuzung sehen:

Beachten Sie, dass durch alle Vorgänge in dem lokalen Koordinatensystem der Form führen wir die Operationen der Transformation jedes Dreieck auf das globale System speichern .

Dieser Algorithmus ist sehr schnell. Ich habe bis zu 3M Dreiecke in weniger als 40 ms getestet.

Der gesamte Code für diesen Test ist verfügbar here.

Answer 2

Nun ich fast abgeschlachtet, also werde ich eine sehr leicht zu verstehen Tutorial bieten. Es ist gut geschrieben und muss zugeben, dass ich auch viel gelernt habe!

ich die Mathematik zu dem Artikel verlassen werden, da es eine Menge (Transforming Punkte und mit Matrizen) zu decken ist

Fassen wir zusammen:

jeder Punkt auf ray ist ein Funktion der Entfernung vom Ursprung

Ray(t) = Origin + Direction(t) 

Hoffnung th ist hilft!

EDIT:

Nach Joses gutes Beispiel, ich mir die Freiheit nahm eine Ray-Klasse zu schaffen, und ein SimpleRayTest Beispiel den Pfad des Strahls über die Distanz zu zeigen (man denke an den Strahl als Projektil) . Obwohl es nicht Dreiecksüberschneidungen abdeckt, sollte es bei der Visualisierung helfen, wie der Strahl funktioniert.

Quellen sind auch in der Bibliothek Link zur Verfügung gestellt Jose zur Verfügung gestellt.