Пересечение Ray-mesh или реализация дерева AABB в C++ с небольшими накладными расходами?

Question

Можете ли вы порекомендовать меня...

• либо проверенная легковесная реализация дерева AABB на C / C++?
• или, альтернативно, другая эффективная структура данных, плюс легкая реализация C / C++, для решения проблемы пересечения большого количества лучей с большим количеством треугольников?

"Большое число" означает несколько сотен тысяч для лучей и треугольников.

Мне известно, что деревья AABB являются частью библиотеки CGAL и, возможно, библиотек физики игр, таких как Bullet. Однако я не хочу накладных расходов на огромную дополнительную библиотеку в моем проекте. В идеале, я хотел бы использовать небольшую шаблонную реализацию только для заголовков. Я также хотел бы получить что-то с кучей файлов CPP, если они легко интегрируются в мой проект. Зависимость от boost в порядке

Да, я гуглил, но безуспешно.

Я должен упомянуть, что мой контекст приложения - обработка сетки, а не рендеринг. Короче говоря, я переношу топологию эталонной сетки на геометрию сетки из трехмерного сканирования. Я снимаю лучи из вершин и по нормали эталонной сетки в направлении 3D-сканирования, и мне нужно восстановить пересечение этих лучей со сканированием.

редактировать

Несколько ответов / комментариев указывали на структуры данных ближайшего соседа. Я создал небольшую иллюстрацию, касающуюся проблем, возникающих при приближении к пересечению лучей с помощью методов ближайших соседей. Методы ближайших соседей могут использоваться в качестве эвристики, которая работает во многих случаях, но я не уверен, что они действительно решают проблему систематически, как это делают деревья AABB.

Answer 1

Хотя этот код немного староват и использует 3DS Max SDK, он дает довольно хорошую систему деревьев для деформаций столкновений объектов в C++. Не могу с первого взгляда сказать, является ли это Quad-деревом, AABB-деревом или даже OBB-деревом (комментарии тоже немного скудны).

http://www.max3dstuff.com/max4/objectDeform/help.html

Это потребует перевода Макса на вашу собственную систему, но это может стоить усилий.

Answer 2

Если нет требований в реальном времени, я бы сначала попробовал грубую силу.

Тесты 1M * 1M ray-> треугольник не должны занимать намного больше нескольких минут (в CPU).

Если это проблема, вторым лучшим решением будет ограничение области поиска путем вычисления графа / отношения смежности между треугольниками / полигонами в целевой сетке. После того, как первоначальное предположение не удалось, можно попробовать соседние треугольники. Это, конечно, зависит от отсутствия самоокклюзии / множественных очков жизни. (я думаю, что это одна из интерпретаций "видимость не относится к этой проблеме").

Также в зависимости от того, насколько патологичны топологии, можно попробовать сопоставить среду целевой сетки на единичном кубе (каждый пиксель будет состоять из проецируемого на него списка треугольников) и проверить первоначального кандидата с помощью одного луча ->aabb test + lookup,

Учитывая обратную связь, существует еще один простой вариант - разбиение пространства на простую трехмерную сетку, где каждое измерение может быть подразделено гистограммой местоположений x/y/z или даже регулярно.

• Сетка 100x100x100 имеет очень управляемый размер 1e6 записей
• максимальное количество посещаемых кубиков пропорционально диаметру (максимум 300)

• Есть ~60000 крайних клеток, что предполагает порядка 10 треугольников на клетку

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

Answer 3

Попробуйте библиотеку ANN: http://www.cs.umd.edu/~mount/ANN/

Это "Приблизительные ближайшие соседи". Я знаю, что вы ищете что-то немного другое, но вот как вы можете использовать это для ускорения обработки ваших данных:

1. Точки подачи в ANN.
2. Запросите выбираемый пользователем радиус (представьте, что это "ручка на сетку") вокруг каждой вершины, из которой вы хотите произвести лучевое наведение, и найдите вершины сетки, находящиеся в пределах диапазона.
3. Выберите только те треугольники, которые находятся в этом диапазоне, и проследите лучи вдоль нормали, чтобы найти нужный.

Разумно выбирая радиус поиска, вы определенно получите значительное ускорение без ущерба для точности.