3D Вычислительная геометрия

Doom (1993) работал на 486-м процессоре без видеокарты - и рендерил трёхмерный мир в реальном времени. Секрет: BSP-дерево, построенное заранее, позволяло за O(n) определить порядок рисования. 3D геометрия - не просто математика, это фундамент компьютерной графики, физических симуляций и робототехники.

• **Игровые движки** (Unreal, Unity) - выпуклые оболочки и BSP для обнаружения коллизий
• **САПР-системы** - пересечение полупространств для CSG (Constructive Solid Geometry)
• **Роботехника** - планирование движений через препятствия в 3D-пространстве конфигураций
• **Физические симуляции** - GJK и EPA используют выпуклые оболочки для детекции столкновений

Convex Hull в 3D: алгоритм Quickhull

Выпуклая оболочка множества точек в 3D - наименьший выпуклый многогранник, содержащий все точки. В 2D это просто замкнутый контур. В 3D - набор треугольных граней. Quickhull - наиболее практичный алгоритм: O(n log n) в среднем, O(n²) в худшем, но на случайных данных работает превосходно.

**Нижняя оценка:** построение выпуклой оболочки n точек в 3D требует Ω(n log n) - это доказывается сведением к задаче сортировки. Quickhull достигает этой оценки на случайных данных.

Halfspace Intersection

Выпуклый многогранник можно описать двумя способами: как выпуклую оболочку набора точек (V-representation) или как пересечение полупространств (H-representation). Переход между ними - двойственность, лежащая в основе линейного программирования и многих геометрических алгоритмов.

**Двойственность точка-плоскость:** точке (a, b, c) в исходном пространстве соответствует плоскость z = ax + by - c в двойственном. Это делает convex hull и halfspace intersection зеркально симметричными задачами - алгоритм для одной автоматически решает другую.

Многогранники и формула Эйлера

Формула Эйлера - одна из фундаментальных теорем геометрии: V - E + F = 2 для любого выпуклого многогранника, где V - вершины, E - рёбра, F - грани. Леонард Эйлер доказал её в 1758 году. Эта формула ограничивает возможные формы многогранников и имеет следствия в алгоритмах.

**Теорема о верхней грани (Upper Bound Theorem):** выпуклая оболочка n точек в d-мерном пространстве имеет O(n^⌊d/2⌋) граней. В 3D это O(n) - практически линейно. В 4D уже O(n²) - именно поэтому 4D выпуклые оболочки используются в алгоритмах линейного программирования.

BSP-деревья в 3D

Binary Space Partitioning (BSP) - техника рекурсивного разбиения 3D-пространства плоскостями. BSP-дерево позволяет отсортировать геометрию от дальней к ближней за O(n) - без явной сортировки. Именно поэтому в 1990-е годы все 3D-игры (Doom, Quake) использовали BSP как основу рендеринга.

**Выбор разделяющей плоскости** - ключевая эвристика: хочется минимизировать число разрезаний полигонов. На практике используют SAH (Surface Area Heuristic) - выбирают плоскость, минимизирующую ожидаемое время трассировки луча. Современные игры перешли с BSP на BVH (Bounding Volume Hierarchy), но BSP остаётся актуальным в задачах видимости и CSG (Constructive Solid Geometry).

3D Вычислительная геометрия

• Quickhull 3D: O(n log n) среднем, строит начальный тетраэдр, добавляет наиболее удалённые точки через horizon ridge
• H-representation: выпуклый многогранник как пересечение полупространств Ax ≤ b, двойственно V-representation
• Формула Эйлера V - E + F = 2 для выпуклых многогранников, характеристика Эйлера обобщает на топологические поверхности
• Выпуклая оболочка n точек в 3D имеет O(n) граней в среднем (Upper Bound Theorem: O(n^⌊d/2⌋))
• BSP-дерево: рекурсивное разбиение пространства плоскостями, O(n) обход для Painter's Algorithm
• Выбор разделяющей плоскости в BSP - эвристика SAH, современная альтернатива - BVH

Связанные темы

3D геометрия расширяет алгоритмы из 2D и открывает специфические трёхмерные конструкции.

• Выпуклая оболочка в 2D — Двумерный аналог - Graham Scan и Jarvis March
• Триангуляция Делоне — 3D Delaunay-триангуляция тетраэдрами
• Триангуляция полигонов — Разбиение 2D полигонов как основа 3D меширования

Вопросы для размышления

• Почему выпуклая оболочка в 4D имеет O(n²) граней, тогда как в 3D только O(n)? Что это означает для алгоритмов линейного программирования?
• BSP-дерева предварительно строятся для статической геометрии. Почему они не подходят для динамических объектов и что использовалось вместо них?
• Формула Эйлера V - E + F = 2 верна для тора при χ = 0. Почему тор фундаментально отличается от сферы с точки зрения геометрии?

Связанные уроки

• la-06-transformations