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

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

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

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

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

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

  • Для каждой грани добавьте точку грани .
    • Установите каждую точку грани как среднее значение всех исходных точек для соответствующей грани.
      Точки лица (синие сферы)
  • Для каждого ребра добавьте краевую точку .
    • Установите каждую точку ребра как среднее значение двух соседних точек грани (A,F) и двух конечных точек ребра (M,E) [2] А + Ф + М + Э 4 {\displaystyle {\frac {A+F+M+E}{4}}}
      Краевые точки (пурпурные кубы)
  • Для каждой исходной точки ( P) возьмите среднее значение ( F) всех n (недавно созданных) точек граней для граней, касающихся P , и возьмите среднее значение (R) всех n средних точек ребер для исходных ребер, касающихся P , где каждая средняя точка ребра является средним значением двух ее конечных вершин (не путать с новыми точками ребер выше). (Обратите внимание, что с точки зрения вершины P количество ребер, соседних с P, также является количеством смежных граней, следовательно, n )
    • Переместить каждую исходную точку в новую вершину ( это барицентр P , R и F с соответствующими весами ( n − 3), 2 и 1) Ф + 2 Р + ( н − 3 ) П н {\displaystyle {\frac {F+2R+(n-3)P}{n}}}
      Новые вершинные точки (зеленые конусы)
  • Сформируйте ребра и грани в новой сетке
    • Соедините каждую новую точку грани с новыми краевыми точками всех исходных ребер, определяющих исходную грань.
      Новые ребра, 4 на каждую точку грани
    • Соедините каждую новую вершину с новыми граничными точками всех исходных ребер, инцидентных исходной вершине.
      3 новых ребра на вершину смещенных исходных вершин
    • Определить новые грани как замкнутые ребрами
      Финальные грани сетки

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

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

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

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

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

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

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

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

Ссылки

  1. ^ abc 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)
Взято с "https://en.wikipedia.org/w/index.php?title=Catmull–Clark_subdivision_surface&oldid=1245827311"