Точка на пресичане на 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).

Ако начертаем тези лица ще видим пресечната точка:

Имайте предвид, че чрез извършване на всички операции в локалната координатна система на фигурата ние запазваме операциите за трансформиране на всеки триъгълник в глобалната система.

Този алгоритъм е наистина бърз. Тествах до 3M триъгълници за по-малко от 40 ms.

Целият код за този тест е достъпен тук.

Е, почти заклах това, така че ще осигуря много лесен за разбиране урок. Написано е добре и трябва да призная, че научих много!

Ще оставя математиката на статията, тъй като има много за покриване (трансформиране на точки и използване на матрици)

За да обобщим:

всяка точка от лъча е функция на разстоянието от началото

Ray(t) = Origin + Direction(t)

Надявам се това да помогне!

РЕДАКТИРАНЕ:

След страхотния пример на Хосе, си позволих да създам клас Ray и пример SimpleRayTest, за да покажа пътя на лъча върху разстояние (мислете за лъча като за снаряд). Въпреки че не обхваща пресичанията на триъгълниците, трябва да помогне с визуализацията на това как работи лъчът.

Източниците също са достъпни във връзката към библиотеката, предоставена от Хосе.