Катмулла-Кларк алгоритм является методом , используемым в 3D компьютерной графике для создания криволинейных поверхностей, используя разделение поверхности моделирования . Он был разработан Эдвином Катмаллом и Джимом Кларком в 1978 году как обобщение бикубических однородных B-сплайновых поверхностей на произвольную топологию . [1]
В 2005 году Эдвин Катмулл вместе с Тони ДеРоузом и Джосом Стамом получил премию Американской киноакадемии за технические достижения за изобретение и применение поверхностей разделения. ДеРоуз писал об «эффективной, справедливой интерполяции» и анимации персонажей. Стам описал метод прямого вычисления предельной поверхности без рекурсии.
Рекурсивная оценка
Поверхности Катмулла – Кларка определяются рекурсивно с использованием следующей схемы уточнения. [1]
Начнем с сетки произвольного многогранника . Все вершины этой сетки будем называть исходными точками .
- Для каждого лица добавьте точку лица
- Задайте для каждой точки лица среднее значение всех исходных точек для соответствующего лица.
- Задайте для каждой точки лица среднее значение всех исходных точек для соответствующего лица.
- Для каждого края добавьте крайнюю точку .
- Задайте для каждой точки края среднее значение двух соседних точек грани и двух исходных конечных точек.
- Задайте для каждой точки края среднее значение двух соседних точек грани и двух исходных конечных точек.
- Для каждой исходной точки ( P) возьмите среднее значение ( F) всех n (недавно созданных) точек лица для граней, соприкасающихся с P , и возьмите среднее значение (R) всех n средних точек кромок для исходных кромок, соприкасающихся с P , где каждая средняя точка кромки - это среднее значение двух его конечных вершин (не путать с новыми краевыми точками выше). (Обратите внимание, что с точки зрения вершины P количество ребер, соседних с P , также является количеством смежных граней, следовательно, n )
- Переместите каждую исходную точку в новую точку вершины (Это барицентр из P , R и F с соответствующими весами ( п - 3), 2 и 1)
- Переместите каждую исходную точку в новую точку вершины (Это барицентр из P , R и F с соответствующими весами ( п - 3), 2 и 1)
- Сформируйте края и грани в новой сетке
- Соедините каждую новую точку грани с новыми точками кромок всех исходных кромок, определяющих исходную грань.
- Соедините каждую новую точку вершины с новыми точками ребер всех исходных ребер, инцидентных исходной вершине.
- Определите новые грани как ограниченные ребрами
- Соедините каждую новую точку грани с новыми точками кромок всех исходных кромок, определяющих исходную грань.
Характеристики
Новая сетка будет состоять только из четырехугольников , которые, как правило, не будут плоскими . Новая сетка обычно будет выглядеть «более гладкой» (т.е. менее «зазубренной» или «заостренной»), чем старая сетка. Повторное подразделение приводит к тому, что сетки становятся все более и более округлыми.
Формула барицентра произвольного вида была выбрана Катмаллом и Кларком на основе эстетического вида получаемых поверхностей, а не математического вывода , хотя они действительно идут на многое, чтобы неукоснительно показать, что метод сходится к бикубическим B-сплайновым поверхностям. [1]
Можно показать, что предельная поверхность, полученная с помощью этого процесса уточнения, не меньше в необычных вершинах и везде (когда n указывает, сколько производных непрерывны , мы говорим о преемственность ). После одной итерации количество необычных точек на поверхности остается постоянным.
Точная оценка
Предельная поверхность поверхностей подразделения Катмулла – Кларка также может быть вычислена напрямую, без каких-либо рекурсивных уточнений. Этого можно добиться с помощью техники Йоса Стама (1998). [2] Этот метод переформулирует процесс рекурсивного уточнения в матричную экспоненциальную задачу, которая может быть решена напрямую посредством диагонализации матрицы .
Программное обеспечение с использованием алгоритма
- 3ds Max
- 3D-пальто
- AC3D
- Anim8or
- AutoCAD
- Блендер [3]
- Каррара
- CATIA (Вообрази и форма)
- CGAL
- Cheetah3D
- Cinema4D
- Clara.io
- Creo (Фристайл) [4]
- Студия Даз, 2.0
- DeleD Community Edition
- DeleD Designer
- Джелато
- Молоток
- Шестиугольник
- Гудини
- LightWave 3D, версия 9
- Makehuman
- майя
- Метасеквойя
- MODO
- Грязевой ящик
- Надстройка Power Surfacing для SolidWorks
- OpenSubdiv Pixar [5] [6] [7] [8] [9]
- PRMan
- Realsoft3D
- Ремо 3D
- Оттенок
- Rhinoceros 3D - плагин Grasshopper 3D - плагин Weaverbird
- Силос
- SketchUp - требуется плагин.
- Softimage XSI
- Страта 3D CX
- Крылья 3D
- Zbrush
Смотрите также
- Обозначение многогранника Конвея - набор связанных топологических операторов многогранника и многоугольной сетки.
- Подразделение поверхности Ду-Сабина
- Поверхность подразделения петли
Рекомендации
- ^ a b c Катмелл, Э .; Кларк, Дж. (1978). «Рекурсивно генерируемые B-сплайновые поверхности на произвольных топологических сетках» (PDF) . Компьютерный дизайн . 10 (6): 350. DOI : 10,1016 / 0010-4485 (78) 90110-0 .
- ^ Стам, Дж. (1998). «Точная оценка поверхностей подразделения Катмулла-Кларка при произвольных значениях параметров» (PDF) . Материалы 25-й ежегодной конференции по компьютерной графике и интерактивным технологиям - SIGGRAPH '98 . С. 395–404 . CiteSeerX 10.1.1.20.7798 . DOI : 10.1145 / 280814.280945 . ISBN 978-0-89791-999-9.
- ^ «Модификатор Subdivision Surface» . 2020-01-15.
- ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 23 ноября 2016 года . Проверено 4 декабря 2016 .CS1 maint: заархивированная копия как заголовок ( ссылка )
- ^ Мануэль Кремер (2014). «OpenSubdiv: взаимодействие вычислений и рисования на GPU». У Мартина Ватта; Эрвин Куманс; Джордж ЭльКура; и другие. (ред.). Многопоточность для визуальных эффектов . CRC Press. С. 163–199. ISBN 978-1-4822-4356-7.
- ^ https://www.youtube.com/watch?v=xFZazwvYc5o
- ^ «Pixar's OpenSubdiv V2: подробный обзор» . 2013-09-18.
- ^ http://on-demand.gputechconf.com/gtc/2014/video/S4856-subdivision-surfaces-industry-standard.mp4
- ^ https://www.youtube.com/watch?v=dzIl_S-qHIQ
дальнейшее чтение
- Derose, T .; Касс, М .; Чыонг, Т. (1998). «Подразделение поверхностей в персонажной анимации» (PDF) . Материалы 25-й ежегодной конференции по компьютерной графике и интерактивным технологиям - SIGGRAPH '98 . С. 85 . CiteSeerX 10.1.1.679.1198 . DOI : 10.1145 / 280814.280826 . ISBN 978-0897919999.
- Петля, Ц .; Шефер, С. (2008). «Аппроксимация поверхностей разделения Катмулла-Кларка бикубическими пятнами» (PDF) . Транзакции ACM на графике . 27 : 1–11. CiteSeerX 10.1.1.153.2047 . DOI : 10.1145 / 1330511.1330519 .
- Ковач, Д .; Mitchell, J .; Drone, S .; Зорин, Д. (2010). «Приближенное разделение поверхностей со смещениями, построенное в реальном времени» (PDF) . IEEE Transactions по визуализации и компьютерной графике . 16 (5): 742–51. DOI : 10.1109 / TVCG.2010.31 . PMID 20616390 . препринт
- Маттиас Нисснер, Чарльз Луп, Марк Мейер, Тони ДеРоуз, « Feature Adaptive GPU Rendering of Catmull-Clark Subdivision Surfaces », ACM Transactions on Graphics Volume 31, выпуск 1, январь 2012 г., doi : 10.1145 / 2077341.2077347 , демонстрация
- Нисснер, Матиас; Петля, Чарльз; Грейнер, Гюнтер: Эффективная оценка полугладких складок на субдивных поверхностях Катмулла-Кларка : Приложение Eurographics 2012: Краткие статьи (Eurographics 2012, Cagliary). 2012, стр. 41–44.
- Уэйд Брейнерд, « Тесселяция в Call of Duty: Ghosts» также представлен в виде учебного пособия по SIGGRAPH2014 [1]
- Д. Ду и М. Сабин: Поведение рекурсивных поверхностей деления вблизи необычных точек , Компьютерное проектирование, 10 (6) 356–360 (1978), ( doi , pdf )