Кривы́е Безье́ — типы кривых, предложенные в 60-х годах XX века независимо друг от друга Пьером Безье из автомобилестроительной компании « Рено » и Полем де Кастельжо из компании « Ситроен », где применялись для проектирования кузовов автомобилей.

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

Кривая Безье является частным случаем многочленов Бернштейна , описанных русским математиком Сергеем Натановичем Бернштейном в 1912 году.

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

Впоследствии это открытие стало одним из важнейших инструментов систем автоматизированного проектирования и программ компьютерной графики .

Определение

Пусть в пространстве ${\displaystyle \mathbb {R} ^{m}}$ размерности ${\displaystyle m\geqslant 1}$ над ${\displaystyle \mathbb {R} }$ задана последовательность контрольных точек ${\displaystyle (\mathbf {P} _{0},\ldots ,\mathbf {P} _{n})}$ , где ${\displaystyle n\geqslant 0}$ , а ${\displaystyle \mathbf {P} _{k}=(x_{1,k},\ldots ,x_{m,k})}$ для ${\displaystyle k=0,\ldots ,n}$ .

Тогда множество ${\displaystyle \left\{\mathbf {B} (t)|0\leqslant t\leqslant 1\right\}}$ точек ${\displaystyle \mathbf {B} (t)=(z_{1}(t),\ldots ,z_{m}(t))}$ с координатами ${\displaystyle (z_{j}(t))_{j=1,\ldots ,m}}$ , параметрически задаваемыми выражениями

${\displaystyle z_{j}(t)=\sum _{k=0}^{n}x_{j,k}b_{k,n}(t)\quad }$ для ${\displaystyle \quad 0\leqslant t\leqslant 1,\quad }$ где ${\displaystyle \quad j=1,\ldots ,m,\quad }$ а ${\displaystyle \quad b_{k,n}(t)={n \choose k}t^{k}(1-t)^{n-k}\quad }$ для ${\displaystyle \quad k=0,\ldots ,n}$ ,

называется кривой Безье.

Многочлен ${\displaystyle b_{k,n}(t)}$ степени ${\displaystyle n}$ по параметру ${\displaystyle t}$ называется базисной функцией (соответствующей контрольной точке ${\displaystyle \mathbf {P} _{k}}$ ) кривой Безье или полиномом Бернштейна .

Здесь ${\displaystyle {n \choose k}={\frac {n!}{k!(n-k)!}}}$ — число сочетаний из ${\displaystyle n}$ по ${\displaystyle k}$ .

Замечания

1. Кривая Безье, соответствующая как ${\displaystyle (\mathbf {P} _{0})}$ так и ${\displaystyle (\mathbf {P} _{0},\mathbf {P} _{0},\ldots ,\mathbf {P} _{0})}$ , есть точка ${\displaystyle \mathbf {P} _{0}}$ .
2. Кривая Безье, соответствующая паре ${\displaystyle (\mathbf {P} _{0},\mathbf {P} _{1})}$ , то есть, при ${\displaystyle n=1}$ , есть (линейно) параметризованный отрезок, соединяющий точку ${\displaystyle \mathbf {P} _{0}}$ (при ${\displaystyle t=0}$ ) с точкой ${\displaystyle \mathbf {P} _{1}}$ (при ${\displaystyle t=1}$ ).
3. При любом порядке ${\displaystyle n\geqslant 0}$ кривая Безье содержит как точку ${\displaystyle \mathbf {P} _{0}}$ (это — образ параметра ${\displaystyle t=0}$ ), так и точку ${\displaystyle \mathbf {P} _{n}}$ (это — образ параметра ${\displaystyle t=1}$ ).
4. Кривая Безье (в общем случае, то есть, если не выродилась в точку ${\displaystyle \mathbf {P} _{0}}$ ) ориентируема, поскольку является образом ориентированного отрезка ${\displaystyle [0;1]}$ . Последовательностям контрольных точек ${\displaystyle (\mathbf {P} _{0},\mathbf {P} _{1},\ldots ,\mathbf {P} _{n-1},\mathbf {P} _{n})}$ и ${\displaystyle (\mathbf {P} _{n},\mathbf {P} _{n-1},\ldots ,\mathbf {P} _{1},\mathbf {P} _{0})}$ соответствуют кривые Безье, которые совпадают как множества точек, но имеют (в общем случае) противоположные ориентации.
5. Кривые Безье, соответствующие последовательностям контрольных точек ${\displaystyle (\mathbf {P} _{0},\mathbf {P} _{1},\mathbf {P} _{2})}$ и ${\displaystyle (\mathbf {P} _{0},\mathbf {P} _{2},\mathbf {P} _{1})}$ , при ${\displaystyle \mathbf {P} _{1}\neq \mathbf {P} _{2}}$ не совпадают.
6. Если изменить ${\displaystyle (x_{j,0},\ldots ,x_{j,n})}$ , то изменяется только ${\displaystyle z_{j}(t)}$ .

