Данная работа посвящена исследованию существующих алгоритмов построения иерархий ограничивающих объемов и их возможных расширений, реализации и оптимизации выбранного подхода, а также сравнительному анализу результатов производительности алгоритма бросания лучей на построенной иерархии с изначальным алгоритмом и имеющимися на рынке решениями. В качестве основной демонстрационной сцены была выбрана модель Crytek Sponza, широко используемая в компьютерной графике для демонстрации различных графических технологий и возможностей, но для объективной оценки результатов приводятся также метрики для других трехмерных моделей. Исходный код проекта написан на языке C++ с использованием графического API DirectX 11 в совокупности с языком программирования шейдеров HLSL. Наиболее значимым результатом является новый алгоритм "SAHFS" для вставок примитивов, используемый на одном из этапов стохастического алгоритма построения иерархии ограничивающих объемов. Представленный подход демонстрирует прирост вплоть до 35% по скорости нахождения листа для вставки и прирост до 25% в качестве результирующей иерархии. Все предложенные оптимизации соответствуют изначальной цели стохастического алгоритма: ускорению имеющихся качественных алгоритмов построения BVH без значительных потерь в качестве. Итоговый алгоритм может быть использован в графических приложениях, в том числе, реального времени, использующих трассировку лучей.

This work is devoted to the study of existing algorithms for constructing bounding volume hierarchies and their possible extensions, implementation and optimization of the chosen approach, as well as a comparative analysis of the performance results of the ray casting algorithm on the constructed hierarchy with the original algorithm and solutions available on the market. The Crytek Sponza model, widely used in computer graphics to demonstrate various graphics technologies and capabilities, was chosen as the main demo scene, but metrics for other 3D models are also provided to objectively evaluate the results. The project’s source code is written in C++ using the DirectX 11 graphics API in conjunction with the HLSL shader programming language. The most significant result is a new method, called "SAHFS for inserting primitives, used at one of the stages of the stochastic algorithm for constructing a bounding volume hierarchy. This approach demonstrates an increase of up to 35% in the speed of finding a leaf to insert and an increase of up to 25% in the quality of the resulting hierarchy. All proposed optimizations correspond to the original goal of the stochastic algorithm: speeding up existing high-quality top-down BVH construction algorithms without significant losses in quality. The resulting algorithm can be used in graphical applications, including real-time, that use ray tracing.

• Построение иерархий ограничивающих объемов для алгоритмов трассировки лучей
  • Введение
  • 1. Постановка задачи
  • 2. Обзор существующих решений
  • 3. Разработка собственного алгоритма
  • 4. Результаты и их анализ
  • Заключение
  • Список использованных источников