Кривая Безье
Кривы́е Безье́ — типы кривых, предложенные в 60-х годах XX века независимо друг от друга Пьером Безье из автомобилестроительной компании «Рено» и Полем де Кастельжо из компании «Ситроен», где применялись для проектирования кузовов автомобилей.
Несмотря на то, что открытие де Кастельжо было сделано несколько ранее Безье (1959), его исследования не публиковались и скрывались компанией как производственная тайна до конца 1960-х.
Кривая Безье является частным случаем многочленов Бернштейна, описанных русским математиком Сергеем Натановичем Бернштейном в 1912 году.
Впервые кривые были представлены широкой публике в 1962 году французским инженером Пьером Безье, который, разработав их независимо от де Кастельжо, использовал их для компьютерного проектирования автомобильных кузовов. Кривые были названы именем Безье, а именем де Кастельжо назван разработанный им рекурсивный способ определения кривых (алгоритм де Кастельжо).
Впоследствии это открытие стало одним из важнейших инструментов систем автоматизированного проектирования и программ компьютерной графики.
Определение
Пусть в пространстве [math]\displaystyle{ \mathbb{R}^m }[/math] размерности [math]\displaystyle{ m \geqslant 1 }[/math] над [math]\displaystyle{ \mathbb{R} }[/math] задана последовательность контрольных точек [math]\displaystyle{ (\mathbf{P}_{0}, \ldots, \mathbf{P}_{n}) }[/math], где [math]\displaystyle{ n \geqslant 0 }[/math], а [math]\displaystyle{ \mathbf{P}_k=(x_{1,k},\ldots,x_{m,k}) }[/math] для [math]\displaystyle{ k=0,\ldots,n }[/math].
Тогда множество [math]\displaystyle{ \left\{\mathbf{B}(t)|0\leqslant t\leqslant 1\right\} }[/math] точек [math]\displaystyle{ \mathbf{B}(t)=(z_{1}(t),\ldots,z_{m}(t)) }[/math] с координатами [math]\displaystyle{ (z_{j}(t))_{j=1,\ldots,m} }[/math], параметрически задаваемыми выражениями
- [math]\displaystyle{ z_{j}(t)=\sum^n_{k=0} x_{j,k} b_{k,n}(t) \quad }[/math] для [math]\displaystyle{ \quad 0\leqslant t\leqslant 1, \quad }[/math] где [math]\displaystyle{ \quad j=1,\ldots,m, \quad }[/math] а [math]\displaystyle{ \quad b_{k,n}(t)={n \choose k} t^k(1-t)^{n-k} \quad }[/math] для [math]\displaystyle{ \quad k=0,\ldots,n }[/math],
называется кривой Безье.
Многочлен [math]\displaystyle{ b_{k,n}(t) }[/math] степени [math]\displaystyle{ n }[/math] по параметру [math]\displaystyle{ t }[/math] называется базисной функцией (соответствующей контрольной точке [math]\displaystyle{ \mathbf{P}_{k} }[/math]) кривой Безье или полиномом Бернштейна.
Здесь [math]\displaystyle{ {n \choose k}=\frac{n!}{k!(n-k)!} }[/math] — число сочетаний из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k }[/math].
Замечания
- Кривая Безье, соответствующая как [math]\displaystyle{ (\mathbf{P}_{0}) }[/math] так и [math]\displaystyle{ (\mathbf{P}_{0}, \mathbf{P}_{0}, \ldots, \mathbf{P}_{0}) }[/math], есть точка [math]\displaystyle{ \mathbf{P}_{0} }[/math].
- Кривая Безье, соответствующая паре [math]\displaystyle{ (\mathbf{P}_{0}, \mathbf{P}_{1}) }[/math], то есть, при [math]\displaystyle{ n=1 }[/math], есть (линейно) параметризованный отрезок, соединяющий точку [math]\displaystyle{ \mathbf{P}_{0} }[/math] (при [math]\displaystyle{ t=0 }[/math]) с точкой [math]\displaystyle{ \mathbf{P}_{1} }[/math] (при [math]\displaystyle{ t=1 }[/math]).
- При любом порядке [math]\displaystyle{ n\geqslant 0 }[/math] кривая Безье содержит как точку [math]\displaystyle{ \mathbf{P}_{0} }[/math] (это — образ параметра [math]\displaystyle{ t = 0 }[/math]), так и точку [math]\displaystyle{ \mathbf{P}_{n} }[/math] (это — образ параметра [math]\displaystyle{ t = 1 }[/math]).
- Кривая Безье (в общем случае, то есть, если не выродилась в точку [math]\displaystyle{ \mathbf{P}_{0} }[/math]) ориентируема, поскольку является образом ориентированного отрезка [math]\displaystyle{ [0;1] }[/math]. Последовательностям контрольных точек [math]\displaystyle{ (\mathbf{P}_{0}, \mathbf{P}_{1}, \ldots, \mathbf{P}_{n-1}, \mathbf{P}_{n}) }[/math] и [math]\displaystyle{ (\mathbf{P}_{n}, \mathbf{P}_{n-1}, \ldots, \mathbf{P}_{1}, \mathbf{P}_{0}) }[/math] соответствуют кривые Безье, которые совпадают как множества точек, но имеют (в общем случае) противоположные ориентации.
- Кривые Безье, соответствующие последовательностям контрольных точек [math]\displaystyle{ (\mathbf{P}_{0}, \mathbf{P}_{1}, \mathbf{P}_{2}) }[/math] и [math]\displaystyle{ (\mathbf{P}_{0}, \mathbf{P}_{2}, \mathbf{P}_{1}) }[/math], при [math]\displaystyle{ \mathbf{P}_{1} \neq \mathbf{P}_{2} }[/math] не совпадают.
- Если изменить [math]\displaystyle{ (x_{j,0},\ldots,x_{j,n}) }[/math], то изменяется только [math]\displaystyle{ z_{j}(t) }[/math].
Виды кривых Безье
Линейные кривые
При n = 1 кривая представляет собой отрезок прямой линии, опорные точки P0 и P1 определяют его начало и конец. Кривая задаётся уравнением:
- [math]\displaystyle{ \mathbf{B}(t)=(1-t)\mathbf{P}_0 + t\mathbf{P}_1 \quad t \in [0,1] }[/math].
Квадратичные кривые
Квадратичная кривая Безье (n = 2) задаётся тремя опорными точками: P0, P1 и P2.
- [math]\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] }[/math].
Квадратичные кривые Безье в составе сплайнов используются для описания формы символов в шрифтах TrueType и в SWF-файлах.
- [math]\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 }[/math]
- [math]\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 }[/math]
- [math]\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 }[/math]
Кубические кривые
В параметрической форме кубическая кривая Безье (n = 3) описывается следующим уравнением:
- [math]\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] }[/math].
Четыре опорные точки P0, P1, P2 и P3, заданные в 2- или 3-мерном пространстве, определяют форму кривой.
Линия берёт начало из точки P0, направляясь к P1 и заканчивается в точке P3, подходя к ней со стороны P2. То есть, кривая не проходит через точки P1 и P2, они используются для указания её направления. Длина отрезка между P0 и P1 определяет, как скоро кривая повернёт к P3.
В матричной форме кубическая кривая Безье записывается следующим образом:
- [math]\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} }[/math],
где [math]\displaystyle{ \mathbf{M}_B }[/math] называется базисной матрицей Безье:
- [math]\displaystyle{ \mathbf{M}_B = \begin{bmatrix}-1&3&-3&1\\3&-6&3&0\\-3&3&0&0\\1&0&0&0\end{bmatrix} }[/math]
В современных графических системах и форматах, таких как PostScript (а также основанные на нём форматы Adobe Illustrator и Portable Document Format (PDF)), Scalable Vector Graphics (SVG)[1], Metafont, CorelDraw и GIMP для представления криволинейных форм используются сплайны Безье, составленные из кубических кривых.
Построение кривых Безье
Линейные кривые
Параметр t в функции, описывающей линейный случай кривой Безье, определяет, где именно на расстоянии от P0 до P1 находится B(t). Например, при t = 0,25 значение функции B(t) соответствует четверти расстояния между точками P0 и P1. Параметр t изменяется от 0 до 1, а B(t) описывает отрезок прямой между точками P0 и P1.
![]() |
Квадратичные кривые
Для построения квадратичных кривых Безье требуется выделение двух промежуточных точек Q0 и Q1 из условия, чтобы параметр t изменялся от 0 до 1:
- Точка Q0 изменяется от P0 до P1 и описывает линейную кривую Безье.
- Точка Q1 изменяется от P1 до P2 и также описывает линейную кривую Безье.
- Точка B изменяется от Q0 до Q1 и описывает квадратичную кривую Безье.
![]() |
Кривые высших степеней
Для построения кривых высших порядков соответственно требуется больше промежуточных точек. Для кубической кривой это промежуточные точки Q0, Q1 и Q2, описывающие линейные кривые, а также точки R0 и R1, которые описывают квадратичные кривые: более простое уравнение [math]\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}} }[/math].
![]() |
Для кривых четвёртой степени это будут точки Q0, Q1, Q2 и Q3, описывающие линейные кривые, R0, R1 и R2, которые описывают квадратичные кривые, а также точки S0 и S1, описывающие кубические кривые Безье:
![]() |
Свойства кривой Безье
![](https://cdn.xn--h1ajim.xn--p1ai/thumb.php?f=Bezier_curve.png&width=300)
- непрерывность заполнения сегмента между начальной и конечной точками;
- кривая всегда располагается внутри фигуры, образованной линиями, соединяющими контрольные точки;
- при наличии только двух контрольных точек сегмент представляет собой прямую линию;
- прямая линия образуется при коллинеарном (на одной прямой) размещении управляющих точек;
- кривая Безье симметрична, то есть обмен местами между начальной и конечной точками (изменение направления траектории) не влияет на форму кривой;
- масштабирование и изменение пропорций кривой Безье не нарушает её стабильности, поскольку с математической точки зрения она «аффинно инвариантна»;
- изменение координат хотя бы одной из точек ведет к изменению формы всей кривой Безье;
- любой частичный отрезок кривой Безье также является кривой Безье;
- степень (порядок) кривой всегда на одну ступень меньше числа контрольных точек. Например, при трёх контрольных точках форма кривой — парабола, так как парабола — кривая 2-го порядка;
- окружность не может быть описана параметрическим уравнением кривой Безье;
- невозможно создать параллельные кривые Безье, за исключением тривиальных случаев (прямые линии и совпадающие кривые), хотя существуют алгоритмы, строящие приближённую параллельную кривую Безье с приемлемой для практики точностью.
Применение в компьютерной графике
Благодаря простоте задания и манипуляции кривые Безье нашли широкое применение в компьютерной графике для моделирования гладких линий. Кривая целиком лежит в выпуклой оболочке своих опорных точек. Это свойство кривых Безье с одной стороны значительно облегчает задачу нахождения точек пересечения кривых (если не пересекаются выпуклые оболочки опорных точек, то не пересекаются и сами кривые), а с другой стороны позволяет осуществлять интуитивно понятное управление параметрами кривой в графическом интерфейсе с помощью её опорных точек. Кроме того, аффинные преобразования кривой (перенос, масштабирование, вращение и др.) также могут быть осуществлены путём применения соответствующих трансформаций к опорным точкам.
Наибольшее значение имеют кривые Безье второй и третьей степеней (квадратичные и кубические). Кривые высших степеней при обработке требуют большего объёма вычислений и для практических целей используются реже. Для построения сложных по форме линий отдельные кривые Безье могут быть последовательно соединены друг с другом в сплайн Безье. Для того, чтобы обеспечить гладкость линии в месте соединения двух кривых, три смежные опорные точки обеих кривых должны лежать на одной прямой. В программах векторной графики, например Adobe Illustrator или Inkscape, подобные фрагменты известны под названием «путей» (path), а в 3DS Max и подобных программах 3D-моделирования кривые Безье имеют название «сплайны».
Преобразование квадратичных кривых Безье в кубические
Квадратичная кривая Безье с координатами [math]\displaystyle{ (x_0;y_0),\,(x_1;y_1),\,(x_2;y_2) }[/math] преобразовывается в кубическую кривую Безье с координатами [math]\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) }[/math].
Уровень дискретизации Кривых Безье[2]
Уровень дискретизации определяется следующим образом:
[math]\displaystyle{ |B_{next}-B_{prev}|=1 }[/math]
, то есть каждая следующая точка должна отличаться от предыдущей на 1 (допустим пиксель). Причём, если задать [math]\displaystyle{ B }[/math] следующим образом:
[math]\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 }[/math]
Через него можно вычислить [math]\displaystyle{ \Delta{t} }[/math].
Решим это уравнение для кривых Безье первого порядка (линейных):
[math]\displaystyle{ B(t) = (1-t)\times P_0 + t \times P_1, 0\leq t\leq1 }[/math]
[math]\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} }[/math]
Запишем разницу точек для одной оси:
[math]\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 }[/math]
Вынесем общие множители за скобки:
[math]\displaystyle{ {\left \vert t_{next} \times (P_0-P_1) - t_{prev} \times (P_0-P_1)\right \vert} = 1 }[/math]
Найдём [math]\displaystyle{ \Delta{t} }[/math]:
[math]\displaystyle{ \Delta{t}={\left \vert t_{next} - t_{prev}\right \vert} = \left \vert \frac{1}{P_0-P_1} \right \vert }[/math]
так можно вычислить уровень дискретизации для обхода конкретной оси кривой Безье определённого порядка. То есть Вам нужно получить 16 таких уравнений для кривых Безье с 1го по 16 порядок, она всегда задаётся точками, их координаты достаточно будет подставить в полученное уравнение, чтобы обойти кривую с минимальным однозначным уровнем дискретизации.
См. также
Примечания
- ↑ World Wide Web Consortium (W3C). Scalable Vector Graphics (SVG) 1.1 (Second Edition). Chapter 8: Paths (англ.) (16 августа 2011). — W3C Recommendation. Дата обращения: 21 мая 2012. Архивировано 24 июня 2012 года.
- ↑ Алгоритмы: Кривые Безье . designermanuals.blogspot.com. Дата обращения: 9 января 2021. Архивировано 12 января 2021 года.
Литература
- Роджерс Д., Адамс Дж. Математические основы машинной графики. — М.: Мир, 2001.
Ссылки
- Wolfram Math World Bézier Curve (англ.)
- American Mathematical Society From Bézier to Bernstein (англ.)
- Кривые Безье в компьютерных играх [1] (рус.)
- Часы на кривых Безье (рус.)
- A Primer on Bézier Curves