Поверхность подразделения Кэтмулла – Кларка

Подразделение куба уровня 3 Кэтмалла – Кларка с предельной поверхностью подразделения, показанной ниже. (Обратите внимание: хотя кажется, что бикубическая интерполяция приближается к сфере , реальная сфера является квадрикой .)

Визуальная разница между сферой (зеленая) и поверхностью подразделения Кэтмулла-Кларка (пурпурная) от куба

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

В 2005 году Эдвин Кэтмалл вместе с Тони ДеРоузом и Джосом Стэмом получил премию Американской киноакадемии за технические достижения за изобретение и применение поверхностей разделения. ДеРоуз писал об «эффективной и справедливой интерполяции» и анимации персонажей. Стэм описал метод прямой оценки предельной поверхности без рекурсии.

Рекурсивная оценка

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

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

• Для каждого лица добавьте точку лица
  • Установите каждую точку грани как среднее значение всех исходных точек для соответствующей грани.

    

    Лицевые точки (синие сферы)

• Для каждого ребра добавьте точку ребра .
  • Установите каждую точку края как среднее значение двух соседних точек грани (A,F) и двух конечных точек края (M,E). ${\frac {A+F+M+E}{4}}$

    

    Краевые точки (пурпурные кубы)

• Для каждой исходной точки ( P) возьмите среднее значение ( F) всех n (недавно созданных) точек граней для граней, соприкасающихся с P , и возьмите среднее значение (R) всех n средних точек ребер для исходных ребер, соприкасающихся с P , где каждая средняя точка ребра является средним значением двух его конечных точек (не путать с новыми граничными точками, указанными выше). (Обратите внимание, что с точки зрения вершины P количество ребер, соседних с P, также является количеством соседних граней, следовательно, n )
  • Переместите каждую исходную точку в новую точку вершины. ${\frac {F+2R+(n-3)P}{n}}$ Это барицентр P ( , R и F с соответствующими весами ( n - 3), 2 и 1)

    

    Новые точки вершин (зеленые конусы)

• Сформируйте края и грани в новой сетке.
  • Соедините каждую новую точку грани с новыми точками ребер всех исходных ребер, определяющих исходную грань.

    

    Новые ребра, по 4 на каждую грань.

  • Соедините каждую новую точку вершины с новыми точками ребер всех исходных ребер, инцидентных исходной вершине.

    

    3 новых ребра на каждую вершину смещенных исходных вершин

  • Определите новые грани как окруженные краями

    

    Окончательные грани сетки

Характеристики

Новая сетка будет состоять только из четырехугольников , которые в целом не будут плоскими . Новая сетка обычно будет выглядеть «более гладкой» (то есть менее «зубчатой» или «заостренной»), чем старая. Повторное подразделение приводит к тому, что сетки становятся все более и более округлыми.

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

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

Точная оценка

Предельную поверхность поверхностей подразделения Катмулла – Кларка также можно вычислить напрямую, без какого-либо рекурсивного уточнения. Этого можно добиться с помощью техники Джоса Стама (1998). Этот метод переформулирует процесс рекурсивного уточнения в матричную экспоненциальную задачу, которую можно решить непосредственно посредством диагонализации матрицы .

Программное обеспечение, использующее алгоритм

• 3дс Макс
• 3D-Пальто
• AC3D
• Аним8ор
• Автокад
• Блендер
• Каррара
• CATIA (Представьте и сформируйте)
• КГАЛ
• Гепард3D
• Синема4Д
• Clara.io
• Я верю (фристайл)
• Даз Студия, 2.0
• ДелеД Сообщество Edition
• ДелеД Дизайнер
• Молоток
• Шестиугольник
• Гудини
• LightWave 3D, версия 9
• Сделать человеком
• Майя
• Метасеквойя
• СПОСОБ
• Грязевой ящик
• Надстройка Power Surfacing для SolidWorks
• от Pixar OpenSubdiv
• PRMan
• Реалсофт3D
• Remo 3D
• Оттенок
• Rhinoceros 3D - Плагин Grasshopper 3D - Плагин Weaverbird
• Силос
• SketchUp — требуется плагин.
• Софтимейдж XSI
• Слой 3D CX
• Крылья 3Д
• Збраш

См. также

• Обозначение многогранника Конвея - набор связанных операторов топологического многогранника и многоугольной сетки.
• Поверхность подразделения Ду-Сабина
• Поверхность разделения контура

Дальнейшее чтение

• Дероз, Т.; Касс, М.; Труонг, Т. (1998). «Поверхности подразделения в анимации персонажей» (PDF) . Материалы 25-й ежегодной конференции по компьютерной графике и интерактивным технологиям - SIGGRAPH '98 . стр. 85 . CiteSeerX   10.1.1.679.1198 . дои : 10.1145/280814.280826 . ISBN  978-0897919999 . S2CID   1221330 .
• Петля, К.; Шефер, С. (2008). «Аппроксимация поверхностей подразделения Катмулла-Кларка бикубическими участками» (PDF) . Транзакции ACM с графикой . 27 : 1–11. CiteSeerX   10.1.1.153.2047 . дои : 10.1145/1330511.1330519 . S2CID   6068564 .
• Ковач, Д.; Митчелл, Дж.; Дрон, С.; Зорин, Д. (2010). «Приблизительное разделение поверхностей со смещениями в режиме реального времени» (PDF) . Транзакции IEEE по визуализации и компьютерной графике . 16 (5): 742–51. дои : 10.1109/TVCG.2010.31 . ПМИД   20616390 . S2CID   17138394 . препринт
• Маттиас Ниснер, Чарльз Луп, Марк Мейер, Тони ДеРоуз, « Функциональная адаптивная визуализация с помощью графического процессора поверхностей подразделения Катмулла-Кларка », Транзакции ACM в графике, том 31, выпуск 1, январь 2012 г., два : 10.1145/2077341.2077347 , демо
• Ниснер, Матиас; Луп, Чарльз; Грейнер, Гюнтер: Эффективная оценка полугладких складок на поверхностях подразделения Катмулла-Кларка : Приложение Eurographics 2012: Короткие статьи (Eurographics 2012, Кальяри). 2012, стр. 41–44.
• Уэйд Брейнерд, «Тесселяция в Call of Duty: Ghosts», также представленная в виде руководства SIGGRAPH2014 [1]
• Д. Ду и М. Сабин: Поведение рекурсивных поверхностей деления вблизи необыкновенных точек , Компьютерное проектирование, 10 (6) 356–360 (1978), ( doi , pdf )