Виды кривых Безье

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

При n = 1 кривая представляет собой отрезок прямой линии, опорные точки P ₀ и P ₁ определяют его начало и конец. Кривая задаётся уравнением:

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

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

Квадратичная кривая Безье (n = 2) задаётся тремя опорными точками: P ₀ , P ₁ и P ₂ .

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

Квадратичные кривые Безье в составе сплайнов используются для описания формы символов в шрифтах TrueType и в SWF -файлах.

${\displaystyle t={\frac {\mathbf {P} _{0}-\mathbf {P} _{1}\pm {\sqrt {(\mathbf {P} _{0}-2\mathbf {P} _{1}+\mathbf {P} _{2})\mathbf {B} +\mathbf {P} _{1}^{2}-\mathbf {P} _{0}\mathbf {P} _{2}}}}{\mathbf {P} _{0}-2\mathbf {P} _{1}+\mathbf {P} _{2}}},\quad \mathbf {P} _{0}-2\mathbf {P} _{1}+\mathbf {P} _{2}\neq 0}$

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

${\displaystyle t={\sqrt {\frac {\mathbf {B} -\mathbf {P} _{0}}{\mathbf {P} _{2}-\mathbf {P} _{1}}}},\quad \mathbf {P} _{0}=\mathbf {P} _{1}\neq \mathbf {P} _{2}}$

Кубические кривые

В параметрической форме кубическая кривая Безье (n = 3) описывается следующим уравнением:

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

Четыре опорные точки P ₀ , P ₁ , P ₂ и P ₃ , заданные в 2- или 3-мерном пространстве, определяют форму кривой.

Линия берёт начало из точки P ₀ , направляясь к P ₁ и заканчивается в точке P ₃ , подходя к ней со стороны P ₂ . То есть, кривая не проходит через точки P ₁ и P ₂ , они используются для указания её направления. Длина отрезка между P ₀ и P ₁ определяет, как скоро кривая повернёт к P ₃ .

В матричной форме кубическая кривая Безье записывается следующим образом:

${\displaystyle \mathbf {B} (t)={\begin{bmatrix}t^{3}&t^{2}&t&1\end{bmatrix}}\mathbf {M} _{B}{\begin{bmatrix}\mathbf {P} _{0}\\\mathbf {P} _{1}\\\mathbf {P} _{2}\\\mathbf {P} _{3}\end{bmatrix}}}$ ,

где ${\displaystyle \mathbf {M} _{B}}$ называется базисной матрицей Безье:

${\displaystyle \mathbf {M} _{B}={\begin{bmatrix}-1&3&-3&1\\3&-6&3&0\\-3&3&0&0\\1&0&0&0\end{bmatrix}}}$

В современных графических системах и форматах, таких как PostScript (а также основанные на нём форматы Adobe Illustrator и Portable Document Format (PDF) ), Scalable Vector Graphics (SVG) , Metafont , CorelDraw и GIMP для представления криволинейных форм используются сплайны Безье, составленные из кубических кривых.

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

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

Параметр t в функции, описывающей линейный случай кривой Безье, определяет, где именно на расстоянии от P ₀ до P ₁ находится B ( t ). Например, при t = 0,25 значение функции B ( t ) соответствует четверти расстояния между точками P ₀ и P ₁ . Параметр t изменяется от 0 до 1, а B ( t ) описывает отрезок прямой между точками P ₀ и P ₁ .

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

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

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

Кривые высших степеней

Для построения кривых высших порядков соответственно требуется больше промежуточных точек. Для кубической кривой это промежуточные точки Q ₀ , Q ₁ и Q ₂ , описывающие линейные кривые, а также точки R ₀ и R ₁ , которые описывают квадратичные кривые: более простое уравнение ${\displaystyle {\frac {P_{0}Q_{0}}{P_{0}P_{1}}}={\frac {Q_{1}P_{1}}{P_{1}P_{2}}}={\frac {BR_{0}}{R_{1}R_{0}}}}$ .

Для кривых четвёртой степени это будут точки Q ₀ , Q ₁ , Q ₂ и Q ₃ , описывающие линейные кривые, R ₀ , R ₁ и R ₂ , которые описывают квадратичные кривые, а также точки S ₀ и S ₁ , описывающие кубические кривые Безье:

Свойства кривой Безье

