Определить, что одно тело находится внутри другого

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

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

как определить этот случай?

нашёл как вариант считать по пересечению луча (чётное/нечётное количество раз),
но это требует больших вычислительных затрат

0

Построить aabb для двух тел, если один из aabb полностью лежит в другом значит и все треугольники полностью лежат в нем.

0

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

Не годится, пример: 2 сферы, большая и маленькая, что может спокойно уместиться в "уголке aabb" большой. А что говорит дипсик?

0

Сообщение от Igor3D Не годится, пример: 2 сферы, большая и маленькая, что может спокойно уместиться в "уголке aabb" большой. А что говорит дипсик?

Хмм... тоже верно. Можно доразвить идею. Предположим один aabb полностью содержится в другом. Алгоритм может быть таким:
1. Определяем наибольший aabb.
2. Подгоняем под размер модели ортогональную матрицу
3. Рисуем объект
4. Считываем из буфера глубины область пикселей отрисованного объекта в массив 1
5. Рисуем второй объект
6. Считываем из буфера глубины область пикселей отрисованного объекта в массив 2
7. Попиксельно сравниваем массив 1 и 2
Случай a: Если есть различие в массиве переходим к задаче пересечения треугольников. Тут кстати опять нам могут помочь aabb, считаем область пересечения двух aabb и ищем пересекающиеся треугольники только в этой области, тут еще можно использовать окто деревья для ускорения...
Случай b: Если различий нет, нужно проверить z-интервал поскольку больший объект может заслонять меньший но не пересекать. Поварачиваем перпендикулярно взгляду камеру и повторяем с пункта 2.

Вариант хардкорный, но достаточно быстрый. Естественно нужно включить тест глубины...

0

Поля расстояний между точками помогут.

0

Сообщение от glBegin Вариант хардкорный

Да какой-то он "натужный" или "суетливый", неужели нужно столько приседаний? Задача ведь не выглядит такой уж сложной. Нужно глянуть теорию/готовые решения.

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

0

Сообщение от Igor3D Да какой-то он "натужный" или "суетливый", неужели нужно столько приседаний? Задача ведь не выглядит такой уж сложной. Нужно глянуть теорию/готовые решения. Заметим что ссылаться на (якобы) решенную задачу пересечения треугольников явно неуместно, там долго пыль глотать, и как делать - неясно

Но быстрый, и пока вы там будете выдумывать алгоритмы за O(n^2), GPU сделает за вас всю работу.
Решать математикой, ну попробуйте, есть варианты? Опять же если задача решена, значит пересечений треугольников не было, а значит либо тело полностью лежит внутри другого либо полностью снаружи...

0

Сообщение от Khludenkov нашёл как вариант считать по пересечению луча (чётное/нечётное количество раз), но это требует больших вычислительных затрат

Кажется это и есть верный путь. Причем достаточно одного луча что стартует с поверхности/полигона меньшего объекта по оси X. Да, перебираем все полигоны обоих объектов, но лишь однажды, поэтому никаких "больших вычислительных затрат" нет. Отбрасываем стартовые пересечения с меньшим и требуем нечет с большим. Конечно при условии что "пересечений нет" и что оба объекта имеют объем

Добавлено через 2 часа 14 минут
Вот полезное утверждение

При отсутствии пересечений если хоть один вертекс меньшего внутри большего - значит и весь меньший внутри

Уточним детали
- по bounding box (он же aabb) находим кто там меньший и больший. По каждой оси диапазон значений меньшего должен быть внутри большего

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

0

Сообщение от Igor3D Кажется это и есть верный путь. Причем достаточно одного луча что стартует с поверхности/полигона меньшего объекта по оси X. Да, перебираем все полигоны обоих объектов, но лишь однажды, поэтому никаких "больших вычислительных затрат" нет. Отбрасываем стартовые пересечения с меньшим и требуем нечет с большим. Конечно при условии что "пересечений нет" и что оба объекта имеют объем

Это самый оптимальный способ для общего случая. Не считая всякие частности для прямоугольников сфер и прочего.

Сообщение от Igor3D Да, перебираем все полигоны обоих объектов

Заранее построенный индекс R-Tree для геометрии отбросит лишние полигоны. R-Tree.

Пару лет назад писал пример для объяснения как работает определение коллизий с помощью полей расстояний
https://www.shadertoy.com/view/3scczB
Компьютеру обычно гораздо проще искать расстояния между точками чем решать систему уравнений треугольника и прямой в трехмерном пространстве для определения коллизии.

Топикстартеру советую гуглить в сторону "R-Tree for poligons" можно в варианте "R-Tree(SRT)" и в сторону "Поля расстояний".

0

0

Сообщение от Igor3D Не уловил идею. Ну для пары сфер работает, а для полигонов (регулярный случай) как?

Без разницы для чего (точки там линии треугольника или тетрайдера =)). просто определяется расстояние между объектами если расстояние до объекта отрицательное то произошла коллизия и луч прошел сквозь объект. Поля расстояний это способ определить шаг на котором ищется коллизия.
https://www.shadertoy.com/view/lslXD8

https://www.shadertoy.com/view/Xtl3Wj (строка 46 определение коллизии)

Еще хороший пример https://www.shadertoy.com/view/wltBRl (Вкладка common 109 строчка)

Ну и для тех кто любит пожестче =) https://www.youtube.com/watch?v=ajv46BSqcK4

0

Сообщение от MallSerg Без разницы для чего (точки там линии треугольника или тетрайдера =). просто определяется расстояние между объектами)

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

0