Войти
ПрограммированиеФорумОбщее

Нахождение ближайших точек 2-х объектов

Страницы: 1 2 Следующая »
#0
(Правка: 19 апр. 2018, 7:48) 16:39, 18 апр. 2018

Доброго всем времени суток.

Есть задача - определить ближайшие точки на поверхности 2х объектов. В общем случае это 2 не выпуклых объекта.

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

Я хочу понять сам принцип и у меня эвристический кризис, не могу придумать с чего даже начать решать такую задачу.


#1
16:51, 18 апр. 2018

Разбить на выпуклые фрагменты, перебрать все попарно.

#2
(Правка: 17:38) 16:57, 18 апр. 2018

Всмысле? Что это даст? Как перебрать?

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

#3
(Правка: 18:03) 17:55, 18 апр. 2018

xXxBlackbirdxXx
> перебираться все вершины одного объекта с всеми другого попарно
истесственно, если не выпуклые объемы

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

2д? 3д?

#4
18:03, 18 апр. 2018

xXxBlackbirdxXx
Сложить треугольники каждой из моделей в дерево. Потом выбрать пары нод из двух деревьев, между которыми есть смысл сравнивать дистанцию. Сравнить дистанцию между треугольниками из кадой ноды.

#5
18:12, 18 апр. 2018

MrShoor
многопоточность + SIMD должны быть сравнимы с GPU

#6
19:34, 18 апр. 2018

xXxBlackbirdxXx
> По-моему это сравни тому, чтобы перебираться все вершины одного объекта с всеми
> другого попарно
Нет, с чего это? Число вершин намного больше, чем число выпуклых объёмов при разбиении.

#7
(Правка: 20:40) 20:32, 18 апр. 2018

xXxBlackbirdxXx
> Визуальное представление: корабль влетает в астероид с полостью или сквозной
> дыркой. Необходимо определить 1 точку на астероиде и 1 точку на корабле,
> которые находятся ближе всего друг к другу.
> Я хочу понять сам принцип и у меня эвристический кризис, не могу придумать с
> чего даже начать решать такую задачу.

Честно решить эту задачу можно перебором всего и вся. Считать да, много. Я решал похожую задачу в формулировке «найти на двух объектах пару полигонов с минимальным расстоянием между ними».

Ближайшими точками объекта А и объекта Б могут оказаться такие пары точек:

1. Вершина А и вершина Б.

2. Вершина А и точка на ребре Б (её проекция на ребро Б).
3. Вершина Б и точка на ребре А.

4. Вершина А и точка внутри грани Б (её проекция на грань Б; при условии что эта проекция попадает внутрь полигона, задающего эту грань).
5. Вершина Б и точка внутри грани А.

6. Точка на ребре А и точка на ребре Б.

+ На всякий случай

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

#8
(Правка: 7:46) 7:45, 19 апр. 2018

1 frag / 2 deaths
> xXxBlackbirdxXx
> > По-моему это сравни тому, чтобы перебираться все вершины одного объекта с
> > всеми
> > другого попарно
> Нет, с чего это? Число вершин намного больше, чем число выпуклых объёмов при
> разбиении.

да, согласен... Но что считать за расстояние между объёмами? Среднеарифметическое координат всех точек объема нельзя т.к. если объем-шар то для 2х шаров модуль вектора от одного такого центра до другого можно сравнить с суммой радиусов и найти минимальное расстояние, при этом если сумма радиусов меньше расстояния между центрами, то объекты не пересекаются. Если же это 2 вытянутых (но выпуклых) объекта, то центры, рассчитанные таким же образом, могут находится также как для шаров в геометрическом центре данных объектов, а вот расстояние будет разным в зависимости от того как объекты развернуты друг к другу.

alexzzzz

Да, эти случаи я понимаю. Но все равно спасибо.
Кстати, ещё и грани (полигоны) могут быть параллельными друг другу. Тогда тоже точек ближайших бесконечное множество.

k119_55524
задача в 3д, т.к. если в 2д в астероиде сделать сквозное отверствие, это уже не будет отверстие, т.к. оно "распилит" астероид надвое. ;)

#9
(Правка: 8:54) 8:53, 19 апр. 2018

1 frag / 2 deaths
> Нет, с чего это? Число вершин намного больше, чем число выпуклых объёмов при
> разбиении.
тор

MrShoor
> Сложить треугольники каждой из моделей в дерево. Потом выбрать пары нод из двух
> деревьев, между которыми есть смысл сравнивать дистанцию. Сравнить дистанцию
> между треугольниками из кадой ноды.
так никто не делает

