Сетчатые сетки

Я ищу библиотеку или документ, который описывает, как определить, пересекает ли одна треугольная сетка другая.

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

Кажется, что это должно быть возможно, потому что пересечение треугольника возможно и потому, что каждая сетка содержит конечное число треугольников. Но я предполагаю, что должен быть лучший способ сделать это, чем очевидный подход O (n * m), где одна сетка имеет n треугольников, а другая имеет m треугольников.

Ответ 1

Как мы обычно делаем это с помощью CGAL с CGAL:: box_intersection_d.

Вы можете сделать это, смешав этот пример с этим one.

Ответ 2

В книге Обнаружение столкновений в реальном времени есть некоторые полезные рекомендации по реализации таких алгоритмов. Основной подход заключается в использовании пространственного разбиения или ограничивающих объемов, чтобы сократить количество проверок tri-tri, которые необходимо выполнить.

Существует ряд хороших академических пакетов, которые затрагивают эту проблему, включая пакет запроса близости, а другая работа Исследовательская группа GAMMA в Университете Северной Каролины, SWIFT, I-COLLIDE и RAPID хорошо известны. Убедитесь, что лицензии в этих библиотеках приемлемы.

Open Dynamics Engine (ODE) - это физический движок, который содержит оптимизированные реализации большого количества примитивов пересечения. Вы можете проверить документацию для теста пересечения треугольника и треугольника на wiki.

Хотя это не совсем то, что вы ищете, я считаю, что это также возможно с CGAL - Дерево треугольников, для запросов пересечения и расстояния

Ответ 3

Я думаю, что поисковый запрос, который вам не хватает, является наложением. Например, здесь представлена веб-страница на Покрытие поверхностной сетки. У этого сайта есть короткая библиография, все те же авторы. Вот еще одна статья по теме: " Наложение структуры сетки с использованием чередующихся остовных деревьев, INFOCOM 2004: Двадцать третья ежегодная совместная конференция Компьютерных и коммуникационных обществ IEEE. См. Также вопрос GIS SE: Выполнение наложения двух триангулированных нерегулярных сетей (TIN).

Ответ 4

Чтобы добавить к другим ответам, есть также методы, связанные с суммой выпуклых многогранников 3D Минковского - вогнутые многогранники можно разложить на выпуклые части. Проверьте это.

Ответ 5

В libigl мы завершаем cgal CGAL::box_intersection_d для пересечения сетки с вершинами V и сталкиваемся с F с другим mesh с вершинами U и грани G, сохраняя пары пересекающихся граней в виде строк в IF:

igl::intersect_other(V,F,U,G,false,IF);

Это игнорирует самопересечения. Для полноты я упомянул, что мы также поддерживаем самопересечения в отдельной функции:

igl::self_intersect(V,F,...,IF);