CGAL: эффективный поиск всех треугольников в объеме (ограничивающая рамка или запрос шара)

Я хочу эффективно найти все треугольники (например, грани многогранной сетки), которые содержатся в объеме или пересекаются с ним (например, запрос AABB или сферы). Я хочу сделать это, если это возможно и разумно, с помощью встроенных функций CGAL.

Мое текущее решение — простая грубая сила: для всех граней в сетке проверьте, меньше ли расстояние от грани до центра шара, чем радиус шара. Раньше я использовал нечеткий сферический запрос KD-дерева по вершинам, но он был недостаточно точен для моего приложения. Мне нужны полные пересечения сферы-треугольника.

Дерево CGAL AABB (https://doc.cgal.org/latest/AABB_tree/index.html) кажется лучшей структурой данных, но мне нужно трехмерное линейное ядро, в котором нет теста пересечения для треугольников и любого объема (https://doc.cgal.org/latest/Kernel_23/group__intersection__linear__grp.html). Дерево CGAL KD не работает, поскольку оно может содержать только точки.

Мои идеи:

  1. Добавьте пользовательскую функцию do_intersect() для Triangle_3 и Sphere_3, которую может использовать дерево AABB. Это вообще возможно? Для этого, вероятно, также потребуется пользовательский метод squared_distance().
  2. Преобразуйте объемный запрос в два запроса области, спроецировав треугольники, например, на плоскости XY и YZ. Может ли дерево AABB обрабатывать даже 2D-поиск? Для круга и двумерного треугольника нет пересечения, но я мог бы использовать пересечение Iso_rectangle_2 и Triangle_2 как хорошее первое предположение.
  3. Каким-то образом пройтись по внутренностям дерева AABB и остановиться, прежде чем я найду узел, который больше не содержит моего запроса.
  4. Измените метод ближайшей точки_и_примитива (), задайте необязательный параметр max_distance и верните все примитивы в пределах этого расстояния. Это потребовало бы от меня возиться с кодом CGAL.
  5. Напишите свою собственную структуру данных. Это займет некоторое время, чтобы все исправить.

Я что-то пропустил? Какое решение потребует наименьших усилий?

3 метода стилизации элементов HTML
3 метода стилизации элементов HTML
Когда дело доходит до применения какого-либо стиля к нашему HTML, существует три подхода: встроенный, внутренний и внешний. Предпочтительным обычно...
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
1
0
376
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Для набора пересекающихся треугольников вы можете использовать:

std::vector<Primitive> primitives;
tree.all_intersected_primitives(sphere, std::back_inserter(primitives));
//or
tree.all_intersected_primitives(tree2, std::back_inserter(primitives));

где tree2 является AABB-деревом треугольников вашего ограничивающего объема.

Это даст вам элементы, которые пересекаются границей вашего объема. Затем вы можете использовать Surface_meshхарактеристики, чтобы установить логическое значение true для всех пересекающихся граней. Затем создайте новое свойство на ребрах и установите для него значение true, если вы установили для свойства одной из падающих граней значение true.

Затем, вызвав connected_components(), вы сможете разделить сетку на части внутри и снаружи ограничивающего объема (игнорируя пересекающуюся часть).

Чтобы закончить, вам нужно выбрать одну точку для каждого подключенного компонента и посмотреть, находится ли она внутри или снаружи ограничивающего объема. Это прямолинейно для сферы, и вы можете использовать Side_of_triangle_mesh для случая сетки (без дублирования дерева AABB для экономии памяти и времени).

Если ваш ограничивающий объем представляет собой bbox, вы можете сделать то же самое для сферы.

Себастьян, спасибо за ваш вклад. Просто для уточнения: версия 1 all_intersected_primitives(sphere, ...) принимает Sphere_3 в качестве входных данных, хотя ядро 3D Kartesian имеет только do_intersection для Sphere_3 с другим Sphere_3 и с Plane_3?

P. Erler 24.05.2019 17:39

Версия 2 all_intersected_primitives(tree2, ...) будет использовать другое дерево AABB, основанное на сфере, аппроксимированной многогранной сеткой? Как насчет использования «Пересекающихся последовательностей dD Iso-ориентированных блоков» на BB треугольников сетки и BB моей сферы в качестве запроса? Это было бы хорошим начальным предположением.

P. Erler 24.05.2019 17:47

Первая версия может принимать сферу, плоскость, ... любой примитив ядра, если do_intersect имеет для него перегрузку. Вторая версия работает с произвольной треугольной сеткой, которую вы бы сначала поместили в дерево AABB.

sloriot 25.05.2019 14:52
Ответ принят как подходящий

Используя некоторые идеи из ответа Слориота, я смог решить свою проблему.

Поскольку в документации по do_intersect() не указана перегрузка для Sphere_3 и Triangle_3, неудивительно, что дерево AABB не поддерживает запросы со Sphere_3.

Однако дерево AABB поддерживает запросы с BBox_3, который не упоминается в документе do_intersect().

Вызов all_intersected_primitives() с Bbox_3 возвращает все примитивы дерева AABB, которые содержатся или пересекаются с Bbox_3. Это первое хорошее предположение, чтобы получить фактические пересечения со сферой.

С помощью этой оптимизации я мог сократить время запроса с 20 мс (простой перебор) до 3 мс на сетке со 100 000 граней, где один запрос возвращает примерно 10 граней.

Вот соответствующий код:

double r = CGAL::sqrt(patch_radius_squared);
CGAL::Bbox_3 query(
    sphere_center.x() - r, 
    sphere_center.y() - r, 
    sphere_center.z() - r, 
    sphere_center.x() + r, 
    sphere_center.y() + r, 
    sphere_center.z() + r);

std::list<Tree::Primitive_id> primitives;
tree.all_intersected_primitives(query, std::back_inserter(primitives));

std::vector<Triangle_3> intersected_facets;
for (const Tree::Primitive_id& p : primitives)
{
    // intersection with bb gives only a good first guess -> check actual intersection
    if (CGAL::squared_distance(*p, sphere_center) <= patch_radius_squared)
    {
        intersected_facets.push_back(*p);
    }
}

Другие вопросы по теме