• непрерывность заполнения сегмента между начальной и конечной точками;
• кривая всегда располагается внутри фигуры, образованной линиями, соединяющими контрольные точки;
• при наличии только двух контрольных точек сегмент представляет собой прямую линию;
• прямая линия образуется при коллинеарном (на одной прямой) размещении управляющих точек;
• кривая Безье симметрична, то есть обмен местами между начальной и конечной точками (изменение направления траектории) не влияет на форму кривой;
• масштабирование и изменение пропорций кривой Безье не нарушает её стабильности, поскольку с математической точки зрения она « аффинно инвариантна»;
• изменение координат хотя бы одной из точек ведет к изменению формы всей кривой Безье;
• любой частичный отрезок кривой Безье также является кривой Безье;
• степень (порядок) кривой всегда на одну ступень меньше числа контрольных точек. Например, при трёх контрольных точках форма кривой — парабола , так как парабола — кривая 2-го порядка;
• окружность не может быть описана параметрическим уравнением кривой Безье;
• невозможно создать параллельные кривые Безье, за исключением тривиальных случаев (прямые линии и совпадающие кривые), хотя существуют алгоритмы, строящие приближённую параллельную кривую Безье с приемлемой для практики точностью.

Применение в компьютерной графике

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

Наибольшее значение имеют кривые Безье второй и третьей степеней (квадратичные и кубические). Кривые высших степеней при обработке требуют большего объёма вычислений и для практических целей используются реже. Для построения сложных по форме линий отдельные кривые Безье могут быть последовательно соединены друг с другом в сплайн Безье . Для того, чтобы обеспечить гладкость линии в месте соединения двух кривых, три смежные опорные точки обеих кривых должны лежать на одной прямой. В программах векторной графики , например Adobe Illustrator или Inkscape , подобные фрагменты известны под названием «путей» ( path ), а в 3DS Max и подобных программах 3D-моделирования кривые Безье имеют название «сплайны».

Преобразование квадратичных кривых Безье в кубические

Квадратичная кривая Безье с координатами ${\displaystyle (x_{0};y_{0}),\,(x_{1};y_{1}),\,(x_{2};y_{2})}$ преобразовывается в кубическую кривую Безье с координатами ${\displaystyle (x_{0};y_{0}),\,\left(x_{0}+{\frac {2\cdot (x_{1}-x_{0})}{3}};y_{0}+{\frac {2\cdot (y_{1}-y_{0})}{3}}\right),\,\left(x_{1}+{\frac {x_{2}-x_{1}}{3}};y_{1}+{\frac {y_{2}-y_{1}}{3}}\right),\,(x_{2};y_{2})}$ .

Уровень дискретизации Кривых Безье

Уровень дискретизации определяется следующим образом:

${\displaystyle |B_{next}-B_{prev}|=1}$

, то есть каждая следующая точка должна отличаться от предыдущей на 1 (допустим пиксель). Причём, если задать ${\displaystyle B}$ следующим образом:

${\displaystyle \left\vert \sum _{k=0}^{n}{{\frac {n!}{k!\times (n-k)!}}\times t_{next}^{k}\times (1-t_{next})^{n-k}\times P_{k}}-\sum _{k=0}^{n}{{\frac {n!}{k!\times (n-k)!}}\times t_{prev}^{k}\times (1-t_{prev})^{n-k}\times P_{k}}\right\vert =1}$

Через него можно вычислить ${\displaystyle \Delta {t}}$ .

Решим это уравнение для кривых Безье первого порядка (линейных):

${\displaystyle B(t)=(1-t)\times P_{0}+t\times P_{1},0\leq t\leq 1}$

${\displaystyle B(t)={\begin{cases}x=(1-t)\times P_{0_{x}}+t\times P_{1_{x}}\\y=(1-t)\times P_{0_{y}}+t\times P_{1_{y}}\end{cases}}}$

Запишем разницу точек для одной оси:

${\displaystyle {\left\vert P_{0}-t_{next}\times P_{0}+t_{next}\times P_{1}-P_{0}+t_{prev}\times P_{0}-t_{prev}\times P_{1}\right\vert }=1}$

Вынесем общие множители за скобки:

${\displaystyle {\left\vert t_{next}\times (P_{0}-P_{1})-t_{prev}\times (P_{0}-P_{1})\right\vert }=1}$

Найдём ${\displaystyle \Delta {t}}$ :

${\displaystyle \Delta {t}={\left\vert t_{next}-t_{prev}\right\vert }=\left\vert {\frac {1}{P_{0}-P_{1}}}\right\vert }$

так можно вычислить уровень дискретизации для обхода конкретной оси кривой Безье определённого порядка. То есть Вам нужно получить 16 таких уравнений для кривых Безье с 1го по 16 порядок, она всегда задаётся точками, их координаты достаточно будет подставить в полученное уравнение, чтобы обойти кривую с минимальным однозначным уровнем дискретизации.

См. также

• Поверхность Безье
• NURBS
• B-сплайн
• Кривые

Примечания

Литература

• Роджерс Д., Адамс Дж. Математические основы машинной графики. — М. : Мир, 2001.

Ссылки

• Wolfram Math World (англ.)
• American Mathematical Society (англ.)
• Кривые Безье в компьютерных играх (рус.)
• (рус.)