11. Основы методов устранения ступенчатости. Алгоритм Брезенхема с устранением ступенчатости. Алгоритм Ву.

Методы устранения ступенчатости

Рассмотреть пиксель не как математическую точку, а как некоторую область. Для этого вводится несколько оттенков цвета, что дает возможность "размыть" краевые пиксели отрезка.

Алгоритм Брезенхема с устранением ступенчатости

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

Отрезок, тангенс угла наклона которого лежит в диапазоне (0, 1), может пересечь 1 или 2 пикселя.

.

Рассмотрим первый случай:

Тут искомая площадь - сумма площади прямоугольника (S1) и треугольника (S2):

S = S1 + S2 = Yi * 1 + 1 * m / 2 = Yi + m / 2

Yi - расстояние между нижней левой вершиной пикселя и точкой пересечения отрезка с левой границей отрезка.

Рассмотри второй случай:

Площадь части нижнего пикселя (S4) можем найти как разность площади и площади треугольника S3.

.

где 1 - Yi - длина одного катета, (1 - Yi) / m - длина другого катета

Площадь S5:

Сумма площадей:

В итоге, видим, что в обоих случаях площадь в обоих случаях ищется по одинаковым формулам.
В качестве ошибки, тут используют как раз эту площадь, находящуюся под отрезком.

.

• Если ордината соседнего пикселя не увеличивается, то площадь, находящаяся под отрезком увеличивается на величину площади прямоугольника со сторонами 1 и m, то есть e = e + m (случай 1)
• Наооборот (увеличивается на едиинцу), вычитаем единицу (площадь пикселя) e = e + m - 1 (случай 2)
• Т.к. площадь не может быть отрицательной, предложено корректировать величину ошибки путём прибавления к ней величины w = 1 - m
• Начальное значение ошибки e = e - 0.5 + 1 - e = 0.5. Значит, первый пиксель будет высвечиваться с половинной интенсивностью.
• Значение ошибки лежит в диапазоне (0, 1)

Псевдокод алгоритма Брезенхема с устранением ступенчатости

1. Ввод Xн, Yн, Xк, Yк, I - количество уровней интенсивности.
2. Вычисление приращений dX = Xк-Xн и dY = Yк-Yн.
3. Вычисление шага изменения каждой координаты: SX = sign(dX), SY = sign(dY).
4. dX = |dX|, dY = |dY|.
5. m = dY / dX
6. Если m > 1
    6.1.t = dX;
    6.2 dX = dY;
    6.3 dY = t;
    6.4 m = 1/m;
    6.5 obmen = 0, если m < 1, иначе obmen = 1
7. e = I / 2
8. X = Xн, Y = Yн.
9. m = mI, W = I-m.
10. Высвечивание пиксела с координатами (X,Y) интенсивностью E(e).
11. Цикл от i = 1 до i = dX с шагом 1:
    11.1. Если e < W, то
          11.1.1 если obmen = 0, то X = X + SX, иначе Y = Y + SY
          11.1.2 e = e + m.
    11.2 иначе
          11.2.1 X = X + SX, Y = Y + SY, e = e - W.
    11. 3 Высвечивание пикселя с координатами (X,Y) интенсивностью E(e).
12. Конец цикла.

Этот алгоритм лучше всего подходит для очерчивания многоугольников.

Алгоритм ВУ (китайский алгоритм)

• Алгоритм высвечиваются толщиной 2 пикселя
• Суммарная интенсивность двух пикселей высвечиваемая на каждом шаге - постоянна. I1 + I2 = Iconst
• Сглаживание получается за счёт перераспределения интенсивности Iconst между 2 пикселей (на каждом шаге)
• Интенсивность пикселя определяется в зависимости от расстояния между пикселем и точкой, рассматриваемой на идеальном отрезке: чем ближе пиксель расположен к точек на идеальном отрезке, тем больше его интенсивность.
• Горизонтальные и вертикальные линии нетребуют дополнительного сглаживания.

d1 = y(иi) - [y(иi)] - расстояние от нижнего пикселя y(i1), до точки на идеальном отрезке. 
d2 = 1 - d1
I(i1) = Iconst * d2 
I(i2) = Iconst * d1

Следующий вопрос: 12. Двумерное отсечение. Простой алгоритм отсечения отрезка.

Предыдущий вопрос: 10. Алгоритмы заполнения с затравкой. Построчный алгоритм заполнения с затравкой.