Точка пересечения 3D-сцены JavaFX 8

Как предполагает @jdub1581, луч — это просто геометрический вектор, поэтому, чтобы найти список треугольников, пересекаемых этим вектором, нам нужно решить задачи типа «линия пересекает плоскость» и «линия пересекает плоскость в границах треугольника».

Предположим, у нас есть TriangleMesh, и у нас есть список вершин и список граней. Каждая вершина с 3 координатами, каждая грань с 3 вершинами (без учета текстуры, нормалей,...). Для простоты давайте будем использовать два списка Point3D для их хранения.

По этой ссылке есть несколько готовых к использованию 3D-фигур. Возьмем один CuboidMesh.

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

Это даст нам эту 3D-форму:

Теперь, если мы посмотрим на сетку, мы можем создать два списка с вершинами и гранями:

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

Давайте добавим в нашу сцену несколько 3D-точек, один источник и одну цель, обе в глобальных координатах, и определим направление нормализованного вектора:

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

Тогда уравнение луча будет таким:

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

Если мы добавим тонкий цилиндр между этими двумя точками, мы получим визуальное представление нашего луча:

Пересечение ограничивающей рамки

Первым шагом будет проверка, пересекает ли луч ограничивающую рамку нашей фигуры. В локальных координатах формы у нас есть 6 граней, заданных их нормалями, с их 6 центрами:

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

Так как мы будем работать в локальной системе, нам нужна наша исходная точка в этих координатах:

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

Теперь для любой из шести граней мы получаем расстояние t до плоскости, следующей за этим ссылка. Затем мы можем проверить, принадлежит ли точка ящику или нет.

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

Если counter.get()>0, то у нас есть пересечения между лучом и фигурой, и мы можем продолжить работу с треугольниками. В данном примере это будут точки пересечения: (3,5,-4,5,-2) и (2,5,0,5,2).

Пересечение треугольников

Существует несколько алгоритмов для задачи определения, пересекает ли луч какой-либо треугольник сетки, поэтому нам не нужно изобретать велосипед.

Тот, который я использовал, принадлежит Tomas Möller & Ben Trumbore. Он предоставит расстояние t от начала координат до плоскости и координаты u,v внутри треугольника для данного пересечения.

Когда у нас есть начало в локальных координатах формы и мы знаем направление луча, реализация этого алгоритма такова:

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

В этом примере мы находим три грани, заданные этими вершинами: (85, 1245, 1274), (85, 1274, 1266) и (351, 1476, 1479).

Если мы построим эти грани, мы увидим пересечение:

Обратите внимание, что, выполняя все операции в локальной системе координат фигуры, мы сохраняем операции преобразования каждого треугольника в глобальную систему.

Этот алгоритм действительно быстрый. Я протестировал до 3 миллионов треугольников менее чем за 40 мс.

Весь код для этого теста доступен здесь.

Ну, я почти вырезал это, поэтому я предоставлю очень простой для понимания учебник. Написано хорошо, и должен признать, что я тоже многому научился!

Я оставлю математику в статье, так как ее очень много (преобразование точек и использование матриц).

Подводя итог:

любая точка на луче является функцией расстояния от начала координат

Ray(t) = Origin + Direction(t)

Надеюсь это поможет!

ИЗМЕНИТЬ:

После отличного примера Хосе я позволил себе создать класс Ray и пример SimpleRayTest, чтобы показать путь луча на расстоянии (представьте себе луч как снаряд). Хотя он не охватывает пересечения треугольников, он должен помочь с визуализацией того, как работает луч.

Исходники также доступны в библиотеке по ссылке, предоставленной Хосе.