Кривая Безье

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

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

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

Кривая Безье ( / ˈ 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 .

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

Кривая Безье определяется набором контрольных точек от _P0 до Pn , где 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 ) по заданным точкам P0 _, P1 и P2 _,

${\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 ₁ . Когда t _{увеличивается} от 0 до 1 , кривая отклоняется от _P0 в направлении P1 _, затем изгибается и достигает P2 в направлении P1 _.

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

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

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

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

Написав B _{P i , P j , P k} ( t ) для квадратичной кривой Безье, определяемой точками Pi , 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.}$

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

Любую серию из 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. Касательные к параболе на концах кривой (А и В) пересекаются в ее контрольной точке (С).
2. Если D является средней точкой AB, касательная к кривой, перпендикулярной CD (пунктирная голубая линия), определяет ее вершину (V). Его ось симметрии (голубой штрихпунктир) проходит через V и перпендикулярна касательной.
3. E — это любая точка кривой с касательной под углом 45 ° к CD (пунктирная зеленая линия). Если G является пересечением этой касательной и оси, линия, проходящая через G и перпендикулярная CD, является направляющей (сплошной зеленый цвет).
4. Фокус (F) находится на пересечении оси и линии, проходящей через E и перпендикулярной CD (желтый пунктир). Широкая прямая кишка — это сегмент линии внутри кривой (сплошной желтый).

Производная

Производная кривой порядка 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 ) составляет четверть пути от _точки P0 до P1 _. Поскольку 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 ₁ , описывающие квадратичные кривые Безье:

Для кривых четвертого порядка можно построить промежуточные точки Q0 , _Q1 , _Q2 и _Q3 , описывающие линейные кривые Безье, точки _{R0 ,} R1 и R2 , _{описывающие} квадратичные кривые Безье, _и точки S0 _и S1 _, которые описать кубические кривые Безье:

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

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

Смещения (или обводки) кривых Безье

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

В области векторной графики рисование двух симметрично расположенных смещенных кривых называется обводкой (кривая Безье или вообще путь из нескольких сегментов Безье). ^[15] Преобразование смещенных кривых в заполненные контуры Безье имеет практическое значение при преобразовании шрифтов, определенных в Metafont , которые требуют обводки кривых Безье, в более широко используемые шрифты PostScript типа 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}$

Существует также модифицированная форма кривой алгоритма рисования линий Брезенхема, разработанная Зинглом, которая выполняет эту растеризацию путем разделения кривой на рациональные части и вычисления ошибки в каждом местоположении пикселя, так что она движется либо под углом 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 г.). Словарь произношения Лонгмана (3-е изд.). Пирсон Лонгман. ISBN 978-1-4058-8118-0.
2. Мортенсон, Майкл Э. (1999). Математика для приложений компьютерной графики. Industrial Press Inc. с. 264. ИСБН 9780831131111.
3. Хазевинкель, Мишель (1997). Энциклопедия математики: Приложение. Том. 1. Springer Science & Business Media. п. 119. ИСБН 9780792347095.
4. «Класс Cubic — библиотека анимации — Dart API». api.flutter.dev . Проверено 26 апреля 2021 г.
5. Бисвас, Прадипта; Лэнгдон, Пэт (3 апреля 2015 г.). «Мультимодальная интеллектуальная система слежения за взглядом». Международный журнал взаимодействия человека и компьютера . 31 (4): 277–294. дои : 10.1080/10447318.2014.1001301. ISSN  1044-7318. S2CID  36347027.
6. Джеральд Э. Фарин; Йозеф Хошек; Мён Су Ким (2002). Справочник по компьютерному геометрическому проектированию. Эльзевир. стр. 4–6. ISBN 978-0-444-51104-1.
7. Поль де Кастельжо. Математика и CAO. Том 2: Формы на полюсах . ISBN 9782866010423.
8. Марио А. Гутьеррес; Фредерик Вексо; Дэниел Тельманн (2023). Шаг в виртуальную реальность. Спрингер Природа. п. 33. ISBN 9783031364877.
9. Джон Буркардт. «Принудительная интерполяция Безье». Архивировано из оригинала 25 декабря 2013 г.
10. Теофило Гонсалес ; Хорхе Диас-Эррера; Аллен Такер (2014). Справочник по вычислительной технике, третье издание: Информатика и разработка программного обеспечения. ЦРК Пресс. стр. 32–14. ISBN 978-1-4398-9852-9.
11. Макс К. Агостон (2005). Компьютерная графика и геометрическое моделирование: реализация и алгоритмы. Springer Science & Business Media. п. 404. ИСБН 978-1-84628-108-2.
12. «Соглашения о глифах FreeType / VI. Контуры FreeType». Проект «Свободный тип» . 13 февраля 2018 г.
    «Соглашения о глифах FreeType - Версия 2.1 / VI. Краткое описание FreeType». 6 марта 2011 г. Архивировано из оригинала 29 сентября 2011 г.
