Назад | Оглавление | Домой | Далее
Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки A(xa, ya) и B(xb, yb). Для простоты будем считать, что
0 ≤ yb – ya ≤ xb – xa . Тогда отрезок описывается уравнением:
| y = ya + |
|
(x–xa), x Є [xa, xb] или y = kx + b. |
Отсюда получаем простейший алгоритм растрового представления отрезка:
void line(int xa, int ya, int xb, int yb, int color)
{
double k = ((double)(yb – ya)) / (xb – xa);
double b = ya – k * xa;
for (int x = xa; x <= xb; x++)
putpixel(x, (int)(k * x + b), color);}
Вычислений значений функции y = kx + b можно избежать, используя в цикле рекуррентные соотношения, так как при изменении x на 1 значение y меняется на k:
void line(int xa, int ya, int xb, int yb, int color)
{
double k = ((double)(yb – ya)) / (xb – xa);
double y = ya;
for (int x = xa; x <= xb; x++, y += k)
putpixel(x, (int)y, color);
}
Приведенные простейшие пошаговые алгоритмы построения отрезка имеют ряд недостатков:
1. Выполняют операции над числами с плавающей точкой, а желательно было бы работать с целочисленной арифметикой;
2. На каждом шаге выполняется операция округления, что также снижает быстродействие.
Эти недостатки устранены в следующем алгоритме Брезенхейма.
Как и в предыдущем случае, будем считать, что тангенс угла наклона отрезка принимает значение в диапазоне от 0 до 1. Рассмотрим i-й шаг алгоритма (рис. 2.3). На этом этапе пиксель Pi-1 уже найден как ближайший к реальному отрезку. Требуется определить, какой из пикселов (Ti или Si) будет установлен следующим.
Рис. 2.3. i-й шаг алгоритма Брезенхейма
В алгоритме используется управляющая переменная di, которая на каждом шаге пропорциональна разности между S и T. Если S < T, то Si ближе к отрезку, иначе выбирается Ti.
Пусть изображаемый отрезок проходит из точки (x1, y1) в точку (x2, y2). Исходя из начальных условий, точка (x1, y1) ближе к началу координат. Тогда перенесем оба конца отрезка с помощью преобразования T(–x1, –y1), так чтобы первый конец отрезка совпал с началом координат. Начальной точкой отрезка стала точка (0, 0), конечной точкой – (dx, dy), где dx = x2 – x1, dy = y2 – y1 (рис. 2.4).
Рис. 2.4. Вид отрезка после переноса в начало координат
Уравнение прямой в этом случае будет иметь вид:
| y=x |
 |
. |
Обозначим координаты точки Pi-1 после переноса через (r, q). Тогда Si = (r+1, q) и Ti = (r+1, q+1).
Из подобия треугольников на рис. 2.4 можно записать, что
|
|
= |
 |
. |
Выразим S:
| S = |
|
(r + 1) – q. |
T можно представить как T = 1 – S. Используем предыдущую формулу
| T = 1 – S = 1 – |
|
(r + 1) – q. |
Найдем разницу S – T:
| S – T = |
|
(r + 1) – q – 1 + |
|
(r + 1) – q = 2 |
|
(r + 1) – 2 q – 1. |
Помножим левую и правую часть на dx:
dx (S – T) = 2 dy (r + 1) – 2 q dx – dx = 2 (r dy – q dx) + 2 dy – dx.
Величина dx положительная, поэтому неравенство dx (S – T) < 0 можно использовать в качестве проверки при выборе Si. Обозначим di = dx (S – T), тогда
di = 2 (r dy – q dx) + 2 dy – dx.
Поскольку r = xi-1 и q = yi-1, то
di = 2 xi-1 dy –2 yi-1 dx + 2 dy – dx.
Прибавляя 1 к каждому индексу найдем di+1:
di+1 = 2 xi dy –2 yi dx + 2 dy – dx.
Вычитая di из di+1 получим
di+1 – di = 2 dy (xi – xi-1) – 2 dx (yi – yi-1).
Известно, что xi – xi-1 = 1, тогда
di+1– di = 2 dy – 2 dx (yi – yi-1).
Отсюда выразим di+1:
di+1 = di + 2 dy – 2 dx (yi – yi-1).
Таким образом, получили итеративную формулу вычисления управляющего коэффициента di+1 по предыдущему значению di. С помощью управляющего коэффициента выбирается следующий пиксель – Si или Ti.
Если di ≥ 0, тогда выбирается Ti и yi = yi–1 + 1, di+1 = di +2 (dy – dx). Если di < 0, тогда выбирается Si и yi = yi–1 и di+1 = di +2 dy.
Начальные значения d1 с учетом того, что (x0, y0) = (0, 0),
d1 = 2 dy – dx.
Преимуществом алгоритма является то, что для работы алгоритма требуются минимальные арифметические возможности: сложение, вычитание и сдвиг влево для умножения на 2.
Реализация этого алгоритма выглядит следующим образом:
void MyLine(int x1, int y1, int x2, int y2, int c)
{
int dx, dy, inc1, inc2, d, x, y, Xend;
dx = abs(x2 - x1);
dy = abs(y2 - y1);
d = dy << 1 - dx;
inc1 = dy << 1;
inc2 = (dy - dx) << 1;
if (x1>x2)
{
x = x2;
y = y2;
Xend = x1;
}
else
{
x = x1;
y = y1;
Xend = x2;
};
putpixel(x, y, c);
while (x < Xend)
{
x++;
if (d < 0) d = d + inc1;
else
{
y++;
d = d + inc2;
};
putpixel(x, y, c);
};
}
Если dy > dx, то необходимо будет использовать этот же алгоритм, но пошагово увеличивая y и на каждом шаге вычислять x.
Назад | Оглавление | Домой | Далее