кривая Безье

Кривая, используемая в компьютерной графике и смежных областях.

Кубическая кривая Безье с четырьмя контрольными точками

Базисные функции в диапазоне t в [0,1] для кубических кривых Безье: синий: y = (1 − t ) ³ , зеленый: y = 3(1 − t ) ² t , красный: y = 3(1 − t ) t ² и голубой: y = t ³ .

Кривая Безье ( / ˈ b ɛ z . i . eɪ / BEH -zee-ay ) ^[1] — параметрическая кривая, используемая в компьютерной графике и смежных областях. ^[2] Набор дискретных «контрольных точек» определяет гладкую, непрерывную кривую с помощью формулы. Обычно кривая предназначена для аппроксимации реальной формы, которая в противном случае не имеет математического представления или представление которой неизвестно или слишком сложно. Кривая Безье названа в честь французского инженера Пьера Безье (1910–1999), который использовал ее в 1960-х годах для проектирования кривых для кузова автомобилей Renault . ^[3] Другие области применения включают проектирование компьютерных шрифтов и анимацию. ^[3] Кривые Безье можно объединить, чтобы сформировать сплайн Безье или обобщить до более высоких измерений, чтобы сформировать поверхности Безье . ^[3] Треугольник Безье является частным случаем последнего.

В векторной графике кривые Безье используются для моделирования плавных кривых, которые можно масштабировать до бесконечности. «Пути», как их обычно называют в программах обработки изображений, ^{[примечание 1]} представляют собой комбинации связанных кривых Безье. Пути не ограничены пределами растровых изображений и интуитивно понятны для изменения.

Кривые Безье также используются во временной области, в частности, в анимации , ^{[4] [примечание 2] дизайне} пользовательского интерфейса и сглаживании траектории курсора в интерфейсах, контролируемых взглядом. ^[5] Например, кривая Безье может использоваться для указания скорости с течением времени объекта, такого как значок, движущегося из точки A в точку B, а не просто перемещения с фиксированным числом пикселей за шаг. Когда аниматоры или дизайнеры интерфейсов говорят о «физике» или «ощущении» операции, они могут иметь в виду конкретную кривую Безье, используемую для управления скоростью с течением времени рассматриваемого перемещения.

Это также относится к робототехнике, где, например, движение сварочного манипулятора должно быть плавным, чтобы избежать ненужного износа.

Изобретение

Математическая основа кривых Безье — полиномы Бернштейна — была установлена ​​в 1912 году, но полиномы не применялись в графике до тех пор, пока примерно 50 лет спустя математик Поль де Кастельжо в 1959 году не разработал алгоритм де Кастельжо , численно устойчивый метод оценки кривых, и стал первым, кто применил их в автоматизированном проектировании во французском автопроизводителе Citroën . ^[6] Метод де Кастельжо был запатентован во Франции, но не публиковался до 1980-х годов ^[7] , в то время как полиномы Безье были широко распространены в 1960-х годах французским инженером Пьером Безье , который открыл их независимо и использовал для проектирования автомобильных кузовов в Renault .

Конкретные случаи

Кривая Безье определяется набором контрольных точек P 0 _через P n _, где n называется порядком кривой ( n = 1 для линейной, 2 для квадратичной, 3 для кубической и т. д.). Первая и последняя контрольные точки всегда являются конечными точками кривой; однако промежуточные контрольные точки обычно не лежат на кривой. Суммы в следующих разделах следует понимать как аффинные комбинации , то есть коэффициенты в сумме дают 1.

Линейные кривые Безье

При наличии различных точек P ₀ и P ₁ линейная кривая Безье — это просто линия между этими двумя точками. Кривая задается как

${\displaystyle \mathbf {B} (t)=\mathbf {P} _{0}+t(\mathbf {P} _{1}-\mathbf {P} _{0})=(1-t)\mathbf {P} _{0}+t\mathbf {P} _{1},\ 0\leq t\leq 1}$

Это самый простой способ, который эквивалентен линейной интерполяции . ^[8] Величина представляет собой вектор смещения от начальной точки до конечной точки. ${\displaystyle \mathbf {P} _{1}-\mathbf {P} _{0}}$

Квадратичные кривые Безье

Квадратичные кривые Безье в струнном искусстве : конечные точки ( • ) и контрольная точка ( × ) определяют квадратичную кривую Безье ( ⋯ ).

Квадратичная кривая Безье — это путь, проложенный функцией B ( t ) через точки P ₀ , P ₁ и P ₂ ,

${\displaystyle \mathbf {B} (t)=(1-t)[(1-t)\mathbf {P} _{0}+t\mathbf {P} _{1}]+t[(1-t)\mathbf {P} _{1}+t\mathbf {P} _{2}],\ 0\leq t\leq 1}$,

что можно интерпретировать как линейный интерполянт соответствующих точек на линейных кривых Безье от P ₀ до P ₁ и от P ₁ до P ₂ соответственно. Перестановка предыдущего уравнения дает:

${\displaystyle \mathbf {B} (t)=(1-t)^{2}\mathbf {P} _{0}+2(1-t)t\mathbf {P} _{1}+t^{2}\mathbf {P} _{2},\ 0\leq t\leq 1.}$

Это можно записать таким образом, чтобы подчеркнуть симметрию относительно P ₁ :

${\displaystyle \mathbf {B} (t)=\mathbf {P} _{1}+(1-t)^{2}(\mathbf {P} _{0}-\mathbf {P} _{1})+t^{2}(\mathbf {P} _{2}-\mathbf {P} _{1}),\ 0\leq t\leq 1.}$

Что немедленно дает производную кривой Безье по t :

