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

Техника 3D компьютерной графики

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

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

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

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

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

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

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

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

    

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

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

    

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

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

    

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

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

    

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

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

    

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

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

    

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

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

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

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

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

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

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

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

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

Смотрите также

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

Рекомендации

1. Кэтмалл, Э .; Кларк, Дж. (1978). «Рекурсивно сгенерированные поверхности B-сплайна на произвольных топологических сетках» (PDF) . Системы автоматизированного проектирования . 10 (6): 350. дои : 10.1016/0010-4485(78)90110-0. S2CID  121149868.
2. "Поверхность подразделения Кэтмалла-Кларка - Розеттский кодекс" . Rosettacode.org . Проверено 13 января 2022 г.
3. Стэм, Дж. (1998). «Точная оценка поверхностей подразделения Катмулла-Кларка при произвольных значениях параметров» (PDF) . Материалы 25-й ежегодной конференции по компьютерной графике и интерактивным технологиям - SIGGRAPH '98. стр. 395–404. CiteSeerX 10.1.1.20.7798 . дои : 10.1145/280814.280945. ISBN  978-0-89791-999-9. S2CID  2771758.
4. «Модификатор поверхности подразделения» . 15 января 2020 г.
5. «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 23 ноября 2016 г. Проверено 4 декабря 2016 г.{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
6. Мануэль Кремер (2014). «OpenSubdiv: взаимодействие вычислений и рисования на графическом процессоре». В Мартине Ватте; Эрвин Куманс; Джордж Эль-Кура; и другие. (ред.). Многопоточность для визуальных эффектов . ЦРК Пресс. стр. 163–199. ISBN 978-1-4822-4356-7.
7. Знакомьтесь с экспертами: Pixar Animation Studios, Проект OpenSubdiv. YouTube . Архивировано из оригинала 11 декабря 2021 г.
8. «OpenSubdiv V2 от Pixar: подробный обзор» . 18 сентября 2013 г.
9. AV Media gputechconf.com
10. Демонстрация OpenSubdiv Blender. YouTube . Архивировано из оригинала 11 декабря 2021 г.

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

• Дероз, Т.; Касс, М.; Труонг, Т. (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. PMID  20616390. S2CID  17138394.препринт
• Маттиас Ниснер, Чарльз Луп, Марк Мейер, Тони ДеРоуз, «Функции адаптивного графического рендеринга поверхностей подразделения Катмулла-Кларка», ACM Transactions on Graphics, том 31, выпуск 1, январь 2012 г., doi : 10.1145/2077341.2077347, демо
• Ниснер, Матиас; Луп, Чарльз; Грейнер, Гюнтер: Эффективная оценка полугладких складок на поверхностях подразделения Катмулла-Кларка: Приложение Eurographics 2012: Короткие статьи (Eurographics 2012, Кальяри). 2012, стр. 41–44.
• Уэйд Брейнерд, «Тесселяция в Call of Duty: Ghosts», также представленная в виде руководства SIGGRAPH2014 [1]
• Д. Ду и М. Сабин: Поведение рекурсивных поверхностей деления вблизи необыкновенных точек , Компьютерное проектирование, 10 (6) 356–360 (1978), (doi, pdf)