Многогранники

Каждая 3D модель в игре, фильме или 3D-принтере-это mesh из вершин, рёбер и граней. Формула Эйлера гарантирует корректность топологии; Half-Edge-структура, на которой работают Blender, Maya и все современные DCC-инструменты.

• **3D игры:** ico-sphere, cube subdivision-стандартные примитивы на основе платоновых тел
• **Collision detection:** GJK algorithm работает с выпуклыми оболочками объектов
• **3D-печать slicing:** mesh обрабатывается через Half-Edge структуру для нахождения контуров срезов
• **Computational geometry:** scipy.spatial.ConvexHull-QuickHull под капотом

Предварительные знания

• Solid Geometry

Формула Эйлера

Формула Эйлера-топологический инвариант для выпуклых многогранников, связывающий число вершин, рёбер и граней.

**Формула Эйлера:** V − E + F = 2 где V-вершины, E-рёбра, F-грани. Пример: куб: V=8, E=12, F=6 → 8−12+6 = 2 ✓ **Обобщение (характеристика Эйлера):** χ = V − E + F = 2 − 2g, где g-род поверхности (число "ручек").

Платоновы тела

Платоновы тела-пять правильных выпуклых многогранников, у которых все грани-одинаковые правильные многоугольники. Доказано, что других не существует.

Sphere mesh в играх создают из икосаэдра путём subdivision: каждый треугольник делится на 4, новые вершины проецируются на сферу. Это даёт равномерное распределение точек.

Выпуклая оболочка

Выпуклая оболочка множества точек-наименьший выпуклый многогранник, содержащий все эти точки. Это базовая структура для collision detection и пространственных запросов.

**Алгоритмы в 3D:** - **Gift Wrapping (Jarvis):** O(nF), F-число граней. Прост в реализации. - **QuickHull:** O(n log n) в среднем-наиболее практичен. - **Incremental:** O(n log n)-добавляем точки по одной. **GJK (Gilbert-Johnson-Keerthi):** определяет пересечение двух выпуклых тел без явного построения оболочки.

Half-Edge структура данных

Half-Edge-стандартная структура данных для 3D mesh, позволяющая эффективно обходить соседние элементы (вершины, рёбра, грани) за O(1).

**Half-Edge:** каждое ребро делится на 2 "полурёбра" с противоположными направлениями. Каждый half-edge хранит: - `vertex`-вершина в начале - `face`-грань слева - `next`-следующий half-edge вдоль грани - `twin`-противоположное полуребро

Ключевые идеи

• **Эйлер:** V−E+F=2 для любого выпуклого многогранника-топологический инвариант
• **Платоновы тела:** ровно 5; икосаэдр-основа sphere mesh в 3D движках
• **Convex Hull:** QuickHull O(n log n)-базовый алгоритм пространственного поиска
• **Half-Edge:** локальный обход mesh за O(k)-стандарт 3D DCC и CAD инструментов

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

Многогранники-основа для тел вращения и вычислительной геометрии:

• Тела вращения — Сфера-предел икосаэдра при бесконечном subdivision
• Векторная геометрия — Нормали граней = векторные произведения рёбер
• Геометрия в CS — Convex hull-ключевой алгоритм вычислительной геометрии

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

• Докажите, что не существует правильного многогранника с шестиугольными гранями, используя формулу Эйлера.
• Почему GJK algorithm работает только с выпуклыми оболочками? Как обрабатывают невыпуклые объекты?
• В чём преимущество Half-Edge перед простым хранением списков вершин и граней (face-vertex mesh)?

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

• la-03-cross-product