Нахождение минимального расстояния между объектами и их пересечения

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

Миниатюры

 

0

Сообщение от Khludenkov Какой самый быстрый алгоритм нахождения минимального расстояния между телами А и В (интересует трёхмерный случай) ?

Аппроксимировать тела примитивами (напр сфера, куб и.т.п) и искать расстояния уже между ними. Часто приходится разбивать тела на convex (выпуклые) части. Что само по себе задача не слабая (хотя есть open-source(s))

Сообщение от Khludenkov А если надо определить наличие пересечения этих тел ?

Использовать движок физики (напр Bullet)

1

год назад читал много книг по компьютерной геометрии
и вот там где-то встречал, а вот где - уже не помню
надо заново всё перечитывать...

Добавлено через 2 минуты

Сообщение от Igor3D Аппроксимировать тела примитивами (напр сфера, куб и.т.п) и искать расстояния уже между ними.

аппроксимировать нельзя
разбивать конечно можно

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

Добавлено через 3 минуты

Сообщение от Igor3D Использовать движок физики (напр Bullet)

я как раз свой движок и пишу
посторонние нельзя использовать...

0

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

0

0

Пример мы видим плоский, я вижу тут замкнутые ломаные. А требуется 3D - многогранники будут?

0

Сообщение от Mikhaylo Пример мы видим плоский, я вижу тут замкнутые ломаные. А требуется 3D - многогранники будут?

Да, многогранники...
Нарисовал как смог.
В общем процесс потихоньку движется.
Спасибо.

0

Многогранник - это по сути набор граней, т.е. ограниченных плоскостей. По идее, нужно определить две грани, на которых лежат две ближайшие точки. Если бы грани были бы неограниченными и непараллельными плоскостями, то такие грани в некоторой прямой пересекались бы, и эта прямая представляла бы множество ближайших пар точек с расстоянием между ними 0. Но плоскости ограничены. Это значит, что на какой-то границе и лежат искомые точки. Так в итоге можно дорассуждаться до того, что достаточно перебрать только вершины многогранника. При чем впуклые вершины можно не рассматривать. Так?

0

Сообщение от Mikhaylo При чем впуклые вершины можно не рассматривать. Так?

Нужно рассматривать. Можно иголкой ткнуть и впуклую вершину.

0

Ок. Не надо пары впуклых вершин рассматривать?

0

как вариант, видно, что может быть и между вершиной и плоскостью

Миниатюры

 

0

то же самое для 3-х мерного случая

0

Сообщение от Khludenkov как вариант, видно, что может быть и между вершиной и плоскостью

Или между 2 ребрами (2 кубика, один повернут)

0

Сообщение от Igor3D Или между 2 ребрами (2 кубика, один повернут)

да.

то есть для 3х мерного случая имеем три типа сущностей

1. вершины
2. рёбра
3. плоскости

и между ними всеми надо проверять минимальное расстояние

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

0

Такой порядок спуска по дереву:

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

2. Пара "ребро-грань"
Если ребро и грань непараллельны, то надо рассмотреть пары "ребро-ребрА", "вершинЫ-грань".

3. Пара "ребро-ребро"
Если ребра непараллельны, то рассмотреть пары "вершины-ребра" в двухстороннем порядке.

4. Пара "вершина-грань"
Если из вершины проводится нормаль на грань, то это минимальное расстояние, не надо перебирать пары "вершина-рёбра" и "вершина-вершины".
Нормаль из точки на грани - это нормаль к плоскости - расчет одного уравнения вида ax+by+cx+d=0. Надо только убедиться, что нормаль к плоскости попадает на грань, а не вне грани. Это классическая задача "находится ли точка внутри/снаружи многоугольника?".

5. Пара "вершина-ребро"
Ребро заменяем на прямую и решаем задачу в плоскости по аналогии с п.4. Если нормаль падает на отрезок, то это минимальное расстояние, если не было останова в п.4.

6. Пара "вершина-вершина"
Тут понятно, евклидово расстояние между точками.

1

Для примера рассмотрим два тетраэдра ABCD и KLMN. Нужно найти минимальное расстояние между всеми парами граней (треугольниками), выбрать наименьшее - это и будет минимальный просвет.

F1 - Функция нахождения расстояния "грань-грань" (для примера найдем минимальное расстояние между гранями ABC и KLM)
1.1. Фиксируем, ABC и KLM параллельны или нет.
1.2 Находим минимальные расстояния между ребрами AB, BC, AC и гранью KLM, а также между ребрами KL, LM, KM и гранью ABC. То есть шесть раз запускаем функцию F2.
1.3 Если ABC и KLM непараллельны, выбираем наименьшее расстояние из шести минимальных.
1.4 Если ABC и KLM параллельны, то один из вызовов функции F2 может прерваться при условии нахождения нормали к грани.

F2 - Функция нахождения расстояния "ребро-грань" (для примера рассмотрим ребро AB и грань KLM)
2.1. Фиксируем, AB и KLM параллельны или нет.
2.2 Находим минимальные расстояния между вершинами A, B и гранью KLM, а также между ребром AB и ребрами KL, LM, KM. То есть два раза запускаем функцию F4 и три раза - функцию F3.
2.3 Если AB и KLM непараллельны, выбираем наименьшее расстояние из пяти минимальных.
2.4 Если AB и KLM параллельны, то один из вызовов функций F3, F4 может прерваться при условии нахождения нормали к грани или ребру.

F3 - Функция нахождения расстояния "ребро-ребро" (для примера рассмотрим ребра AB и KL)
3.1. Фиксируем, AB и KL параллельны или нет.
3.2 Находим минимальные расстояния между вершинами A, B и ребром KL, а также между ребром AB и вершинами K, L. То есть четыре раза запускаем функцию F5.
3.3 Если AB и KL непараллельны, выбираем наименьшее расстояние из четырех минимальных.
3.4 Если AB и KL параллельны, то один из вызовов функций F5 может прерваться при условии нахождения нормали к ребру.

F4 - Функция нахождения расстояния "вершина-грань" (для примера рассмотрим вершину A и грань KLM)
4.1. Находим проекцию точки A на неограниченную плоскость KLM.
4.2. Если проекция точки на плоскости находится внутри многоугольника KLM, то искомое расстояние - это расстояние между точкой A и неограниченной плоскостью KLM. Конец функции F4.
4.3 Если точка проецируется вне грани KLM, то находим минимальные расстояния между вершиной A и ребрами KL, LM, KM. То есть три раза запускаем функцию F5.
4.4 Выбираем наименьшее расстояние из трех минимальных.

F5 - Функция нахождения расстояния "вершина-ребро" (для примера рассмотрим вершину A и ребро KL)
5.1. Находим проекцию точки A на неограниченную прямую KL.
5.2. Если проекция точки на прямой находится на отрезке KL, то искомое расстояние - это расстояние между точкой A и неограниченной прямой KL. Конец функции F5.
5.3 Если точка проецируется вне отрезка KL, то находим минимальные расстояния между вершинами A и K, L. То есть два раза запускаем функцию F6.
5.4 Выбираем наименьшее расстояние из двух минимальных.

F6 - Функция нахождения расстояния "вершина-вершина"
R^2 = (X1-X2)^2 + (Y1-Y2)^2 + (Z1-Z2)^2
Корень необязательно вычислять, все равно минимальное число ищем.

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

0