xXxBlackbirdxXx
> Визуальное представление: корабль влетает в астероид с полостью или сквозной
> дыркой. Необходимо определить 1 точку на астероиде и 1 точку на корабле,
> которые находятся ближе всего друг к другу.
попытка решать такие задачи аналитически, представляя геометрии как polygon soup'ы — очень частый pitfall начинающих программировать физику. в реальности эта задача мало того, что не решается за адекватное время, аналитический поиск minimal translation distance для polygon soup'ов — это вообще очень плохая задача, потому что minimal translation distance для пары тел, состоящих из треугольников в общем случае вовсе не равен minimal translation distance всех пар их треугольников. пример — если высокополигональный гвоздь затолкать в высокополигональную дырку чуть меньшего диаметра, чем он сам, то MTD для всех пар треугольников вернёт небольшое смещение меньше диаметра гвоздя, хотя в реальности mtd должен соответствовать вытаскиванию гвоздя из отверстия. причём проблема не решается точно даже после разбиения дырки на выпуклые тела, не только потому что их получается очень много для хайполи дырки, так ещё и задача их попарного столкновения с гвоздём опять же вернёт не тот mtd, который соответствует исходной задаче.


короче, честная задача поиска столкновений polygon soup'ов настолько неудобна, что её обычно гораздо проще объодить, чем решать. например, в геймдеве  принято моделировать(руками) для каждого игрового объекта его приближённое представление для расчёта физики. обычно для этого используют либо примитивные тела вроде боксов и сфер, либо очень низкополигональные выпуклые модели.

#10
7:53, 20 апр. 2018

Suslik

Задумался. Спасибо за разъяснение.

Суть реально физический движок я сделал свой - силовой, так как импульсные для данной задачи не походили (по сути задача гравитационного движения многих тел). И на этапе написания механизмов определения коллизий даже придумал метод, позволяющий для быстродвижущихся и вращающихся объектов объектов сложной (вытянутой в том числе) формы определить потенциальную возможность столкновения между текущим и следующим тактами расчета физики. Но придумать, как определить будет ли столкновение реально, с учетом взаимного движения, в т.ч. вращательного, для таких сложных объектов пока не получается. После нескольких неудачных методов решил, что определение минимального расстояния может помочь. Видимо не может. Думаю дальше...

#11
18:34, 20 апр. 2018

xXxBlackbirdxXx
> да, согласен... Но что считать за расстояние между объёмами?
Расстояние между объёмами считать методом GJK

Suslik
> тор
избегать

#12
7:08, 21 апр. 2018

Suslik
> так никто не делает
Если надо посчитать расстояние между двумя триангулированными мешами, то только так и делают.

> в реальности эта задача мало того, что не решается за адекватное время
В среднем у меня занимает единицы секунд для поиска дистанции между двумя мешами в каждом из которых ~750К треугольников. Я например считаю это адекватным временем для конкретно моей задачи. А у автора по нульпосту не видно было, какая именно у него была задача.

#13
11:00, 21 апр. 2018

MrShoor
> Если надо посчитать расстояние между двумя триангулированными мешами, то только
> так и делают.
автор написал, что ему для физики надо. ты собрался контакты за секунду искать?

#14
(Правка: 12:04) 11:54, 21 апр. 2018

MrShoor
> Если надо посчитать расстояние между двумя триангулированными мешами, то только
> так и делают.
Вывод - триангулированным мешам не место в физсимуляции.

xXxBlackbirdxXx
> для быстродвижущихся и вращающихся объектов объектов сложной (вытянутой в том
> числе) формы
Вот скажи, в твоей игре прямо
- нельзя ограничить скорости вращения - для игры критически важно, чтобы всё крутилось на сверхтактовых скоростях,
- нельзя упростить форму до применимости более-менее аналитических методов - для игры критически важно, чтобы вращались объекты чуть ли не фрактальной сложности,
- нельзя закрыть глаза на небольшие промахи - для игры критически важно, чтобы даже две антенны на концах крыльев надёжно сцеплялись между собой,
- нельзя нельзя уменьшить число особенных объектов до одного - для игры критически важно, чтобы вращающихся дубовых деревьев с белками было очень много,
или всё-таки лучше пойти на компромисс и сделать хотя бы одну единицу игры?

Страницы: 1 2 Следующая »
ПрограммированиеФорумОбщее