JavaFX 8 3D scene intersection point

Question

Is it possible in a JavaFX 8 3D scene to find points along a ray (e.g. PickRay), starting at an arbitrary point in 3D space with some 3D direction vector, where the ray intersects the triangles in a mesh (TriangleMesh inside a MeshView)?

I know this is done in the Camera/MouseHandler for mouse picking but I can't see any way for doing it for arbitrary rays.

Answer 1

As @jdub1581 suggests, a ray is just a geometric vector, so in order to find a list of triangles intersected by this vector we need to solve problems of the kind 'line intersects plane' and 'line intersects plane within the triangle borders'.

Let's assume we have a TriangleMesh, and we have a list of vertices and a list of faces. Each vertex with 3 coordinates, each face with 3 vertices (without considering texture, normals,... ). For the sake of simplicity let's use two lists of Point3D to store them.

In this link there are several 3D shapes ready to use. Let's grab one CuboidMesh.

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

This will give us this 3D shape:

Now, if we have a look at the mesh, we could create two lists with vertices and faces:

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

Let's add some 3D points in our scene, one origin and one target, both in global coordinates, and define the direction of the vector, normalized:

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

The ray equation then will be this:

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

If we add a slender cylinder between these two points we'll have a visual representation of our ray:

Bounding Box Intersection

The first step will be checking if the ray intersects the bounding box of our shape. In local coordinates of the shape we have 6 faces given by their normals, with their 6 centers:

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

Since we'll work on the local system, we need our origin point in this coordinates:

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

Now, for any of the six faces, we get the distance t to the plane following this link. Then we can check if the point belongs to the box or not.

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

If counter.get()>0 then we have some intersections between the ray and the shape, and we can proceed with the triangles. In this example, these will be the intersection points: (3.5,-4.5, -2) and (2.5,0.5,2).

Triangles intersection

There are several algorithms for the task of finding if the ray intersects any triangle of the mesh, so we don't need to reinvent the wheel.

The one I've used is from Tomas Möller & Ben Trumbore. It will provide the distance t from the origin to the plane, and the coordinates u,v inside the triangle for a given intersection.

Once we have the origin in local coordinates of the shape, and we know the direction of the ray, the implementation of this algorithm is this:

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 this sample, we find three faces, given by these vertices: (85, 1245, 1274), (85, 1274, 1266) and (351, 1476, 1479).

If we plot those faces will see the intersection:

Note that by performing all the operations in the local coordinate system of the shape we save the operations of transforming every triangle to the global system.

This algorithm is really fast. I've tested up to 3M triangles in less than 40 ms.

All the code for this test is available here.

Answer 2

Well I almost butchered this, So I will provide a very easy to understand Tutorial. It is well written, and must admit I learned a lot as well!

I'll leave the math to the article as it is a lot to cover (transforming points and using matrices)

To Summarize:

any point on ray is a function of distance from origin

Ray(t) = Origin + Direction(t)

Hope this helps!

EDIT:

After Jose's great example, I took the liberty of creating a Ray class, and a SimpleRayTest example to show the path of the ray over distance (think of the ray as a projectile). While it does not cover Triangle intersections, it should help with the visualization of how the ray works.

Sources are also available in library link Jose provided.