Пространственные структуры и ускорение
Наивный тест "луч против каждого треугольника" или "каждый объект против каждого" быстро становится узким местом. Пространственные структуры группируют геометрию так, чтобы отбрасывать целые регионы одной проверкой.
Отсечение по окну в 2D — 2D-геометрия и отсечение.
Z-buffer и порядок отрисовки — Видимость и буфер глубины.
RTX/BVH в играх — 3D-графика и анимация.
Пространственные структуры и ускорение
Ограничивающие объёмы
★ AABB (Axis-Aligned Bounding Box) — прямоугольный параллелепипед с гранями параллельно осям. Пересечение луч–AABB сводится к отсечению параметра t по трём парам плоскостей (slab method).
★ OBB (Oriented Bounding Box) — тот же box, но повёрнут вместе с объектом; точнее облегает модель, проверка дороже.
★ Сфера — дешёвый тест расстояния; часто bounding sphere вокруг меша.
★ k-DOP — выпуклая оболочка несколькими парами параллельных плоскостей; компромисс между AABB и OBB.
Сначала проверяют дешёвый bound; только при попадании спускаются к геометрии.
Иерархии и деревья
| Структура | Идея | Типичное применение |
|---|---|---|
| BVH | Дерево вложенных AABB/OBB | Ray tracing, DXR/Vulkan RT, коллизии |
| Octree | Рекурсивное деление куба на 8 частей | Объёмные данные, voxel, loose octree в играх |
| kD-tree | Разбиение плоскостями по осям | Точки, photon maps, offline RT |
| BSP | Двоичное разбиение пространства плоскостями | Indoor-уровни, порядок отрисовки |
| R-tree | Группировка перекрывающихся AABB | GIS, индексы объектов на карте |
| Uniform grid | Равномерная сетка ячеек | Частицы, простые 2D/3D сцены |
Иерархия ограничивающих тел — несколько уровней bounds (группа → объект → часть меша), что совпадает с иерархией сцены в движке.
Луч–треугольник и луч–OBB
Пересечение луча O + t·d с треугольником решают через барицентрические координаты или плоскость треугольника + проверку u,v ≥ 0, u+v ≤ 1. Для OBB переходят в локальную систему box и применяют slab test.
В трассировке после попадания в лист BVH вызывают точный тест; без дерева миллионы треугольников неподъёмны даже на GPU.
Когда что выбирать
- Динамика редкая, много статики — BVH перестраивают или refit.
- Комнаты и коридоры — BSP + порталы.
- Открытый мир, равномерное распределение — grid или loose octree.
- Геоданные — R-tree в PostGIS и аналогах.