Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В области 3D компьютерной графики , A поверхность подразделения представляет собой изогнутая поверхность , представленная спецификацией более грубый полигональную сетку и производится с помощью рекурсивного метода алгоритмического. Криволинейная поверхность, лежащая в основе внутренняя сетка , [1] может быть вычислена из грубой сетки, известная как контрольная клетку или внешняя сетка , в качестве функционального предела итерационного процесса разделения каждого многоугольную лицана более мелкие грани, которые лучше соответствуют конечной основной криволинейной поверхности. Реже используется простой алгоритм для добавления геометрии к сетке путем разделения граней на более мелкие без изменения общей формы или объема.

Обзор [ править ]

Простое деление куба до 3

Алгоритм разбиения поверхности является рекурсивным по своей природе. Процесс начинается с полигональной сетки базового уровня. Схема уточнения затем применяются к этой сетке. Этот процесс берет эту сетку и разделяет ее, создавая новые вершины и новые грани. Положения новых вершин в сетке вычисляются на основе положений соседних старых вершин, ребер и / или граней. Во многих схемах уточнения позиции старых вершин также изменяются (возможно, в зависимости от позиций новых вершин).

Этот процесс создает более плотную сетку, чем исходная, с большим количеством полигональных граней (часто в 4 раза). Полученная сетка может снова и снова проходить через одну и ту же схему уточнения для создания все более и более точных сеток. Каждую итерацию часто называют уровнем подразделения , начиная с нуля (до того, как произойдет какое-либо уточнение).

Предел поверхность подразделения имеет поверхность получает из этого процесса итеративно будучи применены бесконечно много раз. Однако на практике этот алгоритм применяется ограниченное и довольно небольшое ( ) количество раз.

Математически, окрестность из необыкновенной вершины (не-4- валентного узла для четырехкресельных рафинированных меш) поверхности подразделения является сплайном с параметрический особой точкой . [2]

Схемы доработки [ править ]

Схемы уточнения поверхности подразделения можно в общих чертах разделить на две категории: интерполяционные и аппроксимирующие .

  • Схемы интерполяции требуются, чтобы соответствовать исходному положению вершин в исходной сетке.
  • Примерных схем нет; они могут и будут корректировать эти позиции по мере необходимости.

Как правило, аппроксимирующие схемы имеют большую плавность, но пользователь в меньшей степени контролирует результат. Это аналогично сплайновым поверхностям и кривым, где кривые Безье требуются для интерполяции определенных контрольных точек, а B-сплайны - нет (и являются более приближенными).

Схемы разбиения поверхностей также можно разделить на категории по типу многоугольника, с которым они работают: некоторые из них лучше всего подходят для четырехугольников (четырехугольников), а другие в основном работают с треугольниками (трис).

Примерные схемы [ править ]

Аппроксимация означает, что предельные поверхности аппроксимируют исходные сетки, и что после подразделения вновь сгенерированные контрольные точки не находятся на предельных поверхностях. [ требуется пояснение ] Существует пять приблизительных схем подразделения:

  • Catmull и Clark (1978), Quads - обобщает двухкубическую однородную B-сплайновую вставку узлов. Для произвольных начальных сеток эта схема генерирует предельные поверхности, непрерывные C 2 всюду, за исключением необычных вершин, где они непрерывны C 1 (Peters and Reif 1998). [3]
  • Ду-Сабин (1978), квадроциклы. Вторая схема подразделения была разработана Ду и Сабином, которые успешно распространили метод сечения углов Чайкина (Джордж Чайкин, 1974 [4] ) для кривых на поверхности. Они использовали аналитическое выражение биквадратичной однородной B-сплайновой поверхности, чтобы сгенерировать процедуру подразделения для создания предельных поверхностей C 1 с произвольной топологией для произвольных начальных сеток. Вспомогательная точка может улучшить форму подразделения Ду-Сабина. [5] После подразделения все вершины имеют валентность 4. [6]
  • Loop (1987), Triangles - Loop предложил свою схему подразделения, основанную на квадратичном сплайне шести векторов направлений, чтобы обеспечить правило для генерации непрерывных предельных поверхностей C 2 везде, кроме необычных вершин, где они непрерывны C 1 (Zorin 1997).
  • Схема разделения по середине (1997–1999). Схема разделения по середине была независимо предложена Петерс-Рейфом (1997) [7] и Хабибом-Уорреном (1999). [8] Первый использовал среднюю точку каждого ребра для построения новой сетки. Последний использовал четырехсторонний прямоугольный шлиц для построения схемы. Эта схема порождает C 1 непрерывных предельных поверхностей на исходных сетках с произвольной топологией. (Подразделение Mid-Edge, которое можно было бы назвать «делением √2», поскольку два шага уменьшают расстояние вдвое, можно считать самым медленным.)
  • √3 subdivision scheme (2000), Triangles - Эта схема была разработана Коббельтом [9] и предлагает несколько интересных функций: она обрабатывает произвольные треугольные сетки, она является непрерывной C 2 везде, кроме необычных вершин, где она непрерывна C 1, и предлагает естественная адаптивная доработка при необходимости. Он демонстрирует как минимум две особенности: это двойная схема для треугольных сеток, и она имеет более медленную скорость уточнения, чем основные.
Схемы подразделения
Ду – Сабин
Петля

Схемы интерполяции [ править ]

