Материал конференции: "Труды Международной конференции по компьютерной графике и зрению "Графикон" (19-21 сентября 2023 г., Москва)"
Авторы:Лысых А.И., Кинев И.Е., Жданов Д.Д.
Оптимизация многоуровневой ускоряющей структуры пространственного разбиения хеш-таблиц и kd-дерева
Аннотация:
Производится анализ существующих типов ускоряющих структур пространственного разбиения. Рассматриваются свойства и особенности исходной комбинированной структуры пространственного разбиения, построенной на основе хеш-таблиц и kd-дерева. Выделяются три типа случаев применения структуры: динамический, сбалансированный и статический. Предлагаются методы оптимизации алгоритмов построения структур и поиска ячеек. Для трёх типов применения структуры предлагаются алгоритмы определения размера и уровней расположения хеш-таблиц. Производится анализ оптимальных значений параметров этих алгоритмов для каждого из случаев применения. Выполняется сравнение и анализ эффективности модифицированной структуры с исходной комбинированной структурой и kd-деревом. Сравнение показало, что полученная структура может значительно повысить эффективность поиска ячеек для рассмотренных типов применения структуры.
Ключевые слова:
Структуры пространственного разбиения, оптимизация, рендеринг, фотонные карты, трассировка лучей
