Алгоритм Кэтмелла — Кларка

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Первые три шага подразделения куба методом Кэтмелла — Кларка и предельная поверхность (внизу)

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

Рекурсивные вычисления[править | править код]

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

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

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

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

Повторное подразбиение приводит к более гладкой сетке. Можно показать, что предельная поверхность, полученная этим методом, по меньшей мере принадлежит классу в особых точках и во всех остальных местах (здесь n означает число непрерывных производных, когда мы говорим о ). После итерации число особых точек на поверхности не изменяется.

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

Точные вычисления[править | править код]

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

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

Примечания[править | править код]

Литература[править | править код]

Литература для дальнейшего чтения[править | править код]