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

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

0 голосов
/ 22 мая 2019

Я хочу эффективно найти все треугольники (например, грани многогранной сетки), которые содержатся в том или пересекаются с объемом (например, 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-поиск? Для круга и 2D-треугольника пересечения нет, но я мог бы использовать пересечение Iso_rectangle_2 и Triangle_2 в качестве хорошего первого предположения.
  3. Каким-то образом обойдите внутренности дерева AABB и остановитесь, прежде чем я найду узел, который больше не содержит мой запрос.
  4. Измените метод closest_point_and_primitive (), задайте необязательный параметр max_distance и верните все примитивы в пределах этого расстояния. Это потребует от меня возиться с кодом CGAL. ​​
  5. Напишите мою собственную структуру данных. Это займет некоторое время, чтобы сделать это правильно.

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

Ответы [ 2 ]

0 голосов
/ 28 мая 2019

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

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

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

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

С помощью этой оптимизации я мог бы сократить время запроса с 20 мс (простая грубая сила) до 3 мс для сетки с 100k гранями, где один запрос возвращает примерно 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);
    }
}
0 голосов
/ 23 мая 2019

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

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 properties , чтобы установить bool на true для всех граней, которые пересекаются.Затем создайте новое свойство по краям и установите для него значение true, если для свойства одного из инцидентных граней было установлено значение true.

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

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

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

...