После подразделения контрольные точки исходной сетки и вновь сгенерированные контрольные точки интерполируются на предельной поверхности. Самой ранней работой была так называемая « схема бабочки » Дина, Левина и Грегори (1990), которые расширили схему четырехточечного интерполяционного подразделения для кривых до схемы подразделения для поверхности. Зорин, Шредер и Свелден (1996) заметили, что схема «бабочка» не может генерировать гладкие поверхности для нерегулярных треугольных сеток, и таким образом модифицировали эту схему. Коббельт (1996) далее обобщил схему четырехточечного интерполяционного деления для кривых на схему деления тензорного произведения для поверхностей. В 1991 году Насри предложил схему интерполяции Ду-Сабина; [10] в то время как в 1993 году Холстед, Касс и ДеРоуз предложили один для Катмалла-Кларка.[11]

  • Бабочка (1990), Треугольники - названа в честь формы схемы
  • Модифицированная бабочка (1996), Quads [12] - предназначена для устранения артефактов, возникающих из-за неправильной топологии.
  • Kobbelt (1996), Quads - метод вариационного подразделения, который пытается преодолеть недостатки равномерного подразделения

Ключевые события [ править ]

  • 1978: Поверхности подразделения были описаны Эдвином Кэтмаллом и Джимом Кларком (см. Поверхность подразделения Катмалла-Кларка ), а также Дэниелом Ду и Малкомом Сабином (см. Поверхности подразделения Ду-Сабина ).
  • 1995: Ульрих Райф решил, что поведение поверхности разбивается вблизи необычных вершин. [13]
  • 1998: Йос Стэм разработал метод точной оценки поверхностей подразделения Катмулла-Кларка при произвольных значениях параметров. [14]

См. Также [ править ]

  • Игра Джери (1997) - фильм Pixar, в котором впервые использовалось разделение поверхностей для изображения кожи человека.
  • Неоднородные рациональные B-сплайновые поверхности (NURBS) - еще один способ представления криволинейных поверхностей

Ссылки [ править ]

  1. ^ "Подразделение поверхностей" . nevercenter.com . Проверено 19 января 2021 .
  2. ^ J. Peters и U. Reif: Subdivision Surfaces , Springer series Geometry and Computing monograph 3, 2008, doi
  3. ^ J. Peters и U. Reif: Анализ обобщенных алгоритмов деления B-сплайнов , SIAM J. Numer. Анальный. 32 (2) 1998, стр.728-748.
  4. ^ "Кривые Чайкина в обработке" .
  5. ^ K. Karciauskas и J. Peters: Точечно -расширенные биквадратичные поверхности подразделения C 1 , Графические модели, 77, стр.18-26 [1]
  6. ^ Джой, Кен (1996–2000). "ПОВЕРХНОСТИ DOO-SABIN" (PDF) . Заметки о геометрическом моделировании в режиме онлайн - через UC Davis. CS1 maint: date format (link)
  7. ^ J. Peters и U. Reif: простейшая схема подразделения для сглаживания многогранников , ACM Transactions on Graphics 16 (4) (октябрь 1997 г.) p.420-431, doi
  8. ^ А. Хабиб и Дж. Уоррен: Вставка ребер и вершин для класса поверхностей подразделения C 1 , Computer Aided Geometric Design 16 (4) (May 1999) p.223-247, doi
  9. ^ Л. Коббельт: √3-подразделение , 27-я ежегодная конференция по компьютерной графике и интерактивным методам, doi
  10. ^ Насри, AH Поверхностная интерполяция на нерегулярных сетях с нормальными условиями. Компьютерный геометрический дизайн 8 (1991), 89–96.
  11. ^ Холстед, М., Касс, М., и ДеРоуз, Т. Эффективная и точная интерполяция с использованием поверхностей catmullclark. In Computer Graphics Proceedings (1993), Annual Conference Series, ACM Siggraph, стр.
  12. ^ Зорин, Денис; Шредер, Питер; Свелденс, Вим (1996). «Интерполированное подразделение для сеток с произвольной топологией» (PDF) . Департамент компьютерных наук Калифорнийского технологического института, Пасадена, Калифорния 91125 .
  13. ^ Ульрих Райф. 1995. Единый подход к алгоритмам разделения около необычных вершин. Компьютерный геометрический дизайн. 12 (2) 153-174
  14. ^ Jos Stam, "Точная оценка поверхностей подразделения Catmull-Clark при произвольных значениях параметров", Proceedings of SIGGRAPH'98. In Computer Graphics Proceedings, ACM SIGGRAPH, 1998, 395-404.

Внешние ссылки [ править ]

  • Игра Джери  : получившая «Оскар» анимация от Pixar, завершенная в 1997 году, представила разделение поверхностей с использованием подразделения Catmull-Clark (наряду с симуляцией ткани).
  • Подразделение по моделированию и анимации , примечания к курсу SIGGRAPH 1999
  • Подразделение по моделированию и анимации , примечания к курсу SIGGRAPH 2000
  • Единый подход к алгоритмам разделения около необычных вершин , Ульрих Райф (Computer Aided Geometric Design 12 (2): 153-174 March 1995)
  • Подразделение поверхностных и объемных сеток , программа для выполнения разбиения по наиболее популярным схемам.
  • Методы подразделения поверхности в CGAL, библиотеке алгоритмов вычислительной геометрии