13. Дункан Марш (2005). Прикладная геометрия для компьютерной графики и САПР . Серия Springer по математике для студентов (2-е изд.). ISBN 978-1-85233-801-5. АСИН  1852338016.
14. Шене, К.К. «Нахождение точки на кривой Безье: алгоритм де Кастельжо» . Проверено 6 сентября 2012 г.
15. Марк Килгард (10 апреля 2012 г.). «Векторная графика и рендеринг пути CS 354». п. 28.
16. Рида Т. Фаруки. «Введение в кривые годографа Пифагора» (PDF) . Архивировано из оригинала (PDF) 5 июня 2015 г., особенно стр. 16 «Таксономия кривых смещения».
17. Например:
    • Остромоухов, Виктор. Приближение Эрмита для расчета кривой смещения (PDF) . CiteSeerX  10.1.1.43.1724 .
    • Килгард, Марк Дж.; Мортон, Генри Паккард (24 ноября 2011 г.). «US20110285719A1 Аппроксимация штрихованных кривых сегментов высшего порядка квадратичными сегментами кривой Безье». Гугл Патенты .
    Обзор см. в Elber, G. (май 1997 г.). «Сравнение методов аппроксимации кривой смещения» (PDF) . IEEE Компьютерная графика и приложения . 17 (3): 62–71. дои : 10.1109/38.586019.
18. Ричард Дж. Кинч (1995). «MetaFog: преобразование фигур Metafont в контуры» (PDF) . БУКСИР . 16 (3 – Материалы ежегодного собрания 1995 г.). Архивировано (PDF) из оригинала 9 октября 2022 г.
19. Фарин, Джеральд (1997). Кривые и поверхности для автоматизированного геометрического проектирования (4-е изд.). Книги Elsevier по науке и технологиям. ISBN 978-0-12-249054-5.
20. "Сплайны Безье" . Документация FontForge 20230101 .
21. Эк, Матиас (август 1993 г.). «Степень уменьшения кривых Безье». Компьютерное геометрическое проектирование . 10 (3–4): 237–251. дои : 10.1016/0167-8396(93)90039-6.
22. Рабаба, Абедалла; Ибрагим, Салису (2018). «Геометрическое приведение кривых Безье». Математика и информатика . 253 : 87–95. дои : 10.1007/978-981-13-2095-8_8.
23. Нил Доджсон (25 сентября 2000 г.). «Некоторые математические элементы графики: рациональные B-сплайны» . Проверено 23 февраля 2009 г.
24. Х. Санчес-Рейес (ноябрь 2009 г.). «Комплексные рациональные кривые Безье». Компьютерное геометрическое проектирование . 26 (8): 865–876. дои : 10.1016/j.cagd.2009.06.003.
25. Александр Решетов и Дэвид Любке, Phantom Ray-Hair Intersector. В материалах ACM по компьютерной графике и интерактивным методам (1 августа 2018 г.). [1]
26. Сюэсян Ли и Цзюньсяо Сюэ. «Комплексная квадратичная кривая Безье на единичном круге». Чжэнчжоу, Китай: Школа программного обеспечения Университета Чжэнчжоу.
27. Части 19–22 Кнута, Дональда Э. (1986). Метафонт: Программа . Аддисон-Уэсли. ISBN 0-201-13438-1.
28. Зингл, Алоис (2012). Алгоритм растеризации для рисования кривых (PDF) (Отчет).
    Аннотация и демонстрация HTML: Зингл, Алоис (2016). «Бресенхэм». Members.chello.at .
