Можете ли вы порекомендовать мне...
- либо проверенная легкая реализация C/C++ дерева AABB?
- или, как вариант, другую эффективную структуру данных, плюс легковесную реализацию на C/C++, чтобы решить проблему пересечения большого количества лучей с большим количеством треугольников?
«Большое число» означает несколько сотен тысяч как для лучей, так и для треугольников.
Я знаю, что деревья AABB являются частью библиотеки CGAL и, возможно, библиотек игровой физики, таких как Bullet. Однако мне не нужны накладные расходы на огромную дополнительную библиотеку в моем проекте. В идеале я хотел бы использовать небольшую реализацию шаблона только для заголовка плавающего типа. Я бы также выбрал что-то с кучей файлов CPP, если они легко интегрируются в мой проект. Зависимость от boost в порядке.
Да, я гуглил, но безуспешно.
Я должен упомянуть, что мой контекст приложения — это обработка сетки, а не рендеринг. В двух словах, я переношу топологию эталонной сетки в геометрию сетки из 3D-скана. Я стреляю лучами из вершин и по нормалям эталонной сетки в сторону 3D-скана, и мне нужно восстановить пересечение этих лучей со сканом.
Изменить
Несколько ответов/комментариев указывали на структуры данных ближайшего соседа. Я создал небольшую иллюстрацию, касающуюся проблем, возникающих при подходе к пересечениям лучей и сетки с помощью методов ближайшего соседа. Методы ближайших соседей можно использовать в качестве эвристики, которая работает во многих случаях, но я не уверен, что они действительно систематически решают проблему, как это делают деревья AABB.
