Алгоритм Брезенхема рисования линии

В 1965 году Брезенхеймом был предложен простой целочисленный алгоритм для растрового построения отрезка. В алгоритме используется управляющая переменная d_i, которая на каждом шаге пропорциональна разности между s и t (см. рис.2.4.1). На рис.2.4.1 приведен i-ый шаг, когда пиксел P_i-1 уже найден как ближайший к реальному изображаемому отрезку, и теперь требуется определить, какой из пикселов должен быть установлен следующим: T_i или S_i.

Если s<t, то S_i ближе к отрезку и необходимо выбрать его; в противном случае ближе будет T_i. Другими словами, если s-t<0, то выбирается S_i; в противном случае выбирается T_i.

рис. 2.4.1.

Изображаемый отрезок проводится из точки (x₁, y₁) в точку (x₂, y₂). Пусть первая точка находится ближе к началу координат, тогда перенесем обе точки, T(x₁, y₁) так, чтобы начальная точка отрезка оказалась в начале координат, тогда конечная окажется в (D x, D y), где D x= x₂- x₁, D y= x₂- x₁. Уравнение прямой теперь имеет вид y=x× D y/Dx. Из рисунка следует, что

поэтому

помножим на D x:

так как D x>0, величину D x(s-t) можно использовать в качестве критерия для выбора пиксела. Обозначим эту величину d_i:

так как r = x_i-1, q = y_i-1, получаем:

Известно, что x_I - x_i-1=1.

Если d_i >= 0, то выбираем T_i, тогда

Если d_i <0, то выбираем S_i, тогда

Таким образом, мы получили итеративную формулу для вычисления критерия d_i.
Начальное значение d₁=2D y-D x.

Можно построить блок схему алгоритма:

рис. 2.4.2

Линейная интерполяция по яркости при построении отрезка по алгоритму Брезенхема получается параметрическим способом, т.е. , где N – длина отрезка в пикселях.

2.5. Алгоритмы построения окружности.

Рассмотрим окружность с центром в начале координат, для которой x²+y²=R², или в параметрической форме:

1. x=R× cos(a);
2. y=R× sin(a).

То есть легко написать программу рисования окружности:

void Circle (int x, int y, int R, int color)
{

int a;
int x1;
int x2;
int y1;
int y2;
x2=x+R;
y2=y;
for (int a=1; a<=360; a++)
{

x1=x2; y1=y2;
x2=round(R*cos(a))+x;
y2=round(R*sin(a))+x;
Line (x1, y1, x2, y2, color);

}

}

рис. 2.5.1.

Если воспользоваться симметрией окружности, то можно построить более эффективный алгоритм. Если точка (x, y) лежит на окружности, то легко вычислить семь точек, принадлежащих окружности, симметричных этой. То есть, имея функцию вычисления значения y по x=0..R/SQRT(2) для построения дуги от 0⁰ до 45⁰. Построим процедуру, которая будет по одной координате ставить восемь точек, симметричных центру окружности.

void Circle_Pixel(int x0, int y0, int x, int y, int color);
{

putpixel(x0 + x, y0 + y, color);
putpixel(x0 + y, y0 + x, color);
putpixel(x0 + y, y0 - x, color);
putpixel(x0 + x, y0 - y, color);
putpixel(x0 - x, y0 - y, color);
putpixel(x0 - y, y0 - x, color);
putpixel(x0 - y, y0 + x, color);
putpixel(x0 - x, y0 + y, color);

}

Таким образом можно написать программу рисование окружности по точкам:

void Circle (int x0, int y0, int R, int color)
{

for (int x=0; x<=R/sqrt(2); x++)
{

int y = (int)(sqrt(sqr(R)-sqr(x)));
Circle_Pixel (x0, y0, x, y, color);

}

}

2.6. 2.6. Алгоритм Брезенхема генерации окружности

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

рис. 2.6.1

Будем рассматривать сегмент окружности, соответствующий x=x₀.. x₀+R/sqrt(2). На каждом шаге выбираем точку, ближайшую к реальной окружности. В качестве ошибки возьмем величину D(P_i)=(x²_i+ y²_i) – R².

Рассмотрим рис. 2.6.1, на котором показаны различные возможные способы прохождения истинной окружности через сетку пискселов. Пусть пиксел P_i-1 уже найден как ближайший к реальной изображенной окружности, и теперь требуется определить, какой из пикселов должен быть установлен следующим: T_i или S_i. Для этого определим точку, которой соответствует минимальная ошибка:

D(S_i)=((q+1)²+ p²) – R², D(T_i)=((q+1)²+ (p+1)²) – R².

Если |D(S_i)| < |D(T_i)|, то выбираем S_i, иначе - T_i. Введем величину d_i = |D(S_i)| - |D(T_i)|, тогда S_i выбирается при d_i < 0, иначе выбирается T_i. Если рассматривать только часть окружности, дугу от 0⁰ до 45⁰, то D(S_i) > 0 так как точкаS_i лежит за пределами окружности, а D(T_i) < 0, так как T_i находится внутри окружности, поэтому
d_i = D(S_i) + D(T_i).

Алгебраические вычисления, аналогичные тем, которые проводились для линии, приводят к результату:

d₁=3-2R.

Если выбираем S_i (когда d_i < 0),

D_i=4x_i-1+6;

если выбираем T_i (когда d_i >=0),

D _i=4(x_i-1 * y_i-1) +10.

Блок-схема этого алгоритма (рис. 2.6.2).

рис. 2.6.2

Алгоритм хорош тем что отсутствуют операции с плавающей точкой, а также операции деления и извлечения корня.

2.7. Отсечение по полю вывода

На рис.2.7.1. показана плоская сцена и отсекающее окно регулярной формы. Окно задается левым (Л), правым (П), верхним (В) и нижним (Н) двумерными ребрами. Регулярным отсекающим окном является прямоугольник, стороны которого параллельны осям координат объектного пространства или осям координат экрана. Целью алгоритма отсеченияявляется определение тех точек, отрезков или их частей, которые лежат внутри отсекающего окна. Эти точки, отрезки или их части остаются для визуализации. А все остальное отбрасывается.

Поскольку в обычных сценах или картинках необходимо отсекать большое число отрезков или точек, то эффективность алгоритмов отсечения представляет особый интерес. Во многих случаях подавляющее большинство точек или отрезков лежит целиком внутри или вне отсекающего окна. Поэтому важно уметь быстро отбирать отрезки, подобные аb, или точки, подобные р, и отбрасывать отрезки, подобные ij, или точки, подобные q на рис.2.7.1.

Точки, лежащие внутри отсекающего окна, удовлетворяют условию:

x_л <= х <= x_п и у_н <= у <= у_в.

рис. 2.7.1.

Знак равенства здесь показывает, что точки, лежащие на границе окна, считаются находящимися внутри него.

Отрезок лежит внутри окна и, следовательно, является видимым, если обе его концевые точки лежат внутри окна, например отрезок ab на рис. 2.7.1. Однако если оба конца отрезка лежат вне окна, то этот отрезок не обязательно лежит целиком вне окна, например отрезок gh на рис. 2.7.1. Если же оба конца отрезка лежат справа, слева, выше или ниже окна, то этот отрезок целиком лежит вне окна, а значит, невидим. Проверка последнего условия устранит все отрезки, помеченные ij на рис. 2.7.1. Но она не устранит ни отрезка gh, который видим частично, ни отрезка kl, который целиком невидим.

Пусть а и b - концы отрезка, тогда можно предложить алгоритм, определяющий все полностью видимые и большинство невидимых отрезков.