Поиск ближайшего элемента к точечному формату STL

Краткое введение: у меня есть тело, которое выражается внешней поверхностью, заданной в форме STL (набор треугольных элементов и их направленный наружу вектор нормали). Я пытаюсь определить, находится ли точка, заданная координатами, внутри или снаружи тела.

Проблема: как найти ближайший элемент к заданной точке? Более конкретно, скажем, вы нашли ближайшую вершину к точке, и эта вершина является общей для двух (или более) элементов. Какой "ближайший"? Обратите внимание, что конечный результат определяет, находится ли точка внутри или снаружи тела. Простое нормальное расстояние (скалярное произведение с нормалью) не решает проблему и может привести к неоднозначному результату в зависимости от того, какой из элементов, разделяющих узел, выбран. Использование центроида элемента также проблематично.

Любые предложения, идеи (особенно от людей, которые уже занимались этим вопросом) приветствуются!

РЕДАКТИРОВАТЬ: я сделаю проблему немного сложнее. Скажем, есть открытая поверхность (но она покрывает всю область, так что каждая точка находится на одной из двух сторон поверхности, либо внутри, либо снаружи, в зависимости от направления относительно нормали. На это также нужно ответить, используя тот же подход .

EDIT2: ответ найден!

Надеюсь это поможет!


math geometry cad stl nearest-neighbor
person TheWhitestOfFangs    schedule 16.01.2018    source источник
comment
Обычный способ — выстрелить лучом из точки запроса в произвольном направлении и подсчитать пересечения с поверхностью. Если ваша поверхность маленькая, вы можете просто проверить все треугольники на пересечение. Или вы можете использовать структуру данных ускорения (сетка, kd-дерево, иерархия ограничивающих томов...)   -  person Nico Schertler    schedule 17.01.2018
comment
Я видел этот подход раньше, однако это проблематично. 1. См. мой комментарий к редактированию. 2. Сложные тела, которые я использую, разделены между несколькими процессорами для экономии времени выполнения. Мне это бесполезно.   -  person TheWhitestOfFangs    schedule 17.01.2018
comment
STL не поддерживает открытые поверхности. Для проверки попадания вам вообще не нужен ближайший треугольник или вершина, просто начните где-нибудь за пределами вашего bbox в направлении к центру любого треугольника, который не параллелен направлению (так что |dot(direction,triangle_normal)|>0.0)   -  person Spektre    schedule 17.01.2018

Ответы (1)


arrow_upward
0
arrow_downward

Проблема была решена с помощью вариации метода пересечения лучей. 1. Найдите ближайшую вершину, используя норму L2 (в квадрате). 2. Рассмотрим элементы, имеющие общую вершину. Рекомендуется иметь список подключений, а не сопоставлять их каждый раз. 3. Приведение луча проводится от точки интереса к центроиду первого элемента. 4. Отметьте среди элементов в ‹2>, которые пересекают луч, и выберите тот, который имеет наименьшее расстояние пересечения 5. Используйте скалярное произведение вектора пересечения с нормалью элемента (знак минус = снаружи, иначе внутри)

(Это было добавлено в сам вопрос)

person TheWhitestOfFangs    schedule 23.01.2018