Сетка в сетку пересечений

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

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

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


mesh computational-geometry surface triangulation
person Doug McClean    schedule 01.11.2011    source источник
comment
«Очевидный» подход даст ложноотрицательные результаты, если одна из сеток полностью находится внутри другой.   -  person cmannett85    schedule 02.11.2011
comment
Меня интересуют столкновения между сетками как поверхности нулевой толщины. Я понимаю, как бы это случилось, если бы меня интересовали столкновения между сетками, интерпретируемыми как многогранники.   -  person Doug McClean    schedule 02.11.2011
comment
См. также здесь треугольник-треугольник   -  person bobobobo    schedule 16.01.2013

Ответы (5)


arrow_upward
8
arrow_downward

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

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

РЕДАКТИРОВАТЬ:

Начиная с CGAL 4.12 появилась функция person sloriot    schedule 02.11.2011

comment
Экзамены 4 и 5 очень полезны для начинающих. Однако неясно, как создать древовидную структуру AABB, чтобы ускорить весь процесс. Кроме того, примеры более наглядны для случая самопересечения. В случае двух отдельных сеток это не очень понятно (и я предполагаю, что бросать все треугольники / квадраты в один вектор совсем не оптимально). Любые предложения по одному из вышеперечисленных? - person dim_tz; 07.04.2014
comment
Вам нужно использовать один вектор на сетку и использовать CGAL :: box_intersection_d () . - person sloriot; 07.04.2014
comment
Начиная с CGAL 4.12 появилась функция [_1 _] (doc.cgal.org/latest/Polygon_mesh_processing - person sloriot; 24.04.2019

arrow_upward
3
arrow_downward

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

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

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

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

person Andrew Walker    schedule 02.11.2011

arrow_upward
1
arrow_downward

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

person Joseph O'Rourke    schedule 02.11.2011

arrow_upward
1
arrow_downward

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

person cmannett85    schedule 02.11.2011

arrow_upward
1
arrow_downward

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

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

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

igl::self_intersect(V,F,...,IF);
person Alec Jacobson    schedule 26.04.2014