|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
15.12.2012, 03:29
|
#1
|
Бывалый
Регистрация: 21.12.2008
Адрес: UA
Сообщений: 878
Написано 105 полезных сообщений (для 357 пользователей)
|
Ближайшая вершина бокса до прямой в 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х точек выбираю ближайшие к отрезку. Может есть проще пути.
|
(Offline)
|
|
15.12.2012, 03:44
|
#2
|
Мастер
Регистрация: 13.06.2011
Сообщений: 1,103
Написано 481 полезных сообщений (для 1,836 пользователей)
|
Ответ: Ближайшая вершина бокса до прямой в 3д
Есть же расстояние от прямой до точки, взять и проверить его для всех вершин и выбрать ту что ближе.
http://ru.onlinemschool.com/math/lib...ometry/p_line/
|
(Offline)
|
|
15.12.2012, 14:11
|
#3
|
Бывалый
Регистрация: 21.12.2008
Адрес: UA
Сообщений: 878
Написано 105 полезных сообщений (для 357 пользователей)
|
Ответ: Ближайшая вершина бокса до прямой в 3д
dsd, ну это ясно. А быстрее как сделать?
|
(Offline)
|
|
15.12.2012, 16:23
|
#4
|
Элита
Регистрация: 16.01.2010
Адрес: Новосибирск
Сообщений: 2,158
Написано 502 полезных сообщений (для 1,012 пользователей)
|
Ответ: Ближайшая вершина бокса до прямой в 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%
|
(Offline)
|
|
15.12.2012, 16:29
|
#5
|
Бывалый
Регистрация: 21.12.2008
Адрес: UA
Сообщений: 878
Написано 105 полезных сообщений (для 357 пользователей)
|
Ответ: Ближайшая вершина бокса до прямой в 3д
Я конечно понимаю, что перебрать все вершины не так уж и сложно. Но все же интересно можно не переберая их определить ближайшую? Для 2д это легко получилось.
|
(Offline)
|
|
16.12.2012, 14:25
|
#6
|
Знающий
Регистрация: 04.08.2006
Адрес: Россия
Сообщений: 297
Написано 39 полезных сообщений (для 70 пользователей)
|
Ответ: Ближайшая вершина бокса до прямой в 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 ) как раз и определят ближайшую вершину, а ее позицию можно вычислить сдвинув центр бокса, на его полуразмеры по получившейся из этих самых знаков оси.
ЗЫ
хотя я это не проверял, просто мысль
|
(Offline)
|
|
16.12.2012, 15:36
|
#7
|
Бывалый
Регистрация: 21.12.2008
Адрес: UA
Сообщений: 878
Написано 105 полезных сообщений (для 357 пользователей)
|
Ответ: Ближайшая вершина бокса до прямой в 3д
Platon, я в своем первом посту эту идею и написал. Но для 2д было все просто.
Может твой алгоритм заработает.
Может методом разделяющей оси это можно решить, но тут я совсем слабо понимаю.
|
(Offline)
|
|
16.12.2012, 18:40
|
#8
|
Знающий
Регистрация: 04.08.2006
Адрес: Россия
Сообщений: 297
Написано 39 полезных сообщений (для 70 пользователей)
|
Ответ: Ближайшая вершина бокса до прямой в 3д
Сообщение от WISHMASTER35
Platon, я в своем первом посту эту идею и написал. Но для 2д было все просто.
Может твой алгоритм заработает.
Может методом разделяющей оси это можно решить, но тут я совсем слабо понимаю.
|
Перпендикуляр там ненужен, нужны именно два вектора к концам сегмента, иначе не будет понятно какая часть ( начало или конец ) отрезка ближе к вершине.
про SAT кратко и помоему вполне понятно написано здесь
для бокса ориентированого по глобальным осям, иначе говоря AABB, SAT довольно прост - проекции бокса на оси это минимальное и максимальное значение вершин по соответствующим осям X, Y, Z. Ну и отрезок так-же спроецировать можно и сравнить проекции, только вот что это даст, кроме теста пересечения?
ЗЫ
Кстати тот код что ты описал для 2д кажется не рабочий, ты его тестил?
|
(Offline)
|
|
16.12.2012, 19:30
|
#9
|
Бывалый
Регистрация: 21.12.2008
Адрес: UA
Сообщений: 878
Написано 105 полезных сообщений (для 357 пользователей)
|
Ответ: Ближайшая вершина бокса до прямой в 3д
Перпендикуляр там ненужен, нужны именно два вектора к концам сегмента, иначе не будет понятно какая часть ( начало или конец ) отрезка ближе к вершине.
|
А если середина отрезка ближе всего твой алгоритм будет работать?
Чтобы понять SAT нужно не прочитать, а представить это все. Я до сих пор не понимаю как оно помогает найти точки пересечения. Вот демки которые помогут это представить http://www.metanetsoftware.com/technique/tutorialA.html
Мой алгоритм конечно работает. Находим перпендикуляр отрезка. И просто проверяем оси бокса смотрят на отрезок или в другую сторону.
Конечно это для прямой, а не отрезка.
|
(Offline)
|
|
16.12.2012, 20:03
|
#10
|
Бывалый
Регистрация: 21.12.2008
Адрес: UA
Сообщений: 878
Написано 105 полезных сообщений (для 357 пользователей)
|
Ответ: Ближайшая вершина бокса до прямой в 3д
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 знаком, то можешь глянуть. Там сейчас мой алгоритм работает.
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 12:01.
|