Изогнутая кривая, полученная из грубой полигональной сетки.
В области 3D-компьютерной графики поверхность подразделения (обычно сокращаемая до поверхности SubD или Subsurf ) — это изогнутая поверхность , представленная спецификацией более крупной полигональной сетки и созданная рекурсивным алгоритмическим методом. Искривленная поверхность, лежащая в основе внутренняя сетка , [1] может быть рассчитана на основе грубой сетки, известной как контрольная клетка или внешняя сетка , как функциональный предел итерационного процесса разделения каждой многоугольной грани на более мелкие грани, которые лучше аппроксимируют конечный результат. подлежащая изогнутая поверхность. Реже для добавления геометрии в сетку используется простой алгоритм путем разделения граней на более мелкие без изменения общей формы или объема.
Противоположным является уменьшение полигонов или их разделение. [2]
Обзор
Алгоритм подразделения поверхности является рекурсивным по своей природе. Процесс начинается с создания полигональной сетки базового уровня. Затем к этой сетке применяется схема уточнения . Этот процесс берет эту сетку и разделяет ее, создавая новые вершины и новые грани. Положения новых вершин в сетке вычисляются на основе положений близлежащих старых вершин, ребер и/или граней. Во многих схемах уточнения также изменяются положения старых вершин (возможно, на основе положений новых вершин).
Этот процесс создает более плотную сетку, чем исходная, содержащую больше полигональных граней (часто в 4 раза). Полученную сетку можно снова и снова пропускать через одну и ту же схему уточнения для получения все более и более уточненных сеток. Каждую итерацию часто называют уровнем подразделения , начиная с нуля (до того, как произойдет какое-либо уточнение).
Предельная поверхность подразделения — это поверхность, полученная в результате этого процесса, итеративно применяемая бесконечное количество раз . Однако на практике этот алгоритм применяется лишь ограниченное и довольно небольшое ( ) количество раз.
Математически окрестность необыкновенной вершины (нечетырехвалентного узла для четырехкратно уточненных сеток) поверхности подразделения представляет собой сплайн с параметрически особой точкой . [3]
Схемы доработки
Схемы уточнения поверхности подразделения можно условно разделить на две категории: интерполирующие и аппроксимирующие .
Интерполяционные схемы необходимы для соответствия исходному положению вершин исходной сетки.
Аппроксимирующих схем нет; они могут и будут корректировать эти позиции по мере необходимости.
В целом аппроксимирующие схемы имеют большую плавность, но у пользователя меньше возможностей общего контроля над результатом. Это аналогично сплайновым поверхностям и кривым, где кривые Безье необходимы для интерполяции определенных контрольных точек, тогда как B-сплайны этого не делают (и являются более приблизительными).
Схемы разделения поверхностей также можно классифицировать по типу многоугольника, с которым они работают: некоторые лучше всего работают для четырехугольников (четырехугольников), тогда как другие в основном работают с треугольниками (трис).
Аппроксимирующие схемы
Аппроксимация означает, что предельные поверхности аппроксимируют исходные сетки и что после подразделения вновь сгенерированные контрольные точки не попадают в предельные поверхности. [ нужны разъяснения ] Существует пять приблизительных схем подразделения:
Кэтмалл и Кларк (1978), Quads - обобщает вставку бикубического однородного узла B-сплайна . Для произвольных начальных сеток эта схема генерирует предельные поверхности, которые являются C 2 непрерывными везде, за исключением необыкновенных вершин, где они C 1 непрерывны (Peters and Reif 1998). [4]
Ду-Сабин (1978), Квадратики. Вторая схема подразделения была разработана Ду и Сабином, которые успешно распространили метод срезания углов Чайкина (Джордж Чайкин, 1974 [5] ) для кривых на поверхности. Они использовали аналитическое выражение биквадратичной однородной поверхности B-сплайна для создания процедуры подразделения для создания предельных поверхностей C 1 с произвольной топологией для произвольных начальных сеток. Вспомогательная точка может улучшить форму подразделения Ду-Сабин. [6] После подразделения все вершины имеют валентность 4. [7]
Loop (1987), Triangles – Loop предложил свою схему подразделения, основанную на квадратном сплайне из шести векторов направления, чтобы обеспечить правило для генерации непрерывных предельных поверхностей C 2 везде, за исключением необыкновенных вершин, где они являются непрерывными C 1 (Zorin 1997).
Схема подразделения среднего края (1997–1999 гг.). Схема подразделения среднего края была независимо предложена Петерсом-Рейфом (1997) [8] и Хабибом-Уорреном (1999). [9] Первый вариант использовал середину каждого края для построения новой сетки. Последний для построения схемы использовал четырехнаправленный коробчатый сплайн . Эта схема генерирует C 1 непрерывные предельные поверхности на исходных сетках произвольной топологии. (Подразделение Mid-Edge, которое можно было бы назвать «подразделением √2», поскольку два шага сокращают расстояние вдвое, можно считать самым медленным.)
Схема подразделения √3 (2000), Треугольники. Эта схема была разработана Коббелтом [10] и предлагает несколько интересных функций: она обрабатывает произвольные треугольные сетки, она C 2 непрерывна везде, за исключением необыкновенных вершин, где она C 1 непрерывна и предлагает естественная адаптивная доработка, когда это необходимо. Он обладает как минимум двумя особенностями: это двойная схема для треугольных сеток и более медленная скорость уточнения, чем у основных.
Схемы подразделения
Интерполяционные схемы
После разделения контрольные точки исходной сетки и вновь созданные контрольные точки интерполируются на предельной поверхности. Самой ранней работой была так называемая «схема бабочки» Дина, Левина и Грегори (1990), которые расширили четырехточечную интерполяционную схему подразделения кривых до схемы подразделения поверхности. Зорин, Шредер и Свелденс (1996) заметили, что схема «бабочка» не может создавать гладкие поверхности для неправильных треугольных сеток, и поэтому модифицировали эту схему. Коббелт (1996) далее обобщил четырехточечную интерполяционную схему подразделения кривых до схемы подразделения тензорного произведения для поверхностей. В 1991 году Насри предложил схему интерполяции Ду-Сабина; [11] в то время как в 1993 году Холстед, Касс и ДеРоуз предложили один вариант для Кэтмалл-Кларка. [12]
Бабочка (1990), Треугольники - названы в честь формы схемы.
Модифицированная бабочка (1996), Quads [13] - предназначена для устранения артефактов, возникающих из-за нерегулярной топологии.
Коббелт (1996), Квады - вариационный метод подразделения, который пытается преодолеть недостатки равномерного подразделения.
^ Дж. Петерс и У. Рейф: Поверхности подразделения , серия Springer, монография «Геометрия и вычисления» 3, 2008, doi
^ Дж. Питерс и У. Рейф: Анализ обобщенных алгоритмов подразделения B-сплайнов , SIAM J of Numer. Анальный. 32 (2) 1998, с.728-748
^ «Кривые Чайкина в обработке».
^ К. Карчаускас и Дж. Петерс: Биквадратичные поверхности подразделения C 1 , дополненные точками , Графические модели, 77, стр.18-26 [1]
^ Джой, Кен (1996–2000). «ДУ-САБИН ПОВЕРХНОСТИ» (PDF) . Онлайн-заметки по геометрическому моделированию – через Калифорнийский университет в Дэвисе.
^ Дж. Питерс и У. Рейф: Простейшая схема подразделения для сглаживания многогранников , Транзакции ACM в графике 16 (4) (октябрь 1997 г.), стр. 420-431, doi
^ А. Хабиб и Дж. Уоррен: Вставка ребер и вершин для класса поверхностей подразделения C 1 , Компьютерное геометрическое проектирование 16 (4) (май 1999 г.), стр. 223-247, doi
^ Л. Коббелт: √3-подразделение , 27-я ежегодная конференция по компьютерной графике и интерактивным методам, doi
^ Насри, А.Х. Поверхностная интерполяция на нерегулярных сетях с нормальными условиями. Компьютерное геометрическое проектирование 8 (1991), 89–96.
^ Холстед М., Касс М. и ДеРоуз Т. Эффективная и справедливая интерполяция с использованием поверхностей Катмулла-Кларка. В материалах по компьютерной графике (1993), серии ежегодных конференций, ACM Siggraph.
^ Зорин, Денис; Шредер, Питер; Свелденс, Вим (1996). «Интерполяционное подразделение сеток с произвольной топологией» (PDF) . Департамент компьютерных наук, Калифорнийский технологический институт, Пасадена, Калифорния 91125 .
^ Ульрих Рейф. 1995. Единый подход к алгоритмам подразделения вблизи необыкновенных вершин. Компьютерное геометрическое проектирование . 12(2)153–174
^
Джос Стам, «Точная оценка поверхностей подразделения Катмулла-Кларка при произвольных значениях параметров», Труды SIGGRAPH'98. В материалах по компьютерной графике, ACM SIGGRAPH, 1998, 395–404.
Внешние ссылки
Игра Джери: получившая «Оскар» анимация от Pixar , завершенная в 1997 году, в которой были представлены поверхности подразделения с использованием подразделения Кэтмулла-Кларка (наряду с симуляцией ткани).
Учебное пособие «Подраздел моделирования и анимации», конспекты курса SIGGRAPH 1999 г.
Учебное пособие «Подраздел моделирования и анимации», примечания к курсу SIGGRAPH 2000
Единый подход к алгоритмам подразделения вблизи необыкновенных вершин, Ульрих Райф (Computer Aided Geometric Design 12(2):153–174, март 1995 г.)
Подразделение поверхностных и объемных сеток, программное обеспечение для разделения поверхностей с использованием самых популярных схем.
Методы подразделения поверхности в CGAL, библиотеке алгоритмов вычислительной геометрии