JavaFX 8 3D Point Intersection Point

Question

Is it possible in the JavaFX 8 3D scene to find points along the ray (for example, PickRay), starting from an arbitrary point in 3D space using some three-dimensional direction vector where the ray intersects the triangles in the grid (TriangleMesh inside the MeshView)?

I know this is done in Camera / MouseHandler to select the mouse, but I see no way to do this for arbitrary beams.

Answer 1

As follows from @ jdub1581, the ray is just a geometric vector, so to find the list of triangles intersected by this vector, we need to solve problems like “line intersects the plane” and “line intersects the plane in the triangle of the boundary.

Suppose we have a TriangleMesh , and we have a list of vertices and a list of faces. Each vertex with three coordinates, each of which has 3 vertices (excluding texture, normals, ...). For simplicity, use two Point3D to store them.

There are several 3D shapes in this link that are ready to use. Enough 1 CuboidMesh .

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

This will give us this three-dimensional shape:

Now, if we look at the grid, 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)); 

Add some 3D points in our scene, one origin and one target, both in global coordinates, and determine 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 

Then the equation of the beam will be as follows:

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

If we add a thin cylinder between these two points, we get a visual representation of our beam:

Cross border crossing

The first step is to check if the ray intersects the bounding rectangle of our shape. In the local coordinates of the form, we have 6 faces defined 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 will be working on a local system, we need our starting point in these 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 from 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 continue the triangles. In this example, these will be the intersection points: (3,5, -4,5, -2) and (2,5,0,5,2).

Intersection of triangles

There are several algorithms for searching if the ray intersects any triangle of the mesh, so we do not need to reinvent the wheel.

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

As soon as we have the origin in the local coordinates of the form and know the direction of the beam, the implementation of this algorithm is as follows:

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

If we build these faces, we will see the intersection:

Please note that, performing all operations in the local coordinate system of the form, we save the operations of converting each triangle into a global system.

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

All code for this test is available here .

Answer 2

Well, I almost killed it, so I will make it very easy to understand Tutorial . It is well written and I must admit that I learned a lot!

I will leave the math in the article, since it can be covered a lot (transformation of points and the use of matrices)

Summarizing:

any point on the ray is a function of the origin

 Ray(t) = Origin + Direction(t) 

Hope this helps!

EDIT:

After Jose’s great example, I took the liberty of creating a Rei class and a SimpleRayTest example to show the beam’s distance path (think of the beam as a projectile). Although it does not cover the intersection of triangles, it should help in visualizing how the beam works.

Sources are also available in the Jose library link.