Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Растровое представление отрезка. Алгоритм Брезенхейма



Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки A(xa, ya) и B(xb, yb). Для простоты будем считать, что

0 ≤ yb – yaxb – 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.

Пусть изображаемый отрезок проходит из точки (x 1, y 1) в точку (x 2, y 2). Исходя из начальных условий, точка (x 1, y 1) ближе к началу координат. Тогда перенесем оба конца отрезка с помощью преобразования T(­­­­­­– x 1, –y 1), так чтобы первый конец отрезка совпал с началом координат. Начальной точкой отрезка стала точка (0, 0), конечной точкой – (dx, dy), где dx = x 2 – x 1, dy = y 2 – y 1 (рис. 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.

Найдем разницу ST:

ST = (r + 1) – q – 1 + (r + 1) – q = 2 (r + 1) – 2 q – 1.

Помножим левую и правую часть на dx:

dx (ST) = 2 dy (r + 1) – 2 q dx – dx = 2(r dy – q dx) + 2 dy – dx.

Величина dx положительная, поэтомунеравенство dx (ST) < 0 можно использовать в качестве проверки при выборе Si. Обозначим di = dx (ST), тогда

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+ 1di = 2 dy (xi xi- 1) – 2 dx (yiyi- 1).

Известно, что xixi- 1 = 1, тогда

di+ 1di = 2 dy – 2 dx (yiyi- 1).

Отсюда выразим di+ 1:

di+ 1 = di + 2 dy – 2 dx (yiyi- 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.

Начальные значения d 1 с учетом того, что (x 0, y 0) = (0, 0),

d 1= 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 > d x, то необходимо будет использовать этот же алгоритм, но пошагово увеличивая y и на каждом шаге вычислять x.

2.1.2. Растровая развёртка окружности

Существует несколько очень простых, но не эффективных способов преобразования окружностей в растровую форму. Например, рассмотрим для простоты окружность с центром в начале координат. Ее уравнение записывается как x 2 + y 2 = R 2. Решая это уравнение относительно y, получим

y = ± .

Чтобы изобразить четвертую часть окружности, будем изменять x с единичным шагом от 0 до R и на каждом шаге вычислять y. Вторым простым методом растровой развертки окружности является использование вычислений x и y по формулам x = R cos α, y = R sin α при пошаговом изменении угла α от 0° до 90°.

Для упрощения алгоритма растровой развёртки стандартной окружности можно воспользоваться её симметрией относительно координатных осей и прямых y = ± x; в случае, когда центр окружности не совпадает с началом координат, эти прямые необходимо сдвинуть параллельно так, чтобы они прошли через центр окружности. Тем самым достаточно построить растровое представление для 1/8 части окружности, а все оставшиеся точки получить симметрией (см. рис. 2.5).

Рис. 2.5. Восьмисторонняя симметрия

Рассмотрим участок окружности из второго октанта x Є [0, R / ]. Далее опишем алгоритм Брезенхейма для этого участка окружности.

На каждом шаге алгоритм выбирает точку Pi (xi, yi), которая является ближайшей к истинной окружности. Идея алгоритма заключается в выборе ближайшей точки при помощи управляющих переменных, значения которых можно вычислить в пошаговом режиме с использованием небольшого числа сложений, вычитаний и сдвигов.

Рассмотрим небольшой участок сетки пикселов, а также возможные способы (от A до E) прохождения истинной окружности через сетку (рис. 2.6).

Предположим, что точка Pi- 1была выбрана как ближайшая к окружности при x = xi- 1. Теперь найдем, какая из точек (Si или Ti) расположена ближе к окружности при x = xi- 1 + 1.

Рис. 2.6. Варианты прохождения окружности через растровую сетку

Заметим, что ошибка при выборе точки Pi (xi, yi) была равна

D(Pi) = (xi 2 + yi 2) – R 2.

Запишем выражение для ошибок, получаемых при выборе точки Si или Ti:

D(Si) = [(xi-1+ 1)2 + (yi-1)2] – R2;

D(Ti) = [(xi-1+ 1)2 + (yi-1 – 1)2] – R 2.

Если | D(Si) | ≥ | D(Ti) |, то Ti ближе к реальной окружности, иначе выбирается Si.

Введем di = | D(Si) | – | D(Ti) |.

Ti будет выбираться при di ≥ 0, в противном случае будет устанавливаться Si.

Опуская алгебраические преобразования, запишем di и di+ 1 для разных вариантов выбора точки Si или Ti.

D 1 = 3 – 2 R.

Если выбирается Si (когда di < 0), то di+ 1 = di + 4 xi-1 + 6.

Если выбирается Ti (когда di ≥ 0), то di+ 1 = di + 4 (xi- 1yi- 1) + 10.

Существует модификация алгоритма Брезенхейма для эллипса.





Дата публикования: 2014-11-03; Прочитано: 371 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.013 с)...