Алгоритм Катмулла — Кларка — это техника, используемая в компьютерной графике для создания гладких поверхностей путём моделирования . Алгоритм разработали Эдвин Катмулл и Джеймс Кларк в 1978 как обобщение бикубических однородных B-сплайновых поверхностей для произвольной топологии . В 2005 году Эдвин Катмулл получил вместе с Тони Дероузом и за их разработки в области подразделения поверхностей.

Рекурсивные вычисления

Поверхности Катмулла — Кларка определяются рекурсивно, используя следующую схему последовательных уточнений :

Начинаем с сетки в виде произвольного многогранника . Все вершины этой сетки будем называть исходными точками.

• Для каждой грани добавляем точку грани
  • Выбираем в качестве точки грани среднее всех исходных точек соответствующей грани .
• Для каждого ребра добавляем точку ребра .
  • Выбираем в качестве точки ребра среднее из двух соседних точек грани и двух исходных конечных точек ребра .
• Для каждой точки грани , добавим ребро для каждого ребра грани, соединяя точку грани с точкой ребра для грани.
• Для каждой исходной точки P берём среднее F для всех n (вновь созданных) точек граней для граней, касающихся P , и берём среднее R всех n точек рёбер для (исходных) рёбер, касающихся P , где середина каждого ребра является средним двух конечных вершин (не путать с новыми «точками рёбер», определёнными выше). Переносим каждую исходную точку в точку

${\displaystyle {\frac {F+2R+(n-3)P}{n}}.}$

Эта точка является барицентром точек P , R и F с весами ( n − 3), 2 и 1.

• Соединяем каждую новую точку с новыми точками рёбер всех исходных рёбер, инцидентных исходной вершине.
• Определяем новые грани, заключённые новыми рёбрами.

Новая сетка состоит только из четырёхугольников , которые, вообще говоря, не находятся в одной плоскости . Новая сетка, в общем случае, будет выглядеть более гладко, чем исходная.

Повторное подразбиение приводит к более гладкой сетке. Можно показать, что предельная поверхность, полученная этим методом, по меньшей мере принадлежит классу ${\displaystyle {\mathcal {C}}^{1}}$ в особых точках и ${\displaystyle {\mathcal {C}}^{2}}$ во всех остальных местах (здесь n означает число непрерывных производных, когда мы говорим о ${\displaystyle {\mathcal {C}}^{n}}$ ). После итерации число особых точек на поверхности не изменяется.

Формулу для барицентра Катмулл и Кларк выбрали, исходя из эстетических, а не математических, соображений, хотя Катмулл и Кларк приложили большие усилия, чтобы строго доказать, что метод сходится к бикубическим B-сплайновым поверхностям .

Точные вычисления

Результирующая подразделённая поверхность Катмулла — Кларка может быть получена прямо без последовательных улучшений. Это можно сделать с помощью техники . Этот метод переформулирует процесс последовательных приближений в задачу вычисления экспоненты матрицы , которую можно решить путём диагонализации матрицы .

Программное обеспечение, использующее подразделение поверхностей методом Катмулла — Кларка

Примечания

Литература

Литература для дальнейшего чтения

• Derose T., Kass M., Truong T. Subdivision surfaces in character animation // . — 1998. — С. 85. — ISBN 0897919998 . — doi : .
• Loop C., Schaefer S. // ACM Transactions on Graphics. — 2008. — Т. 27 . — С. 1 . — doi : .
• Kovacs D., Mitchell J., Drone S., Zorin D. // IEEE Transactions on Visualization and Computer Graphics. — 2010. — Т. 16 , вып. 5 . — С. 742 . — doi : . — .
• Matthias Nießner, Charles Loop, Mark Meyer, Tony DeRose. // ACM Transactions on Graphics. — 2012. — Январь ( т. 31 , вып. 1 ). — doi : . ,
• Nießner Matthias, Loop Charles, Greiner Günther. // Eurographics 2012 Annex: Short Papers (Eurographics 2012, Cagliary). — 2012. — С. pp 41—44 .
• Wade Brainerd. (неопр.) . Видеоролик с докладом, доступен также документ
• Doo D., Sabin M. // Computer-Aided Design. — 1978. — Т. 10 , вып. 6 . — doi : .