Пространственные структуры и ускорение
Наивный тест «луч против каждого треугольника» или «каждый объект против каждого» быстро становится узким местом. Пространственные структуры группируют геометрию так, чтобы отбрасывать целые регионы одной проверкой.
Пространственные структуры и ускорение
Ограничивающие объёмы
★ 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 и аналогах.
См. также
Другие статьи этого же раздела в боковом меню (как на странице "О разделе"). Компьютерная графика — дисциплина, занимающаяся созданием, обработкой, анализом и визуализацией изображений с использованием вычислительных средств. Растровая графика - изображение как сетка пикселей, разрешение, цвет и компромиссы качества и объёма данных. Векторная графика — это способ представления изображений, при котором визуальное содержимое описывается не как набор цветных точек (пикселей), а как совокупность геометрических примитивов: точек. Трёхмерная графика — это область вычислительной техники, посвящённая созданию, обработке и отображению визуальных объектов, обладающих глубиной, объёмом и пространственной структурой. Blender — установка, настройка, обзор разделов официального руководства и основные рабочие процессы 3D. Цифровая графика существует в двух основных формах: растровой и векторной. Растровые изображения состоят из сетки пикселей, каждый из которых имеет свой цвет. Пересечения, hit-test и отсечение примитивов по окну — алгоритмы, которые связывают векторную геометрию с пиксельным выводом и UI. Как 3D-сцена превращается в картинку без «сквозных» полигонов — culling, z-buffer, алгоритм художника, порталы и PVS. Современный конвейер OpenGL 3.3 — окно, VBO/VAO, GLSL, текстуры и типовые эффекты real-time графики. Сжатая шпаргалка по разделу "Компьютерная графика" — растр, вектор, 3D, рендер и куда читать дальше. Вопросы по разделу "Компьютерная графика" с подсказкой, в какой статье искать ответ.Основы компьютерной графики
Растровая графика
Векторная графика
D-графика и анимация
Blender
Алгоритмы растеризации
D-геометрия и отсечение
Видимость и буфер глубины
OpenGL и шейдеры
Итоги
Чек-лист самопроверки