геометрия — пересечение Ray-mesh или реализация дерева AABB в C ++ с небольшими накладными расходами?
Можете ли вы порекомендовать меня …
- либо проверенная легковесная реализация дерева AABB на C / C ++?
- или, альтернативно, другая эффективная структура данных, плюс легкая реализация C / C ++, для решения проблемы пересечения большого количества лучей с большим количеством треугольников?
«Большое число» означает несколько сотен тысяч лучей и треугольников.
Я знаю, что деревья AABB являются частью библиотеки CGAL и, возможно, библиотек физики игры, таких как Bullet. Однако я не хочу накладных расходов на огромную дополнительную библиотеку в моем проекте. В идеале я хотел бы использовать небольшую шаблонную реализацию только для заголовков. Я также хотел бы получить что-то с кучей файлов CPP, если они легко интегрируются в мой проект. Зависимость от boost в порядке
Да, я гуглил, но безуспешно.
Я должен отметить, что мой контекст приложения это обработка сетки, а не рендеринг. Короче говоря, я переношу топологию эталонной сетки на геометрию сетки из трехмерного сканирования. Я снимаю лучи из вершин и по нормали эталонной сетки к 3D-сканированию, и мне нужно восстановить пересечение этих лучей со сканированием.
редактировать
Несколько ответов / комментариев указывали на структуры данных ближайшего соседа. Я создал небольшую иллюстрацию, касающуюся проблем, возникающих при пересечении сетки лучей методами ближайшего соседа. Методы ближайших соседей могут использоваться в качестве эвристики, которая работает во многих случаях, но я не уверен, что они действительно решают проблему систематически, как это делают деревья AABB.
Решение
Попробуйте библиотеку ANN:
http://www.cs.umd.edu/~mount/ANN/
Это «Приблизительные ближайшие соседи». Я знаю, вы ищете что-то немного другое, но вот как вы можете использовать это для ускорения обработки ваших данных:
- Точки подачи в ANN.
- Запросите выбираемый пользователем радиус (думайте об этом как «ручку на сетку») вокруг каждой вершины, из которой вы хотите отбрасывать лучи, и найдите вершины сетки, которые находятся в пределах диапазона.
- Выберите только те треугольники, которые находятся в пределах этого диапазона, и проследите лучи вдоль нормали, чтобы найти нужный.
Разумно выбирая радиус поиска, вы определенно получите значительное ускорение без ущерба для точности.
Другие решения
Если нет требований в реальном времени, я бы сначала попробовал грубую силу.
Тесты 1M * 1M ray-> треугольник не должны занимать намного больше, чем несколько минут (в CPU).
Если это проблема, то вторым лучшим решением будет ограничение области поиска путем вычисления графа / отношения смежности между треугольниками / полигонами в целевой сетке. После того, как первоначальное предположение не удалось, можно попробовать соседние треугольники. Это, конечно, зависит от отсутствия самоокклюзии / множественных хитпоинтов. (я думаю, что это одна из интерпретаций «видимость не относится к этой проблеме»).
Также, в зависимости от того, насколько патологичны топологии, можно попробовать сопоставить окружение целевой сетки на единичном кубе (каждый пиксель будет состоять из проецируемого на него списка треугольников) и проверить первоначального кандидата с помощью одного луча -> aabb test + lookup ,
Учитывая обратную связь, существует еще один простой вариант — разбиение пространства на простую трехмерную сетку, где каждое измерение может быть подразделено гистограммой местоположений x / y / z или даже регулярно.
- Сетка 100х100х100 очень управляемый размер 1e6 записей
- максимальное количество посещаемых кубиков пропорционально диаметру (максимум 300)
-
Есть ~ 60000 крайних клеток, что предполагает порядка 10 треугольников на клетку
-
предостережения: треугольники должны быть размещены на каждой клетке, которую они занимают
— консервативный алгоритм помещает их в ячейки, к которым они не принадлежат; большие треугольники, вероятно, потребуют отсечения и повторной сборки.
Хотя этот код немного староват и использует 3DS Max SDK, он дает довольно хорошую систему деревьев для деформаций столкновений объектов в C ++. Не могу с первого взгляда определить, является ли это Quad-деревом, AABB-деревом или даже OBB-деревом (комментарии тоже немного скудны).
http://www.max3dstuff.com/max4/objectDeform/help.html
Это потребует перевода Макса на вашу собственную систему, но это может стоить усилий.