Сетка для пересечения сетки

Question

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

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

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

Answer 1

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

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

EDIT:

Начиная с CGAL 4.12, теперь есть функция CGAL::Polygon_mesh_processing::do_intersect().

Answer 2

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

Answer 5

Я думаю, что вам не хватает поискового запроса overlay .Например, вот веб-страница на Surface Mesh Overlay .Этот сайт имеет краткую библиографию всех авторов.Вот еще один документ на эту тему: « Построение наложенной сетки с использованием чередующихся остовных деревьев » * INFOCOM 2004 : двадцать третья ежегодная совместная конференция IEEE Computer and Communications Society.См. Также вопрос GIS SE " Выполнение наложения двух триангулированных нерегулярных сетей (TIN) ."