forum.boolean.name - Ближайшая вершина бокса до прямой в 3д

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Ближайшая вершина бокса до прямой в 3д (http://forum.boolean.name/showthread.php?t=17628)

WISHMASTER35

15.12.2012 03:29

Ближайшая вершина бокса до прямой в 3д

Есть такой алгоритм

Код:

    public static Vector2f getClosestVertex(Box box, Line line) {

        Vector2f dir = Vector2f.sub(line.getB(), line.getA()).getDirection();

        dir = new Vector2f(dir.y, -dir.x);

        if( Vector2f.sub(box.getPos(), line.getA()).dot(dir) > 0 ) dir.mul(-1); 

        

        Vector2f dirX = box.getDirX().getDirection();

        Vector2f dirY = box.getDirY().getDirection();

        

        float sx = Math.signum( dirX.dot(dir) );

        float sy = Math.signum( dirY.dot(dir) );

        

        Vector2f closest = box.getPos();

        closest.add( Vector2f.mul(box.getDirX(), sx) );

        closest.add( Vector2f.mul(box.getDirY(), sy) );

        return closest;

    }

Суть его: находим перпендикуляр прямой, нормализуем его, и проверяем оси бокса смотрят на перпендикуляр или нет. Из этих данных вычисляем вершину: box.pos + box.dirX*sx + box.dirY*sy.
Все довольно просто, но как для 3д это сделать? Ведь перпендикуляр не вычислишь.

Нужно для нахождения ближайших точек между боксом и отрезком. Потом я нахожу ближайшие точки на боксе от вершин отрезка. И из этих 3х точек выбираю ближайшие к отрезку. Может есть проще пути.

dsd	15.12.2012 03:44

Ответ: Ближайшая вершина бокса до прямой в 3д

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

http://ru.onlinemschool.com/math/lib...ometry/p_line/

WISHMASTER35

15.12.2012 14:11

Ответ: Ближайшая вершина бокса до прямой в 3д

dsd, ну это ясно. А быстрее как сделать?

RegIon

15.12.2012 16:23

Ответ: Ближайшая вершина бокса до прямой в 3д

var distantion = Vector3.Cross(point_1-line , line).sqrMagnitude/line.sqrMagnitude;
Для каждой фигуры будет свой алгоритм, если для куба: то узнаешь вектор поворота относительно вектора линии, а так как куб правильный, то длина от центра до точки = sqrt(.75 * scale^2), point = rot_vector_about_line * Mathf.sqrt(.75 * scale^2);

Только тогда оси куба должны быть направленны так, чтобы каждая ось проходила через 2 противоположные точки.

Вектор линии нужно будет параллельно переносить, что бы он проходил через центр куба.
Учитывать что нужный нам угол поворота <90 (а то получим противоположную точку) и ещё человеческий фактор
вроде так,но уверен на 50%

WISHMASTER35

15.12.2012 16:29

Ответ: Ближайшая вершина бокса до прямой в 3д

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

Platon

16.12.2012 14:25

Ответ: Ближайшая вершина бокса до прямой в 3д

Думаю можно и без перебора
вроде того:

Код:

Vector3f vectorA = segment.positionA - box.center;

Vector3f vectorB = segment.positionB - box.center;



Vector3f min_vector = ( dot( vectorA ) < dot( vectorB ) ) ? vectorA : vectorB;



x = sign( min_vector.x );

y = sign( min_vector.y );

z = sign( min_vector.z );



Vector3f closest = box.center + box.extent * Vector3f( x, y, z );

фишка в том, что знаки вектора "бокс-сегмент" ( конечно без нуля: -1, +1 ) как раз и определят ближайшую вершину, а ее позицию можно вычислить сдвинув центр бокса, на его полуразмеры по получившейся из этих самых знаков оси.

ЗЫ
хотя я это не проверял, просто мысль :)

WISHMASTER35

16.12.2012 15:36

Ответ: Ближайшая вершина бокса до прямой в 3д

Platon, я в своем первом посту эту идею и написал. Но для 2д было все просто.
Может твой алгоритм заработает.
Может методом разделяющей оси это можно решить, но тут я совсем слабо понимаю.

Platon

16.12.2012 18:40

Ответ: Ближайшая вершина бокса до прямой в 3д

Цитата:

Сообщение от WISHMASTER35 (Сообщение 246650)

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

про SAT кратко и помоему вполне понятно написано здесь
для бокса ориентированого по глобальным осям, иначе говоря AABB, SAT довольно прост - проекции бокса на оси это минимальное и максимальное значение вершин по соответствующим осям X, Y, Z. Ну и отрезок так-же спроецировать можно и сравнить проекции, только вот что это даст, кроме теста пересечения? :-)

ЗЫ
Кстати тот код что ты описал для 2д кажется не рабочий, ты его тестил?

WISHMASTER35

16.12.2012 19:30

Ответ: Ближайшая вершина бокса до прямой в 3д

Цитата:

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

А если середина отрезка ближе всего твой алгоритм будет работать?
Чтобы понять SAT нужно не прочитать, а представить это все. Я до сих пор не понимаю как оно помогает найти точки пересечения. Вот демки которые помогут это представить http://www.metanetsoftware.com/technique/tutorialA.html

Мой алгоритм конечно работает. Находим перпендикуляр отрезка. И просто проверяем оси бокса смотрят на отрезок или в другую сторону.
Конечно это для прямой, а не отрезка.

WISHMASTER35

16.12.2012 20:03

Ответ: Ближайшая вершина бокса до прямой в 3д

Вложений: 1

Platon, что-то твой алгоритм не работает. Записал так

Код:

        Vector2f vectorA = line.getA().sub(box.getPos());

        Vector2f vectorB = line.getB().sub(box.getPos());

        Vector2f min_vector = ( vectorA.lengthSquared() < vectorB.lengthSquared() ) ? vectorA : vectorB;

        float x = sign( min_vector.x ) * box.getExtents().x;

        float y = sign( min_vector.y ) * box.getExtents().y;

        return box.getPos().add( box.getDirX().mul(x) ).add( box.getDirY().mul(y) );

Вот 2д проект, если с java знаком, то можешь глянуть. Там сейчас мой алгоритм работает.

Часовой пояс GMT +4, время: 11:23.