В области 3D компьютерной графики поверхность подразделения (обычно сокращается до SubD-поверхности или Subsurf ) — это криволинейная поверхность, представленная спецификацией более грубой полигональной сетки и созданная рекурсивным алгоритмическим методом. Криволинейная поверхность, лежащая в основе внутренняя сетка , [1] может быть рассчитана из грубой сетки, известной как контрольная клетка или внешняя сетка , как функциональный предел итеративного процесса подразделения каждой полигональной грани на меньшие грани, которые лучше приближают конечную лежащую в основе криволинейную поверхность. Реже используется простой алгоритм для добавления геометрии к сетке путем подразделения граней на более мелкие без изменения общей формы или объема.
Противоположным процессом является сокращение полигонов или ликвидация подразделения. [2]
Обзор
Простое деление куба до 3Конвейер тесселяции с использованием метода подразделения
Алгоритм поверхности подразделения по своей природе рекурсивен . Процесс начинается с полигональной сетки базового уровня. Затем к этой сетке применяется схема уточнения . Этот процесс берет эту сетку и подразделяет ее, создавая новые вершины и новые грани. Положения новых вершин в сетке вычисляются на основе положений соседних старых вершин, ребер и/или граней. Во многих схемах уточнения положения старых вершин также изменяются (возможно, на основе положений новых вершин).
Этот процесс создает более плотную сетку, чем исходная, содержащую больше полигональных граней (часто в 4 раза). Полученную сетку можно снова и снова пропускать через ту же схему уточнения, чтобы получать все более и более уточненные сетки. Каждую итерацию часто называют уровнем подразделения , начиная с нуля (до того, как произойдет какое-либо уточнение).
Поверхность предельного подразделения — это поверхность, полученная в результате итеративного применения этого процесса бесконечное количество раз. Однако на практике этот алгоритм применяется лишь ограниченное и довольно малое ( ) число раз.
Математически окрестность необычной вершины (не 4- валентный узел для квадратно-измельченных сеток) поверхности подразделения представляет собой сплайн с параметрически особой точкой . [3]
Схемы уточнения
Схемы уточнения поверхности подразделения можно в целом разделить на две категории: интерполяционные и аппроксимационные .
Для соответствия исходному положению вершин в исходной сетке необходимы интерполяционные схемы.
Приближенные схемы не являются таковыми; они могут и будут корректировать эти положения по мере необходимости.
В целом, аппроксимирующие схемы имеют большую гладкость, но у пользователя меньше общего контроля над результатом. Это аналогично сплайновым поверхностям и кривым, где кривые Безье требуются для интерполяции определенных контрольных точек, в то время как B-сплайны не требуются (и более аппроксимированы).
Схемы поверхностей подразделения также можно классифицировать по типу многоугольника, с которым они работают: некоторые из них лучше всего работают с четырехугольниками (quads), в то время как другие в основном работают с треугольниками (tris).
Приближенные схемы
Аппроксимация означает, что предельные поверхности аппроксимируют исходные сетки, и что после подразделения вновь созданные контрольные точки не находятся на предельных поверхностях. [ необходимо разъяснение ] Существует пять схем аппроксимации подразделения:
Catmull и Clark (1978), Quads – обобщает бикубическую однородную вставку узлов B-сплайна . Для произвольных начальных сеток эта схема генерирует предельные поверхности, которые являются C 2 непрерывными везде, за исключением экстраординарных вершин, где они являются C 1 непрерывными (Peters и Reif 1998). [4]
Ду-Сэбин (1978), Квадраты – Вторая схема подразделения была разработана Ду и Сабином, которые успешно расширили метод срезания углов Чайкина (Джордж Чайкин, 1974 [5] ) для кривых на поверхности. Они использовали аналитическое выражение биквадратичной однородной B-сплайновой поверхности для генерации своей процедуры подразделения для получения предельных поверхностей C 1 с произвольной топологией для произвольных начальных сеток. Вспомогательная точка может улучшить форму подразделения Ду-Сэбина. [6] После подразделения все вершины имеют валентность 4. [7]
Loop (1987), Треугольники – Loop предложил свою схему подразделения, основанную на сплайне четвертой степени из шести направляющих векторов, чтобы обеспечить правило для генерации предельных поверхностей непрерывности C2 везде, за исключением необычных вершин, где они непрерывны по классу C1 (Зорин, 1997).
Схема подразделения Mid-Edge (1997–1999) – Схема подразделения Mid-Edge была предложена независимо Петерсом-Райфом (1997) [8] и Хабибом-Уорреном (1999). [9] Первый использовал среднюю точку каждого края для построения новой сетки. Последний использовал четырехнаправленный сплайн-бокс для построения схемы. Эта схема генерирует непрерывные предельные поверхности C 1 на исходных сетках с произвольной топологией. (Подразделение Mid-Edge, которое можно было бы назвать «подразделением √2», поскольку два шага делят расстояния пополам, можно считать самым медленным.)
√3 subdivision scheme (2000), Triangles – Эта схема была разработана Kobbelt [10] и предлагает несколько интересных функций: она обрабатывает произвольные треугольные сетки, она C 2 непрерывна везде, кроме экстраординарных вершин, где она C 1 непрерывна, и она предлагает естественное адаптивное уточнение, когда это необходимо. Она демонстрирует по крайней мере две особенности: это двойная схема для треугольных сеток и она имеет более медленную скорость уточнения, чем первичные.
Схемы подразделения
Интерполирующие схемы
После подразделения контрольные точки исходной сетки и вновь созданные контрольные точки интерполируются на предельной поверхности. Самой ранней работой была так называемая «схема бабочки» Дина, Левина и Грегори (1990), которые расширили схему четырехточечного интерполяционного подразделения для кривых до схемы подразделения для поверхности. Зорин, Шредер и Свелденс (1996) заметили, что схема бабочки не может генерировать гладкие поверхности для нерегулярных треугольных сеток, и поэтому модифицировали эту схему. Коббельт (1996) далее обобщил схему четырехточечного интерполяционного подразделения для кривых до схемы подразделения тензорного произведения для поверхностей. В 1991 году Насри предложил схему для интерполяции Ду-Сэбина; [11] в то время как в 1993 году Холстед, Касс и ДеРоуз предложили схему для Кэтмулла-Кларка. [12]
Бабочка (1990), Треугольники – названы в честь формы схемы
^ "Subdivision Surfaces". nevercenter.com . Получено 19 января 2021 г. .
^ Blender: Уменьшение количества полигонов — простое объяснение
^ J. Peters и U. Reif: Subdivision Surfaces , серия Springer Geometry and Computing, монография 3, 2008, doi
^ J. Peters и U. Reif: Анализ обобщенных алгоритмов подразделения B-сплайнов , SIAM J of Numer. Anal. 32 (2) 1998, стр.728-748
^ «Кривые Чайкина в обработке».
^ К. Карчаускас и Дж. Петерс: Точечно-расширенные биквадратичные поверхности подразделения C 1 , Графические модели, 77, стр. 18-26 [1] [ постоянная мертвая ссылка ]
^ Джой, Кен (1996–2000). «DOO-SABIN SURFACES» (PDF) . Заметки по геометрическому моделированию в режиме онлайн – через UC Davis.
^ J. Peters и U. Reif: Простейшая схема подразделения для сглаживания многогранников , ACM Transactions on Graphics 16(4) (октябрь 1997) стр.420-431, doi
^ А. Хабиб и Дж. Уоррен: Вставка ребер и вершин для класса поверхностей подразделения C 1 , Computer Aided Geometric Design 16(4) (май 1999) стр. 223-247, doi
^ Л. Коббельт: √3-subdivision , 27-я ежегодная конференция по компьютерной графике и интерактивным технологиям, doi
^ Насри, AH Интерполяция поверхности на нерегулярных сетях с нормальными условиями. Computer Aided Geometric Design 8 (1991), 89–96.
^ Halstead, M., Kass, M., и DeRose, T. Эффективная, справедливая интерполяция с использованием поверхностей Catmull-Clark. В Computer Graphics Proceedings (1993), Annual Conference Series, ACM Siggraph
^ Зорин, Денис; Шрёдер, Питер; Свелденс, Вим (1996). "Интерполяционное подразделение для сеток с произвольной топологией" (PDF) . Кафедра компьютерных наук, Калифорнийский технологический институт, Пасадена, Калифорния 91125 .
^ Ульрих Рейф. 1995. Единый подход к алгоритмам подразделения вблизи необычных вершин. Computer Aided Geometric Design . 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, библиотеке алгоритмов вычислительной геометрии
.png/1280px-Cube_simple_subdivisions_(0-3).png)
