mesh разбиение и быстрый поиск

Question

Я пишу raytracer, и я пытаюсь разбить некоторые данные сетки (точки и грани), поэтому я могу рассчитать пересечения.

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

Что такое хорошая структура данных для хранения данных графа (kd tree? Равнораздельное пространство?) Как я могу найти соответствующие пространства/грани с учетом луча?

PS: Им с помощью C++

Answer 1

пространственной структуры разбиения данных (на BSP дерево, к-D дерева или октодерева), или даже в более общем случае иерархии ограничивающий объем (AABB дерево) должен делать эту работу. См. this answer к соответствующему вопросу о построении дерева BSP из сетки и ее обхода. Библиотека C++ CGAL предоставляет структуру данных дерева AABB с требуемой конструкцией и запросом.