Введение
Техника в 3D компьютерной графике
Алгоритм Кэтмулла — Кларка — это техника, используемая в 3D компьютерной графике для создания криволинейных поверхностей с помощью моделирования поверхностей подразделения. Он был разработан Эдвином Кэтмуллом и Джимом Кларком в 1978 году как обобщение бикубических однородных B-сплайнов на произвольную топологию. Начните с сетки произвольного многогранника. Все вершины этой сетки называются исходными точками. Для каждой грани добавьте точку грани. Установите, чтобы каждая точка грани была средним значением всех исходных точек соответствующей грани. Для каждого ребра добавьте точку ребра. Для каждой исходной точки (P) вычислите среднее значение (F) всех n (недавно созданных) точек грани для граней, примыкающих к P, и среднее значение (R) всех n средних точек ребер для исходных ребер, примыкающих к P, где каждая средняя точка ребра является средним значением двух его конечных вершин (не путать с новыми точками ребер, указанными выше). (Обратите внимание, что с точки зрения вершины P, количество ребер, примыкающих к P, также равно количеству прилегающих граней, следовательно, n). Переместите каждую исходную точку в новую вершинную точку (это барицентр P, R и F с соответствующими весами (n − 3), 2 и 1). Сформируйте ребра и грани в новой сетке. Соедините каждую новую точку грани с новыми точками ребер всех исходных ребер, определяющих исходную грань. Соедините каждую новую вершинную точку с новыми точками ребер всех исходных ребер, инцидентных исходной вершине. Определите новые грани как области, ограниченные ребрами.
Set each face point to be the average of all original points for the respective face
For each edge, add an edge point. Set each edge point to be the average of the two neighbouring face points (A,F) and the two endpoints of the edge (M,E)
For each original point (P), take the average (F) of all n (recently created) face points for faces touching P, and take the average (R) of all n edge midpoints for original edges touching P, where each edge midpoint is the average of its two endpoint vertices (not to be confused with new edge points above). (Note that from the perspective of a vertex P, the number of edges neighboring P is also the number of adjacent faces, hence n)
Move each original point to the new vertex point (This is the barycenter of P, R and F with respective weights (n − 3), 2 and 1)
Form edges and faces in the new mesh
Connect each new face point to the new edge points of all original edges defining the original face
Connect each new vertex point to the new edge points of all original edges incident on the original vertex
Define new faces as enclosed by edges
Свойства
Новая сетка будет состоять только из четырехугольников, которые, как правило, не будут плоскими. Новая сетка будет выглядеть "гладче" (то есть менее "зазубренной" или "острой"), чем старая сетка. Повторное подразделение приводит к сеткам, которые становятся все более округлыми. Произвольная формула для вычисления барицентра была выбрана Кэтмуллом и Кларком на основе эстетичного вида получаемых поверхностей, а не на основе математического вывода, хотя они приложили значительные усилия, чтобы строго доказать, что метод сходится к бикубическим B-сплайнам. Этот метод переформулирует процесс рекурсивного уточнения в задачу матричного экспоненциального представления, которую можно решить напрямую посредством диагонализации матрицы.