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

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

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

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

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

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

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

Поверхности Кэтмелла–Кларка определяются рекурсивно , используя следующую схему уточнения. ^[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] Этот метод переформулирует процесс рекурсивного уточнения в матричную экспоненциальную задачу, которая может быть решена напрямую с помощью матричной диагонализации .

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

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

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

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

Ссылки

1. Catmull, E. ; Clark, J. (1978). "Рекурсивно сгенерированные B-сплайновые поверхности на произвольных топологических сетках" (PDF) . Computer-Aided Design . 10 (6): 350. doi :10.1016/0010-4485(78)90110-0. S2CID  121149868.
2. "Поверхность подразделения Кэтмелла–Кларка - Rosetta Code". rosettacode.org . Получено 2022-01-13 .
3. Stam, J. (1998). "Точная оценка поверхностей подразделения Catmull-Clark при произвольных значениях параметров" (PDF) . Труды 25-й ежегодной конференции по компьютерной графике и интерактивным технологиям - SIGGRAPH '98. стр. 395–404. CiteSeerX 10.1.1.20.7798 . doi :10.1145/280814.280945. ISBN  978-0-89791-999-9. S2CID  2771758.
4. "Модификатор поверхности подразделения". 2020-01-15.
5. "Архивная копия" (PDF) . Архивировано из оригинала (PDF) 2016-11-23 . Получено 2016-12-04 .{{cite web}}: CS1 maint: архивная копия как заголовок ( ссылка )
6. Мануэль Крамер (2014). «OpenSubdiv: Interoperating GPU Compute and Drawing». В Martin Watt; Erwin Coumans; George ElKoura; et al. (ред.). Многопоточность для визуальных эффектов . CRC Press. стр. 163–199. ISBN 978-1-4822-4356-7.
7. Встречайте экспертов: Pixar Animation Studios, проект OpenSubdiv. YouTube . Архивировано из оригинала 2021-12-11.
8. "Pixar OpenSubdiv V2: Подробный взгляд". 2013-09-18.
9. AV-медиа gputechconf.com
10. OpenSubdiv Blender demo. YouTube . Архивировано из оригинала 2021-12-11.

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

• Derose, T.; Kass, M.; Truong, T. (1998). "Subdivision surfaces in character animation" (PDF) . Труды 25-й ежегодной конференции по компьютерной графике и интерактивным технологиям - SIGGRAPH '98. стр. 85. CiteSeerX  10.1.1.679.1198 . doi :10.1145/280814.280826. ISBN 978-0897919999. S2CID  1221330.
• Loop, C.; Schaefer, S. (2008). «Аппроксимация поверхностей подразделения Catmull-Clark с бикубическими заплатками» (PDF) . ACM Transactions on Graphics . 27 : 1–11. CiteSeerX  10.1.1.153.2047 . doi :10.1145/1330511.1330519. S2CID  6068564.
• Kovacs, D.; Mitchell, J.; Drone, S.; Zorin, D. (2010). "Real-Time Creased Approximate Subdivision Surfaces with Displacements" (PDF) . IEEE Transactions on Visualization and Computer Graphics . 16 (5): 742–51. doi :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]
• Д. Ду и М. Сабин: Поведение рекурсивных поверхностей деления вблизи экстраординарных точек , Computer-Aided Design, 10 (6) 356–360 (1978), (doi, pdf)