${\displaystyle \mathbf {B} '(t)=2(1-t)(\mathbf {P} _{1}-\mathbf {P} _{0})+2t(\mathbf {P} _{2}-\mathbf {P} _{1}),}$

из чего можно сделать вывод, что касательные к кривой в точках P ₀ и P ₂ пересекаются в точке P _1. При увеличении t от 0 до 1 кривая отходит от P ₀ в направлении P ₁ , затем изгибается, чтобы прийти к точке P ₂ из направления P ₁ .

Вторая производная кривой Безье по t равна

${\displaystyle \mathbf {B} ''(t)=2(\mathbf {P} _{2}-2\mathbf {P} _{1}+\mathbf {P} _{0}).}$

Кубические кривые Безье

Четыре точки P ₀ , P ₁ , P ₂ и P ₃ на плоскости или в пространстве более высоких измерений определяют кубическую кривую Безье. Кривая начинается в P _{0 ,} направляясь к P ₁ , и достигает P _{3 ,} исходя из направления P ₂ . Обычно она не проходит через P ₁ или P ₂ ; эти точки существуют только для предоставления информации о направлении. Расстояние между P ₁ и P ₂ определяет, «насколько далеко» и «насколько быстро» кривая движется к P _{1 ,} прежде чем повернуть к P ₂ .

Записывая B _{P i , P j , P k} ( t ) для квадратичной кривой Безье, определяемой точками P _i , P _j и P _k , кубическую кривую Безье можно определить как аффинную комбинацию двух квадратичных кривых Безье:

${\displaystyle \mathbf {B} (t)=(1-t)\mathbf {B} _{\mathbf {P} _{0},\mathbf {P} _{1},\mathbf {P} _{2}}(t)+t\mathbf {B} _{\mathbf {P} _{1},\mathbf {P} _{2},\mathbf {P} _{3}}(t),\ 0\leq t\leq 1.}$

Явная форма кривой:

${\displaystyle \mathbf {B} (t)=(1-t)^{3}\mathbf {P} _{0}+3(1-t)^{2}t\mathbf {P} _{1}+3(1-t)t^{2}\mathbf {P} _{2}+t^{3}\mathbf {P} _{3},\ 0\leq t\leq 1.}$

_При некоторых вариантах выбора P1 и P2 кривая может пересекать сама себя или содержать _точку возврата .

Любая серия из 4 различных точек может быть преобразована в кубическую кривую Безье, которая проходит через все 4 точки по порядку. Учитывая начальную и конечную точку некоторой кубической кривой Безье и точки вдоль кривой, соответствующие t  = 1/3 и t  = 2/3, можно восстановить контрольные точки для исходной кривой Безье. ^[9]

Производная кубической кривой Безье по t равна

${\displaystyle \mathbf {B} '(t)=3(1-t)^{2}(\mathbf {P} _{1}-\mathbf {P} _{0})+6(1-t)t(\mathbf {P} _{2}-\mathbf {P} _{1})+3t^{2}(\mathbf {P} _{3}-\mathbf {P} _{2})\,.}$

Вторая производная кривой Безье по t равна

${\displaystyle \mathbf {B} ''(t)=6(1-t)(\mathbf {P} _{2}-2\mathbf {P} _{1}+\mathbf {P} _{0})+6t(\mathbf {P} _{3}-2\mathbf {P} _{2}+\mathbf {P} _{1})\,.}$

Общее определение

Кривые Безье можно определить для любой степени n .

Рекурсивное определение

Рекурсивное определение кривой Безье степени n выражает ее как линейную комбинацию точка-точка ( линейную интерполяцию ) пары соответствующих точек двух кривых Безье степени n  − 1.

Пусть обозначает кривую Безье, определяемую любым набором точек P ₀ , P ₁ , ...,  P _k . Тогда для начала, ${\displaystyle \mathbf {B} _{\mathbf {P} _{0}\mathbf {P} _{1}\ldots \mathbf {P} _{k}}}$

${\displaystyle \mathbf {B} _{\mathbf {P} _{0}}(t)=\mathbf {P} _{0}{\text{, and}}}$

${\displaystyle \mathbf {B} (t)=\mathbf {B} _{\mathbf {P} _{0}\mathbf {P} _{1}\ldots \mathbf {P} _{n}}(t)=(1-t)\mathbf {B} _{\mathbf {P} _{0}\mathbf {P} _{1}\ldots \mathbf {P} _{n-1}}(t)+t\mathbf {B} _{\mathbf {P} _{1}\mathbf {P} _{2}\ldots \mathbf {P} _{n}}(t)}$

Эта рекурсия поясняется в анимациях ниже.

Явное определение

Формулу можно явно выразить следующим образом (где t ⁰ и (1-t) ⁰ непрерывно расширяются до 1 на всем протяжении [0,1]):

${\displaystyle {\begin{aligned}\mathbf {B} (t)&=\sum _{i=0}^{n}{n \choose i}(1-t)^{n-i}t^{i}\mathbf {P} _{i}\\&=(1-t)^{n}\mathbf {P} _{0}+{n \choose 1}(1-t)^{n-1}t\mathbf {P} _{1}+\cdots +{n \choose n-1}(1-t)t^{n-1}\mathbf {P} _{n-1}+t^{n}\mathbf {P} _{n},&&0\leqslant t\leqslant 1\end{aligned}}}$

где - биномиальные коэффициенты . ${\displaystyle \scriptstyle {n \choose i}}$

Например, когда n  = 5:

${\displaystyle {\begin{aligned}\mathbf {B} (t)&=(1-t)^{5}\mathbf {P} _{0}+5t(1-t)^{4}\mathbf {P} _{1}+10t^{2}(1-t)^{3}\mathbf {P} _{2}+10t^{3}(1-t)^{2}\mathbf {P} _{3}+5t^{4}(1-t)\mathbf {P} _{4}+t^{5}\mathbf {P} _{5},&&0\leqslant t\leqslant 1.\end{aligned}}}$

Терминология

С этими параметрическими кривыми связана некоторая терминология. У нас есть

${\displaystyle \mathbf {B} (t)=\sum _{i=0}^{n}b_{i,n}(t)\mathbf {P} _{i},\ \ \ 0\leq t\leq 1}$

где полиномы

${\displaystyle b_{i,n}(t)={n \choose i}t^{i}(1-t)^{n-i},\ \ \ i=0,\ldots ,n}$

известны как базисные полиномы Бернштейна степени n .

t ⁰  = 1, (1 −  t ) ⁰  = 1, а биномиальный коэффициент , , равен: ${\displaystyle \scriptstyle {n \choose i}}$

${\displaystyle {n \choose i}={\frac {n!}{i!(n-i)!}}.}$

Точки P _i называются контрольными точками кривой Безье. Многоугольник , образованный соединением точек Безье линиями , начинающимися с P ₀ и заканчивающимися P _n , называется многоугольником Безье (или контрольным многоугольником ). Выпуклая оболочка многоугольника Безье содержит кривую Безье.

Полиномиальная форма

Иногда желательно выразить кривую Безье как полином вместо суммы менее простых полиномов Бернштейна . Применение биномиальной теоремы к определению кривой с последующей некоторой перестановкой даст

${\displaystyle \mathbf {B} (t)=\sum _{j=0}^{n}{t^{j}\mathbf {C} _{j}}}$

где

${\displaystyle \mathbf {C} _{j}={\frac {n!}{(n-j)!}}\sum _{i=0}^{j}{\frac {(-1)^{i+j}\mathbf {P} _{i}}{i!(j-i)!}}=\prod _{m=0}^{j-1}(n-m)\sum _{i=0}^{j}{\frac {(-1)^{i+j}\mathbf {P} _{i}}{i!(j-i)!}}.}$

Это может быть практично, если может быть вычислено до многих оценок ; однако следует проявлять осторожность, поскольку кривые высокого порядка могут не обладать числовой устойчивостью ( в этом случае следует использовать алгоритм де Кастельжау ). Обратите внимание, что пустое произведение равно 1. ${\displaystyle \mathbf {C} _{j}}$ ${\displaystyle \mathbf {B} (t)}$

Характеристики

Кубическую кривую Безье (желтую) можно сделать идентичной квадратичной (черной) с помощью

1. копирование конечных точек и

2. размещение двух ее средних контрольных точек (желтые круги) на расстоянии 2/3 от отрезков линии от конечных точек до средней контрольной точки квадратичной кривой (черный прямоугольник).

• Кривая начинается в точке и заканчивается в точке ; это так называемое свойство интерполяции конечной точки . ${\displaystyle \mathbf {P} _{0}}$ ${\displaystyle \mathbf {P} _{n}}$
• Кривая является линией тогда и только тогда, когда все контрольные точки коллинеарны .
• Начало и конец кривой касаются соответственно первой и последней секции многоугольника Безье.
• Кривую можно разделить в любой точке на две подкривые или на произвольное количество подкривых, каждая из которых также является кривой Безье.
• Некоторые кривые, которые кажутся простыми, такие как окружность , не могут быть точно описаны кривой Безье или кусочной кривой Безье; хотя четырехчастная кубическая кривая Безье может аппроксимировать окружность (см. составную кривую Безье ), с максимальной радиальной ошибкой менее одной тысячной, когда каждая внутренняя контрольная точка (или точка офлайн) является расстоянием по горизонтали или вертикали от внешней контрольной точки на единичной окружности. В более общем смысле, n -частная кубическая кривая Безье может аппроксимировать окружность, когда каждая внутренняя контрольная точка является расстоянием от внешней контрольной точки на единичной окружности, где (т. е. ), и . ${\displaystyle \textstyle {\frac {4\left({\sqrt {2}}-1\right)}{3}}}$ ${\displaystyle \textstyle {\frac {4}{3}}\tan(t/4)}$ ${\textstyle t=2\pi /n}$ ${\displaystyle t=360^{\circ }/n}$ ${\displaystyle n>2}$
• Каждая квадратичная кривая Безье также является кубической кривой Безье, и, в более общем смысле, каждая кривая Безье степени n также является кривой степени m для любого m > n . В деталях, кривая степени n с контрольными точками эквивалентна (включая параметризацию) кривой степени n + 1 с контрольными точками , где , и определяют , . ${\displaystyle \mathbf {P} _{0},\,\dots ,\,\mathbf {P} _{n}}$ ${\displaystyle \mathbf {P} '_{0},\,\dots ,\,\mathbf {P} '_{n+1}}$ ${\displaystyle \mathbf {P} '_{k}={\tfrac {k}{n+1}}\mathbf {P} _{k-1}+\left(1-{\tfrac {k}{n+1}}\right)\mathbf {P} _{k}}$ ${\displaystyle \forall k=0,\,1,\,\dots ,\,n,\,n+1}$ ${\displaystyle \mathbf {P} _{n+1}:=\mathbf {P} _{0}}$ ${\displaystyle \mathbf {P} _{-1}:=\mathbf {P} _{n}}$
• Кривые Безье обладают свойством уменьшения вариации . На интуитивном уровне это означает, что кривая Безье не «волнится» больше, чем многоугольник ее контрольных точек, и на самом деле может «волниться» меньше этого. ^[10]
• В кривых Безье степени n нет локального контроля — это означает, что любое изменение контрольной точки требует пересчета и, таким образом, влияет на вид всей кривой, «хотя чем дальше находится точка от измененной контрольной точки, тем меньше изменение кривой» ^{[11] .}
• Кривая Безье порядка выше двух может пересекать сама себя или иметь точку возврата при определенных вариантах выбора контрольных точек.

Кривая второго порядка представляет собой параболический сегмент.

Эквивалентность квадратичной кривой Безье и параболического сегмента

Квадратичная кривая Безье также является сегментом параболы . Поскольку парабола является коническим сечением , некоторые источники называют квадратичные кривые Безье «коническими дугами». ^[12] Ссылаясь на рисунок справа, важные особенности параболы можно вывести следующим образом: ^[13]

1. Касательные к параболе в конечных точках кривой (A и B) пересекаются в ее контрольной точке (C).
2. Если D — середина AB, то касательная к кривой, перпендикулярная CD (штриховая голубая линия), определяет ее вершину (V). Ее ось симметрии (штрихпунктирная голубая линия) проходит через V и перпендикулярна касательной.
3. E — это точка на кривой с касательной под углом 45° к CD (штриховая зеленая линия). Если G — пересечение этой касательной и оси, то линия, проходящая через G и перпендикулярная CD, является директрисой (сплошная зеленая линия).
4. Фокус (F) находится на пересечении оси и линии, проходящей через E и перпендикулярной CD (пунктирная желтая). Latus rectum — это сегмент линии внутри кривой (сплошная желтая).

Производный

Производная для кривой порядка n равна

${\displaystyle \mathbf {B} '(t)=n\sum _{i=0}^{n-1}b_{i,n-1}(t)(\mathbf {P} _{i+1}-\mathbf {P} _{i}).}$

Построение кривых Безье

Линейные кривые

Пусть t обозначает долю прогресса (от 0 до 1), которую точка B ( t ) совершила на своем пути от P ₀ до P ₁ . Например, когда t = 0,25, B ( t ) находится на четверти пути от точки P ₀ до P ₁ . Когда t изменяется от 0 до 1, B ( t ) рисует линию от P ₀ до P ₁ .

Квадратичные кривые

Для квадратичных кривых Безье можно построить промежуточные точки Q ₀ и Q ₁ такие, что при изменении t от 0 до 1:

• Точка Q ₀ ( t ) изменяется от P ₀ до P ₁ и описывает линейную кривую Безье.
• Точка Q ₁ ( t ) изменяется от P ₁ до P ₂ и описывает линейную кривую Безье.
• Точка B ( t ) линейно интерполируется между Q ₀ ( t ) и Q ₁ ( t ) и описывает квадратичную кривую Безье.

Кривые высшего порядка

Для кривых более высокого порядка нужно соответственно больше промежуточных точек. Для кубических кривых можно построить промежуточные точки Q ₀ , Q ₁ и Q ₂ , которые описывают линейные кривые Безье, и точки R ₀ и R ₁ , которые описывают квадратичные кривые Безье:

Для кривых четвертого порядка можно построить промежуточные точки Q ₀ , Q ₁ , Q ₂ и Q ₃ , которые описывают линейные кривые Безье, точки R ₀ , R ₁ и R _{2 ,} которые описывают квадратичные кривые Безье, и точки S ₀ и S ₁ , которые описывают кубические кривые Безье:

Для кривых пятого порядка можно построить аналогичные промежуточные точки.

Эти представления основаны на процессе, используемом в алгоритме Де Кастельжау для вычисления кривых Безье. ^[14]

Смещения (или штриховка) кривых Безье

Кривая с фиксированным смещением от заданной кривой Безье, называемая смещением или параллельной кривой в математике (лежащая «параллельно» исходной кривой, как смещение между рельсами в железнодорожном полотне ), не может быть точно образована кривой Безье (за исключением некоторых тривиальных случаев). В общем случае, двусторонняя кривая смещения кубической Безье является алгебраической кривой 10-го порядка ^[15] и, в более общем случае, для Безье степени n двусторонняя кривая смещения является алгебраической кривой степени 4 n  − 2. ^[16] Однако существуют эвристические методы, которые обычно дают адекватное приближение для практических целей. ^[17]

В области векторной графики рисование двух симметрично расположенных смещенных кривых называется обводкой (кривая Безье или, в общем случае, путь из нескольких сегментов Безье). ^[15] Преобразование из смещенных кривых в заполненные контуры Безье имеет практическое значение при преобразовании шрифтов, определенных в Metafont , которые требуют обводки кривых Безье, в более широко используемые шрифты PostScript type 1 , которые требуют (в целях эффективности) только математически более простой операции заполнения контура, определенного (несамопересекающимися) кривыми Безье. ^[18]

Степень возвышения

Кривую Безье степени n можно преобразовать в кривую Безье степени n  + 1 с той же формой . Это полезно, если программное обеспечение поддерживает кривые Безье только определенной степени. Например, системы, которые могут работать только с кубическими кривыми Безье, могут неявно работать с квадратичными кривыми, используя их эквивалентное кубическое представление.

Для повышения степени мы используем равенство Каждый компонент умножается на (1 −  t ) и  t , таким образом увеличивая степень на единицу, не меняя значения. Вот пример увеличения степени с 2 до 3. ${\displaystyle \mathbf {B} (t)=(1-t)\mathbf {B} (t)+t\mathbf {B} (t).}$ ${\displaystyle \mathbf {b} _{i,n}(t)\mathbf {P} _{i}}$

${\displaystyle {\begin{aligned}(1-t)^{2}\mathbf {P} _{0}+2(1-t)t\mathbf {P} _{1}+t^{2}\mathbf {P} _{2}&=(1-t)^{3}\mathbf {P} _{0}+2(1-t)^{2}t\mathbf {P} _{1}+(1-t)t^{2}\mathbf {P} _{2}+(1-t)^{2}t\mathbf {P} _{0}+2(1-t)t^{2}\mathbf {P} _{1}+t^{3}\mathbf {P} _{2}\\&=(1-t)^{3}\mathbf {P} _{0}+(1-t)^{2}t\left(\mathbf {P} _{0}+2\mathbf {P} _{1}\right)+(1-t)t^{2}\left(2\mathbf {P} _{1}+\mathbf {P} _{2}\right)+t^{3}\mathbf {P} _{2}\\&=(1-t)^{3}\mathbf {P} _{0}+3(1-t)^{2}t{\tfrac {1}{3}}\left(\mathbf {P} _{0}+2\mathbf {P} _{1}\right)+3(1-t)t^{2}{\tfrac {1}{3}}\left(2\mathbf {P} _{1}+\mathbf {P} _{2}\right)+t^{3}\mathbf {P} _{2}\end{aligned}}}$

Другими словами, исходные начальная и конечная точки не изменяются. Новые контрольные точки — и . ${\displaystyle \mathbf {P'} _{1}={\tfrac {1}{3}}\left(\mathbf {P} _{0}+2\mathbf {P} _{1}\right)}$ ${\displaystyle \mathbf {P'} _{2}={\tfrac {1}{3}}\left(2\mathbf {P} _{1}+\mathbf {P} _{2}\right)}$

Для произвольного n используем равенства ^[19]

${\displaystyle {\begin{cases}{n+1 \choose i}(1-t)\mathbf {b} _{i,n}={n \choose i}\mathbf {b} _{i,n+1}\\{n+1 \choose i+1}t\mathbf {b} _{i,n}={n \choose i}\mathbf {b} _{i+1,n+1}\end{cases}}\quad \implies \quad {\begin{cases}(1-t)\mathbf {b} _{i,n}={\frac {n+1-i}{n+1}}\mathbf {b} _{i,n+1}\\t\mathbf {b} _{i,n}={\frac {i+1}{n+1}}\mathbf {b} _{i+1,n+1}\end{cases}}}$

Поэтому:

${\displaystyle {\begin{aligned}\mathbf {B} (t)&=(1-t)\sum _{i=0}^{n}\mathbf {b} _{i,n}(t)\mathbf {P} _{i}+t\sum _{i=0}^{n}\mathbf {b} _{i,n}(t)\mathbf {P} _{i}\\&=\sum _{i=0}^{n}{\frac {n+1-i}{n+1}}\mathbf {b} _{i,n+1}(t)\mathbf {P} _{i}+\sum _{i=0}^{n}{\frac {i+1}{n+1}}\mathbf {b} _{i+1,n+1}(t)\mathbf {P} _{i}\\&=\sum _{i=0}^{n+1}\left({\frac {i}{n+1}}\mathbf {P} _{i-1}+{\frac {n+1-i}{n+1}}\mathbf {P} _{i}\right)\mathbf {b} _{i,n+1}(t)\\&=\sum _{i=0}^{n+1}\mathbf {b} _{i,n+1}(t)\mathbf {P'} _{i}\end{aligned}}}$

введение произвольного и . ${\displaystyle \mathbf {P} _{-1}}$ ${\displaystyle \mathbf {P} _{n+1}}$

Поэтому новые контрольные точки ^[19]

${\displaystyle \mathbf {P'} _{i}={\frac {i}{n+1}}\mathbf {P} _{i-1}+{\frac {n+1-i}{n+1}}\mathbf {P} _{i},\quad i=0,\ldots ,n+1.}$

Повторное повышение степени

Концепция повышения степени может быть повторена на контрольном полигоне R, чтобы получить последовательность контрольных полигонов R , R ₁ , R ₂ и т. д. После повышения степени на r , полигон R _r имеет вершины P _{0 , r} , P _{1 , r} , P _{2 , r} , ..., P _{n + r , r} , заданные формулой ^[19]

${\displaystyle \mathbf {P} _{i,r}=\sum _{j=0}^{n}\mathbf {P} _{j}{\tbinom {n}{j}}{\frac {\tbinom {r}{i-j}}{\tbinom {n+r}{i}}}.}$

Можно также показать, что для базовой кривой Безье B ,

${\displaystyle \mathbf {\lim _{r\to \infty }R_{r}} =\mathbf {B} .}$

Степень снижения

Снижение степени может быть выполнено только тогда, когда рассматриваемая кривая изначально поднята с более низкой степени. ^[20] Было предложено и использовано на практике несколько алгоритмов аппроксимации. ^{[21] [22]}

Рациональные кривые Безье

Сегменты конических сечений, представленные в точности рациональными кривыми Безье

Рациональная кривая Безье добавляет регулируемые веса для обеспечения более точных приближений к произвольным формам. Числитель — это взвешенная кривая Безье в форме Бернштейна, а знаменатель — это взвешенная сумма полиномов Бернштейна . Рациональные кривые Безье могут, среди прочего, использоваться для точного представления сегментов конических сечений , включая дуги окружностей. ^[23]

При наличии n  + 1 контрольных точек P ₀ , ..., P _n рациональная кривая Безье может быть описана следующим образом:

${\displaystyle \mathbf {B} (t)={\frac {\sum _{i=0}^{n}b_{i,n}(t)\mathbf {P} _{i}w_{i}}{\sum _{i=0}^{n}b_{i,n}(t)w_{i}}},}$

или просто

${\displaystyle \mathbf {B} (t)={\frac {\sum _{i=0}^{n}{n \choose i}t^{i}(1-t)^{n-i}\mathbf {P} _{i}w_{i}}{\sum _{i=0}^{n}{n \choose i}t^{i}(1-t)^{n-i}w_{i}}}.}$

Выражение можно расширить, используя числовые системы помимо вещественных для весов. В комплексной плоскости точки {1}, {-1} и {1} с весами { }, {1} и { } образуют полную окружность с радиусом один. Для кривых с точками и весами на окружности вес можно масштабировать, не меняя форму кривой. ^[24] Масштабирование центрального веса указанной выше кривой на 1,35508 дает более равномерную параметризацию. ${\displaystyle i}$ ${\displaystyle -i}$

Приложения

Компьютерная графика

Путь Безье в Adobe Illustrator

Кривые Безье широко используются в компьютерной графике для моделирования плавных кривых. Поскольку кривая полностью содержится в выпуклой оболочке ее контрольных точек , точки можно графически отобразить и использовать для интуитивного манипулирования кривой. Аффинные преобразования, такие как перенос и вращение, можно применять к кривой, применяя соответствующее преобразование к контрольным точкам кривой.

Квадратичные и кубические кривые Безье являются наиболее распространенными. Кривые более высокого порядка требуют больших вычислительных затрат для оценки. Когда требуются более сложные формы, кривые Безье низкого порядка объединяются, создавая составную кривую Безье . Составная кривая Безье обычно называется «путем» в языках векторной графики (например, PostScript ), стандартах векторной графики (например, SVG ) и программах векторной графики (например , Artline , Timeworks Publisher , Adobe Illustrator , CorelDraw , Inkscape и Allegro ). Чтобы объединить кривые Безье в составную кривую Безье без перегибов, достаточно свойства, называемого непрерывностью G1 , чтобы заставить контрольную точку, в которой встречаются две составляющие кривые Безье, лежать на линии, определяемой двумя контрольными точками с каждой стороны.

Абстрактная композиция кубических кривых Безье, трассируемых лучами в 3D. Пересечение лучей с объемами, охватываемыми вдоль кривых, вычисляется с помощью алгоритма Phantom Ray-Hair Intersector. ^[25]

Самый простой метод преобразования сканирования ( растеризации ) кривой Безье — оценить ее во многих близко расположенных точках и преобразовать сканированием аппроксимирующую последовательность сегментов линии. Однако это не гарантирует, что растеризованный вывод будет выглядеть достаточно гладким, поскольку точки могут быть расположены слишком далеко друг от друга. И наоборот, он может генерировать слишком много точек в областях, где кривая близка к линейной. Распространенным адаптивным методом является рекурсивное подразделение, в котором контрольные точки кривой проверяются, чтобы увидеть, приближает ли кривая линию в пределах малого допуска. Если нет, кривая параметрически подразделяется на два сегмента, 0 ≤ t ≤ 0,5 и 0,5 ≤ t ≤ 1, и та же процедура применяется рекурсивно к каждой половине. Существуют также методы прямого дифференцирования, но необходимо проявлять большую осторожность при анализе распространения ошибок. ^[26]

Аналитические методы, в которых кривая Безье пересекается с каждой линией сканирования, включают в себя нахождение корней кубических полиномов (для кубических кривых Безье) и работу с несколькими корнями, поэтому они нечасто используются на практике. ^[26]

Алгоритм растеризации, используемый в Metafont, основан на дискретизации кривой, так что она аппроксимируется последовательностью « ходов ладьи », которые являются чисто вертикальными или чисто горизонтальными, вдоль границ пикселей. Для этого плоскость сначала разбивается на восемь секторов по 45° (координатными осями и двумя линиями ), затем кривая разбивается на более мелкие сегменты таким образом, чтобы направление сегмента кривой оставалось в пределах одного сектора; поскольку скорость кривой является полиномом второй степени, нахождение значений, при которых она параллельна одной из этих линий, можно выполнить путем решения квадратных уравнений . Внутри каждого сегмента доминирует либо горизонтальное, либо вертикальное движение, и общее количество шагов в любом направлении можно считать из координат конечной точки; например, в секторе 0–45° доминирует горизонтальное движение вправо, поэтому остается только решить, между какими шагами вправо кривая должна сделать шаг вверх. ^[27] ${\displaystyle y=\pm x}$ ${\displaystyle t}$

Существует также модифицированная кривая форма алгоритма рисования линий Брезенхэма от Zingl, которая выполняет эту растеризацию путем деления кривой на рациональные части и вычисления ошибки в каждом пикселе таким образом, что она либо движется под углом 45°, либо прямо в зависимости от ошибки компаундирования при прохождении по кривой. Это сводит следующий шаг вычисления к серии целочисленных сложений и вычитаний. ^[28]

Анимация

В анимационных приложениях, таких как Adobe Flash и Synfig , кривые Безье используются для контура, например, движения. Пользователи очерчивают желаемый путь в кривых Безье, а приложение создает необходимые кадры для перемещения объекта по пути. ^{[29] [30]}

В 3D-анимации кривые Безье часто используются для определения 3D-путей, а также 2D-кривые для интерполяции ключевых кадров. ^[31] Кривые Безье теперь очень часто используются для управления плавностью анимации в CSS , JavaScript , JavaFx и Flutter SDK . ^[4]

Шрифты

Шрифты TrueType используют составные кривые Безье, состоящие из квадратичных кривых Безье. Другие языки и инструменты визуализации (такие как PostScript , Asymptote , Metafont и SVG ) используют составные кривые Безье, состоящие из кубических кривых Безье, для рисования изогнутых фигур. Шрифты OpenType могут использовать любой вид кривой, в зависимости от того, какая технология шрифта лежит в основе оболочки OpenType. ^[32]

Шрифтовые движки, такие как FreeType , рисуют кривые шрифта (и линии) на пикселизированной поверхности, используя процесс, известный как растеризация шрифта . ^[12] Обычно шрифтовые движки и векторные графические движки рендерят кривые Безье, разделяя их рекурсивно до точки, где кривая становится достаточно плоской, чтобы ее можно было нарисовать как серию линейных или круговых сегментов. Точный алгоритм разделения зависит от реализации, необходимо соблюдать только критерии плоскостности, чтобы достичь необходимой точности и избежать немонотонных локальных изменений кривизны. Функция «гладкой кривой» диаграмм в Microsoft Excel также использует этот алгоритм. ^[33]

Поскольку дуги окружностей и эллипсов не могут быть точно представлены кривыми Безье, они сначала аппроксимируются кривыми Безье, которые в свою очередь аппроксимируются дугами окружностей. Это неэффективно, поскольку существуют также аппроксимации всех кривых Безье с использованием дуг окружностей или эллипсов, которые могут быть визуализированы пошагово с произвольной точностью. Другой подход, используемый современными аппаратными графическими адаптерами с ускоренной геометрией, может преобразовать точно все кривые Безье и конические кривые (или поверхности) в NURBS , которые могут быть визуализированы пошагово без предварительного рекурсивного разделения кривой для достижения необходимого условия плоскостности. Этот подход также сохраняет определение кривой при всех линейных или перспективных 2D и 3D преобразованиях и проекциях. ^{[ необходима цитата ]}

Робототехника

Поскольку контрольный многоугольник позволяет определить, сталкивается ли путь с какими-либо препятствиями, кривые Безье используются для создания траекторий конечных эффекторов . ^[34] Кроме того, траектории суставного пространства могут быть точно дифференцированы с помощью кривых Безье. Следовательно, производные траекторий суставного пространства используются для расчета динамики и усилия управления (профилей крутящего момента) роботизированного манипулятора. ^[34]

Смотрите также

• Поверхность Безье
• B-сплайн
• ГЭМ/4 и ГЭМ/5
• кривая Эрмита
• НУРБС
• Стринг-арт – кривые Безье также формируются многими распространенными формами стринг-арта, где нити нанизываются на рамку из гвоздей. ^[35]
• Свойство уменьшения вариации кривых Безье

Примечания

1. Программы для обработки изображений, такие как Inkscape , Adobe Photoshop и GIMP .
2. В приложениях для анимации, таких как Adobe Flash , Adobe After Effects , Microsoft Expression Blend , Blender , Autodesk Maya и Autodesk 3ds Max .

Ссылки

Цитаты

1. Уэллс, Джон (3 апреля 2008 г.). Словарь произношения Longman (3-е изд.). Pearson Longman. ISBN 978-1-4058-8118-0.
2. Мортенсон, Майкл Э. (1999). Математика для приложений компьютерной графики. Industrial Press Inc. стр. 264. ISBN 9780831131111.
3. Хазевинкель, Михиль (1997). Энциклопедия математики: Приложение. Том 1. Springer Science & Business Media. стр. 119. ISBN 9780792347095.
4. "Класс Cubic - библиотека анимации - Dart API". api.flutter.dev . Получено 2021-04-26 .
5. Бисвас, Прадипта; Лэнгдон, Пэт (2015-04-03). «Мультимодальная интеллектуальная система отслеживания взгляда». Международный журнал взаимодействия человека и компьютера . 31 (4): 277–294. doi :10.1080/10447318.2014.1001301. ISSN  1044-7318. S2CID  36347027.
6. Джеральд Э. Фарин; Йозеф Хошек; Мён-Су Ким (2002). Справочник по компьютерному геометрическому проектированию. Elsevier. С. 4–6. ISBN 978-0-444-51104-1.
7. Поль де Кастельжо. Математика и CAO. Том 2: Формы на полюсах . ISBN 9782866010423.
8. Марио А. Гутьеррес; Фредерик Вексо; Дэниел Тельманн (2023). Шаг в виртуальную реальность. Спрингер Природа. п. 33. ISBN 9783031364877.
9. Джон Буркардт. "Forcing Bezier Interpolation". Архивировано из оригинала 25.12.2013.
10. Теофило Гонсалес ; Хорхе Диас-Эррера; Аллен Такер (2014). Computing Handbook, третье издание: Computer Science and Software Engineering. CRC Press. стр. 32-14. ISBN 978-1-4398-9852-9.
11. Макс К. Агостон (2005). Компьютерная графика и геометрическое моделирование: реализация и алгоритмы. Springer Science & Business Media. стр. 404. ISBN 978-1-84628-108-2.
12. "FreeType Glyph Conventions / VI. FreeType outlines". Проект Free Type . 13 февраля 2018 г.
    "FreeType Glyph Conventions – Version 2.1 / VI. FreeType outlines". 6 марта 2011 г. Архивировано из оригинала 29-09-2011.
13. Дункан Марш (2005). Прикладная геометрия для компьютерной графики и САПР . Springer Undergraduate Mathematics Series (2-е изд.). ISBN 978-1-85233-801-5. ASIN  1852338016.
14. Шене, CK "Поиск точки на кривой Безье: алгоритм Де Кастельжо" . Получено 6 сентября 2012 г.
15. Mark Kilgard (10 апреля 2012 г.). «CS 354 Векторная графика и рендеринг путей». стр. 28.
16. Рида Т. Фаруки. "Введение в кривые пифагорейского годографа" (PDF) . Архивировано из оригинала (PDF) 5 июня 2015 г., в частности стр. 16 «таксономия офсетных кривых».
17. Например:
    • Остромоухов, Виктор. Эрмитово приближение для вычисления офсетной кривой (PDF) . CiteSeerX  10.1.1.43.1724 .
    • Килгард, Марк Дж.; Мортон, Генри Паккард (24 ноября 2011 г.). "US20110285719A1 Аппроксимация штрихованных криволинейных сегментов высшего порядка квадратичными сегментами кривой Безье". Google Patents .
    Для обзора см. Elber, G. (май 1997 г.). "Сравнение методов аппроксимации офсетной кривой" (PDF) . IEEE Computer Graphics and Applications . 17 (3): 62–71. doi :10.1109/38.586019.
18. Ричард Дж. Кинч (1995). «MetaFog: преобразование форм Metafont в контуры» (PDF) . TUGboat . 16 (3–Труды ежегодного собрания 1995 года). Архивировано (PDF) из оригинала 2022-10-09.
19. Farin, Gerald (1997). Кривые и поверхности для компьютерного геометрического проектирования (4-е изд.). Elsevier Science & Technology Books. ISBN 978-0-12-249054-5.
20. "Сплайны Безье" . Документация FontForge 20230101 .
21. Эк, Маттиас (август 1993 г.). «Снижение степени кривых Безье». Computer Aided Geometric Design . 10 (3–4): 237–251. doi :10.1016/0167-8396(93)90039-6.
22. Рабабах, Абедаллах; Ибрагим, Салису (2018). «Геометрическое снижение степени кривых Безье». Математика и вычисления . 253 : 87–95. doi :10.1007/978-981-13-2095-8_8.
23. Нил Доджсон (2000-09-25). "Некоторые математические элементы графики: рациональные B-сплайны" . Получено 2009-02-23 .
24. J. Sánchez-Reyes (ноябрь 2009). «Комплексные рациональные кривые Безье». Computer Aided Geometric Design . 26 (8): 865–876. doi :10.1016/j.cagd.2009.06.003.
25. Александр Решетов и Дэвид Любке, Phantom Ray-Hair Intersector. В трудах ACM по компьютерной графике и интерактивным технологиям (1 августа 2018 г.). [1]
26. Xuexiang Li & Junxiao Xue. «Комплексная квадратичная кривая Безье на единичной окружности». Чжэнчжоу, Китай: Школа программного обеспечения, Университет Чжэнчжоу.
27. Части 19–22 из Knuth, Donald E. (1986). Metafont: The Program . Addison-Wesley. ISBN 0-201-13438-1.
28. Зингл, Алоис (2012). Алгоритм растеризации для рисования кривых (PDF) (Отчет).
    Аннотация HTML и демо: Zingl, Alois (2016). "Bresenham". members.chello.at .
29. "Использование путей движения в анимации". Adobe . Получено 2019-04-11 .
30. "По следам сплайна". Synfig Wiki . Получено 11.04.2019 .
31. Доджсон, Нил А. (1999). «Конспект лекций по продвинутой графике» (PDF) . cl.cam.ac.uk . Компьютерная лаборатория Кембриджского университета. Архивировано (PDF) из оригинала 2022-10-09.
32. "Разница между CFF и TTF". Know How . Linotype. Архивировано из оригинала 2017-07-03 . Получено 3 июля 2018 . Формат OpenType был сформулирован в 1996 году. К 2003 году он начал заменять два конкурирующих формата: шрифты Type1, разработанные Adobe и основанные на [P]ost[S]cript, и шрифты TrueType, указанные Microsoft и Apple. (...) TTF обозначает TrueTypeFont и указывает на то, что данные шрифта такие же, как в шрифтах TrueType. CFF обозначает формат шрифта Type1. Строго говоря, он относится к формату Compact Font Format, который используется в процессах сжатия для шрифтов Type2. (...) кубический формат Безье шрифтов Type1 более экономит место по сравнению с квадратичным форматом шрифтов TrueType. Несколько килобайт можно сэкономить в больших, сложных шрифтах, которые могут представлять преимущество в Интернете. С другой стороны, более подробная информация о подсказках шрифтов TrueType полезна для очень обширной оптимизации для использования на экране.
33. "smooth_curve_bezier_example_file.xls". Rotating Machinery Analysis, Inc. Архивировано из оригинала 2011-07-18 . Получено 2011-02-05 .
34. Малик, Арыслан; Хендерсон, Трой; Празеница, Ричард (январь 2021 г.). «Генерация траектории для многотельной роботизированной системы с использованием формулы произведения экспонент». Форум AIAA Scitech 2021 : 2016. doi :10.2514/6.2021-2016. ISBN 978-1-62410-609-5. S2CID  234251587.
35. Гросс, Ренан (2014). «Мосты, струнное искусство и кривые Безье». В Pitici, Mircea (ред.). Лучшее сочинение по математике 2013 года . Princeton University Press. стр. 77–89. doi :10.1515/9781400847990-011. ISBN 9780691160412. JSTOR  j.ctt4cgb74.13.

Источники

• Рида Т. Фаруки (август 2012 г.). «Базовый полином Бернштейна: ретроспектива столетия» (PDF) . Компьютерное геометрическое проектирование . 29 (6): 379–419. doi :10.1016/j.cagd.2012.03.001.
• Пол Бурк (2009-07-19). Поверхности Безье (в 3D). Архивировано из оригинала 2009-07-19.
• Дональд Кнут (1986). Metafont: программа . Addison-Wesley. стр. 123–131.Превосходное обсуждение деталей реализации; доступно бесплатно как часть дистрибутива TeX.
• Томас Седерберг. Кривые Безье (PDF) . Архивировано из оригинала (PDF) 2006-02-21 . Получено 2005-09-14 .
• JD Foley; и др. (1992). Компьютерная графика: принципы и практика в C (2-е изд.). Addison Wesley.
• Раджив Чандел (2014-03-20). «Реализация кривых Безье в играх».

Дальнейшее чтение

• A Primer on Bézier Curves – онлайн-книга с открытым исходным кодом, объясняющая кривые Безье и связанные с ними графические алгоритмы, с интерактивной графикой.
• Кубические кривые Безье – Под капотом (видео) – видео, демонстрирующее, как компьютеры визуализируют кубическую кривую Безье, Питер Ноуэлл
• От Безье до Бернстайна. Тематическая колонка Американского математического общества
• «Кривая Безье», Энциклопедия математики , EMS Press , 2001 [1994]
• Праутч, Хартмут; Бём, Вольфганг; Палушны, Марко (2002). Методы Безье и B-сплайна . Springer Science & Business Media. ISBN 978-3-540-43761-1.
• Галлье, Жан (1999). "Глава 5. Полиномиальные кривые как кривые Безье". Кривые и поверхности в геометрическом моделировании: теория и алгоритмы . Морган Кауфманн.Эта книга больше не переиздается и находится в свободном доступе у автора.
• Фарин, Джеральд Э. (2002). Кривые и поверхности для CAGD: практическое руководство (5-е изд.). Морган Кауфманн. ISBN 978-1-55860-737-8.
• Вайсштейн, Эрик В. «Кривая Безье». Математический мир .
• Хоффман, Гернот. "Кривые Безье" (PDF) . Архивировано из оригинала (PDF) 2006-12-02.(60 страниц)
• Ahn, Young Joon (2004). «Аппроксимация дуг окружностей и смещенных кривых кривыми Безье высокой степени». Журнал вычислительной и прикладной математики . 167 (2): 405–416. Bibcode : 2004JCoAM.167..405A. doi : 10.1016/j.cam.2003.10.008 .
• Дэвис, Джейсон. «Анимированные кривые Безье».
• Хови, Чад (20 мая 2022 г.). «Геометрия Безье». GitHub .
• Хови, Чад (2022). Формулировка и реализация на Python геометрии Безье и B-сплайна. SAND2022-7702C. (153 страницы)

Внешние ссылки

Компьютерный код

• TinySpline: C-библиотека с открытым исходным кодом для NURBS, B-сплайнов и кривых Безье с привязками к различным языкам
• Библиотека C++ для генерации функций Безье во время компиляции
• Простая реализация кривой Безье с помощью рекурсивного метода на Python