Тесселяция — понятие и виды¶
Тесселяция (от лат. tessella — «маленькая плитка», «кубик мозаики») — процесс покрытия плоскости или поверхности фигурами без зазоров и перекрытий, а также результат такого покрытия. Тесселяции делятся на правильные (из однотипных правильных многоугольников), неправильные (из правильных многоугольников с разным числом сторон) и полуправильные (ареоны) — комбинации двух и более правильных многоугольников. Тесселяциями также называют текстуры, наложенные на поверхность 3D-модели, и технологию автоматического разбиения сложной поверхности на примитивы в компьютерной графике.
¶История
Плиточные покрытия пола и стен известны с глубокой античности: мозаики Древней Греции, Рима, Пергама, Византии и исламских стран строились по принципу тесселяции. Систематическое изучение правильных тесселяций плоскости связано с именами математиков XIX века. В 1885 году немецкий математик Аксель Торстен Хардт доказал, что правильных тесселяций плоскости ровно три — из равносторонних треугольников, квадратов и правильных шестиугольников. Классификацию полуправильных тесселяций (ареонов) провели в XIX веке Дж. Кей, Брахмагупта и другие исследователи; полный список из восьми ареонов был установлен в 1987 году.
Особое место занимает наследие голландского художника Маурица Корнелиса Эшера, который в 1936—1939 годах создал серию «Метаморфозы», демонстрирующую непрерывные переходы между различными тесселяциями. Эшер использовал работы математиков Джорджа Поя и Хейне Харекса, опубликованные в 1932 году, и разработал собственную систему классификации периодических тесселяций на основе «заместителей» — фигур, заменяющих узлы и рёбра обычной решётки.
¶Виды тесселяций
¶Правильные тесселяции
Правильная тесселяция строится из одного типа правильных многоугольников, причём в каждой вершине сходится одинаковое их число. Существует ровно три таких тесселяции:
| Фигура | Угол | Число фигур в вершине |
|---|---|---|
| Равносторонний треугольник | 60° | 6 |
| Квадрат | 90° | 4 |
| Правильный шестиугольник | 120° | 3 |
¶Неправильные тесселяции
Неправильные тесселяции допускают разное число сторон фигур в разных вершинах. Всего существует 81 тип неправильной тесселяции плоскости (по классификации Дэмиана Маклина, 2005).
¶Полуправильные тесселяции (ареоны)
Ареоны состоят из двух и более правильных многоугольников, причём в каждой вершине сходится одна и та же последовательность фигур. Всего известно восемь ареонов:
- 3.3.3.3.6 — из треугольников и шестиугольников
- 3.3.3.4.4 — из треугольников и квадратов
- 3.3.4.3.4 — из треугольников и квадратов
- 3.4.6.4 — из треугольников, квадратов и шестиугольников
- 3.6.3.6 — из треугольников и шестиугольников
- 3.12.12 — из треугольников и двенадцатиугольников
- 4.6.12 — из квадратов, шестиугольников и двенадцатиугольников
- 4.8.8 — из квадратов и восьмиугольников
¶Криволинейные тесселяции
Тесселяция не ограничена прямыми линиями: границы плиток могут быть произвольными кривыми. Такие тесселяции встречаются в природе — например, структура пчелиных сот (шестиугольная тесселяция), трещины высохшей глины, чешуя рептилий, кристаллические зерна в металлах.
¶Тесселяция в компьютерной графике
В компьютерной графике под тесселяцией понимают технологию автоматического разбиения пространственных примитивов (обычно треугольников) на более мелкие элементы с целью повышения детализации 3D-модели. Метод активно развивался с начала 2000-х годов и стал стандартной частью графических конвейеров.
¶Аппаратная поддержка
В 2010 году компания NVIDIA представила технологию DirectCompute 5.0, а в 2011 году в стандарте DirectX 11 появился аппаратный блок тесселяции (Tessellation Stage), включённый в конвейер Shader Model 5.0. Технология позволяет процессору отправлять в графическое ядро упрощённую модель, а видеокарте — автоматически увеличивать число полигонов в зависимости от расстояния до камеры и других параметров.
Ключевые компоненты конвейера тесселяции в DirectX 11:
- Hull Shader — вычисляет коэффициент детализации для каждого патча;
- Tessellator — генерирует новую геометрию;
- Domain Shader — преобразует координаты новых вершин.
В OpenGL аналогичная функциональность реализована расширениями ARB_tessellation_shader (введено в OpenGL 4.0), в Vulkan — через этапы tessellation control и tessellation evaluation шейдеров.
¶Применение
Тесселяция используется для:
- сглаживания силуэтов объектов на близком расстоянии;
- создания рельефов на поверхностях (каменные стены, булыжники, следы от колёс);
- процедурной анимации тканей, меха, растительности;
- генерации деталей ландшафта без ручного моделирования.
Технология получила широкое распространение в играх после выхода движков, поддерживающих DirectX 11, — например, в играх Crysis 2, Battlefield 3 и Metro: Last Night.
¶Тесселяция в математике
Математическая теория тесселяций связана с групповой теорией и геометрией. Любая периодическая тесселяция плоскости порождается симметрией — группой движений плоскости (поворотами, параллельными переносами и отражениями). Всего существует 17 групп плоских симметрий (wallpaper groups), и каждая периодическая тесселяция соответствует одной из них.
В неевклидовой геометрии тесселяции исследуются на гиперболической плоскости и сфере. На сфере правильные тесселяции существуют только для конечного числа случаев — например, проекция додекаэдра на сферу даёт тесселяцию из 12 пятиугольников.
Понятие тесселяции обобщается на пространства любой размерности: трёхмерная тесселяция (гексаэдральная) — это заполнение объёма многогранниками без зазоров. Известны, в частности, кубическая и тетраэдрально-октаэдральная тесселяции трёхмерного пространства.
¶Применение
- Архитектура и дизайн — облицовка фасадов, полов, бассейнов; фирменный стиль корпорации «МТС» построен на шестиугольной тесселяции.
- Биология — моделирование структуры клеток, кристаллов, чешуи.
- Материаловедение — описание границ зёрен в поликристаллах.
- Компьютерные игры и кинематограф — генерация детализированных моделей.
- Математическое искусство — работы Эшера, современные генеративные тесселяции.
¶Источники
- Голомазов И. М. «Тесселяции в компьютерной графике»
- Грюнбаум Б., Шепард Г. «Тиллинги и паттерны» (Tilings and Patterns, 1987)
- Эшер М. К. «Метаморфозы» и графические листы серии
- Microsoft DirectX 11 Specification — Tessellation Stage
- Статья «Tessellation» в Wolfram MathWorld