Кривая Безье

Кривы́е Безье́— типы кривых, предложенные в 60-х годах XX века независимо друг от другаПьером Безьеиз автомобилестроительной компании «Рено» иПолем де Кастельжоиз компании «Ситроен», где применялись для проектирования кузовов автомобилей.
Несмотря на то, что открытие де Кастельжо было сделано несколько ранее Безье (1959), его исследования не публиковались и скрывались компанией какпроизводственная тайнадо конца 1960-х.
Кривая Безье является частным случаеммногочленов Бернштейна, описанных русским математикомСергеем Натановичем Бернштейномв 1912 году.
Впервые кривые были представлены широкой публике в1962 годуфранцузским инженером Пьером Безье, который, разработав их независимо от де Кастельжо, использовал их для компьютерного проектированияавтомобильныхкузовов. Кривые были названы именем Безье, а именем де Кастельжо назван разработанный им рекурсивный способ определения кривых (алгоритм де Кастельжо).
Впоследствии это открытие стало одним из важнейших инструментовсистем автоматизированного проектированияи программкомпьютерной графики.
Пусть в пространствеRm{\displaystyle \mathbb {R} ^{m}}размерностиm⩾1{\displaystyle m\geqslant 1}надR{\displaystyle \mathbb {R} }задана последовательность контрольных точек(P0,…,Pn){\displaystyle (\mathbf {P} _{0},\ldots ,\mathbf {P} _{n})},
гдеn⩾0{\displaystyle n\geqslant 0},
аPk=(x1,k,…,xm,k){\displaystyle \mathbf {P} _{k}=(x_{1,k},\ldots ,x_{m,k})}дляk=0,…,n{\displaystyle k=0,\ldots ,n}.
Тогда множество{B(t)|0⩽t⩽1}{\displaystyle \left\{\mathbf {B} (t)|0\leqslant t\leqslant 1\right\}}точекB(t)=(z1(t),…,zm(t)){\displaystyle \mathbf {B} (t)=(z_{1}(t),\ldots ,z_{m}(t))}с координатами(zj(t))j=1,…,m{\displaystyle (z_{j}(t))_{j=1,\ldots ,m}}, параметрически задаваемыми выражениями
называетсякривойБезье.
Многочленbk,n(t){\displaystyle b_{k,n}(t)}степениn{\displaystyle n}по параметруt{\displaystyle t}называется базисной функцией (соответствующей контрольной точкеPk{\displaystyle \mathbf {P} _{k}}) кривой Безье илиполиномом Бернштейна.
Здесь(nk)=n!k!(n−k)!{\displaystyle {n \choose k}={\frac {n!}{k!(n-k)!}}}— числосочетанийизn{\displaystyle n}поk{\displaystyle k}.
При n = 1 кривая представляет собой отрезок прямой линии, опорные точкиP0иP1определяют его начало и конец. Кривая задаётся уравнением:
Квадратичная кривая Безье (n = 2) задаётся тремя опорными точками:P0,P1иP2.
Квадратичные кривые Безье в составесплайновиспользуются для описания формы символов в шрифтахTrueTypeи вSWF-файлах.
В параметрической форме кубическая кривая Безье (n = 3) описывается следующим уравнением:
Четыре опорные точкиP0,P1,P2иP3, заданные в 2- или 3-мерном пространстве, определяют форму кривой.
Линия берёт начало из точкиP0, направляясь кP1и заканчивается в точкеP3, подходя к ней со стороныP2. То есть, кривая не проходит через точкиP1иP2, они используются для указания её направления. Длина отрезка междуP0иP1определяет, как скоро кривая повернёт кP3.
В матричной форме кубическая кривая Безье записывается следующим образом:
гдеMB{\displaystyle \mathbf {M} _{B}}называется базисной матрицей Безье:
В современных графических системах и форматах, таких какPostScript(а также основанных на нём форматахAdobe IllustratorиPortable Document Format (PDF)),Scalable Vector Graphics (SVG),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,Q1иQ2, описывающие линейные кривые, а также точкиR0иR1, которые описывают квадратичные кривые: более простое уравнениеP0Q0P0P1=Q1P1P1P2=BR0R1R0{\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}}}}.
Для кривых четвёртой степени это будут точкиQ0,Q1,Q2иQ3, описывающие линейные кривые,R0,R1иR2, которые описывают квадратичные кривые, а также точкиS0иS1, описывающие кубические кривые Безье:
Благодаря простоте задания и манипуляции кривые Безье нашли широкое применение вкомпьютерной графикедля моделирования гладких линий. Кривая целиком лежит ввыпуклой оболочкесвоих опорных точек. Это свойство кривых Безье с одной стороны значительно облегчает задачу нахождения точек пересечения кривых (если не пересекаютсявыпуклые оболочкиопорных точек, то не пересекаются и сами кривые), а с другой стороны позволяет осуществлять интуитивно понятное управление параметрами кривой вграфическом интерфейсес помощью её опорных точек. Кроме того,аффинные преобразованиякривой (перенос,масштабирование,вращениеи др.) также могут быть осуществлены путём применения соответствующих трансформаций к опорным точкам.
Наибольшее значение имеют кривые Безье второй и третьей степеней (квадратичные и кубические). Кривые высших степеней при обработке требуют большего объёма вычислений и для практических целей используются реже. Для построения сложных по форме линий отдельные кривые Безье могут быть последовательно соединены друг с другом всплайнБезье. Для того, чтобы обеспечить гладкость линии в месте соединения двух кривых, три смежные опорные точки обеих кривых должны лежать на одной прямой. В программахвекторной графики, напримерAdobe IllustratorилиInkscape, подобные фрагменты известны под названием «путей» (path), а в3DS Maxи подобных программах3D-моделированиякривые Безье имеют название «сплайны».
Квадратичная кривая Безье с координатами(x0;y0),(x1;y1),(x2;y2){\displaystyle (x_{0};y_{0}),\,(x_{1};y_{1}),\,(x_{2};y_{2})}преобразовывается в кубическую кривую Безье с координатами(x0;y0),(x0+2⋅(x1−x0)3;y0+2⋅(y1−y0)3),(x1+x2−x13;y1+y2−y13),(x2;y2){\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})}.
Уровень дискретизации определяется следующим образом:
|Bnext−Bprev|=1{\displaystyle |B_{next}-B_{prev}|=1}
, то есть каждая следующая точка должна отличаться от предыдущей на 1 (допустим пиксель). Причём, если задатьB{\displaystyle B}следующим образом:
|∑k=0nn!k!×(n−k)!×tnextk×(1−tnext)n−k×Pk−∑k=0nn!k!×(n−k)!×tprevk×(1−tprev)n−k×Pk|=1{\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}
Через него можно вычислитьΔt{\displaystyle \Delta {t}}.
Решим это уравнение для кривых Безье первого порядка (линейных):
B(t)=(1−t)×P0+t×P1,0≤t≤1{\displaystyle B(t)=(1-t)\times P_{0}+t\times P_{1},0\leq t\leq 1}
B(t)={x=(1−t)×P0x+t×P1xy=(1−t)×P0y+t×P1y{\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}}}
Запишем разницу точек для одной оси:
|P0−tnext×P0+tnext×P1−P0+tprev×P0−tprev×P1|=1{\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}
Вынесем общие множители за скобки:
|tnext×(P0−P1)−tprev×(P0−P1)|=1{\displaystyle {\left\vert t_{next}\times (P_{0}-P_{1})-t_{prev}\times (P_{0}-P_{1})\right\vert }=1}
НайдёмΔt{\displaystyle \Delta {t}}:
Δt=|tnext−tprev|=|1P0−P1|{\displaystyle \Delta {t}={\left\vert t_{next}-t_{prev}\right\vert }=\left\vert {\frac {1}{P_{0}-P_{1}}}\right\vert }
так можно вычислить уровень дискретизации для обходаконкретной осикривой Безье определённого порядка. То есть Вам нужно получить 16 таких уравнений для кривых Безье с 1го по 16 порядок, она всегда задаётся точками, их координаты достаточно будет подставить в полученное уравнение, чтобы обойти кривую с минимальным однозначным уровнем дискретизации.