29. «Использование траекторий движения в анимации». Adobe . Проверено 11 апреля 2019 г.
30. «По сплайну». Синфиг Вики . Проверено 11 апреля 2019 г.
31. Доджсон, Нил А. (1999). «Конспекты лекций по продвинутой графике» (PDF) . cl.cam.ac.uk. _ Компьютерная лаборатория Кембриджского университета. Архивировано (PDF) из оригинала 9 октября 2022 г.
32. «Разница между CFF и TTF» . Секрет производства . Линотип. Архивировано из оригинала 3 июля 2017 г. Проверено 3 июля 2018 г. Формат OpenType был сформулирован в 1996 году. К 2003 году он начал заменять два конкурирующих формата: шрифты Type1, разработанные Adobe и основанные на [P]ost[S]script, и шрифты TrueType, определенные Microsoft и Apple. (...) TTF означает TrueTypeFont и указывает, что данные шрифта такие же, как и в шрифтах TrueType. CFF означает формат шрифта Type1. Строго говоря, это относится к компактному формату шрифтов, который используется в процессах сжатия шрифтов Type2. (...) кубический формат Безье шрифтов Type1 более компактен по сравнению с квадратичным форматом шрифтов TrueType. Некоторые килобайты можно сохранить с помощью крупных и сложных шрифтов, что может стать преимуществом в Интернете. С другой стороны, более подробная информация о шрифтах TrueType полезна для очень обширной оптимизации для использования на экране.
33. "smooth_curve_bezier_example_file.xls". Анализ вращающегося оборудования, Inc. Архивировано из оригинала 18 июля 2011 г. Проверено 5 февраля 2011 г.
34. Малик, Арыслан; Хендерсон, Трой; Праженица, Ричард (январь 2021 г.). «Генерация траектории многотельной робототехнической системы с использованием формулы продукта экспоненты». Форум AIAA Scitech 2021 : 2016. doi : 10.2514/6.2021-2016. ISBN 978-1-62410-609-5. S2CID  234251587.
35. Гросс, Ренан (2014). «Мосты, струнное искусство и кривые Безье». В Питичи, Мирча (ред.). Лучшее сочинение по математике 2013 года . Издательство Принстонского университета. стр. 77–89. дои : 10.1515/9781400847990-011. ISBN 9780691160412. JSTOR  j.ctt4cgb74.13.

Источники

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

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

• Учебник по кривым Безье - онлайн-книга с открытым исходным кодом, объясняющая кривые Безье и связанные с ними графические алгоритмы, с интерактивной графикой.
• Кубические кривые Безье – Под капотом (видео) – видео Питера Ноуэлла, показывающее, как компьютеры отображают кубическую кривую Безье.
• От Безье до Бернштейна. Тематическая колонка Американского математического общества.
• «Кривая Безье», Математическая энциклопедия , 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) 2 декабря 2006 г.(60 страниц)
• Ан, Ён Джун (2004). «Аппроксимация дуг окружностей и кривых смещения кривыми Безье высокой степени». Журнал вычислительной и прикладной математики . 167 (2): 405–416. Бибкод : 2004JCoAM.167..405A. дои : 10.1016/j.cam.2003.10.008 .
• Дэвис, Джейсон. «Анимированные кривые Безье».
• Хови, Чад (20 мая 2022 г.). «Геометрия Безье». Гитхаб .
• Хови, Чад (2022 г.). Формулировка и реализация на Python геометрии Безье и B-сплайна. ПЕСОК2022-7702C. (153 страницы)

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

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

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