Русская Википедия:Алгоритм Катмулла — Кларка
Алгоритм Катмулла — Кларка — это техника, используемая в компьютерной графике для создания гладких поверхностей путём моделирования Шаблон:Не переведено 5. Алгоритм разработали Эдвин Катмулл и Джеймс Кларк в 1978 как обобщение бикубических однородных B-сплайновых поверхностей для произвольной топологииШаблон:Sfn. В 2005 году Эдвин Катмулл получил Шаблон:Не переведено 5 вместе с Тони Дероузом и Шаблон:Не переведено 5 за их разработки в области подразделения поверхностей.
Рекурсивные вычисления
Поверхности Катмулла — Кларка определяются рекурсивно, используя следующую схему последовательных уточненийШаблон:Sfn:
Начинаем с сетки в виде произвольного многогранника. Все вершины этой сетки будем называть исходными точками.
- Для каждой грани добавляем точку грани
- Выбираем в качестве точки грани среднее всех исходных точек соответствующей грани.
- Для каждого ребра добавляем точку ребра.
- Выбираем в качестве точки ребра среднее из двух соседних точек грани и двух исходных конечных точек ребра.
- Для каждой точки грани, добавим ребро для каждого ребра грани, соединяя точку грани с точкой ребра для грани.
- Для каждой исходной точки P берём среднее F для всех n (вновь созданных) точек граней для граней, касающихся P, и берём среднее R всех n точек рёбер для (исходных) рёбер, касающихся P, где середина каждого ребра является средним двух конечных вершин (не путать с новыми «точками рёбер», определёнными выше). Переносим каждую исходную точку в точку
- <math>\frac{F + 2R + (n-3)P}{n}.</math>
- Эта точка является барицентром точек P, R и F с весами (n − 3), 2 и 1.
- Соединяем каждую новую точку с новыми точками рёбер всех исходных рёбер, инцидентных исходной вершине.
- Определяем новые грани, заключённые новыми рёбрами.
Новая сетка состоит только из четырёхугольников, которые, вообще говоря, не находятся в одной плоскости. Новая сетка, в общем случае, будет выглядеть более гладко, чем исходная.
Повторное подразбиение приводит к более гладкой сетке. Можно показать, что предельная поверхность, полученная этим методом, по меньшей мере принадлежит классу <math>\mathcal{C}^1</math> в особых точках и <math>\mathcal{C}^2</math> во всех остальных местах (здесь n означает число непрерывных производных, когда мы говорим о <math>\mathcal{C}^n</math>). После итерации число особых точек на поверхности не изменяется.
Формулу для барицентра Катмулл и Кларк выбрали, исходя из эстетических, а не математических, соображений, хотя Катмулл и Кларк приложили большие усилия, чтобы строго доказать, что метод сходится к бикубическим B-сплайновым поверхностямШаблон:Sfn.
Точные вычисления
Результирующая подразделённая поверхность Катмулла — Кларка может быть получена прямо без последовательных улучшений. Это можно сделать с помощью техники Шаблон:Не переведено 5Шаблон:Sfn. Этот метод переформулирует процесс последовательных приближений в задачу вычисления экспоненты матрицы, которую можно решить путём диагонализации матрицы.
Программное обеспечение, использующее подразделение поверхностей методом Катмулла — Кларка
- 3ds Max
- 3D-Coat
- Шаблон:Не переведено 5
- Шаблон:Не переведено 5
- AutoCAD
- Blender
- Шаблон:Не переведено 5
- CATIA
- Шаблон:Не переведено 5
- Шаблон:Не переведено 5
- Cinema 4D
- Шаблон:Не переведено 5
- Шаблон:Не переведено 5[1]
- DAZ Studio, 2.0
- Шаблон:Не переведено 5
- Hammer
- Шаблон:Не переведено 5
- Houdini
- K-3D
- LightWave 3D, version 9
- Шаблон:Не переведено 5
- Maya
- Шаблон:Не переведено 5
- MODO
- Mudbox
- Pixar's OpenSubdiv[2][3][4][5][6]
- PRMan
- Шаблон:Не переведено 5
- Шаблон:Не переведено 5
- Шаблон:Не переведено 5
- Rhinoceros 3D — Grasshopper 3D Plugin — Weaverbird Plugin
- Silo
- SketchUp — Требуется Plugin.
- Softimage XSI
- Шаблон:Не переведено 5
- Wings 3D
- Zbrush
Примечания
Литература
Литература для дальнейшего чтения
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья, Видеоролик
- Шаблон:Статья
- Шаблон:Cite web Видеоролик с докладом, доступен также PDF документ
- Шаблон:Статья