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

Растровое представление отрезка.

Процесс последовательной инициализации множества пикселов, изображающего отрезок прямой, называется разверткой отрезка, а само множество пикселов - растровым представлением отрезка. Чтобы строить отрезки, надо знать способ (алгоритм) генерации этого множества. Обычно отрезок строится по координатам концов. Следовательно надо знать, какие точки растра последовательно инициировать, чтобы получить полностью отрезок. Решение задачи неоднозначно. Можно строить 4-и 8-связное представление. Возможны и другие растровые модели. Все зависит от того, какими свойствами требуется наделить полученный образ.

Очевидное решение - инициировать последовательно все точки растра, квадратные окрестности которых пересекают данный отрезок. Результатом является 4-связная растровая развертка отрезка. 8-связная решетка включает те точки растра, боковые стороны квадратных окрестностей которых пересекаются с отрезком.

4-связная развертка отрезка 8-связная развертка отрезка

Пусть отрезок имеет координаты концов и . Уравнение прямой . Для простоты предположим, что угловой коэффициент (не отрицателен и не превосходит 1), т.е. . Уравнение отрезка имеет вид , где . Простейшая программа 4-связного представления - rastr/bresenh/ex1.cpp.

include <conio.h>

#include <graphics.h>

#include <process.h>

#include <stdio.h>

#include <math.h>

int round(int x)

{

if (abs(x-(int)x)-0.5)

x = floor(x);

else

x = ceil(x);

return(x);

}

void Line (int x1, int y1, int x2, int y2, int color)

{

double k = ((double)(y2-y1))/(x2 - x1);

double b = y1 - k*x1;

for (int x = x1; x <= x2; x++)

putpixel (x, round (k*x + b), color);

}

main ()

{

int driver = DETECT;

int mode;

int res;

initgraph (&driver, &mode, "c:\\tcpp\\bgi");

if ((res = graphresult ())!= grOk)

{

printf("\nGraphics error: %s\n", grapherrormsg (res));

exit (1);

}

int x1 = 20,

y1 = 20,

x2 = 300,

y2 = 70;

Line (x1, y1, x2, y2, GREEN);

getch ();

closegraph ();

}

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

А а

В 1965 г. Брезенхейм (Bresenham) предложил простой целочисленный алгоритм растрового построения отрезка. Сначала он использовался в графопостроителях. Алгоритм основан на том, что при построении всегда берется ближайший по вертикали пиксел, т.е. точка, ближайшая к исходной прямой. Очевидная оценка близости: если отклонение исходной прямой по оси ординат от текущего значения превышает 0.5, увеличиваем координату y на 1, корректируем текущее значение отклонения. Чтобы перейти к целочисленным расчетам, изменяют "масштаб", умножая отклонение и приращение по оси у на некоторое целое . В качестве естест-

венно выбирается величина , т.е. отклонение вычисляется как

. Если , значение увеличивается на 1,

В

b иначе - не изменяется. при этом уменьшается на "масштабирован-

ную" единицу, (вместо пишем ) или увеличивается на величину "масштабированного" приращения (вместо пишем ).

Пример программы из [ 1 ] для 8- и 4-связной развертки отрезка - rastr\bresenh\line1.cpp. Для наглядности точки увеличены.

#include <conio.h>

#include <graphics.h>

#include <process.h>

#include <stdio.h>

#define putpixel DrawPixel

void DrawPixel (int x, int y, int color)

{

setfillstyle(1,color); // заполнение

fillellipse (10 * x, 10 * y, 5, 5);

}

// simplest Bresenhames alg. 0 <= y2 - y1 <= x2 - x1

void Line (int x1, int y1, int x2, int y2, int color)

{

int dx = x2 - x1;

int dy = y2 - y1;

int d = (dy << 1) - dx; // << - сдвиг влево на 1 поз.,

int d1 = dy << 1; // умножение на 2

int d2 = (dy - dx) << 1;

putpixel (x1, y1, color);

for (int x = x1 + 1, y = y1; x <= x2; x++)

{

if (d > 0)

{

d += d2;

y += 1;

}

else

d += d1;

putpixel (x, y, color);

}

}

void Line4 (int x1, int y1, int x2, int y2, int color)

{

int dx = x2 - x1;

int dy = y2 - y1;

int d = 0;//(dy << 1) - dx;

int d1 = dy << 1;

int d2 = - (dx << 1);

putpixel (x1, y1, color);

for (int x = x1, y = y1, i = 1; i <= dx + dy; i++)

{

if (d > 0)

{

d += d2;

y += 1;

}

else

{

d += d1;

x += 1;

}

putpixel (x, y, color);

}

}

main ()

{

int driver = DETECT;

int mode;

int res;

initgraph (&driver, &mode, "c:\\tcpp\\bgi");

if ((res = graphresult ())!= grOk)

{

printf("\nGraphics error: %s\n", grapherrormsg (res));

exit (1);

}

int x1 = 1,

y1 = 1,

x2 = 20,

y2 = 7;

Line (x1, y1, x2, y2, WHITE);

Line4 (x1 + 30, y1, x2 + 30, y2, GREEN);

getch ();

closegraph ();

}

До сих пор рассматривался случай в уравнении прямой . Для случая переменные x и y меняются местами. Общий случай - rastr\bresenh\line2.cpp. Из программы видно, что в функции line() библиотеки BGI использован 8-связный алгоритм Брезенхейма.

#include <conio.h>

#include <graphics.h>

#include <process.h>

#include <stdio.h>

#include <stdlib.h>

void Line (int x1, int y1, int x2, int y2, int color)

{

int dx = abs (x2 - x1);

int dy = abs (y2 - y1);

int sx = x2 >= x1? 1: -1;

int sy = y2 >= y1? 1: -1;

if (dy <= dx)

{

int d = (dy << 1) - dx;

int d1 = dy << 1;

int d2 = (dy - dx) << 1;

putpixel (x1, y1, color);

for (int x = x1 + sx, y = y1, i = 1; i <= dx; i++, x += sx)

{

if (d > 0)

{

d += d2;

y += sy;

}

else

d += d1;

putpixel (x, y, color);

}

}

else

{

int d = (dx << 1) - dy;

int d1 = dx << 1;

int d2 = (dx - dy) << 1;

putpixel (x1, y1, color);

for (int x = x1, y = y1 + sy, i = 1; i <= dy; i++, y += sy)

{

if (d > 0)

{

d += d2;

x += sx;

}

else

d += d1;

putpixel (x, y, color);

}

}

}

main ()

{

int driver = DETECT;

int mode;

int res;

initgraph (&driver, &mode, "c:\\tcpp\\bgi");

if ((res = graphresult ())!= grOk)

{

printf("\nGraphics error: %s\n", grapherrormsg (res));

exit (1);

}

int x1 = 501,

y1 = 100,

x2 = 150,

y2 = 301;

Line (x1, y1, x2, y2, WHITE);

getch ();

setcolor (GREEN);

line (x1+20, y1+20, x2+20, y2+20);

getch ();

closegraph ();

}

Дата добавления: 2014-01-11