• Алгоритмы

Простые в использовании кривые Безье

Простая и понятная реализация известных кривых Безье на C#.

Введение

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

Краткие сведения

Кривые Безье - параметрические кривые, в значительной степени настраиваемые и гладкие, хорошо подходят для многих задач. Они были названы в честь Пьера Безье, французского математика и инженера, разработавшего данный метод компьютерного черчения в конце 1960 г. во время работы в автомобилестроительной фирме Рено. Говорят, что одновременно такая же разработка возникла в ходе исследования Форда. До сих пор неясно, кто первым создал их.

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

Алгоритм построения кривой Безье

Рассмотрим n+1 точек P0,…,Pnи соединим точки в ломаную линию, называемую далее контрольным полигоном.

При наличии точек Pi, i = 0,...,n, наша задача – определить кривую g (t) для всех значений t ? [0,1]. Идея показана ниже:

Основной алгоритм

 

Здесь цель – найти точки в середине между двумя соседними точками и повторять это до тех пор, пока все повторы не будут исчерпаны. Новые значения точек дадут кривую. Известное уравнение Безье – точная формулировка данной идеи. Here is the algorithm:

Шаг 1: Выбрать значение t ? [0,1]. Это значение не меняется на всех остальных шагах.

Шаг 2: Установить Pi[0] (t) = Pi, для i = 0,...,n.

Шаг 3: Длч j= 0,...,n, установить                  для i = j,...,n.

Шаг 4: g (t) = Pn[n] (t)

Частный и общий случаи

Здесь будут даны формулы для общего и частного случаев, полезные в определенных применениях. Код в статье не показывает ни одну из них, но он использует обобщенную формулу. Начнем с обобщенной формулы:

Для простоты и соглашения, используемого в данной статье и коде, лучше представить эту формулу так:

Это уравнение является лишь формулировкой вышеуказанного алгоритма (итерации по средним точкам). Немаловажно, что весь алгоритм может быть сведен в формулу, и непосредственная реализация может дать правильные результаты. Здесь nобозначает количество точек, а Pобозначает сами точки. Факториальные коэффициенты точек называются базисными функциями Бернштейна, по имени их создателя.

Здесь частные случаи:

Линейный Безье:

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

Безье третьей степени:

Объяснение и использование кода

Это функция, делающая всю работу. Она очень короткая и очень простая. Так как мы имеем дело только с двумерными кривыми, точки имеют только координаты Xи Y. Функция вычисляет точки Безье.

public void Bezier2D(double[] b, int cpts, double[] p)
{
int npts = (b.Length) / 2;
int icount, jcount;
double step, t;

// Вычисляем точки на кривой

icount = 0;
t = 0;
step = (double)1.0 / (cpts - 1);

for (int i1 = 0; i1 != cpts; i1++)
{
if ((1.0 - t) < 5e-6)
t = 1.0;

jcount = 0;
p[icount] = 0.0;
p[icount + 1] = 0.0;
for (int i = 0; i != npts; i++)
{
double basis = Bernstein(npts - 1, i, t);
p[icount] += basis * b[jcount];
p[icount + 1] += basis * b[jcount + 1];
jcount = jcount +2;
}

icount += 2;
t += step;
}
}

Остальные функции – лишь вспомогательные функции, участвующие в факториальных вычислениях и расчетах базисных функций, являющихся довольно тривиальными. Чтобы правильно использовать данную функцию, передайте ей набор точек в формате: XYXYXYXYXYXYXYXYXYXY.... координаты, и сколько точек вам нужно рассчитать на кривой. Функция заполнит массив pточками траектории.

Интересные особенности

Из-за ограничений факториальных вычислений код рассчитывает кривые только до 32 точек. Более сложные конструкции обычно представляются с помощью комбинации данных кривых (как в AdobePhotoshop, Illustratorи Flash– инструмент траектории).

Хотя GDI (интерфейс графических устройств) имеет встроенную функцию расчета кривой Безье, для обучения нежелательно использовать встроенные библиотеки. GDI не всегда сможет делать работу за вас! Где-то, когда-то, вам может понадобиться реализовать ее, и к тому времени вы должны примерно представлять, как работают эти кривые.

Загрузить исходный код