Catmull-Clark

Catmull-Clark — это итеративный алгоритм подразделения (subdivision surface) для создания гладких поверхностей из многогранных сеток (полигональных мешей). Алгоритм был разработан Эдвином Кэтмуллом и Джеймсом Кларком в 1978 году и является одним из наиболее распространённых методов в компьютерной графике для моделирования трёхмерных объектов с плавными формами.

История

Алгоритм Catmull-Clark был впервые описан в статье «Recursively generated B-spline surfaces on arbitrary topological meshes», опубликованной в 1978 году. На момент разработки Кэтмулл работал в Нью-Йоркском технологическом институте, а Кларк — в Калифорнийском университете в Беркли. Идея заключалась в обобщении метода подразделения поверхностей, ранее применявшегося только для регулярных (четырёхугольных) сеток, на произвольные топологии, включая треугольные и многоугольные грани.

Алгоритм стал основой для многих последующих методов подразделения, таких как Loop (для треугольных сеток) и Doo-Sabin. В 1990-х годах Catmull-Clark был принят в индустрии компьютерной анимации, в частности, в студии Pixar (где Кэтмулл был сооснователем), для создания персонажей и объектов в фильмах, таких как «История игрушек» (1995) и «Корпорация монстров» (2001). В 2019 году Кэтмулл и Кларк получили премию «Оскар» за научно-технические достижения за разработку алгоритма.

Принцип работы

Алгоритм Catmull-Clark преобразует исходную полигональную сетку в более гладкую поверхность путём многократного применения набора правил. Каждая итерация (называемая «шагом подразделения») увеличивает количество вершин, рёбер и граней, приближая форму к предельной гладкой поверхности (B-сплайну). Алгоритм работает с сетками произвольной топологии, включая нерегулярные (с вершинами, где сходится не четыре ребра).

Шаги подразделения

1. Вычисление новых точек для граней (face points): Для каждой грани вычисляется среднее арифметическое всех её вершин. Полученная точка становится новой вершиной, связанной с центром грани.
2. Вычисление новых точек для рёбер (edge points): Для каждого ребра вычисляется среднее арифметическое двух его концевых вершин и двух точек граней, смежных с этим ребром. Если ребро является граничным (имеет только одну смежную грань), используется только среднее концевых вершин.
3. Обновление исходных вершин (vertex points): Для каждой исходной вершины вычисляется новая позиция по формуле:

• \( Q \) — среднее точек граней, смежных с вершиной.
• \( R \) — среднее точек рёбер, инцидентных вершине.
• \( S \) — исходная вершина.
• \( n \) — количество рёбер (или граней), сходящихся в вершине.
• Новая позиция: \( \frac{Q}{n} + \frac{2R}{n} + \frac{S(n-3)}{n} \).

1. Построение новых граней: Каждая исходная грань заменяется на \( n \) новых четырёхугольных граней, где \( n \) — количество её сторон. Новые грани соединяют точки граней, точки рёбер и обновлённые вершины.

После одного шага подразделения все грани становятся четырёхугольными (квадратными), что упрощает дальнейшие вычисления. Повторение шагов приводит к сглаживанию поверхности.

Свойства

• Предельная поверхность: При бесконечном числе итераций алгоритм сходится к поверхности, которая является кубическим B-сплайном (C²-непрерывной) в большинстве точек, за исключением так называемых «экстраординарных вершин» (где сходится не четыре ребра), где непрерывность снижается до C¹.
• Локальность: Каждый шаг подразделения использует только локальную информацию (соседние вершины, рёбра и грани), что позволяет эффективно реализовывать алгоритм на параллельных вычислительных системах.
• Адаптивность: Алгоритм может быть применён к части сетки, оставляя остальные области неизменными, что используется для экономии вычислительных ресурсов.

Применение

Catmull-Clark широко используется в трёхмерной компьютерной графике, анимации и промышленном дизайне. Основные области применения:

• Создание персонажей и органических объектов: В программах для 3D-моделирования, таких как Blender, Autodesk Maya, 3ds Max, Cinema 4D, алгоритм позволяет моделировать плавные формы из низкополигональных сеток.
• Промышленный дизайн: Для проектирования корпусов автомобилей, бытовой техники, мебели и других объектов с гладкими поверхностями.
• Игровая индустрия: В реальном времени (например, в Unreal Engine или Unity) алгоритм используется для создания уровней детализации (LOD), где низкополигональные модели сглаживаются на лету.
• Научная визуализация: Для представления сложных геометрических форм, таких как молекулы или анатомические структуры.

Реализации

Алгоритм Catmull-Clark реализован в большинстве коммерческих и открытых 3D-пакетов. В Blender, например, он доступен как модификатор «Subdivision Surface» (тип «Catmull-Clark»). В библиотеках компьютерной графики, таких как OpenSubdiv (разработанная компанией Pixar), алгоритм оптимизирован для GPU-ускорения.

Критика и ограничения

• Вычислительная сложность: При большом числе итераций количество вершин растёт экспоненциально, что может потребовать значительных ресурсов памяти и процессора.
• Артефакты: Вблизи экстраординарных вершин могут возникать визуальные искажения (например, «вмятины» или «шишки»), особенно при агрессивном сглаживании.
• Непригодность для треугольных сеток: Хотя алгоритм работает с треугольными гранями, он преобразует их в четырёхугольные, что может быть нежелательно в некоторых контекстах (например, в игровых движках, где предпочтительны треугольники).
• Отсутствие контроля над формой: В отличие от NURBS, Catmull-Clark не предоставляет точного управления кривизной поверхности, что ограничивает его применение в точном машиностроении.

Источники

• Catmull, E., Clark, J. «Recursively generated B-spline surfaces on arbitrary topological meshes» (1978).
• DeRose, T., Kass, M., Truong, T. «Subdivision surfaces in character animation» (1998).
• Pixar. «OpenSubdiv: A library for subdivision surfaces» (документация).
• Blender Foundation. «Modifiers: Subdivision Surface» (документация Blender).